Adversarial Search and Games Questions and Answers

Answer: C

Starting from positions whose value is known by rule and working backwards, one ply at a time, gives exact values for every position with few enough pieces, and the resulting endgame tablebases are used by every strong chess program. Post game analysis, backward search and move reconstruction are different activities. Computing exactly where exact computation is feasible, and estimating elsewhere, is a division of labour that appears throughout applied search.

Answer: D

When the search reaches a position covered by the tables, it substitutes the exact result for the heuristic estimate, removing all error from that part of the tree. It also settles endgames that a search could not resolve. They say nothing about the middlegame or the opening and are not training data. Grafting an exactly known region onto an otherwise approximate search is a clean way of removing error where removing it is affordable.

Answer: A

Card games hide the opponents' holdings, so a player must reason about a distribution over possible states rather than a single known position. Chance is a separate dimension, though many such games have both. Rule ambiguity is not a game theoretic notion, and simultaneous movement is a further variation. Partial observability transplanted into a game setting brings in belief states and, unlike the perfect information case, makes randomised strategies genuinely necessary.

Answer: B

If a player always bluffs with the same hands, the opponent learns to call, so mixing between actions with the right probabilities is necessary to be unexploitable. That is the content of a mixed strategy equilibrium. Computation, rules and general ignorance are not the reason, and random play is certainly not optimal in itself. That deliberate unpredictability can be part of an optimal policy is a genuine departure from everything in the perfect information case.

Answer: C

At equilibrium each strategy is a best response to the other, so no unilateral change helps. In a zero sum game it coincides with the minimax value. It need not be the outcome both players would prefer, as the prisoner's dilemma shows, and it need not be a win or be symmetric. A solution concept defined by stability rather than by optimality is what game theory offers where a single objective does not exist.

Answer: D

Because one player's gain is the other's loss, maximising one's own payoff is identical to minimising the opponent's, and the minimax value is exactly the equilibrium value. In non zero sum games the two diverge and cooperation becomes possible. Uniqueness, shared evaluation and definitional restriction are not the argument. That a special structure collapses two solution concepts into one explains why the general theory is needed only when that structure is absent.

Answer: A

Each prisoner does better by defecting whatever the other does, so both defect and both fare worse than if both had cooperated. It is the standard demonstration that individual rationality and collective benefit can diverge. It is not zero sum, information is complete, and defection rather than cooperation dominates. A game whose equilibrium is unanimously regretted is the sharpest possible illustration that equilibrium is not the same as optimality.

Answer: B

With an indefinite number of future rounds, a strategy that punishes defection can make cooperation the better long run choice, which is why tit for tat performs so well. The stage payoffs are unchanged, the game remains non zero sum, and randomisation is not required. That a game's character changes entirely when it is repeated, without any change to its payoffs, is one of the more consequential results in the field.

Answer: C

The first two are correct and are the two facts worth remembering about the technique. A chance node's value is an average and cannot be bounded from one child, so the pruning argument does not carry over without additional assumptions about the range of leaf values. Noticing that an argument depends on the backup rule being a maximum or minimum shows immediately where it will and will not apply.

Answer: D

Each addition to a basic alpha beta searcher fixes one specific defect, and together they account for most of the difference between a textbook program and a competitive one. Naming the problem each technique solves, rather than learning the techniques as a list, makes it clear which are needed for a particular game and which may be omitted.