- algorithm approximation bar binary binomial coefficients book cards carnival Carnival of Mathematics chocolate circle coins complex convolution counting decadic decimal diagrams Dirichlet factorization fibonacci fractal game games graph groups Haskell hyperbinary idempotent integers interactive irrational Ivan Niven Lagrange lehmer lucas MaBloWriMo making Mersenne moebius mu multiplication nim notation number numbers objects omega order pi prime primes primitive problem programming proof puzzle rectangles review roots sequence square strategy sum symmetry test tree triangular two-player unit unity video visualization X zero-sum
### Blogroll

### Fun

### Reference

### Categories

- algebra (46)
- arithmetic (63)
- books (29)
- calculus (7)
- challenges (52)
- combinatorics (12)
- complex numbers (6)
- computation (46)
- convergence (9)
- counting (32)
- famous numbers (48)
- fibonacci (18)
- fractals (13)
- games (33)
- geometry (56)
- golden ratio (8)
- group theory (26)
- humor (6)
- induction (7)
- infinity (19)
- iteration (24)
- links (74)
- logic (6)
- meta (41)
- modular arithmetic (24)
- number theory (72)
- open problems (11)
- paradox (1)
- pascal's triangle (8)
- pattern (87)
- people (21)
- pictures (65)
- posts without words (20)
- primes (35)
- probability (6)
- programming (17)
- proof (69)
- puzzles (11)
- recursion (16)
- review (20)
- sequences (28)
- solutions (28)
- teaching (14)
- trig (3)
- Uncategorized (6)
- video (19)

### Archives

- May 2017 (7)
- April 2017 (7)
- March 2017 (5)
- February 2017 (4)
- January 2017 (3)
- December 2016 (4)
- November 2016 (6)
- October 2016 (6)
- September 2016 (2)
- August 2016 (5)
- July 2016 (2)
- June 2016 (4)
- May 2016 (4)
- April 2016 (2)
- March 2016 (3)
- February 2016 (9)
- January 2016 (8)
- December 2015 (5)
- November 2015 (29)
- August 2015 (3)
- June 2015 (2)
- April 2015 (1)
- May 2014 (1)
- December 2013 (1)
- October 2013 (1)
- July 2013 (1)
- June 2013 (1)
- May 2013 (1)
- April 2013 (3)
- March 2013 (3)
- February 2013 (2)
- January 2013 (5)
- December 2012 (3)
- November 2012 (4)
- October 2012 (5)
- September 2012 (1)
- August 2012 (4)
- July 2012 (1)
- June 2012 (6)
- May 2012 (2)
- April 2012 (3)
- March 2012 (1)
- February 2012 (4)
- January 2012 (5)
- December 2011 (1)
- November 2011 (7)
- October 2011 (4)
- September 2011 (6)
- July 2011 (2)
- June 2011 (4)
- May 2011 (5)
- April 2011 (2)
- March 2011 (4)
- February 2011 (1)
- January 2011 (1)
- December 2010 (1)
- November 2010 (4)
- October 2010 (2)
- September 2010 (1)
- August 2010 (1)
- July 2010 (1)
- June 2010 (2)
- May 2010 (3)
- April 2010 (1)
- February 2010 (6)
- January 2010 (3)
- December 2009 (8)
- November 2009 (7)
- October 2009 (3)
- September 2009 (3)
- August 2009 (1)
- June 2009 (4)
- May 2009 (5)
- April 2009 (4)
- March 2009 (2)
- February 2009 (1)
- January 2009 (7)
- December 2008 (1)
- October 2008 (2)
- September 2008 (7)
- August 2008 (1)
- July 2008 (1)
- June 2008 (1)
- April 2008 (5)
- February 2008 (4)
- January 2008 (4)
- December 2007 (3)
- November 2007 (12)
- October 2007 (2)
- September 2007 (4)
- August 2007 (3)
- July 2007 (1)
- June 2007 (3)
- May 2007 (1)
- April 2007 (4)
- March 2007 (3)
- February 2007 (7)
- January 2007 (1)
- December 2006 (2)
- October 2006 (2)
- September 2006 (6)
- July 2006 (4)
- June 2006 (2)
- May 2006 (6)
- April 2006 (3)
- March 2006 (6)

### Meta

## Computing optimal play for the greedy coins game, part 4

Last time I explained a method for computing best play for instances of the greedy coins game, which is feasible even for large games. This general approach is known as *dynamic programming* and is applicable whenever we have some recursively defined thing where the recursion generates a lot of overlap/duplication: in our case, the game tree and the values for Alice are defined recursively, but we saw that there is a lot of duplication of subgames. The solution is to organize things in such a way that we never have to look at a particular subthing more than once.

In practice, instead of thinking about trees, we can just keep an upper-triangular matrix , where will denote Alice’s best score from the point when only coins are left. (The matrix is upper-triangular since this only makes sense when .) We can also keep a separate upper-triangular matrix where is the best move when coins are left ( means that both moves are equally good).

When coins are left, either coin or coin will be taken, leaving coins or . So, if we already know the values of and , we can use them to compute the optimal value for (and to decide which move is better). This corresponds to the observation that we can compute the value at a node in the game tree as long as we already know the values at both of its children.

Here is one way to visualize these tables, turned diagonally so it ends up looking very similar to the compact trees from my previous post; each cell corresponds to the coins along the base of the triangle which has that cell as its apex. The light blue square in each cell shows the value of ; the arrows indicate the best move(s) , with blue arrows for Alice’s moves and green for Bob’s.

For example, the top cell says that from this state (when all four coins remain) Alice will get 5 points with best play, and the two blue arrows mean that it does not matter which coin Alice takes. Suppose she takes the , so the are left. The corresponding cell is the cell at the apex of the triangle whose base is :

So now Bob can look at this cell to see what his optimal play is. He can see that from this position Alice will get 2 more points if they both play their best. He can also see from the green arrow that his best move is to move into the cell below and to the left, that is, to leave Alice with the coins —which means he should take the coin on the *right*, namely, the . Finally, Alice’s best move in this situation is to take the on the right, with the blue arrow pointing to what Bob is left with.

Using this visualization we can easily look at bigger games. For example, in my first post I left readers with the challenge of analyzing this game:

From the table we can now see that Alice will score points with best play, and that her best move is to start by taking the (the blue arrow points to the right, so she should take the on the left in order to send Bob to the game on the right). It doesn’t matter which move Bob plays next, and then Alice will take either the or the , depending on Bob’s move, and so on.

One nice thing to note is that these tables don’t just tell us what should happen when *both* players play optimally. They tell us the optimal play in *any* subgame. In other words, one could say that they even show us how to best capitalize on mistakes made by our opponent. To play the greedy coins game perfectly, first just compute the tables and (actually, this is not too hard to learn how to do by hand, especially if you use the above format). Then when it is your turn, if coins remain just look up to see what your best move is. If you have used the above format you don’t even need to bother with keeping track of the indices and ; just find the remaining coins along the bottom and find the apex of their triangle. (In addition to finding your best move you can also confidently, and annoyingly, announce to your opponent that you will get at least points no matter what they do; for extra annoyingness, you can let your opponent choose your move whenever the move table tells you that both moves are optimal.)

Just for fun, here’s an analysis of the slightly larger game , which is a counterexample to one of my original conjectures about tied games:

One final thing I will mention is that it’s hard to tell from looking at Alice’s *total* score whether the game is tied, or how much Alice will win by. Of course we can compute it if we know the total value of all the coins: Alice will win by the difference between her total and half the total coin value. But it might be nicer to directly visualize not Alice’s *total* score but the *margin* of her victory over Bob. This is related to the function defined by Eric Burgess in a previous comment; more on this in a future post.

Posted in computation, games, recursion
Tagged coins, dynamic, game, optimal, play, programming, proof, recurrence, strategy, tree, two-player, zero-sum
Leave a comment

## 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 , 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.

Posted in computation, games, recursion
Tagged coins, game, optimal, play, proof, recurrence, strategy, tree, two-player, zero-sum
2 Comments

## Computing optimal play for the greedy coins game, part 2

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:

Posted in computation, games, recursion
Tagged coins, game, optimal, play, proof, recurrence, strategy, tree, two-player, zero-sum
1 Comment

## Computing optimal play for the greedy coins game

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!

Posted in computation, games, recursion
Tagged coins, dynamic programming, game, optimal, play, proof, recurrence, strategy, two-player, zero-sum
2 Comments