Как я делал игру индейцев Центральной Америки

    Хочу представить вашему вниманию небольшую статью о том, как я делал для Android пулук — настольную игру индейцев Центральной Америки.


    "Обучать" компьютеры человеческим играм я начал едва научившись программировать. Первым был калах (разновидность манкалы) для калькулятора МК-61. Позже — Волк и овцы, сначала для MS-DOS, а потом и для Android.


    Общие сведения об игре


    Читая на Хабре статьи GlukKazan, я наткнулся на интересный ЖЖ Дмитрия Скирюка с описаниями настольных игр разных народов мира. Одна из них — пулук — меня на столько увлекла, что я решил реализовать ее для Android.


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


    Доска для пулука состоит из 11 полосок, причем первая и последняя служат "городами" для фишек игроков. Фишек у каждого игрока по пять штук. Вместо игрального кубика обычно используются четыре кукурузных зернышка, у которых одна из сторон каким-либо образом помечена. Очки считаются так:


    1. одно из четырех зерен выпало пустой стороной вверх — одно очко
    2. два зерна выпали пустой стороной верх — два очка
    3. три зерна — три очка
    4. четыре зерна — четыре очка
    5. все зерна выпали метками вверх — пять очков

    В начале игры все фишки игроков стоят в "городах". Во время своего хода игрок бросает зерна и перемещает одну из своих фишек на соответствующее число полосок по направлению к "городу" соперника.


    Две фишки одного игрока не могут занимать одну полоску (кроме "города"). Но можно ставить свою фишку на полоску, на которой стоит фишка противника — брать эту фишку в плен. Далее этот столбик продолжает двигаться как одна (верхняя) фишка и может брать в плен другие фишки противника.


    Если в плен берется столбик то все нижние фишки игрока, выполнившего захват, которые были в плену, освобождаются.


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


    Побеждает игрок, который захватит или побьет все фишки противника.


    Как пишет Дмитрий: "Несмотря на кажущуюся простоту и непривычно маленькую доску, пулук очень увлекателен. Тактика его уникальна, он не похож на игры других народов: это не гонки с преследованием, не военная игра и не «переходы» вроде Уголков, а некая хитрая «ловилка-уводилка»".


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


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



    Технические особенности


    В техническом плане игра, наверное, особого интереса не представляет, так как особых хитростей при разработке я не использовал. Программировал Android-приложение я с помощью фреймворка AndEngine. Хотя он в последнее время практически не развивается, его возможностей мне вполне хватило.


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


    Разработка ИИ


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


    • вывести фишку из "города"
    • захватить в плен фишку противника
    • освободить из плена свою фишку
    • вывести из игры плененные фишки противника

    Например, при следующей ситуации:



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


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


    1. Найти все доступные ходы
    2. Присвоить каждому ходу его вес
    3. Выбрать ход с наибольшим весом.

    Используя разные наборы весов, можно получить несколько вариантов ИИ:


    public class OpponentAIFirstController extends OpponentAIController {
    
        protected static final int WEIGHT_IND_HOME = 0;
        protected static final int WEIGHT_IND_CAPTURE = 1;
        protected static final int WEIGHT_IND_RELEASE = 2;
        protected static final int WEIGHT_IND_CAPTURED_MOVE = 3;
    
        protected float movementWeights[];
    
       public OpponentAIFirstController(...) {
            super(...);
            initMovementWeights();
        }
    
       protected void initMovementWeights() {
            movementWeights = new float[] {1.0f, 1.1f, 1.1f, 1.5f};
        }
    
        private void calcInitialScores(int pCornsValue) {
            for(i = mFirstChipIndex; i < mLastChipIndex; i++) {
            ...
                int newRow = mFieldController.calcNewRow(curChip, pCornsValue);
                if (mFieldController.isHomeRow(newRow)) {
                    mMoveScores[j] += 1 + curChip.capturedCount();
                    mMoveScores[j] *= movementWeights[WEIGHT_IND_HOME];
                    continue;
                }
            ...
            }
        }
    ...
    }
    
    public class OpponentAISecondController extends OpponentAIFirstController {
    ...
        @Override
        protected void initMovementWeights() {
            movementWeights = new float[] {1.0f, 2.0f, 1.1f, 1.1f};
        }
    }

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


    Я заранее не знал, какая из стратегий окажется наиболее оптимальной. С другой стороны, называть варианты ИИ как обычно Начинающий, Мастер и т.п. довольно банально. Поэтому каждый из вариантов я назвал в честь определенного индейского божества. Первый алгоритм, который в первую очередь пытается сохранить свои фишки — в честь Кетцалькоатля — наверное, это самое известное индейское божество. Второй алгоритм, стремящийся захватывать фишки противника — в честь божества войны Камаштли. Третий алгоритм, который по моим предположениям должен быть наилучшим, — в честь божества маиса Центеотля. Ведь божество, которому посвящена игра, должно в нее играть лучше всех.


    Дабы привнести некоторый образовательный элемент в игру, в диалог выбора ИИ я добавил ссылки на соответствующие статьи на Wikipedia, а в диалог "О программе" — ссылку на статью Дмитрия о пулук. После некоторого количества игр я получил следующую статистику:




    Итог


    Пулук действительно оригинальная и забавная игра. Теперь "играть партия за партией до изнеможения" можно на дому. С помощью Internet и Google Play Game Services даже можно сразиться с настоящим майя. Ну а фермеры могут проверить ее влияние на урожаи кукурузы.

    Поделиться публикацией

    Комментарии 11

      +5

      Удачная фича с именами богов.

        +1
        Действительно отличная игра (одно плохо — партии слишком короткие). По поводу реализации (кстати, я видел её на маркете совсем недавно, но, к стыду своему, не установил её на свой древний аппарат, забитый всяким хламом) позволю себе пару комментариев:

        В статье Дмитрия Скирюка действительно не совсем понятно описаны правила освобождения фишек. На одном из «Зилантконов» он разъяснил мне неясные моменты и мы сыграли несколько пробных партий:

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


        Да, здесь возможна ситуация когда освобождаются две фишки одного цвета, стоящие на одном поле. Одним из следующих ходов они безболезненно разделяются — верхняя снимается и идёт дальше, а нижняя остаётся на месте. Таким образом, игрок всегда перемещает всего лишь одну фишку своего цвета (и возможно несколько фишек противника под ней). Фишка своего цвета «разделяет» стопку. Разумеется, нельзя ходить на поле уже занятое своей фишкой, «задвоение» может происходить только в плену противника. Это важный момент правил влияющий на тактику игры.

        Второй момент касается костей. Очень важно, что при использовании 4xD2 (четырёх «двугранных» костей), различные очки выпадают не с равной вероятностью! Чаще всего выпадают двойки, реже всего пятёрки и четвёрки. Нельзя заменить 4xD2 на D5 (даже если бы в природе существовала подобная кость), характер игры серьёзно изменится!

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

          +1
          > Да, здесь возможна ситуация когда освобождаются две фишки одного цвета, стоящие на одном поле. Одним из следующих ходов они безболезненно разделяются — верхняя снимается и идёт дальше, а нижняя остаётся на месте.

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

          > Очень важно, что при использовании 4xD2 (четырёх «двугранных» костей), различные очки выпадают не с равной вероятностью!

          Дельное замечание. Надо будет рассказать об этом Центеотлю, пусть меняет стратегию.
          +2
          >  если перед рассмотренной выше ситуацией выпадали значения 5, 5, 4, 3, 2, 3, то с высокой долей вероятности можно предположить, что противнику выпадет значение 1. 

          Что-что, простите?
            +4
            Поскольку мой намёк не достиг цели, скажу прямо:
            вероятность выпадения какого-либо значения никак не зависит от того, какие значения выпадали ранее.
            –1
            Очень жалко, что эту игру нельзя купить на Steam'е :(
              0
              интересно, спасибо
                +1
                На хабре еще GlukKazan публикует статьи о интересных играх
                  0
                  Спасибо, автор статьи меня уже упомянул.
                  0
                  Кстати, в моей коллекции нет «Калаха» для ПМК. Мне (да я думаю, что и другим тоже) было бы интересно и приятно почитать об этой игре. Подобные «ностальгические» статьи пользуются на Хабре некоторой популярностью.
                    +1
                    С ПМК-программами я варился в собственном соку. Про КЛИП я узнал слишком поздно. К счастью, недавно, нашел свои тетради с программами. Так что можно будет написать статейку и подготовить программу для моей версии эмулятора МК-61, чтобы желающим попробовать не пришлось самим вбивать программу.

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

                  Самое читаемое