Pots of Gold Game using Dynamic Programming

In Pots of gold game, there are two players A & B and pots of gold arranged in a line, each containing some gold coins. The players can see how many coins are there in each gold pot and each player gets alternating turns in which the player can pick a pot from one of the ends of the line. The winner is the player which has a higher number of coins at the end. The objective is to “maximize” the number of coins collected by A, assuming B also plays optimally and A starts the game.

 

For example,


                      Player    Opponent

4, 6, 2, 3              3
4, 6, 2                            4
6, 2                    6
2                                  2
                     9 coins    6 coins


                      Player    Opponent

6, 1, 4, 9, 8, 5        6
1, 4, 9, 8, 5                      5
1, 4, 9, 8              8
1, 4, 9                            9
1, 4                    4
1                                  1
                     18 coins   15 coins

 


 

The idea is to find an optimal strategy that makes player wins knowing that opponent is playing optimally as well. The player has two choices for coin[i..j] where i and j denotes the front and rear of the line respectively.

If the player chooses front pot i, opponent is left to choose from [i+1, j].

1. if opponent chooses front pot i+1, recurse for [i+2, j]
2. if opponent chooses rear pot j, recurse for [i+1, j-1]

If the player chooses rear pot j, opponent is left to choose from [i, j-1].

1. if opponent chooses front pot i, recurse for [i+1, j-1]
2. if opponent chooses rear pot j-1, recurse for [i, j-2]

 

Since opponent is playing optimally as well, he will try to minimize the points collected by the player. i.e. opponent will make a choice that will leave the player with minimum coins. So the problem can be recursively defined as –


                        | coin[i]                     (if i = j)
optimalStrategy(i, j) = | max(coin[i], coin[j])       (if i + 1 = j)
                        | max (coin[i] + min(optimalStrategy(coin, i + 2, j),
                                        optimalStrategy(coin, i + 1, j – 1)),
                          coin[j] + min(optimalStrategy(coin, i + 1, j – 1),
                                           optimalStrategy(coin, i, j – 2)))

 
Below is C++ implementation of above approach:

 

Download   Run Code

Output:

Maximum coins collected by player is 9

 
The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

 


 

The problem has an optimal substructure. We have seen that the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on. The problem also exhibits overlapping subproblems so we will end up solving the same subproblem over and over again. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are Memoized rather than computed again and again. This method is illustrated below –

 

Download   Run Code

Output:

Maximum coins collected by player is 9

 

The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

 
Below is bottom-up version of above solution:

 

Download   Run Code

Output:

Maximum coins collected by player is 9

 

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz