用alpha-beta剪枝PYTHON实现minimax算法的迭代深化

Question

我用alpha-beta剪枝实现了一个NegaMax算法（它只是minimax算法的一个较短版本）。现在我想实现迭代深化，这样我就可以为每个深度找到一个最佳的移动，然后根据前面层的分数对树下的节点重新排序，这样我的alphabeta修剪工作就更有效了

以下是我迄今为止所做的工作：

InitialDEPTH = 1

def findBestMove(gs, validMoves):
    global nextMove
    global InitialDEPTH 
    nextMove = None
    
    for d in range(2):
        CurrentDEPTH = InitialDEPTH + d
        findMoveNegaMaxAlphaBeta(gs, validMoves, CurrentDEPTH, -CHECKMATE, CHECKMATE, 1 if gs.whiteToMove else -1)
    
    return nextMove    

在这里，gs是随着everymove而改变的游戏状态，它包含了关于该游戏的所有信息，比如是否可以使用Castle或者是否可以使用enpassant移动。我的negamax算法如下所示：

def findMoveNegaMaxAlphaBeta(gs, validMoves, depth, alpha, beta, turnMultiplier):
    global nextMove
    if depth == 0 :
       return turnMultiplier * scoreBoard(gs)    

    maxScore = -CHECKMATE

    # I have a felling i need to add some code here to make it work
    for move in validMoves :
        gs.makeMove(move)
        nextMoves = gs.getValidMoves()
        score = -findMoveNegaMaxAlphaBeta(gs, nextMoves, depth - 1 , -beta, -alpha, -turnMultiplier)
        if score > maxScore:
            maxScore = score
            if depth == DEPTH :
                nextMove = move
        gs.undoMove() 
        if maxScore > alpha:   # This is were pruning happens
            alpha = maxScore
        if alpha >= beta :
            break    

    return maxScore   

如何将时间约束函数添加到此代码中，使其仅在所述时间结束时返回最佳移动，而不是在此之前

另外，我如何在每个深度之后重新排序节点，以便在下一个深度中进行有效的修剪。我已经为此编写了一些函数，但我不知道如何实现它。我写的函数：

def sorting(move):
    gs.makeMove(move)
    score = scoreBoard(gs)
    gs.undoMove()

    return turnMultiplier * score
validMoves.sort(key = sorting)
    

Answer 1

在我看来，您有两个问题，我将尝试回答：

1. 如何将时间约束函数添加到此代码中，使其仅在所述时间结束时返回最佳移动，而不是在此之前

所以你想在每次移动中搜索特定的秒数，而不是搜索特定的深度？这很容易实现，您所要做的就是将迭代深化到某个较大的深度，然后将当前时间与每个x个节点的搜索开始时间进行比较。大概是这样的：

import time

start_time = time.time()
move_time = 5  # 5 seconds per move
for depth in range(100):
    ...
    score, move = negamax()
    
    # Only save move if you haven't aborted the search at current depth due to time out.
    if move:
        best_score, best_move = score, move

def negamax():
    if time.time() - start_time > move_time:
        return None, None


    ....
    return score, move

1. 另外，我如何在每个深度之后重新排序节点，以便在下一个深度中进行有效的修剪

我不知道你现在的分类是怎么做的。以下是negamax框架通常的外观：

def negamax():
    if depth = 0:
        return evaluation()

    valid_moves = gs.get_valid_moves()

    # Here you sort the moves
    sorted_valid_moves = sort(valid_moves)

    for move in sorted_valid_moves():
        gs.make_move()
        score = -negamax(...)
        gs.unmake_move()

您可以根据几个标准对移动进行排序，您可以阅读更多关于如何实现每个标准的信息here