In competitive programming, several types of combinatorial game theory questions are frequently encountered. These problems often involve strategies to win the game based on mathematical observations and proofs. In this blog, we'll discuss four common types of combinatorial game theory questions and their solutions.↵
#### __**1. Invariance**__ ↵
#### __**2. Symmetry**__ ↵
#### __↵
**3. Reduction to Nim Game problems**__ ↵
#### __↵
**4. Solving using Dynamic Programming.**__ ↵
↵
In invariance and symmetric problems, certain properties of the game remain unchanged throughout its course. Although some may require mathematical proof, others can be solved through careful observations.↵
↵
_- Whytoff's Game:_**** The game involves two piles of stones with x and y stones, respectively. Two players, P1 and P2, take turns choosing a pile and removing at least one stone from it. The player who cannot make any move loses. Let's remove the 'a' stone from both piles such that a >= min(x, y). Whoever can't make any move will lose.↵
↵
**Solution:** We can use dynamic programming with three states (x, y) — one for removing a stone from pile 1, another for pile 2, and the third for removing from both piles. Dp(x,y) --> 1. (a, y) (0 <= a< x) 2. (x, b) (0 <= b < y) 3. (x-a, y-a) (1 <= a <= min(x, y)). The pseudocode for the optimized O(n^2) solution is provided below:↵
↵
_ for(int i = 0; i < n; i++){_↵
_ for(int j = 0; j < n; j++){_↵
_ if(dp[i][j] == 'L'){_↵
_ for(int k = 0; k < n; k++){_↵
_ dp[i+k][j] = 'w';_↵
_ dp[i][j+k] = 'w';_↵
_ dp[i+k][j+k] = 'w';_↵
_ }}}}_↵
↵
**-Nims Game:**__ The game has N piles of stones, each with a certain number of stones (a1, a2, a3, ..., an). Players P1 and P2 take turns choosing any pile and removing x stones (1 <= x <= ai). The player unable to make a move loses. ↵
↵
**Solution:** To determine the winner, calculate the XOR of all pile sizes: X = (a1) XOR (a2) XOR (a3) XOR ... XOR (an). If X is zero, P2 wins; otherwise, P1 wins. We can provide an inductive winning strategy for the second player when XOR is zero, ensuring that the player wins by leaving piles with the property "pile XOR with the largest pile is less than the largest pile." If XOR at the beginning is X > 0, the situation is equivalent to a game with n+1 piles, with the last pile containing X stones.↵
↵
**-Variation 1 of Nim Game:**__ The rules remain the same, but the player who cannot make a move wins. (Misere variation of games)↵
↵
**Solution:** The winning strategy remains unchanged. If X is zero, P2 wins. However, if the number of stones in all piles is 1 and n is even, P1 wins; otherwise, P2 wins.↵
↵
**-Variation 2 of Nim Game:**__ The game has N buildings, each with an initial height of H. Players can take y stones from any building if y divides x (1 <= y < x). Determine the winner.↵
↵
**Solution:** If n is even, P2 will win; otherwise, P1 wins. An exception is when H is 1, in which case, Player 2 will win. The key is to recognize that there will always be a pair of buildings with the same height, maintaining the balance among all imbalanced pairs.↵
↵
**-Variation 3 of Nim Game:**__ Similar to Variation 2, but the heights of the N buildings may differ {h1, h2, h3, ......., hn}. Who will win?↵
↵
**Solution:** Let's factorize the height of each building. Suppose hi (1<= i <= n) can be expressed as (p1^alpha_1) * (p2^alpha_2) * (p3^alpha_3)*....*(pk^alpha_k). ai = alpha_1 + alpha_2 + alpha_3 + alpha_4 + .... + alpha_n. For N heights we will get n such a's; a1, a2, a3, ....., an. X (a1) XOR (a2) XOR (a3) XOR ............. XOR (an).↵
If X == 0 P2 wins else P1 wins. Actually, we have converted this complex game into the basic Nims Game using Grundy Numbers.↵
↵
**-Variation 4 of Nim Game:**__ Suppose we are taking the above example but the difference is each player has a quota of k moves (Let's say he/she can make h1 to (2h1)/ (3h1) / (5h1) / (h1/2) / (h1/3) / (h1/5). Who will win?↵
↵
**Solution:** This variant is equivalent to Nim's Game since one player can always nullify the other's move by responding accordingly.↵
↵
_-Grundy Numbers:_**** Suppose there are X stones. Any player can take Y stones such that Y is a power of 2 and less ↵
than X and greater than 0. Who will win P1 or P2?↵
↵
**Solution:** ↵
1. (1) solution: if(X%3 == 1) P1 wins else P2 wins.↵
↵
2. Dynamic Programming solution:↵
_ for(int i = 0; i <= 1000; i++){_↵
_ for(int j = 0; (1<<j) <= i; j++){_↵
_ if(dp[i-(1<<j)] == 0){_↵
_ dp[i] = 1; break;_↵
_ }_↵
_ }_↵
_ }_↵
__ ↵
_ for(int i = 0; i < 1000; i++){_↵
_ cout << i << " " << dp[i] << "\n";_↵
_ }_ ↵
↵
3. Approach of Grundy Numbers: Suppose the transitions of X are x1, x2, x3,......, xk. Grundy of k G(k) = mex(G(x1), ↵
G(x2), G(x3), ....., G(xk)}↵
↵
C++ pseudo-code: ↵
_long long int G[100010];_↵
_ for(int i = 0; i <= 10000; i++){_↵
_ set<int>st;_↵
_ for(int j = 0; (1<<j) <= i; j++){_↵
_ st.insert(G[i-(1<<j)]);_↵
_ }_↵
_ }_↵
__ ↵
_ long long mex(set<long long> &x){_↵
_ long long ans;_↵
_ for(auto v:x){_↵
_ if(v== ans) ans++;_↵
_ }_↵
_ return ans;_↵
_ }_↵
↵
**Game Theory is a Math-Based Topic!**↵
↵
**So reading solved examples is the KEY !!**↵
↵
[Reading Short](https://www.topcoder.com/community/competitive-programming/tutorials/algorithm-games/) | [Full Notes ](https://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf) | [Practice Problems (15 Challenging Problems of Hackerrank):](https://www.hackerrank.com/contests/5-days-of-game-theory/challenges)↵
↵
I am personally thankful to my college senior **Vivek Gupta** ([user:GodSpeed98,2023-07-30]), who is a ICPC World Finalist 2020 for this blog.
#### __
**3. Reduction to Nim Game problems**
#### __
**4. Solving using Dynamic Programming
↵
In invariance and symmetric problems, certain properties of the game remain unchanged throughout its course. Although some may require mathematical proof, others can be solved through careful observations.↵
↵
_- Whytoff's Game:_**** The game involves two piles of stones with x and y stones, respectively. Two players, P1 and P2, take turns choosing a pile and removing at least one stone from it. The player who cannot make any move loses. Let's remove the 'a' stone from both piles such that a >= min(x, y). Whoever can't make any move will lose.↵
↵
**Solution:** We can use dynamic programming with three states (x, y) — one for removing a stone from pile 1, another for pile 2, and the third for removing from both piles. Dp(x,y) --> 1. (a, y) (0 <= a< x) 2. (x, b) (0 <= b < y) 3. (x-a, y-a) (1 <= a <= min(x, y)). The pseudocode for the optimized O(n^2) solution is provided below:↵
↵
_ for(int i = 0; i < n; i++){_↵
_ for(int j = 0; j < n; j++){_↵
_ if(dp[i][j] == 'L'){_↵
_ for(int k = 0; k < n; k++){_↵
_ dp[i+k][j] = 'w';_↵
_ dp[i][j+k] = 'w';_↵
_ dp[i+k][j+k] = 'w';_↵
_ }}}}_↵
↵
**-Nims Game:**__ The game has N piles of stones, each with a certain number of stones (a1, a2, a3, ..., an). Players P1 and P2 take turns choosing any pile and removing x stones (1 <= x <= ai). The player unable to make a move loses. ↵
↵
**Solution:** To determine the winner, calculate the XOR of all pile sizes: X = (a1) XOR (a2) XOR (a3) XOR ... XOR (an). If X is zero, P2 wins; otherwise, P1 wins. We can provide an inductive winning strategy for the second player when XOR is zero, ensuring that the player wins by leaving piles with the property "pile XOR with the largest pile is less than the largest pile." If XOR at the beginning is X > 0, the situation is equivalent to a game with n+1 piles, with the last pile containing X stones.↵
↵
**-Variation 1 of Nim Game:**__ The rules remain the same, but the player who cannot make a move wins. (Misere variation of games)↵
↵
**Solution:** The winning strategy remains unchanged. If X is zero, P2 wins. However, if the number of stones in all piles is 1 and n is even, P1 wins; otherwise, P2 wins.↵
↵
**-Variation 2 of Nim Game:**__ The game has N buildings, each with an initial height of H. Players can take y stones from any building if y divides x (1 <= y < x). Determine the winner.↵
↵
**Solution:** If n is even, P2 will win; otherwise, P1 wins. An exception is when H is 1, in which case, Player 2 will win. The key is to recognize that there will always be a pair of buildings with the same height, maintaining the balance among all imbalanced pairs.↵
↵
**-Variation 3 of Nim Game:**__ Similar to Variation 2, but the heights of the N buildings may differ {h1, h2, h3, ......., hn}. Who will win?↵
↵
**Solution:** Let's factorize the height of each building. Suppose hi (1<= i <= n) can be expressed as (p1^alpha_1) * (p2^alpha_2) * (p3^alpha_3)*....*(pk^alpha_k). ai = alpha_1 + alpha_2 + alpha_3 + alpha_4 + .... + alpha_n. For N heights we will get n such a's; a1, a2, a3, ....., an. X (a1) XOR (a2) XOR (a3) XOR ............. XOR (an).↵
If X == 0 P2 wins else P1 wins. Actually, we have converted this complex game into the basic Nims Game using Grundy Numbers.↵
↵
**-Variation 4 of Nim Game:**__ Suppose we are taking the above example but the difference is each player has a quota of k moves (Let's say he/she can make h1 to (2h1)/ (3h1) / (5h1) / (h1/2) / (h1/3) / (h1/5). Who will win?↵
↵
**Solution:** This variant is equivalent to Nim's Game since one player can always nullify the other's move by responding accordingly.↵
↵
_-Grundy Numbers:_**** Suppose there are X stones. Any player can take Y stones such that Y is a power of 2 and less ↵
than X and greater than 0. Who will win P1 or P2?↵
↵
**Solution:** ↵
1. (1) solution: if(X%3 == 1) P1 wins else P2 wins.↵
↵
2. Dynamic Programming solution:↵
_ for(int i = 0; i <= 1000; i++){_↵
_ for(int j = 0; (1<<j) <= i; j++){_↵
_ if(dp[i-(1<<j)] == 0){_↵
_ dp[i] = 1; break;_↵
_ }_↵
_ }_↵
_ }_↵
__ ↵
_ for(int i = 0; i < 1000; i++){_↵
_ cout << i << " " << dp[i] << "\n";_↵
_ }_ ↵
↵
3. Approach of Grundy Numbers: Suppose the transitions of X are x1, x2, x3,......, xk. Grundy of k G(k) = mex(G(x1), ↵
G(x2), G(x3), ....., G(xk)}↵
↵
C++ pseudo-code: ↵
_long long int G[100010];_↵
_ for(int i = 0; i <= 10000; i++){_↵
_ set<int>st;_↵
_ for(int j = 0; (1<<j) <= i; j++){_↵
_ st.insert(G[i-(1<<j)]);_↵
_ }_↵
_ }_↵
__ ↵
_ long long mex(set<long long> &x){_↵
_ long long ans;_↵
_ for(auto v:x){_↵
_ if(v== ans) ans++;_↵
_ }_↵
_ return ans;_↵
_ }_↵
↵
**Game Theory is a Math-Based Topic!**↵
↵
**So reading solved examples is the KEY !!**↵
↵
[Reading Short](https://www.topcoder.com/community/competitive-programming/tutorials/algorithm-games/) | [Full Notes ](https://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf) | [Practice Problems (15 Challenging Problems of Hackerrank):](https://www.hackerrank.com/contests/5-days-of-game-theory/challenges)↵
↵
I am personally thankful to my college senior **Vivek Gupta** ([user:GodSpeed98,2023-07-30]), who is a ICPC World Finalist 2020 for this blog.
