Child's game Probability Question

Factual Questions
21

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.

22

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

23

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)