技術メモ

役に立てる技術的な何か、時々自分用の覚書。幅広く興味があります。

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

三目並べでとりうる盤面の状態数を数えてみた。
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))

`Sanmoku.graph`は辞書型で今の状態に対して次に遷移しうる状態が入る。
`Sanmoku.value`は辞書型で今の状態は白が勝ちか(-1)黒が勝ちか(1)が入る。

0 [s]
5478

結果として何も置いてない状態も含めて5478通りあることがわかりました!(黒先番は固定)