The quarter-circle game

Start at a lattice point inside the quarter-circle x^2 + y^2 < 10^6 in the positive quadrant. You and your opponent take turns: the allowable moves are to go up, right, or both at once (i.e. add (0,1), add (1,0), or add (1,1).) First person to leave the quarter-circle wins. What does it look like if you color a starting point black for “first-player loss” and yellow for “first-player win”? It looks like this:

I like the weird zones of apparent order here. Of course you can do this for any planar domain, any finite set of moves, etc. Are games like this analyzable at all?

I guess you could go a little further and compute the nimber or Grundy value associated to each starting position. You get:

What to make of this?

Here’s some hacky code, it’s simple.

M = 1000
def Crossed(a,b):
    return (a**2 + b**2 >= M*M)

def Mex(L):
    return min([i for i in range(5) if not (i in L)])

L = np.zeros((M+2,M+2))
for a in reversed(range(M+2)):
    for b in reversed(range(M+2)):
        if Crossed(a,b):
            L[a,b] = 0
            L[a,b] = Mex([L[a+1,b],L[a,b+1],L[a+1,b+1]])


One natural question: what proportion of positions inside the quarter-circle are first-player wins? Heuristically: if you imagine the value of positions as Bernoulli variables with parameter p, the value at my current position is 0 if and only if all three of the moves available to me have value 1. So you might expect (1-p) = p^3. This has a root at about 0.68. It does look to me like the proportion of winning positions is converging, but it seems to be converging to something closer to 0.71. Why?

By the way, the game is still interesting (but I’ll bet more directly analyzable) even if the only moves are “go up one” and “go right one”! Here’s the plot of winning and losing values in that case:

Tagged ,

12 thoughts on “The quarter-circle game

  1. jb says:

    How does it change if you change the radius? Does anything stabilize as the radius goes to infinity?

  2. JSE says:

    It looks broadly similar, like a lo-res version of what you’re seeing there.

  3. Alison Miller says:

    If I perturb the radius just a tiny bit, how does the pattern change?

  4. jb says:

    Similar enough that there’s a theorem saying converges to something?

  5. JSE says:

    Exactly what I’m wondering is how to express the convergence. You could certainly ask that there’s a continuously family of distributions on nimbers attached to each point in the unit quarter-circle U, and that as n gets big, the mean distribution over the lattice points in nU converges to the mean of the distributions on U. That wouldn’t capture the patterned fluctuations.

  6. Jayadev Athreya says:

    This seems (possibly) relevant:

  7. JSE says:

    Laurent Lessard points out that you can get cross-hatching like what you see in the pictures by taking the boundary to be a line, with different sizes of fluctuation depending on the line’s slope. So you can sort of think of what happens at the circular boundary as a bunch of competing periodic cross-hatch pattern and for some reason some of them “win” in some regions.

  8. Will Sawin says:

    These games are both equivalent to simple cellular automata. The second one is in the class of cellular automata studied by Wolfram, and is equivalent to a bunch of his numbered rules: rule 3, rule 5, rule 17, rule 95, plus two more. So there might be some information on this in that section of the literature.

  9. JSE says:

    Yes, I noticed that too, re the second game! And it looks from the pictures like those rules just induce diagonal stripes which i imagine could be proved easily. Is the original game reducible to a 1-d cellular automaton too, or no?

  10. Will Sawin says:

    I guess the reason for the diagonal stripes in the simplified game is that if (x,y) is a losing position, then (x-1,y) and (x,y-1) are both winning as you can move to (x,y), so (x-1,y-1) is also a losing position. Actually this seems to imply more regularity than is shown on the plot – did I make a mistake? Is this an artifact of the plotting method?

    The original game is a 1-d cellular automaton but there doesn’t seem to be a way to express the cell’s new value in terms of the state of the cell and adjacent cells on the previous time step, instead of the state of the cell and adjacent cells on the previous two time steps. Alternately there is a way of expressing it using the previous time step, but with different rules for different cells (in a checkerboard pattern.) Presumably one can prove that various periodic patterns seen on the graph propagate themselves but I don’t know if there is a big theorem one should look for.

  11. […] Jordan Ellenberg’s “The Quarter Circle Game” blog post […]

Leave a Reply

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

You are commenting using your 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 )

Connecting to %s

%d bloggers like this: