Adversarial Search and Games Questions and Answers

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.

Answer: C

Taking the probability weighted average gives:

\[ 0.5 \times 4 + 0.5 \times 10 = 7 \]

so the node's value is 7. Taking the maximum would treat chance as a cooperative player and the minimum as an adversarial one, both of which misrepresent randomness. Getting the backup rule right for each kind of node is the whole content of extending minimax, and the arithmetic is trivial once the rule is chosen.

Answer: D

Empirically each extra ply is worth a substantial gain in rating, with the returns diminishing as depth grows, so doubling the effective speed is a real improvement. That relationship is why the square root saving from alpha beta matters so much. Evaluation accuracy also matters and the two interact, since a deeper search partly compensates for a weaker evaluation. A measured relationship between a resource and a result is what turns engineering effort into a predictable gain.

Answer: A

Shallow search misses obvious tactics, and correcting those is worth a great deal, whereas the errors surviving a deep search are subtle and rarer. The curve therefore flattens without ever becoming flat. Branching factor, hash effectiveness and time are practical constraints rather than the reason for diminishing returns. A relationship whose shape is explained by the distribution of the errors being corrected is more informative than one merely observed.

Answer: B

A typical chess position offers about 35 legal moves, against roughly two hundred and fifty for go and around 10 for draughts. Those figures explain much of the relative difficulty of the three games for search based programs. Knowing the order of magnitude for a familiar game gives a reference point against which an unfamiliar one can be judged, and it is what makes a complexity estimate concrete rather than abstract.

Answer: C

With around two hundred and fifty moves available and no reliable static evaluation, classical alpha beta made little progress for decades. Monte Carlo methods, which need no evaluation function, changed that. Games are longer rather than shorter, representation is straightforward, and the rules are simpler than chess's. Identifying which of a game's properties defeats a technique is what points at the technique that will succeed.

Answer: D

Avoiding the re-search of positions reached by different move orders can save a large fraction of the tree, which translates directly into extra plies within the same time budget. Values are exact when depth and bounds are handled correctly. Branching and evaluation are unaffected. A saving that converts into depth, and depth into playing strength, is how a memory technique becomes a competitive advantage.