This is definitely new to me, and it's really interesting. I'd like to share about Nim Game, one of the subject for discussion in Game Theory. Below is the description of the game:
Given 3 piles of chips, each of size 3,5, and 7 respectively. Two players take turn to play. When it is a player's turn, he can remove as many chips as he wants from one pile. Whoever removes the last chips wins the game.
Here is an illustration of the game with 2 players, Andhieka and Tio, where Andhieka starts first:
A B C
3 5 7 Initial configuration
1 5 7 Andhieka removes 2 chips from A
1 2 7 Tio removes 3 chips from B
1 2 4 Andhieka removes 3 chips from C
1 2 0 Tio removes 4 chips from C
1 1 0 Andhieka removes 1 chip from B
1 0 0 Tio removes 1 chip from B and begging Andhieka to stop
0 0 0 Andhieka removes 1 chip from A and wins the game.
The game can be generalized to \(k\) piles with \(a_1,a_2,...,a_k\) chips each. The setting above is called normal play where players try to be the one who removes the last chips. Another setting, misere play, is when players try not to be the one who removes the last chips. In both type of setting, there are winning strategies for the generalized Nim game.
Let's start with normal play Nim game. The key observation to win this game is by considering the binary representation of \(a_1,a_2,\ldots ,a_k\). An operation called exclusive or (XOR, represented as \(\oplus\)) reveals an important property of the game. We define \(S\) such that
$$ S = a_1 \oplus a_2 \oplus \ldots \oplus a_k $$
The goal is to have all piles having zero chips, and when this happens, \(S = 0\).
From this observation, we can posit the following claims:
Claim 1:
If \(S\) is currently equals \(0\), whatever we do on our turn, \(S\) will change to something else than \(0\)
Proof:
Suppose that on our turn, we manage to take away some chips from a pile such that \(S \) is changed to \(T = b_1 \oplus b_2 \oplus \ldots \oplus b_k = 0\). Since we can only remove chips from one pile, call that pile \(i\), the other \(k-1\) piles will have the same number of chips after our turn. Then we have:
$$ S \oplus T = ( a_1 \oplus a_2 \oplus \ldots \oplus a_k ) \oplus (b_1 \oplus b_2 \oplus \ldots \oplus b_k) $$
$$ S \oplus T = (a_1 \oplus b_1) \oplus (a_2 \oplus b_2) \oplus \ldots \oplus (a_k \oplus b_k) $$
Note that \((a_j \oplus b_j) = 0\) for \(j \neq i\), hence
$$ S \oplus T = 0 \oplus 0 \oplus \ldots \oplus (a_i \oplus b_i) \oplus \ldots \oplus 0$$
$$ S \oplus T = a_i \oplus b_i $$
Note that LHS equals to 0, since \(S =0 \) and by assumption, \(T = 0\).
However, RHS cannot be 0 since \(a_i \neq b_i\) since we removed some chips from pile \(i\), a contradiction. Hence \(T\) cannot be 0, and the proof is complete. \(\blacksquare\)
Claim 2:
If \(S\) is currently not equal to \(0\), on our turn we can remove chips to arrive at \(S=0\)
Proof:
This is proof will also reveals the strategy and therefore algorithm for players to win the game.
Denote the most significant bit of \(S\) as \(m\). For bit \(m\) to be turned on, there must be odd numbers of piles in which the bit at position \(m\) is also turned on. This means that there will be at least \(1\) such pile, let the pile be \(i\). If there are more than one pile, any one of them will do.
Define \(Y = a_i - (S \oplus a_i)\). If we can take Y chips from pile \(i\), then we will have piles with chips \((a_1,a_2,\ldots ,a_i-Y, \ldots , a_k)\) such that
$$ S' = a_1 \oplus a_2 \oplus \ldots \oplus (a_i - Y) \oplus \ldots \oplus a_k$$
$$ S' = a_1 \oplus \ldots \oplus (S \oplus a_i) \oplus \ldots \oplus a_k $$
Rearranging, we have
$$ S' = S \oplus S = 0$$
which proves our claim. However, we need to show that \((S\oplus a_i)\) is indeed less than \(a_i\), or else we can't take negative amount of \(Y\) chips from pile \(i\). This is actually easy, since \(S\oplus a_i\) at least turns off bit \(m\) from \(a_i\), and it any bit higher than bit \(m\) untouched since \(m\) is the most significant digit of \(S\). Therefore \((S\oplus a_i)\) is guaranteed to be less than \(a_i\), which completes the proof. \(\blacksquare\)
No comments:
Post a Comment