Больше чем Го

от автора

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

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

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

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

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

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

К слову сказать

Использование каких либо «защёлок», на позиции выше, совершенно излишне! Чёрные уже обречены, «доедать» их нет необходимости. Но почему в MarGo используются такие маленькие доски? Главная причина заключается в том, что игра идёт не на плоскости, а в объёме. Игроки строят пирамиды и вряд ли у кого-то хватит терпения заниматься этим на доске 19×19. Стандартная для MarGo доска 9×9, в Го используется, в основном, для обучения новичков!

Для меня это стало большим облегчением, поскольку уже при использовании доски 9×9, я столкнулся с проблемами нехватки памяти. Мне пришлось оптимизировать её использование, убрав из массива лишние строки. Этот момент достаточно очевиден — строя пирамиду, мы никогда не сможем разместить фигуры на большей части полей трёхмерной доски.

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

Как это работает?

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

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

{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		( Завершаем генерацию хода ) ; 

Этот код решает сразу две задачи:

  1. Удаление всех вражеских групп, убитых последним ходом
  2. Самоубийство дружественной группы, если ход был самоубийственным и никого из врагов убить не удалось

Больше подробностей

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 ; 

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

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

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

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

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

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

Вторжение в трёхмерность

Я уже писал о том, что для создания эффекта трёхмерности, мне пришлось разделить каждую фигуру на 4 тайла. Это работает, но загвоздка заключается в том, что фигуры-тайлы приходится располагать на «трёхмерной» доске весьма причудливым образом. Избежать этого никак нельзя. Все тайлы, видимые «сверху», должны находиться в одной плоскости. У этой схемы размещения фигур есть и свои дополнительные плюсы, но навигация в ней уж слишком заковыриста. Для начала, мне понадобилась мандала для медитаций:

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 

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

На схеме показаны лишь функции, ведущие строго на «север» (в каком-то смысле). Часть из них я уже использовал ранее. Направление ‘n‘, например, мне пришлось ввести когда я выкидывал из массива «доски» лишние строки, с целью оптимизации использования памяти. Главная часть «ракетной науки» — функция, позволяющая перемещаться в плоскости, параллельной плоскости доски:

Даже не буду пытаться это комментировать

: 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, south-internal и т.д.:

: 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 ; 

Вся магия скрыта в check-bridge?. Для определения «моста» над головой, «смотрим» наверх, в поисках чужого тайла. То же делаем и на соседнем тайле. Если оба тайла «покрыты» фигурами чужого цвета (разными), «перерубаем» соответствующее направление, заменяя возвращаемое им значение ложным.

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

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

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

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

Разделим код удаления ''мёртвых'' групп на две части

{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} 

С более высоким (normal) приоритетом будет выполняться код удаления мёртвых групп противника (clear-e), а с низким (low) — удаления своих мёртвых групп (уровень high, вне списка приоритетов, резервируем для обычного добавления камней на доску). Теперь всё работает как надо. Сначала генератор ходов пытается выполнить более приоритетный clear-e, в конце которого мы проверяем, не попал ли добавленный камень в окружение (запрещая ход, если это произошло). Если приоритетный ход провалил какую-то из проверок, генератор ходов сам откатывает все изменения, и отрабатывает низкоприоритетный clear-f. Этот код всегда выполняется успешно. Иногда побочным эффектом его выполнения является удаление «самоубитых» групп.

Код очистки тоже усложнился

: 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 ; 

Мы можем помещать на доску невидимые тайлы, чтобы сделать невозможным ход в выбранную позицию. При выполнении хода в любой разрешённый пункт, будем просто удалять эти помехи. Здесь нам на руку играет одно из важных свойств MarGo. Любая Ко-борьба всегда будет происходить в плоскости основания доски! Чтобы добавленные «пустые» тайлы не мешали определению статуса групп, изменим функцию определения пустоты узла:

: 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 добавляет к территории те пункты, которые игрок может заполнить «потенциально». Например, если у игрока есть квадрат 4×4, состоящий из 16 фигур своего цвета, то на его «площадках» он сможет разместить 4 камня (в свою очередь, образующих новую площадку, для ещё одного камня). Помимо этого, если начальный квадрат 4×4 не заполнен, внутренние его пункты также добавляются к территории. Всё это звучит логично, но пока я боюсь даже браться за такую задачку на ForthScript.

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

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

ссылка на оригинал статьи http://habrahabr.ru/post/274043/


Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *