In a previous post we saw how we can organize play sequences in the greedy coins game into a tree. Then in the last post, we saw how to work our way from the bottom of the tree upward and compute the optimal score for Alice at each node—with Alice always making the choice that will give her the maximum score, and Bob always making the choice that will give her the minimum score (and thus giving him the maximum):

However, there is one big problem: for a game of length , this tree will have approximately nodes. Even for a reasonable-sized game of, say, coins (which is, of course, the official standard size used at the annual International Greedy Coins Championship, or IGCC), such a tree would have over one million nodes! And we only have to get up to or so coins—a big game, to be sure, but well within the realm of possibility—before the resulting tree would have more nodes than there are atoms in the universe. (!!)

But there is one important detail that saves us: these trees have a lot of repetition. Look again at the tree for :

Notice how the game occurs twice on the third level of the tree, because there are two ways to get there: Alice could take the 3 and then Bob could take the 1; or Alice could take the 1 and Bob could take the 3. Of course these are different play sequences and result in different overall results for Bob and Alice; but in either case they end up in the same position: with coins and on the table with Alice to move. Likewise, notice that the game consisting of just a single occurs three times (the sequences RRL, RLR, and LRR all lead to it), as does the game consisting of just a single .

There is a very nice way to draw the tree of possibilities that avoids this duplication:

Each possible subgame occurs exactly once, and there may be multiple paths that can be used to reach it. For example, there are three different paths that end in the single at the bottom: RRL, RLR, and LRR. Of course, these correspond exactly to the three copies of that we saw in the previous tree. In general, after we have taken the leftmost coin times and the rightmost coin times, we will have remaining coins through —and the order in which those coins were taken does not matter; we end up with the same remaining coins in any case. (Can you say how many different paths we could have used to get there?)

We can now analyze this compact “tree” in the same way as we did previously (start from the bottom and work our way up by alternating levels); the only difference is that we are no longer doing any redundant work!

This works precisely because we can analyze each subgame independently of the path taken to get there: the best play from a given point onwards is not influenced by the order of moves that came before. Given that we have already analyzed all the games in one level of the tree, we can use them to analyze the games one level up, and so on, until we reach the top.

Previously, the tree for a game of length had about nodes; now we can see that in these compact “trees”, there are games on the bottom row, on the next row up, on the next, and so on, for a total of

nodes. This is much, much better! Remember how drawing the entire tree for coins would require more nodes than there are atoms in the universe? Well, is only —a number which is, shall we say, slightly smaller. While I still wouldn’t particularly want to draw the whole compact tree by hand, having a computer analyze it is entirely feasible. And not just feasible in the sense of theoretically possible; practically speaking, by analyzing a compact game tree, any modern desktop computer could compute the optimal play for a -coin game in a fraction of a second.