Understanding solution to finding optimal strategy for game involving picking pots of gold

Question

I am having trouble understanding the reasoning behind the solution to this question on CareerCup.

Pots of gold game: Two players A & 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?

At the end I was asked to code this strategy!

This was a question from a Google interview.

The proposed solution is:

function max_coin( int *coin, int start, int end ):
    if start > end:
        return 0

    // I DON'T UNDERSTAND THESE NEXT TWO LINES
    int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1))
    int b = coin[end] + min(max_coin(coin, start+1,end-1), max_coin(coin, start, end-2))

    return max(a,b)

There are two specific sections I don't understand:

1. In the first line why do we use the ranges [start + 2, end] and [start + 1, end - 1]? It's always leaving out one coin jar. Shouldn't it be [start + 1, end] because we took the starting coin jar out?
2. In the first line, why do we take the minimum of the two results and not the maximum?
3. Because I'm confused about why the two lines take the minimum and why we choose those specific ranges, I'm not really sure what a and b actually represent?

Answer 1

a and b here represent the maximum A can get by picking the starting pot or the ending pot, respectively.

We're actually trying to maximize A-B, but since B = TotalGold - A, we're trying to maximize 2A - TotalGold, and since TotalGold is constant, we're trying to maximize 2A, which is the same as A, so we completely ignore the values of B's picks and just work with A.

The updated parameters in the recursive calls include B picking as well - so coin[start] represents A picking the start, then B picks the next one from the start, so it's start+2. For the next call, B picks from the end, so it's start+1 and end-1. Similarly for the rest.

We're taking the min, because B will try to maximize it's own profit, so it will pick the choice that minimizes A's profit.

But actually I'd say this solution is lacking a bit in the sense that it just returns a single value, not 'an optimal strategy', which, in my mind, would be a sequence of moves. And it also doesn't take into account the possibility that A can't win, in which case one might want to output a message saying that it's not possible, but this would really be something to clarify with the interviewer.

Answer 2

First of all a and b represent respectively the maximum gain if start (respectively end) is played.

So let explain this line:

int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1))

If I play start, I will immediately gain coin[start]. The other player now has to play between start+1 and end. He plays to maximize his gain. However since the number of coin is fixed, this amounts to minimize mine. Note that

• if he plays start+1 I'll gain max_coin(coin, start+2, end)
• if he plays end Ill gain max_coin(coin, start+1, end-1)

Since he tries to minimize my gain, I'll gain the minimum of those two.

Same reasoning apply to the other line where I play end.

Note: This is a bad recursive implementation. First of all max_coin(coin, start+1, end-1) is computed twice. Even if you fix that, you'll end up computing lots of time shorter case. This is very similar to what happens if you try to compute Fibonacci numbers using recursion. It would be better to use memoization or dynamic programming.