c++ - 如何通过最大数量的 Tic Tac Toe 可能性？

Question

我想知道 Tic Tac Toe 有多少种可能性，所以我在网上搜索并找到了一个数学定理，它表明 Tic Tac Toe 中有 255168 种可能的游戏。

网站:http://www.se16.info/hgb/tictactoe.htm

所以我想知道，我可以编写一个程序，看看计算机能以多快的速度处理每一种可能性，然后我编写了这段代码:

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

但是返回的总金额是:1916，和网站上的不一样，请问我的代码哪里出了问题。

关于代码的一些信息:

• 该字段是一个整数数组，有9个索引，其中1代表十字，2代表圆圈，0代表空字段。
• 它生成一个从 0~9 的随机值(如果之前没有被选择过)，然后它放置一个 1 或 2(取决于它在哪一轮)总是检查是否有人赢了或游戏是否平局。
• 完成游戏后，它将检查该可能性是否已经在列表中，如果是，它将不做任何事情并继续进行下一个。
• 当它经过 10 万种可能性而没有向列表中添加任何一种时，它将完成。

问题出在哪里？

Answer 1

我刚刚注意到，checkListOfFields 将相同的boards 视为相同的games，但这并不完全是真的。您计算的是棋盘结束位置的数量，而不是游戏，这(虽然很有趣)是完全不同的事情。

考虑这两个游戏:

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

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

您的checkListOfFields 函数检测到这些是同一个游戏，并丢弃一个。因此，它还丢弃了此之后所有潜在移动集的一个拷贝。