lotus

previous page: 139 competition/games/think.and.jump.p
  
page up: Puzzles FAQ
  
next page: 141 competition/tests/analogies/long.p

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:













TOP
previous page: 139 competition/games/think.and.jump.p
  
page up: Puzzles FAQ
  
next page: 141 competition/tests/analogies/long.p