Alice Through the Looking-Glass - Playing Chess

Let $P(x)$ denote the probability that the match lasts $x$ rounds.

$P(2)=P($ Alice wins 2 games in a row $)+P($ Red Queen wins 2 games in a row $)=(\frac{2}{3})^{2}+(\frac{1}{3})^{2}=\frac{5}{9}$ .

$P(4)=(1-P(2))P(2)$ as the game does not end in the first two rounds but does in the following two rounds. $P(4)=(\frac{4}{9})(\frac{5}{9})=\frac{20}{81}$ .

$P(6)=1-P(2)-P(4)=1-\frac{5}{9}-\frac{20}{81}=\frac{16}{81}$ .

Therefore, $E(X)=2(\frac{5}{9})+4(\frac{20}{81})+6(\frac{16}{81})=\frac{266}{81}$ , giving the answer of $\boxed{347}$ .

The following code gives the expected number of rounds to be $E(x) = \frac{266}{81}$ , and $266 + 81 = \boxed{347}$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

# Playing Chess
# Python 2.7.3

import string
digs = string.digits + string.ascii_letters
from fractions import Fraction

# Converts decimal to a different base
def int2base(x, base):
    if x < 0:
        sign = -1
    elif x == 0:
        return digs[0]
    else:
        sign = 1
    x *= sign
    digits = []
    while x:
        digits.append(digs[int(x % base)])
        x = int(x / base)
    if sign < 0:
        digits.append('-')
    digits.reverse()
    return ''.join(digits)

expnumcount = 0
# Go through each possibility of rounds, where 0 represents
#  the queen winning and 1 represents Alice winning
for a in range(0, 2 ** 6):
    seq = int2base(a, 2).zfill(6)
    winner = ""
    acount = 0
    qcount = 0
    rcount = 0
    # Analyze the round
    for b in range(0, len(seq)):
        if seq[b] == "0":
            qcount += 1
        else:
            acount += 1
        # If someone gets 2 points more than the other declare
        #  her the winner and record the round count with rcount
        if winner == "" and qcount >= acount + 2:
            winner = "Q"
            rcount = b + 1
        elif winner == "" and acount >= qcount + 2:
            winner = "A"
            rcount = b + 1
    # If someone is still not declared by the last round compare
    #  counts and declare a winner
    if winner == "" and qcount > acount:
        winner = "Q"
        rcount = 6
    elif winner == "" and acount > qcount:
        winner = "A"
        rcount = 6
    elif winner == "":  # It's a draw
        winner = "D"
        rcount = 6
    # Print a report of the findings for each possibility
    print seq, winner, rcount, qcount, acount
    # Give a 1 weight for each queen win (1/3 possibility) and
    #  a 2 weight for each Alice win (2/3 possibility) and
    #  add them all up
    expnum = (1 ** qcount * 2 ** acount) * rcount
    expnumcount += expnum
# Print a report of the expected number of rounds
print "Expected number of rounds E(x) =", Fraction(expnumcount, 3 ** 6)