Another update on the analysis of the greedy coins game (previous posts here, here, and here). I will make another post very soon explaining how to compute optimal play.

In my previous post I reported that Thibault Vroonhove had conjectured the following strategy to be optimal for Alice:

• If the two end coins have unequal values, and the larger of the two is also larger than its neighbor, take it.

• Otherwise, look at the alternating totals (i.e. the total of the “red” coins and the total of the “blue” coins). Take the end coin corresponding to whichever group has the higher total.

• If neither of these rules apply then it doesn’t matter which coin Alice takes.

Note that if the first rule applies, Alice definitely wins by following it: this was proved in a comment by Eric Burgess (though I don’t think it is clear whether this would always be Alice’s best play). The proof is actually not hard to understand (it is obscured a bit in Eric’s presentation because he was trying to investigate something more general): if Alice takes a coin which is bigger than either of the coins Bob could take next, she will be ahead after those two turns. Then it will be Alice’s turn, and it will be as if they are starting a brand new game. But we know that Alice can always at least force a tie. So since she gets ahead after the first two moves and can force the rest of the game to be a tie, she will win.

Now, it turns out that it can matter which coin Alice takes if neither of the two rules apply. Consider the game :

Neither of the rules apply here: the bigger end number, 3, is not bigger than its neighbor, and considering sets of alternating coins we have . However, it matters which coin Alice takes: her only winning move is to take the 3 (she will win by 2). If she takes the 2, the game will be a tie.

Thibault then modified his conjecture to add a third rule: if neither of the first two rules apply, Alice should play to minimize her local loss, that is, she should play so as to maximize the difference between the coin she takes and the larger of the two coins left to Bob. Unfortunately, this does not work either: I wrote a program to search for counterexamples, and it came up with .

• The 3 is not bigger than its neighbor (5) so the first rule does not apply.

• , so the second rule does not apply either.

• The third rule would now tell Alice to take the 2: the biggest coin left to Bob after taking the 2 is the 3, giving Alice a local loss of 1; on the other hand, if Alice takes the 3, the biggest coin left to Bob is a 5, for a local loss of 2. However, it turns out that taking the 3 is actually Alice’s best move: she will win by 2. On the other hand, taking the 2 results in a tie.

Ultimately, based on my experience with solving these sorts of problems from a computational point of view, I am skeptical that this sort of approach can work. In my next post I will explain how Alice can compute an optimal strategy, but the time (and memory) needed for the computation scales quadratically with the size of the game; that is, finding the optimal play for a game of length takes time proportional to . By contrast, note that Thibault’s strategy takes time linear in . I conjecture that the optimal strategy actually cannot be computed in sub-quadratic time. (I would really love to be proven wrong, though, because I think one could use a linear-time algorithm to play perfectly against one’s friends—a great party trick if you go to the right sort of parties—whereas I doubt a quadratic algorithm would be feasible to do quickly enough in one’s head.)

Finally, I will note that in the comments to my previous post, Eric Burgess made some great strides in understanding the theory of the game. I hope you will be able to read more about that soon!