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[9];
int N, move, won, lost, tied;
int perm[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
int rows[8][3] = {
{ 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[0], board[1], board[2],
board[3], board[4], board[5], won, lost, tied,
board[6], board[7], board[8]);
#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[0]; row<rows[8]; row+=3 ) {
s = board[row[0]] + board[row[1]] + board[row[2]];
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:
My Books
