Adversarial Search and Games Questions and Answers

Answer: A

A value obtained from a shallow search must not be reused for a deeper one, and a value cut off by alpha beta is a bound rather than an exact figure, so both facts must be recorded or the search will return wrong answers. Visit counts, move sequences and function identity are unnecessary. A cache that stores results without the conditions under which they are valid is a reliable source of subtle and intermittent errors.

Answer: B

When a node is abandoned because it cannot affect the root, its exact value was never determined and all that is known is that it lies on one side of the window. Storing it as though it were exact corrupts later searches. Evaluation accuracy, transpositions and depth are different issues. Recording what is actually known, rather than what was returned, is the discipline that keeps a caching scheme sound.

Answer: C

The principal variation is the path through the tree along which every player chooses the move minimax says is best, and its first move is what the program plays. Displaying it lets a human check the program's reasoning. Opponent likelihood and game history are different notions. A single line summarising what an entire search concluded is both a debugging aid and the most informative thing a program can show a user.

Answer: D

Seeing that the program expects a particular exchange, and disagreeing with the human reader about it, localises an error to the evaluation or to a specific tactical oversight far more effectively than a bare score does. Node counts, technique usage and timings are performance data rather than reasoning. Exposing the chain of reasoning behind a conclusion, rather than the conclusion alone, is what makes a system's errors diagnosable.

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.