Counting them all in C

Everyone knows the game of tic-tac-toe. The number of different legal games is probably higher than what one would guess at first. That number is 255,168. A proof can be found here.

The purpose of this page is to find that number by computer experimentation.

The following C code scans all possible games. Its innermost loop consists of just adding 1 to a counter.

• The code

 
 #include 
 #define Tic i++;for(move[i]=0;move[i]<=8;move[i]++){draw=0;for(j=0;j<(i);j++){if(move[i]==move[j]){draw=1;}}if(!(draw||win(i+1,move))){
 #define Toe }}i--;
 #define m8(a) a a a a a a a a
 
 int win(int nbMoves,int move[]);
 int move[]={0,0,0,0,0,0,0,0,0},nbWin[]={0,0,0,0,0,0,0,0,0},w1[]={0,3,6,0,1,2,0,2},
 w2[]={1,4,7,3,4,5,4,4},w3[]={2,5,8,6,7,8,8,6},i=0,j,nbDraw=0,draw;
 
 int main(void){int j,draw,nbDraw=0;
 
 for(move[i]=0;move[i]<=8;move[i]++){m8(Tic)nbDraw++;m8(Toe)}
 
 printf("nb draws:%dn",nbDraw);
 for(i=4;i<9;i++) printf("nb wins in %d moves:%dn",i+1,nbWin[i]);
 printf("Total:%dn",nbDraw+nbWin[4]+nbWin[5]+nbWin[6]+nbWin[7]+nbWin[8]);
 return 0;
 }
 
 int win(int nbMoves,int move[])
 {
 int k,winner=0;char board[9],symbol;
 for(k=0;k<9;k++)board[k]=' ';symbol='X';for(k=0;k{board[move[k]]=symbol;if(symbol=='X')symbol='O';else symbol='X';}
 k=0;m8(winner=winner||((board[w1[k]]==board[w2[k]])&&(board[w2[k]]==board[w3[k]])&&(board[w1[k]]!=' '));k++;)
 if(winner==1)nbWin[nbMoves-1]++;
 return winner;
 }
 
 

Note: Here, the program is coded in a compact tway. If you need to understand the code, I suggest you expand the #define

A fraction of a second is enought to run the program and find the above number.

• Statistics:

By adding extra counters in the innermost loop, one can compute some statistics about the game.
All games have a duration of at least 5 moves. I think it’s pretty obvious to you.
The maximum duration of a game is 9 moves. The distribution is as follows.ion of zz,zz moves.
The 1st player wins zz,z % of the time
The 2nd player wins zz,z % of the time
A draw happens zz,z % of the time

• Graphical representation:

In addition, I wrote a small project in C++ Builder to generate a picture containing all tic-tac-toe games. The first game is at the top left of the picture and the last is at the bottom right. Each pixel represents a cell of the 3x3 tic-tac-toe board. Each player has a different color. …..expliquer couleurs gagnant

>>> picture
>>> how to interpret (zoom sur une région)

The C++ Builder project generating the picture can be downloaded here.

• Symmetries: Reflexions and Rotations

This count ignores rotations and reflexions of the board. If we authorize symmetries to reduce the total count, then the number reduces dramatically to yyy. That number is probably nearer to what one would think when asked how many legal games exist. See for the theory.

I did not implement a count that does that calculation. If I were to do it, I’d define a ’standard form’ for a game. That form would be the same for all games that are ‘the same’ under rotations and reflexions. The game counter would then increment only for different standard forms.

Top