cs50 python Tictoe极小极大算法

Question

我目前正在cs50 AI中解决这个问题，我们需要为玩Tictatcoe制作一个minimax算法。我的算法根本不起作用（打败电脑真的很容易），我想知道我做错了什么。我也非常确定我所有的其他函数都是正确的，只有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（平局）的移动。 然后，只是简单地返回任何移动，因为这意味着玩家将失败

Answer 1

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

• 极小极大本身
• 从一个位置获得所有可能的移动（除非你想在minimax内循环）
• 确定一个玩家是否赢了
• 确定电路板是否已满

另外，您是否查看过Wikipedia等网站上的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

以下是总体思路：

1. 检查当前板是否为赢、平或输，并根据信息返回值，通常返回-1、0或1。这是伪代码中的第一条if语句
2. 然后从if-else语句中查看是轮到它还是对手
3. 在里面，你可以设置麦汁可能的分数作为起始值。如果只返回-1、0或1，则分别将-2和2设置为最大/最小值就足够了
4. 现在，您可以在该位置运行所有可能的移动
5. 您将新值设置为另一个minimax调用返回值的最大/最小值，其中玩家回合已更改
6. 在这个递归循环之后，您将返回一个值，该值将给出从给定电路板开始的最佳路径

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