Adversarial Search and Games Questions and Answers

Answer: A

Because expectations are taken, doubling one leaf value and not another changes the averages and hence the move, so only affine rescaling is safe. In pure minimax any order preserving transformation is harmless, since only comparisons are made. That difference is easily overlooked and it means an evaluation function tuned for minimax may misbehave in an expectimax setting. Knowing which transformations a method is invariant to tells you how much freedom the designer really has.

Answer: B

Every backup in minimax is a maximum or a minimum, which depends only on the ordering of the values, so any order preserving transformation gives the same move. Expectimax averages and so depends on the magnitudes. Signs, normalisation and terminal application are not the reason. Identifying an invariance is practically useful, because it says which aspects of a heuristic need tuning and which are free.

Answer: C

MCTS plays many games out to the end from a position, averaging the results to estimate its value, and grows the tree preferentially where the estimates are promising or uncertain. It needs no hand written evaluation function, which is why it transformed computer go. Random traversal, random move choice and database sampling are different ideas. Replacing a hand crafted estimate with a statistical one obtained by simulation is a change of kind rather than of degree.

Answer: D

Each iteration descends the existing tree by a selection rule, adds a node, plays a random game from it and propagates the result back up the path. Repeating this many thousands of times concentrates effort on the promising lines. The other lists mix real terms from other algorithms. A loop of four clearly named phases makes an otherwise unfamiliar algorithm easy to implement correctly, which is part of why the method spread so quickly.

Answer: A

The rule adds a term that grows when a move has been tried rarely, so a move with a good average is preferred but one with few samples is not neglected. That is the multi-armed bandit problem transplanted into a tree. Depth against breadth, resources and simulation quality are different trades. Importing a principled solution to exploration from another field, rather than inventing an ad hoc rule, is what gave the method its theoretical footing.

Answer: B

Decades of effort failed to produce a static evaluation of a go position accurate enough to be useful, whereas random playouts to the end supply an estimate needing no such knowledge. Go's branching factor of around two hundred and fifty is far larger than chess's, exact evaluation is intractable, and minimax applies perfectly well in principle. A method that sidesteps the component that could not be built is a different kind of solution from one that builds it better.

Answer: C

Self play generates unlimited training data at exactly the level the program has reached, so the opponent improves as the program does and no human games are required. Combined with tree search and a learned evaluation it produced superhuman play in several games. Fixed opponents, human game databases and two sided analysis are different arrangements. A training signal that scales with the system's own ability removes the dependence on an external curriculum entirely.

Answer: D

A pair of identical programs may settle into a narrow style, becoming excellent against each other and vulnerable to strategies neither explores. Randomised openings, population diversity and occasional external opponents mitigate it. Data volume is the method's strength, convergence to random play does not occur, and computation is the accepted cost. A training regime that defines its own test set risks optimising for a target that drifts away from the real one, which is a hazard shared with several other self supervised methods.

Answer: A

A weakly solved game has its value from the opening known, and a strongly solved one has the value of every position known, as for draughts. Superhuman play is a quite different achievement and does not constitute a solution. Enumeration is one route to a solution rather than the definition, and the value need not be a draw. Distinguishing a proof about the game from an engineering achievement against opponents is a distinction the popular reporting rarely makes.

Answer: B

Weak solution establishes the outcome and a strategy from the initial position, while strong solution establishes optimal play from any position however reached. Draughts is weakly solved as a draw, and small games are often strongly solved by retrograde analysis. Approximation, player count and playing strength are not the distinction. A hierarchy of results, each answering a different question, is worth keeping straight when a game is claimed to be solved.