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 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 mini max trees and i cant 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 actually have a tree.

Answer 1

As far as I understood, your main problem is the following: you have been shown how to use minimax in a situation where max / min go in cycle and now you have a game where sometimes one player can do multiple moves in a row.

I will explain you the general approach which works for basically any game, and then I will add a couple of things that can be done differently for mancala.

So the general approach

Standard minimax goes like this:

function minimax(node, depth, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        bestValue := -∞
        for each child of node
            val := minimax(child, depth - 1, FALSE)
            bestValue := max(bestValue, val)
        return bestValue
    else
        bestValue := +∞
        for each child of node
            val := minimax(child, depth - 1, TRUE)
            bestValue := min(bestValue, val)
        return bestValue

Where you initialize the minimax call with max/min and then it constantly changes. In your case you only need to add one tiny check.

function minimax(node, depth, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        bestValue := -∞
        for each child of node
            # here is a small change
            if freeTurn(child):
               isMax := TRUE
            else:
               isMax := FALSE
            val := 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 := TRUE
            val := minimax(child, depth - 1, isMax)
            bestValue := min(bestValue, val)
        return bestValue

Where your function freeTurn returns you whether you have a free turn after your current move. Note that there is no difference for this algorithm whether you can do only 2 moves in a row or 5 moves in a row.

Regarding Mancala

There are many variations of mancala, but the branching factor of the game is pretty small (in the one that I know is <= 6). Now assume that you have three moves A, B, C, D and move C allows you to play one more time. From the position C you can do moves C1, C2. So you can combine them (C + C1, C + C2) and treat them as just one move (small bookkeeping should be done to remember that this is actually two moves). So right now you end up with your min max iterations where you have not 4 but 5 moves: A, B, C + C1, C + C2, D. Actually there is nothing wrong to use this approach for games with bigger branching factor.