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

В этой статье мы будем рассматривать игры со скрытой информацией, с ветвистыми и глубокими деревьями решений.

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

Итак, что будем делать? Будем писать ботов и, со временем, средства их обнаружения.

И тут важно согласиться, что боты – это не всегда Зло. Боты – это лишь инструмент в руках Зла. Или Добра...

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

Настолки!? Да, многие настольные игры содержат скрытую информацию, в них зачастую есть Природа. Вариант хороший, я даже хотел остановиться на игре «Цитадели», но нашёл более простой для понимания, пусть и несуществующий в формате реальной игры)

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

Игра – это конфликт интересов

Начнём с определения сторон конфликта (игры) и выявления их мотивации.

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

Всё меняется, когда мы выходим на уровень выше и рассматриваем конфликт на уровне экосистемы вокруг игры.

Сторонами будут уже не только два друга-игрока. К ним добавится дилер, сдающий карты и работающий за почасовую плату. Добавится собственник заведения, где проводится игра, и также получающий за это плату. Оплатить работу дилера и «казино» конфетами не получится, налицо конфликт интересов. Друзья будут вынуждены оплатить реальными деньгами непрямое участие третьих лиц в игре. Это означает, что стоимость эмоций должна быть выше стоимости потраченных средств, чтоб игра была интересной. К счастью, Числовой покер именно такая игра.

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

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

Выглядит естественным желание профессионала передачи своих навыков за определённую плату новичкам-карьеристам. Также выглядит естественным желание успешных игроков формализовать свои выигрышные стратегии в виде свода правил (алгоритмов).

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

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

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

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

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

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

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

Задача нечестного игрока, использующего подсказчик, найти соперников со скиллами ниже, чем у используемого им подсказчика. В ход идут различные инструменты по определению уровня игры оппонента. И чем раньше будет определён тип (скилл) оппонента, тем быстрее будет подобран под него стиль игры, и тем быстрее оппонент лишиться своего стека. Но особо зарабатывающие и дерзкие незамедлительно попадут под пристальное внимание площадки! Поэтому и в нечестной игре также важно не выделятся, даже если есть возможности.

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

Супер-бот, выигрывающий всех, может жить без бана на пощадке вечно только в том случае, если он представлен на ней в единственном числе. Либо площадка будет достаточно пассивна (молода, неразвита, неэффективна), чтоб бороться с популяцией зарабатывающих клонов.

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

К чему стремимся

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

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

Core

Имеет смысл начать с ограничений, накладываемых изначально на абстрактную игру, которую мы собираемся «оцифровать». Игра будет дискретной, с конечным числом шагов. Это означает, что игры, в которых время является фактором для принятия решений, мы моделировать не сможем. Вот, пожалуй, и всё, что критически важно.

Дискретность сразу же наталкивает нас на возможность представления игры в виде конечного автомата (КА) – очень удобной для моделирования абстракции. Действительно, большинство знакомых нам (карточных) игр имеют внятные последовательные состояния, в которых игрокам необходимо принимать решения. Это относится как к игре в «Дурака», так и к выбранному нами Числовому Покеру.

Более того, игроки также будут иметь дискретные состояния, что означает возможность их моделирования конечными автоматами. На использовании конечных автоматов построен агентный подход и агентное моделирование. Моделируемый (исследуемый) процесс представляется в виде взаимодействующих КА (=агентов), с чёткими стратегиями поведения.

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

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

public interface Stateful<E extends Enum<E>> {
    void setState(E state);
    E getState();
}

public interface TransitionFunction<E extends Enum<E>, S extends Stateful<E>, C> {
    E apply(S stateful, int idx, C context);
}

public interface Guard<S extends Stateful<?>, C> {
    boolean check(S s, int idx, C c);
}

public interface Action<S extends Stateful<?>, C> {
    void apply(S stateful, C context);
}

public class HashMapStateMachine<Event extends Enum<Event>, State extends Enum<State>, S extends Stateful<State>, C> 
  implements StateMachine<Event, State, S, C> {

    private class TransitionData {
        Guard<S, C> guard;
        TransitionFunction<State, S, C> transitionFunction;
        Action<S, C> errorAction;

        public TransitionData(Guard<S, C> guard, TransitionFunction<State, S, C> transitionFunction, Action<S, C> errorAction) {
            this.guard = guard;
            this.transitionFunction = transitionFunction;
            this.errorAction = errorAction;
        }
    }

    private final Map<State, Map<Event, TransitionData>> transitions = new HashMap<>();

    @Override
    public HashMapStateMachine<Event, State, S, C> addTransition(State src,
                                                                 Event event,
                                                                 Guard<S, C> guard,
                                                                 TransitionFunction<State, S, C> transitionFunction,
                                                                 Action<S, C> errorAction) {
        transitions.computeIfAbsent(src, s -> new HashMap<>())
                .put(event, new TransitionData(guard, transitionFunction, errorAction));
        return this;
    }

    @Override
    public void apply(S stateful, Event event, int idx, C context) {
        State state = stateful.getState();
        Map<Event, TransitionData> destinationsByEventMap = Optional.ofNullable(transitions.get(state))
                .orElseThrow(() -> new RuntimeException("The state " + state + " is not registered as source for event=" + event + " with idx=" + idx + "\nstateful=" + stateful + "\ncontext=" + context));
        TransitionData transitionData = Optional.ofNullable(destinationsByEventMap.get(event))
                .orElseThrow(() -> new RuntimeException("The state " + state + " does not accept event " + event + " with idx=" + idx + "\nstateful=" + stateful + "\ncontext=" + context));
        if (transitionData.guard.check(stateful, idx, context)) {
            State dest = transitionData.transitionFunction.apply(stateful, idx, context);
            stateful.setState(dest);
        } else {
            transitionData.errorAction.apply(stateful, context);
        }
    }
}

Посмотрим, что умеет этот код, и это довольно стандартные вещи: проверять валидность перехода и устанавливать целевое состояние сущности Stateful. Видим, что состояния и события ограничены перечислимым множеством имён (Enum), что даст нам в будущем преимущества над, например, строковыми типами. Об этом позже.

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

public class Feature<E, S extends Stateful<? extends FeaturedState<S>>> {

    private final Enum<?> name;
    private final Function<S, Descriptor<E>> descriptorsFunc;

    public Feature(Enum<?> name, Function<S, Descriptor<E>> descriptorsFunc) {
        this.name = name;
        this.descriptorsFunc = descriptorsFunc;
    }

    public Enum<?> name() {
        return name;
    }

    public Descriptor<E> descriptor(S stateful) {
        return descriptorsFunc.apply(stateful);
    }

    public E value(S stateful) {
        return descriptorsFunc.apply(stateful).value();
    }
}

public class Descriptor<T> {
    private final Enum<?> name;
    private final T value;

    public Descriptor(Enum<?> name, T value) {
        Objects.requireNonNull(value);
        this.name = name;
        this.value = value;
    }

    public Enum<?> name() {
        return name;
    }

    public T value() {
        return value;
    }

    @Override
    public String toString() {
        return name.name() + ": " + value;
    }
}

Класс Feature умеет на основе сущности Stateful вычислять значения описателей (класс Descriptor) текущего состояния. Описатели имеют внутри себя имя и значение.

В коде, который относится к этой статье, классы Feature и Descriptor совершенно не используется. Именованные таким образом функции и данные позволят нам впоследствии более просто взаимодействовать с базами данных и AI/ML фреймворками.

Числовой Покер

Писать абстракции довольно скучно. Давайте спроектируем КА Числового Покера и реализуем его в коде.

На рисунках показаны довольно сильно упрощённые графы переходов КА для префлопа и флопа. Тёрн и ривер идентичны флопу. Стрелки между узлами обозначают события (решения игроков), в результате которых игра меняет своё состояние.

Графы переходов префлопа и флопа

Графы содержат циклы. Это означает, что некоторые (очень тонкие) ветви дерева будут замыкаться на себя. Так мы избежим необходимости накопления большого объёма данных и избежим ненужных просчётов. Проектирование графа переходов игры является нетривиальной задачей, требующей глубочайшего понимания особенностей игры. Эксперт, при составлении графа, должен стремиться к максимально сбалансированному представлению, выделяя в узлы уникальные ситуации, обладающие уникальной спецификой в общей стратегии принятия решений агентом.

Да, действительно, КА игры может быть совершенно по-разному спроектирован, лишь бы не было противоречий с правилами игры. Тщательное проектирование графа необходимо, в первую очередь, для возможно более точного (правильного, адекватного) принятия решения агентом или статистического анализа поведения агента в текущем переходе при расчёте описателей ситуации.

Спроектированный нами граф переходов КА Числового Покера довольно прост. Каждый узел графа кодирует определённую ситуацию в игре, получившую развитие в результате определённых действий игроков. Слишком редкие и, в этой связи, не представляющие интереса ситуации, могут быть схлопнуты в один узел. В частности, на префлопе узел PF_A кодирует все возможные ситуации, когда перед текущим игроком было ALLIN решение.

Ещё раз – в один узел можно схлопнуть те ситуации, логика принятия решений в которых близка. Это не означает, что игрок-агент не сможет различить пути достижения этого узла. Игроку в любой момент времени доступен контекст (непосредственно, игра), а, значит, и влияющие факторы.

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

На этом заканчивается этап проектирования КА игры. Можно перейти к написанию игровых сущностей Числового Покера.

Боты

Итак, Числовой Покер оцифрован (github), можно приступить к написанию ботов. И наша цель в рамках этой статьи написать следующих ботов:

1. простого rule-based, смотрящего только на свои карты. Назовём его SMARTY

2. играющего рандом (в пределах установленных ему ограничений). Назовём его RANDY)

3. мошенника, видящего карты оппонента. Назовём его FRAUDO

Принимающий решение игрок оперирует многими факторами. Важнейшим из них является сила комбинации своих карт. Поэтому на каждом этапе игры важно уметь оценивать вероятность победы, имея на руках те или иные карты. Например, в ситуации PF_FIRST игрок, получив на руки комбинацию из двойки и тройки (что в сумме даёт скромные 5 очков), имеет настолько низкие шансы на победу, что может выиграть только блефом. Очевидно, рациональная игра против рациональных игроков будет разворачиваться внутри некоего диапазона стартовых комбинаций.

Чтобы прописать логику принятия решений для рационального агента (SMARTY) потребуется анализ игровых зависимостей. И чем более изощрённую логику мы хотим реализовать, тем более глубоким должен быть анализ. Для наших текущих задач нам вполне хватит зависимости вероятности выигрыша (силы руки) от текущего числа очков руки и наличия туза в руке.

Воспользуемся написанным кодом для определения силы комбинаций на всех улицах.

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

Сгенерируем, скажем, 1 млн вариантов раздач, и выгрузим их хотя бы в Excel для анализа в сводных таблицах.

Часть сгенерированного файла

Графики винрейта от текущего числа очков и наличия туза в руке

Префлоп

Флоп

Тёрн

Ривер

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

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

SMARTY {

        public static final int PREFLOP_BEST_POINTS = 20;
        public static final int FLOP_BEST_POINTS = 36;
        public static final int TURN_BEST_POINTS = 40;

        private int getDistanceToBestScore(Street street, int currentPlayerPoints) {
            return switch (street) {
                case PF -> Math.abs(currentPlayerPoints - PREFLOP_BEST_POINTS);
                case FL -> Math.abs(currentPlayerPoints - FLOP_BEST_POINTS);
                case TN -> Math.abs(currentPlayerPoints - TURN_BEST_POINTS);
                case RV -> Math.abs(currentPlayerPoints - PointsEvaluator.GAME_GOAL_POINTS);
            };
        }

        @Override
        public Decision makeDecision(Game game) {
            Street street = game.getStreet();
            Player currentPlayer = game.getCurrentPlayer();
            int currentPlayerPoints = currentPlayer.getPoints(street);
            boolean hasAce = currentPlayer.getPreflopHand().contains(Card.ACE);
            int dist = getDistanceToBestScore(street, currentPlayerPoints);
            GameState gameState = game.getState();
            boolean boardContainsAce = game.getBoardCards().contains(Card.ACE);
            return switch (gameState) {
                case PF_FIRST -> {
                    if (hasAce || dist <= 4) {
                        yield Decision.raise(game.getBbAmount() * 2);
                    } else {
                        yield Decision.fold;
                    }
                }
                case PF_A,
                        PF_R,
                        PF_RR,
                        PF_RRR -> {
                    if (hasAce || dist <= 4) {
                        yield Decision.call(game.getUncalledBet());
                    } else {
                        yield Decision.fold;
                    }
                }
                case FL_FIRST, FL_C -> {
                    if (dist <= 3 && boardContainsAce) {
                        yield Decision.bet(game.getCurrentPot() * 0.25);
                    } else {
                        yield Decision.check;
                    }
                }
                case TN_FIRST, TN_C -> {
                    if (dist <= 3 && boardContainsAce) {
                        yield Decision.bet(game.getCurrentPot() * 0.66);
                    } else {
                        yield Decision.check;
                    }
                }
                case FL_A, TN_A, FL_B, FL_CB, FL_BR, FL_MR, TN_B, TN_CB, TN_BR, TN_MR, FL_CBR, TN_CBR -> {
                    if (dist <= 3 && boardContainsAce) {
                        yield Decision.call(game.getUncalledBet());
                    } else {
                        yield Decision.fold;
                    }
                }
                case RV_FIRST, RV_C -> {
                    if (dist <= 3 && boardContainsAce) {
                        yield Decision.bet(game.getCurrentPot() * 0.75);
                    } else {
                        yield Decision.check;
                    }
                }
                case RV_A, RV_B, RV_CB, RV_BR, RV_MR, RV_CBR -> {
                    if (dist <= 3 && boardContainsAce) {
                        yield Decision.call(game.getUncalledBet());
                    } else {
                        yield Decision.fold;
                    }
                }
                default -> throw new IllegalStateException("Unexpected value: " + gameState);
            };
        }
    }

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

RANDY бот – наверное, самый простой из всех. Ему жестко прописаны стратегии ставок в каждом узле игры. Случайные диапазоны, от которых отталкивается бот, прописаны «на глаз», но, при этом, не имеют неадекватных перекосов. При этом он совершенно не знает о силе рук. Так, он может запросто сбросить в пас сильную комбинацию на префлопе, или уравнять со слабейшей комбинацией на ривере.

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

Тестируем ботов в виртуальном бою

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

Запустим 10 тыс. случайных игр и посмотрим на результаты.

Графики профита

Видим, что в парных сражениях уверенно лидирует мошенник) Что ж, ожидаемо. Не играйте в карты с мошенниками)

Интересно, что SMARTY более эффективно, чем FRAUDO, отнимает фишки у RANDY – бота со случайными решениями. Что, впрочем, легко объяснимо. В этом следует благодарить случайные пасы на ривере, которые совершает RANDY, даже имея более сильную комбинацию по сравнению с соперником. SMARTY не подсматривает в карты соперника, а, значит, не знает о силе его руки. Без страха и сомнений он последовательно реализует заложенную в него стратегию. В отличие от FRAUDO, который, видя более сильную комбинацию у соперника, может сыграть пассивно или даже сбросить карты в пас.

Что дальше

В этой статье мы увидели только верхушку айсберга. 90% осталось нераскрытым.

Будет следующая статья. И в ней мы создадим ML бота, копирующего игру конкретного игрока. Основой для копирования будет накопленная на него история раздач. ML модели будут на классических деревьях принятия решений и реализованы на Spark mllib.

? С Наступающим Новым 2025 Годом! ?