Maximum margin for victory in coins pick up game problem

#1

I am trying to solve the following problem from EPI:
Design an efficient algorithm for computing the maximum margin of victory for the starting player in the pick-up-coins game.

I saw the recurrence and am unable to understand the intuition behind the recurrence solution, i.e.:
f(a,b) = max| C[a] + min( f(a+2,b), f(a+1,b-1) ) ,
| C[b] + min( f(a,b-2), f(a+1,b-1) )

I see that it gives the correct answer but am unable to get my head around it. If anyone has an explanation regarding this it would be greatly appreciated.
Thanks

0 Likes
#2

f(a,b) = max(c[a]+min(f(a+2,b),f(a+1,b-1)), c[b]+min(f(a,b-2),f(a+1,b-1))

Player needs to determine the maximum profit between choice a and b. Thus max(choice a, choice b).

The reason for the min() is because player 2 is trying to maximize his own profit, thus from player1’s perspective, he needs to calculate the smallest profit he can gain after picking a or b.

For example, if player1 takes from a, then player 2 has 2 choices: f(a+2,b),f(a+1,b-1), both call to the function returns the maximum profit from picking from a or b. Player 2 will pick the choice that gives the largest revenue, leaving player1 with the lesser choice. Thus the equation is expressed using min() function.

1 Like
#3

You should lookup the minimax decision making tree. Its the same idea.

0 Likes
#4

Hey @foolan,

It is exactly like what @telenoobies explained, and this is what people called minmax optimization problem.

0 Likes
#5

Still dunt understand. Shouldn’t it be
f(a,b) = max(c[a]+min(f(a+1,b),f(a,b-1)), c[b]+min(f(a,b-1),f(a+1,b))

Instead of

0 Likes
#6

Yea this question is confusing to understand. I think the key point here is to realize that f(a,b) doesn’t do what you think it does (yes it does return an int revenue, but you are missing a very important detail). f(a,b) doesn’t care which player it is… lets break down your equation and see what it says:

f(a,b) = max(c[a]+min(f(a+1,b),f(a,b-1)), c[b]+min(f(a,b-1),f(a+1,b))

First,

c[a]+min(f(a+1,b),f(a,b-1))

What you are saying here is, the total amount Player gets when he chooses index a, is the coin itself plus the minimum revenue between picking a+1 or b-1. Which doesn’t make sense right? I mean, how are you taking Opponent into account?

Fine, lets argue from a different perspective. Lets say that we assume f(a+1,b) returns opponent’s revenue, then why are you adding your opponent’s revenue to the Players? Makes no sense either right?

Now go back to the original equation:

f(a,b) = max(c[a]+min(f(a+2,b),f(a+1,b-1)), c[b]+min(f(a,b-2),f(a+1,b-1))
c[a]+min(f(a+2,b),f(a+1,b-1))

The Opponent wants to minimize Player’s revenue, thus its equivalent to saying Player’s revenue is equals to the coin he picks up, plus the MIN revenue he can gain AFTER opponent picks up a+1 or b-1, thats why its a+2 or b-2, its from the Player’s perspective.

This solutions is really clever, you just have to keep thinking about it. I hope someone else can explain it better than I did. The insight for me was realizing the very subtle but important difference between

c[a]+min(f(a+1,b),f(a+1,b-1)
c[a]+min(f(a+2,b),f(a+1,b-1)

And that the equation is formulated from the Player’s perspective.

1 Like