井字形使用 minMax 算法

Question

首先你好 我正在尝试使用极小极大算法实现井字棋游戏，我尝试了很多方法，直到我对这种实现感到满意，但我面临着人工智能移动中的一些不合逻辑的移动，我尝试调试很多次，但无法达到不合逻辑的错误这让我可以通过 AI 动作进行连续动作

我正在尝试从 Ai 获得最佳 sol，这样 X 不会获胜或 Ai 获胜

import random


class TicTacToe:

    def __init__(self):
        """Initialize with empty board"""
        self.board = [" ", " ", " ",
                      " ", " ", " ",
                      " ", " ", " "]

    def show(self):
        """Format and print board"""
        print("""
          {} | {} | {}
         -----------
          {} | {} | {}
         -----------
          {} | {} | {}
        """.format(*self.board))

    def clearBoard(self):
        self.board = [" ", " ", " ",
                      " ", " ", " ",
                      " ", " ", " "]

    def whoWon(self):
        if self.checkWin() == "X":
            return "X"
        elif self.checkWin() == "O":
            return "O"
        elif self.gameOver() == True:
            return "Nobody"

    def availableMoves(self):
        """Return empty spaces on the board"""
        moves = []
        for i in range(0, len(self.board)):
            if self.board[i] == " ":
                moves.append(i)
        return moves

    def getMoves(self, player):
        """Get all moves made by a given player"""
        moves = []
        for i in range(0, len(self.board)):
            if self.board[i] == player:
                moves.append(i)
        return moves

    def makeMove(self, position, player):
        """Make a move on the board"""
        if self.board[position] == " ":
            self.board[position] = player
            return True
        elif self.board[position] != " " and player is " ":
            self.board[position] = player
            return True
        else:
            print("Invalid Move")
            return False

    def checkWin(self):
        """Return the player that wins the game"""
        combos = ([0, 1, 2], [3, 4, 5], [6, 7, 8],
                  [0, 3, 6], [1, 4, 7], [2, 5, 8],
                  [0, 4, 8], [2, 4, 6])

        for player in ("X", "O"):
            positions = self.getMoves(player)
            for combo in combos:
                win = True
                for pos in combo:
                    if pos not in positions:
                        win = False
                if win:
                    return player

    def gameOver(self):
        """Return True if X wins, O wins, or draw, else return False"""
        if self.checkWin() != None:
            return True
        for i in self.board:
            if i == " ":
                return False
        return True

    def minimax(self, board=None, depth=None, player=None):
        # scores={"X":1,"O":-1,"Nobody":0}
        # if self.gameOver() or depth == 0:
        #     return scores[self.whoWon()]
        win = self.whoWon()
        if win == "X":
            return 1
        if win == "O":
            return -1
        if self.gameOver() or depth == 0:
            return 0
        if player == "O":
            best = 9999
            for i in self.availableMoves():
                if self.board[i] == " ":
                    self.board[i] = player
                    # self.show()
                    # print(f"best at depth:{depth} and i :{i},and best score:{best}")
                    best = min(best, self.minimax(depth=depth+ 1, player=changePlayer(player)))
                    self.board[i] = " "
            return best
        else:
            best = -9999
            for i in self.availableMoves():
                if self.board[i] == " ":
                    self.board[i] = player
                    best = max(best, self.minimax(depth=depth +1, player=changePlayer(player)))
                    self.board[i] = " "
            return best

        # """
        # Recursively analyze every possible game state and choose
        # the best move location.
        # node - the board
        # depth - how far down the tree to look
        # player - what player to analyze best move for (currently setup up ONLY for "O")
        # if depth is zero, then it's the root node or game is over (no more moves)
        # """
        # return 1
        # pass


def changePlayer(player):
    """Returns the opposite player given any player"""
    if player == "X":
        return "O"
    else:
        return "X"


def make_best_move(board, depth, player):
    bestMove = -1
    bestScore = -9999
    for i in range(0, 9):
        if board.board[i] == " ":
            board.board[i] = player
            moveVal = board.minimax(depth=depth, player="O")
            board.board[i] = " "

            if moveVal > bestScore:
                bestScore = moveVal
                bestMove = i
    print("The value of the best Move is :", bestScore)
    print()
    return bestMove
    # """
    # Controllor function to initialize minimax and keep track of optimal move choices
    # board - what board to calculate best move for
    # depth - how far down the tree to go
    # player - who to calculate best move for (Works ONLY for "O" right now)
    # """


# Actual game
if __name__ == '__main__':
    game = TicTacToe()
    game.show()

    while game.gameOver() == False:

        isValid = False
        while not isValid:
            person_move = int(input("You are X: Choose number from 1-9: "))
            # c1 = make_best_move(game,-1,"X")
            # isValid = game.makeMove(c1,"X")
            isValid = game.makeMove(person_move - 1, "X")
        game.show()

        if game.gameOver() == True:
            break

        print("Computer choosing move...")
        ai_move = make_best_move(game, -1, "O")
        print(f"ai move:{ai_move}")
        game.makeMove(ai_move, "O")
        game.show()

print("Game Over. " + game.whoWon() + " Wins")

Answer 1

主要问题是：

1. 在

   make_best_move

   中，

   player

   参数被忽略。相反，调用

   minimax

   时，玩家参数设置为“O”。但在你的主循环中，

   make_best_move

   被调用，

   player

   也等于“O”，所以现在

   make_best_move

   执行“O”的移动，然后仍然调用

   minimax

   让它为“O”播放移动。这是错误的。

   make_best_move

   应考虑其

   player

   参数并决定是最大化还是最小化，并确保将 opponent 传递给

   minimax

   调用。

2. 主循环传递 -1 作为

   depth

   的值。由于

   minimax

   在每次递归调用时都会将深度加 1，因此您将很快达到

   depth == 0

   的基本情况，因此您通常会得到 0 作为评估，这意味着最佳移动通常是第一个可能的举动。让主循环传递一个值 -5，以确保在

   depth

   第一次下棋后检测到强制获胜之前，

   O

   不会达到 0。例如：

    X . .       X O .
    . . .  =>   . . .
    . . .       . . .
   

   深度设置为 -5 时，

   O

   的这一步棋将被丢弃，并进行更好的棋步。

这是对

make_best_move

的更正：

def make_best_move(board, depth, player):
    bestMove = -1
    # Decide to minimize or maximize
    bestScore = 9999 if player == "O" else -9999 
    for i in range(0, 9):
        if board.board[i] == " ":
            board.board[i] = player
            # Call changePlayer
            moveVal = board.minimax(depth=depth, player=changePlayer(player))
            board.board[i] = " "
            # Minimize or maximize
            if (moveVal < bestScore) == (player == "O"):
                bestScore = moveVal
                bestMove = i
    print("The value of the best Move is :", bestScore)
    print()
    return bestMove

并在主循环中，提供不同的

depth

参数：

ai_move = make_best_move(game, -5, "O")  # Pass -5 for correct play