python - 在我的代码中实现 Alpha Pruning 的最佳方法是什么？

Question

我目前正在通过井字游戏学习 Mini Max 和 AlphaBetaPruning。我能够实现和理解 Mini max，但不确定如何将 alpha-beta 修剪与我当前的代码结合起来。我必须完全重新启动吗？或编写另一个项目？

此外，我熟悉 Alpha-beta 只是基于使用树搜索最佳结果的 mini max 决策的即兴创作。我

#Referenced: https://www.youtube.com/watch?v=JC1QsLOXp-I
from AlphaBest import *
# board - if player inputs the numbers, it will pos his move on the board there
board = {1: ' ', 2: ' ', 3: ' ',
         4: ' ', 5: ' ', 6: ' ',
         7: ' ', 8: ' ', 9: ' '}


def printBoard(board):
    print(board[1] + ' | ' + board[2] + '| ' + board[3])
    print("--+--+--")
    print(board[4] + ' | ' + board[5] + '| ' + board[6])
    print("--+--+--")
    print(board[7] + ' | ' + board[8] + '| ' + board[9])
    print("--+--+--")
    print("\n")


def spaceIsFree(position):
    # if board space is ' '  then it is empty
    if board[position] == ' ':
        return True
    else:
        return False

def positionsAvaliable(board):
    for key in board.keys():
        if (board[key] == ' '):
            return key
    return False

# here we insert a letter at a give position
def insertLetter(letter, position):
    # if the space is free, then we insert the letter at position
    if spaceIsFree(position):
        board[position] = letter
        printBoard(board)

        # determine if there is a draw in the game
        if checkDraw():
            print("It's a draw!")
            exit()

        # determine if there is a winner
        if checkForWin():
            if letter == 'X':
                print("Bot wins.")
                exit()
            else:
                print("player wins")
                exit()
        return

    else:
        print("Can't insert letter there")
        position = int(input("Enter a new position: "))
        insertLetter(letter, position)
        return


def checkForWin():
    # check for all possibilities to determine if the player/bot won
    if (board[1] == board[2] and board[1] == board[3] and board[1] != ' '):
        return True
    elif (board[4] == board[5] and board[4] == board[6] and board[4] != ' '):
        return True
    elif (board[7] == board[8] and board[7] == board[9] and board[7] != ' '):
        return True
    elif (board[1] == board[4] and board[1] == board[7] and board[1] != ' '):
        return True
    elif (board[2] == board[5] and board[2] == board[8] and board[2] != ' '):
        return True
    elif (board[3] == board[6] and board[3] == board[9] and board[3] != ' '):
        return True
    elif (board[1] == board[5] and board[1] == board[9] and board[1] != ' '):
        return True
    elif (board[7] == board[5] and board[7] == board[3] and board[7] != ' '):
        return True
    else:
        return False

# this is what the minimax algorithm uses for it's depth and to check which possibilities it can make
def checkWhichMarkWon(mark):
    if board[1] == board[2] and board[1] == board[3] and board[1] == mark:
        return True
    elif (board[4] == board[5] and board[4] == board[6] and board[4] == mark):
        return True
    elif (board[7] == board[8] and board[7] == board[9] and board[7] == mark):
        return True
    elif (board[1] == board[4] and board[1] == board[7] and board[1] == mark):
        return True
    elif (board[2] == board[5] and board[2] == board[8] and board[2] == mark):
        return True
    elif (board[3] == board[6] and board[3] == board[9] and board[3] == mark):
        return True
    elif (board[1] == board[5] and board[1] == board[9] and board[1] == mark):
        return True
    elif (board[7] == board[5] and board[7] == board[3] and board[7] == mark):
        return True
    else:
        return False


# this determines if there is a draw by iterating through the keys
# if there are no keys in the board and no winner, then it is a draw
def checkDraw():
    for key in board.keys():
        if (board[key] == ' '):
            return False
    return True


player = '0'
bot = 'X'


def playerMove():
    position = int(input("Enter the position for O: "))
    insertLetter(player, position)
    return


def botMove():
    bestScore = -1000
    bestMove = 0
    for key in board.keys():
        if (board[key] == ' '):
            board[key] = bot
            score = miniMax(board, 0, False)
            board[key] = ' '
            if (score > bestScore):
                bestScore = score
                bestMove = key

    insertLetter(bot, bestMove)
    return

def miniMax(board, depth, isMaximizing):
    # need to find terminal states here
    if checkWhichMarkWon(bot):
        return 100
    elif checkWhichMarkWon(player):
        return -100
    elif checkDraw():
        return 0

    # here the bot plays against itself to find the best score based on it's moves
    if isMaximizing:
        bestScore = -1000

        for key in board.keys():
            if (board[key] == ' '):
                board[key] = bot
                score = miniMax(board, 0, False)
                board[key] = ' '
                if (score > bestScore):
                    bestScore = score

        return bestScore

    else:
        bestScore = 800
        for key in board.keys():
            if (board[key] == ' '):
                board[key] = bot
                score = miniMax(board, 0, False)
                board[key] = ' '
                if (score < bestScore):
                    bestScore = score

        return bestScore


while not checkForWin():
    botMove()
    playerMove()

标签： pythontic-tac-toeminimaxheuristicsalpha-beta-pruning

Answer 1

切换到 alpha-beta 算法时，无需更改太多内容。

该算法添加了两个参数，alpha 和 beta，以及一些处理这些变量的行。

您可以直接将维基百科伪代码更新为您的代码。

您的代码存在一些错误：

1. 你miniMax每次都想用更少的深度跟注。因此写 miniMax(board, depth-1, False)（而不是0作为深度）。此外，在 中，以一定的深度（而不是 0）botMove()调用您。miniMax
2. 此外，您想miniMax与其他玩家通话。因此miniMax(board, depth-1, False)，如果当前玩家正在最大化，并且miniMax(board, depth-1, True)当前玩家正在最小化。