python-3.x - perft 函数搜索 3 个节点深度的国际象棋位置需要多长时间？

Question

我创建了一个 perft 函数来测试我的国际象棋引擎的速度，该函数需要 205 秒（>2 分钟）才能深入 3 层并评估所有叶子（~42,000 个叶子，因为 35^3 = 42,000 个）。这种缓慢应该发生吗？它只有 42,000 个节点，非常少。我希望一些具有国际象棋引擎经验的人可以帮助我找出问题所在。国际象棋中的性能结果：https ://www.chessprogramming.org/Perft_Results#Perft_10

perft 函数的运行根本不涉及使用 minimax 或 alpha-beta 修剪，因此它不可能是导致缓慢的那些。

我的完美功能：

a = GameState()

def perft(game_state, nodes, counter):
    if nodes == 0:
        return 1
    internal_count = 0
    if game_state.player_turn == 'w':
        for piece in game_state.w_pieces:
            # I call .copy() after game_state because I don't want the set holding the pieces in 
            # game_state to change when I call all_possible_moves() on it. .copy() in GameState 
            # calls deepcopy on the internal sets and dicts in game_state. Every piece in the 
            # game_state set has a method called .all_possible_moves(GameState) that 
            # generates all the possible moves for that piece. 
            for move in piece.all_possible_moves(game_state.copy()):
                counter += perft(game_state.copy().make_move(piece.coor, move), nodes - 1, 0)
    else:
        for piece in game_state.b_pieces:
            for move in piece.all_possible_moves(game_state.copy()):
                counter += perft(game_state.copy().make_move(piece.coor, move), nodes - 1, 0)
    return counter

counter = perft(a, 3, 0)
print(counter)

我的 perft 函数应该没有什么明显的问题，对吧？我不知道为什么它会运行这么长时间。我预计找到 42,000 个节点需要不到一秒钟的时间，但正如您在此处看到的那样花费了 2 多分钟：https ://imgur.com/Tas05CJ

对于那些想查看我的完整代码的人，这里是：https ://repl.it/@kasparov/WarmHightechKeygen-1

标签： python-3.xperformancechessminimaxalpha-beta-pruning