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?

(In reply to computer aided solution by Charlie)

The following simulation verifies the probabilities found previously:

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

FOR trial = 1 TO 100000
 move 3
NEXT

FOR i = 0 TO 2
  PRINT wins(i);
  PRINT wins(i) / (wins(1) + wins(2) + wins(0))
NEXT

SUB move (mno)
  player = (mno - 1) MOD 2 + 1
  psn = INT(9 * RND(1) + 1)
  row = (psn - 1) \ 3 + 1
  col = (psn - 1) MOD 3 + 1
  WHILE grid(row, col) > 0
    psn = INT(9 * RND(1) + 1)
    row = (psn - 1) \ 3 + 1
    col = (psn - 1) MOD 3 + 1
  WEND
  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 SUB

The results:

 11447  .11447   draw 
 72884  .72884   win for X
 15669  .15669   win for Y

Posted by Charlie on 2013-12-24 21:45:24