三目並べが常に引き分けとなることを、minimax法総当たりによって検証

gistfile1.txt

$ python three_by_three.py
0

three_by_three.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class ThreeByThree():
    def __init__(self):
        self.board = [0] * 9
        self.memo = {}

    def result(self, current_state=1):
        """
         1: 先手必勝
        -1: 後手必勝
         0: 常に引き分け
        """
        memoise_key = repr([current_state, self.board])
        if memoise_key in self.memo:
            return self.memo[memoise_key]

        winner = self.won_by()
        if winner != 0:
            self.memo[memoise_key] = winner
            return winner

        spaces = [i for (i, v) in enumerate(self.board) if v == 0]
        if len(spaces) > 0:
            current_value = -current_state * float('inf')
            for i in spaces:
                self.board[i] = current_state
                value = self.result(-current_state)
                self.board[i] = 0
                if current_state * (value - current_value) > 0:
                    current_value = value
        else:
            current_value = 0

        self.memo[memoise_key] = current_value
        return current_value

    def won_by(self):
        for i in range(3):
            if self.board[3*i] == self.board[3*i+1] == self.board[3*i+2]:
                if self.board[3*i] != 0:
                    return self.board[3*i]
            if self.board[i] == self.board[3+i] == self.board[6+i]:
                if self.board[i] != 0:
                    return self.board[i]
        if (self.board[0] == self.board[4] == self.board[8]
            or self.board[2] == self.board[4] == self.board[6]):
            if self.board[4] != 0:
                return self.board[4]
        return 0


if __name__ == '__main__':
    print ThreeByThree().result()