THE MINIMAX HEURISTIC As a simplified example, consider a checkers program that does a search of depth two (that is, looks two moves into the future) before applying its evaluation function. The situation might look like this: A / \ / \ Computer's move / \ B C / | \ / | \ / | \ / | \ Human's move / | \ / | \ D E F G H I | | | | | | | | | | | | V V V V V V 4 5 6 1 7 -12 Here, the numbers 4, 5, 6, 1, 7, and -12 indicate the estimated desirability of a position from the computer's point of view. The bigger this number is, the more the position favors the computer; that, at least, is the computer's simplifying assumption. This assumption, like most of the assumptions on which heuristics are based, cannot be proved, and is often demonstrably false; nevertheless, the procedure that it gives rise to is often quite a good one. Under the minimax heuristic, the computer further assumes that its adversary will use the same evaluation function as it does, and will make the best move possible for it, resulting in the worst possible position for the computer. Therefore, the computer predicts that if it moves from position A to position B, its opponent will move to position D rather than position E or position F, since the score of D (4) is less than the score of E (5) and the score of (6), indicating that position D is less favorable to the computer than the other two choices. That is, the computer assumes that its opponent will try to minimize the evaluation function. On the other hand, the computer predicts that if it moves from A to C, its opponent will move from C to I, resulting in a position with value -12. Even though the best outcome two steps in the future is position H, with value 7, the computer prudently judges that its best safe move is not to position C but to position B. max(4,-12) = 4 / \ / \ Computer's move / \ min(4,5,6) = 4 min(1,7,-12) = -12 / | \ / | \ / | \ / | \ Human's move / | \ / | \ 4 5 6 1 7 -12 This sort of prudent style of play is called minimax strategy. [Source of example: Mark Brockington.]