Combinatorial Game Theory

Sometimes we find questions where two Players say A and B play a game optimally and we have to find out who ultimately is going to win the game provided there are some constraints.

These questions are generally branched under the topic Combinatorial Game Theory. And the speciality about these is that the coding part is relatively very small and easy. The key to the Game Theory problems is the hidden observations which can be sometimes very hard to find.

First, we will look at the basic division of positions to winning and losing.

Question: Two players are playing a game with n stones where player 1 always plays first. The two players move in alternating turns and play optimally. In a single move, a player can remove either 1, 3 or 4 stones from the pile of stones. If a player is unable to make a move then that player loses the game. Given the number of stones, find and print the name of the winner.

Approach: As we can see positions 1, 3 and 4 are winning positions since the player can pick up all the stones and another player will not be able to make a move. 0 is a losing position since the player can not pick any stones. Also, 2 is a losing position as there is only one option that is to pick 1 stone and the other player is left with 1 stone which he will pick up certainly and so the previous player loses.

So, from the following observation, we can conclude that :

· All terminal positions are losing.

· If a player can move to a losing position then he is on a winning position.

· If a player can only move to a winning position than he is on a losing position.

 It can be seen that whether a position is winning or losing depends only on the last k positions, where k is the maximum number of coins we can take away. While there are only 2^k possible values for the sequences of the length k, our sequence will become periodic.

In fact, we can predict the winner of the game before even playing the game!

Solution: 

bool dp[n];
dp[0] = dp[3] = 0;
dp[1] = dp[2] = dp[4] = dp[5]=1;
for(int i=6;i<=n;i++){
 if(dp[i-1] == 0 or dp[i-2] == 0 or dp[i-5] == 0)
  dp[i]=1;
 else
  dp[i]=0;

Here 1 represents winning and 0 represents losing position. 

1. 
   

Another famous Question in this respect is the Game of Nim.

The basic rules for this game are as follows:

• The game starts with a number of piles of stones. The number of stones in each pile may not be equal.
• The players alternately pick up 1 or more stones from a pile.
• The player to remove the last stone wins.

Approach: Try out different combinations of piles and stones and also for a different player playing first. And try to observe. You would find that the game depends on two factors-

• The player who starts first.
• The initial configuration of the piles/heaps.

If both A and B play optimally, then the player starting first is guaranteed to win if the Nim-Sum at the beginning of the game is non-zero. Otherwise, if the Nim-Sum evaluates to zero, then player A will lose definitely.

Here, Nim-sum is the cumulative XOR of the number of stones in each pile.

To get the proof of this method I suggest you refer this.

Solution:  

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {   
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> nums(n, 0);
        int val = 0;
        for(int i=0; i<n; ++i){
            cin >> nums[i];
            val ^= nums[i];
        }
        
        if (val>0)
            cout << "First\n";
        else
            cout << "Second\n";
        
    }
    return 0;
}

Practice Problems:

• Tower Breakers
• Misere Nim
• Nimble Game
• Poker Nim
• Game Theory
• MMMGAME
• The Game
• Yet Another Fancy Game
• The Game of 31
• Stone Game