# How to utilize miniMax algorithm in Checkers game

I am sorry...as there are too many articles about it.But I can't simple get this.

I am confused in the implementation of AI. I have generated all possible moves of computer's type pieces. Now I can't decide the flow. Whether I need to start a loop for the possible moves of each piece and assign score to it.... or something else is to be done.

Kindly tell me the proper flow/algorithm for this. Thanks

UPDATE:

MiniMax code

Now I coded the algorithm but not getting correct moves. Please help me find out the logical error.

One useful thing to understand about minimax for a game like Checkers is that it's traditionally viewed (to first approximation) as symmetric - this means that both players can share the same evaluation function, but simply with the signs flipped, or put another way that it's a zero-sum game: if you evaluate the position as being 4/10ths of a checker in your favor, you know that your opponent's evaluation will be -4/10ths of a checker. This means that you can use the same loop structure for both sides and simply multiply by a 'sign flip', rather than having to have different control structures for min and max (or switching within the loop). In simplest form, the minimax can be done as a classic recursive function, with a termination once you've reached your maximum depth:

float EvaluatePositionRecursive(int depth, Board curBoard, float signFactor)
{
if ( depth >= MAX_DEPTH )
return EvaluatePositionStatic(curBoard);
MoveList moves = GenerateMoveList(curBoard);
float posValue = -FLT_MAX;
for (move in moves) do {
Board newBoard = MakeMove(curBoard, move);
float newValue = signFactor*EvaluatePositionRecursive(depth+1, newBoard, -signFactor);
if ( newValue > posValue ) posValue = newValue;
}
return signFactor*posValue;
}

[...]

val = EvaluatePositionRecursive(0, thisBoard, 1.0f);


This code has the property/requirement that the value returned from the EvaluatePosition functions will always be in terms of one side's evaluation - that is, a positive value of EvaluatePositionRecursive will always be better for (e.g.) black; this is why it (re-)multiplies by signFactor before returning its value.

Note that there's a lot that this (pseudo)code doesn't do: it doesn't do any alpha-beta pruning, it doesn't use transposition tables to cut down on re-evaluating the same position, and it doesn't do any sort of quiescence search or similar adaptive-depth techniques to avoid misevaluating positions where a forced-capture is on the horizon of your search. What's more, for practical considerations you might not want to use explicit recursion for the minimax, and instead maintain a stack yourself, and there are plenty of other object-management optimizations that you would want to make for a practical implementation of the algorithm (rather than a quick-and-dirty one). Still, this code should show the core of the algorithm: to evaluate a position, evaluate all of the subpositions from the current side's point of view, pick the 'best', and return that value.

• So, each valid move is abstratcly performed and its score is evaluated. There must ba a track for all the scores. In the end, the move which gives the best score is performed. Am I right? – engineer Jun 27 '12 at 6:12
• Exactly - what I've done here is show you the (abstract) score evaluation function. I can clean up the 'calling code' to show how the move is chosen, but it's just as you say. – Steven Stadnicki Jun 27 '12 at 6:40
• Thanks alot. Now I am pretty clear about what is to be done. If I get stuck some where, I will seek your advice. – engineer Jun 27 '12 at 7:24