Очевидно, что попытка применить алгоритм min-max к полному дереву ходов работает только для небольших игр (я прошу прощения у всех любителей шахмат, под словом «маленький» я не подразумеваю «упрощенный»). В типичных пошаговых стратегических играх, где доска часто шире, чем 100 фишек, и все фигуры в одной стороне могут двигаться одновременно, алгоритм min-max неприменим.
Мне было интересно, не может ли быть достаточно хорош частичный алгоритм min-max, который ограничивается N конфигурациями плат на каждой глубине? Используя генетический алгоритм, можно найти ряд конфигураций платы, которые подходят для функции оценки. Надеемся, что эти конфигурации также могут быть полезны для долгосрочных целей.
Я был бы удивлен, если бы об этом не думали раньше и не пытались. Есть это? Как это работает?
источник
Ответы:
Это зависит от механики игры. Игровое дерево min-max может быть неприменимо в целом, но, возможно, оно применимо в некоторых областях. Часто некоторые местоположения на карте являются стратегически важными. Мин-макс может применяться на стратегическом уровне, для которого из этих мест контролировать. На тактическом уровне для квадратов х вокруг каждого стратегического местоположения может использоваться min-max, чтобы решить, как развернуть юниты, чтобы захватить и защитить его.
источник
Это не минимаксный алгоритм, однако ребята, ответственные за ИИ Killzone, выпустили статью, основанную на функциях оценки позиции, которую также использует некоторый шахматный ИИ.
Это очень просто в том, что все, что он делает - выбирает позицию на доске, основываясь на текущих знаниях агента. Таким образом, если у агента мало здоровья, то позиции, расположенные подальше от его врага, получат более высокий балл, так как более желательно быть вне досягаемости противника.
Этот документ можно найти в « Мудрости программирования игр AI 3» и называется «Динамическая оценка тактической позиции».
Черновик документа можно найти в Интернете здесь:
http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf
Надеюсь, это поможет.
источник
Я не думаю, что это было бы достаточно хорошо. Выбор конкретных N конфигураций, сколько и каких, было бы практически невозможно в чем-то таком сложном. Помните, что если в вашей игре есть бесконечные ресурсы или что-то подобное, в ней могут быть круги, в которые можно играть, что делает использование такого ИИ относительно простым.
источник
Я бы предложил, по крайней мере, реализовать min-max с альфа-бета-обрезкой.
Не пытаясь сделать это и решив, что это нецелесообразно (то есть, ужасна производительность), и без дополнительной информации об игровой механике, я не понимаю, почему вы думаете, что min-max неприменим.
Размер платы потенциально является проблемой, но с сокращением, отбрасывание потерянных путей дает возможность более глубокого поиска с тем же количеством вычислений, так что, возможно, большие области платы не будут проблемой при сокращении? Кроме того, если предположить, что размер доски сам по себе является проблемой, может быть преждевременным, это не столько размер доски, сколько сложность механики и сколько ходов возможно с каждой позиции доски. Если ваша игра имеет большую, но малонаселенную область, количество возможных ходов от каждого состояния доски может не сильно отличаться от того, если бы доска была достаточно большой, чтобы вместить все фигуры. Конечно, если у вас есть гигантская доска, заполненная на 90%, и каждый ход может двигаться куда угодно, это потребует большого количества поиска.
Я также не уверен, почему одновременное движение по своей сути является проблемой. Пока вы переходите из одного дискретного состояния платы в другое и имеете функцию оценки, алгоритм должен применяться.
Я предполагаю, что в любом случае вам нужна функция оценки, и независимо от того, какой поиск вы используете, функция оценки - это то, куда может пойти большая часть работы. Алгоритм min-max с отсечкой сам по себе очень прост в реализации, что-то, что вы, вероятно, сможете сделать через час или два, и большая часть инфраструктуры работает, например, хранение состояния платы, оценка, генерация перемещений, и, вероятно, будет одинаковой независимо от поиск вы остановитесь на.
источник
Победитель конкурса Google AI 2011 использовал min-max (глубиной 1). Другой топ-участник использовал случайную выборку . Этот участник упомянул, что сочетание минимальной и максимальной случайной выборки, которое, в основном, я описал в своем вопросе, работает плохо. Это решает это, я думаю.
С другой стороны, он показывает, что можно использовать min-max в больших играх. Кажется, однако, что необходимо было ограничить его небольшими группами муравьев, работа с полным набором всех муравьев, вероятно, была бы слишком медленной. Еще одним интересным наблюдением является то, что глубины 1 было достаточно. Мы (люди) очень хорошо играем в шахматы, и ИИ для этой игры требует гораздо более глубоких деревьев поиска, чтобы быть сложным. Новые более сложные игры не игрались и не изучались так долго, и глупые ИИ могут иметь достаточную развлекательную ценность.
источник
Основная идея шахматного ИИ состоит в том, чтобы составить список всех возможных ходов из текущего оцениваемого лучшего хода, затем оценить их и повторить процесс. Это отбрасывает тех, у кого слишком мало шансов, так как они не будут взяты (или можно предположить, что они не будут взяты, поскольку они не дают преимущества).
Основная идея требует от вас составить список всех возможных ходов и повторить этот процесс для всех этих ходов и т. Д. Это возможно в шахматах (где список вероятных следующих ходов эффективно перечисляем; начальная шахматная доска имеет 20 возможных ходов). ) и до некоторой степени для других вещей, таких как нарды, шашки и решение кубика Рубика.
Если я возьму в качестве примера простую пошаговую игру (Civilization 2), каждый из ваших ребят может перейти к 8 клеткам (или 24) за один ход. Если у вас есть 10 парней (что не так уж много, у вас, как правило, к тому времени, когда это начинает становиться несколько интересным), общее количество возможных «ходов» из текущего состояния (так, одного уровня) уже составляет 8 ^ 10. или около 4 млрд. Даже если вы подрежете 99,99% из них, вы все равно не сможете углубиться в дерево, так как количество возможных ходов взрывается очень быстро.
Добавьте к этому, что игра немного похожа на проблему кубика Рубика, где вы видите прогресс только после 10 или 12 ходов, проблема взрывается до такой степени, что преимущества стандартного минимума / максимума преобладают только при объеме памяти больше, чем ваш типичный компьютер будет иметь.
Другими словами, найденные стратегии будут воспроизводимыми, но плохими.
Для реальной проблемы, как сделать приличный ИИ, я бы пошел в направлении случайного движения в основном управляемым (двигайте каждого парня с небольшим количеством основного интеллекта), оценки и настройки. Сделайте это параллельно для 100 или 1000 разных и выберите тот, который окажется лучшим. Вы можете отправить результаты из этого в оригинальное интеллектуальное рулевое управление, чтобы настроить его снова. Немного похоже на симуляцию Монте-Карло.
источник
Чтобы успешно применить мин / макс в пошаговой стратегии, вам нужно правильно применить все доступные шахматные приемы ...
Функция оценки
Даже шахматные движки имеют очень плохую силу, если ваши функции оценки плохие. Наиболее простая версия функции оценки: 1 = игра, выигранная белым, -1 = игра, выигранная черным, 0 = все остальные случаи; Но это даст вам очень плохую производительность. То же самое происходит с вашей пошаговой игрой! Если вы хотите использовать мин / макс (с альфа / бета-обрезкой и прочим), как в шахматах, вы также должны реализовать разумную функцию оценки! Иначе, вы не можете сравнить производительность этих алгоритмов применительно к вашей стратегии и к случаю, когда она применяется к шахматам.
Что оценивают функции шахматных движков, так это оценивают такие вещи, как:
Те части функции оценки должны быть сначала «переведены» в вашу игру:
Различные рейтинги должны суммироваться с помощью весовой функции (factor_a * rating_a + factor_b * ranting_b + ...) для всех единиц ...
В стратегических играх также должны учитываться оставшиеся ресурсы (золото, дерево, ...).
Если ваша функция оценки достаточно хороша, вам не нужно действительно искать «глубоко» в дереве в большинстве случаев. Таким образом, вам, вероятно, нужно только присмотреться к 3 или 10 наиболее перспективным вариантам. Смотрите следующую главу ...
Возможные ходы в каждой позиции
Наиболее проблемная вещь в использовании мин / макс для стратегических игр состоит в том, что вы можете командовать несколькими юнитами за один ход, тогда как в шахматах вам разрешено командовать только одним юнитом (за исключением рокировки, но это четко определенная комбинация ходов). Это вызывает 5 ^ N возможных ходов для N юнитов для каждой «позиции» (шахматный термин), если вы решите только «двигаться на север, юг, запад, восток ИЛИ остановиться» для каждого юнита. Вы можете решить эту проблему, разбив сложную команду на команды низкого уровня: например, выберите действие для блока A, углубитесь и выберите блок B .... выберите блок N ... и затем завершите этот ход. Но одно это не меняет сложности! Вы должны оптимизировать порядок, в котором действия назначаются единицам (например, первая единица B, C, D, а затем единица A). Вы можете записать влияние решения для каждой единицы во время последнего расчета, а затем отсортировать по важности. Таким образом, альфа-бета-обрезка может быть использована для раннего удаления любой плохой комбинации из дерева поиска. Наивысшим приоритетом всегда должно быть «ничего не делать и закончить свой ход» (обрезка нулевого хода) в каждой итерации. Таким образом, вы можете «пропустить» назначение большинства задач большинству юнитов и позволить им просто продолжить то, что они делали раньше. Таким образом, поиск быстро углубится в глубину, просто взглянув на «критические» юниты (например, те, которые действительно сейчас находятся в бою). Обязательно командуйте каждым юнитом только один раз ... Вы также можете использовать некоторую случайность, чтобы убедиться, что «важные» юниты тоже время от времени получают команду. Особенно, единицы, заканчивающие некоторую работу (например,
Итеративное углубление + кеширование / хеш-таблица
Затем вы можете «углубляться друг в друга», чтобы углубляться в глубины, пока не будет достигнут некоторый срок. Так что вы будете искать глубже, если будет меньше единиц, и у вас всегда будет какой-то «результат», если вы перестанете искать лучшее решение. Итеративное углубление потребовало бы использования хеш-таблицы для кэширования прежних результатов поиска. Это также позволяет повторно использовать некоторые результаты поиска последних ходов (ветвь дерева поиска, которая охватывает команды, которые были фактически выполнены в последнем ходу). Чтобы реализовать это, вам нужна очень хорошая функция хеширования (взгляните на «ключ zobrist»), которую можно многократно обновлять. Обновление хеш-ключа означает, что вы можете просто взять хеш-ключ старой «позиции» и просто нажать на изменение позиции (например, уберите устройство в положение x и поместите его в положение y). Таким образом, вычисление ключа хеша происходит быстро, и вам не нужно обрабатывать всю ситуацию с досками, чтобы вычислить ее, просто чтобы проверить, содержит ли хэш прежнюю запись для этой позиции. В некотором смысле вы должны убедиться, что коллизии хэшей не происходят.
Недетерминированное поведение
Недетерминированное поведение является проблемой для минимального / максимального поиска. Это означает, что вы не уверены, попадете ли вы в атакуемую цель (например, вероятность составляет 10%). Тогда вы не можете просто планировать, что это произойдет. В этом случае вам нужно изменить алгоритм и поместить «вероятностный» слой между ними. Это немного похоже на «поворот вероятностей». Каждый независимый результат должен рассматриваться отдельно. Оценка через этот глубинный «слой» должна быть затем отобрана (выборка Монте-Карло), и результат углубленной оценки должен быть взвешен вероятностью возникновения. Разные результаты слоя вероятности должны рассматриваться как разные ходы противника (но вместо min / max следует вычислять «среднее»). Это, конечно, увеличит сложность дерева поиска.
Резюме
Применяя все эти приемы (которые все используются нынешними шахматными движками) в детерминированной игре, вы наверняка сможете достичь разумных результатов и для игры. Для недетерминированных игр это, вероятно, будет более сложным, но я думаю, что все еще управляемым.
Хороший ресурс для объяснения этих методов (для шахмат) - http://chessprogramming.wikispaces.com/
Вы даже можете реализовать какую-то направленную случайность в поисках мин / макс. Вместо детерминистского исследования лучших результатов сначала в каждой итерации, вы можете просто рандомизировать это и позволить его порядку определяться распределением вероятностей, основанным на текущих оценках ...
источник