Adversarial Search and Games Questions and Answers

Answer: C

Since the players move in turn, each level of the tree belongs to one of them, and the backup rule alternates between maximum and minimum accordingly. Drawing conventions, memory and evaluation placement are incidental. The alternation is a property of the game rather than of the drawing, and it is exactly what distinguishes an adversarial search tree from an ordinary one.

Answer: D

With three or more players a single number no longer describes a position, so each node carries one utility per player and each player maximises their own component. Alliances and non zero sum effects then appear, which have no counterpart in the two player case. Reduction and single utilities discard the information the algorithm needs. Extending a representation to carry one value per participant is the minimal change that makes the framework general.

Answer: A

When one player is far ahead, the others' utilities both rise if that player is checked, so temporary cooperation is individually rational without any agreement being made. It emerges from the payoffs rather than from the rules. Formal agreements, zero sum structure and computability are separate matters. Behaviour that looks social but follows from each participant pursuing their own utility is a recurring and instructive phenomenon in multi-agent settings.

Answer: B

Each terminal position assigns a value to every participant, and those vectors are backed up with each player selecting the successor maximising their own component. A single value, an average or a range would all discard the information that makes the multiplayer case different. Generalising a scalar to a vector, and a maximum to a component-wise selection, is the minimal extension and it shows exactly what the two player case was assuming.

Answer: C

A player who cannot see the opponent's cards must reason about every hand consistent with the play so far, so the effective state is a distribution and the problem grows enormously. Sampling the possible states and solving each is a common approximation. Branching, finiteness and terminal counts are unaffected or worsened. Lifting a problem from states to distributions over states is the same move partial observability forces in ordinary search, and it costs the same exponential.

Answer: D

Determinisation samples a consistent assignment of the hidden cards, solves the resulting perfect information game and averages over many samples, which is fast and misses the value of information gathering and of concealment. Worst case assumptions are unduly pessimistic, ignoring the hidden state is worse still, and waiting is not available. An approximation whose specific blind spots are understood can be used deliberately, whereas one whose failures are unknown cannot.

Answer: A

By solving each sampled world as though the hidden cards were known to both players, the method never sees the point of a probe that reveals information or of a bluff that conceals it. Those are precisely the actions that distinguish skilled play in such games. Distributions, utilities and rules are all represented correctly. Identifying exactly what an approximation cannot express, rather than treating it as merely inaccurate, tells you which applications it is unsuitable for.

Answer: B

A player who bets only with strong hands is read easily, so occasionally betting with weak ones is necessary to make the strong bets profitable. The correct frequency follows from the equilibrium of the game. Individual hands may lose, the rules require nothing of the kind, and the opponent's uncertainty increases rather than decreases. That a locally losing action can be part of an optimal strategy is a result with no counterpart in single agent decision making.

Answer: C

Auctions, negotiation, resource allocation and security problems all involve agents whose payoffs depend on each other's choices, and equilibrium reasoning applies to all of them. The board game setting is the clearest introduction rather than the main application. Search, learning and representation come from other traditions. A body of theory developed for one purpose turning out to govern a much wider class of situations is one of the reasons the subject borrows so widely.

Answer: D

Because the opening is the same in every game and has been analysed for centuries, a prepared book avoids spending search time on positions whose best moves are already known. It also prevents the program from being led into a known bad line. Game histories, textbooks and exhaustive databases are different things, the last being infeasible. Precomputing the part of a problem that recurs identically is the same reasoning that produces endgame tablebases at the other end of the game.