Back

Explore Courses Blog Tutorials Interview Questions
0 votes
1 view
in AI and Deep Learning by (50.2k points)

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.

1 Answer

0 votes
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.

Welcome to Intellipaat Community. Get your technical queries answered by top developers!

28.4k questions

29.7k answers

500 comments

94.1k users

Browse Categories

...