Как выбрать лучший алгоритм для настольной игры, такой как шашки?

15

Как выбрать лучший алгоритм для настольной игры, такой как шашки?

До сих пор я рассмотрел только три алгоритма, а именно минимакс, альфа-бета-обрезку и поиск по дереву Монте-Карло (MCTS). По-видимому, и альфа-бета-обрезка, и MCTS являются расширениями базового минимаксного алгоритма.

детеныш
источник

Ответы:

17

ТЛ; др:

  • Ни один из этих алгоритмов не является практичным для современной работы, но они - хорошие места, чтобы начать педагогически.

  • Вы всегда должны предпочитать использовать альфа-бета-обрезку вместо минимаксного поиска.

  • Вы должны предпочесть использовать некоторую форму эвристического управляемого поиска, если вы можете придумать полезную эвристику. Придумывание полезной эвристики обычно требует большого знания предметной области.

  • Вы должны предпочесть использовать поиск по дереву Монте-Карло, когда вам не хватает хорошей эвристики, когда вычислительные ресурсы ограничены, и когда ошибки не будут иметь больших реальных последствий.

Больше деталей:

В минимаксном поиске мы не пытаемся быть очень умными. Мы просто используем стандартный подход динамического программирования. Легко определить значение разностных ходов, если мы приближаемся к концу игры (поскольку игра закончится следующим ходом, нам не нужно смотреть далеко вперед). Точно так же, если мы знаем, что будет делать наш оппонент на последнем ходу игры, легко понять, что нам следует делать на втором последнем ходу. Фактически мы можем рассматривать второй последний ход как последний ход более короткой игры. Затем мы можем повторить этот процесс. Использование этого подхода, несомненно, позволит раскрыть лучшие стратегии в стандартной игре в расширенной форме, но потребует от нас рассмотреть каждый возможный ход, который невозможен для всех, кроме самых простых игр.

Альфа-бета-обрезка - это строгое улучшение поиска минимакса. Он использует тот факт, что некоторые движения явно хуже, чем другие. Например, в шахматах мне не нужно рассматривать ход, который дал бы вам возможность поставить меня в мат, даже если бы вы могли делать другие вещи с этой позиции. Как только я увижу, что движение может привести к проигрышу, я не буду думать о том, что еще может произойти с этой точки. Я пойду смотреть на другие вещи. Этот алгоритм также наверняка даст правильный результат, и он быстрее, но все же должен учитывать большинство ходов на практике.

Существует два распространенных способа, позволяющих обойти огромную вычислительную стоимость решения таких игр:

  1. Используйте эвристику (поиск * является обычным алгоритмом в педагогических целях, но поиск покоя - аналогичная идея в играх с двумя игроками). Это просто функция, которая дает оценку значения состояния игры. Вместо того, чтобы рассматривать все ходы в игре, вы можете просто рассмотреть ходы на некоторое конечное расстояние впереди, а затем использовать значение эвристики для оценки значения состояний, которые вы достигли. Если ваша эвристика непротиворечива (по существу: если она всегда переоценивает качество состояний), то это все равно даст правильный ответ, но с огромными ускорениями на практике.

  2. Используйте Rollouts (например, поиск по дереву Монте-Карло). По сути, вместо рассмотрения каждого хода, запустите несколько тысяч смоделированных игр между игроками, действующими случайным образом (это быстрее, чем рассмотрение всех возможных ходов). Присвойте значения состояниям, равным среднему коэффициенту выигрыша в играх, начиная с него. Это может не дать правильный ответ, но в некоторых играх он работает надежно. Он часто используется как расширение более точных методов, а не используется сам по себе.

Джон Дусетт
источник
A * действительно не вписывается в контекст игр для двух игроков, как другие алгоритмы? Примечание по MCTS: типичные реализации не "учитывают все перемещения вниз до некоторой фиксированной глубины", а затем начинают развертывание; вместо этого, типичные реализации динамически, постепенно наращивают дерево поиска, увеличивая его в более многообещающие части (части, на которые ориентированы многие стратегии развертывания), уменьшая его в менее многообещающих частях.
Деннис Соемерс
1
@JohnDoucette, почему бы вам сказать: «Ни один из этих алгоритмов не является практичным для современной работы, но они являются хорошими местами для педагогического начала». В случае MCTS это кажется очень подходящим для современной работы, даже для поиска в одиночной игре, когда переход к следующему состоянию, заданному состоянию и действию, четко определен. Вы бы согласились?
Мигель Сарайва
1
@MiguelSaraiva Сам по себе MCTS - это не то, что вы обычно используете для современного приложения. В сочетании с чем-то вроде DNN обеспечить хорошо изученную эвристику было бы неплохо.
Джон Дусетт
1
@JohnDoucette "MCTS - это не то, что вы обычно используете для современного приложения". Прежде всего, «современность», на которую вы ссылаетесь, имела большой прорыв в 2016 году (MCTS + DNN), и кажется, что вы намекаете, что все до этого устарело (очевидно, ложно). На самом деле, было бы даже более правдоподобно сказать, что MCTS обычно не используется из-за обратного: он слишком продвинут: в промышленности есть куча приложений, которые действительно устарели и могут быть обновлены до MCTS. Для многих из этих MCTS + DNN это просто мечта, так как предварительное обучение немыслимо.
Йохан
1
@Johan Это звучит хорошо для промышленного применения , но вопрос задается о «настольной игре, такой как шашки». Я думаю, что для такого рода игрушечных задач MCTS не является подходящим современным подходом. Безусловно, существует множество реальных проблем, которые значительно улучшат существующие развернутые системы.
Джон Дусетт
7

NB. Причина, по которой я выбрал только эти три алгоритма, была вызвана временем, которое у меня было для их понимания. Из небольшого исследования я обнаружил, что эти алгоритмы в основном вплетены в минимаксный алгоритм. Так что, если я смогу понять одно, то два других просто встанут на свои места.

Учитывая этот контекст, я бы рекомендовал начать с Minimax . Minimax - это самый простой для понимания алгоритм из трех.

Альфа-бета , как уже упоминалось в других ответах, - это строгое улучшение по сравнению с минимаксом. Minimax - это, по сути, часть реализации Alpha-Beta, и хорошее понимание Alpha-Beta в любом случае требует начинать с хорошего понимания Minimax. Если у вас есть время, оставшееся после понимания и внедрения Minimax, я бы порекомендовал перейти к Alpha-Beta и построить его поверх Minimax. Начинать с Альфа-беты, если вы еще не понимаете, минимакс не имеет смысла.

Поиск по дереву Монте-Карло , вероятно, немного сложнее и сложнее для понимания. В последнее десятилетие MCTS действительно стала более популярной, чем две другие, поэтому с этой точки зрения понимание MCTS может быть более «полезным».

Связь между Minimax и MCTS менее прямая / очевидная, чем связь между Minimax и Alpha-Beta, но все же существует связь, по крайней мере, на концептуальном уровне. Я бы сказал, что иметь хорошее представление о Minimax сначала полезно до погружения в MCTS ; в частности, понимание Minimax и его недостатков / слабых мест может предоставить полезный контекст / помочь вам понять, почему MCTS стала «необходимой» / популярной.


В заключение, на мой взгляд:

  • Альфа-бета строго лучше, чем Минимакс, но также сильно связана / построена поверх Минимакса; Итак, начните с Minimax, затем перейдите к альфа-бете, если позволит время
  • MCTS имеет различные сильные и слабые стороны, часто лучше, чем Alpha-Beta в «современных» задачах (но не всегда), хорошее понимание Minimax, вероятно, будет полезно, прежде чем начать погружаться в MCTS
Деннис Соемерс
источник
Есть ли другой алгоритм, который вы могли бы предложить, чтобы я мог также использовать? Это как уровень обрезки альфа-бета
Джои
@ Джо Хм, нет, не совсем. Минимакс - очень естественная отправная точка, я очень рекомендую, если вы только начинаете. Это был в основном первый алгоритм, разработанный для таких игр, как шахматы / шашки / крестики-нолики / что угодно. После этого были разработаны сотни, если не тысячи улучшений, многие из которых вы, вероятно, можете найти по адресу chessprogramming.wikispaces.com/Search . Альфа-бета является наиболее естественным дополнением к минимаксам.
Деннис Соемерс
@Joey Monte-Carlo Tree Search немного отличается (не обязательно использует Minimax в качестве основы), интересен, весел, популярен и очень актуален в «современном» AI. Тем не менее, основы важны, я не рекомендовал бы начинать с MCTS немедленно, если вы еще не понимаете Minimax + Alpha-Beta, даже если это технически возможно.
Деннис Соемерс
Спасибо за этот сайт. Это богатство знаний, которые я теперь могу прочитать. Самое сложное в изучении новых вещей - найти правильный материал, который поможет вам понять. Так что еще раз спасибо за сайт
Джои
@Joey Я не уверен на 100%, является ли шахматное программирование самым простым сайтом для изучения (и наверху, кажется, страшное уведомление о том, что сайт может исчезнуть в конце июля). Если я правильно помню, многие описания довольно короткие /, вероятно, не легко понять, если вы новичок в этой области. Это будет, по крайней мере, хорошая, всеобъемлющая коллекция имен всех видов алгоритмов / улучшений, и вы можете попробовать поискать исходные источники или Google все эти имена для получения более подробной информации в другом месте.
Деннис Соемерс
1

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

Kaizokun
источник