如何提高我使用Minimax算法的Tic脚趾AI的成功率？

Question

这是我在这里的第一篇帖子！

我正在开发Python中的Tic Tac Toe AI，它使用Minimax算法击败计算机或普通播放器。到目前为止，它有大约70%的机会赢得每场比赛，但我试图增加这个数字。下面的几个测试显示了使用极小极大算法的完美玩家对普通计算机播放器的测试结果，后者在游戏中随机选择要玩的点：

第一次测试：Perfect Player X won 67 time(s), Player O won 25 time(s), and there were 8 tie(s).

第二次测试：Perfect Player X won 70 time(s), Player O won 21 time(s), and there were 9 tie(s).

第三次测试：Perfect Player X won 68 time(s), Player O won 25 time(s), and there were 7 tie(s).

算法播放器(PerfectPlayer)和普通计算机播放器(ComputerPlayer)的代码如下所示。

# Recognise the player as an object, with a specific letter (X or O)
class Player:

    # Set the player's letter (noughts or crosses)
    def __init__(self, letter): self.letter = letter

    # Turn-based system
    def get_move(self, game): pass

# Perfect Tic Tac Toe AI using the Minimax Algorithm
class PerfectPlayer(Player):

    # Initialize the player and it's letter
    def __init__(self, letter):
        super().__init__(letter)

    # Get the pefect move for the game -- where the MAGIC happens!
    def get_move(self, game):
        
        # If all moves are open, then do any random move
        if len(game.open_moves()) == 9: choice = random.choice(game.open_moves())

        # If there are tokens on the board, then find the optimal move based on that token's position
        else: choice = self.minimax(game, self.letter)["position"]

        return choice

    # Minimax, the engine for the magic!
    def minimax(self, state, player):

        # Get which player is who
        max_player = self.letter
        opponent = "O" if player == "X" else "X"

        # Check if game is over
        if state.current_winner == opponent:

            return {
                    "position": None,
                    "score": 1 * (state.empty_square_vals() + 1) if opponent == max_player else -1 * (state.empty_square_vals() + 1)
                    }

        # Check if there are no empty squares
        elif not state.empty_squares():
            
            return {
                    "position": None,
                    "score": 0
                    }

        if player == max_player:
            
            # Each score should maximize
            best = {
                    "position": None,
                    "score": -math.inf
                    }

        else:
            # Each score should minimize
            best = {
                    "position": None,
                    "score": math.inf
                    }

        for possible_move in state.open_moves():

            # Try a spot
            state.make_move(possible_move, player)

            # Simulate a game with that move
            sim_score = self.minimax(state, opponent)

            # Undo the move (remember, it's only the simulation)
            state.board[possible_move] = " "
            state.current_winner = None
            sim_score["position"] = possible_move

            # Maximize the 'max_player'
            if player == max_player:

                # If the simulated score from a specific move is the best option, do it
                if sim_score["score"] > best["score"]:
                    best = sim_score

            # Minimize the 'opponent'
            else:

                if sim_score["score"] < best["score"]:
                    best = sim_score

            return best

# Use the inheritance of classes to create a computer player that uses the 'Player' class
class ComputerPlayer(Player):

    # Set the computer's letter with teh super class
    def __init__(self, letter): super().__init__(letter)

    # Turn-based system, get a random move from all open possibilities
    def get_move(self, game):
        choice = random.choice(game.open_moves())
        return choice

有人对如何改进我的算法有什么建议吗？另外，对于不同的赢球方法的建议也是有效的。

另外，如果我缺少任何必要的代码，请告诉我(这里并不包括所有代码，但如果需要，我可以提供更多代码)。提前谢谢你！

编辑:我已经被告知，我应该包括一些代码，所以他们在这里。

game.py：

# Import other Python file and classes for game
from player import NormalPlayer, ComputerPlayer, PerfectPlayer
from store import store_results

empty = " "

# Store results?
store = True

def update_board(this):
    print("╭-----------╮")
    this.print_board_values()
    print("|-----------|")
    this.print_board()
    print("╰-----------╯")

# Tic Tac Toe game
class TicTacToe:

    # Initialize the game features
    def __init__(self):

        # Create an empty board list with 9 free spots
        self.board = [empty for _ in range(9)]
    
        # Track the current winner of the game
        self.current_winner = None

    # Method to print the board
    def print_board(self):

        # Create the board rows and print
        for row in  [self.board[x * 3: (x + 1) * 3] for x in range(3)]:
            print("| " + " | ".join(row) + " |")

    # This is a static method, as it doesn't require the 'self' parameter
    def print_board_values(self):

        # Set the board with spot values
        # | 0, 1, 2... 6, 7, 8 |
        number_board = [[str(value) for value in range(row * 3, (row + 1) * 3)]  for row in range(3)]

        # Print out the board with the spot values
        for row in number_board: print("| " + " | ".join(row) + " |")

    # Check for all the possible moves for the game
    def open_moves(self):

        # Enumerate, or list, all spot values that are empty
        return [i for i, spot in enumerate(self.board) if spot == empty]

    # Return all the empty board spots
    def empty_squares(self): return empty in self.board

    # Return the number of possible moves
    def empty_square_vals(self): return self.board.count(empty)

    # Method to update the board with player moves
    def make_move(self, choice, letter):

        # If the spot is open, then set the board accordingly
        if self.board[choice] == empty:
            self.board[choice] = letter

            # Check for the winner
            if self.winner(choice, letter): self.current_winner = letter
            return True
        
        return False


    # If any player makes 3 in a row, they are the winner
    def winner(self, choice, letter):

        # Check rows for tic tac toe
        row_ind = choice // 3
        row = self.board[row_ind * 3 : (row_ind + 1) * 3]

        if all([spot == letter for spot in row]): return True

        # Check columns for tic tac toe
        col_ind = choice % 3
        col = [self.board[col_ind + i * 3] for i in range(3)]

        if all([spot == letter for spot in col]): return True

        # Check diagonals for tic tac toe
        if choice % 2 == 0:

            # Left to right
            diagonal1 = [self.board[i] for i in [0, 4, 8]]

            if all([spot == letter for spot in diagonal1]): return True

            # Right to left
            diagonal2 = [self.board[i] for i in [2, 4, 6]]

            if all([spot == letter for spot in diagonal2]): return True


def  play(game, x_player, o_player, print_game = True):

    # Print the board
    if print_game:
        print("")
        update_board(game)
        print("")

        # Cross player statrts
        letter = "X"

        # Keep running the game procedure as long s no one has won, and there are empty spaces
        while game.empty_squares():

            # If the noughts player is going, ask for their move
            if letter == "O": choice = o_player.get_move(game)
        
            # If the crosses player is going, ask for their move
            else: choice = x_player.get_move(game)

            # Print out the game updates
            if game.make_move(choice, letter):

                # Print which player went, and where
                if print_game:
                    print("")
                    print("Player " + letter + " played " + str(choice) + "!")
                    update_board(game)
                    print("")

                # If there is a winner, announce who won!
                if game.current_winner:

                    if print_game: print(letter + " won the game!")

                    return letter


            # Switch the player turns
            letter = "O" if letter == "X" else "X"

    # If no one wins, say it is a tie
    if print_game: print("It's a tie!")

# Play the game
if __name__ == "__main__":

    x_wins = 0
    o_wins = 0
    ties = 0

    # Check how many times the game should be run
    games = input("How many games do you want to run? ")

    if games == "": games = 100

    # Repeat game over and over 
    for _ in range(int(games)):
        
        x_player = PerfectPlayer("X") # Minimax Player
        o_player = ComputerPlayer("O")

        ttt = TicTacToe()

        result = play(ttt, 
                        x_player, 
                        o_player, 
                        print_game = True)

        if result == "X": x_wins += 1
        elif result == "O": o_wins += 1
        else: ties += 1 

    # Say who won how many times    
    print("Perfect Player X won " + str(x_wins) + " time(s), Player O won " + str(o_wins) + " time(s), and there were " + str(ties) + " tie(s).")

    if type(x_player).__name__ == "PerfectPlayer" and type(o_player).__name__ == "ComputerPlayer" and store:
        
        print("")
        # Store results
        store_results(x_wins, o_wins, ties)

player.py：

# Things to keep in mind...
# The official term for the X's and O's in Tic-Tac-Toe are Noughts (O) and Crosses (X)
# The board is stored as a list, with values ranging from 0 (top left) to 8 (bottom right)
# The Tic-Tac-Toe AI uses the minimax algorthim, that predicts possible moves from the current board state

# All imports here!
import math
import random

empty = " "


# Recognise the player as an object, with a specific letter (X or O)
class Player:

    # Set the player's letter (noughts or crosses)
    def __init__(self, letter): self.letter = letter

    # Turn-based system
    def get_move(self, game): pass

# Use the inheritance of classes to create a computer player that uses the 'Player' class
class ComputerPlayer(Player):

    # Set the computer's letter with teh super class
    def __init__(self, letter): super().__init__(letter)

    # Turn-based system, get a random move from all open possibilities
    def get_move(self, game):
        choice = random.choice(game.open_moves())
        return choice

# Use the inheritance of classes for the user object that uses the 'Player' class
class NormalPlayer(Player):

    # Set the user's letter with the super class
    def __init__(self, letter): super().__init__(letter)

    # Turn-based system, get the player's movement choice
    def get_move(self, game):

        # Player's choice must first be verified
        verified = False

        # The spot value of the move the player wants to make
        value = None

        # Ask for the player's move
        while not verified:
            choice = input(self.letter + "'s turn. Which spot do you want to play? ")

            # Check if the player's choice is valid...
            try:

                # Turn the input into an integer
                value = int(choice)
                verified = True

                # If the spot value is not available, catch the error and tell the player
                if value not in game.open_moves():
                    verified = False
                    raise ValueError

            # ...if it is, then announce it
            except ValueError:

                # If the choice was invalid, have the player decide their move again
                print("The spot value is not valid. Please choose another spot.")

        return value


# Perfect Tic Tac Toe AI using the Minimax Algorithm
class PerfectPlayer(Player):

    # Initialize the player and it's letter
    def __init__(self, letter): super().__init__(letter)

    # Get the pefect move for the game -- where the MAGIC happens!
    def get_move(self, game):
        
        # If all moves are open, then do any random move
        if len(game.open_moves()) == 9: choice = random.choice(game.open_moves())

        # If there are tokens on the board, then find the optimal move based on that token's position
        else: choice = self.minimax(game, self.letter)["position"]

        return choice

    # Minimax, the engine for the magic!
    def minimax(self, state, player):

        # Get which player is who
        max_player = self.letter
        opponent = "O" if player == "X" else "X"

        # Check if game is over
        if state.current_winner == opponent:

            return {
                    "position": None,
                    "score": 1 * (state.empty_square_vals() + 1) if opponent == max_player else -1 * (state.empty_square_vals() + 1)
                    }

        # Check if there are no empty squares
        elif not state.empty_squares():
            
            return {
                    "position": None,
                    "score": 0
                    }

        if player == max_player:
            
            # Each score should maximize
            best = {
                    "position": None,
                    "score": -math.inf
                    }

        else:
            # Each score should minimize
            best = {
                    "position": None,
                    "score": math.inf
                    }

        for possible_move in state.open_moves():

            # Try a spot
            state.make_move(possible_move, player)

            # Simulate a game with that move
            sim_score = self.minimax(state, opponent)

            # Undo the move (remember, it's only the simulation)
            state.board[possible_move] = empty
            state.current_winner = None
            sim_score["position"] = possible_move

            # Maximize the 'max_player'
            if player == max_player:

                # If the simulated score from a specific move is the best option, do it
                if sim_score["score"] > best["score"]:
                    best = sim_score

            # Minimize the 'opponent'
            else:

                if sim_score["score"] < best["score"]:
                    best = sim_score

            return best

另外，请注意，minimax用户确实会在时间上丢失。虽然70%的比赛是由它赢的，但它确实输掉了一小部分比赛，并将一小部分比赛与随机选择的对手绑在一起。

Answer 1

抽搐脚趾很容易解决。这意味着你的PerfectPlayer没有理由不完美:它不应该松懈(而且面对一个随机的对手，它应该经常赢)。

很明显，你的极大极小算法有问题。为什么得分这么复杂？为什么算法关心的是谁把它变成“真正的”呢？return best应该在for possible_move...循环中吗？

• 保持你的格式乏味。您可以使用像皮科德基式这样的检查器。(我不喜欢它的所有规则，但检查器的要点是不要花时间担心代码的格式是否正确。)
• 尝试使无效状态无法表示。对非任意文本的数据使用字符串并不好。对于具有已知结构的数据使用dicts也不是很好。
• 为了限制什么是“可表示的”，我喜欢使用类型注释。但是请注意，python本身并不检查类型；如果您希望您的类型注释不是花哨的注释，那么您必须使用像形象化这样的外部工具