Стратегии для игр с неполной информацией

Ответ 1

Я хотел бы внести некоторую конкретную информацию для карточной игры Doppelkopf, которую автор попросил пример. В 2012 году была написана магистерская работа Sievers, где он принял UCT для игры Doppelkopf.

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

После решения этого вопроса он попробовал два способа выполнить алгоритм с его решением проблемы с назначением карты:

1) Угадайте назначение карты для каждого дерева UCT и посмотрите на среднее количество нескольких деревьев. Он называет этот стратегический ансамбль UCT.

2) Возьмите одно дерево uct и угадайте для каждого развертывания новое задание. На этапе выбора UCT вы просто игнорируете всех непоследовательных детей. Он называет эту стратегию единым UCT.

Я чувствую, что 2) делает более сильный ИИ, но он казался более слабым, что он более четко указал на последующую конференцию с 2015 года.

Вдохновленный успехом AlphaGo, я начал проект с другом для его бакалавриата, и он сделал политическую нейронную сеть, используя основанную на символах LSTM для управления процессом выбора алгоритма UCT. Его диплом бакалавра охватывает только некоторые результаты тестов для ансамбля-UCT, но я уже тестировал его для одного игрока UCT, и он делает намного более сильный ИИ. Я предполагаю, что это связано с тем, что единственный игрок UCT намного больше выигрывает от более эффективного сокращения пространства поиска.

Итак, этот ответ более или менее тот же, что и @charley, но немного более конкретный.

Ответ 2

Я думаю, что Expectimax обычно используется для этих типов проблем. Стратегия состоит в том, чтобы свести к минимуму наихудшее ожидаемое значение оценки противника.

Ответ 3

Вы могли бы попытаться внедрить схему Reinforcement Learning. Ему нужно много математики, но это приятно использовать.

Изменить: Вот ссылка на отличный ресурс в RL.

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

Edit2: Вкратце, RL позволяет вашему агенту учиться на его опыте, точно так же, как мы, люди, учимся. Мы горим один раз - мы избегаем прикосновения к огню. Мы получаем вознаграждение после того, как что-то делаем - мы продолжаем делать это ради большего вознаграждения. То же самое относится к агентам, использующим RL.

Ответ 4

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

"Экспертная система" пример "неполной информации" будет: мне нужен новый автомобиль. Вселенная начинается со всех "известных" автомобилей или, возможно, с помощью динамического (возможно, случайного) набора "возможных" автомобилей (например, разных функций/моделей, разных производителей, разных возможностей и т.д.). Тогда система может задать мне вопросы, например:

ВОПРОС: Что самое главное?

• грузоподъемность
• пробег газа
• цена
• Я не знаю

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

Как это применимо специально к движку игры, вы должны создать "вселенную возможностей", например, коридоры, которые вы могли бы спуститься, плитки на доске, все возможные направления ориентации, всевозможное "оружие", которое можно было использовать, каждый возможные "вражеские лица" или "вражеские группы" и т.д.

Затем, основываясь на динамике игры, ваша работа ТОЛЬКО для:

• Основываясь на правилах/контексте/пользовательском вводе, удалите нежизнеспособные параметры.
• В соответствии с правилами/контекстом/пользовательским вводом наиболее предпочтительными параметрами SORT/RANK.
• Элемент в верхней части списка выбран или используется в игре RIGHT NOW.

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

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

И эта игра "dyanmic" и "бесконечно бегающая" - это прежде, чем вы добавите стохастический компонент, который есть в некоторых играх. Игры, такие как Minefield и Battleship и Stratego, в основном не меняются во время игры, поэтому ваши "ответы на локализованные и временные расхождения" могут быть достаточными для (очень) долгоиграющей игры. Тем не менее, если вы произвольно генерируете новых врагов или врагов передвигаетесь, или есть какой-то другой случайный компонент для "настройки платы" (например, океанские приливы, где некоторые пути доступны только иногда), то это добавляет совершенно новый уровень сложности.

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

Ответ 5

Я не знаю общих стратегий, но я реализовал игру со скрытыми ходами и достойным AI.

ИИ попытался выяснить, к чему стремился человек, глядя на все возможные цели атаки и выясняя, на какую цель двигались движения. ИИ попытается укрепить, если это возможно, или эвакуироваться, если он не сможет ожидать.

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

Было достаточно сложно, большинство людей, которых я подарил, не смогли победить его на паритете.