Содержание статьи
- Что есть покер?
- Простая схема покер-бота
- Принятие решений в покере
- Примечание о теории вероятности
- Математическая сторона принятия решений в покере
- Объяснение формулы
- Расчет вероятности
- Кодируем расчет вероятности
- Функция сортировки массива карт
- Функция определения силы комбинации
- Название карт в покере
- Алгоритм моделирования
- Заключение
- Links
- Функция определения силы комбинации
- О законности создания покер-ботов
Сегодня мы расскажем тебе о создании своего покер-бота. Зачем? Во-первых, это интересно — проектировать и писать своего бота, состоящего из множества разных компонентов. Во-вторых, это познавательно — в процессе можно узнать о математической стороне покера и кое-что о проектировании высоконагруженных систем.
Что есть покер?
В отличие от шахмат, покер — игра с неполной информацией. То есть, игроки не знают, какая карта есть на руках у оппонентов — они могут это лишь предполагать с определенной степенью вероятности. Правила покера просты — выигрывает тот, у кого на руках сильнейшая комбинация, составленная из его карт и тех, что на столе, или последний оставшийся игрок, если все остальные сбросили. Всего в покере десять комбинаций: Роял-флеш, Стрит-флеш, Каре, Фулл-хаус, Флеш, Стрит, Сет/Трипс/Тройка, Две пары, Одна пара, Старшая карта.
Существует много разных видов покера. Здесь мы будем рассматривать 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
Расчет вероятности
Если размер банка и размер ставки величины вполне известны, то как узнать вероятность выигрыша? На этот вопрос есть несколько ответов:
- Узнать, сколько комбинаций хуже нашей текущей руки, и разделить это число на количество комбинаций;
- Промоделировать несколько сотен тысяч раз ситуацию со своими картами на руках и на столе и со случайными картами у оппонентов, затем разделить число выигрышных раундов на их общее количество (набор методов, в которых используются случайные числа и большое число повторений, называются методами Монте-Карло. Да, да название произошло от знаменитого казино в Лас-Вегасе).
Плюс первого метода — самая высокая точность. Минусы — большое потребление памяти и сложность предварительного расчета. Так как всего комбинаций может быть 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. Это сделано для того, чтобы можно было легко рассчитать вероятности и в пре-флопе (когда карты на стол еще не положили, но раздали карты игрокам), и в терне и ривере (когда на стол положили четыре и пять карт соответственно). То есть теперь нам нужно будет дать функции список всех карт, которые лежат на столе и у игрока, а функция из этого набора карт выделит комбинацию.
Чтобы оптимизировать определение комбинаций, мы сделаем следующее:
- Упорядочим комбинации по убыванию достоинства карт;
- Разделим входной массив карт на три: массив с достоинствами карт, массив с мастями карт и массив с количеством карт каждой масти.
Эти действия будет выполнять функция 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/<количество игроков с такой же комбинацией>;
- Повторяем шаги 1-4 нужное количество раз;
- Вероятность выигрыша равна <кол-во выигрышных раундов>/<общее кол-во раундов>. К коду я приложил 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);
}
О законности создания покер-ботов
По законам РФ и других государств создание и использование покер-ботов (и ботов для других игр) не запрещено. А по правилам всех известных мне покер-румов — запрещено.
Что это значит? Если ты попался на использовании бота, то самое страшное, что тебе грозит — это бан аккаунта и списание с него всех средств. Все. Никаких штрафов, повесток в суд, блокировки кредитки и т.д. не последует. Кстати, практически во всех покер-румах разрешается использование «помощников» в игре — различных калькуляторов и программ для сбора статистики.