Медленный шахматный бот, нужно идти быстрее

Я создал шахматного бота, используя минимаксную и альфа-бета-обрезку, а также создал графический интерфейс. Но мой бот не может идти очень глубоко, пока не станет очень медленным. Уже на глубине 4 на поиск хода может уйти до 40-50 секунд.

Алгоритм выглядит так:

def minimax(depth,board, alpha, beta, is_max):
    if depth == 0:
        return evaluation(board)
    leg_moves = board.legal_moves
    if is_max:
        value = -9999
        for i_move in leg_moves:
            move = chess.Move.from_uci(str(i_move))
            board.push(move)
            value = max(value, minimax(depth - 1, board, alpha, beta, False))
            board.pop()
            alpha = max(alpha, value)
            if beta <= alpha:
                return value
        return value
    else:
        value = 9999
        for i_move in leg_moves:
            move = chess.Move.from_uci(str(i_move))
            board.push(move)
            value = min(value, minimax(depth - 1, board, alpha, beta, True))
            board.pop()
            beta = min(beta, value)
            if(beta <= alpha):
                return value
        return value

Подводя итог, как мне сделать это быстрее?


python algorithm chess minimax alpha-beta-pruning
person oscar melin    schedule 03.12.2020    source источник
comment
Вы профилировали свой код? В чем узкое место? В большинстве случаев проблема заключается в медленном алгоритме, а не в медленном коде. Вы пробуете все возможные законные ходы. Шахматные движки AFAIK используют эвристику.   -  person Thomas Sablik    schedule 03.12.2020
comment
Еще один важный фактор заключается в том, что можно достичь одной и той же позиции несколькими последовательностями ходов, поэтому кэширование анализа позиций полезно.   -  person Karl Knechtel    schedule 03.12.2020

Ответы (2)


arrow_upward
2
arrow_downward

Реализация функции Negamax вместо Minimax значительно упростит будущие реализации эффективности, а также сделает код чище:

def negamax(depth, board, alpha, beta, color):
    if depth == 0:
        return evaluation(board)
    leg_moves = board.legal_moves
    for i_move in leg_moves:
        move = chess.Move.from_uci(str(i_move))
        board.push(move)
        value = -negamax(depth - 1, board, -beta, -alpha, -color)
        board.pop()
        alpha = max(alpha, value)
        if beta <= alpha:
            return value
     return value

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

Вы, вероятно, также захотите посмотреть на генерацию ходов и посмотреть, сможете ли вы сделать это быстрее. Например, какое представление на доске вы используете?

Я сделал шахматный движок на Python, который совсем не на высшем уровне. Он достигает глубины 6 примерно за 15 секунд, и вы можете найти код здесь для вдохновения: Affinity Chess. Он использует представление одномерной доски, но представление битовой доски было бы еще быстрее.

Я также настоятельно рекомендую заглянуть на www.chessprogramming.org, там много полезной информации.

person Eli    schedule 15.12.2020
comment
Спасибо за этот ответ. Я реализовал это, а также исправил функцию оценки. Теперь бот может пройти на 1 глубину дальше. Спасибо :) - person oscar melin; 11.02.2021

arrow_upward
0
arrow_downward

Есть много факторов, которые делают алгоритм быстрым, добавляя больше стандартных функций шахматных программ. Но всего 4 хода и столько времени - это ненормально с вашим исходным кодом. Как вы генерируете ходы? Вы не должны запрашивать их через протокол UCI, вместо этого постарайтесь сгенерировать их очень быстро. В частности, не ищите фигуры на доске, вместо этого организуйте их позиции в списке и добавляйте/удаляйте их, если они взяты с доски.

Возможно, ваша функция оценки работает медленно. Если вы заботитесь только о значениях частей, тогда у вас есть переменная, которая будет хранить разницу цветов и обновлять ее только в том случае, если часть взята или восстановлена. Таким образом, оценка почти не требует времени.

В java-программе я достигаю глубины 7 за 4 секунды, реализуя эти детали без использования таких методов, как хеш-таблицы.

person TheSlater    schedule 03.12.2020