All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Tic Tac Toe II (Posted on 2013-12-24)
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?

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer aided solution | Comment 1 of 2

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

 Search: Search body:
Forums (5)