Greedy coins game update

Posted on April 22, 2017 by Brent

I plan to write a longer post soon, but for the moment I just wanted to provide a quick update about the greedy coins game (previous posts here and here). It turns out that the game is a lot more interesting—and has generated a lot more discussion—than I thought when I first posted it!

In my previous post I conjectured that the only tied games are the ones that can be built up by surrounding a tied game with a coin ( $cGc$ ) or concatenating two tied games ( $G_1 G_2$ ). That conjecture was quickly shot down, with commenters tinyboss and Thibault Vroonhove independently pointing out counterexamples: $1243$ or $1342$ are both tied, even though they can’t be built up in the conjectured way. As you can check, with best play in these games, one player will get $1 + 4$ and the other will get $2 + 3$ .
Thibault noted that these particular tied games can be made by starting with a symmetric game (like $1331$ ) and then adding the same number to all the coins in one half (e.g. adding $1$ to each coin in the second half of $1331$ yields $1342$ ). However, although I think this always yields a tied game for games of length 4, it turns out that this does not always result in a tied game in general: for example, $123432$ isn’t tied, since the coins add up to an odd total.
Thibault then came up with a counterexample to my other conjecture, namely, that $G_1 G_2$ is tied if $G_1$ and $G_2$ both are: $51151221$ is not tied, even though it is the concatenation of two tied games. In fact, even $21121221$ is not tied: Alice can guarantee that she will get at least three of the $2$ s.
Given all this it’s kind of amazing that the big game I constructed as a quick test of my conjectures, namely $01233244156650$ , is indeed tied. Eric Burgess reported that in fact every cyclic permutation of this game is tied!
Eric also introduced the function $S$ , where $S(c_i \dots c_j)$ denotes the winning margin, with best play, of whoever’s turn it is. That is, starting from position $c_i \dots c_j$ , with best play, what is the difference between the current player’s score and the other player’s? (Note that in the case of Bob the “winning margin” can be negative, if Bob is going to lose even with best play.) If the current player takes coin $c_i$ , then $S(c_{i+1} \dots c_j)$ denotes the winning margin of the other player from that point on, which is the same as the losing margin of the current player. But they also got $c_i$ ; so overall their winning margin will be $c_i - S(c_{i+1} \dots c_j)$ . Of course, best play means that the current player will choose whichever coin gives them the higher winning margin. This motivates the following inductive definition of $S$ , where we use $x \vee y$ to denote the maximum of $x$ and $y$ :
- $S() = 0$
- $S(c) = c$
- $S(c_i \dots c_j) = (c_i - S(c_{i+1} \dots c_j)) \vee (c_j - S(c_i \dots c_{j-1}))$
Thibault conjectured that the following strategy for Alice is optimal (I’ve rephrased it in a way that I’m pretty sure is equivalent, and which I think makes it more clear):
- 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.
If this strategy is indeed optimal, that would be really cool, since it is pretty easy to apply in practice. But I am not ready to say whether I believe this conjecture or not. In any case it should be possible to test this strategy with a computer program to play lots of random games, which I hope to do soon (and to write another post about it).

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

This entry was posted in games, proof and tagged coins, conjecture, game, proof, strategy, two-player, zero-sum. Bookmark the permalink.

18 Responses to Greedy coins game update

Thibault Vroonhove says:

April 24, 2017 at 8:30 am

I should slightly modify my conjecture : if neither of these rules apply, then take the coin so that your loss is minimized at this turn. For example, in the game $5,6,2,0,2,3$ , Alice should take the 5 because $5-(6\vee 3) = -1 > -2 = 3-(5\vee 2)$ .
- Thibault Vroonhove says:
  
  April 24, 2017 at 8:36 am
  
  Wait, not at all actually. Alice can also force a win by taking the 3. I don’t think it doesn’t matter in every case, but here it doesn’t.
  - Brent says:
    
    April 27, 2017 at 9:48 pm
    
    A game where it matters is $2,1,2,3,3,3$ . The only winning move is to take the 3.
  - Brent says:
    
    April 27, 2017 at 9:55 pm
    
    I wrote a program to search for counterexamples to your strategy, and the smallest one I found is $2,1,2,4,4,3$ . None of the rules of your strategy apply, including the fact that the local loss from taking either the 2 or the 3 is equal. However, the only winning move is to take the 3 on the right.
    - Brent says:
      
      April 27, 2017 at 10:43 pm
      
      $2, 1, 2, 5, 5, 3$ is perhaps a better counterexample: the winning move is still to take the 3 on the right, even though the local loss (-2) is actually more than the local loss from taking the 2 (-1).
Eric Burgess says:

April 25, 2017 at 10:03 pm

I’ve been thinking about classifying games according to the sequence of coins taken under optimal play. For example, the optimal sequence for the length-2 game $c_1c_2$ is $(1,2)$ if $c_1>c_2$ , and $(2,1)$ if $c_2>c_1$ . If $c_1=c_2$ then both sequences are optimal and neither is preferred.

(My previous posts generalized to games with odd numbers of coins, but here I only consider games with an even number.)

Call a game interior if it has a unique optimal play sequence, and boundary if it has more than one.

Conjecture: Tied games are properly contained in boundary games.

Easy half of the proof: the game $1112$ is boundary but not tied. The other half is to prove that every tied game has more than one optimal play sequence. The terminology gives an idea of my line of reasoning, but I want to nail it all the way down before I post it. I also suspect there may be a short and sweet proof ala the Alice-can’t-lose theorem.
- Eric Burgess says:
  
  April 26, 2017 at 9:13 am
  
  Let $\mathbb{G}^{2k}$ be the set of all games with $2k$ coins. Define $\mathrm{seq}(2k)$ to be the set of legal play sequences for a game $G\in\mathbb{G}^{2k}$ . Let $R(G,s)$ denote the resulting total for the first player (Alice) if the game $G$ is played with sequence $s$ .
  
  (Breaking here to make sure the LaTeX I’m using is supported…)
- Eric Burgess says:
  
  April 26, 2017 at 4:48 pm
  
  Brent, your comment at the end of this entry really got me thinking about generating random games. Even if we confine ourselves to integer-valued coins, it’s a tricky task. How high (or low) do we go? Do we miss out on anything interesting by using integers, or by bounding the values of our coins? Can we do a uniform sample in any reasonable sense?
  
  It’s obvious that $(1,2,3,4)$ and $(10,20,30,40)$ are the “same” game, equally obvious that $(1,1)$ and $(1,1.001)$ are not, and almost as obvious that $(1,2,2,4)$ and $(1,2,2,4.001)$ are again the same. How can we make this precise? My current definition of “same” is that two games are equivalent if you play them the same way.
  
  (Along the way I came up with the conjecture above, and I’ve reduced the handwaving to an amount I’m comfortable with, so here’s my almost-proof.)
  
  Identify games (sequences of coins) with vectors in $\mathbb{R}^{2k}$ in the obvious way. At each turn, the player can choose the leftmost or rightmost coin, so for a $2k$ -coin game, a play sequence (I’ll just say “sequence”) is a string of L’s and R’s of length $2k-1$ (because the last move is forced). A sequence is optimal if it can arise from the definition of $S(G)$ given previously, equivalently, if it results in the maximum score for Alice. For example, $1234$ has the unique optimal sequence RRR, giving Alice a 6-4 win, and $2111$ has four optimal sequences (all the ones beginning with L) with Alice winning 3-2.
  
  Definition: Two games are equivalent if they have the same set of optimal sequences.
  
  Lemma 1: Every game with a unique optimal sequence has a neighborhood of equivalent games.
  
  Proof: Suppose $G$ has a single optimal sequence. That means that at each turn there is a unique optimal choice of coin to take, so (referring back to the definition of $S(G)$ ) we have $c_i-S(c_{i+1}\cdots c_j) \neq c_j-S(c_i\cdots c_{j-1})$ . Since there are finitely many turns, there is a minimum amount by which any choice is decided. (Begin handwaving…) I’m confident that there’s an inductive (or otherwise) argument to show that changing one of the $c_i$ by $\delta$ changes the value of $S(G)$ by at most $\pm 2 \delta$ . (End handwaving.) So we can find an $\varepsilon$ -ball around $G$ where the same sequence of choices is forced.
  
  Lemma 2: Every neighborhood of a tied game contains a game not equivalent to it.
  
  Proof: Suppose $G$ is tied, choose an optimal sequence $s$ for $G$ , and let $c_i$ be a coin that Alice chooses under $s$ . If we reduce the value of $c_i$ by any amount, no matter how small, then $s$ is no longer optimal, because Alice loses.
  
  From the two lemmas it follows that if a game is tied, then it has more than one optimal sequence.
  
  One thing I need to nail down is whether a tied game can be equivalent to a non-tied game. I certainly hope not, otherwise it’s not a very good notion of “sameness”!
  
  I’ll post again with more about the structure of the space of games and how we might do random sampling.
- Eric Burgess says:
  
  April 26, 2017 at 6:05 pm
  
  We can’t uniformly sample $\mathbb{R}^{2k}$ . But if we consider equivalence classes of games, the situation is much better. Write $G\sim G'$ if $G$ and $G'$ have the same set of optimal sequences.
  
  Since we’ve identified $\mathbb{G}^{2k}$ with the vector space $\mathbb{R}^{2k}$ , we can add games to one another and multiply them by real numbers. If $\lambda$ is a positive real number and $\delta$ is any real number, then it’s not hard to see that:
  
  (1) $G \sim \lambda G$ , and
  (2) $G \sim G + \delta(1, 1, \dots, 1)$ .
  
  (Because $S(\lambda G)=\lambda S(G)$ and $S(G+\delta(1, 1, \dots, 1))=S(G)$ , the optimal choices are all the same.)
  
  This means that the set of games equivalent to $G$ contains at least $\{\lambda G + \delta(1,1,\dots,1)\mid \lambda\in\mathbb{R}_+, \delta\in\mathbb{R}\}$ . If $G\notin \langle 1,1,\dots,1 \rangle$ then this is a two-dimensional open half-subspace of $\mathbb{R}^{2k}$ . In other words, the equivalence classes of games are unions of open half 2-planes whose boundary is $\langle 1,1,\dots,1 \rangle$ . An exceptional class is the line spanned by $(1,1,\dots,1)$ (which I’ll call the zero equivalence class, since these games are all equivalent to $(0,0,\dots,0)$ ).
  
  Each non-zero class is a union of half-planes, each of which contains a unique unit-length vector orthogonal to $(1,1,\dots,1)$ , which we’ll choose as the representative of that plane (remember many planes will belong to the same game equivalence class). All the non-zero class representatives together form a sphere of dimension $2k-2$ , which is divided up into game equivalence classes in some way, and which we can sample uniformly. I propose that this is a reasonable way of choosing “random” games.
  
  If we let the zero class be represented by $(0,0,\dots,0)$ , which seems like the only reasonable choice, then it’s an isolated point and would be excluded from this way of sampling. I don’t know if this is saying anything interesting or not.
  
  Because we go up by two dimensions every time we increase the game size, we unfortunately skip straight from trivial to mind-bending, but let’s at least look at the trivial case, games of length 2. We had better come up with three classes, corresponding to the left coin being smaller than, larger than, or equal to the right coin.
  
  We identify $\mathbb{G}^2$ with $\mathbb{R}^2$ , so that the game $c_1c_2$ corresponds to the vector $(c_1, c_2)$ . There are exactly two open half 2-planes with boundary $\langle 1,1 \rangle$ : one where $c_1 > c_2$ , represented by $(1,-1)$ , and one where $c_1 < c_2$ , represented by $(-1,1)$ . A zero-dimensional sphere is defined to be two disconnected points. Together with the zero class, that gives us the three classes of length-2 games, so we've passed the trivial case.
  
  If I haven't made any unfixable mistakes, then the non-zero equivalence classes of length-4 games should be mapped out on a 2-dimensional sphere, which could actually be visualized. Since there are 8 possible sequences and we classify games by the (nonempty) subset of these which are optimal, there are at most 255 equivalence classes (although I suspect the actual number is much smaller). I hope to be able to produce the map. If I'm right about all this but can't nail down the map itself, then the open regions, at least, can be mapped pretty easily with a Monte Carlo method.
  - Eric Burgess says:
    
    April 26, 2017 at 6:11 pm
    
    Oops, the sentence near the top that reads,
    
    This means that the set of games equivalent to $G$ contains at least $[G]=\{\lambda G + \delta(1,1,\dots,1)\mid \lambda\in\mathbb{R}_+, \delta\in\mathbb{R}\}$
    
    …should instead be
    
    This means that the set of games equivalent to $G$ contains at least $\{\lambda G + \delta(1,1,\dots,1)\mid \lambda\in\mathbb{R}_+, \delta\in\mathbb{R}\}$ .
    
    I got confused between the half-planes and the equivalence classes, and I thought I fixed all the errors, but I missed (at least) that one.
    
    Oops, one more error…right after that sentence, the not-equal sign should be not-an-element-of.
    
    Also, I forgot to normalize my representatives in the dimension-2 example. Dang.
    - Brent says:
      
      April 29, 2017 at 3:38 pm
      
      I fixed these errors and a few others for you, except I didn’t fix the non-normalized representatives (it’s much nicer not to have the $\sqrt{2}$ ‘s in there anyway, and since $G \sim \lambda G$ it really doesn’t matter!).
  - Brent says:
    
    April 29, 2017 at 3:41 pm
    
    I’ve only just now gotten a chance to read through this carefully, and it’s amazing! Would you consider writing a guest post (or two or three…) about it?
    
    Have you made any progress on computing/visualizing the equivalence class map for $\mathbb{G}^{2k}$ ?
  - Thibault Vroonhove says:
    
    May 4, 2017 at 6:01 pm
    
    The following lemma proves that a tied game can’t be equivalent to a non-tied game.
    Lemma: $G$ is tied iff both $LLL\dots L$ and $RRR\dots R$ are optimal sequences.
    Proof: Suppose $G$ is tied. Since Alice can force the tie by using the red/blue strategy and no matter what Bob does, both $LLL\dots L$ and $RRR\dots R$ have to be optimal sequences.
    Conversely, if both $LLL\dots L$ and $RRR\dots R$ are optimal sequences, then we have that $S(G) = c_1 + c_3 +\dots +c_{2n-1}$ and $S(G) = c_2+c_4+\dots +c_{2n}$ , and it follows that $G$ is tied.
    - Eric Burgess says:
      
      May 4, 2017 at 6:11 pm
      
      Fantastic! Your result also implies my (not-quite-proved) statement that tied games have more than one optimal sequence. Very slick.
    - Thibault Vroonhove says:
      
      May 4, 2017 at 6:18 pm
      
      Nope, I’m wrong again. In $3113$ , neither $LLL$ nor $RRR$ are optimal sequences, sorry…
      But I can rephrase it like this: $G$ is tied iff there are both optimal sequences such that Alice gets all the red coins and ones such that Alice gets all the blue coins. So the consequence still holds.
      - Thibault Vroonhove says:
        
        May 4, 2017 at 6:19 pm
        
        [And I forgot the “latex” so the $G$ should be $G$ ]
      - Eric Burgess says:
        
        May 4, 2017 at 6:23 pm
        
        Good catch and save.
Pingback: Another greedy coins game update | The Math Less Traveled