Minimax search: how to print the path from the chosen next move to the leaf

Question

Confusing title. I'll try to elaborate: I have an AI chess game that uses minimax search to generate the computer's next move. After going down the minimax tree to a chosen depth (say 5), it finally finds the next best move to take. For my own testing purposes, I would like to be able to print out this next best move (represented as a chess board configuration), but also the following 4 moves that it used to determine the score for that next move. That is, the path of the best choices at each of the lower levels in the minimax tree, starting with the top node that was eventually chosen to be the best next move. Any ideas?

Answer 1

You want to determine the Principal Variation.

The Principal variation (PV) is a sequence of moves that programs consider best and therefore expect to be played.

-- Chess Programming Wiki

My implementation of a game engine uses the transposition tabe to determine the PV. To print the PV the program does following steps:

1. move = the best move determined with the last search
2. Print move
3. Make move
4. Get the transposition table entry of the new board
5. Is the transposition table entry exact?
   • Yes: move = move stored in the transposition table entry. Go to step 2.
   • No: Undo moves. Go to step 6.
6. End