用极大极小优化象棋引擎

Question

我用python开发了一个使用minimax算法的国际象棋引擎，我还使用了Alpha-Beta剪枝对其进行进一步优化。目前我搜索的深度为4，虽然不是很多，但仍然需要10-60秒来考虑移动

减慢程序速度的主要原因是一次又一次的迭代。我首先在deque.collection()中生成所有可能的移动，然后遍历它一次以验证它。现在，我再次对其进行迭代以评估移动，然后比较它们以获得最佳移动。我在整个过程中使用for循环，所有可能移动的格式都是集合（移动）的集合（mainmoves）

我可以做些什么来优化这一点，并减少生成移动所需的时间

def minimaxRoot(depth,isMaximizing):
    global board
    possibleMoves = gen(False)
    bestMove = -math.inf
    bestMoveFinal = None
    for move in possibleMoves:
        orig = normperform(move)
        value = max(bestMove, minimax(depth - 1,not isMaximizing,-math.inf,math.inf))
        undo(move,orig)
        if value > bestMove:
            bestMove = value
            bestMoveFinal = move
    return bestMoveFinal

def minimax(depth,ismax,alpha,beta):
    global board
    if depth == 0:
        return calcpoints()
    maxeval = -math.inf
    mineval = math.inf
    if ismax == True:
        mainmoves = gen(False)
        if mainmoves == 'mate':
            return 8000
        for move in mainmoves:
            orig = normperform(move)
            eval = minimax(depth-1,False,alpha,beta)
            undo(move,orig)
            maxeval=max(eval,maxeval)
            alpha = max(alpha,eval)
            if beta <= alpha:
                break
        return maxeval
    elif ismax == False:
        mainmoves2 = gen(True)
        if mainmoves2 == 'mate':
            return 8000
        for move2 in mainmoves2:
            orig2 = normperform(move2)
            eval2 = minimax(depth-1,True,alpha,beta)
            undo(move2,orig2)
            mineval = min(mineval,eval2)
            if eval2 < beta:
                beta = eval2
            if beta <= alpha:
                break
        return mineval

Answer 1

有两个主要问题导致您的国际象棋引擎搜索深度较低：

1. 首先，您没有执行移动排序。搜索完成所需的时间在很大程度上取决于它访问的节点。我建议您在每次搜索迭代中计算引擎访问的节点数。理想情况下，你不应该一次计算所有的移动，或者至少搜索那些有可能首先成为最佳移动的移动（例如捕获）。这样你就可以增加早期测试的机会。移动顺序对于搜索算法至关重要。您可以阅读有关移动排序here的更多信息
2. Python不是实现高性能国际象棋引擎的最佳语言。您最好使用像C或C++这样的编译语言。虽然Python中有一个名为Sunfish的引擎，但我认为它的ELO强度大约为2000