Лучшие приемы для ИИ карточной игры

27

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

  • После раздачи карт игрокам нет случайности. Я имею в виду, что каждый игрок может выбрать, какие карты он играет, но случайный процесс не происходит, как при раздаче карт в начале игры.
  • Существует ограничение на карты, которые можно разыграть, когда карта уже разыграна.
  • Игрок, выигравший трюк, играет первым. Например, игрок 1 разыгрывает карту, игрок 2 разыгрывает карту и выигрывает. Затем игрок 2 играет карту, а затем игрок 1 играет.

Я знаю много подсказок / правил (например, если я знаю, что у игрока есть карты A, B, C, я должен играть в D), что помогает мне выиграть в игре. Поэтому я сначала хотел использовать байесовскую сеть для описания этих правил. Проблема в том, что я не знаю вероятностей для назначения, но я мог бы вычислить эвристику, используя историю сыгранных игр (против человека). Во-вторых, очень вероятно, что я не знаю всех правил и что есть некоторые неявные правила, которые нужны ИИ, чтобы найти оптимальную игру.

Я не уверен, что это был бы хороший способ разработать ИИ для такой карточной игры?

Мне также интересно, есть ли другие методы, которые лучше всего подходят для этой проблемы. Например, я взглянул на минимакс (возможно, с алгоритмом сокращения), но будет ли хорошим вариантом для этой проблемы? Я совершенно не уверен, так как самые важные игры находятся в начале игры, когда есть самые высокие неизвестные параметры (большинство карт еще не разыграно).

LaurentG
источник
1
Отличный вопрос! Не имею полного ответа. Я просто хотел бы добавить свой 2c: если вы знаете все возможные состояния, в которых может находиться ваша игра, то Minimax теоретически был бы хорошим способом пройти через это дерево игровых состояний. Могут возникнуть проблемы с производительностью, если дерево этой игры слишком велико ...
Shivan Dragon
1
Какова цель игры? Кто выигрывает? Может ли игрок приблизить свои шансы на победу в игре в любой момент времени?
Приходите с
Я не могу подробно объяснить игру. Чтобы выиграть, нужно набрать наибольшее количество очков (больше, чем у другого игрока). В начале трудно / невозможно сказать, собираемся ли мы победить. В конце концов, мы можем быть уверены, что выиграть, если у одного уже достаточно очков (другой игрок не может больше набрать достаточно очков, чтобы выиграть).
LaurentG
1
Является ли игра HeartStone? :)
Lescai Ionel
1
Похоже, я нахожусь с вами в такой же ситуации, в том числе в карточной игре, а также в местной (хотя и не в Швейцарии), и я также пытаюсь понять, с чего начать. Одна вещь, которая мне показалась интересной, - это эволюционер, где вы назначаете ДНК виртуальным игрокам, а затем сопоставляете их друг с другом. Вы убиваете неудачников и разводите победителей. Результатом могут быть вполне приличные AI-боты. Я не понял, как адаптировать этот tropiceuro.com/puerto-rico-evolver для моей карточной игры, но я думаю, что это возможно.
Андрей Савиных

Ответы:

11

Ваш пример звучит похоже на Бридж . Лучшие системы для игры в бридж используют методы Монте-Карло для выбора ходов. На высоком уровне:

  • Определите вероятности каждой карты в данной руке. Вы точно знаете, какие карты находятся в вашей руке, а какие были разыграны. Определите вероятность всех других карт на основе сыгранных карт и, возможно, ставки игрока, если в ней участвуют ставки. Для начала вы можете просто использовать наивную и равную вероятность того, что карта окажется в руке какого-то игрока.
  • Теперь запустите столько «виртуальных» игр, сколько сможете. Смоделируйте игру карты со своей руки, а затем определите ответы своих оппонентов, используя правила игры и свои вероятности. Для каждой виртуальной игры используйте свои вероятности, чтобы назначить карты игроку, а затем быстро смоделировать игру. Предположим, что каждый игрок будет играть в меру своих возможностей. Вы знаете все карты в своей виртуальной игре, чтобы каждый игрок мог играть идеально.
  • Когда у вас солидная выборка (или у вас заканчивается время), выберите законный ход, который чаще всего дает вам лучший результат.

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


Изменить за комментарий LaurentG:

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

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

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

Корбин Март
источник
Спасибо за ваш интересный ответ. Вы правы, игра разделяет несколько правил с Бриджем. Как я понимаю, ваш ИИ не будет лучше того, что вы закодировали. Есть ли способ использовать метод Монте-Карло и заставить ИИ учиться? Можно ли назначить вероятности для каждой карты, используя прошлые события (из всех предыдущих игр)?
LaurentG
Вы можете определенно заставить ИИ учиться. Хитрость заключается в том, чтобы отделить вероятности для карты, находящейся в конкретной руке, от вероятности того, что игрок разыграет данную легальную карту, когда она окажется в их руке. Я уточню выше.
Корбин
6

Случай недавнего личного опыта:

Я сам работал над карточной игрой (Bisca, португальская игра для 2 игроков), и я получал хорошие результаты, используя методы Монте-Карло, особенно с использованием недавнего алгоритма поиска информационных множеств Монте-Карло (ISMCTS), описанного с помощью пример исходного кода на Python по адресу http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm ).

Игра неплохо, с неправильным ходом, просто со знанием правил игры. В настоящее время я пытаюсь добиться этого, чтобы иметь возможность улучшить его, так как согласно информации, которую я прочитал об этом (и его "родительском" MCTS), возможно улучшить его игру с помощью эвристики ( http: // www .orangehelicopter.com / ed /apers / aiide13.pdf ) и вывод карты оппонента.

Черный кот
источник
1
этот пост довольно трудно читать (стена текста). Не могли бы вы изменить его в лучшую форму?
комнат
спасибо за ответ от кого-то с реальным опытом по проблеме. отличные ссылки!
Любен
3

Я думаю, это зависит от правил игры.

Вот что я понимаю из вашего вопроса:

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

Предположения:

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

Пример игры, которая следует этим правилам:

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

Теперь эта игра определяется удачей розыгрыша и возможностью запомнить, какие карты были разыграны, чтобы узнать руку противника.
В этой ситуации я бы заставлял ИИ лишь частично запоминать, какие карты были сыграны, то есть случайным образом удалять из запоминаемого списка некоторый процент сыгранных карт (меньшее число = высокий уровень сложности ИИ), но не такие важные, как тузы или короли. Таким образом, например, ИИ будет знать, что безопасно играть в «Королеву сердец», потому что он будет помнить, что у противника нет туза или короля, но ему придется рассчитать вероятность, если он захочет сыграть 10, потому что он может не помнить, если Джек все еще в игре.
Это имитирует человеческое внимание.

TL; DR
Ограничьте, сколько ИИ знает, поэтому его решения не идеальны, просто достаточно хороши.

Цезарь Моиз
источник
Спасибо за Ваш ответ. Но, как сказано в вопросе, после раздачи карт не бывает удачи / случайности. И игрок не знает карты других игроков. Он должен делать предположения, используя уже сыгранные карты и некоторые «правила».
LaurentG
2
Понравилась идея случайного удаления запомненных карточек. Это дает подсказку о развитии уровней, таких как легкий, средний и сложный.
СуперМ