How to go through the maximum amount of Tic Tac Toe possibilities?

Question

I wanted to know how many amounts of Tic Tac Toes possibilities there is, so I searched the web and found an mathematical theorem which says that there is 255168 possible games in Tic Tac Toe.

Website: http://www.se16.info/hgb/tictactoe.htm

So I wonder, I can make an program and see how fast can the computer go through each and every one of those possibilities, then I made this code:

#include <iostream>
#include <time.h>
#include <windows.h>
#include <stdio.h>
using namespace std;

typedef int TTTField[9];

bool checkIfWon(TTTField j){
    if(j[0]==1&&j[1]==1&&j[2]==1) return true;
    if(j[0]==2&&j[1]==2&&j[2]==2) return true;
    if(j[3]==1&&j[4]==1&&j[5]==1) return true;
    if(j[3]==2&&j[4]==2&&j[5]==2) return true;
    if(j[6]==1&&j[7]==1&&j[8]==1) return true;
    if(j[6]==2&&j[7]==2&&j[8]==2) return true;
    if(j[0]==1&&j[3]==1&&j[6]==1) return true;
    if(j[0]==2&&j[3]==2&&j[6]==2) return true;
    if(j[1]==1&&j[4]==1&&j[7]==1) return true;
    if(j[1]==2&&j[4]==2&&j[7]==2) return true;
    if(j[2]==1&&j[5]==1&&j[8]==1) return true;
    if(j[2]==2&&j[5]==2&&j[8]==2) return true;
    if(j[0]==1&&j[4]==1&&j[8]==1) return true;
    if(j[0]==2&&j[4]==2&&j[8]==2) return true;
    if(j[2]==1&&j[4]==1&&j[6]==1) return true;
    if(j[2]==2&&j[4]==2&&j[6]==2) return true;
    return false;
}

bool checkIfItsOver(TTTField j){
    for(int i=0;i<9;i++){
        if(j[i]==0){
            return false;
        }
    }
    return true;
}

bool checkListOfFields(TTTField game, TTTField listOfFields[], int amountAdded){
    int i,j;
    for(j=0;j<amountAdded;j++){
        int temporaryField=0;
        for(i=0;i<9;i++){
            if(game[i]==listOfFields[j][i]) temporaryField++;
        }
        if(temporaryField==9)return true;
    }
    return false;
}

void clearField(TTTField game){
    int i;
    for(i=0;i<9;i++) game[i]=0;
}

void addlistOfFields(TTTField game, TTTField listOfFields[], int amountAdded){
    for(int i=0;i<9;i++) listOfFields[amountAdded][i]=game[i];
}

int main(){
    TTTField listOfFields[50000];
    TTTField temporaryField;
    int amountAdded=0,randA,round=1,roundCounter=0,amountPassed=0,amountOfWins=0,amountOfDraws=0,winWith5=0,winWith6=0,winWith7=0,winWith8=0,winWith9=0,roundAmountFinished=0;
    for(int i=0;roundCounter<100000;i++){
        clearField(temporaryField);
        roundAmountFinished=0;
        do{
            do{
                randA=rand()%9;
            }while(temporaryField[randA]!=0);
            temporaryField[randA]=round;
            if(checkIfWon(temporaryField)){
                break;
            }
            if(checkIfItsOver(temporaryField)){
                break;
            }
            round=round==1?2:1;
            roundAmountFinished++;
        }while(1);
        if(!checkListOfFields(temporaryField,listOfFields,amountAdded)){
            addlistOfFields(temporaryField,listOfFields,amountAdded);
            amountAdded++;
            if(checkIfWon(temporaryField)){
                amountOfWins++;
            }
            if(checkIfItsOver(temporaryField)){
                amountOfDraws++;
            }
            switch(roundAmountFinished){
                case 4:
                    winWith5++;
                    break;
                case 5:
                    winWith6++;
                    break;
                case 6:
                    winWith7++;
                    break;
                case 7:
                    winWith8++;
                    break;
                case 8:
                    winWith9++;
                    break;
            }
        }
        if(amountPassed==amountAdded){
            roundCounter++;
        }else roundCounter=0;
        amountPassed=amountAdded;
    }
    system("cls");
    printf("Total: %d, roundCounter: %d\nWins with 5 rounds:%d\nWins with 6 rounds:%d\nWins with 7 rounds:%d\nWins with 8 rounds:%d\nWins with 9 rounds:%d\namountOfWins: %d, amountOfDraws: %d",amountAdded,roundCounter,winWith5,winWith6,winWith7,winWith8,winWith9,amountOfWins,amountOfDraws);

    return 0;
}

But it returns me an total amount of: 1916, which is different from the one in the website, and I wonder what is wrong with my code.

Some information about the code:

• The field is a array of integer with 9 indexes in which 1 represents crosses and 2 represents circles, also 0 is for null field.
• It generates an random value from 0~9 (if it hasn't been picked before) than it puts an 1 or 2 (depending whom round it is) always checking if someone won or the game has resulted in a draw.
• After finishing the game it will check if that possibility is already on the list, if it is it will do nothing and proceed to another one.
• It will finish when it went through 100k of possibilities without adding a single one to the list.

Where is the problem?

Answer 1

I would probably write this problem recursively. Your method would take a board state, add a piece, check if it finishes (full or win), and if not, call the method again with the new board state. And every time you are full or win, increment some global counter. When the method returns, move your piece to a new spot.

Here's a rough idea of what i'd do:

recurseBoard(vector<vector<square> >& board, int pieceType) {
    for (int i = 0; i < 3; i++) {
       for (int j = 0; j < 3; j++) {
          // If there's a piece there already, skip
          if (board[i][j] != 0) continue;
          // add the piece
          board[i][j] = pieceType;
          // if it's full or win, increment counter
          if (victory(board)) count++;
          else (recurseBoard(board), otherPieceType);
          // Clear the piece you just added
          board[i][j] = 0;
      }
   }
}

Answer 2

If I were you I would start by creating an enum for the square values instead of passing around and comparing numbers:

enum square {X, O, EMPTY};

So then you could keep the boards as 2d vectors:

vector<vector<square> > board (3, vector<square>(3, EMPTY));

Then finding the number of possible games could happen via recursion:

int find_games(vector<vector<square> >& board, square move) {
    if(game_over(board)) return 1;
    int num_moves = 0;
    for(int x = 0; x < board.size(); x++) {
        for(int y = 0; y < board[x].size(); y++) {
            if(board[x][y] != EMPTY) continue;
            board[x][y] = move; //test if player made a move here...
            num_moves += find_games(board, (move == X) ? Y : X);
            board[x][y] = EMPTY; //set space back to empty
        }
    }
    return number_moves;
}

Answer 3

I just noticed, checkListOfFields counts identical boards as identical games, wheras that is not quite true. You're calculating the number of end positions of boards rather than games, which (although interesting) is a different thing altogether.

Consider these two games:

X| |   X|O|   X|O|X
-----  -----  -----
 | |    | |    | | 
-----  -----  -----
 | |    | |    | | 

 | |X   |O|X  X|O|X
-----  -----  -----
 | |    | |    | | 
-----  -----  -----
 | |    | |    | | 

Your checkListOfFields function detects that these are the same game, and discards one. It therefore also discards one copy of all potential movesets that come after this.