3目並べは先手有利(全局面列挙してみた)

1.はじめに

「3目並べ」「OXゲーム」「TicTacToe」等色々な呼ばれ方をされているゲームですが、思いついたので全局面列挙してみました。結果、先手有利なことが判りました。

2.組み合わせ

TicTacToeには 3x3=9個のマスがあります。これをOとXで埋めていきます。初手は置ける候補が9か所あります。二手目は(すでに初手で1個置いたので)置ける候補が8か所になります。そのような理屈で結局 $9!$ 通りとなります。

9! = 9 * 8 * 7 * \cdots * 2  * 1 = 362880

38万通り(38万局面)と意外と少ないです。昔ならまだしも最近のパソコンなら余裕で列挙できそうです。

組み合わせの生成は再帰を使って実装できます。

#define D_MAX_DEPTH  (9)

void    MakeCombination(int *pNum, int depth);

int main()
{
    int Num[D_MAX_DEPTH] = { 0 };
    MakeCombination(Num, 0);

    return 0;
}

void       MakeCombination(int *pNum, int depth)
{
    int nBuf[D_MAX_DEPTH] = { 0 };

    if (depth == D_MAX_DEPTH) {
        // 組み合わせの表示
        for (int n = 0; n < D_MAX_DEPTH; n++) {
            printf("%d,", pNum[n]);
        }
        printf("\n");
        return;
    }
    for (int n = 0; n < depth; n++) {
        nBuf[pNum[n]] = 1;
    }
    for (int n = 0; n < D_MAX_DEPTH; n++) {
        if (nBuf[n] != 0) {
            continue;
        }
        pNum[depth] = n;
        MakeCombination(pNum, depth+1);
    }
}

結果はこんな感じ。

0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,8,7,
0,1,2,3,4,5,7,6,8,
0,1,2,3,4,5,7,8,6,

...(略)...

8,7,6,5,4,3,1,0,2,
8,7,6,5,4,3,1,2,0,
8,7,6,5,4,3,2,0,1,
8,7,6,5,4,3,2,1,0,

printfで時間を食いましたが、数分で終了しました。

以下のように a～iまでの9個のマスがあったとして、

「0,1,2,3,4,5,6,7,8」は0手目(初手)にaの位置へ、1手目にbの位置へ$\cdots$置くことにします。同様に、
「8,7,6,5,4,3,2,1,0」は0手目(初手)にiの位置へ、1手目にhの位置へ$\cdots$置ことにします。

さて、「0,1,2,3,4,5,6,7,8」「0,1,2,3,4,5,6,8,7」のときに、

6手目で勝負が付きますが、本投稿ではこれをそれぞれ「1局面」で数え、2局面としています。

3.結果

で、こんな結果になりました。

全362880局面

	局面数	勝率
先手勝ち	209376	57.7%
後手勝ち	101664	28.0%
引き分け	51840	14.3%

4.恥ずかしいけど全リスト(バグってませんように)

main.cpp

#include <stdio.h>

#define D_MAX_DEPTH  (9)

enum ETurn
{
    eUnknown = 0,
    eCircle,
    eCross,
    eDraw,
};

void    MakeCombination(int *pNum, int depth);
void    MakeBoard(int *pNum);

int     Search(int* pNum, int target);

void    PrintOrder(int* pNum);
void    PrintBoard(ETurn* pTurn);

ETurn   Judge(ETurn* pTurn, int depth);
ETurn   JudgeLine(ETurn *pTurn, int a, int b, int c);

long    nCircle = 0;
long    nCross  = 0;
long    nDraw   = 0;

int main()
{
    int Num[D_MAX_DEPTH] = { 0 };

    MakeCombination(Num, 0);

    int total = nCircle + nCross + nDraw;

    printf("O %ld(%g%%)\n",    nCircle, nCircle * 100. / total);
    printf("X %ld(%g%%)\n",    nCross,  nCross  * 100. / total);
    printf("Draw %ld(%g%%)\n", nDraw,   nDraw   * 100. / total);
    printf("total %d\n", total);

    return 0;
}

void       MakeCombination(int *pNum, int depth)
{
    int nBuf[D_MAX_DEPTH] = { 0 };

    if (depth == D_MAX_DEPTH) {
        MakeBoard(pNum);
        return;
    }
    for (int n = 0; n < depth; n++) {
        nBuf[pNum[n]] = 1;
    }
    for (int n = 0; n < D_MAX_DEPTH; n++) {
        if (nBuf[n] != 0) {
            continue;
        }
        pNum[depth] = n;
        MakeCombination(pNum, depth+1);
    }
}

int     Search(int* pNum, int target)
{
    for (int n = 0; n < D_MAX_DEPTH; n++) {
        if (pNum[n] == target) {
            return n;
        }
    }
    // ここに落ちることはない
    return -1;
}

void    MakeBoard(int* pNum)
{
    ETurn   aBoard[D_MAX_DEPTH] = { eUnknown };
    ETurn   dResult = eUnknown;

    ETurn   turn = eCircle;
    for (int n = 0; n < D_MAX_DEPTH; n++) {
        aBoard[Search(pNum, n)] = turn;
        dResult = Judge(aBoard, n+1);
        if (dResult != eUnknown) {
            break;
        }
        turn = (turn == eCircle) ? eCross : eCircle;
    }

    switch (dResult) {
    case eCircle:
        nCircle++; break;
    case eCross:
        nCross++;  break;
    default:
        nDraw++; break;
    }
//  PrintOrder(pNum);
//  PrintBoard(aBoard);
}

ETurn   Judge(ETurn* pTurn, int depth)
{
    // 横
    ETurn turn = JudgeLine(pTurn, 0, 1, 2);
    if ((turn == eCircle) || (turn == eCross)) {
        return turn;
    }
    turn = JudgeLine(pTurn, 3, 4, 5);
    if ((turn == eCircle) || (turn == eCross)) {
        return turn;
    }
    turn = JudgeLine(pTurn, 6, 7, 8);
    if ((turn == eCircle) || (turn == eCross)) {
        return turn;
    }
    // 縦
    turn = JudgeLine(pTurn, 0, 3, 6);
    if ((turn == eCircle) || (turn == eCross)) {
        return turn;
    }
    turn = JudgeLine(pTurn, 1, 4, 7);
    if ((turn == eCircle) || (turn == eCross)) {
        return turn;
    }
    turn = JudgeLine(pTurn, 2, 5, 6);
    if ((turn == eCircle) || (turn == eCross)) {
        return turn;
    }
    // ナナメ
    turn = JudgeLine(pTurn, 0, 4, 8);
    if ((turn == eCircle) || (turn == eCross)) {
        return turn;
    }
    turn = JudgeLine(pTurn, 2, 4, 6);
    if ((turn == eCircle) || (turn == eCross)) {
        return turn;
    }
    if (depth == D_MAX_DEPTH) {
        return eDraw;
    }
    return eUnknown;
}

ETurn   JudgeLine(ETurn* pTurn, int a, int b, int c)
{
    ETurn c0 = pTurn[a];
    ETurn c1 = pTurn[b];
    ETurn c2 = pTurn[c];

    if ((c0 != eCircle) && (c0 != eCross)) {
        return eUnknown;
    }
    if ((c1 != eCircle) && (c1 != eCross)) {
        return eUnknown;
    }
    if ((c2 != eCircle) && (c2 != eCross)) {
        return eUnknown;
    }
    if ((c0 == c1) && (c0 == c2)) {
        return c0;
    }
    return eUnknown;
}

void    PrintOrder(int* pNum)
{
    printf("%d|%d|%d\n", pNum[0], pNum[1], pNum[2]);
    printf("-+-+-\n");
    printf("%d|%d|%d\n", pNum[3], pNum[4], pNum[5]);
    printf("-+-+-\n");
    printf("%d|%d|%d\n\n", pNum[6], pNum[7], pNum[8]);
}

void    PrintBoard(ETurn* pTurn)
{
    char    c[D_MAX_DEPTH];

    for (int n = 0; n < D_MAX_DEPTH; n++) {
        switch (pTurn[n]) {
        case eCircle:
            c[n] = 'O'; break;
        case eCross:
            c[n] = 'X';  break;
        default:
            c[n] = ' ';  break;
        }
    }
    printf("%c|%c|%c\n", c[0], c[1], c[2]);
    printf("-+-+-\n");
    printf("%c|%c|%c\n", c[3], c[4], c[5]);
    printf("-+-+-\n");
    printf("%c|%c|%c\n\n", c[6], c[7], c[8]);
}