Tic Tac Toe AI 不工作（最小最大算法）

Question

我正在尝试使用 minimax 算法在 python 中制作井字棋 ai。我已经阅读了一些博客并提出了这些功能。但由于某种原因，它不起作用。

代码：

class RunTimeError(Exception):
    pass

class TicTacToe:
    '''Tic Tac Toe class'''
    
    SYMBOL_X = 'x'
    SYMBOL_O = 'o'
    SYMBOL_EMPTY = '-'
    INDEX_MAP = {
        0: [0, 0], 1: [0, 1], 2: [0, 2],
        3: [1, 0], 4: [1, 1], 5: [1, 2],
        6: [2, 0], 7: [2, 1], 8: [2, 2]
    }

    def __init__(self) -> None:
        '''Initialize the game'''
        self.reset()

    def reset(self) -> None:
        '''Reset the game'''
        self.board = [[self.SYMBOL_EMPTY for _ in range(3)] for _ in range(3)]
        self.current_turn = 'x'
        self.moves_stack = []
        self.winner = None
        self.game_state = 'RUNNING'

    def swap_turn(self) -> None:
        '''Swap the turn'''
        self.current_turn = self.SYMBOL_X if self.current_turn == self.SYMBOL_O else self.SYMBOL_O

    def play_move(self, index: int) -> None:
        '''Play a move on the given index:
            0 1 2
            3 4 5
            6 7 8'''

        if self.game_state != 'RUNNING':
            raise RuntimeError('Game already terminated')
        if not isinstance(index, int):
            raise RunTimeError(f"Expected index type 'int' got {type(index)}")
        try:
            y, x = self.INDEX_MAP[index]
        except KeyError:
            raise RunTimeError(f'Expected index to be from 0-8, got {index}')
        if self.board[y][x] != self.SYMBOL_EMPTY:
            raise RunTimeError('Invalid Move - Box occupied')

        self.board[y][x] = self.current_turn
        self.moves_stack.append(index)
        self.update_game_state()
        self.swap_turn()

    def undo_move(self) -> int:
        '''Reverse the last move and return its index'''
        index = self.moves_stack.pop()
        y, x = self.INDEX_MAP[index]
        self.board[y][x] = self.SYMBOL_EMPTY
        self.winner = None
        self.game_state = 'RUNNING'
        self.swap_turn()
        return index

    def update_game_state(self) -> None:
        '''Check for a winner'''
        win_cases = [
            self.board[0][0] == self.board[0][1] == self.board[0][2] == self.current_turn,
            self.board[1][0] == self.board[1][1] == self.board[1][2] == self.current_turn,
            self.board[2][0] == self.board[2][1] == self.board[2][2] == self.current_turn,
            self.board[0][0] == self.board[1][0] == self.board[2][0] == self.current_turn,
            self.board[0][1] == self.board[1][1] == self.board[2][1] == self.current_turn,
            self.board[0][2] == self.board[1][2] == self.board[2][2] == self.current_turn,
            self.board[0][0] == self.board[1][1] == self.board[2][2] == self.current_turn,
            self.board[0][2] == self.board[1][1] == self.board[2][0] == self.current_turn,
        ]
        if any(win_cases):
            self.winner = self.current_turn
            self.game_state = 'WIN'
        elif self.SYMBOL_EMPTY not in [element for row in self.board for element in row]:
            self.game_state = 'DRAW'

    def generate_possible_moves(self) -> list:
        '''Returns a list with all possible move indexes'''
        moves = []
        for num in range(8):
            if num not in self.moves_stack:
                moves.append(num)
        return moves

    def __str__(self) -> str:
        '''Returns the board as a string'''
        return '\n'.join([
            f' {self.board[0][0]} | {self.board[0][1]} | {self.board[0][2]}',
            '-' * 11,
            f' {self.board[1][0]} | {self.board[1][1]} | {self.board[1][2]}',
            '-' * 11,
            f' {self.board[2][0]} | {self.board[2][1]} | {self.board[2][2]}'
        ])

    def ai_play(self):
        best_score = -100
        best_move = None

        for move in self.generate_possible_moves():
            self.play_move(move)
            score = self.minmax(False, self.current_turn)
            print(score)
            self.undo_move()

            if score > best_score:
                best_score = score
                best_move = move

        self.play_move(best_move)

    def minmax(self, maximizing, symbol):
        if self.game_state == 'DRAW':
            return 0
        elif self.game_state == 'WIN':
            return 1 if self.winner == symbol else -1

        scores = []
        for move in self.generate_possible_moves():
            self.play_move(move)
            scores.append(self.minmax(not maximizing, symbol))
            self.undo_move()

        return max(scores) if maximizing else min(scores)

game1 = TicTacToe()

print(game1)
game1.ai_play()
print(game1)

它引发了以下错误：

Traceback (most recent call last):
  File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 139, in <module>
    game1.ai_play()
  File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 112, in ai_play
    score = self.minmax(False, self.current_turn)
  File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 131, in minmax
    scores.append(self.minmax(not maximizing, symbol))
  File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 131, in minmax
    scores.append(self.minmax(not maximizing, symbol))
  File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 131, in minmax
    scores.append(self.minmax(not maximizing, symbol))
  [Previous line repeated 4 more times]
  File "c:\Users\LENOVO\Desktop\tic tac toe.py", line 134, in minmax
    return max(scores) if maximizing else min(scores)
ValueError: max() arg is an empty sequence

我不知道是什么问题（我花了很多时间试图解决它）如有任何帮助，我们将不胜感激！

Answer 1

max 和 min 函数要求传递的列表中至少有一项。当在 minmax 函数中没有更多可能的移动时，generate_possible_moves return 是一个空列表，因此 scores 是 []。 max([]) 会抛出错误，因为 max from.

无事可做

当没有可能的移动时，您将不得不分配一些分数，并且 return 当 len(scores) 为 0

时

另外，撤消动作时必须调用update_game_state，否则状态不正确。

Tic Tac Toe AI 不工作（最小最大算法）

Tic Tac Toe AI not working(min max algorithm)

python

artificial-intelligence

tic-tac-toe

minmax