 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 powers prime primes primitive problem programming proof puzzle review roots sequence square strategy sum symmetry test tree triangular twoplayer unit unity video visualization X zerosum
Blogroll
Fun
Reference
Categories
 algebra (46)
 arithmetic (63)
 books (29)
 calculus (7)
 challenges (53)
 combinatorics (12)
 complex numbers (6)
 computation (46)
 convergence (9)
 counting (32)
 famous numbers (48)
 fibonacci (18)
 fractals (13)
 games (34)
 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 (75)
 open problems (11)
 paradox (1)
 pascal's triangle (8)
 pattern (89)
 people (21)
 pictures (67)
 posts without words (22)
 primes (35)
 probability (6)
 programming (17)
 proof (69)
 puzzles (14)
 recursion (16)
 review (20)
 sequences (28)
 solutions (28)
 teaching (14)
 trig (3)
 Uncategorized (6)
 video (19)
Archives
 June 2017 (4)
 May 2017 (9)
 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 uppertriangular matrix , where will denote Alice’s best score from the point when only coins are left. (The matrix is uppertriangular since this only makes sense when .) We can also keep a separate uppertriangular 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, twoplayer, zerosum
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 reasonablesized 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, twoplayer, zerosum
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 lefthand 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 righthand 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, twoplayer, zerosum
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 rightorleft 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, twoplayer, zerosum
2 Comments
Another greedy coins game update
Another update on the analysis of the greedy coins game (previous posts here, here, and here). I will make another post very soon explaining how to compute optimal play.
In my previous post I reported that Thibault Vroonhove had conjectured the following strategy to be optimal for Alice:

If the two end coins have unequal values, and the larger of the two is also larger than its neighbor, take it.

Otherwise, look at the alternating totals (i.e. the total of the “red” coins and the total of the “blue” coins). Take the end coin corresponding to whichever group has the higher total.

If neither of these rules apply then it doesn’t matter which coin Alice takes.
Note that if the first rule applies, Alice definitely wins by following it: this was proved in a comment by Eric Burgess (though I don’t think it is clear whether this would always be Alice’s best play). The proof is actually not hard to understand (it is obscured a bit in Eric’s presentation because he was trying to investigate something more general): if Alice takes a coin which is bigger than either of the coins Bob could take next, she will be ahead after those two turns. Then it will be Alice’s turn, and it will be as if they are starting a brand new game. But we know that Alice can always at least force a tie. So since she gets ahead after the first two moves and can force the rest of the game to be a tie, she will win.
Now, it turns out that it can matter which coin Alice takes if neither of the two rules apply. Consider the game :
Neither of the rules apply here: the bigger end number, 3, is not bigger than its neighbor, and considering sets of alternating coins we have . However, it matters which coin Alice takes: her only winning move is to take the 3 (she will win by 2). If she takes the 2, the game will be a tie.
Thibault then modified his conjecture to add a third rule: if neither of the first two rules apply, Alice should play to minimize her local loss, that is, she should play so as to maximize the difference between the coin she takes and the larger of the two coins left to Bob. Unfortunately, this does not work either: I wrote a program to search for counterexamples, and it came up with .

The 3 is not bigger than its neighbor (5) so the first rule does not apply.

, so the second rule does not apply either.

The third rule would now tell Alice to take the 2: the biggest coin left to Bob after taking the 2 is the 3, giving Alice a local loss of 1; on the other hand, if Alice takes the 3, the biggest coin left to Bob is a 5, for a local loss of 2. However, it turns out that taking the 3 is actually Alice’s best move: she will win by 2. On the other hand, taking the 2 results in a tie.
Ultimately, based on my experience with solving these sorts of problems from a computational point of view, I am skeptical that this sort of approach can work. In my next post I will explain how Alice can compute an optimal strategy, but the time (and memory) needed for the computation scales quadratically with the size of the game; that is, finding the optimal play for a game of length takes time proportional to . By contrast, note that Thibault’s strategy takes time linear in . I conjecture that the optimal strategy actually cannot be computed in subquadratic time. (I would really love to be proven wrong, though, because I think one could use a lineartime algorithm to play perfectly against one’s friends—a great party trick if you go to the right sort of parties—whereas I doubt a quadratic algorithm would be feasible to do quickly enough in one’s head.)
Finally, I will note that in the comments to my previous post, Eric Burgess made some great strides in understanding the theory of the game. I hope you will be able to read more about that soon!
Posted in games, proof
Tagged coins, conjecture, game, proof, strategy, twoplayer, zerosum
Leave a comment