Сколько времени должно занимать совершенная функция для поиска шахматной позиции на 3 узла глубиной? - PullRequest
Новая
       79

Сколько времени должно занимать совершенная функция для поиска шахматной позиции на 3 узла глубиной?

0 голосов
/ 25 сентября 2019

Я сделал специальную функцию для проверки скорости моего шахматного движка, и эта функция занимает 205 секунд (> 2 минуты), чтобы пройти 3 слоя глубиной и оценить все листья (~ 42 000 листов, потому что 35 ^ 3 = 42 000),Это медлительность должна произойти?Это всего 42 000 узлов, что очень мало.Я надеюсь, что некоторые люди с опытом работы с шахматными двигателями помогут мне понять, что не так.Результат приводит к шахматам: https://www.chessprogramming.org/Perft_Results#Perft_10

Запуск функции perft вообще не предполагает использования минимаксной или альфа-бета-обрезки, поэтому это не может быть причиной медлительности.

Моя функция perft: 

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

...