Pull to refresh

AI для «Дурака»

Reading time 11 min
Views 35K
Знал бы прикуп — жил бы в Сочи.

       Народная мудрость. 

Под игрока — с семака, под вистующего — с тузующего.

       Ещё одна народная мудрость. 


Похоже, в этом посте всё смешалось. "Дурак" в заголовке, преферансные поговорки в эпиграфе и КДПВ, не имеющая отношения ни к тому ни к другому. Впрочем, само понятие "джокера", к предмету сегодняшнего разговора, отношение имеет самое непосредственное.

Около месяца назад ComradMax опубликовал статью о своей дебютной игре под Android (статья, кстати, тоже дебютная). Затронутая тема приятно поразила меня обилием вариантов известной всем игры. Про некоторые я знал, другие стали для меня откровением. Сама идея — превратить карточную игру в некое подобие RPG взяла меня за живое. К сожалению, AI реализации проявил себя не лучшим образом. Хоть я и не играл в «Дурака» с пятилетнего возраста, я легко обыгрываю программу. Некоторые её ходы просто глупые (надеюсь, что автор на меня не обидится).

Это несоответствие мощи задумки и весьма слабого «интеллекта» реализации и заставило меня задуматься над тем, каким образом должен работать AI подобной игры. Надо сказать, что эта проблема гораздо сложнее, чем кажется на первый взгляд. Карточные игры (и «Дурак» в том числе) относятся к категории игр с неполной информацией. Алгоритмы, применяемые в шахматных программах или программах для игры в Го к ним не подходят. Во всяком случае, в исходном виде.

Сбор данных


Залогом победы является разведка! А основа разведки — тщательный анализ полностью открытых данных. Что нам известно о картах противника, когда мы играем в «Дурака»? Казалось бы немного, карты ведь от нас закрыты? На деле, всё не так плохо. Например, мы знаем какие карты у нас на руках и номинал карты показывающей козырь (если игра идёт с козырем). Это само по себе уже неплохо, но еще лучше наше знание о том, что этих карт нет у противника (это в случае, если игра идёт одной колодой). Попробуем составить полный список источников данных о картах противников, применительно к «Дураку»:

  1. Открытые карты (об этом я уже говорил)
  2. Карты взятые игроками по ходу игры (в том числе те, которыми они пытались неуспешно отбиться)
  3. Карты вышедшие из игры, в результате отбоя (этот источник менее очевиден, чем предыдущие)
  4. Карты, побить которые не удалось (это еще менее очевидно и я расскажу об этом ниже)

Ещё один источник
Программа ComradMax может получить информацию о картах противника ещё одним забавным образом. Дело в том, что все действия в ней (такие как отбой или взятие карт с колоды) автор постарался реализовать жестами. Это управление достаточно интуитивно, для того, чтобы обходиться без кнопок (хотя кнопки, на всякий случай, тоже есть). Так вот, если взять карту с колоды и «не дотащить» до своих карт, она открывается и противники её «видят». Компьютерные игроки отпускают ехидные замечания, но, со слов автора, AI программы эту информацию пока никак не использует.

В принципе, никто не может помешать компьютеру подсмотреть все карты игрока. Более того, именно по этому пути идут разработчики большинства карточных игр, но этот путь порочен, по своей сути. Игра компьютера, сама по себе, мало напоминает человеческую, а если он «знает» все карты — это ещё больше бросается в глаза. Пользователь может даже не осознать этого, но сыграв десяток партий он охладеет к программе. Я считаю, что стиль игры подобных «развлекательных» программ следует максимально приближать к человекоподобному. Цель не в том, чтобы программа играла максимально сильно. Главное, чтобы она не вызывала отторжения! А вариант AI с «подглядыванием» карт можно использовать для специальных опций, таких как «игра с шуллером».

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

Начиная с третьей цифры, всё становится чуть сложнее. В общем-то понятно, что AI должен учитывать карты, вышедшие из игры, вопрос в том, как это реализовать технически. Для представления карт на руках противников, можно использовать два типа объектов. Первый — карта с точно известным номиналом (масть + значение), второй — джокер, который, в самом плохом случае (то есть, в начале игры), может быть почти чем угодно. По мере того, как игроки делают ходы, мы получаем всё больше информации о вышедших из игры картах. Вычеркивая эти значения из «джокера» (при таком представлении данных, он один на все неизвестные карты), мы уточняем свои знания о закрытых картах. Когда колода полностью разобрана, мы знаем все карты (не знаем только какие у кого), а когда игроков остаётся двое, мы просто знаем все карты противника!

Четвёртый источник ещё более эфемерный. Допустим, мы ходим под противника, а он берёт карту, даже не попытавшись её побить. Что нам это даёт? Скорее всего ничего (возможно он просто копит карты для своего хода), но можно взять на заметку, что эту масть он берёт и, скорее всего, если сходить тоё-же мастью, но номиналом повыше (ниже ходить резона нет, по понятным причинам), то он и её возьмёт тоже (или наконец возьмётся за козыри). Это означает, что для «джокеров», у него на руках, можно сделать пометку, что они не выше того номинала, картой которого мы сходили (с учётом старшинства козырей). Если мы ошиблись, пометку никогда не поздно снять.

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

В дураке "С прикупом" (есть прикуп в «Дураке», не врал эпиграф), каждому игроку, в начале игры, раздаётся несколько закрытых карт. Игрок берёт эти карты, когда карты в колоде и на руках полностью заканчиваются, после чего, доигрывают игру с ними. Это гораздо более щадящий вариант. Фактически, в финальной стадии игры, он почти ничего не меняет в наших знаниях о раскладе, но лишь обязывает заканчивать игру совершенно случайными картами. Если карты окажутся неудачными, AI вряд ли чем сможет помочь.

Также, на неожиданный финал ориентирован "Потайной" дурак. Под козырь кладётся закрытая карта. Когда козырь (после разбора колоды) забирается одним из игроков, эта карта открывается и показывает новый козырь. В этот момент, всё что было нажито непосильным трудом, в ходе игры (включая вожделенную козырную карту, внизу колоды), вполне может превратиться в пыль. В этой игре, случайность также может перевесить интеллект AI (если только не использовать стратегию игры в "Бескозырного" дурака, с набором старших карт во всех мастях).

Пожалуй, самый жёсткий для AI вариант — "Чукотский". Сразу после раздачи и открытия козыря, колода (вместе с открытым козырем) удаляется из игры. Игра очень скоротечна и происходит, практически, «в тёмную». AI здесь негде развернуться.

Во всём важна мера


Хорошо, мы собрали данные и, в какой-то мере, знаем, что за карты на руках у противника. Мы можем вычислить вероятность того, что противник может успешно отбиться от нашего захода (это не значит, что он будет это делать), но этого мало! Мы всё ещё не можем «взять и просто использовать» минимаксный алгоритм с альфа-бета отсечением. Необходима количественная оценка позиции. Как вы уже догадываетесь, в разных «дураках» она будет разная.

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

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

Небольшое разъяснение
Вообще говоря, даже при наличии хорошей оценочной функции, применить альфа-бета отсечение мешают ещё два обстоятельства. Во первых, все эти минимаксные штуки рассчитаны на игру двух игроков. Оценочная функция строится таким образом, что из оценки состояния игрока, вычитается оценка состояния его противника. Если мы вычисляем оценку той-же позиции, но с точки зрения противника — знак изменяется, но абсолютное значение остаётся тем же (и это важно для работы алгоритма). В случае «Дурака», игра двух человек — скорее исключение чем правило. Впрочем, можно вывернуться и считать всех противостоящих игроков одним единым противником (нас ведь интересует худший вариант их совместного поведения). В случае же игры "2x2", противостоящими игроками следует считать пары.

Другим открытым вопросом остаются «джокеры» на руках противников, номинал которых нам известен лишь приблизительно. Здесь сложно предложить удовлетворительное решение. Можно усреднять номиналы тех карт, которые может представлять «джокер», но требуются эксперименты, чтобы определить, насколько этот подход хорош.

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

Битва за кормушку


Какой стратегии следует придерживаться при игре в «Дурака»? В первую очередь, это зависит от фазы игры. В наиболее распространённом варианте, можно выделить три основных фазы:

  1. Начальная
  2. Промежуточная
  3. Финальная

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

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

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

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

Когда колода разобрана и карта, показывающая козырь, взята, наступает финальная стадия игры. Единственная цель игрока, в этой фазе игры — как можно скорее избавиться от всех своих карт. Частным (но очень важным) случаем оказывается ситуация, когда игроков остаётся двое. В этом случае, карты на руках противника точно известны (если речь не идёт о «Чукотском» варианте) и можно распланировать последовательность своих ходов так, чтобы противник не мог отбиться ни на каком ходу кроме последнего. Если это невозможно, следует отбиваться таким образом, чтобы противник не имел возможности подкидывать свои карты.

Разумеется, народная мудрость и здесь изыскала способы, сделать нашу жизнь интереснее. В "Отбойном" дураке каждый второй отбой идёт в колоду, что усложняет игру, но даёт «второй» шанс заполучить хорошие карты. В "Пустом" карты берутся лишь тогда, когда рука полностью опустеет (при таком подходе, сохранить до конца игры козыри, полученные при первоначальном раскладе вряд ли удастся). В варианте "Вторая попытка", игрок, которому не удаётся побить карту, может попытаться отбиться картой взятой с колоды, а в "Армянском" дураке может брать карту с колоды для своего захода (эти варианты можно комбинировать). Наконец в "Наваленном" колода просто делится между всеми игроками, после чего всякая борьба за колоду оказывается исключена, ввиду отсутствия таковой. С Дураком не соскучишься!

Враг моего врага


Итак, со стратегическими целями всё ясно (требуется накапливать крупные карты), но как этого добиться? В наиболее распространённом "Подкидном" дураке (и в "Переводном" тоже, если речь идёт не про "Бесподкидный") имеется великолепная тактическая возможность. Подкидывая отбивающемуся игроку карты, можно добиться того, чтобы он их взял (или растратил всех своих козырей). Есть ряд ограничений, касающихся этой возможности, например нельзя подкидывать больше карт чем есть на руках отбивающегося и, как правило, первым подкидывает тот, кто ходил, но, всё равно, «подкидывание» карт — это великолепная возможность изменить ход игры.

Осталось определиться с тем, кому подкидывать карты. В игре двух игроков всё понятно — мелкие карты следует подкидывать при любой возможности, крупные (особенно козыри) — лишь в редких случаях (например, когда идёт борьба за последние карты колоды). Если играют трое (наиболее распространённый случай), всё становится интереснее. Противник, ходящий под игрока, очевидно является его естественным врагом, но тот, под кого ходит сам игрок, до некоторой степени, его союзник! Невыгодно «топить» его, подкидывая ему карты или выполняя ход крупной картой (это, в любом случае, не самая удачная мысль), поскольку, если он не отобьётся — следующий ход будет уже под нас.

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

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

Конец — делу венец


Как я уже говорил, когда колода полностью разобрана и все карты на руках, единственная задача игрока — поскорее от них избавиться. И здесь становится важна не столько сила карт, сколько их количество. В самом деле, если игрок остался на своём ходу с одной, пусть даже самой младшей картой (или с парой карт одного ранга) — он уже выиграл. Сильные карты нужны лишь для успешного отбоя (и очень желательно, чтобы после этого отбоя у противника ещё оставались карты). Если играют два игрока (и если не используются специальные правила, скрывающие информацию до последнего) выигрышную последовательность ходов можно просто просчитать полным перебором (все карты на руках известны и возможных вариантов не очень много). При этом, можно даже приберечь пару шестёрок для последнего хода, чтобы одеть «погоны» на проигравшего.

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

Есть несколько разновидностей «Дурака», позволяющих поскорее избавляться от своих карт. Например, в "Американском" можно подкидывать карты самому себе, на своём отбое, и покрывать их (после того как подкинули все остальные игроки). В "Хитром" дураке, если игрок не смог побить одну или несколько карт, то тот участник игры, из за которого не удалось отбиться, может побить эти карты из «своих запасов». В результате, он избавляется от лишних карт, а тот игрок, что не смог отбиться — забирает дополнительные карты. В "Наглом" дураке, побить свою карту таким образом можно ещё до того как подкинуть её сопернику. Разумеется, если правила предоставляют такие возможности избавления от своих карт, их надо всячески использовать.

Конечно, моя статья не претендует ни на сколь нибудь подробное описание всех существующих правил игры ни на формальное описание алгоритмов AI для неё. Это всего лишь разрозненные мысли, которыми я обещал поделиться с уважаемым ComradMax до отпуска. Надеюсь, что они будут ему полезны.
Tags:
Hubs:
+24
Comments 7
Comments Comments 7

Articles