三目並べの全ての状態数とその遷移関係を数え上げるアルゴリズム

三目並べでとりうる盤面の状態数を数えてみた。
f:id:swdrsker:20170413102529p:plain

英語ではTicTacToeと言ってボードゲームAIの入門によく使われる題材だったりする。
ゲームの状態数はよく9マス×3状態で $3^9=19683$ 通りだとか最初は9通りで次の番は8通り…だから $9!=362880$ 通りだとか言われるけれどどれも厳密な答えではない。
実は厳密な答えって探してもあんまり見つからない。そこでプログラムを組んで数え上げてみた。

# coding:utf-8
import numpy as np
from copy import deepcopy

BLANK = 0 # fix
BLACK = 1
WHITE = 2
SIMBOL = [" ","@","O",]


class Sanmoku():
    def __init__(self, n=3):
        self.graph = dict()
        self.value = dict()
        for i in range(pow(3,9)):
            self.graph[i] = []
            self.value[i] = 0
        self.make_graph()

    def display(self, number):
        board = self.num2board(number).reshape([3,3])
        for i in range(3):
            for j in range(3):
                print "|"+SIMBOL[board[i,j]],
            print "|\n"

    @staticmethod
    def num2board(number):
        if number < 0 or number > pow(3,9): return None
        number = int(number)
        map1d = np.zeros(9).astype(int)
        for i in range(9):
            map1d[i] = number%3
            number = number/3
        return map1d

    @staticmethod
    def board2num(board):
        return np.dot(board, pow(3 ,np.arange(9)))

    @staticmethod
    def is_over(board):
        """
        judge whether game is over : black wins 1 white wins -1
        """
        board2d = board.reshape([3,3])
        for i in range(3):
            if board2d[0,i] == board2d[1,i] and board2d[1,i] == board2d[2,i]:
                if board2d[0,i] == BLACK: return 1
                if board2d[0,i] == WHITE: return -1
            if board2d[i,0] == board2d[i,1] and board2d[i,1] == board2d[i,2]:
                if board2d[i,0] == BLACK: return 1
                if board2d[i,0] == WHITE: return -1
        if board2d[0,0] == board2d[1,1] and board2d[1,1] == board2d[2,2]:
            if board2d[0,0] == BLACK: return 1
            if board2d[0,0] == WHITE: return -1
        if board2d[2,0] == board2d[1,1] and board2d[1,1] == board2d[0,2]:
            if board2d[2,0] == BLACK: return 1
            if board2d[2,0] == WHITE: return -1
        return 0

    def make_graph(self):
        que = [[0,WHITE]]
        visited = dict()
        for i in self.graph.keys():
            visited[i] = False
        visited[0] = True
        while len(que) > 0:
            [number,turn] = que.pop(0)
            board = self.num2board(number)
            empty_index = [i for i, x in enumerate(board) if x == BLANK]
            if turn == BLACK: turn = WHITE
            else: turn = BLACK
            for i in empty_index:
                vboard = deepcopy(board)
                vboard[i] = turn
                new_num = self.board2num(vboard)
                self.graph[number].append(new_num)
                if not visited[new_num]:
                    visited[new_num] = True
                    reward = self.is_over(vboard)
                    if reward:
                        self.value[new_num] = reward
                        continue
                    que.append([new_num , turn])

        for i in self.graph.keys():
            if not visited[i]:
                self.graph.pop(i)
                self.value.pop(i)


if __name__=="__main__":
    import time
    start = time.time()
    sm = Sanmoku()
    end = time.time()
    print("%d [s]"%(end-start))
    print(len(sm.value))