In a game of
tictactoe, X
went first followed by O. The situation after two moves was as follows:
 
++
O  X 
++
 
Given that both X and O act at random, what is the probability that X wins the game?
DECLARE SUB move (mno#)
DECLARE SUB moveww (mno#)
DECLARE FUNCTION fact# (x#)
DEFDBL AZ
CLEAR , , 25000
DIM SHARED grid(3, 3), wins(2)
grid(2, 2) = 1: grid(2, 1) = 2
CLS
move 3
FOR i = 0 TO 2
PRINT wins(i);
PRINT wins(i) / (wins(1) + wins(2) + wins(0))
NEXT
PRINT
wins(0) = 0
wins(1) = 0
wins(2) = 0
moveww 3
FOR i = 0 TO 2
PRINT wins(i);
PRINT wins(i) / (wins(1) + wins(2) + wins(0))
NEXT
FUNCTION fact (x)
f = 1
FOR i = 2 TO x
f = f * i
NEXT
fact = f
END FUNCTION
SUB move (mno)
player = (mno  1) MOD 2 + 1
FOR psn = 1 TO 9
row = (psn  1) \ 3 + 1
col = (psn  1) MOD 3 + 1
IF grid(row, col) = 0 THEN
grid(row, col) = player
vhit = 1
FOR r = 1 TO 3
IF grid(r, col) <> player THEN vhit = 0: EXIT FOR
NEXT
hhit = 1
FOR c = 1 TO 3
IF grid(row, c) <> player THEN hhit = 0: EXIT FOR
NEXT
d1hit = 1
FOR r = 1 TO 3
IF grid(r, r) <> player THEN d1hit = 0: EXIT FOR
NEXT
d2hit = 1
FOR r = 1 TO 3
IF grid(4  r, r) <> player THEN d2hit = 0: EXIT FOR
NEXT
IF vhit OR hhit OR d1hit OR d2hit THEN
wins(player) = wins(player) + 1
ELSE
IF mno < 9 THEN
move mno + 1
ELSE
wins(0) = wins(0) + 1
END IF
END IF
grid(row, col) = 0
END IF
NEXT
END SUB
SUB moveww (mno)
player = (mno  1) MOD 2 + 1
FOR psn = 1 TO 9
row = (psn  1) \ 3 + 1
col = (psn  1) MOD 3 + 1
IF grid(row, col) = 0 THEN
grid(row, col) = player
vhit = 1
FOR r = 1 TO 3
IF grid(r, col) <> player THEN vhit = 0: EXIT FOR
NEXT
hhit = 1
FOR c = 1 TO 3
IF grid(row, c) <> player THEN hhit = 0: EXIT FOR
NEXT
d1hit = 1
FOR r = 1 TO 3
IF grid(r, r) <> player THEN d1hit = 0: EXIT FOR
NEXT
d2hit = 1
FOR r = 1 TO 3
IF grid(4  r, r) <> player THEN d2hit = 0: EXIT FOR
NEXT
IF vhit OR hhit OR d1hit OR d2hit THEN
wins(player) = wins(player) + fact(9  mno)
ELSE
IF mno < 9 THEN
moveww mno + 1
ELSE
wins(0) = wins(0) + 1
END IF
END IF
grid(row, col) = 0
END IF
NEXT
END SUB
reports:
576 .1761467889908257 
2082 .636697247706422 } naive results
612 .1871559633027523 
576 .1142857142857143 draw
3672 .7285714285714285 X wins
792 .1571428571428571 Y wins
The first grouping shows the results of the naive approach, corrected in the second. In each case the order of the lines refers to ties, X wins and finally O wins.
The first grouping takes a particular quick winning sequence as being equally likely as a long winning sequence. Say the spaces are numbered as follows:
123
456
789
The first treats the win for x 54268 as being only as likely as the win for x 542836917, but actually 54268 is just as likely as any one string of nine that begins 54283... .
So the second set, instead of reporting the raw count of ways of winning, shows those ways weighted by the number of permutations of the remaining spots. Next to each weighted number of ways appears the probability of draw, win by X and win by Y, obtained by dividing by the total of the weighted ways.
The numbers show an approximately 11.4% probability of a draw, 72.9% of a win by X and 15.7% by Y.

Posted by Charlie
on 20131224 20:41:09 