Знав би прикуп - жив би в Сочі.
Народна мудрість.
Під гравця - з семака, під вістуючого - з тузуючого.
Ще одна народна мудрість.
Схоже, в цьому пості все змішалося. "Дурень" "у заголовку, преферансні приказки в епіграфі та КДПВ, що не має стосунку ні до того ні до іншого. Втім, саме поняття "джокера" ", до предмета сьогоднішньої розмови, відношення має саме безпосереднє.
Близько місяця тому ComradMax опублікував статтю про свою дебютну гру під Android (стаття, до речі, теж дебютна). Порушена тема приємно вразила мене великою кількістю варіантів відомої всім гри. Про деякі я знав, інші стали для мене одкровенням. Сама ідея - перетворити карткову гру на якусь подобу RPG взяла мене за живе. На жаль, AI реалізації проявив себе не кращим чином. Хоч я і не грав в «Дурня» з п'ятирічного віку, я легко обігрую програму. Деякі її ходи просто дурні (сподіваюся, що автор на мене не образиться).
Ця невідповідність потужності задумки і вельми слабкого «інтелекту» реалізації і змусила мене задуматися над тим, яким чином повинен працювати AI подібної гри. Треба сказати, що ця проблема набагато складніша, ніж здається на перший погляд. Карткові ігри (і «Дурень» в тому числі) відносяться до категорії ігор з неповною інформацією. Алгоритми, що застосовуються в шахових програмах або програмах для гри в Го до них не підходять. У всякому разі, у вихідному вигляді.
Збирання даних
Запорукою перемоги є розвідка! А основа розвідки - ретельний аналіз повністю відкритих даних. Що нам відомо про карти противника, коли ми граємо в «Дурня»? Здавалося б трохи, карти ж від нас закриті? На ділі, все не так погано. Наприклад, ми знаємо які карти у нас на руках і номінал карти показує козир (якщо гра йде з козирем). Це саме по собі вже непогано, але ще краще наше знання про те, що цих карт немає у супротивника (це в разі, якщо гра йде однією колодою). Спробуємо скласти повний список джерел даних про картки супротивників, стосовно «Дурня»:
- Відкриті карти (про це я вже говорив)
- Карти взяті гравцями по ходу гри (в тому числі ті, якими вони намагалися неуспішно відбитися)
- Карти вийшли з гри, в результаті відбою (це джерело менш очевидне, ніж попередні)
- Карти, побити які не вдалося (це ще менш очевидно і я розповім про це нижче)
Ще одне джерело
Програма ComradMax може отримати інформацію про картки супротивника ще одним кумедним чином. Справа в тому, що всі дії в ній (такі як відбій або взяття карт з колоди) автор постарався реалізувати жестами. Це управління досить інтуїтивно, для того, щоб обходитися без кнопок (хоча кнопки, про всяк випадок, теж є). Так от, якщо взяти карту з колоди і «не дотягнути» до своїх карт, вона відкривається і противники її «бачать». Комп'ютерні гравці відпускають єхидні зауваження, але, зі слів автора, AI програми цю інформацію поки ніяк не використовує.
В принципі, ніхто не може перешкодити комп'ютеру підглянути всі карти гравця. Більш того, саме цим шляхом йдуть розробники більшості карткових ігор, але цей шлях порочений, за своєю суттю. Гра комп'ютера, сама по собі, мало нагадує людську, а якщо він «знає» всі карти - це ще більше кидається в очі. Користувач може навіть не усвідомити цього, але зігравши десяток партій він охолоне до програми. Я вважаю, що стиль гри подібних «розважальних» програм слід максимально наближати до людиноподібного. Мета не в тому, щоб програма грала максимально сильно. Головне, щоб вона не викликала відторгнення! А варіант AI з «підгляданням» карт можна використовувати для спеціальних опцій, таких як «гра з шуллером».
Хоча з другим пунктом все і так зрозуміло, хочу підкреслити, що ми повинні враховувати будь-які відомі нам карти, які бере противник. Наприклад, в модифікації гри "Чарівний" ", якщо ми ходимо чорним джокером (до місця все-таки картинка), то віддаємо противнику свої дві карти. Після цього, ми точно знаємо, що ці карти у нього є, до тих пір, поки він від них, яким-небудь чином, не позбудеться (ми дізнаємося про це). Можливо це не очевидно, але подібне може статися в той момент, коли він, в свою чергу, сходить чорним джокером. Як вчинити, в такому випадку, буде ясно з подальшої оповіді.
Починаючи з третьої цифри, все стає трохи складніше. Загалом-то зрозуміло, що AI повинен враховувати карти, що вийшли з гри, питання в тому, як це реалізувати технічно. Для представлення карт на руках противників, можна використовувати два типи об'єктів. Перший - карта з точно відомим номіналом (масть + значення), другий - джокер, який, в найгіршому випадку (тобто, на початку гри), може бути майже чим завгодно. У міру того, як гравці роблять ходи, ми отримуємо все більше інформації про картах, що вийшли з гри. Викреслюючи ці значення з «джокера» (при такому поданні даних, він один на всі невідомі карти), ми уточнюємо свої знання про закриті картки. Коли колода повністю розібрана, ми знаємо всі карти (не знаємо тільки які у кого), а коли гравців залишається двоє, ми просто знаємо всі карти противника!
Четверте джерело ще більш ефемерне. Припустимо, ми ходимо під противника, а він бере карту, навіть не спробувавши її побити. Що нам це дає? Швидше за все нічого (можливо він просто копить карти для свого ходу), але можна взяти на замітку, що цю масть він бере і, швидше за все, якщо сходити тим же мастью, але номіналом вище (нижче ходити резону немає, зі зрозумілих причин), то він і її візьме теж (або нарешті візьметься за козирі). Це означає, що для «джокерів», у нього на руках, можна зробити позначку, що вони не вище того номіналу, картою якого ми сходили (з урахуванням старшинства козирів). Якщо ми помилилися, позначку ніколи не пізно зняти.
Зрозуміло, щоб життя зовсім вже не здавалося нам медом, були придумані різноманітні правила, що ускладнюють збір інформації. У "Покерному" "дурні, гравець, перед відбоєм, має право поміняти будь-які свої дві карти на карти з колоди. Фактично, це означає, що нам доведеться повністю скидати інформацію про точно відомі картки гравця. Після такого обміну, всі його карти перетворюються на «джокерів». Виняток можна зробити, хіба що, для старших карт у мастях і козирів (навряд чи хтось у тверезому розумі стане їх змінювати).
У дурні "З прикупом" "(є прикуп в" Дурні ", не брехав епіграф), кожному гравцеві, на початку гри, лунає кілька закритих карт. Гравець бере ці карти, коли карти в колоді і на руках повністю закінчуються, після чого, дограють гру з ними. Це набагато більш щадний варіант. Фактично, у фінальній стадії гри, він майже нічого не змінює в наших знаннях про розклад, але лише зобов'язує закінчувати гру абсолютно випадковими картами. Якщо карти виявляться невдалими, AI навряд чи чим зможе допомогти.
Також, на несподіваний фінал орієнтований "Потаємною" "дурень. Під козир кладеться закрита карта. Коли козир (після розбору колоди) забирається одним з гравців, ця карта відкривається і показує новий козир. У цей момент, все що було нажито непосильною працею, в ході гри (включаючи жадану козирну карту, внизу колоди), цілком може перетворитися на пил. У цій грі, випадковість також може переважити інтелект AI (якщо тільки не використовувати стратегію гри в "Безкозирного" "дурня, з набором старших карт у всіх мастях).
Мабуть, найжорсткіший для AI варіант - "Чукотський" ". Відразу після роздачі і відкриття козиря, колода (разом з відкритим козирем) видаляється з гри. Гра дуже швидкоплинна і відбувається, практично, «в темну». AI тут ніде розвернутися.
У всьому важлива міра
Добре, ми зібрали дані і, в якійсь мірі, знаємо, що за карти на руках у противника. Ми можемо вирахувати ймовірність того, що противник може успішно відбитися від нашого заходу (це не означає, що він буде це робити), але цього мало! Ми все ще не можемо «взяти і просто використовувати» мінімаксний алгоритм з альфа-бета відсіканням. Необхідна кількісна оцінка позиції. Як ви вже здогадуєтеся, в різних «дурнях» вона буде різна.
Для того, щоб зрозуміти, наскільки хороші карти на руках, ми можемо, для кожної з них, визначити кількість карт (що знаходяться в грі), здатних її побити (це не єдино можливий підхід, але мені він видається найбільш перспективним). Найпростіше справа йде з "Безмастним" "варіантом. Вибудовуємо карти за ранжиром (без урахування масті) і підраховуємо кількість тих, що старше (з тих, що ще в грі, зрозуміло). У "Безкозирному" "цих" ранжирів "буде вже чотири (за кількістю мастей), а в найбільш поширеному" Козирному "варіанті, ланцюжок козирів буде покривати кожну з мастей.
Існують і більш заковиристі варіанти. У "Двокозирному" "дурні кожен з гравців оголошує свій козир. За домовленістю, козирі одного гравця необхідно бити або тією-ж майстрою або, додатково, ще й своїми козирями. У результаті, оціночні функції, що застосовуються для гравців, будуть різними, але, зрозуміло, незмінними від одного ходу до іншого (інакше весь мінімакс полетить до біса).
Невелике пояснення
Взагалі кажучи, навіть при наявності хорошої оціночної функції, застосувати альфа-бета відсікання заважають ще дві обставини. По-перше, всі ці мінімаксні штуки розраховані на гру двох гравців. Оціночна функція будується таким чином, що з оцінки стану гравця, віднімається оцінка стану його противника. Якщо ми обчислюємо оцінку тієї-ж позиції, але з точки зору противника - знак змінюється, але абсолютне значення залишається тим же (і це важливо для роботи алгоритму). У випадку «Дурня», гра двох людей - швидше виняток ніж правило. Втім, можна вивернутися і вважати всіх ворогуючих гравців одним єдиним противником (нас адже цікавить найгірший варіант їх спільної поведінки). У разі ж гри "2x2" ", противостоящими гравцями слід вважати пари.
Іншим відкритим питанням залишаються «джокери» на руках супротивників, номінал яких нам відомий лише приблизно. Тут складно запропонувати задовільне рішення. Можна усереднювати номінали тих карт, які може представляти «джокер», але потрібні експерименти, щоб визначити, наскільки цей підхід хороший.
Подвійний «», «Королівський» «і» Дикий «» варіанти гри також вимагають спеціальної побудови оціночних функцій, але запропонований вище підхід цілком працює і в їх випадку.
Битва за годівницю
Якої стратегії слід дотримуватися при грі в «Дурня»? В першу чергу, це залежить від фази гри. У найбільш поширеному варіанті, можна виділити три основних фази:
- Початкова
- Проміжна
- Фінальна
Перша фаза найтриваліша. Поки колода не розібрана, основне завдання гравця (крім збору даних) - накопичення на руках старших карт (особливо козирів). Це означає, що слід ходити так, щоб позбутися якомога більшої кількості молодших карт (для того, щоб взяти відповідну кількість карт з колоди). Противників слід від колоди відтісняти, стежачи за тим, щоб вони не відчували нестачі в картах на руках.
Якщо на руках велика кількість старших карт, їх слід економити. Часто вигідніше взяти карти (тим самим заощадивши свої старші карти), навіть якщо є можливість відбитися. Взяті карти можна буде згодом віддати або підкинути (особливо якщо взята карта приходить в пару або трійку до карт іншої масті), а з урахуванням того, що старші карти вже у нас на руках, ймовірність того, що противники знайдуть в колоді щось цінне, мала.
У якийсь момент карт у колоді залишається так мало, що вони будуть повністю обрані перед наступним ходом. Цю швидкоплинну фазу гри складно помітити людині, але вона може бути дуже важлива. В першу чергу, на цьому ходу, слід дбати про те, щоб забрати собі не повний комплект карт. Друга мета - відкрита карта козиря внизу колоди (якщо там лежить туз або король, за нього варто поборотися). Крім відкритого козиря, метою боротьби можуть бути і останні карти колоди. Про них відомо менше, але в деяких випадках, можна з високою ймовірністю передбачити там наявність великих карт.
З усього сказаного випливає, що AI слід постаратися, щоб хід, після якого вся колода розбирається, припадав на його відбій (який відбивається бере карти останнім), але при цьому в колоді залишалася б достатня кількість карт, щоб встигнути взяти козира. Якщо карт в колоді мало, AI може бути вигідно бути одним з підкидних (тим, хто забере останні карти). Це головоломне завдання, але для комп'ютера цілком посильне, оскільки точне число карт, що залишилися в колоді, йому відомо в будь-який момент гри.
Коли колода розібрана і карта, що показує козир, взята, настає фінальна стадія гри. Єдина мета гравця, в цій фазі гри - якомога швидше позбутися всіх своїх карт. Приватним (але дуже важливим) випадком виявляється ситуація, коли гравців залишається двоє. У цьому випадку, карти на руках противника точно відомі (якщо мова не йде про «Чукотський» варіант) і можна розпланувати послідовність своїх ходів так, щоб противник не міг відбитися ні на якому ходу крім останнього. Якщо це неможливо, слід відбиватися таким чином, щоб противник не мав можливості підкидати свої карти.
Зрозуміло, народна мудрість і тут вишукала способи, зробити наше життя цікавішим. У "Відбійному" "дурні кожен другий відбій йде в колоду, що ускладнює гру, але дає" другий "шанс отримати хороші карти. У "Порожньому" "карти беруться лише тоді, коли рука повністю спорожніє (при такому підході, зберегти до кінця гри козирі, отримані при початковому розкладі навряд чи вдасться). У варіанті «Друга спроба» «, гравець, якому не вдається побити карту, може спробувати відбитися картою взятої з колоди, а в» Вірменському «» дурні може брати карту з колоди для свого заходу (ці варіанти можна комбінувати). Нарешті в "Наваленому" "колода просто ділиться між усіма гравцями, після чого всяка боротьба за колоду виявляється виключена, зважаючи на відсутність такої. З Дурнем не скучиш!
Ворог мого ворога
Отже, зі стратегічними цілями все ясно (потрібно накопичувати великі карти), але як цього домогтися? У найбільш поширеному "Підкидному" "дурні (і в" Перекладному "" теж, якщо мова йде не про "Безпідкидний" ") є чудова тактична можливість. Підкидаючи гравцеві карти, можна домогтися того, щоб він їх взяв (або розтратив всіх своїх козирів). Є ряд обмежень, що стосуються цієї можливості, наприклад не можна підкидати більше карт ніж є на руках відбивається і, як правило, першим підкидає той, хто ходив, але, все одно, «підкидання» карт - це чудова можливість змінити хід гри.
Залишилося визначитися з тим, кому підкидати карти. У грі двох гравців все зрозуміло - дрібні карти слід підкидати при будь-якій можливості, великі (особливо козирі) - лише в рідкісних випадках (наприклад, коли йде боротьба за останні карти колоди). Якщо грають троє (найбільш поширений випадок), все стає цікавіше. Противник, що ходить під гравця, очевидно є його природним ворогом, але той, під кого ходить сам гравець, до деякої міри, його союзник! Невигідно «топити» його, підкидаючи йому карти або виконуючи хід великою картою (це, в будь-якому випадку, не найвдаліша думка), оскільки, якщо він не відіб'ється - наступний хід буде вже під нас.
Гравцеві зліва (хід передається по годинниковій стрілці) слід дати легко відбитися, після чого підтримати його хід, по можливості змусивши відбивається забрати карти. За аналогією з преферансною приказкою з епіграфа, той, під кого ходимо ми - «гравець», а той, хто ходить під нас - «вістуючий». При грі чотирьох гравців (або шести, що зовсім вже рідко), природним чином формуються дві «коаліції» (навіть якщо формально гра не йде «2x2»). Гравці, які сидять один на проти одного - союзники (принаймні, поки кількість гравців, що залишилися в грі, не зменшиться).
Всі наші прекрасні плани, як зазвичай, вщент розбиваються "Добрим" "дурнем. У цьому варіанті гри, не має значення, кому підкидати карти, оскільки, навіть якщо гравець не зможе відбитися, наступним ходити буде все одно він! У "Прибалтійському" "ж дурні сам процес відбою може легко перерости в контратаку (але, мабуть, це надто екзотичний варіант гри, у всякому разі, не дуже зрозуміло, як грати за цими правилами трьом і більше гравцям).
Кінець-справі вінець
Як я вже говорив, коли колода повністю розібрана і всі карти на руках, єдине завдання гравця - скоріше від них позбутися. І тут стає важлива не стільки сила карт, скільки їх кількість. Насправді, якщо гравець залишився на своєму ходу з однією, нехай навіть наймолодшою картою (або з парою карт одного рангу) - він вже виграв. Сильні карти потрібні лише для успішного відбою (і дуже бажано, щоб після цього відбою у противника ще залишалися карти). Якщо грають два гравці (і якщо не використовуються спеціальні правила, що приховують інформацію до останнього) виграшну послідовність ходів можна просто прорахувати повним перебором (всі карти на руках відомі і можливих варіантів не дуже багато). При цьому, можна навіть приберегти пару шісток для останнього ходу, щоб одягнути «погони» на переможеного.
Якщо гравців більше двох, карти залишилися в грі також відомі, але немає інформації про те у кого з гравців які. Якщо немає можливості відразу віддати карти своїм ходом (або скинути всі дрібні карти, залишивши козирів для останнього відбою), слід дотримуватися тієї ж тактики, що і в основній фазі гри - ходити дрібними картами, підкидати гравцеві справа покрупніше, берегти козирі. Рано чи пізно гравців залишиться двоє (і якщо вам не пощастить - ви будете одним з них). У цей момент стане ясно, хто переміг, оскільки прихованої інформації в грі не залишиться.
Є кілька різновидів «Дурня», що дозволяють скоріше позбавлятися від своїх карт. Наприклад, в "Американському" "можна підкидати карти самому собі, на своєму відбої, і покривати їх (після того як підкинули всі інші гравці). У "Хитрому" "дурні, якщо гравець не зміг побити одну або кілька карт, то той учасник гри, через який не вдалося відбитися, може побити ці карти зі" своїх запасів ". В результаті, він позбавляється від зайвих карт, а той гравець, що не зміг відбитися - забирає додаткові карти. У "Нахабному" "дурні, побити свою карту таким чином можна ще до того як підкинути її супернику. Зрозуміло, якщо правила надають такі можливості позбавлення від своїх карт, їх треба всіляко використовувати.
Звичайно, моя стаття не претендує ні на скільки-небудь докладний опис всіх існуючих правил гри ні на формальний опис алгоритмів AI для неї. Це всього лише розрізнені думки, якими я обіцяв поділитися з шановним ComradMax до відпустки. Сподіваюся, що вони будуть йому корисні.
