Аксиома — повышаем градус!

          Старый серый ослик Иа-Иа стоял один-одинешенек в заросшем чертополохом уголке Леса, широко расставив передние ноги и свесив голову набок, и думал о Серьезных Вещах.

                  Генрих Альтов «Ослик и аксиома»

Что самое сложное в разработке настольных игр? Очевидно, не анимация перемещения фигур по доске. Сложно придумать разумные и интересные игровые правила. Бывает очень сложно обеспечить игровой баланс. Если мы занимаемся компьютерной разработкой, зачастую, безумно сложно реализовать качественный AI (для таких игр как Го или Сёги эта проблема не решена до сих пор). И даже если нам удалось реализовать работающий AI, приходится проделать очень большой объем работ, чтобы оценить качество его работы и выбрать из нескольких возможных вариантов наилучший.

Я хочу рассказать об инструменте, способном существенно упростить решение всех этих вопросов. Axiom Development Kit задумывалась разработчиками как способ улучшения Zillions of Games. В частности, она ориентирована на реализацию игр, связанных с захватом территории (таких как Го), с которыми AI ZoG справляется очень плохо. Кроме того, Аксиома существенно расширяет возможности ZoG-разработчиков, предоставляя массу возможностей, практически не реализуемых в рамках традиционного ZRF (языка описания правил). При всём этом, Аксиома может работать совершенно самостоятельно, даже если ZoG на компьютер никогда не устанавливался и не покупался. Но, обо всём по порядку…

По образу и подобию

Я уже писал о том, что у ZoG имеется множество недостатков. К счастью, разработчики предоставили механизм, позволяющий справиться с частью из них. Модуль расширения (engine) представляет собой динамически загружаемую библиотеку (DLL), берущую под своё управление все аспекты игры, кроме её визуализации. Вот здесь можно посмотреть пример такого расширения.

Самостоятельная разработка собственного расширения может оказаться весьма трудоёмкой. Придётся разрабатывать AI (скорее всего на C++), поскольку, при подключении engine, штатный AI ZoG отключается. Axiom представляет собой программируемый engine, реализующий такие сложные для разработчика вещи, как алгоритмы AI и предоставляющий возможность сосредоточиться на игровой логике.

Для работы необходим минимальный ZRF-файл:

(version "2.0")

(game
   (title "Ur")

   (engine "../Axiom/Ur/axiom.dll")

   (option "animate captures" false)
   (option "animate drops" false)
   (option "show moves list" false)
   (option "pass turn" forced)
   (option "highlight goals" false)
   (option "prevent flipping" true)
   (option "recycle captures" true)

   (drop-sound "Audio/Dice_cup.wav")
   (move-sound "Audio/Clack.wav")
   (capture-sound "")

   (players Black White ?Dice)

   (turn-order White ?Dice ?Dice ?Dice ?Dice Black ?Dice ?Dice ?Dice ?Dice)

   (board 
      (image "ImagesUrboard.bmp")
      (grid
         (start-rectangle -503 -13 -442 79)
         (dimensions
             ("a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q" (67 0)) ; files
             ("5/4/3/2/1" (0 66)) ; ranks
         )    
      )
   )

   (board-setup
          (?Dice (wdice q4) (bdice q3 q2) (lock q1) )
          (Black (init i5 j5 k5 l5 m5 n5 o5) )
          (White (init i1 j1 k1 l1 m1 n1 o1) )
   )

   (piece
	  (name lock)
          (image ?Dice "ImagesUrinvisible.bmp"
                 Black "ImagesUrinvisible.bmp"
                 White "ImagesUrinvisible.bmp")
   )
   (piece
	  (name  init)
          (image Black "ImagesUrbinit.bmp"
                 White "ImagesUrwinit.bmp")
   )
   (piece
	  (name  prom)
          (image Black "ImagesUrbprom.bmp"
                 White "ImagesUrwprom.bmp")
   )
   (piece
	  (name wdice)
          (image ?Dice "ImagesUrwdice.bmp")
   )
   (piece
	  (name bdice)
          (image ?Dice "ImagesUrbdice.bmp")
   )

   ; The following dummy piece is required in order to placate the Zillions engine.
   ; It appears as though Zillions must find at least one "moves" keyword somewhere
   ; in the zrf in order for it to be happy and thus allow "moves" to work correctly.
   (piece (name Dummy) (dummy) (moves (from)))
)

Здесь осталось описание игроков, последовательности ходов, фигур, но нет описания правил, по которым ходят фигуры. Также отсутствуют определения направлений на доске, игровых зон, условий завершения игры и всего прочего, связанного с игровыми правилами. Всё это будет содержаться в скриптах Аксиомы. Грустным моментом является то, что интерфейс взаимодействия ZoG с engine не предусматривает передачи информации, содержащейся в ZRF-файле. Это означает, что все эти описания придётся продублировать в скриптах Axiom.

К счастью, в составе Axiom Development Kit поставляется утилита, позволяющая автоматизировать этот процесс. ZRF Converter довольно капризен в работе. Если ему что-то не понравилось в ZRF-файле (например описание доски вынесенное в макрос), процесс конвертации прерывается с загадочной диагностикой, заставляющей поломать голову. Если всё прошло нормально, на выходе мы получаем следующее описание:

{board
	{position}	a5
	{position}	b5
	{position}	c5
	{position}	d5
	{position}	e5
	{position}	f5
	{position}	g5
	{position}	h5
	{position}	i5
	{position}	j5
	{position}	k5
	{position}	l5
	{position}	m5
	{position}	n5
	{position}	o5
	{position}	p5
	{position}	q5
	{position}	a4
	{position}	b4
	{position}	c4
	{position}	d4
	{position}	e4
	{position}	f4
	{position}	g4
	{position}	h4
	{position}	i4
	{position}	j4
	{position}	k4
	{position}	l4
	{position}	m4
	{position}	n4
	{position}	o4
	{position}	p4
	{position}	q4
	{position}	a3
	{position}	b3
	{position}	c3
	{position}	d3
	{position}	e3
	{position}	f3
	{position}	g3
	{position}	h3
	{position}	i3
	{position}	j3
	{position}	k3
	{position}	l3
	{position}	m3
	{position}	n3
	{position}	o3
	{position}	p3
	{position}	q3
	{position}	a2
	{position}	b2
	{position}	c2
	{position}	d2
	{position}	e2
	{position}	f2
	{position}	g2
	{position}	h2
	{position}	i2
	{position}	j2
	{position}	k2
	{position}	l2
	{position}	m2
	{position}	n2
	{position}	o2
	{position}	p2
	{position}	q2
	{position}	a1
	{position}	b1
	{position}	c1
	{position}	d1
	{position}	e1
	{position}	f1
	{position}	g1
	{position}	h1
	{position}	i1
	{position}	j1
	{position}	k1
	{position}	l1
	{position}	m1
	{position}	n1
	{position}	o1
	{position}	p1
	{position}	q1
board}

{players
	{player}	Black
	{player}	White
	{player}	?Dice	{random}
players}

{pieces
	{piece}		lock
	{piece}		init
	{piece}		prom
	{piece}		wdice
	{piece}		bdice
	{piece}		Dummy
pieces}

{turn-order
	{repeat}
	{turn}	White
	{turn}	?Dice
	{turn}	?Dice
	{turn}	?Dice
	{turn}	?Dice
	{turn}	Black
	{turn}	?Dice
	{turn}	?Dice
	{turn}	?Dice
	{turn}	?Dice
turn-order}

{board-setup
	{setup}	?Dice wdice q4
	{setup}	?Dice bdice q3
	{setup}	?Dice bdice q2
	{setup}	?Dice lock q1

	{setup}	Black init i5
	{setup}	Black init j5
	{setup}	Black init k5
	{setup}	Black init l5
	{setup}	Black init m5
	{setup}	Black init n5
	{setup}	Black init o5

	{setup}	White init i1
	{setup}	White init j1
	{setup}	White init k1
	{setup}	White init l1
	{setup}	White init m1
	{setup}	White init n1
	{setup}	White init o1
board-setup}

Здесь нас поджидают первые сюрпризы. Axiom позволяет описывать доску более компактно, но с серьёзными ограничениями. Конструкция grid позволяет описывать только прямоугольные доски со «стандартным» именованием ячеек (кроме того, в описании доски может использоваться только один grid). В случае необходимости описания досок более сложной формы (например трёхмерных), придётся явно описывать каждую позицию так, как это сделал ZRF Converter. Поскольку, в нашем случае, все ограничения соблюдаются (мне пришлось переименовать столбцы и строки доски, по сравнению с ZRF-реализацией), используем более компактную запись:

{board
	5 17 		{grid}
board}

Далее, необходимо определить направления, по которым смогут двигаться фигуры. В таких играх как Шахматы или Шашки, мы могли бы использовать компактную запись, определяющую направления в терминах приращения координат:

{directions 
  -1  0 {direction}  North 
   1  0 {direction}  South 
   0  1 {direction}  East 
   0 -1 {direction}  West 
  -1  1 {direction}  Northeast 
   1  1 {direction}  Southeast 
  -1 -1 {direction}  Northwest 
   1 -1 {direction}  Southwest 
directions}

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

{directions
	( Anext )
	{link}		Anext i1 l2
	{link}		Anext j1 l2
	{link}		Anext k1 l2
	{link}		Anext l1 l2
	{link}		Anext m1 l2
	{link}		Anext n1 l2
	{link}		Anext o1 l2
	{link}		Anext l2 k2
	{link}		Anext k2 j2
	{link}		Anext j2 i2
	{link}		Anext i2 i3
	{link}		Anext i3 j3
	{link}		Anext j3 k3
	{link}		Anext k3 l3
	{link}		Anext l3 m3
	{link}		Anext m3 n3
	{link}		Anext n3 o3
	{link}		Anext o3 o2
	{link}		Anext o2 p2
	{link}		Anext p2 p3
	{link}		Anext p3 p4
	{link}		Anext p4 o4
	{link}		Anext o4 o3

	( Bnext )
	{link}		Bnext i5 l4
	{link}		Bnext j5 l4
	{link}		Bnext k5 l4
	{link}		Bnext l5 l4
	{link}		Bnext m5 l4
	{link}		Bnext n5 l4
	{link}		Bnext o5 l4
	{link}		Bnext l4 k4
	{link}		Bnext k4 j4
	{link}		Bnext j4 i4
	{link}		Bnext i4 i3
	{link}		Bnext i3 j3
	{link}		Bnext j3 k3
	{link}		Bnext k3 l3
	{link}		Bnext l3 m3
	{link}		Bnext m3 n3
	{link}		Bnext n3 o3
	{link}		Bnext o3 o4
	{link}		Bnext o4 p4
	{link}		Bnext p4 p3
	{link}		Bnext p3 p2
	{link}		Bnext p2 o2
	{link}		Bnext o2 o3

	( Cnext )
	{link}		Cnext p3 p4
	{link}		Cnext p4 o4
	{link}		Cnext o4 o3
	{link}		Cnext o3 n3
	{link}		Cnext n3 m3
	{link}		Cnext m3 l3
	{link}		Cnext l3 k3
	{link}		Cnext k3 j3
	{link}		Cnext j3 i3
	{link}		Cnext i3 h3

	( Dnext )
	{link}		Dnext p3 p2
	{link}		Dnext p2 o2
	{link}		Dnext o2 o3
	{link}		Dnext o3 n3
	{link}		Dnext n3 m3
	{link}		Dnext m3 l3
	{link}		Dnext l3 k3
	{link}		Dnext k3 j3
	{link}		Dnext j3 i3
	{link}		Dnext i3 h3
directions}

Чёрные и белые фишки движутся различными путями, поэтому пришлось определить направление Anext для белых и Bnext для чёрных фигур. Кроме того, для фишек, прошедших через поле превращения, необходимо доопределить направления Cnext и Dnext. Если этого не сделать, на поле o3 образуется развилка и все фишки будут крутиться по кругу в малом блоке, выбирая первый из доступных маршрутов.

{symmetries 
	Black		{symmetry} Anext Bnext
	Black		{symmetry} Cnext Dnext
symmetries}

Эта конструкция позволяет определить «симметрию». Хорошей иллюстрацией может служить движение пешек в Шахматах. Пешки всегда двигаются «вперёд», но для белых это движение вверх по доске, а для чёрных — в противоположном направлении. Существуют и более сложные формы симметрии. Например в четырёхсторонних вариантах Шахмат, движение «вперёд», в зависимости от цвета, может происходить в направлении любой из четырёх «сторон света». Определив «симметрию», мы cможем всегда использовать одно и тоже направление (например Anext), не обращая внимания на цвет фигуры. Для чёрных, оно будет автоматически преобразовано в симметричное (Bnext).

Фортификация

Моё знакомство с Фортом было ранним, но очень долгое время оставалось весьма шапочным. Впервые я увидел Форт во времена БК-шек и Микрош. У моего друга был Вектор 06Ц, оттащить от которого нас удавалось только за уши, совместными усилиями всех родителей. К Вектору, периодически, докупались кассеты с играми, а на них, время от времени, обнаруживалась «неучтенка». Среди такой неучтенки, мы и нашли реализацию Форта. Вволю наигравшись со стеком, мы с другом сказали «ага», и установили основание системы счисления в ноль (есть в Форте такая забавная возможность). Форт естественно не смог этого перенести и мы про него, на некоторое время, забыли.

Впоследствии, уже в институте, Форт неоднократно всплывал на поверхность моего внимания, но заняться им серьезно никак не удавалось. В самом деле, мне так и не довелось столкнуться ни с программированием микроконтроллеров ни с каким либо другим полезным применением Форта. И вот теперь, благодаря разработчикам Axiom, у меня такая возможность появилась! Дело в том, что слово Forth фигурирует в их ForthScript не просто так. На самом деле, и сама Axiom-а и часть ForthScript-а реализованы на Форте, а в axiom.dll имеется интерпретатор, позволяющий их использовать. При необходимости, в axiom.4th и CORE.4TH можно посмотреть детали реализации, а возможно и что-то подправить.

Итак, программировать всю игровую логику придётся на Форте. Но с чего начать разработку? Для начала, было бы неплохо добиться простого движения фигур по доске. Каждая фигура должна иметь возможность двигаться на 1, 2, 3 или 4 клетки по своей траектории движения (пока не будем отвлекаться на выбрасывание случайных очков на «костях»):

: common-move ( 'dir n -- )
	SWAP
	BEGIN
		DUP EXECUTE verify SWAP
		1-  DUP
		0=  IF
			DROP
			TRUE
		ELSE
			SWAP
			FALSE
		ENDIF
	UNTIL
	empty? IF
		from
		here
		move
		add-move
	ENDIF
;

: i-move-1 ( -- ) ['] Anext 1 common-move ;
: i-move-2 ( -- ) ['] Anext 2 common-move ;
: i-move-3 ( -- ) ['] Anext 3 common-move ;
: i-move-4 ( -- ) ['] Anext 4 common-move ;
: p-move-1 ( -- ) ['] Cnext 1 common-move ;
: p-move-2 ( -- ) ['] Cnext 2 common-move ;
: p-move-3 ( -- ) ['] Cnext 3 common-move ;
: p-move-4 ( -- ) ['] Cnext 4 common-move ;

{moves i-moves
	{move} i-move-1
	{move} i-move-2
	{move} i-move-3
	{move} i-move-4
moves}

{moves p-moves
	{move} p-move-1
	{move} p-move-2
	{move} p-move-3
	{move} p-move-4
moves}

{pieces
	{piece}		init	{moves} i-moves
	{piece}		prom	{moves} p-moves
pieces}

Запустив ZRF-ку на выполнение, можно убедиться, что теперь фигуры можно двигать. Как всё это работает? Посмотрим на реализацию common-move. Комментарий (в стиле Форта), расположенный сразу после имени, показывает, что она принимает на стеке два параметра — скомпилированную команду перехода по направлению и количество шагов перемещения. Сама реализация состоит из двух частей. Сначала, в цикле, заданное количество раз, выполняется переход по направлению, затем, после проверки того, что целевое поле пусто, выполняется последовательность команд Axiom, формирующих ход (перемещение фишки). Самое главное, во время всей этой эквилибристики — не разрушить стек!

Описание каждой из выполняемых команд можно посмотреть в руководствах по ForthScript и Axiom, поставляемых в комплекте с Axiom Development Kit, я же хочу обратить ваше внимание на пару важных отличий этого кода от того, что можно было бы написать используя ZRF:

• В Axiom команда перехода по направлению (в скрипте выше она выполняется при помощи EXECUTE) формирует булевский код, используя который можно проверить успешность перехода (если направление в заданной клетке не определено, переход не производится и на стек кладётся FALSE)
• Команда завершения формирования хода add-move отделена от команды перемещения фигуры move (я уже писал, в одной из своих статей, почему это так важно)!

Поигравшись с этой версией некоторое время, можно заметить, что фишки, дойдя до малого блока, начинают ходить по кругу. Для того, чтобы фишка могла вырваться из этого «круга сансары», её необходимо перевернуть (для перевёрнутых фишек заданы направления Cnext и Dnext, ведущие к финишу). Напомню, что переворачивание фишек, в игре Ур, хитрое. Фишка переворачивается не встав на поле превращения, а проходя через него. Кроме того, поскольку теперь фишки смогут проходить весь путь до конца, не забудем об удалении с доски фишек, дошедших до финиша:

VARIABLE	isPromouted

: common-move ( 'dir n -- )
	FALSE isPromouted !
	SWAP
	BEGIN
		current-player White
		= IF
			here p2
		ELSE
			here p4
		ENDIF
		= IF TRUE isPromouted ! ENDIF
		DUP EXECUTE verify SWAP
		1-  DUP
		0=  IF
			DROP
			TRUE
		ELSE
			SWAP
			FALSE
		ENDIF
	UNTIL
	empty? IF
		from
		here
		move
		here h3 = IF
			capture
		ENDIF
		isPromouted @ IF
			current-piece-type 1+ change-type
		ENDIF
		add-move
	ENDIF
;

Здесь стоит сказать пару слов о переменных в Форте. Мы определяем переменную isPromouted, используя ключевое слово VARIABLE. После того как переменная определена, любое её упоминание в коде кладёт на стек адрес этой переменной. Для извлечения значения, расположенного по заданному адресу, используется команда @, команда ! перезаписывает значение переменной.

Некоторую сложность, в Axiom, представляют манипуляции с типами фигур. Дело в том, что определения фигур расположены после кода, управляющего их перемещением (поскольку они его используют). По этой причине, мы не можем использовать имена типов фигур в коде (так как в этом месте они ещё не определены). Как правило, из этой неприятной ситуации можно выкрутиться. Например, в нашем коде, для переворачивания фишки, мы просто инкрементируем тип фигуры, выполняющей ход.

Важной частью игрового процесса является возможность пропуска хода игроками. Игрок обязан выполнить ход, если есть такая возможность и пропустить ход, в противном случае. Если не позаботиться об этом специально, игра будет автоматически завершена вничью при первой же невозможности хода любым из игроков. Также, пропуском хода противника, логично реализовать повторный ход игрока после хода на «розетку». Сделаем это:

: is-rosette? ( -- ? )
	here i2 =
	here i4 = OR
	here l3 = OR
	here o2 = OR
	here o4 = OR
;

: common-move ( 'dir n -- )
	q5 enemy-at? NOT IF
		FALSE isPromouted !
		SWAP
		BEGIN
			current-player White
			= IF
				here p2
			ELSE
				here p4
			ENDIF
			= IF TRUE isPromouted ! ENDIF
			DUP EXECUTE verify SWAP
			1-  DUP
			0=  IF
				DROP
				TRUE
			ELSE
				SWAP
				FALSE
			ENDIF
		UNTIL
		empty? IF
			from
			here
			move
			here h3 = IF
				capture
			ENDIF
			isPromouted @ IF
				current-piece-type 1+ change-type
			ENDIF
			is-rosette? IF
				q1 piece-type-at q5 create-piece-type-at
			ELSE  
				q5 capture-at
			ENDIF
			add-move
		ENDIF
	ENDIF
;

: pass-move ( -- )
	q5 capture-at
	Pass
	add-move
;

{moves i-moves
	{move} i-move-1  {move-type} normal-type
	{move} i-move-2  {move-type} normal-type
	{move} i-move-3  {move-type} normal-type
	{move} i-move-4  {move-type} normal-type
	{move} pass-move {move-type} pass-type
moves}

{moves p-moves
	{move} p-move-1  {move-type} normal-type
	{move} p-move-2  {move-type} normal-type
	{move} p-move-3  {move-type} normal-type
	{move} p-move-4  {move-type} normal-type
	{move} pass-move {move-type} pass-type
moves}

{move-priorities
	{move-priority} normal-type
	{move-priority} pass-type
move-priorities}

Первым в глаза бросается заковыристое определение is-rosette?. К сожалению, в Axiom, в отличии от ZRF, нет возможности определения игровых зон. Все поля приходится проверять индивидуально.

Реализация пропуска хода также отличается от подхода, используемого в ZRF. Установка опции "pass turn" игнорируется Аксиомой. Вместо этого, пропуск хода должен формироваться явно, командой Pass. Это один из примеров более полного использования возможностей нотации записи ходов ZSG (используемой для передачи хода из engine в ZoG). Другим таким примером является возможность использования команд сброса (drops) при выполнении частичных ходов (partial moves), не реализованная в ZRF.

Для того, чтобы пропуск хода работал только при отсутствии возможности какого либо другого хода, необходимо использовать приоритеты. Ход, имеющий более низкий приоритет, может быть выполнен только при отсутствии возможности хода с более высоким приоритетом. К сожалению, пропуск хода в стиле Axiom функционально не полностью эквивалентен поведению ZoG, при установке опции "pass turn" в force. В ZRF-реализации пропуск хода выполняется автоматически, в случае Axiom, придётся нажать на кнопку:

Должен сказать, это здорово сбивает с толку.

Для реализации пропуска хода после хода на «розетку», в позицию q5, не используемую в игре, помещается невидимая фигура lock. В самом начале common-move, выполняется проверка на наличие в этом поле вражеской фигуры. Если поле занято врагом — ход невозможен.

Теперь, пришло время научиться бросать «кости»:

{players
	{player}	White
	{player}	Black
	{player}	?Dice	{random}
players}

{turn-order
	{turn}	White
	{turn}	?Dice {of-type} clear-type
	{turn}	?Dice
	{turn}	?Dice
	{turn}	?Dice
	{turn}	Black
	{turn}	?Dice {of-type} clear-type
	{turn}	?Dice
	{turn}	?Dice
	{turn}	?Dice
turn-order}

: drop-dices ( -- )
	q2 here = q3 here = OR q4 here = OR empty? AND IF
		drop
		add-move
	ENDIF
;

: count-dices ( -- n )
	q2 piece-at piece-value
	q3 piece-at piece-value +
	q4 piece-at piece-value +
	DUP 0= IF
		DROP
		4
	ENDIF
;

: clear-dices ( -- )
	q1 here = verify
	q2 not-empty-at? q3 not-empty-at? q4 not-empty-at?
	AND AND IF
		drop
		q2 capture-at
		q3 capture-at
		q4 capture-at
		add-move
	ENDIF
;

: i-move ( -- ) ['] Anext count-dices common-move ;
: p-move ( -- ) ['] Cnext count-dices common-move ;

{moves p-moves
	{move} p-move {move-type} normal-type
	{move} pass-move {move-type} pass-type
moves}

{moves drops
	{move} drop-dices {move-type} normal-type
	{move} pass-move {move-type} pass-type
moves}

{moves clears
	{move} clear-dices {move-type} clear-type
moves}

{pieces
	{piece}		lock	{moves} clears
	{piece}		init	{moves} i-moves
	{piece}		prom	{moves} p-moves
	{piece}		wdice	{drops} drops 1 {value}
	{piece}		bdice	{drops} drops 0 {value}
pieces}

Бросок «костей» (drop-dices) выполняется элементарно. Просто проверяем, что целевое поле предназначено для броска костей, ставим фигуру командой drop и завершаем ход командой add-move. Несколько сложнее выполняется очистка (clear-dices). В ZoG отсутствует возможность сформировать ход, заключающийся лишь в удалении фигуры с доски. Ход очистки мы связываем со сбросом невидимой фигуры на неиспользуемое в игре поле q1. Удаление с доски «костей» является побочным эффектом этого хода. Осталось подсчитать выпавшие очки (count-dices) и передать это значение в common-move.

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

{board
	5 17 		{grid}
	{variable}	WhitePieces
	{variable}	BlackPieces
board}

: WhitePieces++ WhitePieces ++ ;
: BlackPieces++ BlackPieces ++ ;

: common-move ( 'dir n -- )
	q5 enemy-at? NOT IF
		FALSE isPromouted !
		SWAP
		BEGIN
			current-player White
			= IF
				here p2
			ELSE
				here p4
			ENDIF
			= IF TRUE isPromouted ! ENDIF
			DUP EXECUTE verify SWAP
			1-  DUP
			0=  IF
				DROP
				TRUE
			ELSE
				SWAP
				FALSE
			ENDIF
		UNTIL
		empty? IF
			from
			here
			move
			here h3 = IF
				current-player White = IF
					COMPILE WhitePieces++
				ELSE
					COMPILE BlackPieces++
				ENDIF
				capture
			ENDIF
			isPromouted @ IF
				current-piece-type 1+ change-type
			ENDIF
			is-rosette? IF
				q1 piece-type-at q5 create-piece-type-at
			ELSE  
				q5 capture-at
			ENDIF
			add-move
		ENDIF
	ENDIF
;

: OnNewGame ( -- )
	RANDOMIZE
;

: OnIsGameOver ( -- gameResult )
	repetition-reset
	#UnknownScore
	current-player White = IF
		BlackPieces @
		7 - 0=  IF
			DROP
			#LossScore
		ENDIF
	ENDIF
	current-player Black = IF
		WhitePieces @
		7 - 0=  IF
			DROP
			#LossScore
		ENDIF
	ENDIF
;

Для получения полноценной игры осталось реализовать бой фигур и обработку специальных полей. Я не буду загромождать статью этими подробностями, поскольку, они не несут в себе ничего принципиально нового. Желающие могут посмотреть полную реализацию «Королевской игры Ур» на GitHub.

Основной инстинкт

Главной изюминкой ZoG является её универсальность. ZRF позволяет создать новую игру (или описать существующую), просто задекларировав её правила. Да, играет она заметно хуже чем специализированные программы, но подобная возможность быстрого создания прототипа почти любой игры дорогого стоит! Количество разработанных для ZoG приложений говорит само за себя.

Axiom также универсальна. Она снимает многие неприятные ограничения ZoG и позволяет описывать такие настольные игры, с которыми ZoG не справляется. Одна возможность использования полноценной арифметики, вместо манипуляций с булевскими флагами, выводит этот продукт на качественно более высокий уровень, но это не главное достоинство Axiom! Хорошо играет ZoG или плохо, но для нас её AI представляет собой чёрный ящик. Мы никак не можем повлиять на качество его игры! Axiom предоставляет нам возможность (но не требует этого) поучаствовать в разработке алгоритмов выбора оптимального хода.

Самая очевидная возможность вмешательства в работу AI Axiom — выбор весовой функции, при помощи которой оценивается каждая позиция. От нас требуется всего лишь переопределить OnEvaluate. Попробуем создать очень простую оценочную функцию, взяв за основу суммарное продвижение фишек от старта до финиша. Размещение фишки на стартовой позиции будем оценивать весом 0, а фишки, прошедшие полный путь, будем оценивать каким нибудь большим числом, например 100. Очевидно, что если какая-то фишка будет взята, значение оценки резко снизится (тем больше, чем дальше фишка успела продвинуться). Разумеется, для противника будем использовать ту же оценку, взятую с обратным знаком. Чем лучше позиция противника — тем наша хуже:

VARIABLE		whiteScored
VARIABLE		blackScored

: Score ( value piece-type player pos -- score )
	DUP not-empty-at? IF
		DUP player-at White = IF
			whiteScored --
		ELSE
			blackScored --
		ENDIF
		DUP ROT SWAP player-at =
		ROT ROT piece-type-at =
		AND NOT IF
			DROP 0
		ENDIF
	ELSE
		DROP DROP DROP DROP 0
	ENDIF
;

: OnEvaluate ( -- score )
	 7 	whiteScored !
	 7 	blackScored !

	 0	1 White i1 Score
	 0	1 White j1 Score +
	 0	1 White k1 Score +
	 0	1 White l1 Score +
	 0	1 White m1 Score +
	 0	1 White n1 Score +
	 0	1 White o1 Score +

	 0	1 Black i5 Score +
	 0	1 Black j5 Score +
	 0	1 Black k5 Score +
	 0	1 Black l5 Score +
	 0	1 Black m5 Score +
	 0	1 Black n5 Score +
	 0	1 Black o5 Score +

	 1	1 White l2 Score +
	-1	1 Black l4 Score +
	 2	1 White k2 Score +
	-2	1 Black k4 Score +
	 3	1 White j2 Score +
	-3	1 Black j4 Score +
	 4	1 White i2 Score +
	-4	1 Black i4 Score +
	 5	1 White i3 Score +
	-5	1 Black i3 Score +
	 6	1 White j3 Score +
	-6	1 Black j3 Score +
	 7	1 White k3 Score +
	-7	1 Black k3 Score +
	 8	1 White l3 Score +
	-8	1 Black l3 Score +
	 9	1 White m3 Score +
	-9	1 Black m3 Score +
	 10	1 White n3 Score +
	-10	1 Black n3 Score +
	 11	1 White o3 Score +
	-11	1 Black o3 Score +
	 12	1 White o2 Score +
	-12	1 Black o4 Score +
	 13	1 White p2 Score +
	-13	1 Black p4 Score +
	 14	2 White p3 Score +
	-14	2 Black p3 Score +
	 15	2 White p4 Score +
	-15	2 Black p2 Score +
	 16	2 White o4 Score +
	-16	2 Black o2 Score +
	 17	2 White o3 Score +
	-17	2 Black o3 Score +
	 18	2 White n3 Score +
	-18	2 Black n3 Score +
	 19	2 White m3 Score +
	-19	2 Black m3 Score +
	 20	2 White l3 Score +
	-20	2 Black l3 Score +
	 21	2 White k3 Score +
	-21	2 Black k3 Score +
	 22	2 White j3 Score +
	-22	2 Black j3 Score +
	 23	2 White i3 Score +
	-23	2 Black i3 Score +

	 1	1 White c2 Score +
	 1	1 White c3 Score +
	 1	1 White c4 Score +
	-1	1 Black d2 Score +
	-1	1 Black d3 Score +
	-1	1 Black d4 Score +

	 3	1 White a2 Score +
	 3	1 White a3 Score +
	 3	1 White a4 Score +
	-3	1 Black b2 Score +
	-3	1 Black b3 Score +
	-3	1 Black b4 Score +

	 7	1 White f2 Score +
	 7	1 White f3 Score +
	 7	1 White f4 Score +
	-7	1 Black f2 Score +
	-7	1 Black f3 Score +
	-7	1 Black f4 Score +

	 10	1 White g2 Score +
	 10	1 White g3 Score +
	 10	1 White g4 Score +
	-10	1 Black g2 Score +
	-10	1 Black g3 Score +
	-10	1 Black g4 Score +

	 11	1 White e2 Score +
	 11	1 White e3 Score +
	 11	1 White e4 Score +
	-11	1 Black e2 Score +
	-11	1 Black e3 Score +
	-11	1 Black e4 Score +

	 17	2 White e2 Score +
	 17	2 White e3 Score +
	 17	2 White e4 Score +
	-17	2 Black e2 Score +
	-17	2 Black e3 Score +
	-17	2 Black e4 Score +

	 18	2 White g2 Score +
	 18	2 White g3 Score +
	 18	2 White g4 Score +
	-18	2 Black g2 Score +
	-18	2 Black g3 Score +
	-18	2 Black g4 Score +

	 21	2 White f2 Score +
	 21	2 White f3 Score +
	 21	2 White f4 Score +
	-21	2 Black f2 Score +
	-21	2 Black f3 Score +
	-21	2 Black f4 Score +

	 whiteScored @ 100 * +
	 blackScored @ 100 * -

	 current-player Black = IF NEGATE ENDIF
;

Конечно, Axiom не оставляет нас один на один с Фортом при разработке оценочной функции. Нам предоставляются удобные примитивы для оценки как материальной, так и позиционной составляющих. Например, следующая оценочная функция (с точностью до коэффициентов), взятая из официального руководства, будет неплохо работать для большинства игр, наподобие Шашек и Шахмат:

: Mobility ( -- mobilityScore ) 
	move-count                               Number of moves available to us. 
	current-player TRUE 0 $GenerateMoves     Generate moves for opponent 
	move-count                               Number of moves available to opponent. 
	-                                        #friendlyMoves - #unfriendlyMoves 
	$DeallocateMoves                         Deallocate the opponent's move list 
;

: OnEvaluate ( -- score ) 
	Mobility 
	current-player material-balance 3 * + 
;

Здесь вызов move-count подсчитывает количество возможных ходов из текущей позиции, а material-balance вычисляет сумму весов, назначенных фигурам, при помощи атрибута {value} (в нашем коде, мы используем его для задания числовых значений «костям»).

Всё это прекрасно, но как быть в тех случаях, когда само использование минимаксного алгоритма является избыточным? В той игре, которую пытаемся реализовать мы, заглядывание более чем на один ход вперёд, скорее всего, приведёт лишь к напрасной трате вычислительных ресурсов. Как я уже писал, здесь нам нужен не «Искусственный интеллект», а скорее «Искусственный инстинкт»! Axiom предоставляет нам возможность вмешаться в алгоритм выбора хода на более глубоком уровне:

VARIABLE BestScore		 Keep track of the best score found so far by our search engine.
VARIABLE Nodes			 The number of possibilities explored by our search engine.
VARIABLE Eated
VARIABLE Rosettes

: enemy-value-at ( pos -- value )
	DUP
	empty-at?
	IF
		DROP 0
	ELSE
		0 SWAP
		player-at current-player <>
		IF DROP 1 ENDIF
	ENDIF
;

: friend-value-at ( pos -- value )
	DUP
	empty-at?
	IF
		DROP 0
	ELSE
		1 SWAP
		player-at current-player <>
		IF DROP 0 ENDIF
	ENDIF
;

: Make_enemy_p  ( pos -- ) <BUILDS , DOES> @ enemy-value-at ;
: Make_friend_p ( pos -- ) <BUILDS , DOES> @ enemy-value-at ;

i1 Make_enemy_p e0
j1 Make_enemy_p e1
k1 Make_enemy_p e2
l1 Make_enemy_p e3
m1 Make_enemy_p e4
n1 Make_enemy_p e5
o1 Make_enemy_p e6
i5 Make_enemy_p e7
j5 Make_enemy_p e8
k5 Make_enemy_p e9
l5 Make_enemy_p e10
m5 Make_enemy_p e11
n5 Make_enemy_p e12
o5 Make_enemy_p e13

i2 Make_friend_p r0
i4 Make_friend_p r1
l3 Make_friend_p r2
o2 Make_friend_p r3
o4 Make_friend_p r4

: CountEated ( -- count )
	e0 e1 + e2 + e3 + e4 + e5 + e6 + e7 + e8 + e9 + e10 + e11 + e12 + e13 +
;

: CountRosettes ( -- count )
	r0 r1 + r2 + r3 + r4 +
;

: Score ( -- score )
	Eated @ CountEated < IF 10 ELSE 0 ENDIF
	Rosettes @ CountRosettes < IF 5 ELSE 0 ENDIF +
;

: Custom-Engine ( -- )
	-1000 BestScore !				 Keep track of the best score.
	0 Nodes !					 Count the number of possibilities explored.
	CountEated Eated !
	CountRosettes Rosettes !
(
  Notes:
  1 - We do not need to invoke $GenerateMoves since they have already been generated for the
  current player { since ZoG has called DLL_GenerateMoves prior to calling DLL_Search}.

  2 - ZoG does not invoke the search engine if there are no moves, so we can safely assume.
  that at least one move exists.  Thus we can use BEGIN..UNTIL instead of BEGIN...WHILE..REPEAT
  for iterating moves.
)
	$FirstMove					 Obtain the address of the first move.
	BEGIN
		$CloneBoard				 Create a temporary copy of the current board.
		DUP $MoveString CurrentMove!		 Inform ZoG of the current move being examined.
		DUP .moveCFA EXECUTE			 Apply the move to the board by executing its code.
		Score					 Calculate the score for the new board.
		BestScore @ OVER <			 Have we found a better score?
		IF
			DUP BestScore !			 Save the improved score.
			Score!				 Inform ZoG of the improved score.
			DUP $MoveString BestMove!
		ELSE
			DROP 				 We didn't find a better move, drop the score.
		ENDIF
		$DeallocateBoard			 Done with the revised board.
		Nodes ++				 Count one more node explored.
		Nodes @ Nodes!				 Inform ZoG of the node count.
		$Yield					 Allow ZoG to dispatch Windows messages.
		$NextMove				 Advance to the next move.
		DUP NOT					 No more moves?
	UNTIL
	DROP
;

{players
	{player}	White	{search-engine} Custom-Engine
	{player}	Black	{search-engine} Custom-Engine
	{player}	?Dice	{random}
players}

Большая часть этого кода взята из документации. Как понятно из комментариев, мы перебираем все возможные ходы, и применяем к построенным временным позициям функцию оценки. В качестве оценочной функции, мы могли бы брать ту же функцию, которую написали для OnEvaluate, но это было бы не интересно. Я постарался сформулировать некую предельно агрессивную стратегию игры. Если есть возможность взять вражескую фигуру или встать на «розетку», этот ход считается предпочтительным, если такой возможности нет, выбирается первый попавшийся ход.

К слову сказать, предопределённые Axiom примитивные игровые стратегии {first} и {random} реализованы аналогичным образом. Вот как они описываются в axiom.4th:

: $RandomMoveEngine
	$FirstMove
	0
	$movesList @ CELLSIZE + @ 1-
	$RAND-WITHIN

	BEGIN
	DUP 0>
	WHILE
		SWAP @ SWAP
		$Yield
		1-
	REPEAT
	DROP

	( move ) $MoveString DUP CurrentMove! BestMove!
	1 Nodes! 0 Score! 0 Depth!
;

: {random}
	['] $RandomMoveEngine $CompileEngine
;

: $FirstMoveEngine
	$FirstMove $MoveString DUP CurrentMove! BestMove!
	$Yield
;

: {first}
	['] $FirstMoveEngine $CompileEngine
;

Как я уже говорил, открытый (пусть даже частично) исходный код — это прекрасно!

Ложь, наглая ложь и статистика

Хорошо, мы создали новую игру и можем в неё поиграть, используя ZoG. Мы реализовали несколько вариантов игры с различными алгоритмами выбора хода, но как нам определить, какой из них лучше? Конечно, можно собрать десяток «экспертов» и попросить каждого из них сыграть по сотне раз с каждым из вариантов. Как говорил один мой знакомый, «это может растянуться на годы». Есть способ лучше!

В составе Axiom предоставляется утилита AutoPlay, позволяющая автоматизировать процесс тестирования. Первое, что мы должны сделать, следуя по пути автоматизации — это создание вариантов игры:

(variant (title "Ur [random]"))
(variant (title "Ur [simple evaluation]"))
(variant (title "Ur [aggressive]"))

Дописав эти строки в конец ZRF-файла, заново запустим ZRF Converter, чтобы получить заготовки 4th-файлов вариантов игры. В эти файлы необходимо внести изменения, влияющие на стратегию, используемую программой. Вот так, например, выглядит один из простейших вариантов:

LOAD Ur.4th ( Load the base Ur game )

{players
	{player}	White   {random}
	{player}	Black   {random}
	{player}	?Dice	{random}
players}

Как легко видеть, мы можем переопределять отдельные секции описания, вынося весь совместно используемый код в подгружаемые файлы скриптов.

После того как варианты созданы, мы можем запустить игру в режиме игры одного варианта против другого. Это главное достоинство AutoPlay! Не требуется создавать варианты, в которых игроки играют, используя различные стратегии. Достаточно дать следующую команду:

AutoPlay Ur-[random] Ur-[random] 100

Всё максимально просто. Задаём варианты для первого и второго игроков (в текущей реализации AutoPlay большее количество игроков не поддерживается) и количество партий. Дальше программа работает сама. И делает она это гораздо быстрее, чем если бы эти партии игрались с использованием ZoG! На выходе формируется большой текстовый файл, содержащий описание всех сыгранных партий в ZSG-нотации. В самом конце, выводится итоговая статистика, по которой можно видеть, что при условии того, что ходы выбираются случайно, игрок делающий первый ход имеет небольшое преимущество (даже с учетом того, что он всегда ходит на «единичку»):

Final results:
Player 1 "Ur-[random]", wins = 52.
Player 2 "Ur-[random]", wins = 48.
Draws = 0
100 game(s) played

Наличие полного ZSG-описания позволяет нам, после небольшой обработки, загрузить любую из партий в ZoG и рассмотреть её пошагово. Кстати, именно таким образом были обнаружены и исправлены эти ошибки в реализации (не знаю чем я думал когда решил просто дропнуть результат перехода вместо того, чтобы его проверить).

Другим достоинством наличия полного ZSG-описания, является то, что мы, обработав данные, можем собрать любую необходимую статистику, если нас не устроит простое соотношение количества выигранных/проигранных партий. Следующий ниже скрипт выводит данные о продолжительности партий, итоговом счёте на конец партии, количестве пропусков хода и количестве фишек «срубленных» каждым из игроков:

#!/usr/bin/perl -w

my @S = (0, 0, 0, 0, 0, 0);
my $ix = 0;
my $T;

while (<>) {
    if (/results/) {
        my $d = $S[0] - $S[1];
        print "$T, $d, $S[3], $S[2], $S[4], $S[5]n";
        @S = (0, 0, 0, 0, 0, 0);
        $ix = 0;
    } else {
        if (/^(d+).s+[^?].*$/) {
             $T = $1;
             if (/x h3/) {
                 $S[$ix]++;
             }
             if (/Pass|^(d+).s+xs+q5s*$/) {
                 $S[$ix + 2]++;
             }
             if (/Black init [ijklmno]5/) {
                 $S[4]++;
             }
             if (/White init [ijklmno]1/) {
                 $S[5]++;
             }
             $ix++;
             if ($ix > 1) {
                 $ix = 0;
             }
        }
    }
}

Теперь у нас есть всё необходимое для сравнения качества игры разработанных нами вариантов. Будем рассматривать три варианта:

• Со случайным выбором хода (random)
• С простой оценочной функцией (simple)
• С «агрессивным» алгоритмом выбора хода (agressive)

Final results:
Player 1 "Ur-[random]", wins = 52.
Player 2 "Ur-[random]", wins = 48.
Draws = 0
100 game(s) played

Final results:
Player 1 "Ur-[random]", wins = 50.
Player 2 "Ur-[simple-evaluation]", wins = 50.
Draws = 0
100 game(s) played

Final results:
Player 1 "Ur-[simple-evaluation]", wins = 87.
Player 2 "Ur-[random]", wins = 13.
Draws = 0
100 game(s) played

Final results:
Player 1 "Ur-[random]", wins = 25.
Player 2 "Ur-[aggressive]", wins = 75.
Draws = 0
100 game(s) played

Final results:
Player 1 "Ur-[aggressive]", wins = 90.
Player 2 "Ur-[random]", wins = 10.
Draws = 0
100 game(s) played

Final results:
Player 1 "Ur-[simple-evaluation]", wins = 73.
Player 2 "Ur-[aggressive]", wins = 27.
Draws = 0
100 game(s) played

Final results:
Player 1 "Ur-[aggressive]", wins = 64.
Player 2 "Ur-[simple-evaluation]", wins = 36.
Draws = 0
100 game(s) played

Кстати, обратите внимание на следующую замечательную строку:

Draws = 0

Дело в том, что Axiom предлагает способ борьбы с «3-Time Repetition Draw!». Я тщательно проштудировал соответствующий раздел документации и предпринял все необходимые действия. Проблема в том, что в ZoG эта ситуация всё равно возникает. Обычно это происходит когда длинные цепочки (3-4 фишки подряд) белых и чёрных фишек блокируют друг друга. В «Королевском Ур», благодаря безопасным полям, способ разойтись для них всегда есть, но ZoG (даже под управлением Axiom) не дожидается пока фишки разойдутся! А вот AutoPlay, доигрывает все партии до конца. В принципе, как я уже говорил, его можно запускать даже без установленного и купленного ZoG, просто интерфейса графического не будет.

… и тысяча слонов!

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

Здесь есть и поддержка контроля времени, и поддержка командной игры, которых так не хватало в ZoG. Axiom предоставляет специальную структуру данных (Ring Buffer) для разработки игр на «соединение» и «захват территории». Несколько расстраивает тот факт, что не поддерживаются атрибуты фигур (с использованием которых в ZoG, например, реализована шахматная рокировка), но Axiom предоставляет достаточно возможностей, чтобы обойти это досадное ограничение.

Отдельных и очень тёплых слов заслуживает качество документации и примеров. Очень сложный материал преподнесён так, что его усвоение не связано с какими либо трудностями. И даже если этого материала окажется недостаточно, на сайте ZoG имеется более 60 интереснейших приложений, разработанных с использованием Axiom, доступных для анализа и изучения.

Автор: GlukKazan

Источник