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

Home > Probability
Tic-Tac-Toe Toss Tactics? (Posted on 2004-10-04) Difficulty: 3 of 5
Two expert and jaded tic-tac-toe players, after drawing for the n-th 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?

See The Solution Submitted by Old Original Oskar!    
Rating: 3.6667 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution re: Solution | Comment 4 of 10 |
(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 8-fold possibility is 13 (corner and adjacent corner), then 15 (corner and center--this is only a 4-fold possibility), etc.

DECLARE FUNCTION isWin% (r%, c%, p%)
DECLARE FUNCTION chooseMove$ (n%)
DEFINT A-Z
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 2004-10-05 09:52:21
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information