Як я робив гру індіанців Центральної Америки

Хочу представити вашій увазі невелику статтю про те, як я робив для 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.0 f, 1.1 f, 1.1 f, 1.5 f};
}

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.0 f, 2.0 f, 1.1 f, 1.1 f};
}
}

насправді деякі передбачення можна зробити, ґрунтуючись на теорії ймовірностей. Наприклад, якщо перед розглянутої вище ситуацією випадали значення 5, 5, 4, 3, 2, 3, то з високою часткою ймовірності можна припустити, що противнику випаде 1. В цьому випадку вкрай бажано врятувати від полону фішку, що стоїть на 8-й смужці. Тому третій алгоритм, який я розробив, запам'ятовує випали значення зерен і приписує високий вагу тим ходах, які рятують фішки від потенційного полону.
Я заздалегідь не знав, яка із стратегій виявиться найбільш оптимальною. З іншого боку, називати варіанти ІЇ як зазвичай Початківець, Майстер і т. п. досить банально. Тому кожен з варіантів я назвав на честь певного індійського божества. Перший алгоритм, який в першу чергу намагається зберегти свої фішки — в честь Кетцалькоатля — напевно, це найвідоміше індійське божество. Другий алгоритм, який прагне захоплювати фішки супротивника — в честь божества війни Камаштли. Третій алгоритм, який за моїми припущеннями повинен бути найкращим, — на честь божества маїсу Центеотля. Адже божество, якому присвячена гра, має в неї грати краще за всіх.
Щоб привнести певний освітній елемент в гру, в діалог вибору ШІ я додав посилання на відповідні статті на Wikipedia, а в діалог "Про програму" — посилання на статтю Дмитра про пулук. Після деякої кількості ігор я отримав наступну статистику:


Підсумок
Пулук дійсно оригінальна і цікава гра. Тепер "грати партія за партією до знемоги" можна на дому. З допомогою Internet і Google Play Game Services навіть можна битися з цим майя. Ну а фермери можуть перевірити її вплив на врожаї кукурудзи.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.