Adversarial Search and Games Questions and Answers

Answer: A

The first three are correct. The horizon effect is caused by stopping the search at a fixed depth, not by the evaluation function being poor, and it persists however good the evaluation is. Attributing it to the wrong component leads to effort spent improving the evaluation when the cure is a selective extension of the search. Matching a symptom to the right cause is what decides where effort is worth spending.

Answer: B

Alpha beta, transposition tables and move ordering all reduce the work while returning exactly the value a full search would give. Forward pruning discards branches on suspicion and can therefore discard the best move. The distinction between provably safe and merely plausible pruning is the most important one in this area, since only the first can be adopted without qualification.

Answer: C

Both are true and the second is the reason. With perfect ordering the effective branching factor is the square root, which doubles the depth reachable in a given time, while with the worst ordering no pruning occurs at all. Depth is closely related to playing strength, so ordering translates directly into results. An algorithm whose benefit varies by an exponential factor according to a heuristic choice makes that choice the real subject of study.

Answer: D

The second is correct: forward pruning discards branches without proof and can lose the best move. Alpha beta prunes only what it has proved cannot affect the root value, so its answer is identical. The pair separates two techniques that are often lumped together as pruning and whose guarantees are entirely different. Knowing which of two similar sounding techniques is safe determines whether it may be used without further thought.

Answer: A

Delaying an unavoidable loss past the last ply searched makes it invisible, and extending the search along forcing lines such as checks and captures is the standard remedy. A uniformly deeper search merely moves the horizon. Move ordering and hash tables address efficiency rather than this systematic misjudgement. Recognising a characteristic pattern of play as the signature of a known algorithmic defect is a diagnostic skill worth having.

Answer: B

Whatever the depth, there is always a horizon, and a position with enough forcing resources can push a loss past any fixed one. Only extending selectively along the forcing lines, so that the search follows the tactics to their end, removes the problem. Evaluation accuracy, time and hash errors are separate issues. A defect that reappears at every scale points at the structure of the algorithm rather than at any parameter of it.

Answer: C

The root is the current position, each edge is a legal move and each level belongs alternately to one player, with terminal nodes carrying the game's outcome. Levels do correspond to players, but that is a property rather than the definition. Game records and material counts are different structures. The tree is the same object as a search tree with the addition that two agents choose alternately, which is the whole of what adversarial search adds.

Answer: D

Terminal utilities are defined by the rules, typically one for a win, a half for a draw and zero for a loss, and everything else in the tree is derived from them. Estimates apply at non terminal cutoffs, move counts and probabilities are different quantities. Anchoring the whole computation on values that are exact by definition, and estimating only where necessary, is the structure minimax shares with every other backup algorithm.

Answer: A

The maximiser selects the move giving the largest value, the minimiser the smallest, and the alternation of these two operations up the tree is the whole of minimax. Averaging belongs to chance nodes and random choice to a weak player. Describing the algorithm as two alternating operations on a tree, rather than as a procedure, makes both its correctness and its extensions to chance and to multiple players immediately visible.

Answer: B

A chance node takes the expectation of its children weighted by the probability of each outcome, so a dice roll or a card deal is modelled correctly. Selection would ignore the randomness, actual sampling belongs to Monte Carlo methods, and skipping would discard the structure. Adding a third kind of node with its own backup rule extends minimax to a whole class of games without disturbing the rest of the algorithm.