Recall the greedy coins game, in which two players alternate removing one of the coins from either end of a row, and the player with the highest total at the end is the winner. What if we wanted to play this game perfectly—is it possible to figure out the best strategy for Alice? Analyzing this game by hand can start to get confusing even for games of length , so we need some sort of way to systematically analyze the possibilities.

At each turn, a player has only two choices, to take the left coin or the right coin. If we record the sequence of right-or-left choices made by the players, we can easily reconstruct the state of the game at each point and the total score for each player. For example, suppose we start with the game

and that the players make the sequence of choices . This means that Alice first took the coin on the right, namely, the 3, thus leaving ; next, Bob took the coin on the right, that is, the 4, leaving ; then Alice took the 1 on the left; and finally, Bob took the only coin remaining, the 2. So Alice’s total is 4, and Bob’s is 6 (Alice did not play very well!). Note that on his last move Bob has no choice at all, since there is only one coin left, which is why we had a sequence of three choices instead of four. In general, for a game with coins, playing the game will result in a sequence of R’s and L’s. Since each move is completely independent of the other moves, there are a total of such move choice sequences.

We can easily list all the possible sequences of R’s and L’s, and compute the resulting score from each. Then we just see which is the biggest, right? Well… not so fast! The biggest possible score for Alice will actually come from the game where Alice plays her best and Bob plays his worst, which is not what we want to know. (Actually, it’s even worse than that: the biggest score comes from Alice playing not the best moves, but the moves that she knows will be the best assuming that Bob plays his worst. That is, her highest possible score might come from playing moves that “shouldn’t” be her best moves, but since Bob will screw up they end up being better than they should be!)

Instead of just blindly evaluating the score from each possible sequence of moves in isolation, we can arrange all possible sequences of moves in a tree, like this:

Each node in the tree corresponds to a position in the game, and has two edges coming out of it corresponding to the two possible choices which could be made by the player whose turn it is. It may seem like I have labelled the edges “backwards”, but when a player takes the coin on the right, it is the coins on the left that remain, and vice versa, so it looks a bit nicer to arrange the tree this way.

Now, when it is Alice’s turn she will be trying to play so as to maximize her score. But Bob will be instead trying to minimize Alice’s score. So we can compute the best overall play by working our way up the tree: for a node where it is Alice’s turn, once we know her score with best play in either subtree, we can pick the move for her that will maximize her score. Likewise, for a node representing Bob’s turn, we can pick the move for him that will minimize Alice’s score. If we keep working our way up the tree in this way, level by level, we can compute the optimal score for Alice (and what moves she should play to get there). Soon I plan to draw a nice picture of how this process works, but it’s taking me a while to create and I didn’t want to hold up this blog post any longer!

So, this works, but there is one big problem: this tree has approximately nodes, which gets very big, very fast. Even if we bump up to a game with 6 coins instead of 4, we can see that the tree is already quite a bit bigger (four times as big, in fact):

And with eight coins it is already looking ridiculous:

There’s one more important observation we can make about these trees which will allow us to cut out a lot of unnecessary work, and avoid having to deal directly with such enormous trees—which I will explain next time!