-1

我正在尝试为永远不会输的井字游戏构建一个最小-最大算法......

我尝试通过阅读一些资料来构建它：

  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

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

但是，我总是能打败这个——我只需要做一个“叉子”
。例如：（我是 x，算法是 o） 

xx-   
xo-   
-o-

我赢了……
有一种算法可以制作一棵可以阻止分叉的树吗？

4

1 回答 1

1

你有三个错误。

1.在您的极小极大方法中，符号交换了太多次

你交换else块中的符号——对于myTurn的情况False——但你不应该这样做。您已经与每个递归调用交换了符号。由于这个错误，您在极小极大搜索过程中总是在棋盘上放置相同的符号，而不是相反的符号。显然，您因此错过了对手的所有威胁。

所以改变：

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

到：

    else:
        bestVal = (2**700)
        for move in board.empty:
            b = copy.deepcopy(board)
            b.ins(move, sign) # <-- corrected

2. 在find_best_move 中，您应该像调用 minimax 一样交换移动

find_best_move中也出现了类似的错误。每走一步，在新棋盘上叫极小极大时必须交换符号，否则会让同一个玩家玩两次。

所以改变这个：

    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中你不考虑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条件永远不应该为真，因为最近的举动是针对相反的标志，所以这永远不会导致对sign的胜利。

但是问题是：第二个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

如何调用find_best_move

最后，如果您始终使用myTurn参数调用find_best_move ，则上述方法有效，因为find_best_move使结果最大化，从 可以看出。因此，为避免使用 调用它，最好删除此参数并传递给minimax。所以：Trueif (curr_move > best_move)FalseFalse

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上运行。

请注意，此算法不是最优的。这只是蛮力。您可以查看存储先前评估位置的结果，进行 alpha-beta 修剪等...

于 2016-12-20T19:15:10.320 回答