Homework 4 - Answers

5.10) The main difference from backgammon is that although there is missing information (as with the dice roll), that information is not purely random but is actually selected by an opponent trying to make things as bas as possible for the player. Technically, this is called a  _game_of_partial_information_. Bridge, poker, market competition, and auctions fail in this class. The hey issues are: 
1. As well as trying to figure out the missing information, one must also try to figure out what one's opponent knows and doesn't know;
2. Minimax in the normal sense fails, because if player 1 can calculate a single optimal move in the initial state, then player 2 can figure out which move player 1 will make, and player 1 loses the advantage of having a hidden move. It turns out that a  _randomized_strategy_ is optimal, where the player should move by selecting from a given set (not necessarily all the legal moves) according to a certain probability distribution.

5.7) This procedure will give incorrect results. Mathematically, the procedure amounts to assuming that averaging commutes with min and max, which it does not. Intuitively, the choices made by each player in the deterministic trees are based on full knowledge of future dice rolls, and bear no necessary relationship to the moves made without such knowledge.

5.13) Construct a table of all possible positions with six pieces or less. The table values are computed by dynamic programming, starting with the end positions and working backwards. The table is thus filled in O(n) time.

5.14) Games can be continuous in two senses: the actions on each turn can be drawn from a continuous space, and the turns themselves can be continuous in the sense that the action at each point in continuous time is significant. Pool, tennis, and croquet are obviously continuous in the first sense, because in each case the ball can be projected with a velocity, direction, and spin drawn from a continuous range of possibilities. Tennis is also continuous in the second sense because one's continuous motion between shots must also be optimized.

5.16) The outcome of MAX can only be the same OR BETTER if MIN plays suboptimally compared to MIN playing optimally. Suppose MAX assumes MIN is rational and minimax says MIN will win, whatever moves to MAX are losing and are equally good, including those that lose in one step. Better algorithms would make it very hard for MIN to find the winning line. Minimax NEVER EVER sets traps. 

Extra-credit:

5.17) The version of minimax described in 5.8 will handle non-zero-sum games by maximizing components of a utility vector. However, in general no pruning (e.g., alpha-beta) can be done without risking suboptimality. This is because any node that is a candidate to be pruned by some algorithm _might_ be a node that is an optimal outcome for both players. In this case, each player should move towards it: they will essentially _cooperate_ in reaching the desired state. Therefore no node can be pruned.