MinMax Simple Demonstration for TicTacToe

Question

I have been pulling out my hair trying to figure out how the MinMax algorithm, and hopefully the alpha-beta pruning algorithms work. I'm confused as to the recursion that occurs.

• Firstly, does each intermediate board get scored? or only terminal game boards.
• Secondly, what exactly is being returned? how does the program know where to place the next move? I see that im supposed to return the board score (in tictactoe, -1,0,1) but how does the program know which move should be played next.

I have tried finding a simple C or c++ program to demonstrate this, but I have not had much luck. I am trying to learn this alogrithms I can create a presentation for the rest of my computer programming class.

Thanks a lot! V

Answer 1

Only terminal positions (after quiescence search) are scored. Non-terminal positions compare the score returned by a recursive minimax() call to the best score returned so far. In the case of alpha-beta the returned score is also compared to the alpha value.

The point of minimax is producing a score. Your mistake appears to be thinking that the minimax search function needs to return the best move. It can be coded that way, but it might be simpler for you to instead have a top level loop in another function that executes a move, uses minimax() to produce a score and unexecutes the move. Keep track of the move with the best score and return that move when the loop completes or the time to choose a move runs out.