cs50 python tictactoe minimax 算法

Question

我目前正在 cs50 AI 中做这个问题，我们需要制作一个 minimax 算法来玩 tictactoe。我的算法根本不起作用（打败计算机真的很容易），我想知道我做错了什么。我也很确定我的所有其他函数都是正确的，只有 minimax 函数不正确。非常感谢任何帮助，谢谢大家！



import math, copy

X = "X"
O = "O"
EMPTY = None


def initial_state():
    """
    Returns starting state of the board.
    """
    return [[EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY]]


def player(board):
    """
    Returns player who has the next turn on a board.
    """
    xplayer = 0
    yplayer = 0
    for row in board:
        for column in row:
            if column == 'X':
                xplayer += 1
            elif column == 'O':
                yplayer += 1

    if xplayer == yplayer:
        return X
    else:
        return O


def actions(board):
    """
    Returns set of all possible actions (i, j) available on the board.
    """
    ans = set()
    rownum = 0
    colnum = 0
    for row in board:
        colnum = 0
        for column in row:
            if not column:
                ans.add((rownum, colnum))
            colnum += 1
        rownum += 1

    return ans

def result(board, action):
    """
    Returns the board that results from making move (i, j) on the board.
    """
    if board[action[0]][action[1]] != None :
        raise BoardError("Tried to place on full square")
    move = player(board)
    newboard = copy.deepcopy(board)
    newboard[action[0]][action[1]] = move
    return newboard


def winner(board):
    """
    Returns the winner of the game, if there is one.
    """


    for i in range(3):
        sum = 0
        for j in range(3):
            if board[i][j] == 'X':
                sum += 1
            elif board[i][j] == 'O':
                sum -= 1
        if sum == 3:
            return X
        elif sum == -3:
            return O

    for j in range(3):
        sum = 0
        for i in range(3):
            if board[i][j] == 'X':
                sum += 1
            elif board[i][j] == 'O':
                sum -= 1
        if sum == 3:
            return X
        elif sum == -3:
            return O
    if board[0][0] == board[1][1] == board[2][2]:
        return board[0][0]
    if board[2][0] == board[1][1] == board[0][2]:
        return board[2][0]
    return None


def terminal(board):
    """
    Returns True if game is over, False otherwise.
    """
    if winner(board):
        return True
    if not actions(board):
        return True
    return False



def utility(board):
    """
    Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
    """
    if winner(board) == X:
        return 1
    elif winner(board) == O:
        return -1
    else:
        return 0

def minimax(board):
    """
    Returns the optimal action for the current player on the board.
    """
    if player(board) == X:
        aim = 1
    elif player(board) == O:
        aim = -1
    if terminal(board):
        return None


    possiblemoves = actions(board)
    for move in possiblemoves:
        newboard = result(board,move)

        #if move leads to the aimed score, return move
        if utility(newboard) == aim:
            return move

        #if nodes down the chain return a value cos they have reached the aim, return this current move
        if minimax(newboard):
            return move


    aim = 0

    #change the aim to be a draw since winning is no longer possible
    for move in possiblemoves:
        newboard = result(board,move)


        if utility(newboard) == aim:
            return move

        if minimax(newboard):
            return move

    #all the moves will result in a loss, so i just return the first move
    return possiblemoves[0]

基本上X的目标是最大化，O的目标是最小化。我为算法所做的工作取决于玩家，首先根据玩家寻找会导致 1 或 -1 的动作。然后，如果没有发生这种情况，请寻找导致 0（平局）的动作。然后之后只需 return 任何移动，因为这意味着玩家将输。

Answer 1

您似乎有很多不必要的函数，而且您的极小极大代码看起来太复杂了。基本上你的游戏需要 4 个主要功能：

极小极大本身
从一个位置获取所有可能的移动（除非你想在 minimax 内进行循环）
确定玩家是否获胜
判断看板是否已满

此外，您是否看过 minimax 的伪代码，例如维基百科？ :

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

大致思路如下：

判断当前棋盘是赢、平还是输，根据信息判断return值，一般为return-1、0、1。这是第一个if语句伪代码。
然后根据if-else判断是轮到自己还是对手。
在其中，您将麦芽汁可能得分设置为起始值。如果你只有 return -1、0 或 1，那么将 -2 和 2 分别设置为 max/min 值就足够了。
您现在运行完成了该位置的所有可能移动。
您将新值设置为 returned 值的 max/min 来自玩家轮次已更改的另一个 minimax 调用。
在此递归循环之后，您 return 将给出从给定板出发的最佳路线的值。

深度是不必要的，因为井字游戏是一个简单的游戏，我们总能达到最终状态。您可以使用深度来确保计算机通过将深度添加到启发式 return 值来选择可能的最短路径来取得胜利。但我建议你先让它工作，不要让事情复杂化:)

cs50 python tictactoe minimax 算法

cs50 python tictactoe minimax algorithm

python

algorithm

tic-tac-toe

minimax

cs50