Nim Game

Two Player Nim Game : 

          There are several piles, each with several stones. In a move, a player can take any positive number of stones from any one pile and throw them away. A player loses if they can’t make a move, which happens when all the piles are empty.

Suppose there are three piles. First pile have 4 stone, Second pile have 2 stone, Third pile have 3 stone. Game start from first player.

In this state of game, the First player may do one of the following: 

            

        ▶ Take 1, 2, 3 or 4 stones from 1st pile.

        ▶ Take 1 or 2 stones from 2nd pile. 

        ▶ Take 1, 2 or 3 stones from 3rd pile. 

Q: Now the question is Who will win, First Player or Second player?

Answer: This question have a sort-cut solution. This solution provide by Charles Bouton.

Charles Bouton Theorem :  

                 The current player has a winning strategy if and only if the xor-sum of the pile sizes is non-zero.

Above scenario when First player start the game 1st pile have 4 stone, Second pile have 2 stone, Third pile have 3 stone. By Charles Bouton Theorem First player win if xor-sum of (4, 2, 3) is greater than 0.

          xor-sum = 4 ⊕ 2 ⊕ 3

                  = 5

xor-sum is 5 so if two player play this game optimally obviously First player win this game.

Coding Part:

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n;

    cout << "Enter Number of Piles : ";

    cin >> n;

    int a[n], xor_sum = 0;

    cout << "Enter Each Piles Stone Number : ";

    for(int i=0; i<n; i++)

    {

        cin >> a[i];

        xor_sum ^= a[i];

    }

    if(xor_sum > 0)

        cout << "First Player Win." << "\n";

    else

        cout << "Second Player Win" << "\n";

    return 0;

}