Adversarial Search and Games Questions and Answers

Answer: C

Because different move orders reach the same position, storing its computed value avoids searching it again, often saving a large fraction of the tree. It is the graph search explored set applied to games, usually with a hash of the position as the key. Move generation, game records and representation conversion are different structures. Recognising a general technique reappearing in a specialised setting is what allows its known properties and pitfalls to be carried across.

Answer: D

Under a clock, a program must have a move ready at any moment, and the best move from the previous shallower search is an excellent ordering hint for the next, which more than repays the repeated work. Memory saving is a benefit of the underlying depth first search, optimality is unattainable with a cutoff, and the evaluation function is unchanged. An algorithm that solves the deadline problem and the ordering problem simultaneously is exactly what a practical program needs.

Answer: A

With about thirty five moves available and games lasting eighty plies, the tree contains something like ten to the hundred and twenty nodes, beyond any conceivable computation. Search must therefore stop early and estimate. Game length is bounded by the repetition rules, terminal evaluation is trivial, and branching factor variation is minor. A number so large that no improvement in hardware could matter is what forces the whole apparatus of cutoffs and evaluation functions into existence.

Answer: B

Since the search must stop before the game does, the leaf positions are scored by a heuristic combining material, mobility, king safety and structure, and the quality of that estimate largely determines the program's strength. Terminal utilities are exact by definition, move counts are a different quantity, and win probability is a related but distinct formulation used in Monte Carlo methods. An estimate standing in for an unreachable exact value is the same device as a heuristic in ordinary search.

Answer: C

The function is called at every leaf, so it must be cheap, and it must order positions in the same way their true values do, since only the ordering affects the move chosen. Exact values are unobtainable, searching within the evaluation confuses the two mechanisms, and three values would discard the distinctions the search needs. A requirement stated as a correlation rather than an equality is much easier to satisfy and is all that the algorithm actually depends on.

Answer: D

A program may play a series of pointless checks or sacrifices that delay a loss until after the last ply it examines, so the loss disappears from its view and the position looks acceptable. Extending the search selectively in forcing lines is the standard remedy. Endgame evaluation, accuracy decay and time limits are separate matters. A failure caused by stopping the search at a fixed depth, rather than by any error in the evaluation, points at changing where the search stops.

Answer: A

Applying the evaluation function in the middle of an exchange gives nonsense, so the search continues along captures and checks until a stable position is reached and only then evaluates. It costs extra nodes and removes a whole class of blunder. Reduced depth in quiet positions is a different technique, and refusing to evaluate unstable positions without searching them would leave nothing to return. Ensuring that an estimate is applied only where it is valid is a principle that extends well beyond games.

Answer: B

A position in which a queen has just been captured looks winning until the recapture is considered, so evaluating there systematically misjudges by a wide margin. Quiescence search resolves the exchange first. Speed, terminal detection and prediction are separate concerns. An estimator that is accurate on average but badly wrong on an identifiable subset of cases should be prevented from being applied to that subset, which is exactly what quiescence does.

Answer: C

Backgammon and card games contain chance nodes whose value is the expectation over the possible outcomes, so the tree alternates maximising, minimising and averaging layers. Multiplayer games need a vector of utilities, opponent modelling is a separate refinement and non-zero sum games change the backup rule differently. Adding an averaging layer to a minimax tree is a small structural change with large consequences for the search's cost.

Answer: D

An average cannot be bounded from one child alone unless the range of leaf values is known, so the alpha beta argument does not apply directly. Bounding the utilities does permit a limited form of pruning. Successor counts, unbounded utilities and unpredictability are not the obstacle. An algorithmic technique that depends on a maximum or minimum being determined by a single child fails as soon as the backup rule becomes an average, which is a clean example of a technique's assumptions mattering.