Whoo! Your machine is a damn sight faster than mine! Good work!
This is why infinite sequences are (mathematically) possible, and why an explicit analysis would be a pain. This is (in the abstract) an infinite game, not a finite one.
Whoo! Your machine is a damn sight faster than mine! Good work!
This is why infinite sequences are (mathematically) possible, and why an explicit analysis would be a pain. This is (in the abstract) an infinite game, not a finite one.
I wrote some code to the analysis exactly by boiling the game down to 345 (or 414) distinct states. Each state has a small number of parent states and the transition probabilities between states are pretty easy to compute. You can also normalize state exit probabilities to handle the infinite loop problem. Then just sum the probabilities of the 5 (or 6) winning states.
The unsurprising answer is:
0.6313573066006350 for 5 crow moves
0.7684969326194143 for 6 crow moves
Here’s the code (Python). It’s pretty cludgy, but it runs pretty much instantly. I’m sure it could be tightened up quite a bit.
def find_parents(a,b,c,d,x):
if a==d:
if a<4:
parents = [[a+1,b,c,d,x]]
else:
parents = []
elif a==c:
if a<4:
parents = [[a+1,b,c,d,x],[a,b,c,d+1,x]]
else:
parents = [[a,b,c,d+1,x]]
elif a==b and c==d:
if a<4:
parents = [[a+1,b,c,d,x],[a,b,c+1,d,x]]
else:
parents = [[a,b,c+1,d,x]]
elif a==b and c!=d:
if a<4:
parents = [[a+1,b,c,d,x],[a,b,c+1,d,x],[a,b,c,d+1,x]]
else:
parents = [[a,b,c+1,d,x],[a,b,c,d+1,x]]
elif b==d:
if a<4:
parents = [[a+1,b,c,d,x],[a,b+1,c,d,x]]
else:
parents = [[a,b+1,c,d,x]]
elif b==c:
if a<4:
parents = [[a+1,b,c,d,x],[a,b+1,c,d,x],[a,b,c,d+1,x]]
else:
parents = [[a,b+1,c,d,x],[a,b,c,d+1,x]]
elif c==d:
if a<4:
parents = [[a+1,b,c,d,x],[a,b+1,c,d,x],[a,b,c+1,d,x]]
else:
parents = [[a,b+1,c,d,x],[a,b,c+1,d,x]]
else:
if a<4:
parents = [[a+1,b,c,d,x],[a,b+1,c,d,x],[a,b,c+1,d,x],[a,b,c,d+1,x]]
else:
parents = [[a,b+1,c,d,x],[a,b,c+1,d,x],[a,b,c,d+1,x]]
if x > 0 and a>0:
parents += [[a,b,c,d,x-1]]
return parents
def find_prob_from_parent(child, parent):
a,b,c,d,x = child
q,r,s,t,y = parent
denom = 6 - int(q==0) - int(r==0) - int(s==0) - int(t==0)
if q > a:
numer = parent[:-1].count(q) + 1
elif r > b:
numer = parent[:-1].count(r) + int(r==q)
elif s > c:
numer = parent[:-1].count(s) + int(s==q)
elif t > d:
numer = parent[:-1].count(t) + int(t==q)
else:
numer = 1
return numer/denom
probstatemat = [[[[[-1 for x in range(8)] for d in range(5)] for c in range(5)] for b in range(5)] for a in range(5)]
probstatemat[4][4][4][4][0] = 1.0
def probstate(a,b,c,d,x):
if probstatemat[a]**[c][d][x] == -1:
ps = find_parents(a,b,c,d,x)
probstatemat[a]**[c][d][x] = sum([find_prob_from_parent([a,b,c,d,x], p)*probstate(p[0],p[1],p[2],p[3],p[4]) for p in ps])
return probstatemat[a]**[c][d][x]
total = 0.0
for i in range(5):
total += probstate(0,0,0,0,i)
print(total)
total = 0.0
for i in range(6):
total += probstate(0,0,0,0,i)
print(total)