cs50算法

Question

我目前在cs50 AI中做这个问题，在这里我们需要一个极小的算法来玩tictactoe。我的算法根本不工作(它真的很容易击败计算机)，我想知道我做错了什么。我也非常肯定，我的所有其他函数都是正确的，而且只有极小极大函数是不正确的。真的很感谢你的帮助，谢谢大家！

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)

• Determine
• 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

以下是一般的想法：

statement.

• Inside

1. 根据信息检查当前的棋盘是否为胜诉、抽签或损失以及返回值，通常返回-1、0或1。这是伪代码中的第一条if语句。
2. 则会查看是否是轮到它的，还是来自if -
3. 的对手将麦汁可能的分数设置为起始值。如果您只返回-1、0或1，那么将-2和2分别设置为max/min值就足够了。position.
4. You中的
5. 现在运行所有可能的移动，将新值设置为从另一个极小调用返回值的最大值/分钟，在该调用中，玩家转到changed.
6. After这个递归循环，返回的值将从给定的板上返回最佳路径。

深度是不必要的，因为抽搐-战术-脚趾是一个简单的游戏，我们总是可以达到一个结束状态。您可以使用深度来确保计算机通过在启发式返回值中添加深度来选择尽可能最短的获胜途径。但我建议你先让它发挥作用，不要让事情变得复杂:)