Dagaz: эволюция вместо революции / forpes.ru

Главная
Dagaz: эволюция вместо революции

Dagaz: эволюция вместо революции +22

03.02.2017 06:12

GlukKazan 9 3400 Источник

В этом мире того, что хотелось бы нам НЕТ!
Мы верим, что в силах его изменить ДА!

Юрий Шевчук

Те из вас, кто читал мои статьи, должны знать о том, что я, довольно давно, занимаюсь изучением метаигровой системы 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-схеме. Для разработки новой игры требуется написать её модель и представление. Модель определяет правила игры, а представление — то, как игра будет показана пользователю. Контроллер, написанный разработчиками, берёт на себя всё остальное (включая зашитых в него ботов).

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

Для генерации хода (создания объекта Move), используется текущее состояние Board, но одного лишь его недостаточно для реализации всех возможностей ZRF. В процессе генерации хода, ZRF может использовать переменные (флаги и позиционные флаги), не являющиеся частью игрового состояния. Всем этим, а также логикой выполнения команд стековой машины, занимается Move Generator. Если говорить вкратце, такова архитектура модуля zrf-model.js.

Дьявол в деталях

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

Хранение текущего состояния игры
Генерация всех ходов, допустимых для текущего состояния игры
Изменение состояния игры, путём применения к нему одного из сгенерированных ходов

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

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, но и ведёт к более серьёзным проблемам.

Здесь показана последовательность позиций, возникающих при выполнении составного хода в игре "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-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, "Bishop", board.player);
                        if (promoted.length > 0) {
                            m.actions[j][2] = promoted;
                        }
                    }
                }
                break;
            }
       }
  }
  CheckInvariants(board);
}

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

Промежуточные итоги

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

Поделиться с друзьями

-->

Комментарии (9)

Deosis
03.02.2017 15:29
#10051606
+1
А чем не устроило описание наподобие регулярных выражений?
Просто сложные ходы можно попытаться описать отдельно. Например:
player-turn player-king-unmoved east empty-unattacked empty-unattacked (?: (1:player-pawn-unmoved)) \1 west any any

для короля: anyDir (empty|enemy-capture)-unnattacked
def Leap = empty|(enemy-capture?)
def Ride = empty* Leap
ферзь: anyDir Ride
Слон: digDir Ride
Ладья: crossDir Ride
Конь: (forward any forwardDiag Leap) | (backward any backwardDiag Leap)|…
Пешка: forward empty lastline-promote | forwardDiag enemy-capture | secondline forward empty empty trigger-fastmove |
(?: west (1:enemy-fastmove)) northwest any (?:\1-capture) | (?: east (1:enemy-fastmove)) northeast any (?:\1-capture)
1. GlukKazan
  03.02.2017 15:52
  #10051658
  Слишком сложно получается (я уже всю голову на эту тему сломал). Пока речь идёт просто о причудливых шахматных перемещениях, типа Chu Shogi, всё более-менее нормально (хотя там тоже чудес хватает). Шашки и, например, Фанорона уже заставляют напрячься. Когда дело доходит до манкал и "Болотуду", начинаешь рвать на себе волосы. Ну а как выразить «регэкспами» правила Го или, например "Ордо" или "Ритмомахию", я просто не представляю. Отсюда родилась идея обогащения ходов. Описать всё что описывается просто DSL-ем (да хоть и регэкспами), создав заготовку с простейшим перемещением фигур, а всю сложную логику вынести в JavaScript-расширения (благо писать их легче чем ZoG-расширения на C++).
1. GlukKazan
  03.02.2017 15:56
  #10051666
  Вот тут много писал по этому поводу.

morgreek
03.02.2017 20:21
#10052296
Отказываться от чего-то, во то вложено много времени и сил, и вправду очень тяжело. Но, похоже, был сделан правильный выбор в пользу разработки своих компонентов — разжав пальцы, сбросили и оковы (судя по списку запланированных опций — много оков).
Успехов в дальнейшей эволюции! И мне кажется, что создателям Jocly про это тоже можно было узнать.
1. GlukKazan
  05.02.2017 15:55
  #10053646
  Спасибо. Пока нет работающего прототипа, им нет смысла писать.
  Когда получится что-то работающее, конечно попробую связаться.

XVadim
05.02.2017 20:08
#10053820
+1
Всегда с интересом читаю статьи GlukKazan
Желаю удачного развития проекта.
1. GlukKazan
  05.02.2017 20:19
  #10053828
  Спасибо, Вадим. Ваша статья про Пулук мне тоже понравилась.
  Не хотите продолжить? Рекомендую Шен.
  1. XVadim
    06.02.2017 20:32
    #10055428
    +1
    Хм… что-то мой ответ не отправился. Повторю.
    
    Я уже давненько думаю о реализации Дальдозы. А с недавнего времени еще и Сиджы. Ее правила я узнал еще в детстве. Есть возможность сделать и наконец-то поиграть :)
    
    GlukKazan
    06.02.2017 20:47
    #10055438
    Дальдозу я сделал, но вроде не совсем правильно. Вроде бы, при активации фигуры должны оставаться на месте, но у меня бред какой-то получался. Сделал, чтобы двигались на единичку. Хорошая игра, молодцы викинги. Сиджа тоже ничего.