Tag Archives: game theory

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
        else:
            L[a,b] = Mex([L[a+1,b],L[a,b+1],L[a+1,b+1]])

plt.imshow(L,interpolation='none',origin='lower')
plt.show()

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 ,

Cosma Shalizi 1, game theory 0

From Cosma’s review of a new book on social network analysis:

What game theorists somewhat disturbingly call rationality is assumed throughout—in other words, game players are assumed to be hedonistic yet infinitely calculating sociopaths endowed with supernatural computing abilities.

 

Tagged , , ,
%d bloggers like this: