Two expert and jaded tictactoe players, after drawing for the
nth time, decided to add some randomness to their favorite game.
First, they used a coin to decide who would start. Then, that player would pick his initial move randomly. Next, the other player would also pick his answer randomly. Finally, from then on the game went on as usual, with each player playing in the best possible way.
For each player, what are the odds of winning, losing, or drawing?
(In reply to
Solution by Penny)
There must be a bug in the program. A clue to its incorrectness can be seen in its odd number of wins for player 1, out of 72 games, even though each situation of two first moves occurs with a fourfold symmetry, possibly doubled again by reflection.
The following program uses the notation for the tic tac toe positions:
1 2 3
4 5 6
7 8 9
There are 12 unique starts, as for example 1,2 is the symmetric opposite of 1,4, and rotated this is 3,2; 3,6; 9,6; 9,8; 7,8; 7,4. I've left out the commas and called this 12. Another 8fold possibility is 13 (corner and adjacent corner), then 15 (corner and centerthis is only a 4fold possibility), etc.
DECLARE FUNCTION isWin% (r%, c%, p%)
DECLARE FUNCTION chooseMove$ (n%)
DEFINT AZ
DATA 1,1, 1,2, 1,3, 2,1, 2,2, 2,3, 3,1, 3,2, 3,3
FOR i = 1 TO 9: READ mvRow(i), mvCol(i): NEXT
DATA 12,13,15,16,19, 23,25,26,28,29, 52,53
DIM mvInit$(12)
FOR i = 1 TO 12: READ mvInit$(i): NEXT
DIM SHARED board(3, 3)
DIM SHARED hist$(9)
FOR strt = 1 TO 12
PRINT mvInit$(strt); " ";
hist$(1) = LEFT$(mvInit$(strt), 1)
hist$(2) = RIGHT$(mvInit$(strt), 1)
board(mvRow(VAL(hist$(1))), mvCol(VAL(hist$(1)))) = 1
board(mvRow(VAL(hist$(2))), mvCol(VAL(hist$(2)))) = 2
rslt$ = chooseMove$(3)
IF rslt$ = "win" THEN
rslt$ = "lose"
ELSEIF rslt$ = "lose" THEN
rslt$ = "win"
END IF
PRINT rslt$
board(mvRow(VAL(hist$(1))), mvCol(VAL(hist$(1)))) = 0
board(mvRow(VAL(hist$(2))), mvCol(VAL(hist$(2)))) = 0
NEXT
FUNCTION chooseMove$ (n)
player = (n + 1) MOD 2 + 1
best$ = ""
FOR row = 1 TO 3
FOR col = 1 TO 3
IF board(row, col) = 0 THEN
IF isWin(row, col, player) THEN
chooseMove$ = "lose": ' report loss for caller (other player)
EXIT FUNCTION
END IF
board(row, col) = player
IF n < 9 THEN
rslt$ = chooseMove$(n + 1)
ELSE
rslt$ = "tie"
END IF
board(row, col) = 0
IF rslt$ = "win" THEN
chooseMove$ = "lose": ' report loss for caller (other player)
EXIT FUNCTION
END IF
IF rslt$ = "tie" THEN
best$ = "tie"
END IF
END IF
NEXT
NEXT
IF best$ = "tie" THEN
chooseMove$ = "tie"
ELSE
chooseMove$ = "win"
END IF
END FUNCTION
FUNCTION isWin (r, c, p)
bSv = board(r, c)
board(r, c) = p
w = 0
IF r = 2 AND c = 2 THEN
IF board(1, 1) = p AND board(3, 3) = p THEN w = 1
IF board(1, 2) = p AND board(3, 2) = p THEN w = 1
IF board(1, 3) = p AND board(3, 1) = p THEN w = 1
IF board(2, 1) = p AND board(2, 3) = p THEN w = 1
ELSEIF r = 2 OR c = 2 THEN
IF board(r, 1) = p AND board(r, 2) = p AND board(r, 3) = p THEN w = 1
IF board(1, c) = p AND board(2, c) = p AND board(3, c) = p THEN w = 1
ELSE
IF board(r, 1) = p AND board(r, 2) = p AND board(r, 3) = p THEN w = 1
IF board(1, c) = p AND board(2, c) = p AND board(3, c) = p THEN w = 1
IF board(2, 2) = p AND board(4  r, 4  c) = p THEN w = 1
END IF
board(r, c) = bSv
isWin = w
END FUNCTION
The results are:
12 win
13 win
15 tie
16 win
19 win
23 tie
25 tie
26 win
28 tie
29 win
52 win
53 tie
noted for the first player (x).
Annotated with their respective total occurrences out of 72 this becomes:
12 win 8
13 win 8
15 tie 4
16 win 8
19 win 4
23 tie 8
25 tie 4
26 win 8
28 tie 4
29 win 8
52 win 4
53 tie 4
This comes out to 48 wins out of 72 or 2/3.

Posted by Charlie
on 20041005 09:52:21 