Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic Programming — Coin In a Line Game Problem

Objec­tive: In this game, which we will call the coins-in-a-line game, an even num­ber, n, of coins, of var­i­ous denom­i­na­tions from var­i­ous coun­tries, are placed in a line. Two play­ers, who we will call Alice and Bob, take turns remov­ing one of the coins from either end of the remain­ing line of coins. That is, when it is a player’s turn, he or she removes the coin at the left or right end of the line of coins and adds that coin to his or her col­lec­tion. The player who removes a set of coins with larger total value than the other player wins, where we assume that both Alice and Bob know the value of each coin.

Exam­ple:

coins []  =  { 6, 9, 1, 2, 16, 8}

trial 1: (players will pick the best option available for them)
coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 8
coins [] = { 6, 9, 1, 2, 16}, Bob picks 16
coins [] = { 6, 9, 1, 2}, Alice picks 6
coins [] = { 9, 1, 2}, Bob picks 9
coins [] = {1, 2}, Alice picks 2
coins [] = {1}, Bob picks 1
Alice: 8+6+2 =16 Bob: 16+9+1=26 => Alice Lost

So clearly picking up the best in each move is not good for Alice. What else Alice can do to win the game.

trial 2: (Alice thinks about Bob's move, Will discuss the strategy in solution) 
coins [] = { 6, 9, 1, 2, 16, 8} , Alice picks 6
coins [] = { 9, 1, 2, 16, 8}, Bob picks 9
coins [] = { 1, 2, 16, 8}, Alice picks 1
coins [] = 2, 16, 8}, Bob picks 8
coins [] = {2, 16}, Alice picks 16
coins [] = {2}, Bob picks 2
Alice: 6+1+16 =23 Bob: 9+8+2=19 => Alice Won

So this time Alice has won. Let's see the solution and discuss what Alice has done to win the game. 

Approach:

We will solve this prob­lem using Dynamic pro­gram­ming in Bottom-up manner.

In the exam­ple above we have seen that in trail 1 Alice has lost and in trial 2 Alice has won. So clearly pick­ing the best coin avail­able in each move is good option for Alice.

So the ques­tion is what Alice has done dif­fer­ently to win in sec­ond trial. Since Alice and Bob, both are play­ing to win the game and both are equally clever then “Alice has to think about Bob’s move means options avail­able for the Bob once Alice is done with the move, What Bob will pick (Bob is equally clever and tries to leave Alice with min­i­mum val­ues to be cho­sen from) and  then what Alice will chose.

So if we can clearly see that each player is mak­ing the move by keep­ing in mind the two moves can be made in future and pick the best of them.

Let’s make it more clear– Sup­pose we have coins lined up from Ci to Cj wit the val­ues of Vi to Vj respectively.

MV(i, j)  = maximum value the Alice can collect from i'th coin to j'th coin.

In every move Alice has 2 options -

  • Either pick the ith coin (from starting)
  • OR pick the jth coin ( from the end).

Let’s dis­cuss both the options

Alice Picks the ith coin (from starting)

coin game -1

As we can see above if Alice picks the ith coin, Ci then Bob will be left with 2 choices Ci+1 and Cj, since Bob is equally clever than Bob will pick the coin which will leave the Alice with min­i­mum value coins.

So if Bob picks i+1th coin then it will again Alice turn and prob­lem will be reduced to Alice has to pick a coin from i+2th to jth coin and sim­i­larly if   if Bob picks jth coin then it will again Alice turn and prob­lem will be reduced to Alice has to pick a coin from i+1th to j-1th coin.

So Alice will col­lec­tion will be

= Vi + Min{MV(i+2,j), MV(i+1, j-1)}

 Alice Picks the jth coin (from the end)

coin game -2

As we can see above if Alice picks the jth coin, Cj then Bob will be left with 2 choices Ci and Cj-1, since Bob is equally clever than Bob will pick the coin which will leave the Alice with min­i­mum value coins.

So if Bob picks ith coin then it will again Alice turn and prob­lem will be reduced to Alice has to pick a coin from i+1th to j-1th coin and sim­i­larly if Bob picks j-1th coin then it will again Alice turn and prob­lem will be reduced to Alice has to pick a coin from ith to j-2th coin.

So Alice will col­lec­tion will be

= Vi + Min{MV(i+1,j-1), MV(i, j-2)}

So now we need to decide whether Alice should pick ith coin or jth coin. Alice will pick the coin which ever gives the more value con­sid­er­ing 2 moves ahead

so

MV(i, j) = Max { Vi + Min{MV(i+2,j), MV(i+1, j-1)} , Vi + Min{MV(i+1,j-1), MV(i, j-2)}}

Let’s see how the recur­sive equa­tion will look like:

coin game - Recursive Equation (1)
See the Com­plete Code for more understanding:

Out­put:

Max value pick up by player1(Alice)- 23

Ref­er­ence: http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/

You may also like...

  • Venkata NTV

    Hi tuto­ri­al­hori­zon,

    I’m not able to see code to any of the questions…

    • tuto­ri­al­hori­zon

      I am able to see.. All the codes are on gist. Just check if u can see the gist code from some other sites.

  • Sam­rat Sreevatsa

    what hap­pens in case of ODD num­ber of coins?

  • Vipin Sharma

    typo : MV(i, j) = Max { Vi + Min{MV(i+2,j), MV(i+1, j-1)} , Vi + Min{MV(i+1,j-1), MV(i, j-2)}}
    Cor­rec­tion : MV(i, j) = Max { Vi + Min{MV(i+2,j), MV(i+1, j-1)} , Vj + Min{MV(i+1,j-1), MV(i, j-2)}}