Больше чем Го

Бросая в воду камешки, смотри на круги, ими образуемые;
иначе такое бросание будет пустою забавою.

                      Козьма Прутков "Плоды раздумья" 
 

Эта игра — самый настоящий долгострой. Я начал работать над ней ещё в июне! Нельзя сказать, чтобы я каждый день надрывался, но крови она мне попортила немало. На сегодняшний день, это мой самый сложный проект в Axiom. По объёму (весьма нетривиального) кода, MarGo сопоставима, разве что, с Ритмомахией.

Что особенного в этой игре? Стоило ли из за неё так мучиться? Я расскажу, а вы сами судите.

Поверхностное сходство

Попытки «усовершенствовать» Го предпринимались неоднократно, но они редко бывали удачными. MarGo, на мой взгляд, именно такая редкость! Главное, что подкупает в этой игре, так это тот факт, что она является надмножеством Го. Я уже писал о том, как казалось бы простые правила Го приводят к неожиданно сложным тактическим построениям. Не стану повторяться, скажу лишь, что всё что я писал о Го, справедливо и для MarGo тоже (до тех пор, пока мы не выходим за пределы плоскости). Вот так, например, выглядит знаменитая "защёлка" — простейшая жертва одного камня, с целью получения трёх:

При определении статуса групп, значение имеют лишь пустые пункты, расположенные в плоскости доски. Каждый камень «живой» группы должен быть связан (непосредственно или через другие камни) хотя бы с одним из таких пунктов (называемых "дамэ"). Как только последнее из дамэ будет закрыто, группа становится мёртвой и снимается с доски.

{players
	{player}	W
	{player}	B
	{player}	?C	{random}
players}

{turn-order
	{turn}	W	{of-type} normal
	{turn}	?C	{for-player} W	{of-type} clean
	{turn}	B	{of-type} normal
	{turn}	?C	{for-player} B	{of-type} clean
turn-order}

: drop-m ( -- )
	here a1 = verify	( Это целевое поле? )
	drop			( Ставим фигуру )
	['] my-enemy? 		( Обрабатываем фигуры противника )
	init-alive 		( Добавляем в массив безусловно живые фигуры )
	proceed-alive 		( и всех их соседей )
	capture-all		( Удаляем все фигуры не оказавшиеся в построенном массиве )
	captured-tiles @ 0= IF  ( Если не удалено ни одной фигуры )
		['] my-friend? 	( Повторяем те же действия для дружественных фигур )
		init-alive 
		proceed-alive 
		capture-all
	ENDIF
	add-move		( Завершаем генерацию хода )
;

TOTAL []	alive[]				( Массив живых камней )
VARIABLE	alive-count			( и его размер )

: not-alive? ( -- ? )				( Поиск в массиве )
	TRUE
	0 BEGIN
		DUP alive-count @ < IF
			DUP alive[] @ here = IF
				SWAP DROP FALSE SWAP
				TRUE
			ELSE
				1+
				FALSE
			ENDIF
		ELSE
			TRUE
		ENDIF
	UNTIL DROP
;

: add-alive ( -- )				( Добавление в массив )
	not-alive? alive-count @ TOTAL < AND IF	( не забываем проверять повторы! )
		here alive-count @ alive[] !
		alive-count ++
	ENDIF
;

: check-alive ( 'op 'dir -- )			( Проверка дружественности соседнего камня )
	EXECUTE IF
		EXECUTE IF
			add-alive
		ENDIF
	ELSE
		DROP
	ENDIF
;

: init-alive ( 'op -- 'op )			( Инициализация массива )
	0 alive-count !
	0 BEGIN					( Все искомые камни расположены в плоскости доски! )
		DUP empty-at? IF
			DUP to OVER ['] n check-alive
			DUP to OVER ['] s check-alive
			DUP to OVER ['] w check-alive
			DUP to OVER ['] e check-alive 
		ENDIF
		1+ DUP PLANE >=
	UNTIL DROP
;

: proceed-alive ( 'op -- 'op )			( Добавление соседей "живых" камней )
	0 BEGIN					( и их соседей тоже )
		DUP alive-count @ < IF
			DUP alive[] @ to OVER ['] n check-alive
			DUP alive[] @ to OVER ['] s check-alive
			DUP alive[] @ to OVER ['] w check-alive
			DUP alive[] @ to OVER ['] e check-alive
			1+ FALSE
		ELSE
			TRUE
		ENDIF
	UNTIL DROP
;

Небольшой размер доски приводит к высокой конкуренции за дамэ. Те из вас, кто играет в Го, должны знать, что схватки на малой доске (9x9) могут быть гораздо более ожесточёнными, чем игра на стандартной доске (19x19). С самого первого хода, игроки входят в плотное соприкосновение и вынуждены непрерывно решать задачи «жизни и смерти». Такова игра в MarGo, но если бы этим дело и ограничивалось, я не стал бы о ней рассказывать.

Основное отличие

Название игры состоит из двух слов: «marbles» (шарики) и «Go». Вместе получается — «игра в Го шариками». В чём отличие от традиционной игры? В её трёхмерности! Попытки игры в Го на трёхмерных досках предпринимались неоднократно (я писал о программе, позволяющей играть на произвольных графах), но, в большинстве таких случаев, серьёзно страдал игровой баланс. Исключением, пожалуй, является лишь доска, имитирующая кристаллическую решётку алмаза. Она во многом подобна классической плоской доске. Каждый узел имеет от 2 до 4 соседей:

Подход MarGo совершенно отличен. Шарик не может просто так «висеть в воздухе». Чтобы «подняться над доской» он должен опираться на четыре других шарика (свои или противника). Разумеется, для того, чтобы этот шарик оставался живым, он должен контактировать с группой, имеющей выход хотя бы на одно дамэ. К ортогональным соединениям, лежащим в плоскости доски, добавляются вертикальные направления, соединяющие шарики, находящиеся в основании пирамиды с её вершиной.

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

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

4       A A
3     8 8|9 9
2   5 5|6 6|7 7
1 1 1|2 2|3 3|4 4
+ A B C D E F G H
1 1|5|8|A A|9|7|4
2   1|2 2|3 3|4
3     5|6 6|7
4       8|9

: common-internal ( 'dir -- ? )
	here is-plane? IF
		get-height SWAP EXECUTE IF
			get-height -
			DUP 0= IF
				DROP TRUE
			ELSE
				0> IF
					FALSE
				ELSE
					BEGIN d NOT empty? OR UNTIL
					empty? IF u verify ENDIF
					TRUE
				ENDIF			
			ENDIF
		ELSE
			DROP FALSE
		ENDIF
	ELSE
		here OVER EXECUTE NOT empty? OR IF
			to BEGIN u NOT UNTIL
			EXECUTE
		ELSE
			2DROP TRUE
		ENDIF
	ENDIF
;

: north-internal ( -- ? ) ['] n common-internal ;
: south-internal ( -- ? ) ['] s common-internal ;
: west-internal  ( -- ? ) ['] w common-internal ;
: east-internal  ( -- ? ) ['] e common-internal ;

: wrap-direction ( 'dir -- ? )
	here 			( Запоминаем положение "маркера" )
	SWAP EXECUTE IF		( и вызываем базовую функцию перемещения )
		DROP TRUE	( если всё прошло успешно, отбрасываем сохранённое значение )
	ELSE
		to FALSE	( в противном случае, возвращаем "маркер" в исходную позицию )
	ENDIF
;

: north ( -- ? ) ['] north-internal wrap-direction ;
: south ( -- ? ) ['] south-internal wrap-direction ;
: west  ( -- ? ) ['] west-internal  wrap-direction ;
: east  ( -- ? ) ['] east-internal  wrap-direction ;

: up-internal ( -- ? ) 
	here is-plane? IF
		FALSE
	ELSE
		d NOT empty? OR IF
			BEGIN u NOT UNTIL
		ENDIF
		TRUE
	ENDIF
;

: down-internal ( -- ? ) 
	here is-plane? IF
		d NOT empty? OR IF
			FALSE
		ELSE
			BEGIN d NOT empty? OR UNTIL
			empty? IF
				u verify
			ENDIF
			TRUE
		ENDIF
	ELSE
		u verify
		here is-plane? NOT
	ENDIF
;

: up 	( -- ? ) ['] up-internal	wrap-direction ;
: down	( -- ? ) ['] down-internal	wrap-direction ;

Зомби — интересная новая сущность, порождённая простыми и логичными правилами игры. Интересная, но не единственная! MarGo припасла другие сюрпризы.

Мосты и ущелья

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

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

TRUE	CONSTANT	BRIDGE-CUTTING

: is-covered? ( -- ? )
	player up empty? NOT AND IF
		player <>
	ELSE
		DROP FALSE
	ENDIF
;

: check-bridge? ( 'dir piece-type -- ? )
	piece-type SWAP equal-types? IF
		here
		is-covered? IF
			SWAP OVER to
			EXECUTE IF
				is-covered?
				SWAP to
			ELSE
				to FALSE
			ENDIF
		ELSE
			to DROP FALSE
		ENDIF
	ELSE
		DROP FALSE
	ENDIF
;

: common-cutting ( 'dir 'dir piece-type 'dir piece-type -- ? )
	BRIDGE-CUTTING IF
		check-bridge? IF
			2DROP TRUE
		ELSE
			check-bridge?
		ENDIF
	ELSE
		2DROP 2DROP
		FALSE
	ENDIF
	IF DROP FALSE ELSE EXECUTE ENDIF
;

: north-cutting ( -- ) ['] north ['] east  nw-piece ['] west  ne-piece common-cutting ;
: south-cutting ( -- ) ['] south ['] east  sw-piece ['] west  se-piece common-cutting ;
: west-cutting  ( -- ) ['] west  ['] south nw-piece ['] north sw-piece common-cutting ;
: east-cutting  ( -- ) ['] east  ['] south ne-piece ['] north se-piece common-cutting ;

Думаете, что на этом сюрпризы кончились? Как бы не так!

Самый сложный кейс

Самоубийственные ходы запрещены (и по большей части бесполезны). Игрок не может поместить свой камень «в окружение», если при этом не берёт ни одного камня противника. В Го, с этим всё просто. Если мы берём какую-то группу камней, она должна контактировать с только что добавленным камнем и её «убийство» откроет дамэ, необходимые нам для выживания. Но в MarGo есть зомби!

Даже взяв камень на вершине пирамиды, белый камень всё равно окажется «в окружении», создав тем самым недопустимую позицию! Два чёрных камня составляют «виртуальную группу», защищённую «зомби» лежащим в её основании. Забавно, что это защита очень эфемерна. Если белому, по какой-то причине, удастся взять любой из соседствующих с ним четырёх камней, защита «виртуальной группы» перестанет действовать. Это не просто искусственное построение. Виртуальные группы — важная тактическая составляющая игры MarGo! Что вы скажете, например, о статусе этой позиции?

Выглядит как полностью окружённая группа (с одним «глазом»), которую начал поедать белый. В принципе, так оно и есть, но «доесть» группу чёрных не так просто. Белый не может просто сходить в левый нижний угол. Поскольку два белых камня окружают лишь «зомби», такой ход будет считаться самоубийственным. Но и чёрным не стоит спешить с поеданием вторгшегося белого камня:

Чёрный добавляет на доску камень, не являющийся «зомби», разрушая тем самым защиту «виртуальной группы». Белый получает право сходить в тот же пункт, где находился его только что съеденный камень, забирая пять чёрных камней. Получается, что лучшее решение для чёрных — не делать ничего? Конечно же, это не так. Белый имеет ещё одну возможность для убийства группы.

Если чёрный проигнорирует эту угрозу — его группа обречена! Соединив свои группы, белый игрок получит возможность безопасно занять последнее дамэ. Защита от такого вторжения очевидна. Лучший ход противника — это и твой лучший ход!

: drop-m ( -- )
	here a1 = verify
	drop
	['] my-enemy? init-alive proceed-alive check-zombies capture-all
	captured-tiles @ 0= IF
		['] my-friend? init-alive proceed-alive check-zombies capture-all
		captured-tiles @ NEGATE
		update-variables
	ELSE
		captured-tiles @
		update-variables
	ENDIF
	add-move
;

{players
	{player}	W
	{player}	B
	{player}	?C	{random}
players}

{turn-order
	{turn}	W	{of-type} high-priority
	{turn}	?C	{for-player} W
	{turn}	B	{of-type} high-priority
	{turn}	?C	{for-player} B
turn-order}

{move-priorities
	{move-priority} normal-priority
	{move-priority} low-priority
move-priorities}

{moves w-drop
	{move} drop-w	{move-type} high-priority
	{move} drop-nw	{move-type} high-priority
moves}

{moves n-drop
	{move} drop-n	{move-type} high-priority
	{move} drop-ne	{move-type} high-priority
moves}

{moves e-drop
	{move} drop-e	{move-type} high-priority
	{move} drop-se	{move-type} high-priority
moves}

{moves s-drop
	{move} drop-s	{move-type} high-priority
	{move} drop-sw	{move-type} high-priority
moves}

{moves m-drop
	{move} clear-e	{move-type} normal-priority
	{move} clear-f	{move-type} low-priority
moves}

{pieces
	{piece}		M	{drops} m-drop
	{piece}		tw	{drops} w-drop
	{piece}		zw
	{piece}		ww
	{piece}		bw
	{piece}		tn	{drops} n-drop
	{piece}		zn
	{piece}		wn
	{piece}		bn
	{piece}		te	{drops} e-drop
	{piece}		ze
	{piece}		we
	{piece}		be
	{piece}		ts	{drops} s-drop
	{piece}		zs
	{piece}		ws
	{piece}		bs
pieces}

: clear-e ( -- )
	0 captured-count !
	here a1 = verify
	drop
	['] my-enemy? init-alive proceed-alive check-zombies capture-all
	captured-tiles @ 0> verify
	captured-tiles @ update-variables
	['] my-friend? init-alive proceed-alive check-zombies check-not-captured
	add-move
;

: clear-f ( -- )
	0 captured-count !
	here a1 = verify
	drop
	['] my-friend? init-alive proceed-alive check-zombies capture-all
	captured-tiles @ 0> IF
		captured-tiles @ NEGATE
		update-variables
	ELSE
		DROP
	ENDIF
	add-move
;

Без Ко нет Го

Ну ладно, есть ещё один непростой кейс, благополучно унаследованный от более традиционной версии игры. Поскольку, как я уже говорил, в плоскости доски все правила Го остаются в силе, вполне можно проделать следующий фокус:

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

Чёрный не может съесть белый камень немедленно и вынужден ходить в другой части доски. Следующим ходом, белый может соединиться.

: drop-marks ( -- )
	0 BEGIN
		DUP captured-count @ < IF
			mark OVER captured[] @ create-piece-type-at
			1+ FALSE
		ELSE
			TRUE
		ENDIF
	UNTIL DROP
;

: clear-marks ( -- )
	0 BEGIN
		DUP empty-at? NOT IF
			DUP piece-type-at mark = IF
				DUP capture-at
			ENDIF
		ENDIF
		1+ DUP PLANE >=
	UNTIL DROP
;

: my-empty-at? ( pos -- ? )
	DUP curr-pos !
-	empty-at? IF
+	DUP empty-at? SWAP piece-type-at mark = OR IF
		TRUE
	ELSE
	...
	ENDIF
;

Что за кадром?

Разумеется, не всё пошло гладко. Некоторые правила реализовать я просто не смог. Самоубийственные ходы, например, в MarGo безусловно запрещены. Это означает, что игрок не имеет права сделать ход, лишающий группу (возможно состоящую лишь из одного, только что добавленного камня) последнего дамэ, при условии, что не берёт этим ходом камни противника.

Я был вынужден разделить ходы, выполняющие добавление камня и удаление взятых камней, что лишило меня всякой возможности запрета «самоубийственных» ходов. Это может показаться мелочью. В конце концов, хотя «самоубийственные» ходы и запрещены в большинстве вариантов правил Го, правила Инга их допускают. На то имеется веская причина. Существуют (очень редкие) позиции, в которых убийство собственной группы позволяет игроку спастись в совершенно безнадёжной ситуации.

Секи не принесёт очков, но по сравнению с полной потерей группы, это серьёзное подспорье, ведь противник не получит очков тоже! К сожалению, одно тянет за собой другое. В MarGo (в отличии от Го) игрокам запрещается пропускать ход. Но, попав в безвыходную ситуацию, игрок, практически всегда, будет иметь возможность сделать ход, приводящий к самоубийству только что добавленного камня. Что это как не пропуск хода? И это то, что я также не могу запретить.

В любом случае, эти отличия не столь значимы, чтобы о них стоило переживать. С AI дело обстоит гораздо хуже. В текущей реализации его попросту нет! Приложение можно использовать как «интеллектуальную» доску, для игры двух человек или для разбора этюдов, но поиграть с ней не получится. Дело даже не в самой сложности AI для Го (разработчикам ZoG пришлось использовать DLL-engine и играет он не слишком хорошо). Прежде чем думать об AI, необходимо реализовать, по крайней мере, логику подсчёта очков.

Целью игры Го является не «поедание» камней противника (хотя они тоже идут в зачёт), а захват территории (о том, чем он отличается от китайского, я писал здесь). Территорией игрока считаются все пустые пункты, добраться от которых можно лишь до фигур своего цвета. MarGo расширяет и это понятие. К традиционным пунктам территории, расположенным в плоскости доски, добавляются пункты на «площадках», состоящих из четырёх камней своего цвета. Если подумать, это тоже территория. На этих пунктах можно разместить камни и «добраться» от них можно лишь до своих камней. Подчеркну, что дамэ такие пункты не являются! Жизнь группы обеспечивают лишь свободные пункты, расположенные в плоскости доски.

Подсчёт территории, определённой таким образом, дело сложное, но вполне решаемое. К сожалению, этим дело не ограничивается. MarGo добавляет к территории те пункты, которые игрок может заполнить «потенциально». Например, если у игрока есть квадрат 4x4, состоящий из 16 фигур своего цвета, то на его «площадках» он сможет разместить 4 камня (в свою очередь, образующих новую площадку, для ещё одного камня). Помимо этого, если начальный квадрат 4x4 не заполнен, внутренние его пункты также добавляются к территории. Всё это звучит логично, но пока я боюсь даже браться за такую задачку на ForthScript.

Подсчёт захваченных камней — дело тоже хитрое. Кроме камней, захваченных в процессе игры, к ним, понятное дело, добавляются «зомби» (ладно, их можно сосчитать), а также камни, составляющие группы, оказавшиеся, к концу игры, в безнадёжной ситуации (а вот тут — всё плохо). Обычно, перед подсчётом очков, игрокам предоставляется возможность ручного удаления «мёртвых» групп, но в ZoG это та ещё задачка!

Даже если мне удастся решить все эти проблемы, то это ещё не означает, что я смогу реализовать хоть сколь нибудь сильный AI для этой игры. Хотя попробовать, наверное, стоит.

Автор: GlukKazan

Источник