I want to explain in more detail how we can think about computing the best possible score for Alice in the greedy coins game, assuming best play on the part of both players. I glossed over this too quickly in my previous post.

Recall that we were using this example game:

We can draw out the tree of all possible sequences of moves, like this:

Now, let’s work from the bottom up, computing the best score for Alice at each point. First, the bottom row of the tree corresponds to the point when there is only a single coin left, and it is Bob’s turn. Bob has no choice, and Alice can’t get any more coins. In general, we will put Alice’s best score in a blue square next to each node. Since Alice can’t get any coins at this point in the game, we put a zero next to each game on the bottom row:

Now consider the next row up. In these games, it is Alice’s turn. She wants to maximize her score, so she should pick the coin which gives her the biggest total. Her total will consist of the value of the coin plus the zero she will get from that point on—that is, just the value of the coin.

Notice how in each case we have highlighted Alice’s best move in blue, and written Alice’s best score from this point on in the blue square next to each game. So, for example, in the leftmost game, where only and are left, Alice should take the , and this will give her a total score of .

Considering the next row up, it will be Bob’s turn in these games: of course, he will play so as to minimize Alice’s total score (which is the same as maximizing his score, since the scores always add up to the total value of all the coins). So he should look at the scores Alice will get (i.e. the numbers in the little blue squares) and pick the move that will lead to the smallest number for Alice.

Notice how in the left-hand game (), Bob’s best move is highlighted in green: he should take the , since this will lead to a game in which Alice will get a total of , which is better than his other choice, which will lead to Alice getting . In the right-hand game, it doesn’t matter what Bob picks: Alice will get in either case. So neither move is highlighted for Bob.

We have again written the best score Alice can expect to get from this point on in a little blue square to the right of each game. From the discussion above we can see that for this row (and any even row in general) this will just be the minimum of Alice’s score values from the level below.

Finally, considering the top node, we can analyze Alice’s choices: she can either take the on the right, which leads to a game in which we know she will get more, for a total of ; or she can take the on the left, which leads to a game in which she will get more, again for a total of . So in this case it doesn’t matter which move Alice picks. We write the total in a little blue square to the right of the game, and highlight neither move since either one is optimal. The final analyzed tree looks like this: