Натягиваем сетевые poker Room’ы: кодинг покер-бота - логика принятия решений

Сегодня мы расскажем тебе о создании своего покер-бота. Зачем? Во-первых, это интересно — проектировать и писать своего бота, состоящего из множества разных компонентов. Во-вторых, это познавательно — в процессе можно узнать о математической стороне покера и кое-что о проектировании высоконагруженных систем.

Что есть покер?

В отличие от шахмат, покер — игра с неполной информацией. То есть, игроки не знают, какая карта есть на руках у оппонентов — они могут это лишь предполагать с определенной степенью вероятности. Правила покера просты — выигрывает тот, у кого на руках сильнейшая комбинация, составленная из его карт и тех, что на столе, или последний оставшийся игрок, если все остальные сбросили. Всего в покере десять комбинаций: Роял-флеш, Стрит-флеш, Каре, Фулл-хаус, Флеш, Стрит, Сет/Трипс/Тройка, Две пары, Одна пара, Старшая карта.
Существует много разных видов покера. Здесь мы будем рассматривать Texas Holdem No Limit Poker, он же турнирный покер.

Простая схема покер-бота

Из каких блоков будет состоять наш робот? Рассмотрим по пунктам:

• Logic — Блок логики принятия решений (Fold, Call, Raise)
• Negotiator — Блок взаимодействия с программой для игры в покер;
• Statistics — Блок обработки и накопления статистики по игрокам.

Из Negotiator в Logic поступает информация о текущих действиях на столе. Из Logic в Negotiator — информация о своих действиях, которые нужно совершить (сделать Fold, Call или Raise). Из Negotiator в Statistics — информация о действиях игрока за столом для последующей обработки и хранения. Из Statistics в Logic — информация о статистических данных игроков.

Принятие решений в покере

Как правило, во время каждого хода игрок может принять три решения: Fold, Call, Raise. Есть еще All-in — когда денег для продолжения игры нет, и придется поставить все. Существует множество алгоритмов принятия решений: DIVAT анализ, дерево решений, различные эмпирические алгоритмы (кстати, большинство из этих алгоритмов используют вероятность выигрыша). Мы будем использовать в принятии решений беспристрастную математику, а точнее — теорию вероятности.

Примечание о теории вероятности

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

Математическая сторона принятия решений в покере

Формула принятия решений в покере чрезвычайно проста: p*pot = win, где p — вероятность выигрыша с текущими картами (на руках и на столе), pot — размер банка на момент принятия решения, win — выигрыш, который мы получим, если будем разыгрывать множество партий с этими картами.

Если win < bet_cur, то Fold

Если bet_cur + SB > win >= bet_cur, то Call (или Check)

Если win >= bet_cur + SB, то Raise (или Bet)

bet_cur — это все деньги, которые мы положили в банк за текущую игру (НЕ только за один круг торговли), плюс те деньги, которые нужно сейчас поставить. Пояснения к bet_cur:

Если на первом круге торговли мы поставили всего $10, а на втором круге мы должны поставить $5, и в этот момент мы принимаем решение, то bet_cur равно $15 (10+5). SB (Small Blind) — размер малого блайнда «(первая ставка вслепую — прим. ред.)». Это значение прибавляется к bet_cur во втором условии, так как мы можем увеличивать ставку только на число, кратное малому блайнду. Следовательно, если win > bet_cur, но при этом win < bet_cur + SB, то увеличивать ставку нам не выгодно, так как пришлось выставить bet_cur + SB. BB (Big Blind) - размер большого блайнда.
Стоит также добавить, что эта формула может использоваться только в компьютерной игре — в жизни за столом вряд ли будет возможность самому вычислять вероятность выигрыша и все это считать. Поэтому при реальной игре используется вычисление аутов (outs) и одсов (odds). Существуют таблицы для облегчения этих вычислений, которые можно найти в любой книжке по покеру и/или в интернете.

Объяснение формулы

Из этой формулы мы получаем математическое ожидание выигрыша (в нашей формуле это win). Иначе говоря, разыгрывая много раз игру с такой вероятностью (с такими же картами у нас на руках и на столе) и таким банком, мы получим такой выигрыш. Следовательно, чтобы оставаться в плюсе, мы должны ставить не больше этого выигрыша (на рисунке это bet1). Если поставим больше, то окажемся в минусе — выиграем меньше, чем будем ставить (на рисунке это bet2). Стоит сделать замечание к формуле — так как покер-румы берут комиссию с каждого банка, то нужно размер банка уменьшить на величину этой комиссии. Формула с комиссией будет такова:

p*pot*0,91 = win

Расчет вероятности

Если размер банка и размер ставки величины вполне известны, то как узнать вероятность выигрыша? На этот вопрос есть несколько ответов:

1. Узнать, сколько комбинаций хуже нашей текущей руки, и разделить это число на количество комбинаций;
2. Промоделировать несколько сотен тысяч раз ситуацию со своими картами на руках и на столе и со случайными картами у оппонентов, затем разделить число выигрышных раундов на их общее количество (набор методов, в которых используются случайные числа и большое число повторений, называются методами Монте-Карло. Да, да название произошло от знаменитого казино в Лас-Вегасе).

Плюс первого метода — самая высокая точность. Минусы — большое потребление памяти и сложность предварительного расчета. Так как всего комбинаций может быть 2.598.960 (число сочетаний 5 карт из 52), в памяти это будет занимать примерно 10Мб (из расчета, что на одну комбинацию отводится 4 байта для хранения вероятности). Несмотря на то, что это значение уменьшится, поскольку некоторые комбинации будут одинаковы по силе и их можно будет свести в одну (за счет того, что масти в этих комбинациях не важны), этот метод мы пока рассматривать не будем, а перейдем к следующему.

Плюс второго метода — простота реализации.

Минусы — при малом числе раундов не очень точен, а большое число раундов требует больше ресурсов процессора.

Кодируем расчет вероятности

На данный момент можно найти множество библиотек для расчета вероятности выигрыша. Есть как бесплатные, так и платные версии. А мы изобретем свой велосипед. Почему? Чтобы разобраться в этом вопросе детальнее и из-за желания сделать полностью своего бота. Здесь я дам краткие пояснения к коду. Он написан на Java и снабжен документацией в виде JavaDoc, так что ты без труда сможешь разобраться в нем.

Замечания по кодированию карт:

Всего 52 карты = 4 масти x 13 карт каждой масти. Масть текущей карты = <порядковый номер карты>/4 (/ — целочисленное деление).

Достоинство текущей карты = <порядковый номер карты>%13 (% остаток от деления). Собственно, у нас должно быть 10 функций по определению комбинации. Назовем их так:

isHighCard, isOnePair, isTwoPair, isSet, isStraight, isFlush, isFullHouse, isQuads, isStraightFlush, isRoyalFlush.

Объединяет эти функции следующее — на входе подается набор карт, а на выходе — число от -1 до 12, где -1 — комбинация не найдена, от 0 до 12 — старшая карта в комбинации. 0 это двойка, 1 — тройка, и так до 12 — туз. Масть не важна. Набор карт может быть любой длины — от 1 до 7. Это сделано для того, чтобы можно было легко рассчитать вероятности и в пре-флопе (когда карты на стол еще не положили, но раздали карты игрокам), и в терне и ривере (когда на стол положили четыре и пять карт соответственно). То есть теперь нам нужно будет дать функции список всех карт, которые лежат на столе и у игрока, а функция из этого набора карт выделит комбинацию.

Чтобы оптимизировать определение комбинаций, мы сделаем следующее:

1. Упорядочим комбинации по убыванию достоинства карт;
2. Разделим входной массив карт на три: массив с достоинствами карт, массив с мастями карт и массив с количеством карт каждой масти.

Эти действия будет выполнять функция sortHand. Входной параметр — массив hand, в котором хранится список карт. Выходные параметры — массивы card (достоинства карт), suite (масти карт), suiteCount (количество карт каждой масти). В первой части функции происходит простая сортировка заменой (можно заменить ее на быструю сортировку). Тут есть маленький нюанс — сортируются не сами карты, а их достоинства. Чтобы узнать достоинство карты, нужно узнать остаток от деления на 13. Дальше, если достоинства карт одинаковы, то проверяем, чтобы карты с большим порядковым номером (карты, у которых номер масти больше) были «левее» карт с меньшим номером. После сортировки вычисляем достоинства карт (массив card), масти карт (массив suite) и количество карт каждой масти (массив suiteCount).

Функция сортировки массива карт

void sortHand(int[] hand, int[] card,
int[] suite, int[] suiteCount) {
for (int i = 0; i < hand.length; i++) {
for (int j = 0; j < hand.length - 1; j++) {
int t;
if (hand[j] % 13 < hand[j + 1] % 13) {
t = hand[j + 1];
hand[j + 1] = hand[j];
hand[j] = t;
}
if ((hand[j] % 13 == hand[j + 1] % 13) &&
(hand[j] < hand[j + 1])) {
t = hand[j + 1];
hand[j + 1] = hand[j];
hand[j] = t;
}
}
}
for (int i = 0; i < hand.length; i++) {
card[i] = hand[i] % 13;
suite[i] = hand[i] / 13;
suiteCount[suite[i]]++;
}
}

Рассмотрим алгоритмы определения комбинаций (код приводить не буду, так как он достаточно тривиален и его всегда можно найти на диске):

isHighCard

Возвращаем первую карту массива.

isOnePair

Ищем две одинаковые карты, идущие подряд, и возвращаем достоинство этих карт.

isTwoPair

Ищем две одинаковые карты, идущие подряд, ищем еще две одинаковых карты и из двух достоинств этих карт возвращаем максимальное.

isSet

Ищем три одинаковые карты, идущие подряд, и возвращаем достоинство этих карт.

isStraight

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

isFlush

Проверяем, чтобы было пять карт одной масти, и возвращаем достоинство старшей карты этой масти.

isFullHouse

Ищем три карты одного достоинства и еще две одинаковые карты. Возвращаем достоинство трех карт.

isQuads

Ищем две карты одного достоинства, идущие подряд. Возвращаем достоинство этих карт.

isStraightFlush

Проверяем, чтобы было пять или более карт одной масти, и чтобы эти карты шли по порядку. Возвращаем достоинство старшей карты.

isRoyalFlush

Проверяем, чтобы в комбинации были Туз, Король, Дама, Валет, 10, 9 одной масти. Возвращаем 12 (порядковый номер достоинства туза).

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

Функция определения силы комбинации

int getCombination(int[] hand, int[] board) {
int[] allCard;
if ((board == null) || (board.length == 0)) {
allCard = new int[hand.length];
System.arraycopy(hand,0,allCard,0,hand.length);
} else {
allCard = new int[hand.length + board.length];
System.arraycopy(hand,0,allCard,0,hand.length);
System.arraycopy(board,0,allCard,hand.length,
board.length);
}
int[] card = new int[allCard.length];
int[] suite = new int[allCard.length];
int[] suiteCount = new int[4];
sortHand(allCard, card, suite, suiteCount);
if (isRoyalFlush(card, suite, suiteCount) != -1) {
return 117;
}
int result = isStraightFlush(card, suite,
suiteCount);
if (result != -1) {
return 104 + result;
}
result = isQuads(card);
if (result != -1) {
return 91 + result;
}
result = isFullHouse(card);
if (result != -1) {
return 78 + result;
}
result = isFlush(card, suite, suiteCount);
if (result != -1) {
return 65 + result;
}
result = isStraight(card);
if (result != -1) {
return 52 + result;
}
result = isSet(card);
if (result != -1) {
return 39 + result;
}
result = isTwoPair(card);
if (result != -1) {
return 26 + result;
}
result = isOnePair(card);
if (result != -1) {
return 13 + result;
}
return isHighCard(card);
}

Далее сделаем функцию, которая возвращает абсолютную силу карточной комбинации (я назвал ее getCombination). Всего таких разных по силе комбинаций будет 118: девять комбинаций со старшими картами (по 13 старших карт в каждой комбинации), и одна комбинация без старшей карты (флеш-рояль, в котором старшая карта — всегда туз) — 9x13+1=118. Хотя в комбинации «две пары» может быть только 12 старших карт (двойка в этой комбинации не может являться старшей), чтобы не нарушать порядок, мы это не учитываем. Эта функция нужна для последующего удобного сравнения комбинаций между собой — она возвращает число, и чем оно больше, тем сильнее комбинация.

Название карт в покере

Карта записывается двумя латинскими символами. Первый символ — достоинство карты, второй — масть. Карты от 2 до 9 так и записываются. T — десять (хотя иногда и просто 10), J — валет, Q — дама, K — король, A — туз. Трефы — c, пики — s, бубны — d, червы — h.

Как видно из кода, сначала функция складывает карты на руках и карты на столе в один массив, потом сортирует его, а далее по порядку определяет комбинации.

Определение идет от сильнейшей комбинации (флеш-рояль) к слабейшей (старшая карта). Чтобы комбинации отличались друг от друга, они имеют область действия — набор значений карт, находящихся в этой комбинации. Так, комбинации High card (старшая карта) соответствуют значения от 0 до 12, где 0 — это High card со старшей «двойкой», а 12 — со старшим тузом. А комбинации «пара» соответствуют значения от 13 до 25, где 13 — «пара» со старшей «двойкой», а 25 — со старшим тузом.

И, наконец, сделаем функцию для опреде ления вероятности выигрыша (getProbabilityOfWin). Параметры этой функции следующие: свои карты, карты на столе (если есть) и количество игроков. Далее все просто — раздаем случайные карты остальным игрокам, выкладываем карты на стол (если их еще нет или не хватает) и проверяем комбинации. Если выиграли мы, то увеличиваем количество выигранных раундов на 1 (или, если есть еще игроки с такими же картами, то на 1/<количество этих игроков + 1>).

Маленькое замечание по моделированию: карты игрокам лучше выдавать случайно, а не мешать колоду, а потом выдавать, так как в первом случае будет быстрее.

Алгоритм моделирования

1. Раздать случайные карты игрокам;
2. Положить случайные карты на стол (если на столе еще не пять карт);
3. Сравнить свою комбинацию с комбинациями других игроков;
4. Если наша комбинация лучшая, то прибавляем к количеству выигранных раундов 1/<количество игроков с такой же комбинацией>;
5. Повторяем шаги 1-4 нужное количество раз;
6. Вероятность выигрыша равна <кол-во выигрышных раундов>/<общее кол-во раундов>. К коду я приложил unit-тесты, так что можно сразу проверить работоспособность всех методов.

Заключение

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

Промоделировав ситуацию с несколькими игроками и одинаковыми картами, можно заметить, что с увеличением количества игроков вероятность выигрыша уменьшается. Все правильно: чем больше игроков, тем больше вероятность, что у оппонентов карты будут лучше, чем у нас. Есть и радостная новость — все это уравнивается размером банка, поскольку он тоже будет больше. Если вспомнить формулу (p*pot = win), то получим уменьшение p с увеличением pot, то есть величина win остается неизменной. Если ты будешь использовать величину p в игре без учета размера банка, то ставь количество игроков равным 2, чтобы этот параметр не влиял на расчет. На этом я предлагаю на сегодня закруглиться, а если тебе (не)понравилось и ты (не)желаешь продолжения темы кодинга покерных ботов в следующих ][ — присылай свои отзывы мне и редактору рубрики (alexander@ real.xakep.ru). Если ты, господин наш, читатель, изъявишь свое желание, то в следующем номере мы опишем несколько алгоритмов для принятия решений и сделаем симулятор игры в Texas Holdem No Limit Poker, в котором будут играть эти покерные алгоритмы.

Links

Рекомендую почитать в вики статьи о покере, теории вероятности и математическом ожидании, посетить pokerai.org — лучший сайт о покерном AI, а также почитать цикл статей о создании покер-бота на www.codingthewheel.com

Функция определения силы комбинации

int getCombination(int[] hand, int[] board) {
int[] allCard;
if ((board == null) || (board.length == 0)) {
allCard = new int[hand.length];
System.arraycopy(hand,0,allCard,0,hand.length);
} else {
allCard = new int[hand.length + board.length];
System.arraycopy(hand,0,allCard,0,hand.length);
System.arraycopy(board,0,allCard,hand.length,
board.length);
}
int[] card = new int[allCard.length];
int[] suite = new int[allCard.length];
int[] suiteCount = new int[4];
sortHand(allCard, card, suite, suiteCount);
if (isRoyalFlush(card, suite, suiteCount
) != -1) {
return 117;
}
int result = isStraightFlush(card, suite,
suiteCount);
if (result != -1) {
return 104 + result;
}
result = isQuads(card);
if (result != -1) {
return 91 + result;
}
result = isFullHouse(card);
if (result != -1) {
return 78 + result;
}
result = isFlush(card, suite, suiteCount);
if (result != -1) {
return 65 + result;
}
result = isStraight(card);
if (result != -1) {
return 52 + result;
}
result = isSet(card);
if (result != -1) {
return 39 + result;
}
result = isTwoPair(card);
if (result != -1) {
return 26 + result;
}
result = isOnePair(card);
if (result != -1) {
return 13 + result;
}
return isHighCard(card);
}

О законности создания покер-ботов

По законам РФ и других государств создание и использование покер-ботов (и ботов для других игр) не запрещено. А по правилам всех известных мне покер-румов — запрещено. Что это значит? Если ты попался на использовании бота, то самое страшное, что тебе грозит — это бан аккаунта и списание с него всех средств. Все. Никаких штрафов, повесток в суд, блокировки кредитки и т.д. не последует. Кстати, практически во всех покер-румах разрешается использование «помощников» в игре — различных калькуляторов и программ для сбора статистики.