Problem Statement:
455B - A Lot of Games
Solution:
An interesting game theory problem. As usual, game theory problems tend to be pretty creative. First of all, we need to build a prefix tree using all the strings, which can be done in \(O(N)\). The root of the tree is an empty string, which is also the initial state of the game. The tree hence represent the graph of valid moves on each state of the game. We want to know, assuming both players play optimally, whether First can force his way to win and also whether he can lose a given game. We can use Sprague Grundy Theorem, but for this particular problem it is not necessary, as we can use a simple dynamic programming reasoning. First denote win[u] and lose[u] as the table which tells us whether the current player who has to move at state u can eventually win or lose. Suppose we want to fill up win[u], we check all states v that is directly pointed by u, and win[u] is only true if and only if there is a state with win[v] which is false. This reasoning also applies for filling up lose[u].
Showing posts with label Game Theory. Show all posts
Showing posts with label Game Theory. Show all posts
Wednesday, January 7, 2015
Thursday, June 19, 2014
a bit of game theory: Nim Game
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\)
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\)
Subscribe to:
Posts (Atom)