Всем привет! Меня зовут Григорий Дядиченко, и я технический продюсер. А в прошлом я был профессиональным игроком в покер. Сейчас я решил сделать на 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
}

И проверки на Стрит, Флеш, СтритФлеш и Роял-флеш проще сделать без битовых операций. А просто через код.

    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, немного комбинаторики и математики. А я пойду дальше дописывать весь проект, чтобы уже потом сделать туториал по полной сборке однопользовательского покера с ботами. Мне кажется боты тоже будут интересной задачкой и кому-то могут пригодится, как иллюстрация, как их можно делать.