Post without words #16

Image | Posted on by | Tagged , , , | 7 Comments

Now on

Christian Lawson-Perfect and Colin Wright have set up an instance of Mastodon—a decentralized, open-source Twitter clone—as a place for mathy folks to be social. It’s appropriately named, and because it’s open-source they were able to easily hack in \LaTeX support. Neato! I’ve never been on Twitter—the costs of the resulting distraction would far outweight any benefits for me—but seems like it could be a fun place to discuss math without being endlessly distracting (we’ll see), so I decided to try it out for now: I’m @byorgey.

Here’s my initial entry to the #proofinatoot contest—the idea is to write a proof that fits in Mastodon’s 500-character limit for “toots” (you know, like a tweet, but more mastodon-y). To fit this proof into 500 characters I had to leave out a lot of details; it was a fun exercise to take a cool proof and try to distill it down to just its core ideas. Can you fill in the details I omitted? (Also, can you figure out what word is commonly used to refer to graphs with these properties?)

Let G be a graph with |V|=n. Any two of the following imply the third: 1. G is connected; 2. G is acyclic; 3. G has n-1 edges.

1,2 \Rightarrow 3: by induction. Any walk must reach a leaf. Delete it and apply the IH.

1,3 \Rightarrow 2: by induction. Sum of degrees is 2(n-1), so there are at least two leaves. Delete one and apply the IH.

2,3 \Rightarrow 1: Let G have c connected components. Since 1,2 \Rightarrow 3 for each, the total number of edges is n-c, hence c=1.

Posted in meta, proof | Tagged , , , , , , | 2 Comments

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 A, where A[i,j] will denote Alice’s best score from the point when only coins i \dots j are left. (The matrix is upper-triangular since this only makes sense when i \leq j.) We can also keep a separate upper-triangular matrix M where M[i,j] \in \{\textsf{L},\textsf{R}, \textsf{LR}\} is the best move when coins i \dots j are left (\textsf{LR} means that both moves are equally good).

When coins i \dots j are left, either coin i or coin j will be taken, leaving coins (i+1) \dots j or i \dots (j-1). So, if we already know the values of A[i+1,j] and A[i,j-1], we can use them to compute the optimal value for A[i,j] (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 A[i,j]; the arrows indicate the best move(s) M[i,j], 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 3, so the 1,2,4 are left. The corresponding cell is the cell at the apex of the triangle whose base is 1,2,4:

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 1,2—which means he should take the coin on the right, namely, the 4. Finally, Alice’s best move in this situation is to take the 2 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 27 points with best play, and that her best move is to start by taking the 1 (the blue arrow points to the right, so she should take the 1 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 9 or the 17, 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 A and M (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 i \dots j remain just look up M[i,j] 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 i and j; 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 A[i,j] 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 12212112, 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 S function defined by Eric Burgess in a previous comment; more on this in a future post.

Posted in computation, games, recursion | Tagged , , , , , , , , , , , | 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 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.

Posted in computation, games, recursion | Tagged , , , , , , , , , | 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 1 and 2 are left, Alice should take the 2, and this will give her a total score of 2.

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 (124), Bob’s best move is highlighted in green: he should take the 4, since this will lead to a game in which Alice will get a total of 2, which is better than his other choice, which will lead to Alice getting 4. In the right-hand game, it doesn’t matter what Bob picks: Alice will get 4 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 3 on the right, which leads to a game in which we know she will get 2 more, for a total of 5; or she can take the 1 on the left, which leads to a game in which she will get 4 more, again for a total of 5. So in this case it doesn’t matter which move Alice picks. We write the total 5 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 , , , , , , , , , | 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 6, 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 RRL. This means that Alice first took the coin on the right, namely, the 3, thus leaving 124; next, Bob took the coin on the right, that is, the 4, leaving 12; 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 2n coins, playing the game will result in a sequence of 2n-1 R’s and L’s. Since each move is completely independent of the other moves, there are a total of 2^{2n-1} such move choice sequences.

We can easily list all the possible 2^{2n-1} 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 2^{2n} 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 , , , , , , , , , | 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 212333:

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 2 + 2 + 3 = 1 + 3 + 3 = 7. 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 212553.

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

  • 2 + 2 + 5 = 1 + 5 + 3 = 9, 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 2n takes time proportional to n^2. By contrast, note that Thibault’s strategy takes time linear in n. I conjecture that the optimal strategy actually cannot be computed in sub-quadratic time. (I would really love to be proven wrong, though, because I think one could use a linear-time 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 , , , , , , | Leave a comment