#python #algorithm #minimax
#python #алгоритм #минимакс
Вопрос:
До сих пор я успешно мог использовать минимаксный алгоритм в Python и применять его к игре в крестики-нолики. Я могу запустить свой алгоритм по всему дереву поиска и вернуть значение.
Однако я не понимаю, как принять это значение и преобразовать его в перемещение? Как я должен знать, какой ход сделать?
Спасибо.
Комментарии:
1. Вы использовали рекурсивный алгоритм? Если это так, в дополнение к возврату конечного значения, вы также можете возвращать соответствующий ход на каждом шаге и получать свой ход, когда закончите со всей распаковкой.
2. Как вам удалось успешно использовать minimax, если вы не понимаете, как использовать значение? Я не понимаю, где именно у вас возникли проблемы.
3. @user189 Да, я использую рекурсивный алгоритм. Спасибо, я попробую это. Однако как программа должна знать, что она находится в конце? Поскольку он рекурсивный, я не думаю, что было бы возвращать ход каждый раз, когда он делает свое дело.
4. @twinlakes На данный момент я могу использовать минимаксный алгоритм для получения эвристического значения текущего узла.
5. Я вижу две возможности. Во-первых, вы возвращаете ход для каждого вызова, и ваш основной вызов автоматически получит следующий ход. Во-вторых, вы используете дополнительный параметр (скажем, «isFirst»), если isFirst затем установите isFirst в False и возвращаете ход.
Ответ №1:
Концептуализируйте минимаксный алгоритм как граф, где каждая вершина представляет собой возможную конфигурацию доски, а каждое ребро от вершины к ее соседу представляет собой переход / переход от одной конфигурации доски к следующей.
Вам нужно посмотреть на эвристическое значение каждого состояния платы, соседнего с вашим текущим состоянием, затем выбрать состояние с наилучшим эвристическим значением, затем обновить экран, чтобы показать это состояние платы.
Если вы выполняете анимацию / переходы между состояниями доски, вам нужно будет посмотреть на ребро и выяснить, какая часть отличается между двумя состояниями, и соответствующим образом анимировать эту часть.
Ответ №2:
При использовании алгоритма MM у вас должен был быть способ генерировать возможные платы-преемники; каждая из них была результатом перемещения. Как было предложено, вы можете изменить свой алгоритм, чтобы включить отслеживание хода, который использовался для создания доски (например, добавив его в определение доски или используя структуру, в которой есть доска и ход); или у вас может быть особый случай для верхней частиуровень алгоритма, поскольку это единственный, в котором важен конкретный ход.
Например, если ваша функция в настоящее время возвращает только вычисленное значение переданной доски, она может вместо этого вернуть dict (или кортеж, что не так понятно) как со значением, так и с первым ходом, использованным для получения этого значения, а затем изменить ваш код, чтобы использовать тот бит, который необходим.
Комментарии:
1. Именно с этим отслеживанием у меня возникают проблемы. Например, если я попытаюсь вернуть плату, это испортит мой алгоритм из-за рекурсии минимаксов. Я боюсь, что если я попытаюсь сделать особый случай только для верхнего уровня, это не позволит программе выполнять поиск. Как я могу реализовать этот вид отслеживания в псевдокоде?
Ответ №3:
Самый простой способ выбрать свой ход — это выбрать ход с максимальным количеством выигрышных позиций, вытекающих из этого хода.
Я бы для каждого узла в вашем дереве поиска (состояние игры) вел учет возможных состояний выигрыша, которые могут быть созданы текущим состоянием игры.