Two player coin game using Dynamic Programming | faceprep

Two player coin game using Dynamic Programming is discussed here. 

There is an array of coins with different worth. Two players playing this game can pick a coin from either of the left or right end. The player with maximum sum will win. Both players are optimally playing the game.

If player one wins the game print “PLAYER 1 WINS” else if player 2 wins print “PLAYER 2 WINS” if they both have equal sum at the end, print “DRAW”.

Strategy 1:

Array = { 18, 20, 15, 30, 10, 14 }
Player 1 picks 18, now the array of coins is
20 15 30 10 14
Player 2 picks 20, now the array of coins is 
15 30 10 14
Player 1   picks 15, now the array of coins is
30 10 14
Player 2 picks 30, now the array of coins is 
10, 14
Player 1   picks 14, now the array of coins is
10
Player 2 picks 10.
The total value of coins picked by the second player is more (20 + 30 + 10) compared to the first player (18 + 15 + 14). So, the second player wins.

Having made the first move, the first player is unable to succeed. So, should we make the first move or not? Does it matter?

Playing first will guarantee that the player will not lose or at least end up with a draw game. Now, consider the strategy 2 using a dynamic programming approach.

Strategy 2:

  • Count the sum of all coins that are odd-numbered. (Let the odd-numbered coins be X)
  • Count the sum of all coins that are even-numbered. (Let the even-numbered coins be Y)
  • If X > Y, take the left-most coin first. Choose all odd-numbered coins in subsequent moves.
  • If X < Y, take the right-most coin first. Choose all even-numbered coins in subsequent moves.
  • If X == Y, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.

Considering the same example,

Array = {18, 20, 15, 30, 10, 14}

  • Sum of odd coins = 18 + 15 + 10 = 43
  • Sum of even coins = 20 + 30 + 14 = 64

Since the sum of even coins is more, the first player decides to collect all even coins. He first picks 14, now the other player can only pick a coin (10 or 18). Whichever is picked by the other player, the first player again gets an opportunity to pick an even coin and block all even coins.

Program for the two player game using dynamic programming

/* C++ program for the two player game using dynamic programming */

#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
       cin>>a[i];
   int table[n][n];
   for(int i=0;i<n;i++)
   {
       table[i][i]=a[i];
       if(i != n-1)
           table[i][i+1]=max(a[i],a[i+1]);
   }
   int x,y,z,r,c;
   bool flag = true;
   for(int i=2;i<n;i++)
   {
       for(int j=0;j+i<n;j++)
       {
           r=j;
           c=j+i;
           x=table[r+2][c];
           y=table[r+1][c-1];
           z=table[r][c-2];
           if(r == 0 and c == n-1)
           {
               if(max(a[r]+min(x,y),a[c]+min(y,z)) == a[r]+min(x,y))
                   flag=true;
               else
                   flag= false;
           }
           table[r][c]=max(a[r]+min(x,y),a[c]+min(y,z));
       }
   }
   int player1,player2;
   /*
   cout<<table[0][n-1]<<endl;
   if(flag)
   cout<<table[1][n-1];
   else
   cout<<table[0][n-2]<<endl;
   */
   player1=table[0][n-1];
   player2=(flag)?table[1][n-1]:table[0][n-2];
   if(player1 > player2)
       cout<<“PLAYER 1 WINS”;
   else if(player2 >  player1)
       cout<<“PLAYER 2 WINS”;
   else
       cout<<“DRAW”;
}

Test Case 1

I/P
5
2 1 2 1 2
O/P
DRAW

Test Case 2

I/P
10
14 26 10 13 24 14 17 30 21 24
O/P
PLAYER 1 WINS

Test Case 3

I/P
5
1 36 41 20 5
O/P
PLAYER 2 WINS

Test Case 4

I/P
6
2 2 2 2 2 2
O/P
DRAW

Test Case 5
I/P
3
21 150 34
O/P
PLAYER 2 WINS