python - 絶対に負けない Minmax tic-tac-toe アルゴリズム

Question

決して負けない三目並べの最小最大アルゴリズムを構築しようとしています...

私はいくつかのソースを読んでそれを構築しようとしています:

1. http://neverstopbuilding.com/minimax
2. http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/ (これと非常によく似たものを作成しました)。

コードは次のとおりです: クラスツリー:

def find_best_move(self,board,depth,myTurn,sign):
    """

    :param board:
    :return:
    """
    if (board.empty==[]): return None

    best_move=-(2**(board.s**2))
    m=board.empty[0]
    for move in board.empty:
        b=copy.deepcopy(board)
        b.ins(move,sign)
        if (self.is_win(b,sign) or self.is_win(b,xo.opp_sign(sign))):
            return move
        curr_move=self.minimax(b,depth,myTurn,sign)
        if (curr_move > best_move):
            best_move = curr_move
            m=move
        print(curr_move,best_move,m)

    return m #This should be the right move to do....


# *****************************************************************************************************#

def minimax(self,board,depth,myTurn,sign):
    """

    :param depth:
    :param myTurn:
    :return:
    """
    #print(depth,end='\n')
    if (self.is_win(board,sign)):
        #print("I win!")
        return (board.s**2+1) - depth
    elif (self.is_win(board,xo.opp_sign(sign))):
        #print("You win!")
        return -(board.s**2+1) + depth
    elif (board.is_full()):
        return 0

    if (myTurn):
        bestVal=-(2**700)
        for move in board.empty: #empty - the empty squares at the board 
            b = copy.deepcopy(board)
            b.ins(move, sign)
            value=self.minimax(b,depth+1,not myTurn, xo.opp_sign(sign))
            #xo.opp_sign(sign) - if function for the opposite sign: x=>o and o=>x
            bestVal = max([bestVal,value])
        return bestVal

    else:
        bestVal = (2**700)
        for move in board.empty:
            b = copy.deepcopy(board)
            b.ins(move, xo.opp_sign(sign))
            value = self.minimax(b, depth + 1, not myTurn, xo.opp_sign(sign))
            #print("opp val: ",value)
            bestVal = min([bestVal, value])
        return bestVal


# *****************************************************************************************************#
def is_win(self,board, sign):
    """
    The function gets a board and a sign.
    :param board: The board.
    :param sign: The sign (There are only two options: x/o).
    :return: True if sign "wins" the board, i.e. some row or col or diag are all with then sing. Else return False.
    """

    temp=board.s
    wins = []  # The options to win at the game.
    for i in range(1, temp + 1):
        wins.append(board.get_col(i))
        wins.append(board.get_row(i))
    wins.append(board.get_diag1())
    wins.append(board.get_diag2())

    for i in wins:
        if (self.is_same(i, sign)):
            return True
    return False



# *****************************************************************************************************#
def is_same(self, l, sign):
    """
    The function get a list l and returns if ALL the list have the same sign.
    :param l: The list.
    :param sign: The sign.
    :return: True or false
    """

    for i in l:
        if (i != sign):
            return False
    return True

私のコードに何か問題がある場合は、教えてください!

しかし、私はいつでもこれを打ち負かすことができます-「フォーク」を作成する必要があるだけです
.eg：（私はx、アルゴリズムはoです）

xx-   
xo-   
-o- 

そして、私は勝ちます...
フォークをブロックできるツリーを作成するためのアルゴリズムはありますか?