Как найти оптимальный узел при использовании минимакса с альфа-бета-отсечкой - PullRequest
Новая
       69

Как найти оптимальный узел при использовании минимакса с альфа-бета-отсечкой

0 голосов
/ 13 февраля 2020

Я пытаюсь создать шахматный движок, основная идея c заключается в том, что когда я нажимаю кнопку, компьютер делает ход. Вот мой код: 

def alphabeta(board, node, depth, a, b, maximizer):
    if depth == 0:
        return evaluate.node(node)

    if maximizer == True:
        value = -10**3 # Number that's smaller than what the evaluation algorithm can return
        for child in board.get_all_nodes(node):
            m = alphabeta(board, child, depth-1, a, b, False)
            value = max(value, m)
            a = max(a, value)
            if a >= b:
                break
        return value
    else:
        value = 10**3 # Number that's bigger than what the evaluation algorithm can return
        for child in board.get_all_nodes(node):
            m = alphabeta(board, child, depth - 1, a, b, True)
            value = min(value, m)
            b = min(b, value)
            if a >= b:
                break
        return value

Проблема в том, что этот код возвращает оценку наилучшего возможного хода вместо самого дерева ходов. Как мне найти лучший ход без повторного запуска всей функции?

1 Ответ

0 голосов
/ 01 марта 2020

Есть два способа справиться с этим:

  1. Создать другую функцию getbestmove, которая выглядит как alphabeta, но когда она получает наилучшее значение, она также назначает соответствующую child (переместить) в новую переменную bestnode. И вместо возврата значения он возвращает bestnode. Не позволяйте этой функции вызывать сам по себе рекурсивно, но alphabeta, что касается более глубоких уровней поиска, вам не нужно запоминать лучший ход.

    Вы бы всегда вызывали getbestmove чтобы получить лучший ход, ... больше нет необходимости вызывать alphabeta напрямую, вне getbestmove.

  2. Адаптировать alphabeta, чтобы он возвращал оба значение и соответствующий ход, как кортеж. Когда глубина равна 0, у вас нет движения, поэтому просто позвольте этому лучшему движению быть None. Рекурсивные вызовы должны извлечь первое значение из возвращенного кортежа (часть значения), и самый внешний вызов alphabeta может получить лучший ход из второй части возвращенного кортежа. 

    def alphabeta(board, node, depth, a, b, maximizer):
    if depth == 0:
        return (evaluate.node(node), None) # tuple of value and move

    bestmove = None
    if maximizer == True:
        value = -10**3 # Number that's smaller than what the evaluation algorithm can return
        for child in board.get_all_nodes(node):
            m = alphabeta(board, child, depth-1, a, b, False)[0] # ignore the move part
            value = max(value, m)
            if value > a:
                bestmove = child
                a = value
                if a >= b:
                    break
    else:
        value = 10**3 # Number that's bigger than what the evaluation algorithm can return
        for child in board.get_all_nodes(node):
            m = alphabeta(board, child, depth - 1, a, b, True)[0] # ignore the move part
            value = min(value, m)
            if value < b:
                bestmove = child
                b = value
                if a >= b:
                    break
    return (value, bestmove) # tuple of value and move

    You может даже расширить это, чтобы отслеживать «лучший путь» в дереве поиска.

...