2 views

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.

by (108k points)

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.