Больше чем Го

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

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


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

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

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


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

a270220215884ea9aadbd5873819c1f8.PNG

К слову сказать
Использование каких либо «защёлок», на позиции выше, совершенно излишне! Чёрные уже обречены, «доедать» их нет необходимости. Но почему в 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 соседей:

72785db068954845af18145fffe78e3f.png


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

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

b9276e71990744548dad97f64882363d.PNG

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

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

aa52d5016b3349de95e0721e0ae43d79.PNG

На схеме показаны лишь функции, ведущие строго на «север» (в каком-то смысле). Часть из них я уже использовал ранее. Направление '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 припасла другие сюрпризы.

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


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

8d660aebfb1f4e01a2010aea8015faf1.PNG

В Го такое соединение считается принципиально не разрезаемым, независимо от возможных ошибок построившего его игрока. Камни, стоящие рядом, живут и умирают вместе. Их невозможно разделить, но только не в 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 есть зомби!

908dead0a36141dab90a6cc573e3833d.PNG

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

57ef4d58b2014921bc603ec4cd3b49ae.png

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

6295269949904ec7803604fcf41fa4c7.png

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

52348a38fe9b4a9ab554fb485a220be9.PNG

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

Действительно сложно
Как я уже писал выше, добавление игроком камня и удаление «мёртвых» групп мне пришлось разделить на два следующих друг за другом хода (иначе всё получалось совсем сложно). Помимо прочих неудобств, это означает, что я не могу запретить игроку сделать ход, просто на основании того, что он «самоубийственен». В принципе, это не очень большая беда. Разрешим сделать ход и пусть добавленный камень просто умрёт (возможно с группой других камней своего цвета), но это только часть проблемы! Помните, я писал что-то вроде такого кода?
: 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
;



В целом, немножко замороченно, но это работает.


Без Ко нет Го


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

aadfb3956bbf40d2a163f1915af08773.PNG

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

29e543f6689146af8bde5ca651b19220.PNG

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

Из жизни невидимок
Увы, мне не реализовать обнаружение ни позиционного ни ситуационного суперко. Для этого необходима информация о предыдущих позициях (хотя бы хэши), а у меня её нет! К счастью, все эти «циклические ко», «вечные жизни» и прочие экзотические позиции не делают погоды. В реальной Ко-борьбе, практически всегда, фигурирует простое Ко. Его и будем ловить.
Чтобы запретить ход в ''пустой'' пункт, надо сделать его не пустым
: 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 безусловно запрещены. Это означает, что игрок не имеет права сделать ход лишающий группу (возможно состоящую лишь из одного, только что добавленного камня) последнего дамэ, при условии, что не берёт этим ходом камни противника.

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

d471fb2686124d169a84dbd195d2e110.PNG

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

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

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

c8d0d908cabd41e7b044c8c4a50c4e71.PNG

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

8a64414a2ad843d2996f77b6628f9f34.PNG

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

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

© Habrahabr.ru