为什么minimax在这种情况下不选择最优解

Question

我正在为 cs50 课程做 tictactoe 项目
当我使用 minimax 时，我发现 minimax 在某些情况下找不到最优解

这是我的代码：

"""
Tic Tac Toe Player
"""
import copy
import math

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]]

board = initial_state()

def player(board):
    """
    Returns player who has the next turn on a board.
    """
    numO = 0
    numX = 0
    FirstPlayer = None
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] == O:
                numO += 1
            elif board[i][j] == X:
                numX += 1
    return X if numO == numX else O


def actions(board):
    """
    Returns set of all possible actions (i, j) available on the board.
    """
    possact = set()
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board [i][j] == EMPTY:
                possact.add((i, j))
    return possact


def result(board, action):
    """
    Returns the board that results from making move (i, j) on the board.
    """
    boardcopy = copy.deepcopy(board)
    boardcopy[action[0]][action[1]] = player(board)
    return boardcopy
    

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

    for i in range(3):
        wonO = True
        wonX = True
        for j in range(3):
            if board[i][j] == O or board[i][j] == EMPTY:
                wonX = False
            if board[i][j] == X or board[i][j] == EMPTY:
                wonO = False
        if wonX:
            return X
        if wonO:
            return O

    for j in range(3):
        wonO = True
        wonX = True
        for i in range(3):
            if board[i][j] == X or board[i][j] == EMPTY:
                wonO = False
            if board[i][j] == O or board[i][j] == EMPTY:
                wonX = False
        if wonX:
            return X
        if wonO:
            return O

    diag1 = ''
    diag2 = ''
    j = 2

    for i in range(3):
      diag1 += str(board[i][i])
      diag2 += str(board[i][j])
      j -= 1

    if diag1 == 'XXX' or diag2 == 'XXX':
      return X
    elif diag1 == 'OOO' or diag2 == 'OOO':
      return O


def terminal(board):
    """
    Returns True if game is over, False otherwise.
    """
    if winner(board) == X:
        return True
    elif winner(board) == O:
        return True

    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] == EMPTY:
                return False
    return True    

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


def minimax(board):
    """
    Returns the optimal action for the current player on the board.
    """
    if terminal(board):
        return None
    Max = float("-inf")
    Min = float("inf")

    if player(board) == X:
        return Max_Value(board, Max, Min)[1]
    else:
        return Min_Value(board, Max, Min)[1]

def Max_Value(board, Max, Min):
    move = None
    if terminal(board):
        return [utility(board), None]
    v = float('-inf')
    for action in actions(board):
        test = Min_Value(result(board, action), Max, Min)[0]
        Max = max(Max, test)
        if test > v:
            v = test
            move = action
        if Max >= Min:
            break
    return [v, move]

def Min_Value(board, Max, Min):
    move = None
    if terminal(board):
        return [utility(board), None]
    v = float('inf')
    for action in actions(board):
        test = Max_Value(result(board, action), Max, Min)[0]
        Min = min(Min, test)
        if test < v:
            v = test
            move = action
        if Max >= Min:
            break
    return [v, move]

情况如下（电脑玩O）： picture of 5th move
最佳解决方案是中间单元格的底部
但它选择了这个：picture of 6th move
计算机最终获胜但不是最佳方式

为什么minimax不选择最优解？
我该如何解决？

Answer 1

我没有查看您的代码是否正确实现了 minimax，但我可以解释为什么会出现这样的结果。

游戏树中可能有几条路径通向具有相同效用值的节点。 minimax算法不区分快赢和慢赢；它采取任何能保证获胜的路径。

解决这个问题的一种常见方法是为较慢的胜利分配较低的效用。例如，将胜利的效用设置为 1000 - depth。相反，损失的效用应设置为 -1000 + depth，以使算法更愿意尽可能长时间地提取不可避免的损失。（如果您想使用 negamax，保持评估函数对称也很好。）

为什么minimax在这种情况下不选择最优解

why minimax don't choose the optimal solution in this situation

python

artificial-intelligence

tic-tac-toe

minimax