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?
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.