In a game of tic-tac-toe, 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 A-Z

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 2013-12-24 20:41:09