Minimax Search

When you have a game tree and you want to determine the best move for the computer opponent , you do what is called a minimax search . The idea is this: When O makes a move, he is trying hard to win as O, but when X makes a move, even though the computer is pretending to make the move, X must pretend to be trying hard to win. That means we must be able to simulate playing as either the computer or the human. Look at the version of our tic tac toe tree in Figure 10.11.

Figure 10.11: The search tree is divided into layers named min and max. These min and max layers alternate.

Notice the layers in Figure 10.11. They are labeled min and max, but they are associated with player X and player O. When player O makes a move, that level of the game tree is called a max level. When X moves, that layer is called a min layer. In this way, the layers of your game tree alternate between min and max.

We want to associate a value with any given board position. If the board is a win for X, we give it a value of negative infinity. If the board is a win for O, we give it a value of positive infinity.

In the game tree, player O tries to reach positive infinity where he wins. In other words, he tries to maximize the value of the board. Player X, on the other hand, wants to see the board become negative infinity where he wins. In that way, he is trying to minimize the board's value.

Searching a game tree trying to maximize player O moves and minimize player X moves is called a minimax search . It's the basis for all turn -based games , including chess, checkers, mancala, backgammon, and go.