Adversarial Search and Games Questions and Answers

Answer: A

In both phases the search would otherwise rely on a heuristic estimate, and substituting prepared or exact values removes that error entirely. The middlegame, where no such resource exists, is where search and evaluation must do the work. Memory rises rather than falls, and the evaluation is simply not consulted there. Using exact knowledge wherever it is affordable, and estimating only where it is not, is the division of labour every mature system arrives at.

Answer: B

A program with a fixed total time must decide whether the current position deserves more than its share, spending longer on critical positions and moving quickly in simple ones. It is a metareasoning problem: deciding how much to compute is itself a decision. Hardware, clock synchronisation and cutoff depth are different concerns. Allocating a scarce resource across a sequence of decisions, each of unknown importance, is a problem far more general than chess.

Answer: C

If two moves have similar scores, or the score has just dropped sharply, extra thought is likely to change the choice and is worth the time. In a clearly decided position further search rarely alters anything. The opponent's timing is not informative, and reaching maximum depth is a reason to stop. Spending effort where it is most likely to change a decision, rather than uniformly, is the practical content of metareasoning.

Answer: D

By assuming the opponent will play the predicted move and searching that position while waiting, a program uses time that would otherwise be idle, and if the prediction is right the search is already complete. It roughly doubles the effective thinking time when the prediction succeeds. Post hoc reconsideration, offline analysis and delay tactics are different activities. Using an idle resource on the most likely continuation is a cheap and substantial improvement.

Answer: A

A go position offers about 250 legal moves, against about 35 for chess, which is one of the two reasons classical search made so little progress at it. The board has 361 intersections, so the figure falls as the game proceeds. Having the branching factors of the familiar games at hand makes any estimate of search feasibility immediate rather than speculative.

Answer: B

Where only one move is legal, no branching occurs and the search can extend an extra ply for free, which is one of the standard selective extensions. Sequences of checks often contain several. Strong evaluations, agreements and predictability are different notions. Recognising that a position costs nothing to search deeper, and taking advantage of it, is a small optimisation that follows directly from the structure of the tree.

Answer: C

A sequence of checks and recaptures has few legal replies and reaches a stable position quickly, so following it to its end costs little and removes a whole class of horizon error. Quiet moves branch widely and cannot be extended so cheaply. Frequency, evaluation accuracy and node counts are not the argument. Spending the extension budget where the branching factor is smallest, and the uncertainty greatest, is what makes selective search worthwhile.

Answer: D

If one move stands out by a wide margin, the position probably turns on it, so searching that line deeper is likely to change the assessment. Extensions are budgeted because applying them everywhere would defeat the purpose. Uniform extension, principal variation only and one sided sequences describe different techniques. Spending an extension where the outcome hinges on a single choice is the same reasoning that extends forcing sequences, applied to a different signal.

Answer: A

Each extension lengthens the search, and a position that triggers extensions repeatedly could extend without bound, so a limit on total extension along a path is imposed. Fractional extension counts are a common implementation. Memory, evaluation accuracy and rules are not the constraint. A mechanism that can trigger itself needs an explicit bound, which is a general requirement of any recursive refinement.

Answer: B

Minimax gives the correct framework, alpha beta makes it affordable, and a stack of carefully chosen approximations converts an impossible computation into a strong player. Neither exhaustive search nor evaluation alone suffices, and the results in chess and go settle the last option. Building on an exact foundation and approximating deliberately, rather than approximating from the start, is what makes the behaviour of such systems analysable.