Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.