Consider the following 2-player game: you start with n tokens on a table, in a single pile. Players alternate turns. On a player's turn, they must choose one pile of their choice, and split it into two piles. A player may distribute the tokens in any way between the two piles, as long as both piles have at least one token, and both piles do not have the same number of tokens. So, if a player splits a pile of size 6, she can do so via a 5 1 split, or a 4 2 split. A player loses if it is her turn, and there is no valid move. Can anyone do the following problem: (a) why player 2 will win when n = 4, and player 1 will win when n = 5. (b) Draw a game tree with n = 7. (c) Using the minimax algorithm can anyone explain who will win the game when n = 7.
On 2- player game.
662 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail AtThere are 2 best solutions below
On
The Grundy number (sometimes called the "nimber"; see Conway and Guy Winning Ways) for single piles of up to 21 chips are: $$\begin{array}{ccccc} 0: 0 & 5:2 & 10: 0 & 15:1 & 20:0\\ 1: 0 & 6:1 & 11: 2 & 16:3 & 21:4\\ 2: 0 & 7: 0& 12: 1& 17:2 \\ 3: 1 & 8:2 & 13:3 & 18:4 \\ 4:0 & 9: 1 & 14: 4 & 19: 3 \end{array} $$ What the Grundy number $G(p)$ for a position $p$ means is that from $p$ there are moves available to leave a positions $p'$ with $G(p') = 0, 1, 2, \ldots G(p)-1$ but no move available leaving $G(p')=G(p)$.
In particular, if there is no move available leaving $G(p'=0)$ then $G(p) = 0$, and the set of winning positions to leave are all positions with $G(p)= 0$.
So the winning positions with one pile of up to $22$ chips are $20, 10, 7, 4, 2, 1, 0$ chips in the pile. If you leave $7$ chips you have a forced win.
The advantage of this nimber concept is that if there is a game consisting of the "sum" of multiple games with nimbers $n_1, n_2, \ldots$ then the nimber for the combined game is obtained by expressing the individual nimbers in binary, lining them up in columns, and then adding each column mod 2 and interpreting that row of mod-2 sums as a binary number.
For example, if I leave the position with three piles of $19$, $15$, and $14$ chips, I can force a win because the "nimber sum" of $3 \oplus 1 \oplus 2 = 0$.
a) 4 - 31 - 211. Player 1 must go 4-31, player 2 must go 3-21 and there are no more moves.
b) 5 - 41 - 31 - 211, so player 1 wins. 5 - 32 - 212, player 2 wins. Because Player 1 goes first, (s)he should choose 41.
c) The tree looks like this:
Whatever Player 1 chooses to do, Player 2 has a winning move, so Player 2 always wins. After Player 2 moves for the first time, there are no options available.