==> 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;
}