Begin /* Покер на конечных автоматах. Теория
Вводные
Мне тут показалось, что для закрепления разных, мною же обозначенных теоретических тезисов не плохо было бы реализовать их на практике. Проблема в том, что сложно каждый раз подкреплять теорию реальными ситуациями и соответствующим кодом. В основном, потому что в чистом виде таких ситуаций либо не бывает, либо они вмешаны в другую окружающую действительность и выделить конкретные сущности из нее либо сложно, либо для описания требуются дополнительные вводные. Как вот привести пример, допустим, интернационализации программы? Писать отдельную "Hello world" программу или выдирать кусок из существующей утилиты, половина которой вообще не об этом?
Короче, не долго думая, я подобрал, на мой взгляд тот вариант, где одновременно можно внедрить практически все элементы современного технологического процесса создания программ с одной стороны, и, вместе с этим, понятный и доступный для довольно широкого круга читателей с другой. Пусть это будет программа, симулирующая поведение ведущего за столом в Техасский холдем.
Готовых реализаций этой популярной карточной игры существует огромная масса. Есть и просто клиентские приложения, есть варианты с искусственными противниками, есть варианты для мобилок, для серверов, для разных игровых платформ, для ботов и вообще всего что пожелаете. Есть разные способы реализации: от примитивных, собранных на коленке, до промышленных монстров над которыми работают команды разработчиков. Есть отдельные кусочки и библиотечки, выполняющие вспомогательные функции: оценка руки, всяческие алгоритмы выбора стратегии. Есть отдельно ядра игры без какого бы-то ни было обвеса.
Тем не менее, по моему твердому убеждению, некоторые вещи программист в своей жизни должен повторить самостоятельно. Какие-то основополагающие конструкции легче использовать в дальнейшем, если есть четкое понимание внутреннего устройства. Есть, например, мнение, что более глубокое знание устройства автомобиля дает некое преимущество при управлении им в нестандартных ситуациях. Так же и тут, понимая как работает фреймворк изнутри, проще добиться от него более эффективного использования. А что может быть лучше для понимания того как что-то работает изнутри, чем попытка собрать это самостоятельно?
Постановка задачи
Итак, Техасский Холдем, для простоты я буду называть его далее просто "покер". Итоговой задачей является создание системы позволяющей нескольким пользователям взаимодействовать с ней посредством некоего протокола сообщениями, которые по заданным правилам выявляют победителя и выдают им некий итоговый результат в виде доли выигрыша. Все правила покера достаточно хорошо и жестко описаны, в том числе и система подсчета ставок и выигрыша. Есть некоторые вариации в правилах, о которых оговаривается специально перед началом игры, но внутри процесса каких-то спорных моментов возникать не должно.
Определим сущности. Поскольку покер игра карточная, то основной сущностью здесь являются карты. Карты тоже совершенно четко определяются правилами и представляют из себя стандартную колоду из 52 игральных карт достоинством от туза до короля (или от двойки до туза, забегая вперед это один из довольно неприятных нюансов) и четырьмя мастями "черви", "бубны", "пики", "трефы".
Единицей для ставок возьмем казиношный стандарт фишек достоинством 1, 5, 10, 25, 50, 100, 500 и 1000. То есть, как ставки, так и выигрыш игрока будет пересчитываться именно в фишки разного достоинства.
Поскольку наличие фактического казино не предполагается, то и правила игры будут диктоваться тем случаем, когда игроки сами будут по очереди выступать в качестве сдающих (дилеров). Таким образом игрок может выступать в двух ипостасях: как пассивный игрок и как дилер орудующий колодой карт.
Сама система, призванная реализовать правила игры будет выступать отдельной сущностью для обработки действий игроков и выдачи им соответствующей реакции. Система должна принимать на вход сообщения от игроков в виде ставок и карт, и, выдавать в ответ карты, фишки и сообщения о нарушениях правил.
Начальная настройка правил может подразумевать под собой установку заранее оговариваемых положений, касательно начальных ставок, "анте", курсовой стоимости фишек и прочего. На начальном этапе система должна позволять пользователям свободно регистрироваться и выходить из игры, а так же контролировать общее количество одновременно взаимодействующих игроков. По стандартным правилам это от двух до восьми игроков. Таким образом игра так же имеет два разных, но связанных между собой режима: начальная стадия и непосредственно игровой процесс, где некоторые из функций, как например, покупка дополнительных фишек, уже не доступны.
Помимо этого система должна быть изолированный от смежных процессов и не должна зависеть, например от того зарегистрирован ли игрок в других процессах. Для этого введем такую дополнительную сущность как игровой стол, для которой будет однозначно определена основная система. Другими словами игра по оговоренным правилам однозначно определяется для стола, на который зарегистрированы игроки, но любой из игроков может одновременно находиться на других столах с другими задействованными на них правилами. Каждый из игроков волен покидать стол в любой момент игры, а так же присоединяться к игре между раундами ставок.
Конечные детерминированные автоматы
Игра с жесткими правилами как алгоритмическая задача довольно легко сводится к математической абстракции - так называемому конечному ориентированному графу состояний. Это наглядно показали еще математики докомпьютерной эпохи в фундаментальных работах по теории этих самых графов. Любая система с ограниченным количеством состояний представима в виде вершин - состояний и соединяющих их ребер - событий. А как затем показал небезызвестный Алан Тьюринг любой конечный ориентированный граф представим в виде конечного детерминированного автомата - машины Тьюринга.
Не вдаваясь в математические тонкости, здесь детерминированность - отвечает за то, что система не может изменять свое внутреннее устройство во времени. Конечность - собственно, не бесконечность. А ориентированность графа означает, что переход от одного состояния к другому имеет определенное направление, когда переход из одной вершины возможен, а обратно не обязательно. Что собственно и позволяет нам преобразовать граф в машину Тьюринга, которая имеет определенное направление работы: начало и конец.
На практике это означает, что состояния в игре не могут меняться без начального состояния соответствующих событий на это состояние влияющих. А правила игры не могут меняться ни при каких входящих условиях.
Реализацию конечных автоматов можно встретить во многих жестко сформулированных играх, в протоколах обмена данными, в трансляторах, в разнообразных системах управления бизнес-процессами. В общем случае вообще любая программа предназначенная для исполнения на регистровой машине с ограниченным набором команд, каковыми являются любые фон Неймановские процессоры - есть конечный детерминированные автомат. Да и компилятор - как средство трансляции программы в машинный код - по сути является машиной Тьюринга.
То есть, если есть какие-то четкие правила, то можно напрямую описать их в терминах состояний, событий и переходов, не используя какие-то лишние надстройки как в виде каких-либо фреймворков, так и в принципе языков программирования. В минималистском варианте описанную задачу можно решить посредством, грубо говоря, таблицы на листе бумаги, с правильно подобранными значениями.
С другой стороны, если рассуждать и дальше в таком ключе, то можно вообще любую задачу программирования свести к заполнению таблицы переходов. Понятно, что в каком-то месте следует остановиться и задуматься надо ли нам оно такое программирование.
Менее хипстерский вариант реализации состоит в том, что бы найти компромисс между удобством решения задачи и его оптимальностью. С точки зрения реализации основной идеи - реализации игры не в целях получения самой оптимальной в мире теоретико-прикладной конструкции, а в целях показать на примерах основные приемы и подходы существующие в реальной производственной деятельности - подойти к решению можно несколькими способами.
Самый простой - решение в лоб. Декомпозируем задачу, создаем соответствующие объекты и структуры данных и просто начинаем кодить последовательно и до получения результата. Однако, в свете всего вышесказанного это был бы не самый "умный" способ. Мы заранее знаем, что игра - это автомат. Зачем реализовывать автомат в виде какой-то другой структуры не совсем понятно. Заранее известно и другое - реализация каким-то другим способом приведет, скорее всего, к слишком сложному и громоздкому коду, который будет страдать низкой надежностью.
Другое дело, решить на этапе проектирования как следует реализовать сам автомат, так что бы код получился и понятным и компактным. Мне на данном этапе видится смешанный, скажем так, объектно-автоматный подход. То есть сам автомат будет реализован с помощью объекта, а взаимодействовать этот объект с внешней средой будет посредством интерфейсов.
Иерархический автомат со стековой памятью
Реализация самого автомата внутри объекта тоже может быть разной. Есть простые автоматы без каких-то дополнительных сущностей, но снабженные из-за этого полным множеством всевозможных состояний в точности до положения каждой конкретной карты в колоде. Что понятно, так же плохо реализуемо напрямую. Есть и более продвинутые модели с памятью о предыдущих состояниях и событиях в виде магазинов и стеков. Так же существует такое понятие как вложенные автоматы с иерархической структурой, что как нельзя хорошо подходит к нашей ситуации с покером.
Логически у нас есть игроки, каждый из которых в какой-то момент может управлять колодой карт. То есть игрок сам являясь автоматом с энным количеством собственных состояний, может воздействовать на колоду, которая в свою очередь тоже может быть вынесена в отдельный объект с собственным автоматом внутри. А поскольку колода сущность, в принципе не зависящая от того у кого конкретно она в данный момент находится, это полностью ложится на модель иерархического автомата, так как нет обратной связи между состоянием колоды и состоянием игрока. Ну, то есть расположение или количество карт не влияет на сам процесс игры, внося в нее лишь вероятностный характер.
Так же и игроки не могут непосредственно влиять на ни на состояния других игроков, ни на процесс в целом снизу вверх по иерархии. То есть игра по отношению к игрокам автомат более высокого порядка.
Более того, и сама игра может быть представлена в виде отдельных кусков подчиненных общему набору правил. Каждая партия в покер состоит из полностью изолированных друг от друга раздач - раундов.
Таким образом в результате можно раздробить весь автомат на более понятные вложенные друг в друга структуры. Автомат верхнего уровня - игра или партия, начинающаяся с определения правил и заканчивающаяся на последнем игроке с фишками. Игра управляет вложенным автоматом представляющими из себя раунды с фиксированным начальным количеством игроков, выбранным дилером и новой колодой карт, каждый из которых заканчивается распределением банка. Так же на уровне игры создаются отдельные автоматы на каждого игрока, которые в свою очередь могут управлять колодой карт.
Интерфейсы
Каждый из вложенных автоматов можно реализовать отдельно и разными способами. Например, автомат представляющий из себя раунд наиболее сложен и есть подозрение, что без стека состояний его реализовать будет достаточно сложно. Игрок так же довольно хитрая структура, которая ко всему прочему, должна адекватно учитывать то сколько у игрока в данный момент фишек в наличии. Наличие или отсутствие фишек у игрока теоретически тоже в общем случае можно представить в виде маленького автомата с двумя состояниями, но это уже, наверное, лишнее. Хотя как знать, поживем увидим.
А вот автомат реализующий колоду карт довольно прямолинейный и простой, не требующий каких-то ухищрений в виде стеков и магазинов. Тем не менее, существует соблазн сделать так, что бы автомат как сущность в принципе был бы одинаковым на любом уровне иерархии и сложности. Мы можем объявить некий абстрактный автомат, который бы реагировал стандартно, но по алгоритму заложенному в него не изначально, а посредством определения поведения в явном виде. Что было бы ко всему прочему идеологически верно. Мы ведь задались целью все сделать так как следует?
У меня получилось пока нечто промежуточное. Абстрагировать сам автомат я попытался, но сейчас выходит, что можно было бы заложить еще более гибкую схему.
Реализация
Здесь и далее, когда я буду говорить "я" и "мое", я буду ссылаться на свой, с позволения сказать, творческий проект. Здесь покер реализован в виде телеграм бота @pulseday_bot, который пока работает с домашней рабочей станции и потрогать его можно лишь в те редкие моменты, когда я его ковыряю. А соответственно когда я его ковыряю, он может работать в общем-то как попало. Бот слушается команду /holdem start (и не только её), для исполнения которой вам надо пригласить его себе в группу.
Либо вы можете совершенно безвозмездно забрать форк проекта и запустить у себя. Коммиты приветствуются. Бот работает на основе LongPollingBot автора Timo Schulz и собран на Java 11 с минимальными внешними зависимостями. В репу я стараюсь закидывать максимально стабильные версии. Так что при наличии Maven и jdk-11.0.8 все должно собираться и запускаться без проблем.
На данный момент, то о чем говорится в данной заметке можно отыскать в пакете ru.rembo.bot.telegram.statemachine. Так же ко всему что касается покера я постарался, ну или собираюсь сделать в соответствии с тем о чем я ранее говорил в заметках данной рубрики.
На будущее есть план вытащить абстракции связанные с автоматами в отдельную библиотеку в виде эдакого фреймворка. То ли в качестве образца, то ли для дальнейшего использования в собственных поделках.
Следует, однако, понимать, что это именно больше демонстрационный проект, чем фактический инструмент для использования в каких-то практических целях. В промышленном применении данный проект годится разве что в качестве источника каких-то идей или для сравнения с существующими проектами с более серьезной технической поддержкой. С моей стороны нет никаких гарантий о том, что в проекте будут отслеживаться багрепорты и по какому-либо графику выкладываться исправления или плановые улучшения. Да и как сказано выше, есть масса готовых и работающих решений.
Тем не менее если есть желание поучаствовать в проекте, милости прошу, бросать его в ближайшее время намерений нет. Есть как краткосрочные, так и далеко идущие планы по модернизации и доведению проекта до ума. Ну, например, до состояния выкладывания бота в облачный сервис.