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 can do almost anything 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("e");
    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-схеме. Для разработки новой игры требуется написать её модель и представление. Модель определяет правила игры, а представление — то, как игра будет показана пользователю. Контроллер, написанный разработчиками, берёт на себя всё остальное (включая зашитых в него ботов).
b8c9589e0d7f4a7bb13babe05148c6d8.PNG

Архитектура универсальной модели, реализуемой Z2J также не очень сложна. Основу составляет компонент Design, содержащий неизменяемое описание правил игры. Состояние игры (размещение фигур на доске) хранится в экземплярах класса Board. Данные этих компонентов также не изменяются. Выполняя ход (применяя объект Move к Board), мы создаём новое состояние. Старое остаётся неизменным!
db6d21e9d485452682cea190633bb5d0.PNG

Для генерации хода (создания объекта 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 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, но и ведёт к более серьёзным проблемам.
75969aa342a24d159fccd076e7998d08.PNG

Здесь показана последовательность позиций, возникающих при выполнении составного хода в игре «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 — Поддержка глобальных значений состояния (как в Axiom)

  • 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-mo

© Habrahabr.ru