Computing optimal play for the greedy coins game, part 3

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 2n, this tree will have approximately 2^{2n} nodes. Even for a reasonable-sized game of, say, 20 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 270 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 1243:

Notice how the game 2,4 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 2 and 4 on the table with Alice to move. Likewise, notice that the game consisting of just a single 2 occurs three times (the sequences RRL, RLR, and LRR all lead to it), as does the game consisting of just a single 4.

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 2 at the bottom: RRL, RLR, and LRR. Of course, these correspond exactly to the three copies of 2 that we saw in the previous tree. In general, after we have taken the leftmost coin l times and the rightmost coin r times, we will have remaining coins 1+l through 2n-r—and the order in which those r+l 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 2n had about 2^{2n} nodes; now we can see that in these compact “trees”, there are 2n games on the bottom row, 2n-1 on the next row up, 2n-2 on the next, and so on, for a total of

\displaystyle 1 + 2 + 3 + \dots + 2n = 2n(2n+1)/2 = 2n^2 + n

nodes. This is much, much better! Remember how drawing the entire tree for 270 coins would require more nodes than there are atoms in the universe? Well, 2 \cdot 270^2 + 270 is only 146070—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 270-coin game in a fraction of a second.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in computation, games, recursion and tagged , , , , , , , , , . Bookmark the permalink.

2 Responses to Computing optimal play for the greedy coins game, part 3

  1. Naren Sundar says:

    The number of ways to get to a state with K coins (with L coins removed to the left of it and R coins removed to the right of it) in an N (= K + L + R) coin game is:
    – equal to the number of ways we can arrange L 0s and R 1s
    – this is equal to (L+R)! / L! R!

  2. Pingback: Computing optimal play for the greedy coins game, part 4 | The Math Less Traveled

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s