Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Pots of gold

Sharing is caring!

Problem statement
Pots of gold game: Two players A and B. There are 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 – perfect information). They get 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. A starts the game.

The idea is to find an optimal strategy that makes A win knowing that B is playing optimally as well. How would you do that?

Solution
Because A plays optimally, the problem of maximizing the coins collected by A becomes equal to minimizing the coins collected by B. Similarly because B also plays optimally, the problem of maximizing the coins collected by B becomes equal to minimizing the coins collected by A.

Without loss of generality, assume A plays first. He will have two possible choices:

  1. He can choose the pot at the start of the line. Then B chooses next. B can choose either start+1 or end.
    1. If B chooses start+1, A is left with two options start+2 and end.
    2. If B chooses end, A is left with two options start+1 and end-1.
      \rightarrow A's outcome will be pots[start] + minimum(choose(start + 2, end), choose(start + 1, end - 1)).
  2. He can choose the pot at the end of the line. Then B chooses next. B can choose either start or end-1.
    1. If B chooses start, A is left with two options start+1 and end-1.
    2. If B chooses end-1, A is left with two options start and end-2.
      \rightarrow A's outcome will be pots[end] + minimum(choose(start + 1, end-1), choose(start, end - 2)).

The reason we take the minimum is because B also plays optimally. That is, B chooses the pots that minimize the output for A. So when A chooses pots[start] or pots[end], on A's next turn what’s left will be the minimum of what A could get.

Full code