How to adapt my Minimax search tree to deal with no term based game?

Question

I have to do a project where we need to implement a mancala board game, and then also implement the AI for it.

We have been instructed that we need to modify or change a minimax tree to be able to work with mancala as in the game it is possible for a player to have multiple turns in a row.

I have implemented my game logic and GUI already, But now before i start with the AI I would like to try and get some idea on the theory behind it. I have searched on the net for non-turn based minimax trees and I can't seem to find anything. But i have seen many people talking about using minimax for mancala.

Now I understand the normal minimax tree and how each level alternates between a minimum node and a maximum node. With the tree that I need now, would I say: min > max > max > min > max if the 2nd player got TWO turns?

We also need to be able to specify the given ply-depth of the Minimax tree. We also need to do alpha-beta pruning, but that's for later on, once I have a tree.

Answer 1

Your main problem is that you have been shown how to use minimax in a situation where max/min go in a cycle and now you have a game where sometimes one player can do many moves in a row. Where you initialize the minimax function with max/min and then it constantly changes. In your state, you only need to add one tiny check.

function minimax(node, depth, maximizingPlayer)

    if depth = 0 or the node is a terminal node

        return the heuristic value of a node

    if maximizingPlayer

        bestValue := -∞

        for each child of node

            # here is a small change

            if freeTurn(child):

               isMax := TRUE

            else:

               isMax := FALSEval := minimax(child, depth - 1, isMax)

            bestValue := max(bestValue, val)

        return bestValue

    else

        bestValue := +∞

        for each child of node

            # here is a small change

            if freeTurn(child):

               isMax := FALSE

            else:

               isMax := TRUEval := minimax(child, depth - 1, isMax)

            bestValue := min(bestValue, val)

        return bestValue

If you wish to learn about Artificial Intelligence then visit this Artificial Intelligence Course.