Хочу представить вашему вниманию небольшую статью о том, как я делал для 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)


  1. k12th
    29.09.2016 00:29
    +5

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


  1. GlukKazan
    29.09.2016 09:47
    +1

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

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

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


    1. XVadim
      29.09.2016 10:16
      +1

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

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

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

      Дельное замечание. Надо будет рассказать об этом Центеотлю, пусть меняет стратегию.


  1. sophist
    29.09.2016 09:55
    +2

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

    Что-что, простите?


    1. sophist
      29.09.2016 12:20
      +4

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


  1. Idot
    29.09.2016 10:35
    -1

    Очень жалко, что эту игру нельзя купить на Steam'е :(


  1. laughman
    29.09.2016 12:31

    интересно, спасибо


  1. marapper
    29.09.2016 13:33
    +1

    На хабре еще GlukKazan публикует статьи о интересных играх


    1. GlukKazan
      29.09.2016 13:39

      Спасибо, автор статьи меня уже упомянул.


  1. GlukKazan
    29.09.2016 13:42

    Кстати, в моей коллекции нет «Калаха» для ПМК. Мне (да я думаю, что и другим тоже) было бы интересно и приятно почитать об этой игре. Подобные «ностальгические» статьи пользуются на Хабре некоторой популярностью.


    1. XVadim
      29.09.2016 20:29
      +1

      С ПМК-программами я варился в собственном соку. Про КЛИП я узнал слишком поздно. К счастью, недавно, нашел свои тетради с программами. Так что можно будет написать статейку и подготовить программу для моей версии эмулятора МК-61, чтобы желающим попробовать не пришлось самим вбивать программу.