Minmax tictactoe算法永不失败

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

如果我的代码有问题，请告诉我！在

但是，我总是能战胜这个-我只需要做个“叉子”
例如：（I是x，算法是o）

^{pr2}$

我赢了…
有没有一种算法可以使一棵树阻塞分叉？在

Answer 1

你有三个错误。在

1。在您的minimax方法中，符号交换一次太多

如果myTurn是False，那么可以交换else块中的符号，但不应该这样。您已经在每个递归调用中交换了符号。因为这个错误，你总是把相同的标志在你的极小化最大搜索，从来没有相反的一个。很明显你错过了对手的所有威胁。在

所以改变一下：

    else:
        bestVal = (2**700)
        for move in board.empty:
            b = copy.deepcopy(board)
            b.ins(move, error xo.opp_sign(sign)) # <  bug

收件人：

^{pr2}$

2。在查找最佳移动中，您应该按您所称的minimax

交换移动

类似的错误也发生在find\u best\u move中。当你完成每一步动作时，你必须在新的棋盘上调用minimax时交换符号，否则你让同一个玩家玩两次。在

所以改变这个：

    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) # <  bug

收件人：

    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,not myTurn,xo.opp_sign(sign)) # <  corrected

请注意，第二个条件不应该是必要的：如果你是刚刚搬家的那个人，那么另一个应该处于有利位置是不符合逻辑的。在

3。在minimax中，当有win

时，您不考虑myTurn的值

虽然您考虑了myTurn的值来确定是最小化还是最大化，但是在检查是否获胜时，您不会执行此操作。在

您当前拥有：

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条件永远不应该是真的，因为最近的移动是针对相反的符号，所以这永远不会导致符号的胜利。在

但问题是：第二个if没有通过myTurn来确定返回值应该是负数还是正值。它应该这样做以保持一致。因此，将上述代码改为：

if self.is_win(board,xo.opp_sign(sign)):
    if myTurn: 
        return -(board.s**2+1) + depth
    else:
        return (board.s**2+1) - depth
elif board.is_full():
    return 0

如何调用查找最佳移动

最后，如果您总是使用myTurn参数将find_best_move调用为True，那么上面的方法是有效的，因为find_best_move最大化了可以从^{看到的结果。因此，为了避免用False来调用它，您最好删除这个参数，并将False传递给minimax。所以：

def find_best_move(self,board,depth,sign): # <  myTurn removed as argument
    # ... etc ...

        curr_move=self.minimax(b,depth,False,xo.opp_sign(sign)) # pass False

这样，参数myTurn指示该回合是否与调用find_best_move的玩家相同。在

工作溶液

通过添加最少的代码使其工作（添加了Board和XO类），可以看到程序在repl.it上运行。在

注意这个算法不是最优的。这只是蛮力。你可以查看存储先前评估过的位置的结果，做α-β修剪，等等。。。在