Определение комбинации в Техасском Холдеме
Всем привет! Меня зовут Григорий Дядиченко, и я технический продюсер. А в прошлом я был профессиональным игроком в покер. Сейчас я решил сделать на Unity пример проекта с покером, который выложу в опенсорс, когда я его доделаю. А пока хочется посмотреть на интересную задачку с определением сильнейшей комбинации в техасском холдеме. Разберём хеш-функции, битовые операции, поиск подмножеств определённой длинны из множества, биномиальный коэффициент и другое. Если вам интересна эта тема, то добро пожаловать под кат!
Немного о покере и о карьере в нём
Пока онлайн покер не был запрещён повсеместно я играл около 8-30 столов на покерном сайте. Играл я в финале по ставкам 0.25/0.5$ и зарабатывал на этом около 1000$ в месяц, что для студента было достаточно неплохо. И сыграл более 3 миллионов рук. Потом в какой-то момент в РФ всё стало запрещено, да и такой заработок хороший, но не предел мечтаний, так что я ушёл в программирование. Но периодически всё равно возвращаюсь к своему старому хобби. И да, конечно же. Не играйте в азартные игры на деньги, вы проиграете. Мне повезло за карьеру заработать больше 40 000$, но это был путь в 4 года, где я прочитал порядка 15 книг по покеру, очень много анализировал свою статистику и занимался этим сутками, прям как работой. Из плюсов покера, что понятия мат. ожидания, дисперсии и ряда задач комбинаторики я понимал на 100%, так как приходилось много такого оценивать.
Чтобы описать алгоритм определения для начала нам надо бы знать правила Техасского Холдема. Все правила я расписывать не буду. Нам лишь важно то, что наш алгоритм должен определять лучшую комбинацию из пяти карт в семи картах. Так как в Техасском Холдеме если вы дошли до того, что открыли карты, то играет пять карт на столе плюс две ваши. Ниже приведу таблицу комбинаций:
Покерной рукой или рукой мы будем называть комбинацию из пяти карт. С условиями задачи плюс-минус разобрались, теперь перейдём к алгоритмам.
Полный перебор
Он конечно же в этой задаче не подходит. Давайте оценим для разминки число способов выбрать 7 карт из колоды в 52 карты. В комбинаторике это число сочетаний. Сочетанием из n по k называется набор элементов k выбранных из n не учитывая порядок. Оно в свою очередь равно биномиальному коэффициенту. То есть формула у нас такая и многим знакомая:
где n — это 52 карты в колоде, k — 7 карт, которые мы из неё выбираем. И мы получаем подставив всё в формулу 133 784 560 комбинаций. Перебирать такое число комбинаций нет никакого смысла. Игроки просто заснут.
Идеальная хеш-функция
На такое решение я наткнулся в этом репозитории пока искал разные варианты реализации. Что такое Perfect Hash Function? Идеальная хеш функция — это хеш-функция, которая отображает отдельные элементы множества в ключи без пересечений. Что в свою очередь позволяет нам искать эти значения по ключу за O(1).
В случае с техасским наше множество это 133 784 560 комбинаций из 7 карт в колоде в 52 карты. В соответствие которым можно поставить разные покерные руки. Каждую комбинацию мы можем представить в виде ключа определив его через 52 битное представление:
Допустим на картинке у нас 5 пик, 7 пик, десять пик (для удобства записи в покере пишется как T), 5 червей, валет бубей, 4 крести и туз крести. То есть комбинация пара пятёрок.
С таким представлением каждому значению 52 битного представления руки будет соответствовать одна комбинация. То есть мы можем пред рассчитать больше 100 миллионов значений наших рук и выбирать из них за O(1). Звучит не очень хорошо по памяти. Только такое число 52-битных ключей будут занимать около 870 мегабайт памяти. А ещё соответствующие им значения рук + вес руки, чтобы рассчитать силу руки. Если у нас серверное решение конечно можно считать прям так, так как 1гб памяти на сервере обычно найти не проблема. Но лучше оптимизировать алгоритм.
Битовая математика
Продолжаем наше исследование. В поисках алгоритма оптимальнее я нашёл вот такую статью. Оно определено для 5-ти карточного покера, но мы же с вами уже знаем комбинаторику. Давайте прикинем. Если нам не важен порядок, то число комбинаций из 5-ти карт, если общее число карт равно 7 будет:.
Перебрать 21 вариант по 5 карт алгоритмом через битовую математику не особо долго. Так как сам алгоритм шустрый. Давайте и его разберём.
Тут так же битовое представление руки, но в немного другой форме.
У автора зачем-то добавлены лишние биты. Их можно не добавлять и получится новое 52 битное представление руки, только теперь мы ничего не знаем о мастях. Знаем сразу о числе карт и их старшинсве. Основной трюк этого представления заключается в том, что через операции mod (получение остатка от деления) на 15 мы можем легко одной операцией определить 6 видов рук.
Каре — остаток 1
Фулл хаус — остаток 10
Сет — остаток 9
Две пары — остаток 7
Пара — остаток 6
Старшая карта — остаток 5
Это в целом не так сложно доказать, так как у нас информация о числе карт хранится в 4-битах и при остатке от деления на 15 (а в данном случае такое число принимает значения от 0 до 15) мы всегда будем получать такие остатки. Так как 4 одинаковые карты всегда будут давать один блок, который даст остаток 0 (число 15, все 4 бита заполнены) и одну карту, которая не входит в этот диапазон. Можно так же проверить и все остальные комбинации
Но ведь это не все комбинации. Где стриты и флеши? В флеше и стрите очевидно не будет повторов. Так как чтобы карты были по порядку или одной масти, то там не должно быть пар. Поэтому мы запускаем доп. проверки, только если у нас получилась комбинация Старшая карта.
Добавим немного кода. Так как в игре по ряду причин мы вряд ли будем хранить руку в виде строки, как разбирают все примеры. Мы будем иметь структуру вроде.
public struct GameCard
{
public int Value;
public CardSuit Suit;
}где CardSuit
public enum CardSuit
{
Clubs = 0,
Diamonds = 1,
Hearts = 2,
Spades = 3
}И проверки на Стрит, Флеш, СтритФлеш и Роял-флеш проще сделать без битовых операций. А просто через код.
Detect Poker Combination
public static PokerCombination DetectCombination(List<GameCard> cards)
{
ulong handValue = 0;
Dictionary<int, int> cardValues = new Dictionary<int, int>();
foreach (var card in cards)
{
if (cardValues.ContainsKey(card.Value))
{
cardValues[card.Value]++;
}
else
{
cardValues[card.Value] = 0;
}
}
foreach (var cardValue in cardValues.Keys)
{
var cardsCount = cardValues[cardValue];
for (int i = 0; i < cardsCount; i++)
{
handValue += (ulong) Math.Pow(2, i) << cardValue * 4;
}
}
var normalizedValue = handValue % 15;
switch (normalizedValue)
{
case 1:
return PokerCombination.FourOfKind;
case 10:
return PokerCombination.FullHouse;
case 9:
return PokerCombination.ThreeOfKind;
case 7:
return PokerCombination.TwoPair;
case 6:
return PokerCombination.Pair;
}
bool isSameSuit = cards.TrueForAll(card => card.Suit == cards[0].Suit);
bool isOrdered = true;
int? tmpValue = null;
foreach (var cardValue in cards.OrderBy(card => card.Value))
{
if (tmpValue.HasValue)
{
if (cardValue.Value - tmpValue.Value != 1)
{
isOrdered = false;
break;
}
else
{
tmpValue = cardValue.Value;
}
}
else
{
tmpValue = cardValue.Value;
}
}
bool isHighAce = Constants.PokerSingleSuitCardsCount - 1 == tmpValue.Value;
if (isSameSuit)
{
if (isOrdered)
{
return isHighAce ? PokerCombination.RoyalFlush : PokerCombination.StraightFlush;
}
else
{
return PokerCombination.Flush;
}
}
else
{
if (isOrdered)
{
return PokerCombination.Straight;
}
else
{
return PokerCombination.HighCard;
}
}
}Чтож. Реализация написана. А теперь давайте проверим работает ли. Для этого напишем простенький тест.
using System.Collections.Generic;
using System.Diagnostics;
using UnityEngine;
using Debug = UnityEngine.Debug;
public class MockTest : MonoBehaviour
{
[SerializeField] private List<GameCard> _cards;
[ContextMenu("Test")]
public void TestMockData()
{
Stopwatch stopwatch = Stopwatch.StartNew();
var subsetsForSeat = CollectionsUtils.CombinationsRosettaWoRecursion<GameCard>(_cards.ToArray(), 5);
foreach (var subset in subsetsForSeat)
{
var log = "";
foreach (var card in subset)
{
log += $"Suit:{card.Suit} Value:{card.Value}\n";
}
log += $"Result: {HoldemRules.DetectCombination(subset)}";
Debug.Log(log);
}
Debug.Log(stopwatch.Elapsed.ToString());
stopwatch.Stop();
}
}
Итак, вот мы и получили наш тест. Задав 7 карт в инспекторе. Мы получили как и ожидается 22 лога (21 на комбинации и 1 на оценку времени).
Работает очень шустро. Так как за столом максимум 7 пользователей, то данная реализация уже подойдёт для продакшен решения. Конечно там есть, что оптимизировать, так как я не указал, что за метод такой CombinationsRosettaWoRecursion:
using System;
using System.Collections.Generic;
using System.Linq;
public class CollectionsUtils
{
private static IEnumerable<int[]> CombinationsRosettaWoRecursion(int m, int n)
{
int[] result = new int[m];
Stack<int> stack = new Stack<int>(m);
stack.Push(0);
while (stack.Count > 0)
{
int index = stack.Count - 1;
int value = stack.Pop();
while (value < n)
{
result[index++] = value++;
stack.Push(value);
if (index != m) continue;
yield return (int[])result.Clone();
break;
}
}
}
public static IEnumerable<List<T>> CombinationsRosettaWoRecursion<T>(T[] array, int m)
{
if (array.Length < m)
throw new ArgumentException("Array length can't be less than number of selected elements");
if (m < 1)
throw new ArgumentException("Number of selected elements can't be less than 1");
T[] result = new T[m];
foreach (int[] j in CombinationsRosettaWoRecursion(m, array.Length))
{
for (int i = 0; i < m; i++)
{
result[i] = array[j[i]];
}
yield return result.ToList();
}
}
}
Данный алгоритм был найден в Rosetta Code. На нём есть много прикольных решений задач на разных языках программирования. Я его чуть ухудшил переводом к List, так как не хочется тратить пока время на переделку для иллюстрации концепта. В финальном проекте уже приведу к нормальному виду.
Собственно всё. Остался всего один вопрос. А что если две одинаковые комбинации? Как решать делёжку или ничью? Самый простой способ просто взять, отсортировать карты игроков по старшинству и сравнить попарно. Таким образом получится узнать чья рука сильнее. Определив самую сильную комбинацию. Это уже дело техники так сказать.
В заключении
Спасибо за внимание! Надеюсь статья вам была полезна и интересна. И кому-то пригодится для реализации его проектов. Но помимо самой задачи мы прошлись по таким темам как BitShift, немного комбинаторики и математики. А я пойду дальше дописывать весь проект, чтобы уже потом сделать туториал по полной сборке однопользовательского покера с ботами. Мне кажется боты тоже будут интересной задачкой и кому-то могут пригодится, как иллюстрация, как их можно делать.