Game Theory(Introduction)

Game Theory Introduction

Here played by two players who take turns moving. At the beginning there

are N Marvel. When it is a player’s turn he can take away 2, 3 or 5 Marvel.

The player who takes the last one away is declared the winner.

We can see that n = 2, 3, 5 are winning positions and 0, 1 are losing positions

because can not make a move from it.

Positions have the following properties:

1. All terminal positions are losing.

2. If a player is able to move to a losing position then he is in a winning position.

3. If a player is able to move only to the winning positions then he is in a losing position.

Now The question is: For N marvel first player win or second player win if they both play optimally?

If win_lose() function return 1 means first player win this game otherwise win_lose() function return 0 means second player win this game.

#include<bits/stdc++.h>

using namespace std;

int win_lose(int n)

{

    if(n == 0 || n == 1)

        return 0;

    if(win_lose(n-2) == 0 || win_lose(n-3) == 0 || win_lose(n-5) == 0)

        return 1;

    return 0;

}

int main()

{

    int n;

    cout << "Enter Marvel Number :: ";

    cin >> n;

    if(win_lose(n) == 1)

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

    else

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

return 0;

}