Alpha-beta pruning consecutive moves for same player

Question

I have implemented alpha-beta pruning for Checkers and thought I had it working, but found out that the computer does not take multiple jumps in a row (when it has to). For example:

AI does:

O _ _ _ _      _ _ _ _ _

_ X _ X _  ->  _ _ _ X _  (misses a jump because it only does a single move)

_ _ _ _ _      _ _ O _ _

AI should do:

O _ _ _ _      _ _ _ _ O
_ X _ X _  ->  _ _ _ _ _  (sees that it's current turn is not finished, continues)
_ _ _ _ _      _ _ _ _ _

I attempted to fix it by checking the return value of MovePiece, which returns whether or not the player has completed his turn or not, determined by if the move was a jump and if there are further jumps to be made. Based on the return value, it will either run MaxValue/MinValue again (depends on which one it was at when it first saw there were further moves to be made) or continue on in the tree and switch players.

Relevant code (in C#) is as follows (retVal is of a type that contains the Value, Depth, and Move to do):

foreach(var m in moves)
{
    var resultingBoard = board.Clone();

    var moveResult = resultingBoard.MovePiece(m.TypeOfMove,
                                resultingBoard.GetPieceAtPosition(m.OriginalPieceLocation.X,
                                                                  m.OriginalPieceLocation.Y),
                                m.FinalPieceLocation.X, m.FinalPieceLocation.Y);

    var newDepth = currentDepth;

    if(moveResult == TurnResult.NotDone)
    {
        retVal = MaxValue(resultingBoard, ref alphaValue, ref betaValue, color, ref newDepth, ref maxDepth);
    }
    else if(moveResult == TurnResult.Finished)
    {
        newDepth++; 
        retVal = MinValue(resultingBoard, ref alphaValue, ref betaValue, color == PieceColor.Black ? PieceColor.Red : PieceColor.Black, ref newDepth, ref maxDepth);
    }
}

...

However, this results in some...interesting results (first move does nothing but min prunes), even though I thought this would be the correct change to make.

Is making MaxValue/MinValue call itself again with the new move the right thing to do?

Answer 1

The fact that your minimax algorithm needs to "generate" new moves smells (when you need to eat a second piece).

I would try to redesign it - you can do it extending the move (an element in the iterable moves), to make it contain tuples (or a list) of moves, and avoid the TurnResule.NotDone in the minimax algorithm stage.

With this approach - the list moves will be extended beforehand to also contain the move (eat piece,eat piece) in addition to the single move.

---

This solution will make the algorithm much more robust and will allow you future modifications easily.