 # 140 competition/games/tictactoe.p

## Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

# 140 competition/games/tictactoe.p

In random tic-tac-toe, what is the probability that the first mover wins?

competition/games/tictactoe.s

Count cases.

First assume that the game goes on even after a win. (Later figure
out who won if each player gets a row of three.) Then there are
9!/5!4! possible final boards, of which

8*6!/2!4! - 2*6*4!/0!4! - 3*3*4!/0!4! - 1 = 98

have a row of three Xs. The first term is 8 rows times (6 choose 2)
ways to put down the remaining 2 Xs. The second term is the number
of ways X can have a diagonal row plus a horizontal or vertical row.
The third term is the number of ways X can have a vertical and a
horizontal row, and the 4th term is the number of ways X can have two
diagonal rows. All the two-row configurations must be subtracted to
avoid double-counting.

There are 8*6!/1!5! = 48 ways O can get a row. There is no double-
counting problem since only 4 Os are on the final board.

There are 6*2*3!/2!1! = 36 ways that both players can have a
row. (6 possible rows for X, each leaving 2 possible rows for O
and (3 choose 2) ways to arrange the remaining row.) These
cases need further consideration.

There are 98 - 36 = 62 ways X can have a row but not O.

There are 48 - 36 = 12 ways O can have a row but not X.

There are 126 - 36 - 62 - 12 = 16 ways the game can be a tie.

Now consider the 36 configurations in which each player has a row.
Each such can be achieved in 5!4! = 2880 orders. There are 3*4!4!
= 1728 ways that X's last move completes his row. In these cases O
wins. There are 2*3*3!3! = 216 ways that Xs fourth move completes
his row and Os row is already done in three moves. In these cases O
also wins. Altogether, O wins 1728 + 216 = 1944 out of 2880 times
in each of these 36 configurations. X wins the other 936 out of
2880.

Altogether, the probability of X winning is ( 62 + 36*(936/2880) ) / 126.

```win:   737 / 1260  ( 0.5849206... )
lose:  121 / 420   ( 0.2880952... )
draw:  8 / 63      ( 0.1269841... )
```

The computer output below agress with this analysis.

1000000 games: won 584865, lost 288240, tied 126895

Instead, how about just methodically having the program play every
possible game, tallying up who wins?

Wonderful idea, especially since there are only 9! ~ 1/3 million
possible games. Of course some are identical because they end in
fewer than 8 moves. It is clear that these should be counted
multiple times since they are more probable than games that go
longer.

The result:
362880 games: won 212256, lost 104544, tied 46080

```#include <stdio.h>

int	board;
int	N, move, won, lost, tied;

int	perm = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };

int	rows = {
{ 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 },
{ 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 }
};

main()
{
do {
bzero((char *)board, sizeof board);
for ( move=0; move<9; move++ ) {
board[perm[move]] = (move&1) ? 4 : 1;
if ( move >= 4 && over() )
break;
}
if ( move == 9 )
tied++;
#ifdef DEBUG
printf("%1d%1d%1d\n%1d%1d%1d  w %d, l %d, t %d\n%1d%1d%1d\n\n",
board, board, board,
board, board, board, won, lost, tied,
board, board, board);
#endif
N++;
} while ( nextperm(perm, 9) );

printf("%d games:  won %d, lost %d, tied %d\n", N, won, lost, tied);
exit(0);
}

int	s;
int	*row;

over()
{
for ( row=rows; row<rows; row+=3 ) {
s = board[row] + board[row] + board[row];
if ( s == 3 )
return ++won;
if ( s == 12 )
return ++lost;
}
return 0;
}

nextperm(c, n)
int	c[], n;
{
int	i = n-2, j=n-1, t;

while ( i >= 0 && c[i] >= c[i+1] )
i--;
if ( i < 0 )
return 0;
while ( c[j] <= c[i] )
j--;
t = c[i];  c[i] = c[j];  c[j] = t;
i++;  j = n-1;
while ( i < j ) {
t = c[i];  c[i] = c[j];  c[j] = t;
i++;  j--;
}
return 1;
}
```

Continue to: