Adversarial Search and Games Questions and Answers

Answer: A

A ply is a single player's move, so what a chess player calls a move is two plies, and search depths are always quoted in plies to avoid the ambiguity. Full moves, cutoff depth and complete lines are different notions. Precision here matters because a program searching ten plies is looking five moves ahead in the everyday sense, and confusing the two doubles or halves every estimate of a program's strength.

Answer: B

The minimax value is computed by backing up terminal utilities, with each player choosing the successor best for themselves, so it presumes optimal play by both sides. Against a weak opponent a different move might score better, but minimax guarantees the value against any opponent. Averaging belongs to expectimax, direct evaluation is the leaf estimate, and luck belongs to games of chance. A value defined by an assumption is only as useful as the assumption, which is why the assumption is stated explicitly.

Answer: C

Assuming the strongest reply gives a lower bound on what the player can achieve, so the move chosen is safe whatever the opponent does. Modelling a weaker opponent could score more against that opponent and worse against a better one. Ease of computation is not the argument, real opponents err constantly, and pruning is a separate technique. Choosing a criterion that is robust to the opponent's behaviour, rather than optimal against a guess about it, is a defensible conservative choice.

Answer: D

In a zero sum game the utilities of the two players always add to a constant, so a single number describes the position from both points of view and minimax applies directly. Chess, draughts and go are of this kind. Zero payoffs, forced draws and move counts are different properties. Games that are not zero sum admit cooperation and require a payoff for each player, which changes the algorithms substantially and is why the restriction is stated.

Answer: A

Alpha is a lower bound on the value the maximiser has already secured elsewhere in the tree, and beta is the corresponding upper bound for the minimiser. When a node's value is shown to fall outside the window between them, further exploration of it cannot affect the result and is abandoned. Depth and current evaluation are different quantities. Two bounds carried down the tree, and used to prove that a subtree cannot matter, is the whole of the technique.

Answer: B

A branch is abandoned as soon as it is proved that the value at the root is already determined regardless of what the branch contains, which happens when a minimiser finds a value at or below alpha, or a maximiser one at or above beta. Low evaluations, depth limits and equal values are unrelated conditions. Pruning that is provably safe, changing the search's cost but not its result, is a different and stronger thing than pruning by heuristic judgement.

Answer: C

Alpha beta prunes only branches proved irrelevant, so the value and the chosen move are identical to those a full minimax search would return. It changes only the effort. That distinguishes it sharply from forward pruning techniques, which discard branches on suspicion and do change the result. A technique that is free in the sense of costing nothing in quality deserves to be used always, which is exactly the status alpha beta has.

Answer: D

Taking the square root of the branching factor gives:

\[ \sqrt{36} = 6 \]

so the effective branching factor falls to 6, which means the same effort searches twice the depth. For chess, with about thirty five legal moves, that is the difference between a weak program and a strong one. Halving the exponent is a far larger gain than any constant factor, which is why move ordering receives so much attention.

Answer: A

Examining the best move first establishes a strong bound immediately and allows everything else to be cut, while examining the worst first prunes nothing at all. Perfect ordering gives the square root improvement and random ordering gives roughly the three quarters power. Depth, evaluation quality and move count matter but do not control the pruning. That an algorithm's benefit depends entirely on a heuristic choice made outside it is unusual and it makes move ordering a first class concern.

Answer: B

A move that produced a cutoff in a sibling position is likely to do so again, so trying it early improves the ordering cheaply. Capture ordering and the history heuristic serve the same purpose by different means. Abandoning lines and shortest wins are different ideas. Reusing information gathered elsewhere in the tree, at almost no cost, is characteristic of the practical machinery that turns a textbook algorithm into a competitive program.