Dagaz: Еволюція замість революції

imageВ цьому світі того, що хотілося б нам НЕМАЄ!
Ми віримо, що в силах його змінити ТАК!
 
Юрій Шевчук
 
 
 
 
Ті з вас, хто читав мої статті, повинні знати про те, що я, досить давно, займаюся вивченням метаигровой системи Zillions of Games. За весь цей час, я розробив трохи менше півсотні ігор і вивчив цю платформу вздовж і впоперек. Моєю метою є розробка аналогічної (а бажано більше функціональної) системи з відкритим вихідним кодом. Про хід цієї роботи я і хочу розповісти.

За образом і подобою
Як я вже сказав, я дуже добре розумію, як саме працює Zillions of Games. Мені не заважає відсутність її вихідних кодів, оскільки я не збираюся займатися портацией цього продукту. Мова йде про розробку нової системи з нуля, з урахуванням переваг (і ще більшою мірою недоліків) всіх відомих мені на даний момент, метаигровых платформ. Перерахую їх:

  • Zillions of Games — найбільш відома метаигровая система, про яку я багато писав
  • Axiom Development Kit — досить цікавий проект, реалізований як модуль розширення Zillions of Games, але здатний працювати і автономно
  • The LUDÆ project — Забавна система, призначена для автоматизованої розробки нових настільних ігор
  • Jocly — Сучасна і дуже цікава розробка (на жаль, якість реалізованих під неї ігор залишає бажати кращого)
Всі ці продукти працюють і роблять те, для чого вони призначені — допомагають, з витратою великих або менших зусиль, створювати комп'ютерні реалізації різноманітних настільних ігор. Мова йде не тільки про Шашках та Шахах! Кількість і (що найголовніше) різноманітність вже створених ігор перевершує всі очікування. У цьому головна перевага метаигровых систем — працюючий прототип нової і досить складною настільної гри можна створити буквально за пару годин!

Ложка дьогтюГоловний їх недолік також очевидний. Ні одному універсальному ігровому «движку» ніколи не зрівнятися (по продуктивності) з спеціалізованими програмами, орієнтованими на одну і тільки одну настільну гру. З цим безпосередньо пов'язана й «інтелектуальність» ботів, покликаних скласти компанію гравцеві-людині, що перебуває в самоті. Всі універсальні ігрові системи відіграють дуже слабо, але оскільки мова, як правило, йде про досить екзотичних іграх, це не є дуже великою проблемою. Навряд чи програмі пощастить зустрітися з людиною, граючим, наприклад, Chu Shogi на рівні гросмейстера.

Крім цього загального недоліку (а також фатального недоліку, пов'язаного з закритістю вихідних кодів), кожен з перерахованих проектів має і індивідуальними особливостями. Так, Zillions of Games використовує лиспо-подібний DSLвельми полегшує процес опису настільних ігор, але дещо обмежує функціональність доступну розробнику. Реалізувати, з його допомогою, можна действительно дуже багато, але далеко не все. Деякі ігри, такі як "Ритмомахия" або "Каурі", розробити на чистому ZRF рішуче неможливо. Інші, на кшталт "Ko Shogi" або "Gwangsanghui", зробити можна, але настільки складним чином, що істотно страждає їх продуктивність (а отже і «інтелект» AI).

Розширення Axiom Development Kit з'явилося як спроба поліпшення Zillions of Games. Оскільки ця бібліотека оперує числами (а не тільки булевскими прапорами, як Zillions of Games), такі ігри як «Ритмомахия» стають реализуемыми, але сам процес розробки місцями нагадує кошмар (я трохи писав про це). Як DSL, Axiom використовує Forth Script підмножина мови Форт) і ця мова (а головне налагодження програм на ньому) справді набагато складніше теплого і лампового ZRF. Крім того, зробити з його допомогою можна далеко не все. Розробка таких ігор як "Таврели" або, згадана вище «Каурі», як і раніше, не представляється можливим.

Про «LUDÆ» я мало що можу розповісти (оскільки ніколи не бачив цього продукту наживо), що ж стосується Jocly, то недоліком цієї системи (на мій погляд) є повна відмова від використання якого або DSL для опису ігор. Фактично, це MVC-фреймворк для розробки настільних ігор на мові JavaScript. Навіть внесення досить тривіальних змін у вже розроблені гри перетворюється в досить трудомісткий процес. Ігри, створені самими авторами, також не позбавлені серйозних помилок (я пов'язую це зі складністю процесу розробки). Наприклад, у "Алькуэрке" виникають ситуації, при яких одні й ті ж фігури «беруться» по декілька разів за хід, а "Турецьких шашках" помилково діє правило "Турецького удару" — головне що відрізняє цю гру від інших шашкових систем.

Знайомство з Jocly підштовхнуло мене до перегляду деяких рішень. Для подальшої розробки я твердо вирішив використовувати JavaScript, оскільки це очевидно найбільш простий шлях до створення розширюваної і кроссплатформної системи з сучасним інтерфейсом. Однопоточность трохи відлякує, але, насправді, цей момент важливий виключно для AI (та й у ньому, використовувати багатопоточність правильно зовсім не просто), а ми вже (для себе) з'ясували, що AI не найсильніша сторона метаигровых систем.

З іншого боку, для мене абсолютно очевидна необхідність наявності якогось DSL для опису найбільш рутинних моментів настільних ігор. Безпосереднє використання JavaScript для розробки всієї ігрової моделі надає процесу небувалу гнучкість, але вимагає старанності і зосередженості (і, як показала практика, навіть їх наявність не сильно допомагає). В ідеалі, хотілося б забезпечити сумісність з базовим ZRF, щоб мати можливість запускати в новій системі, якщо і не все дві з половиною тисячі ігор, то, хоча б, значну їх частину. Ось що пишуть з цього приводу розробники Jocly:

In ZoG, games are described in a lisp-based language called ZRF. This gives a nice formal framework to the game rules, but introduces a number of limitations when ZRF has no predefined instruction for a given feature. The Jocly approach is quite different since games are developed in Javascript and use APIs to define the rules and user interface. The good with Jocly is that developers almost anything can do they want, the bad is that they must write more code.

In theory, it would be possible to write a ZRF interpretor in Javascript for Jocly to run any ZoG game. If you are willing to develop that kind of tool, let us know.
Я вирішив піти по цьому шляху, зосередившись, правда, не на інтерпретації, а на свого роду «компіляції» ZRF-файлу в опис гри для Jocly. Постійний розбір текстового файлу, нехай навіть і містить дуже просте опис гри, мовою нагадує Лисп — це не та справа, якою хотілося б займатися в JavaScript.

ПодробиціЯ вирішив створити додаток, перетворює вихідний zrf-файл, що містить опис гри, форму, придатну для завантаження в модель Jocly. Наприклад, замість этого файлу (для перегляду всіх відкритих текстів платформи Jocly Jocly Inspector). Зрозуміло, потрібна прослойка, здатна «склеїти» це опис з моделлю Jocly. Z2J-транслятор одноразово виконує ту роботу, якій не хотілося б займатися в JavaScript-додатку постійно. Наприклад:

Наступний опис ігрової дошки
(grid
(start-rectangle 6 6 55 55)
(dimensions
("a/b/c/d/e/f/g/h" (50 0)) ; files
("8/7/6/5/4/3/2/1" (0 50)) ; ranks
)
(directions (n 0 -1) (s 0 1) (e 1 0) (w -1 0))
)

Перетворюється в ...
design.addDirection("w");
design.addDirection("е");
design.addDirection("s");
design.addDirection("n");

design.addPosition("a8", [0, 1, 8, 0]);
design.addPosition("b8", [-1, 1, 8, 0]);
...

Фактично, це опис графа, вершинами якого є окремі позиції на дошці, а дугами (орієнтованими) — напрямки, в яких фігури можуть рухатися. Цілі числа, зазначені в масивах, асоційованих з вершинами графа, являють собою зміщення всередині лінійного масиву всіх позицій, що використовуються в грі (нульове значення зміщення означає відсутність дуги). При використанні такого підходу, навігація по будь-якому напрямку зводиться до одного арифметичного додавання:

ZrfDesign.navigate
ZrfDesign.prototype.navigate = function(aPlayer, aPos, aDir) {
var dir = aDir;
if (typeof this.players[aPlayer] !== "undefined") {
dir = this.players[aPlayer][aDir];
}
if (this.positions[aPos][dir] !== 0) {
return aPos + this.positions[aPos][dir];
} else {
return null;
}
}

Ну ладно, є ще опціональне зміна напрямку переміщення, залежно від гравця виконує хід (так звана «симетрія»), що дозволяє, наприклад, описувати переміщення всіх пішаків (і чорних і білих) як переміщення «на північ». Якщо хід буде виконуватися чорними, напрямок буде змінено на «південне» автоматично. «Нульова симетрія» дозволяє описувати «опозитні» переміщення для кожного напрямку (у багатьох іграх це буває корисно):
design.addPlayer("White", [1, 0, 3, 2]);
Дещо складніше перетворюються правила переміщення фігур.

Хід шашки
(define checker-shift (
$1 (verify empty?)
(if (in-zone? promotion)
(add King)
else
add
)
))

Перетворюється в ...
design.addCommand(1, ZRF.FUNCTION, 24); // from
design.addCommand(1, ZRF.PARAM, 0); // $1
design.addCommand(1, ZRF.FUNCTION, 22); // navigate
design.addCommand(1, ZRF.FUNCTION, 1); // empty?
design.addCommand(1, ZRF.FUNCTION, 20); // verify
design.addCommand(1, ZRF.IN_ZONE, 0); // promotion
design.addCommand(1, ZRF.FUNCTION, 0); // not
design.addCommand(1, ZRF.IF, 4);
design.addCommand(1, ZRF.PROMOTE, 1); // King
design.addCommand(1, ZRF.FUNCTION, 25); // to
design.addCommand(1, ZRF.JUMP, 2);
design.addCommand(1, ZRF.FUNCTION, 25); // to
design.addCommand(1, ZRF.FUNCTION, 28); // end

Це команди стекової машини, кожна з яких дуже проста. Наприклад, команда PARAM дістає числове значення з масиву параметрів прикріпленого до шаблону ходу (набору команд) і поміщає його на стек. Вона дозволяє параметризировать шаблони ходів, передаючи напрямку переміщення в параметрах:

Опис фігури
design.addPiece("Man", 0);
design.addMove(0, 0, [3, 3], 0);
design.addMove(0, 0, [0, 0], 0);
design.addMove(0, 0, [1, 1], 0);
design.addMove(0, 1, [3], 1);
design.addMove(0, 1, [0], 1);
design.addMove(0, 1, [1], 1);

В якості третього параметра передається «режим» ходу — числове значення, яке, крім усього іншого, відокремити «тихі» ходи (у шашках) від виконання взяттів. Вся трійка (шаблон + параметри + режим ходу) становить повне опис одного з можливих ходів, виконуваних фігурою.

Jocly побудована за класичною MVC-схемою. Для розробки нової гри потрібно написати її модель та подання. Модель визначає правила гри, а уявлення, як гра буде показана користувачеві. Контролер, написаний розробниками, бере на себе все інше (включаючи зашитих в нього ботів).


Архітектура універсальної моделі, реалізованої Z2J також не дуже складна. Основу становить компонент Design, що містить незмінне опис правил гри. Стан гри (розміщення фігур на дошці) зберігається в примірниках класу Board. Дані цих компонентів також не змінюються. Виконуючи хід (застосовуючи об'єкт Move Board), ми створюємо новий стан. Старе залишається незмінним!


Для генерації ходу (створення об'єкта Move), використовується поточний стан Board, але лише одного його недостатньо для реалізації всіх можливостей ZRF. В процесі генерації ходу, ZRF може використовувати змінні (прапори і позиційні прапори), які не є частиною ігрового стану. Усім цим, а також логікою виконання команд стекової машини, займається Move Generator. Якщо говорити коротко, така архітектура модуля zrf-model.js.

Диявол у деталях
Отже, я збирався вбудувати в Jocly свою модель (zrf-model.js), зконфігуровану результатом компіляції "Турецьких шашок", замість модели Jocly і спробувати запустити все це, не вносячи жодних змін у представление ігри. Озираючись назад, я розумію, що ідея була авантюрною (чому — розповім нижче), але саме з цього я почав. Від моделі було потрібно небагато:

  1. Зберігання поточного стану ігри
  2. Генерація всіх ходів, допустимих для поточного стану ігри
  3. Зміна стану ігри, шляхом застосування до нього одного з згенерованих ходів
Складність полягала в тому, що хід, далеко не завжди, зводиться до простого переміщення однієї з фігур на дошці. В найбільш загальній формі, хід складається з послідовності таких елементарних дій:

  • move — Переміщення фігури з однієї позиції в іншу
  • capture — Видалення фігури з однією з позицій на дошці
  • drop — Додавання (скидання) нової фігури на дошку
Наприклад, взяття фігури у шашках складається з одного переміщення своєї фігури і взяття фігури противника (при цьому, взяття не «шахове», оскільки позиція, з якої воно виконується, не збігається з кінцевою позицією переміщення фігури), а ходи в таких іграх як "Рендзю" складаються з одиничних скидів фігур на дошку. Не слід думати, що при виконанні ходу може переміщатися всього одна фігура! Так, при виконанні рокировки в шахах, човен і король переміщаються одночасно, в рамках одного неподільного ходу.

Як це працюєГенерація ходу зводиться до формування списку елементарних дій, виконуваних у правильній послідовності. Це просто послідовна інтерпретація команд стекової машини:

ZrfMoveGenerator.generate
ZrfMoveGenerator.prototype.generate = function() {
this.cmd = 0;
while (this.cmd < this.template.commands.length) {
var r = (this.template.commands[this.cmd++])(this);
if (r === null) break;
this.cmd += r;
if (this.cmd < 0) break;
}
}

Якщо опустити подробиці, пов'язані з перевірками необхідних умов (не знаходження полів під шахом, нерухомість фігур до виконання ходу тощо), код виконання короткої рокіровки, виражений на ZRF може виглядати так:

Рокіровка
(define O-O (
e to e
cascade w w
add
))

Перетворюється в ...
design.addCommand(0, ZRF.FUNCTION, 24); // from
design.addCommand(0, ZRF.PARAM, 0); // e
design.addCommand(0, ZRF.FUNCTION, 22); // navigate
design.addCommand(0, ZRF.PARAM, 1); // e
design.addCommand(0, ZRF.FUNCTION, 22); // navigate
design.addCommand(0, ZRF.FUNCTION, 25); // to
design.addCommand(0, ZRF.PARAM, 2); // e
design.addCommand(0, ZRF.FUNCTION, 22); // navigate
design.addCommand(0, ZRF.FUNCTION, 24); // from
design.addCommand(0, ZRF.PARAM, 3); // w
design.addCommand(0, ZRF.FUNCTION, 22); // navigate
design.addCommand(0, ZRF.PARAM, 4); // w
design.addCommand(0, ZRF.FUNCTION, 22); // navigate
design.addCommand(0, ZRF.FUNCTION, 25); // to
design.addCommand(0, ZRF.FUNCTION, 28); // end

Крім параметризованной навігації, все зводиться до переміщення фігур, взятих командою from (неявно виконуваної на початку ходу і при виконанні команди cascade), на полі вказане командою to (також формованої неявно). Сам обробник команди виглядає елементарно:

Model.Move.ZRF_TO
Model.Game.functions[Model.Move.ZRF_TO] = function(aGen) {
if (aGen.pos === null) {
return null;
}
if (typeof aGen.piece === "undefined") {
return null;
}
aGen.movePiece(aGen.from, aGen.pos, aGen.piece);
delete aGen.from;
delete aGen.piece;
return 0;
}

ZrfMoveGenerator.prototype.movePiece = function(aFrom, aTo, aPiece) {
this.move.movePiece(aFrom, aTo, aPiece, this.level);
if (aFrom !== aTo) {
this.setPiece(aFrom, null);
}
this.setPiece(aTo, aPiece);
}

ZrfMove.prototype.movePiece = function(from, to, piece, part) {
this.actions.push([ from, to, piece, part ]);
}


Але все це — лише частина проблеми! У шашках, фігура може (і більше того, зобов'язана виконати кілька взяттів «по ланцюжку». Поки не виконані всі взяття, хід не передається іншому гравцеві. З точки зору моделі і для AI, це один хід! З контролером і поданням все трохи складніше. В інтерфейсі гри, кожне шашкова взяття (частковий хід), повинно виконуватися окремо. Користувач (гравець) повинен мати можливість вибору того чи іншого часткового ходу на кожному етапі виконання довгого складеного ходу.

Звичайно, це не єдино можливий підхідZillions of Games, окремим ходом вважається кожен частковий хід. Це спрощує інтерфейс, але, з іншого боку, не тільки ускладнює життя AI, але і веде до більш серйозних проблем.


Тут показана послідовність позицій, що виникають при виконанні складеного ходу в грі "Mana", розробленої Клодом Лероєм в 2005 році. За правилами гри, білий Damyo повинен виконати три послідовних кроки, по горизонталі або вертикалі, на сусідню порожню позицію. При цьому, всі кроки повинні бути зроблені і фігурі забороняється повертатися раніше пройдені позиції. Як легко бачити, фігура може загнати себе в «глухий кут», обравши неправильну послідовність часткових ходів. У Zillions of Games ця проблема нерозв'язна!

З Шашками теж не все просто. Практично у всіх традиційних шашкових іграх (за винятком Фанороны), гравець зобов'язаний продовжувати взяття, поки є така можливість. Це означає, що виконуючи частковий хід містить взяття, ми ще не знаємо, він завершує допустимий складовою хід чи ні.

Зрозуміло, з цим можна боротись ...але це вже сильно нагадує…
«захід Сонця вручну»
(define checker-captured-find
mark
(if (on-board? $1) 
$1 
(if (and enemy? (on-board? $1) (empty? $1) (not captured?)) 
(set-flag more-captures true)
)
)
back
)

(define king-captured-find
mark
(while (and (on-board? $1) (empty? $1))
$1
)
(if (on-board? $1) 
$1 
(if (and enemy? (empty? $1) (not captured?)) 
(set-flag more-captures true)
)
)
back
)

(define checker-jump (
(verify (not captured?)) 
$1
(verify enemy?)
(verify (not captured?))
$1
(verify empty?)
(set-flag more-captures false)
(if (in-zone? promotion)
(king-captured-find $1)
(king-captured-find $2)
(king-captured-find $3)
else
(checker-captured-find $1)
(checker-captured-find $2)
(checker-captured-find $3)
)
(if (flag? more-captures)
(opposite $1)
(markit)
$1
)
(if (not (flag? more-captures))
(opposite $1) 
(if enemy?
capture
)
$1
(capture-all)
)
(if (in-zone? promotion)
(if (flag? more-captures)
(add-partial King jumptype)
else
(add-partial King notype)
)
else
(if (flag? more-captures)
(add-partial jumptype)
else
(add-partial notype)
)
)
))

Більш того, у багатьох шашкових іграх, таких як "Міжнародні шашки", діє «правило більшості», згідно з яким гравець зобов'язаний взяти максимально можлива кількість фігур супротивника. У деяких іграх уточнюється, що пріоритетним має розглядатися взяття найбільшого кількість дамок. Розглядаючи кожен частковий хід окремо, Zillions of Games вимушено вдається до «магії опцій»:

  • (option pass partial» true) — дозволяє переривати ланцюжок взяттів
  • (option «maximal captures» true) — взяти максимальну кількість фігур
  • (option «maximal captures» 2) — взяти максимальну кількість дамок (якщо кількість взятих дамок однаково — брати максимальну кількість фігур)
А тепер, просто порівняйте цей хардкод з тим,…

як аналогічну перевірку виконує Jocly
if(aGame.g.captureLongestLine) {
var moves0=this.mMoves;
var moves1=[];
var bestLength=0;
for(var i in moves0) {
var move=moves0[i];
if(move.pos.length==bestLength)
moves1.push(move);
else if(move.pos.length>bestLength) {
moves1=[move];
bestLength=move.pos.length;
}
}
this.mMoves=moves1;
}

Коли весь складовою хід доступний цілком, ніщо не заважає просто підрахувати кількість виконуваних ним взяттів.

Генерація складеного ходу — це найпростіше застосування ZrfMoveGenerator. Кожен примірник генератора формує свій частковий хід, а самі часткові ходи зчіплюються в «ланцюжок» складеного ходу. На жаль, це не єдиний спосіб, яким ZRF може користуватися, щоб визначати ходи. Розглянемо дуже простий кейс, що описує фігуру, рухається через порожні поля в одному напрямку (наприклад, Слон Ладья і Ферзь Шахах):

Шаховий Rider
(define slide (
$1 (while empty? add $1) 
(verify enemy?)
add
))

Можна бачити, що команда add, що завершує формування ходу, використовується в тілі циклу. Це означає, що фігура може зупинитися на будь-якому порожньому полі, на шляху прямування до ворожої фігури (і це буде вважатися коректним ходом). Зрозуміло, що від такого циклу можна позбутися, переписавши визначення:

У деяких іграх на ZRF доводиться використовувати такий спосіб
(define slide-1 (
$1 (verify enemy?)
add
))

(define slide-2 (
$1 (verify empty?)
$1 (verify enemy?)
add
))

(define slide-3 (
$1 (verify empty?)
$1 (verify empty?)
$1 (verify enemy?)
add
))
...

Команда add, що виконується в тілі циклу, призводить до формування недетерминированного ходу. Фігура може зупинитися або піти далі. Для ZrfMoveGenerator, це означає необхідність клонування. Генератор створює повну копію свого стану і поміщає її в стек, для подальшої генерації, після чого, поточна копія завершує формування ходу. Ось як це виглядає:

Переміщення дамки
(define king-shift (
$1 (while empty?
add $1
)
))

перетворюється в ...
design.addCommand(3, ZRF.FUNCTION, 24); // from
design.addCommand(3, ZRF.PARAM, 0); // $1
design.addCommand(3, ZRF.FUNCTION, 22); // navigate
design.addCommand(3, ZRF.FUNCTION, 1); // empty?
design.addCommand(3, ZRF.FUNCTION, 0); // not
design.addCommand(3, ZRF.IF, 7);
design.addCommand(3, ZRF.FORK, 3);
design.addCommand(3, ZRF.FUNCTION, 25); // to
design.addCommand(3, ZRF.FUNCTION, 28); // end
design.addCommand(3, ZRF.PARAM, 1); // $2
design.addCommand(3, ZRF.FUNCTION, 22); // navigate
design.addCommand(3, ZRF.JUMP, -8);
design.addCommand(3, ZRF.FUNCTION, 28); // end

Команда FORK клонує генератор ходу разом з усім його поточним станом і працює як умовний перехід. У породженому генераторі, управління перейде до наступної команди, а батько передасть управління на задане параметром кількість кроків (так-так, це дуже сильно нагадує створення процесу в Linux).

Тягар сумісностіДля того, щоб ZRF-описи ігор працювали після «трансляції» їх на JavaScript, недостатньо просто виконати аналогічні команди в тому ж порядку. Семантика операцій (в частині взаємодії з станом дошки) повинна повністю збігатися з використовуваної Zillions of Games. Щоб ви уявляли собі всю ступінь заплутаність питання, коротко перерахую основні пункти:

  • Під час генерації ходу, дошка доступна в тому стані, яким воно було на момент початку генерації. Переміщувана фігура не прибирається з вихідного поля і, зрозуміло, не встановлюється на поточне. Це вимога зрозуміло (особливо якщо згадати про иммутабельности дошки), але в реальному житті буває вкрай незручним.
  • Стан прапорів (бітових змінних) і позиційних прапорів (бітових змінних, прив'язаних до конкретних позиціях) доступно лише в процесі генерації ходу. У разі Zillions of Games, розглядає кожен частковий хід як окремий, це сильно знижує їх корисність, але ми повинні забезпечити аналогічну семантику, щоб все працювало.

  • Зберігання атрибутів (іменованих бітових прапорів, прив'язаних до фігур) не обмежена генерацією ходу. Атрибути — частина стану дошки. До речі, самі фігури теж иммутабельны, змінюючи їм якоїсь із атрибутів, ми створюємо нову фігуру.
  • Оскільки стан дошки доступно на момент початку генерації ходу, прочитати атрибут можна лише за місцем початкового розташування фігури, але якщо ми хочемо змінити атрибут, то робити це треба на тій позиції, де фігура завершує своє переміщення (тобто виявиться в момент завершення ходу). Якщо змінити атрибут на іншому полі (наприклад на вихідному) — фатальної помилки не станеться. Значення просто не встановиться.
  • Каскадні ходи не передаються при клонуванні ходів. Вірніше передаються, але тільки якщо відключена опція "discard cascades". Жодного разу не бачив гри, де це використовується!
  • Проміжні взяття і скиди фігур також не передаються у клонований хід. В результаті, взяття королем в «Російських шашках» перетворюється в справжню головоломку (від точки можливого завершення ходу командою add, що виконується у циклі, необхідно рухатися назад, щоб взяти раніше перепрыгнутую ворожу фігуру.
  • Ми не можемо взяти фігуру, у якої на ходу змінився тип, значення атрибута або власник! Це більше схоже на баг, але з пісні слова не викинеш.
  • Якщо хід завершується на позиції містить фігуру, «шахове взяття» виконується автоматично. Якщо на тому ж полі викликати команду capture вочевидь, буде видалена і та фігура, яка виконувала хід (таким чином можна робити фігури-камікадзе). Аналогічним чином (командою create) можна змінювати тип і власника фігури.
  • Якщо включена опція відкладеного взяття, при продовженні ходу, все взяття фігур повинні переміщатися в останній частковий хід складеного ходу. Цієї опції, зі зрозумілих причин, немає в ZRF, але коли вона потрібна, її так не вистачає! Реалізація правила "Турецького удару" в ZRF — це формене мука! На щастя, ми розглядаємо складовою хід цілком. Чому б не реалізувати таку корисну опцію?
Це не повний список. Просто перше, що прийшло в голову. Крім цього, необхідно реалізувати цикл перебору всіх своїх фігур, здатних виконати переміщення (Zillions of Games, гравець може рухати лише свої фігури), а також всіх порожніх полів, на які фігуру можна «скинути».

Все разом це виглядає якось так
var CompleteMove = function(board, gen) {
var t = 1;
if (Model.Game.passPartial === true) {
t = 2;
}
for (var pos in board.pieces) {
var piece = board.pieces[pos];
if ((piece.player === board.player) || (Model.Game.sharedPieces === true)) {
for (var move in Model.Game.design.pieces[piece.type]) {
if ((move.type === 0) && (move.mode === gen.mode)) {
var g = f.copy(move.template, move.params);
if (t > 0) {
g.moveType = t;
g.generate();
if (g.moveType === 0) {
CompleteMove(board, g);
}
} else {
board.addFork(g);
}
t = 0;
}
}
}
}
}

ZrfBoard.prototype.generateInternal = function(callback, cont) {
this.forks = [];
if ((this.moves.length === 0) && (Model.Game.design.failed !== true)) {
var mx = null;
for (var pos in this.pieces) {
var piece = this.pieces[pos];
if ((piece.player === this.player) || (Model.Game.sharedPieces === true)) {
for (var move in Model.Game.design.pieces[piece.type]) {
if (move.type === 0) {
var g = Model.Game.createGen(move.template, move.params);
g.init(this, pos);
this.addFork(g);
if (Model.Game.design.modes.length > 0) {
var ix = Model.find(Model.Game.design.modes, move.mode);
if (ix >= 0) {
if ((mx === null) || (ix < mx)) {
mx = ix;
}
}
}
}
}
}
}
for (var tp in Model.Game.design.pieces) {
for (var pos in Model.Game.design.positions) {
for (var move in Model.Game.design.pieces[tp]) {
if (move.type === 1) {
var g = Model.Game.createGen(move.template, move.params);
g.init(this, pos);
g.piece = new ZrfPiece(tp, this.player);
g.from = null;
g.mode = move.mode;
this.addFork(g);
if (Model.Game.design.modes.length > 0) {
var ix = Model.find(Model.Game.design.modes, move.mode);
if (ix >= 0) {
if ((mx === null) || (ix < mx)) {
mx = ix;
}
}
}
}
}
}
}
while ((this.forks.length > 0) && (callback.checkContinue() === true)) {
var f = this.forks.shift();
if ((mx === null) || (Model.Game.design.modes[mx] === f.mode)) {
f.generate();
if ((cont === true) && (f.moveType === 0)) {
CompleteMove(this, f);
}
}
}
if (cont === true) {
Model.Game.CheckInvariants(this);
Model.Game.PostActions(this);
if (Model.Game.passTurn === 1) {
this.moves.push(new ZrfMove());
}
if (Model.Game.passTurn === 2) {
if (this.moves.length === 0) {
this.moves.push(new ZrfMove());
}
}
}
}
if (this.moves.length === 0) {
this.player = 0;
}
return this.moves;
}

Алгоритм побудований таким чином, щоб продовження ходів «затирали» свої більш короткі «префікси» (зрозуміло, якщо не включена опція "pass partial").

Використовуючи два цих способу (вибудовування генераторів ходів в «ланцюжок» і клонування) можна реалізувати будь-які конструкції мови ZRF. Звичайно, реалізація виходить не простий і, в силу необхідності забезпечення сумісності з семантикою ZRF, досить заплутаною. Це не дуже велика проблема, якщо код працює. Проблема в тому, що сам ZRF далеко не ідеальний!

Розтиснути пальці
Цей рік почався з розчарувань. Для початку, я зайшов в глухий кут у своїх спробах створення універсального DSL, придатного для простого опису всіх відомих мені настільних ігор. Універсально, в принципі, виходило, «зрозуміло» — немає. Навіть відносно прості ігри, такі як Фанорона, норовили описаться в якийсь жах.

Зразок цього(*)[p]|((\1[ex])*;~1(~1[ex])*)

Навіть ZRF це виглядає зрозуміліше
(define approach-capture (
$1
(verify empty?)
to
$1
(verify enemy?)
capture
(while (enemy? $1) до $1 capture)
(add-partial capturing)
))

(define withdrawl-capture (
$1
(verify empty?)
to
back
(opposite $1)
(verify enemy?)
capture
(while (enemy? (opposite $1)) (opposite $1) capture)
(add-partial capturing)
))

C Jocly справа теж якось відразу не задалося. Мені не сподобалася її архітектура. Почнемо з того, що для зберігання стану дошки в ній використовується мутабельный сінглтон Model.Board. Як з цим працювати AI-боту — розуму не прикладу. Але головне навіть не в цьому. Одна модель в неї зовсім не схожа на інший (просто не має нічого спільного). При цьому, активно використовуються «магічні» члени, на зразок mWho або mMoves, а вистава повинна «знати» про те, як влаштована модель, оскільки використовує її нарівні з контролером!

Мої надії «підмінити» модель були заздалегідь приречені на невдачу! Тобто, мені цілком можливо і вдасться підмінити модель "Турецьких шашок" так, щоб з нею працювало відповідне представлениеале для будь-якої іншої гри (навіть для "Англійських шашок") довелося б починати все з початку, тому що її модель від «Турецьких шашок» отличалается досить значно. Я розумів, що не готовий, крім моделі, займатися ще й розробкою подання і перебував у глибокій депресії. А потім, в роботу включився jonic і на горизонті трохи посвітлішало.

Ми вирішили відмовитися від спроб інтеграції з Jocly і розробити відсутні контролери (для мережевих і локальних ігор, а також утиліту autoplay), подання (2D і 3D), а також ботів (в асортименті) самостійно. Причому, всією цією роботою погодився зайнятися jonic, щоб я зміг зосередитися на роботі над моделлю. Першим ділом я позбувся від безглуздих успадкованих обмежень Jocly. Так, тепер модель підтримує ігри для двох гравців! А потім я увійшов у смак…

Це список запланованих мною опцій
  • maximal-captures = true — Правило більшості (наприклад, у «Міжнародних шашках»)

  • pass-partial = true — Можливість переривання складеного ходу (як в «Фанороне»)
  • pass-turn = true — Можливість пропуску ходу
  • pass-turn = forced — Можливість пропуску ходу при відсутності інших ходів
  • discard-cascades = true — Скидання каскадних переміщень при завершенні версії ходу
  • include-off-pieces = true — Облік фігур, які перебувають у резерві при підрахунку
  • recycle-captures = true — Переклад ігор в резерв при виконанні взяття
  • smart-moves = true — Режим «інтелектуального» UI (при наявності єдиного ходу)
  • smart-moves = from — Переміщує фігуру при вказівці стартової позиції
  • smart-moves = to — Переміщує фігуру при вказівці цільової позиції
  • zrf-advanced = true — Всі опції zrf-advanced
  • zrf-advanced = simple — Спрощена семантика переміщення фігур при генерації ходу
  • zrf-advanced = fork — Взяття і скиди переносяться через ZRF_FORK
  • zrf-advanced = composite — Доступність прапорів встановлених попередніми частковими ходами
  • zrf-advanced = mark — Підтримка вкладених викликів mark/back
  • zrf-advanced = delayed — Реалізація правила «Турецького удару» (у всіх шашках, крім турецьких)
  • zrf-advanced = last — Очищення позначок last-from і last-to при завершенні складеного ходу
  • zrf-advanced = shared — Можливість ходу чужими фігурами (як в «Ставропольских шашках»)
  • zrf-advanced = partial — Можливість продовження складеного ходу не тільки фігурою, що завершила часткових хід
  • zrf-advanced = numeric — Підтримка роботи з числовими значеннями (як в «Ритмомахии»)
  • zrf-advanced = foreach — Підтримка оператора foreach для пошуку позиції на дошці
  • zrf-advanced = repeat — Підтримка команди повторення ходу (пропуск ходу усіма гравцями)
  • zrf-advanced = player — Підтримка команд для визначення поточного гравця, наступного, приналежності фігур
  • zrf-advanced = global — Підтримка глобальних значень стану (як Аксіоми)
  • board-model = heap — Зберігання неупорядкованого безлічі фігур на позиції (як у манкалах)
  • board-model = stack — Зберігання упорядкованого безлічі фігур на позиції (як в «Стовпових шашках»)
  • board-model = quantum — Квантова дошка (фігура одночасно присутня на декількох позиціях)

Я ж казав, що обмеження ZRF мені теж не подобаються? Менша частина цих опцій — успадковані параметри Zillions of Games, які необхідно підтримувати. Решта — розширення, досі в ZRF не бачені. Так всі опції zrf-advanced (їх можна включити всі разом, однією командою) — розширюють семантику ZRF, роблячи її більш зручною (я постарався врахувати побажання користувачів Zillions of Games), а опції board-model — вводять нові типи дощок.

Про це варто сказати докладнішеПрацюючи з фігурами на дошці, Zillions of Games дотримується деяких угод. Зокрема, одне ігрове поле не може бути зайнято більш ніж однією фігурою. Наслідком цього є спрощена реалізація «шахового взяття» (не потрібно явно викликати capture для видалення фігури на цільовому поле). Зрозуміло, не у всіх іграх це зручно. Існує ціла категорія ігор (таких, як "Пулук" і "Стовпові шашки"), в яких переміщаються по дошці «стопки» фігур, встановлених один на одного.


До тих пір, поки «стопки» мають обмежену і невелику висоту, можна схитрувати, оголосивши кожне можливе размещение фігур окремим типом фігури. Але можливість такого рішення — швидше виняток, ніж правило. Вже при збільшенні розміру стопки до 6 фігур, кількість типів фігур, необхідних для реалізації кожного розміщення, перевищує можливості Zillions of Games. З цим теж можна боротися, переходячи на роботу з тривимірними дошками, але набагато зручніше мати можливість роботи з впорядкованими послідовностями (розміщеннями) фігур.


Комбінаторні сочетания також затребувані в настільних іграх. Манкалы є найдавнішим і чи не найбільш масовим їх сімейством. Поки мова йде про каміння одного кольору, можна використовувати той же фокус з призначенням окремого типу фігури кожному поєднанню (розробка манкал на ZRF трудомістка, але цілком можлива), але існують манкалы, використовують камені двох і більше типів. Є й інші ігри (такі як Ритмомахия), в яких можливість маніпуляції невпорядкованими наборами фігур вкрай затребувана.


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

Самі опції реалізовані як довантажувати JavaScript-модулі. Наприклад, якщо в грі (як в «Міжнародних шашках») потрібно брати максимальну кількість фігур, необхідно завантажити відповідний модульпісля завантаження zrf-model. Підключення модуля проводиться функцією checkVersion:

ZRF-файлі
...
(option "maximal captures" true)
...

JavaScript-файл
...
design.checkVersion("z2j", "1");
design.checkVersion("zrf", "2.0");
design.checkVersion("maximal-captures", "true");
...

Модель перевірить сумісність версій потрібних модулів і підключить відповідні опції. Цей розширюваний механізм наштовхнув мене на цікаву думку. У деяких іграх існують правила, реалізувати які, використовуючи тільки ZRF, диявольськи важко. У більшості випадків, ці правила зводяться до додатковим перевіркам, що впливає на можливість виконання того чи іншого ходу. Винесення перевірок у довантажувати опції позбавить мене від необхідності розширення базової мови для їх реалізації (що було б зовсім не просто).

Варто відзначити, що розробники Zillions of Games пішли по тому ж шляхуВони чудово усвідомлювали, що хоча правила деяких ігор (наприклад Го) і можуть бути описані на ZRF (дуже складно), це ніяк не допоможе AI, вбудованому в Zillions of Games, впоратися з самими іграми. У програму додана можливість «розширення» ігор, підключенням спеціально розроблених DLL-модулів. Хоча API цих розширень досить незручно і розраховане лише на взаємодію з AI, деякі розробники стали використовувати спільні бібліотеки і для генерації ходів.

Апофеозом роботи в цьому напрямку стала розробка Грегом Шмідтом його Axiom Development Kit — опускається бібліотеки, яка виконує генерацію ходів, на підставі описів ігор, виконаному на мові ForthScript. Вона багаторазово розширила можливості Zillions of Games, але не зробила процес розробки більш комфортним. Використовуючи JavaScript, я перебуваю в більш вигідному становищі. Принаймні, мені не доведеться збирати свої розширення!

Поясню на прикладі. Існує різновид «Турецьких шашок», про яку я дізнався нещодавно. Єдина відмінність «Бахрейнських шашок» від турецьких полягає в тому, що в них заборонено відповідати нападом на напад противника. Можна з'їсти напала фігуру або піти з-під удару, але не можна напасти на іншу фігуру у відповідь! З урахуванням того, що правило поширюється і на дамки, реалізація цієї гри на ZRF вийшла доволі складною і, що найголовніше, не дуже «прозорою». Але якщо я використовую розширювані опції, мені немає ніякої необхідності ускладнювати код в ZRF!

Bahrain Dama
(variant 
(title "Bahrain Dama")
(option "bahrain dama extension" true)
)

Я можу взяти "Турецькі шашки" і підключити опцію виконує необхідні перевірки. Подгружаемый модуль підміняє метод постобробки ходу і, при необхідності, може заборонити раніше згенерований хід! Сама логика перевірки може бути як завгодно складною, вона все одно буде зрозуміліше аналогічної реалізації на ZRF! Справа не обмежується додаткової валідацією вже згенерованих ходів. Опція може «збагачувати» хід! Наприклад, виконуючи хід в "Го", необхідно зробити наступне:

  • Перевірити 4 сусідніх каменю (3 на кордоні дошки або 2 в кутку).
  • Якщо сусідній камінь належить ворогу, побудувати «зв'язне» групу каменів, в яку він входить, і порахувати кількість її дамэ (вільних пунктів, з якими межує група).
  • Якщо ворожа група не межує з вільними пунктами — видалити всі її камені.
  • Якщо ні одна з ворожих груп не видалена, побудувати групу, яка містить доданий камінь
  • Якщо побудованої групи немає дамэ, заборонити хід (Строго кажучи, не завжди. Правилами Інга дозволений суїцид груп, що складаються з більш ніж одного каменю).
Все це можна «заховати» в JavaScript-расширение! Воно не тільки виконає необхідні перевірки, але і доповнить хід видаленням ворожих каменів. ZRF-опис гри стає елементарним! Більш того, теж розширення підходить і для інших ігор! Наприклад, для "Багатоколірного Го".

Більше ніж один хід...
Розширювані опції дозволили поглянути на проект по новому, але одна маленька завдання раніше не давала мені спокою. В деяких іграх, при певних умовах, допускається взяття з дошки будь фігури противника. Наприклад, у "Млині":

  • Гравці ставлять на дошку і переміщують свої фігури, намагаючись поставити 3 фігури «в ряд».
  • Якщо це вдається, гравець отримує право зняти з дошки будь-яку фігуру супротивника.
  • При цьому, повинна віддаватися перевага фігурам не стоять «в ряду» (фігури складові ряд беруться в останню чергу).
  • Якщо у гравця залишається 3 фігури, він отримує можливість переміщати їх у будь-який місце дошки (не тільки за зазначеними лініями).
  • Програє гравець, у якого залишилося менше 3 фігур.

не Можна сказати, що це нереально на ZRF, але код виходить дуже заплутаний. Ну і взагалі, генерація набору ходів, однакових практично у всьому, крім забирається фігури — досить сумне рішення. Я подумав, що було б набагато зручніше, якби в діях ходів можна було використовувати масиви позицій:

ZrfMove.prototype.capturePiece = function(pos, part) {
- this.actions.push([ pos, null, null, part]);
+ this.actions.push([ [pos], null, null, part]);
}

Це була досить-таки глобальна переделка коду, але unit-тести, в черговий раз, допомогли. Поки такі недетерміновані ходи планується формувати тільки з JavaScript-розширень, в рамках «збагачення» ходів, що формуються максимально простим ZRF-описом гри. Якщо говорити про "Мельнице", то мова йде про все те ж додаванні в хід взяттів фігур. Просто замість набору одиночних взяттів, додається одне недетерминированное:

Магія недетермінізму
Model.Game.CheckInvariants = function(board) {
var design = Model.Game.design;
var cnt = getPieceCount(board);
for (var i in board.moves) {
var m = board.moves[i];
var b = board.apply(m);
for (var j in m.actions) {
fp = m.actions[j][0];
tp = m.actions[j][1];
pn = m.actions[j][3];
if ((fp !== null) && (tp !== null) {
if (checkLine(b, tp[0], board.player) === true) {
var all = [];
var captured = [];
var len = design.positions.length;
for (var p = 0; p < len; p++) {
var piece = b.getPiece(p);
if (piece.player !== board.player) {
if ((checkLine)(b, p, b.player) === false) {
captured.push(p);
}
all.push(p);
}
}
if (captured.length === 0) {
captured = all;
}
if (captured.length > 0) {
captured.push(null);
m.actions.push([captured, null, null, pn]);
}
}
...
break;
}
}
}
CheckInvariants(board);
}

Але це більш широка концепція. Не тільки взяття може бути недетерминированным! Пам'ятайте, що в «Млині» є правило, за яким три залишилися фігури гравця можуть стрибати «куди завгодно». Фактично, це недетерминированное переміщення на будь-яку вільну позицію:

Ще трохи магії
...
if (cnt === 3) {
var len = design.positions.length;
for (var p = 0; p < len; p++) {
if (p !== tp[0]) {
var piece = board.getPiece(p);
if (piece === null) {
tp.push(p);
}
}
}
}
...

Переміщувана фігура також може бути масивом! Згідно з правилами перетворення в Шахах, пішак, досягаючи останньої горизонталі, може перетворитися в будь-яку з 4 фігур (Кінь, Слон, Човен, Ферзь), на вибір гравця. Це ні що інше як недетерминированное перетворення, що виконується при переміщенні фігури. У ZRF-коді пішака можна перетворити, наприклад, в ферзя, а в JavaScript-расширении:

… збагатити це перетворення
var promote = function(arr, name, player) {
var design = Model.Game.design;
var t = design.getPieceType(name);
if (t !== null) {
arr.push(design.createPiece(t player));
}
}

Model.Game.CheckInvariants = function(board) {
var design = Model.Game.design;
for (var i in board.moves) {
var m = board.moves[i];
for (var j in m.actions) {
fp = m.actions[j][0];
tp = m.actions[j][1];
if ((fp !== null) && (tp !== null) {
var piece = board.getPiece(fp[0]);
if ((piece !== null) && (piece.getType() === "Pawn")) {
var p = design.navigate(board.player, tp[0], design.getDirection("n"));
if (p === null) {
var promoted = [];
promote(promoted, "Queen", board.player);
promote(promoted, "Rook", board.player);
promote(promoted, "Knight", board.player);
promote(promoted, "!", board.player);
if (promoted.length > 0) {
m.actions[j][2] = promoted;
}
}
}
break;
}
}
}
CheckInvariants(board);
}

Для контролера змінюється мало. Отримавши від моделі хід, допустимий для поточного стану дошки, він повинен перевірити розмір масивів в кожному з дій. Якщо передається більше одного елемента, контролер повинен перебрати всі можливі варіанти, формуючи детерміновані ходи. Думаю, не варто говорити про те, що з подібним недетерминизмом слід бути обережним. Декартів добуток кількох незалежних позицій здатне породити просто неймовірна кількість різних ходів!

підсумки
В цілому, можу сказати, що мені подобається напрямок розвиток проекту. Я відмовився від ідеї створення чогось революційно нового (хоч це було і не просто) і зосередився на досяжних, але ані трохи не менш цікавих цілях. Можна сказати, що з двох відомих птахів я віддаю перевагу «синицю в руках». Робота над проектом допомагає освоїти новий для мене мова, а приєднання до проекту нового, більш досвідченого розробника несе надію, що робота все-таки увінчається успіхом. Я відмовився від «революції», але проект продовжує еволюціонувати!

Джерело: Хабрахабр

0 коментарів

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