Вчені прорахували оптимальну стратегію гри в покер «∀ x, y, z

Мал. 1. Гра хедз-ап (heads-up) в покер. За столом двоє гравців і круп'є, який здає їм карти. Фото з сайту pokernews.com

В на початку 2015 року в журналі Science вийшла стаття, в якій було оголошено про успішне завершення роботи комп'ютерної програми, прораховувати одну з версій покеру - хедз-ап в лімітному техаському холдеме. Програма навчилася приймати правильне рішення в кожному з приблизно 3,19 × 1014 можливих станів гри. Знайдена таким чином стратегія на довгій дистанції повинна обігравати інші стратегії. Одним з результатів аналізу стало доказ того, що дилер має перевагу перед другим гравцем. Автори статті пропонують провідною професійною гравцям в покер випробувати стратегію на практиці і переконатися в її оптимальності.

Техаський холдем ( texas hold'em ) - найпопулярніший різновид покеру. Гра ведеться стандартною колодою з 52 карт. На початку кожного розіграшу гравці отримують по 2 карти (кишенькові карти). Вони дивляться на свої карти, після чого відбувається перший раунд торгівлі. Гравця, який починає торгівлю, називають дилером (або гравцем на кнопці, см. Button (poker) ), Після кожного розіграшу дилером стає следущий по колу гравець. Під час торгівлі гравець може підвищити ставку (raise), зрівняти ставку суперника (call) або відмовитися від подальшої участі в розіграші і скинути карти (fold). У підсумку після раунду торгівлі кожен залишився в розіграші гравець поставив на кін одну і ту ж суму грошей. Далі для всіх відкриваються три загальні карти (flop), після чого відбувається другий раунд торгівлі. Після цього відкривається ще одна карта (turn), відбувається третій раунд торгівлі. Нарешті, відкривається п'ята загальна карта (river), і відбувається останній, четвертий раунд торгівлі. Якщо в якийсь момент в грі залишається тільки один гравець, він забирає весь банк. Якщо після четвертого раунду торгівлі в грі залишається більше одного гравця, то вони розкривають свої кишенькові карти і порівнюють отримані 5-карткові комбінації, які кожен може побудувати з особистих і загальних карт. Той, у кого комбінація краще, забирає банк.

Комбінація складається з двох кишенькових карт, які лунають гравцям на початку гри, і п'яти загальних карт, які викладаються на стіл в процесі гри. У комбінації беруть участь п'ять карт з цих семи. Комбінації перераховані по спадаючій старшинства.

Роял-флеш (royal flush) - окремий випадок стріт-флеш, старший з усіх можливих, складається з 5 старших (туз, король, дама, валет, десять) карт однієї масті.

Стріт-флеш (straight flush) - будь-які п'ять карт однієї масті по порядку.

Каре (four of a kind) - чотири карти однієї гідності.

Фул-хаус (full house) - трійка і пара.

Флеш (flush) - п'ять карт однієї масті.

Стріт (straight) - п'ять карт по порядку будь-яких мастей.

Сет (three of a kind, set) - три карти однакової гідності.

Дві пари (two pairs) - дві пари карт.

Пара (pair) - дві карти одного достоїнства.

Старша карта (high card) - у гравця немає жодної з перерахованих вище комбінацій.

Хедз-ап ( heads up ) Означає, що грають тільки два гравці. Лімітний покер - це версія гри, в якій ставки можна підвищувати на фіксовану величину, причому підвищувати ставку можна не більше ніж заздалегідь обумовлену кількість разів. Тому лімітний техаський холдем - це кінцева гра. послідовні ігри в теорії ігор прийнято ставити за допомогою дерев . Вершин дерева будуть відповідати різні стану гри. Кожній вершині приписано ім'я гравця, якому в цій вершині належить хід. Ребрах, що виходить з цієї вершини, відповідають дії, які може зробити цей гравець. Одним з учасників гри є «природа» - так в теорії ігор називають штучного гравця, що виконує роль генератора випадкових чисел. «Природа» випадковим чином вирішує, яку карту здати гравцям або відкрити на столі.

Послідовні ігри можна розділити на два види: ігри з досконалою інформацією (див. Perfect information ) І гри з недосконалою інформацією. В іграх з досконалою інформацією кожен гравець завжди знає, в якій вершині дерева він знаходиться і що відбувалося до цього. В іграх з недосконалою інформацією гравець може бути не впевнений в тому, в якому стані знаходиться гра. Покер - приклад гри з недосконалою інформацією: гравець, який не знає, які карти знаходяться на руках у його суперника. Кожен може спостерігати загальні карти і здійснюються дії в момент торгівлі, однак карти суперника в момент торгівлі відомі не будуть.

Будь-яку кінцеву послідовну гру з досконалою інформацією можна прорахувати з кінця, використовуючи алгоритм зворотного індукції. Розглянувши одну подигру самого останнього рівня (тобто таку подигру, на якій після прийняття будь-якого рішення гра закінчується і гравці підраховують отримані платежі), можна знайти оптимальне дію гравця, якому належить хід на цій подигре. Далі точно так же можна знайти оптимальні дії гравців на всіх подиграх останнього рівня. Після цього, знаючи, як будуть вести себе раціональні гравці на подиграх останнього рівня, можна перейти до аналізу ігор передостаннього рівня, і так далі. Рано чи пізно, точно вийде дістатися до подигри, що збігається з усією грою, після чого можна знайти в ній оптимальне дію гравця, якому належить перший хід. Таким чином, буде знайдено оптимальне поведінка всіх гравців в будь-якій можливій ситуації і буде з'ясовано, чим закінчується гра при правильних діях всіх гравців. Саме так в 2007 році були прораховані шашки - виявилося, що при правильній грі обох сторін в шашках партія обов'язково закінчиться внічию (J. Schaeffer et al., 2007. Checkers is solved ).

Покер менше шашок за кількістю можливих станів гри. Однак покер, на відміну від шашок, є грою з недосконалою інформацією. Це робить неможливим пряме застосування алгоритму зворотного індукції: якщо гравець в якийсь момент не знає, в який з вершин він знаходиться, то він не зможе знайти однозначно оптимальне рішення. Проте таку гру можна переписати у вигляді матриці ( нормальна форма гри ): По горизонталі можна виписати всі стратегії першого гравця, по вертикалі - все стратегії другого гравця, після чого в отриманої матриці можна знайти рівновагу Неша . Теоретично. Тут нас чекає ще одна проблема: отримана матриця для покеру буде дуже великий. Складність знаходження рівноваги Неша за допомогою алгоритму лінійного програмування зростає експоненціально при зростанні кількості станів гри, тому для складних ігор на зразок покеру метод непридатний. Доводиться відмовитися від ідеї прямого відомості дерева до матриці. Замість цього автори використовують спеціальну модифікацію критерію Севіджа (див. Regret (decision theory) ), Призначену для вирішення ігор з недосконалою інформацією за лінійний час від числа станів гри. Алгоритм переглядає з кінця інформаційні безлічі і приписує їм той чи інший штраф в залежності від зіграної стратегії. Після цього алгоритм мінімізує набраний штраф.

Ще одна складність у вирішенні покеру полягала в тому, що в ньому очікувані платежі гравців виражаються не обов'язково цілими числами - порівняйте з шашками, в яких можливі лише 3 результату! Оскільки мова йде про обчислення платежів комп'ютером, то авторам довелося наближати нескінченні десяткові дроби з заданим рівнем точності ε. Але тоді не можна використовувати стандартне визначення рівноваги Неша, адже похибка обчислення може перешкодити відповісти на питання, чи вигідно комусь із гравців відхилятися від того чи іншого профілю гри. Автори використовують концепцію ε-рівноваги Неша , Відповідно до якої профіль стратегій називається ε-рівновагою Неша, якщо жоден з гравців, відхиляючись від цього профілю стратегій, не може збільшити свою корисність більш ніж на ε. Зокрема, будь-який рівновагу Неша є ε-рівновагою Неша.

Нарешті ми підійшли до результату, який отримали автори статті в Science. Для деякого досить малого ε автори пред'явили ε-рівновагу Неша (ε настільки мало, що людського життя не вистачить на перевірку відмінності ε-рівноваги Неша від рівноваги Неша). На рис. 2 наведені дії гравців на першому ходу в цьому профілі стратегій. Зліва для будь-якої стартовою комбінації двох карт вказані перші дії дилера (зелена клітка - «підвищувати», червона - «скидання»), праворуч наведено відповідь другого гравця, якщо дилер на першому ходу підвищив ставку (зелений колір - «підвищувати», синій - « зрівнювати », червоний -« скидання », змішані кольори відповідають можливості змішувати з різними можливостями кілька своїх стратегій). В цьому профілі дилер дуже часто блефує - підвищує ставку з поганою картою, а другий гравець досить часто змушений скидати свою карту, не будучи в силах розпізнати, блефує дилер. За рахунок цього дилер на довгій дистанції обігрує другого гравця.

Мал. 2. Оптимальні дії гравців на першому ходу. Кожна клітина таблиці відповідає одному з 169 варіантів кишенькової пари: в кожної масті 13 карт, при цьому в покері конкретна масть не важлива, а важливо лише, однією чи масті кишенькові карти (це збільшує шанси на складання флеша); одномасних парам відповідають клітини над головною діагоналлю (що йде з лівого верхнього кута в правий нижній) таблиці (Suited), різномастих - клітини під цією діагоналлю. Квітами позначені дії гравців: червоний - скинути карти, синій - зрівняти ставку, зелений - підняти ставку; змішані кольору відповідають складним варіантів, при яких гравець може з деякими можливостями приймати різні рішення. Зліва - перший хід першого гравця, праворуч - хід у його опонента в тому випадку, якщо перший гравець підняв ставку. Малюнок з обговорюваної статті в Science

У розглянутій нами грі можуть існувати й інші ε-рівноваги Неша. Однак слід мати на увазі, що в грі з нульовою сумою , Якої і є покер, все рівноваги Неша приносять гравцям однакові платежі. Тому знаходження одного рівноваги Неша означає, що знайдені стратегії, використовуючи які гравці можуть гарантувати для себе найкращий можливий результат.

Чи можна заробити, граючи знайдену стратегію? Так, якщо вміти відтворювати дії, які наказує здійснювати стратегія в кожній позиції. Навряд чи на це буде здатна людина - не вистачить пам'яті. А ось проти комп'ютера грати в лімітний хедз-ап тепер марно. Швидше за все, це означає, що скоро лімітний хедз-ап покер пропаде з покерних сайтів - буде дуже складно перевіряти, що людина не використовує спеціальні програми, які допомагають знайти оптимальні відповіді. Однак гравцям в покер засмучуватися рано. Навіть якщо про всі варіації лімітного покеру одного разу все стане відомо, чи залишиться безлімітний покер (можна робити ставки будь-якого розміру), який не є кінцевою грою. Через це вирішити безлімітний покер модифікаціями алгоритму зворотного індукції вже навряд чи вийде ...

Джерело: M. Bowling, N. Burch, M. Johanson and O. Tammelin. Heads-up limit hold'em poker is solved // Science. 2015. V. 347. P. 145-149.

Див. також:
А. В. Захаров «Теорія ігор в суспільних науках» - хороший підручник з теорії ігор.

Дмитро Дагаєв
«Елементи»