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

Сразу оговорюсь, что я в покер не играю, и знаю его хуже чем те, кто играет свои первые партии в жизни. Но может это не так уж и важно?

Рассматриваю тот покер, где в колоде 52 карты: 2-10, В, Д, К, Т и 4 масти. Вероятно это Техасский Холдем. На столе в последнем круге пять карт, и по две карты у игроков.

При написании программы расчетов использовался проект https://github.com/lvandeve/oopoker, из него были взяты модули card.h/cpp & combination.h/cpp - так я сумел обойти необходимость знать нюансы комбинаций покера.

Прикрепленная моя программа выглядит вот так:

Что здесь что обозначает и почему именно так, это нужно вчитываться в смыслы статьи. Итак, как здесь что считается...

Простейший абстрактный случай - все всегда доигрывают

Сначала рассмотрим простейший случай, если все расклады доигрываются до раскрытия. Описание этого случая примитивно, и не достоверно для практики, но важно его понимание для дальнейших шагов.

Колода это выборка с изъятием, из них при начальном раскладе известны 5 карт - 3 на столе и 2 на руках, и 47 не известны. У каждого из соперников есть две неизвестных карты. При последующих кругах на стол добавляются еще две карты, итого становится известно о 7 картах.

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

При таких генерациях, получится, что если было N - количество сгенерированных партий, и W из них выигрышных, тогда W/N - вероятность выигрыша нашего обсчитываемого расклада.

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

Примерно таким алгоритмом:

using ListCards = vector<IdxCard>; // IdxCard: int 0..51

struct ResProb {
    int cAll = 0;
    int cWin = 0;
    int cLoss = 0; // cAll - cWin - cLoss = кол-во ничьих

    double probWin() const { return FDIV(cWin, cAll); }
    double probLoss() const { return FDIV(cLoss, cAll); }
};

ResProb calcProbability(
        Deck& deck, // колода с механизмом изъятия
        const ListCards& myHand, // карты у меня на руках
        const ListCards& srcDesk, // карты на столе, пока здесь 3 штуки
        int cInterate = 1000) {

    ResProb r;

    for (; r.cAll < cInterate; ++r.cAll) {
        int c = calcOneRandomVariant_genAlienAndDesk(
                   deck, myHand, srcDesk, check);
        if (c > 0)
            ++r.cWin;
        else if (c < 0)
            ++r.cLoss;
    }

    return r;
}

// этот класс представляет собой колоду с изъятием.
struct Deck {

    ListCards residueDeck;

    // изъять одну случайную карту
    IdxCard takeRandom();
    // изъять несколько случайных карт
    ListCards takeRandomCount(int cnt);

    // вернуть в колоду карту
    void recall(IdxCard card);
    // вернуть в колоду несколько карт
    void recallList(const ListCards& cards);
};

// соединяет два множества карт рука и стол, и считает
//  лучшу покерную комбинацию
Combination getConcatCombo(
        const ListCards& cards1, const ListCards& cards2) {

    vector<Card> nativeCards;
    nativeCards.reserve(cards1.size() + cards2.size());

    for (const IdxCard& card: cards1)
        nativeCards.push_back(Card(card));

    for (const IdxCard& card: cards2)
        nativeCards.push_back(Card(card));

    // вызов функции из проекта oopoker:
    //   - расчет лучшей комбинации на основе расклада
    Combination res;
    getCombo(res, nativeCards);
    return res;
}

// достраивает srcDesk до 5 и сравнивает результат.
int calcOneRandomVariant_genDesk(
        Deck& deck,
        const ListCards& myHand,
        const ListCards& alienHand,
        const ListCards& srcDesk) {

    int szSrcDesk = srcDesk.size();

    // 1. достраивает desk до 5, если desk меньше
    ListCards newDesk(srcDesk);
    while (newDesk.size() < 5)
        newDesk.push_back(deck.takeRandom());

    // 2. расчет комбинаций
    Combination myCombo = getConcatCombo(myHand, newDesk);
    Combination alienCombo = getConcatCombo(alienHand, newDesk);

    // 3. возвращает карты в колоду - на выходе колода
    //    будет как на входе
    for (int ii = szSrcDesk; ii < newDesk.size(); ++ii)
        deck.recall(newDesk.at(ii));

    // 4. сравнение комбинаций
    //      - вызов функции из проекта oopoker
    return compareCombo(myCombo, alienCombo);
}

// генерирует расклад противника,
//   и после вызывает генерацию расклада стола,
//   а после сравнивает результат с нашим раскладом
int calcOneRandomVariant_genAlienAndDesk(
        Deck& deck,
        const ListCards& myHand,
        const ListCards& srcDesk) {

    // 1. генерирует расклад противника
    ListCards alienHand = deck.takeRandomCount(2);

    // 2. достраивает стол
    int r = calcOneRandomVariant_genDesk(
              deck, myHand, alienHand, srcDesk);

    // 3. возврат в колоду противника
    deck.recallList(alienHand);

    return r;
}

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

Если нагенерировать много-много случайных начальных раскладов, и для каждого посчитать такую вероятность, то можно нарисовать график распределения вероятностей выигрыша - для наглядности, и для того, чтобы посмотреть на это и подумать "и как это раньше играли в такое без компьютеров":

Кривая получилась не симметричная и несколько ломанная, несмотря на то, что было обсчитано порядка 100тыс раскладов. Но и суть раскладов это то же нечто дискретное и не упорядоченное. Генерацию этого графика можно увидеть здесь.

Повышаем точность расчета: отказ соперника от игры

Соперник иногда отказывается от игры при своем текущем раскладе. Это происходит когда у него на руках расклад с низкой вероятностью выигрыша, или может по причинам предрассудков или коварных планов обмануть соперников.

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

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

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

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

Замечу только, что количество вариантов начальных комбинаций это 52*51*50*49*48 = ~300млн. Это не большое количество для компьютеров, можно сохранить предрасчитанные варианты в памяти и использовать для дальнейших расчетов. Так же можно уменьшить размер индекса за счет частичной сортировки - первые две сортируем, и последующие три сортируем раздельно. И за счет нивелирования влияния мастей. Но тут нужно очень задуматься какая точная формула для расчета количества вариантов.

Расчет с отбрасыванием части раскладов противника представлен в исходниках в функции calcPseudoRealProbability. Там используется второй раз вложенный вызов calcProbability для определения вероятности расклада противника. Функция получилась вроде не большая, но заморочнная по смыслу, поэтому сюда ее напрямую не вставляю, но думаю особо интересующиеся и дотошные разберутся.

В общем, в прикрепленной программе в закладке "Расчет" можно указать любую вероятность, при ниже которой противник якобы отказывается играть, и считать с учетом отбрасывания таких вероятностей.

Еще больше уточняем вероятность выигрыша начального расклада

Таблиц с сохраненными реальными играми у меня нет, а все дальнейшие шаги они основываются уже на статистике игры, а не просто комбинаторных свойствах колоды карт.

Но если бы были такие таблицы, то можно... Во первых первое простое уточнение - сколько именно раскладов отказывается от игры.

Количество раскладов в игре это количество участников. Суммируем их по всем играм, и обозначим буквой P (persons).

Подсчитываем количество раскладов с отказом без ставки - так же по отдельности каждого игрока и во всех играх, и обозначим буквой C (cancellation).

Тогда вероятность отказа будет C/P. Эта цифра это не сама абстрактная вероятность отказа!!! Это площадь графика распределения вероятности приведенного выше. Отсчитываем такую площадь на том графике с левой стороны, и получаем точку на графике. И это уже и будет тот уровень абстрактной вероятности, при котором в среднем игроки отказываются от игры.

Такой расчет можно произвести в прикрепленной программе на закладке "Распределение". Выставить вероятность реальных отказов, и по нажатию "Сделать график распределения" и тогда в том числе будет рассчитан уровень таких абстрактных вероятностей. И после это значение применять на первой закладке "Расчет" для обсчета раскладов.

Еще чуть-чуть уточняем и залезаем в дебри распределений

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

Если собрать все отказы в виде распределения по вероятностям выигрыша, и наложить на график распределения всех комбинаций вероятностей выигрыша, то получим наверное нечто подобное этому:

График распределения отказов накладывается умноженным на вероятность всех отказов от всех раскладов.

И тогда, при генерации расклад противника оценивается на отсечение как вероятность, что-то типа такого:

bool checkCancelAlienCards(
        const Distrib& distrWin,
        const Distrib& distrCancel,
        double allProbCancel,
        double probAlienWin) {

    double denWin = distrWin.getDensityByProbabilityX(probAlienWin);
    if (!denWin)
        return false;

    double denCancel = distrCancel.getDensityByProbabilityX(probAlienWin);
    double probOfCancel = (denCancel * allProbCancel) / denWin;

    if (FDIV(rand(), RAND_MAX) <= probOfCancel)
        return true; // вероятностным образом отбросили расклад противника

    return false;
}

Для этого кусочка кода, описание класса Distrib здесь, но сам этот метод не включен в исходники. Только здесь

Деньги вместо вероятностей

Здесь и дальше я буду делать только теоретические рассуждения и описания, не вдаваясь в детали. Программной части для этих этапов я не делал.

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

Чтобы избежать проигрыша в деньгах, нужно чтобы генерационная программа суммировала не только вероятности, или даже вместо вероятностей, нужно просто суммировать предполагаемые выигрыши-проигрыши в деньгах.

И тогда средняя сумма, которая будет состоять из суммированных сумм деленных на количество таких сумм, будет средним выигрышем-проигрышем на игру.

Опять же, на основании таблиц сохраненных игр, нужно строить распределения ставок в зависимости от успешности карт противника. И при генерации вариантов игры, сгенерированную комбинацию противника заменять на сумму денег соответствующую его успешности карт.

Величину денег можно считать не в абсолютной величине, а в относительной от начальной ставки. И соответственно суммарный выигрыш-проигрыш будут в относительных величинах.

Что дальше? - Моделирование процесса игры

Дальше нужно делать генерацию процесса игры, а не только начальных раскладов.

Нужно в предыдущем процессе моделирования, после сгенерированного расклада противника, от которого виртуальный противник не отказался, от него начинать генерировать последующие возможные действия противника.

Опять же, нужны таблицы сохраненных игр - реальных или тестовых приближенных к реальности - и из них считать, с какими вероятностями при каких раскладах происходят события отказа от игры, поддержания ставки и повышения ставки. И с такими вероятностями производить эти события в этой симуляции, согласно генератору случайных величин.

Стратегия нашего хода

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

В коментариях подсказали, что это дерево решений. Но в отличии от классического дерева решений, здесь его нужно отстраивать на каждый шаг заново. Мне это напомнило q-learning, но там то же значительные отличие от нужного здесь процесса.

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

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

У таких обсчетов возможные варианты развития событий это только генерации случайных ходов противника, и докладывание двух карт на стол. Здесь существенно меньше вариантов, чем обсчет от начального состояния, и потому это все же вроде реализуемо по объему вычислений на каждый из вариантов нашего хода.

Заключение

Здесь последние главы я делал не детально. Но в принципе при желании в подобном направлении не сложно проработать алгоритм до практической реализации. Используя только механизмы общего направления, без закладывания специальных стратегий покера. Такая реализация, это скорее муторная и объемная вещь, чем что-то сверхсложное. Реализация выигрывающей программы в покер для меня не является особым интересом, и в свободное время я лучше буду изобретать свои алгоритмы прогнозирования общего направления, чем покерного.

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

Но может так и со всеми выигрышными стратегиями под покер? Может быть что любые лучшие стратегии будут естественным следствием использования описанного в статье механизма? Может оно будет работать чуть подольше без таких стратегий, но тем не менее будет и местами даже качественней? Потому что просто посчитает вероятности...

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

В коментариях мне еще упоминули про оценку погрешности при подобных генерационных методах. И именно про оценку подобных методов у меня написано в предыдущей статье.