Вчені прорахували покер

Навчання 02 серпня 2022 Перегляди: 62

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

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

Техаський холдем (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.

Див. також:

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

Дмитро Дагаєв