TAOCP 7.1.2 Exercise 66
The strategy in exercise 65 is a refinement of the optimal-play construction from (47)–(56), where each position is assigned a value under minimax evaluation: win, draw, or loss.
Section 7.1.2: Boolean Evaluation
Exercise 66. [20] [20] Criticize the moves chosen in exercise 65. Are they always optimum?
Verified: yes
Solve time: 1m31s
Solution
The strategy in exercise 65 is a refinement of the optimal-play construction from (47)–(56), where each position is assigned a value under minimax evaluation: win, draw, or loss. The modified procedure prescribes moves that preserve the optimal minimax value, typically by selecting moves that avoid immediate loss and maintain positions classified as non-losing.
From the standpoint of game-theoretic correctness, every move produced by the strategy is consistent with optimal play in the strict minimax sense. In particular, whenever the current position has value “draw” under perfect play, the strategy never selects a move that converts it into a forced loss, and whenever a forced win exists it selects a move that preserves win status.
However, optimality in the sense of exercise 66 depends on a stronger criterion than minimax value. Among moves that preserve the same minimax value, the construction in exercise 65 does not enforce a secondary optimization, such as minimizing the number of moves to a win, maximizing the speed of conversion to a win, or selecting lexicographically canonical moves among symmetric alternatives. The strategy only guarantees that the resulting value is not worsened, not that the resulting continuation is extremal within the class of optimal continuations.
In particular, in positions with multiple winning moves, some choices may lead to strictly longer win-lengths in the induced game tree even though all are winning in the minimax sense. Similarly, in drawn positions with multiple legal moves preserving a draw, different choices can produce continuations with different depths before termination, and the strategy does not distinguish among them. Since the algorithm does not incorporate a tie-breaking rule based on depth or move economy, it cannot guarantee optimality with respect to shortest-win or fastest-draw criteria.
Therefore, the moves in exercise 65 are not always optimal in the refined sense of minimizing game-tree depth or move count to terminal outcome. They are optimal only with respect to the coarse minimax classification, not with respect to secondary optimization criteria among equally valued moves. ∎