Two player coin game using Dynamic Programming | faceprep

Two player coin game using Dynamic Programming | faceprep

Two player coin game using Dynamic Programming is discussed here.





Two player coin game using Dynamic Programming


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

@@coding::1@@


Recommended Programs



Two player coin game using Dynamic Programming

c