Problem : Compute the position values for 0 through 16 for 1-row misere Nim where the legal moves are to take 1, 4, or 5 stones.
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
outcome class | N | P | N | P | N | N | N | N | N | P | N | P | N | N | N | N | N |
Problem : Consider a normal game played with $n$ rows of stones. On each turn, the current player can take any number of stones from any row, or may move any number of stones to the row directly above it (including to a row that has been emptied, not skipping over any row that has not been emptied, and not to a row that never existed).
The rows are not independent games since stones can move between rows.
Position (top/middle/bottom) | Moves | Grundy Numbers of Moves | Grundy Number |
---|---|---|---|
1/1/1 | {2/0/1, 1/2/0, 0/1/1, 1/0/1, 1/1/0} | {*0, *2, *0, *2, *0} | *1 |
2/0/1 | {2/1/0, 1/0/1, 0/0/1, 2/0/0} | {*1, *2, *2, *2} | *0 |
1/2/0 | {3/0/0, 2/1/0, 0/2/0, 1/1/0, 1/0/0} | {*3, *1, *1, *0, *1} | *2 |
2/1/0 | {3/0/0, 1/1/0, 0/1/0, 2/0/0} | {*3, *0, *2, *2} | *1 |
0/1/1 | {1/0/1, 0/2/0, 0/0/1, 0/1/0} | {*2, *1, *1, *2} | *0 |
1/0/1 | {1/1/0, 0/0/1, 1/0/0} | {*0, *1, *1} | *2 |
1/1/0 | {2/0/0, 0/1/0, 1/0/0} | {*2, *2, *1} | *0 |
3/0/0 | {2/0/0, 1/0/0, 0/0/0} | {*2, *1, *0} | *3 |
0/2/0 | {2/0/0, 1/1/0, 0/1/0, 0/0/0} | {*2, *0, *2, *0} | *1 |
2/0/0 | {1/0/0, 0/0/0} | {*1, *0} | *2 |
0/0/1 | {0/1/0, 0/0/0} | {*2, *0} | *1 |
0/1/0 | {1/0/0, 0/0/0} | {*1, *0} | *2 |
1/0/0 | {0/0/0} | {*0} | *1 |
0/0/0 | {} | {} | *0 |
1/1/1 + 0/2/0 is equivalent to *1 + *1. The Nim-sum is 0. So there is no winning move.
The 5 stones can be in any of the three rows, so we can view the positions as multisets where each element in the multiset indicates the row a particular stone is in; for example 3/1/1 would be {1,1,1,2,3}. The number of size-5 multisets of {1,2,3} is ${7 \choose 5} = 21$.
Problem : Prove or disprove: for any position $G \approx *n$ and any $m < n$, there is an option $G'$ of $G$ such that $G + G' \approx *m$.
Problem : Suppose we modify Coino (the coin flipping game from Homework #3) so that you get one do-over: at most once during the game you may discard the result of a flip and reflip any number of coins if the initial result was not to your liking. How would you modify the algorithm to find the optimal strategy and the expected winnings in this case?
$OPT(c,t,r)$ would record the argmax of the outer max for each entry to record the optimal choices of how many coins to flip; $OPT(c,t,r,f,h)$ would store the argmax of the inner max to record, for each position $(c,t,r)$, choice ($f$), and outcome of that choice ($h$), whether the optimal choice was to reflip or not.
Problem : Compute the minimax value of each node in the tree below. Squares represent max nodes and circles represent min nodes.
Problem : Show the operation of alpha-beta pruning on the tree shown below. Show the (alpha, beta) windows passed to each node as the tree is traversed, the values returned from each node, and which branches are pruned.
Node | $(\alpha, \beta)$ | Value |
---|---|---|
A | $(-\infty, \infty)$ | 7 |
B | $(-\infty, \infty)$ | 4 |
C | $(4, \infty)$ | 7 |
D | $(7, \infty)$ | 6 |
E | $(-\infty, \infty)$ | 4 |
F | $(-\infty, 4)$ [prunes 2nd child] | 6 |
G | $(-\infty, 4)$ [prunes 2nd child] | 7 |
H | $(4, \infty)$ | 7 |
I | $(4, 7)$ [prunes 2nd, 3rd children] | 9 |
J | $(7, \infty)$ | 9 |
K | $(7, 9)$ | 6 |
Problem : Repeat the previous exercise for Scout.
Node | $(\alpha, \beta)$ | Value |
---|---|---|
A | $(-\infty, \infty)$ | 7 |
B | $(-\infty, \infty)$ | 4 |
C | $(4, 5)$ $(5, \infty)$ |
7 7 |
D | $(7, 8)$ | 6 |
E | $(-\infty, \infty)$ | 4 |
F | $(-\infty, 4)$ [prunes 2nd child] | 6 |
G | $(-\infty, 4)$ [prunes 2nd child] | 7 |
H | $(4, 5)$ [prunes 2nd child] $(5, \infty)$ |
7 7 |
I | $(4, 5)$ [prunes 2nd, 3rd children] $(6, 7)$ [prunes 2nd, 3rd children] |
9 9 |
J | $(7, 8)$ [prunes 2nd, 3rd children] | 9 |
K | $(7, 8)$ | 6 |
Problem : Consider a constant-sum game with payoff matrix $$\left( \begin{array}{ccc} 0 & 2 & -1 \\ 1 & -2 & 0 \\ -2 & 0 & 2 \end{array} \right)$$.
Problem : Find a saddle point and its value for the constant-sum game with payoff matrix $$ \left( \begin{array}{cc} 3 & 2 \\ 0 & 4 \\ \end{array} \right) $$
For $Y$ the inequalities are \begin{array}{rcccl} E(1, Y) &=& y + 2 &\le& v \\ E(2, Y) &=& 4 - 4y &\le& v \\ \end{array} The minimum value of $v$ above both lines is at their intersection, which is where $y + 2 = 4 - 4y$, or $y = \frac{2}{5}$, so $Y^* = (\frac{2}{5} \frac{3}{5})$.
$E(X^*, Y^*) = \frac{12}{5}$.
Problem : Set up the linear program to find a saddle point for the constant-sum game with payoff matrix $$ \left( \begin{array}{ccc} 4 & 7 & 3 \\ 0 & 5 & 4 \\ 10 & 6 & 2 \\ \end{array} \right) $$
Minimize $p_1 + p_2 + p_3$ subject to \begin{array}{rcl} -5p_1 - p_2 - 11p_3 & \le & -1 \\ -8p_1 - 6p_2 - 7p_3 & \le & -1 \\ -4p_1 - 5p_2 - 3p_3 & \le & -1 \\ p_1, p_2, p_3 & \ge & 0 \\ p_1, p_2, p_3 & \le & 1 \\ \end{array}
Minimize $-q_1 - q_2 - q_3$ subject to \begin{array}{rcl} 5q_1 + 8q_2 + 4q_3 & \le & 1 \\ q_1 + 6q_2 + 5q_3 & \le & 1 \\ 11q_1 + 7q_2 + 3q_3 & \le & 1 \\ q_1, q_2, q_3 & \ge & 0 \\ q_1, q_2, q_3 & \le & 1 \\ \end{array}