There n stacks of coins. Each stack contains k_i coins and the coins in a particular stack have distinct values. In each turn, you get to pick one coin from the top of any stack, and your opponent can pick one coin from the bottom of any stack. The person with the highest value of coins wins.
What would be the optimal strategy for this game?
I think it should be some kind of greedy algorithm combined with the opponents response and maybe splitting each stack in half to compare values maybe?
As a special case, consider if all the stacks are even.
The second player can copy the first player to get value equal to all the bottom halves of the stacks. This shows that the value of the game for the second player is at least bottom - top (i.e. value of game for the first player is at most top - bottom).
Similarly, the first player can take from any stack, then copy the second player to get value equal to all the top halves of the stacks. (If the second player plays from the odd stack, the first player is again free to take from any stack.) This strategy guarantees the first player to get value equal to all the top halves of the stacks. This shows that the value of the game for the first player is at least top - bottom.
Therefore, the value of this game is exactly top - bottom and the optimal strategy for at least one player is this copying approach. Of course, if the players are not playing optimally it may be possible to do better, but this is the theoretical optimum value with best play on both sides.
With odd sized stacks more care needs to be taken about the central values of each stack.
In general, the value for a set of stacks is given by adding the values on your side, subtracting the values in the other side, and taking turns to add/subtract any central values (in decreasing size order). (If it is your turn, the first value is added, otherwise the first value is subtracted.)
In Python, this could be written as:
def compute_value(stacks):
t=0
middle=[]
for S in stacks:
n=len(S)
n2,r = divmod(n,2)
t += sum(S[:n2]) - sum(S[n2+r:])
if r:
middle.append(S[n2])
middle.sort(reverse=True)
for i,m in enumerate(middle):
if i%2==0:
t += m
else:
t -= m
return t
This leads to an efficient optimal strategy. Simply consider taking one coin from each stack, compute the value of the resulting stacks (form the opponents perspective), and choose the option that gives you the highest score (score = value of coin + value of resulting stacks).
Note that this is efficient because you only need to consider one move ahead, you do not need to explore a whole tree of moves.
(This could also be optimized further because all values in the stacks can be ignored other than the coins that could be taken on this turn, the central coins, and the coins that could become central coins.)
First lets try to find which gems will be taken if both players play optimally. Instead of a stack, let's assume the gems assume that the gems were arranged in a row and the players put a mark beside the gems they pick.
Lemma 5.1: First let’s prove that if any player chooses, they can forcefully split all stacks as evenly as possible. To do this, a player simply has to mirror their opponents moves, and all the stacks will end up getting split as evenly as possible.
The hypothesis based on intuition is that if both players play optimally, then they will end up only picking gems from their half. We only compare two stacks out of all the stacks. So we will get 3 cases:
Case 1: Even and Even
Let's take some two stacks with $2m$ and $2n$ gems and let the gems be numbered as $a_1,a_2,...,a_{2m} $ and $b_1,b_2,...,b_{2n}$ from left to right respectively, and player 1 chooses from the left and player 2 from the right.
By intuition, we expect the players to split each stack perfectly evenly between them. So let's assume the contrary, that in the end, player 1 has chosen gems $a_1,a_2,...,a_m,...,a_{m+k}$ and $b_1,b_2,...,b_{n-k}$ and player 2 chose the remaining gems in these two stacks.
From Lemma 5.1, we know that any player could have forced a split, but since they didn’t, we can assume that the sum of the values of gems from $a_{m+1},...,a_{m+k}$ and from $b_{n-k+1},...,b_n$ are equal, because otherwise, it would mean that the players didn’t play optimally. It is possible that the values are equal, but when we are playing, we can choose to split it evenly for the sake of simplicity.
Case 2: Odd and Odd
Let’s do the exact same thing as before but two stacks having $2m+1$ and $2n+1$ gems. So the center most gems are $a_{m+1}$ and $b_{n+1}$.
Let’s again assume that in the end, player 1 has chosen gems $a_1,a_2,...,a_{m+1},...,a_{m+1+k}$ and $b_1,b_2,...,b_{n+1-k}$ and player 2 chose the remaining gems in these two stacks. Similar to the previous case, the sum of the values of gems from $a_{m+2},...,a_{m+1+k}$ and from $b_{n+1-k+1},...,b_{n+1}$ must be equal, because both players are assumed to be playing optimally. The only difference is in this case, the player who gets to go first can choose the greater of the gems between $a_{m+1}$ and $b_{n+1}$. Therefore, we can split the stacks equally and need only compare the center gems.
Case 3: Even and Odd
Let’s do the exact same thing as before but two stacks having 2m and 2n+1 gems. So the center gem for stack B is b_(n+1). Let’s assume that player 1 picks first.
Let’s assume that in the end, player 1 has chosen gems $a_1,a_2,...,a_m,...,a_{m+k}$ and $b_1,b_2,...,b_{n+1-k}$ and player 2 chose the remaining gems in these two stacks. Similar to the previous case, the sum of the values of gems from $a_{m+1},...,a_{m+k}$ and from $b_{n+1-k+1},...,b_{n+1}$ must be equal.
Similarly, if in the end, player 1 has chosen gems $a_1,a_2,...,a_{m-k}$ and $b_1,b_2,...,b_{n+1},...,b_{n+1+k}$ and player 2 chose the remaining gems, then the sum of the values of gems from $a_{m-k+1},...,a_m$ and from $b_{n+2},...,b_{n+1+k}$ must be equal. So we can just split each stack in half for the sake of simplicity.
Therefore, the optimal strategy (for both players) would be to split each stack with an even number of gems in half, and order all the stacks with an odd number of gems in descending based on the value of their center gems and then the 1st stack will be split such that the player 1(assume player 1 starts) gets the center gem, and the 2nd stack will be split such that the player 2 gets the center gem, and the $(2n-1)th$ stack with an odd number of gems will split with player 1 getting the center gem, and the $(2n)th$ stack with an odd number of gems will split with player 2 getting the center gem.
Therefore, if we go first, we must choose the stack with an odd number of gems and the most valuable center gem, and we can simply mirror the bot’s moves until the stack gets removed, because we are assuming that the bot is also playing optimally. If there are no partially empty stacks in your turn, you should choose a stack with an odd number of gems with the currently most valuable center gem.
Let’s sort and number all stacks with an odd number of gems in descending, based on their center gem, from 1 to $k$.
By this strategy, if both players play optimally, assuming player 1 goes first and picks from the top,
Player 1’s score = sum of the values of all gems in the top half of all stacks with an even number of gems + sum of the values of all gems in the top half of the stacks with an odd number of gems { including the center gem if the stack is numbered as an odd number, and excluding the center gem if the stack is numbered as an even number}
Player 2’s score = sum of the values of the remaining gems
I think this is the outcome if both players play with (what I think is) the most optimal strategy.