Adversarial Search and Games Questions and Answers

Answer: A

Guessing that the value will be close to the previous iteration's and searching with a narrow alpha beta window prunes far more, at the risk of the value falling outside and requiring a re-search. Usually the guess is right and the saving is substantial. Move restriction, targets and progressive widening are different techniques. A gamble that usually pays and whose failure costs only a repeat is a favourable bet, provided the failure is detected rather than silently accepted.

Answer: B

A fail high or fail low means only that the true value lies beyond the window, so the search is redone with the window opened on that side. Using the bound as though it were a value would be wrong. Playing regardless discards the information, and narrowing would make matters worse. Detecting that an optimisation's assumption has failed, and falling back correctly, is what separates a sound optimisation from a source of intermittent errors.

Answer: C

If a player would still be winning after giving the opponent a free move, the position is probably good enough to prune, which saves a great deal at the cost of occasional error. It fails in zugzwang positions where being obliged to move is itself a disadvantage. It is a forward pruning technique and therefore not provably safe. Recognising the exact circumstance in which a heuristic's assumption fails, and disabling it there, is what makes such techniques usable in practice.

Answer: D

The technique rests on the premise that having the move is an advantage, and in zugzwang the player to move is obliged to worsen their own position, so the premise is exactly reversed. Endgames with few pieces are the usual case, and programs disable the technique there. Evaluation reliability, termination and recognisability are separate issues. A heuristic justified by an assumption must be switched off wherever that assumption is known to fail, which requires the assumption to be stated in the first place.

Answer: A

If the move ordering is good, moves tried late are unlikely to be best, so searching them shallowly and re-searching only if they look promising saves a great deal. It is another forward pruning technique whose soundness depends on the ordering being reliable. Endgame move counts, clock management and game phase are different notions. A technique whose safety depends on another component working well creates a coupling that must be remembered when either is changed.

Answer: B

Killer moves, aspiration windows, null move pruning and late move reduction all assume that the program's ordering and evaluation are usually right, and all lose a little correctness in exchange for depth. Only alpha beta itself and transposition tables are provably safe. Memory and branching factor are not the common thread. Recognising that a family of techniques shares one assumption tells you what happens to all of them when that assumption is violated.

Answer: C

Forward pruning trades a small probability of a blunder for a large increase in depth, and empirically the depth is worth far more. The errors are rare and usually inconsequential, which is why every strong program uses such techniques. Values are not systematically biased, searches complete normally, and play becomes faster rather than slower. Accepting a quantified risk in exchange for a measured benefit is an engineering decision rather than a compromise of principle.

Answer: D

The classical architecture is an iteratively deepened alpha beta search, aggressively ordered, with a transposition table, quiescence, selective extensions and reductions, and a tuned evaluation. Modern programs add learned evaluations and, in some games, Monte Carlo tree search. Pure minimax, pure simulation and pure lookup each describe part of the picture. Knowing which components a mature system contains, and why each was added, is more instructive than any one of them alone.

Answer: A

Learned evaluations and move priors have replaced decades of hand tuning, and combined with search they produced superhuman play in chess, shogi and go from self play alone. Search remains essential rather than being replaced, representations are still game specific, and the rules must be known to generate the tree. A component learned rather than written, inside an otherwise classical architecture, is the shape most of the recent advances have taken.

Answer: B

The principal variation begins with the move minimax selected, so its first element is the program's choice and the rest is its expectation of what follows. The previous iteration's best move is used for ordering rather than played, and cutoff counts belong to the killer heuristic. Being able to read a program's output correctly is a small skill that makes its behaviour comprehensible rather than mysterious.