Hi, I am trying implement the Minimax algorithm and am a bit confused. I read about the algorithm here: http://www.brucemo.com/compchess/programming/minmax.htm But no one ever seems to describe how to actually use the MinMax() function. I can't just call MinMax() on my current position because that would simply score that position - that is not what I need - I need to pick the best move to make *from* my current position. So that leads me to think that I must first generate the immediate children of the current position, *then* call MinMax() iteratively on each of them to determine which is the best move to make. Is this line of thinking correct? Thanks! BT

MinMax is a recursive function, in that it calls itself.

i.e.

int MinMax ( Position postion, depth){    if ( depth < MAX_DEPTH)    {       PositionList positionList;       positionList.makeAllPossiblePositions ( position);       for each position in positionList          tempScore = MinMax ( positionList.getNext());          if tempScore > bestScore then bestScore = tempScore      }    else       return Evaluate ( position);     }

So Minmax keeps calling itself until it's looked deep enough.

The above code will not work for many many reasons, but I hope you get the idea. :)

Will

Hi RPGeezus,

Thanks for your reply, but your answer highlights the *exact* problem! The pseudocode that you provided will not determine the move to make given a specific starting position.

I understand recursion - I have a B.S in Computer Science - what I don't understand is:

"Given a starting position, how can MiniMax() be used to determine the best NEXT move to make"?

Thanks,
BT

Yes, you can just treat the first level differently.

MinMax returns a score for the 'Initial' move. You run min-max on each possible move, take the one with the best min-max score.

I'll be a little more explicit. Write a special function to analyze the root node. It will look very similar to minimax, except that it keeps track of which is the best move. Over time that function will become more and more different from your minimax function, when you add initializations, iterative deepening, time control, printing of information on the results of the search as you go, keeping the moves in good order (important once you use alphabeta)...

I hope that helps.

Quote: Original post by alvaro
I'll be a little more explicit. Write a special function to analyze the root node. It will look very similar to minimax, except that it keeps track of which is the best move. Over time that function will become more and more different from your minimax function, when you add initializations, iterative deepening, time control, printing of information on the results of the search as you go, keeping the moves in good order (important once you use alphabeta)...

I hope that helps.

Exactly what Alvaro said.

Here is the modified code...

Position gBestPosition;int MinMax ( Position postion, depth){    if ( depth < MAX_DEPTH)    {       PositionList positionList;       positionList.makeAllPossiblePositions ( position);       for each position in positionList          tempScore = MinMax ( positionList.getNext());              /* -=-=-=-=-=-=-= Remember the best move -=-=-=-=-==-=- */           if (tempScore > bestScore)           bestScore = tempScore             gBestPosition = positionList.current;       endif    }    else       return Evaluate ( position);     }

or, as Alvaro suggested, you could write a function that calls MinMax.


Let us know if you get it working. :)

Will

What people above said, and:

The principle in MiniMax is that it is a searching algorithm that tries to find the best possible moves by associating a child move with a score. The higher score a move has for you, the higher are the chances that a move hierarchy including that move leads to the WIN case for you.

But it is also interesting to note that this algorithm can only be applied to games where there the chance, as in the die roll, has no saying. Another interesting fact to note is that each of the 2 functions in a classic MiniMax algo. correspond to one of the players.

For classic minimax algo and an explanation see:
http://ai-depot.com/LogicGames/MiniMax.html

(try to make a tic-tac-toe algo., that deep you can debug with a little pacience).

Quote: Original post by ttdeath
[...]
But it is also interesting to note that this algorithm can only be applied to games where there the chance, as in the die roll, has no saying.

Well, a small modification to minimax would work for games like parcheesi, by taking the maximum of the scores when player 1 makes a decision, the minimum when player 2 makes a decision and the mean when a die is rolled. What won't work so well in this case is alpha-beta, although some not-too-effective form of it can be written with some effort.