Программирование «для души»

Полно, голубь, не греши!
Убери свои гроши.
Я ведь это не для денег.
Я ведь это для души.

Linus Torvalds

Не секрет, что люди получают удовольствие по-разному. Одним нравится смотреть телевизор, другие собирают квадрокоптеры. Я хочу поделиться своим рецептом. Вряд ли он будет полезен всем, но возможно кого-то заинтересует. Мне нравится писать программы (и думаю, что это не редкость, даже среди профессиональных программистов), но мне не очень нравится, когда этот процесс превращается в унылую рутину.

Чтобы быть интересным, программирование должно представлять собой, своего рода «зарядку для ума». Хорошим примером такого (полезного) развлечения является, известный многим ресурс ^[2], посвященный совершенствованию навыков составления SQL-запросов. Но не SQL-ем единым жив программист! Недавно, я нашел отличный способ усовершенствовать свои навыки владения Фортом ^[3]. Axiom ^[4] позволяет напрограммироваться на Форте вволю!

Мой рецепт получения Fun-а, при помощи Axiom, прост:

1. Выбираем любую ^[5] игру, с правилами позаковыристее, из числа ещё не реализованных ZoG-сообществом
2. Пытаемся её воплотить в жизнь, используя Axiom
3. Получаем удовольствие, в процессе решения возникающих при этом задач
4. В случае, если в полученное приложение интересно играть, выработанный Fun автоматически удваивается!

С выполнением первого пункта этого плана мне, обычно, помогает Internet. В этот раз, объектом для своих бесчеловечных экспериментов я выбрал Splut! ^[6]. Вот его описание ^[7] на IG Game Center. Не вдаваясь в пересказ правил, постараюсь объяснить, чем меня привлекла эта игра:

• В неё играют более двух игроков (что является, в определённой степени, вызовом, для алгоритмов AI)
• Ход игрока включает в себя последовательное перемещение нескольких (от 1 до 3) фигур
• Ходы, ведущие к выигрышу, не прямолинейны (нельзя просто взять и съесть фигуру, требуется выполнить последовательность ходов, объединенных одной целью)
• Правила этой игры весьма продуманны и очень оригинальны

Магия с разоблачением

Приступим к выработке Fun-а. Начнем с простого — с ходов Тролля. Обычный ход фигуры никаких сложностей не представляет. Его реализация очевидна и хорошо подходит для объяснения концепций Axiom:

: one-step ( 'dir -- )
        EXECUTE verify                      Шаг вперёд
        empty? verify                       Пусто?
        from                                Из исходной точки
        here                                Сюда
        move                                Ходим
        add-move                            Ход завершён
;

Сразу хочу посоветовать, обращать внимание на комментарии (в круглых скобках). Они помогут не запутаться в том, что происходит на стеке (это действительно важно в Форте). Также стоит обращать внимание на пробелы. Пробел, не поставленный, в неудачном месте, может заставить вас потратить немало времени.

По самому коду, думаю, всё понятно. Мы выполняем переход в направлении (взятом со стека), командой EXECUTE, после чего проверяем булевский результат перехода (если не TRUE, завершаем расчет хода). Затем, выполняем проверку того, что целевая клетка пуста, после чего, перемещаем фигуру. Команда move, выполняющая перемещение, берёт со стека два значения — точку начала хода (from) и позицию, в которой мы находимся, после перемещения (here). Команда add-move завершает формирование хода.

Чуть более сложен ход, с перемещением камня:

: drag ( 'dir 'opposite -- )
        EXECUTE verify                      Шаг назад
        is-stone? verify                    Это камень?
        piece-type                          Кручу верчу
        SWAP here SWAP                      Запутать хочу
        DUP EXECUTE DROP EXECUTE verify     Два раза шагаем вперёд
        empty? verify                       Пусто?
        from                                Из исходной точки
        here                                Сюда
        move                                Перемещаем фигуру
        capture-at                          Удаляем Камень с позиции, запомненной ранее
        from create-piece-type-at           И создаём его там, откуда начинали ход
        add-move                            Это всё!
;

: drag-to-north ( -- ) ['] north ['] south drag ;
: drag-to-south ( -- ) ['] south ['] north drag ;
: drag-to-east  ( -- ) ['] east  ['] west  drag ;
: drag-to-west  ( -- ) ['] west  ['] east  drag ;

Здесь мы кладём на стек сразу два направления — направление перемещения и противоположное ему. Сам код выглядит сложнее, из-за манипуляций со стеком, но к этому можно привыкнуть. Очень важно, что все «побочные» действия по захвату или созданию фигур должны выполняться после перемещения основной фигуры. Также важно помнить, что и в каком порядке лежит на стеке после каждой команды. Подробное описание самих команд всегда можно посмотреть в руководстве по Axiom.

На одном моменте, впрочем, стоит остановиться особо. Проверка того, что фигура в текущей клетке является Камнем, выполняется предикатом is-stone?. Разумеется, это не встроенная функция Axiom, а наша. Вот как выглядит её реализация:

DEFER           SSTONE
DEFER           NSTONE
DEFER           WSTONE
DEFER           ESTONE

: is-stone? ( -- ? )
        piece-type SSTONE =
        piece-type NSTONE = OR
        piece-type WSTONE = OR
        piece-type ESTONE = OR
;

...
{pieces
        {piece}         lock    {moves} pass-moves
        {piece}         sstone  {drops} stone-drops
        {piece}         nstone  {drops} stone-drops
        {piece}         wstone  {drops} stone-drops
        {piece}         estone  {drops} stone-drops
        {piece}         wizard  {moves} wizard-moves
        {piece}         dwarf   {moves} dwarf-moves
        {piece}         troll   {moves} troll-moves
pieces}

' sstone                IS SSTONE
' nstone                IS NSTONE
' wstone                IS WSTONE
' estone                IS ESTONE

Помните, в прошлой статье ^[8], я сетовал на то, что не удаётся использовать имена объектов (в данном случае фигур) до их определения? DEFER позволяет справится с этой проблемой. Плохо только то, что этот важный паттерн не описан в документации на Axiom.

Но почему у нас четыре типа камня? Разве нельзя было обойтись одним? Увы, правила Splut! составлены таким образом, что мы не можем обойтись без «индивидуальности» камней. Я покажу позже, для чего это нужно.

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

DEFER           CONTINUE-TYPE

: one-step ( 'dir -- )
        check-continue? IF
                EXECUTE verify
                empty? verify
                from
                here
                move
                add-move
        ELSE
                DROP
        ENDIF
;

: step-to-north ( -- ) ['] north one-step ;
: step-to-south ( -- ) ['] south one-step ;
: step-to-east  ( -- ) ['] east  one-step ;
: step-to-west  ( -- ) ['] west  one-step ;

: drag ( 'dir 'opposite -- )
        check-continue? IF
                EXECUTE verify
                is-stone? verify
                piece-type
                SWAP here SWAP
                DUP EXECUTE DROP EXECUTE verify
                empty? verify
                from
                here
                move
                capture-at
                DUP lock-stone
                from create-piece-type-at
                add-move
        ELSE
                DROP DROP
        ENDIF
;

: drag-to-north ( -- ) ['] north ['] south drag ;
: drag-to-south ( -- ) ['] south ['] north drag ;
: drag-to-east  ( -- ) ['] east  ['] west  drag ;
: drag-to-west  ( -- ) ['] west  ['] east  drag ;

: take-stone ( 'dir -- )
        check-continue? IF
                EXECUTE verify
                is-stone? verify
                CONTINUE-TYPE partial-move-type
                from
                here
                move
                add-move
        ELSE
                DROP
        ENDIF
;

: take-to-north ( -- ) ['] north take-stone ;
: take-to-south ( -- ) ['] south take-stone ;
: take-to-east  ( -- ) ['] east  take-stone ;
: take-to-west  ( -- ) ['] west  take-stone ;

: drop-stone ( 'opposite 'dir -- )
        check-edge? check-wizard? OR 
        on-board? AND IF
                check-troll? piece-is-not-present? AND IF
                        player piece-type
                        drop
                        WIZARD = IF
                                drop-team
                        ELSE
                                DROP
                        ENDIF
                        lock-continue
                        current-piece-type lock-stone
                        add-move
                ENDIF
        ENDIF
;

: drop-to-north ( -- ) ['] north ['] south drop-stone ;
: drop-to-south ( -- ) ['] south ['] north drop-stone ;
: drop-to-east  ( -- ) ['] east  ['] west  drop-stone ;
: drop-to-west  ( -- ) ['] west  ['] east  drop-stone ;

{moves troll-moves
	{move} step-to-north {move-type} normal-type
	{move} step-to-south {move-type} normal-type
	{move} step-to-east  {move-type} normal-type
	{move} step-to-west  {move-type} normal-type
	{move} drag-to-north {move-type} normal-type
	{move} drag-to-south {move-type} normal-type
	{move} drag-to-east  {move-type} normal-type
	{move} drag-to-west  {move-type} normal-type
	{move} take-to-north {move-type} normal-type
	{move} take-to-south {move-type} normal-type
	{move} take-to-east  {move-type} normal-type
	{move} take-to-west  {move-type} normal-type
moves}

{moves stone-drops
	{move} drop-to-north {move-type} continue-type
	{move} drop-to-south {move-type} continue-type
	{move} drop-to-east  {move-type} continue-type
	{move} drop-to-west  {move-type} continue-type
moves}

' continue-type         IS CONTINUE-TYPE

Я не буду описывать вспомогательные функции. Их реализацию можно посмотреть здесь ^[9]. Остановлюсь лишь на бросках. Тролль может взять камень ходом take-stone (реализация этой функции тривиальна), после чего команда partial-move-type включает продолжение хода, с заданным типом (continue-type). Под этим типом зарегистрирован единственный тип хода — бросок (drop) Камня на доску.

Бросать можно не абы как, а в строго определённые места! По правилам, камень летит от Тролля по прямой (вертикали или горизонтали), пролетая над головой Гномов, до препятствия (Мага, края доски или другого Тролля). Мага пришибает сразу, в других случаях, падает на доску. Если в этом месте оказался Гном — ему просто не повезло. Это сложное в реализации правило и будет удобнее воплотить его в жизнь, начав с другого конца. Будем искать поля, граничащие с препятствием и двигаться от них, в противоположном направлении, по пустым клеткам или клеткам занятыми Гномами. Если по дороге встретим своего Тролля, значит в то место, с которого мы начали движение, можно бросать камень.

Кроме того, в коде реализованы сопутствующие правила. Например то, что при убийстве Мага, с поля удаляется вся его команда, а также то, что после броска камня, ход сразу же переходит к другому игроку. Я не буду останавливаться на этом подробно.

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

VARIABLE        forward
VARIABLE        backward
VARIABLE        step-count
VARIABLE        here-pos

: push-step ( 'opposite 'dir -- )
        check-continue? IF
                0 step-count ! forward ! backward !
                forward @ EXECUTE verify not-empty? verify
                step-count ++
                player piece-type
                here here-pos !
                BEGIN
                        forward @ EXECUTE IF
                                empty? IF
                                        TRUE
                                ELSE
                                        step-count ++
                                        player piece-type
                                        FALSE
                                ENDIF
                        ELSE
                                BEGIN
                                        step-count @ 0> IF
                                                step-count --
                                                DROP DROP
                                                FALSE
                                        ELSE
                                                TRUE
                                        ENDIF
                                UNTIL
                                TRUE
                        ENDIF
                UNTIL
                step-count @ 0> verify
                from here-pos @ move
                BEGIN
                        step-count @ 0> IF
                                step-count --
                                DUP is-stone-type? IF
                                        DUP lock-stone
                                ENDIF
                                create-player-piece-type
                                backward @ EXECUTE DROP
                                FALSE
                        ELSE
                                TRUE
                        ENDIF		
                UNTIL
                add-move
        ELSE
                DROP DROP
        ENDIF
;

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

Конечно, Маги не были бы Магами, если бы не доставили нам максимум неприятностей. Маги могут левитировать камни. Любые, но… при определенных условиях. Например нельзя левитировать камень, который перемещался (любым образом) на предыдущем ходу. Здесь сразу возникает вопрос: что считать предыдущим ходом? К сожалению, правила не расшифровывают этот момент. В своём коде я реализовал очистку признаков перемещения камней (именно здесь нужна индивидуальность, у каждого камня свой флаг) сразу перед передачей хода первому игроку. Конечно, это даёт ему серьезное преимущество (он может двигать любые Камни, а следующие игроки только те, которые не двигал он), но другие возможные реализации этого правила также не безупречны.

: fly-stone ( 'dir -- )
        check-continue? IF
                DUP EXECUTE empty? AND IF
                        a5 to
                        BEGIN
                                is-stone? not-locked? AND IF
                                        here here-pos !
                                        DUP piece-type SWAP
                                        EXECUTE SWAP
                                        can-fly? AND IF
                                                from to
                                                DUP EXECUTE DROP
                                                from
                                                here
                                                move
                                                here-pos @ to
                                                DUP piece-type SWAP capture
                                                EXECUTE DROP
                                                DUP lock-stone
                                                DUP begin-fly
                                                create-piece-type
                                                add-move
                                        ENDIF
                                        here-pos @ to
                                ENDIF
                                DUP next NOT
                        UNTIL
                ENDIF
                DROP
        ELSE
                DROP
        ENDIF
;

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

: push-stone ( 'dir -- )
	check-continue? IF
		DUP EXECUTE is-stone? not-locked? AND AND IF
			piece-type can-fly-lock? IF
				here SWAP
				piece-type SWAP
				EXECUTE empty? AND IF
					SWAP from SWAP move
					DUP lock-stone
					DUP begin-fly
					create-piece-type
					add-move
				ELSE
					DROP DROP DROP
				ENDIF
			ELSE
				DROP
			ENDIF
		ENDIF
	ELSE
		DROP
	ENDIF
;

Этот код проще, поскольку не приходится искать Камни по всему полю. Если мы хотим встать на поле, занятое Камнем, то единственный Камень, который можно левитировать — это он и есть.

А и Б сидели на трубе

Как я уже говорил выше, реализация AI, для игр с участием более двух игроков, связана с некоторыми сложностями. Проблемы начинаются уже при определении условия завершения игры. Например, в разработанной мной недавно реализации игры Yonin Shogi ^[10] (вариант японских шахмат на 4 человек), было бы заманчиво определить условие поражения следующим образом:

(loss-condition (South North West East) (checkmated King))

Эта запись означает, что игра должна вестись до мата Королю любого из игроков. Увы, этот подход не работает! Я уже писал ^[11] о том, что команда checkmated, несёт в себе слишком много «магии». В частности, она определяет, что Король всегда должен уходить из под шаха (и никогда не вставать под шах). В целом, это работает… до тех пор пока в игре участвуют два игрока. Видео иллюстрирует проблему:

Как можно заметить, checkmated работает нормально лишь для одного из 4 игроков. Для остальных игроков, защита от шаха не считается обязательным ходом! Разумеется, на следующем ходу, такого короля возможно съедят, но этот факт лишь усугубляет ситуацию. Как ни крути, нормального мата в такой игре поставить не удастся.

В Splut! ситуация еще хуже. Игра должна вестись до тех пор, пока на доске не останется лишь одна команда. Но ZoG не позволяет изменять список очередности ходов во время игры! Это означает, что каждая выбывшая команда должна делать свой ход, когда до нее дойдет очередь (разумеется она будет пасовать, поскольку никакой другой возможности сделать ход нет). Кроме того, в Splut! каждая команда делает несколько ходов подряд (1-2 в начале игры и 3 в середине партии). В общем, для меня не стало сюрпризом то, что штатный AI Axiom не справился с этой игрой.

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

За основу я взял следующий, известный многим, алгоритм из книги Евгения Корнилова «Программирование Шахмат и других логических игр»:

int AlphaBeta(int color, int Depth, int alpha, int beta)
{
    if (Depth == 0) return Evaluate(color);
    int score = -INFINITY;
    PMove move = GenerateAllMoves(color);

    while (move)
    {
        MakeMove(move);
        int tmp = -AlphaBeta(color==WHITE?BLACK:WHITE, Depth - 1, -beta, -alpha);
        UnMakeMove(move);
        if (tmp > score) score = tmp;
        if (score > alpha) alpha = score;
        if (alpha >= beta) return alpha;
        move = move -> next;
    }
    return score;
}

Как легко заметить, в исходном виде, этот алгоритм нам совершенно не подходит. У нас больше двух игроков, да и с чередованием ходов все гораздо сложнее. Но этот алгоритм — хорошая отправная точка для разработки собственной версии.

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

VARIABLE        Depth

MaxDepth []     CurrMove[]
MaxDepth []     CurrTurn[]
MaxDepth []     CurrScore[]

: Score ( alpha beta turn -- score )
        Depth -- Depth @
        0< IF
                EvalCount ++
                SWAP DROP SWAP DROP
                Eval
                SWAP turn-offset-to-player
                current-player <> IF
	                NEGATE
                ENDIF
        ELSE
                DUP turn-offset-to-player FALSE 0 $GenerateMoves 
                Depth @ CurrTurn[] !
                $FirstMove Depth @ CurrMove[] !
                -10000 Depth @ CurrScore[] !
                BEGIN
                        $CloneBoard
                        Depth @ CurrMove[] @
                        .moveCFA EXECUTE
                        2DUP
                        Depth @ CurrTurn[] @ next-turn-offset
                        RECURSE
                        $DeallocateBoard
                        $Yield
                        DUP Depth @ CurrScore[] @ > IF
                                Depth @ CurrScore[] !
                        ELSE
                                DROP
                        ENDIF
                        Depth @ CurrTurn[] @ turn-offset-to-player
                        current-player <> IF
                                NEGATE SWAP NEGATE
                        ENDIF
                        OVER Depth @ CurrScore[] @ < IF
                                SWAP DROP
                                Depth @ CurrScore[] @
                                SWAP
                        ENDIF
                        2DUP >= IF
                                OVER Depth @ CurrScore[] !
                                TRUE
                        ELSE
                                Depth @ CurrTurn[] @ turn-offset-to-player
                                current-player <> IF
                                        NEGATE SWAP NEGATE
                                ENDIF
                                Depth @ CurrMove[] @
                                $NextMove
                                DUP Depth @ CurrMove[] !
                                NOT
                        ENDIF
                UNTIL
                $DeallocateMoves
                DROP DROP
                Depth @ CurrScore[] @
                Depth @ CurrTurn[] @ turn-offset-to-player
                current-player <> IF
                        NEGATE
                ENDIF
        ENDIF
        Depth ++
;

Здесь очень много «магии» Форта и Аксиомы, связанной с генерацией ходов и позиций, но, при некотором напряжении, исходный алгоритм вполне просматривается. Для разгрузки стека пришлось эмулировать несколько стеков с переменными, используемыми в рекурсивных вызовах. На самом стеке, в процессе вычисления, лежат всего два значения alpha и beta. В рекурсивные вызовы (RECURSE) они всегда передаются в одном и том же порядке, но если расчет выполняется для враждебного игрока, мы меняем их знак, после чего, меняем эти значения местами. Также мы изменяем знак оценки, полученной при оценке позиции враждебным игроком.

Вызывается эта функция из уже знакомой нам, по прошлой статье, реализации Custom Engine:

3  CONSTANT	MaxDepth

VARIABLE        BestScore
VARIABLE        Nodes

: Custom-Engine ( -- )
        -10000 BestScore !
        0 Nodes !
        $FirstMove
        BEGIN
                $CloneBoard
                DUP $MoveString 
                CurrentMove!
                DUP .moveCFA EXECUTE
                MaxDepth Depth !
                0 EvalCount !
                BestScore @ 10000 turn-offset next-turn-offset Score
                0 5 $RAND-WITHIN +
                BestScore @ OVER <
                IF
                        DUP BestScore !
                        Score!
                        0 Depth!
                        DUP $MoveString BestMove!
                ELSE
                        DROP
                ENDIF
                $DeallocateBoard
                Nodes ++
                Nodes @ Nodes!
                $Yield
                $NextMove
                DUP NOT
        UNTIL
        DROP
;

Можно заметить, что в этом коде мы прибавляем к значению оценки случайное число от 1 до 5. Это делается для того, чтобы программа не ходила всегда одинаково в тех случаях, когда оценки ходов различаются незначительно.

Как обычно, главная сложность заключается в построении оценочной функции. Я не буду загружать статью листингом текущего ее варианта (желающие всегда могут посмотреть код на GitHub ^[12]), скажу только, что в ней, в настоящее время, учитываются следующие моменты:

• Количество вражеских Магов (наша основная цель — уменьшение этого значения)
• Количество дружественных Магов (если эта величина изменится с 1 на 0, игра для нас закончится)
• Количество вражеских Гномов (всегда приятно связать противнику руки)
• Количество дружественных Гномов (не то чтобы мы без него не обошлись, но своя фигура все-таки)
• Штраф за нахождение дружественного Мага на одной линии с Камнем (это действительно опасно)
• Бонусы за нахождение вражеских Магов на одних линиях с Камнями (по той же причине)
• Суммарное количество шагов от Троллей до Камней (стараемся уменьшить для своих и увеличить для чужих)

Это конечно не идеальный вариант. Весовые значения стоит подобрать более оптимально, да и сам факт, к примеру, нахождения Мага на одной линии с Камнем, сам по себе, ни о чем не говорит. Линия броска может быть перекрыта, например Троллем, да и до камня надо еще добраться, чтобы его кинуть. Так или иначе, мы написали код и можем посмотреть, как он работает:

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

Подсчитали — прослезились

Конечно, чтобы оценить качество AI, можно сыграть с ним много раз и построить «экспертную оценку», но это не наш метод. В комплекте с Axiom поставляется замечательная утилита AutoPlay, позволяющая автоматизировать этот процесс. К сожалению, она пока не умеет работать с играми, рассчитанными более чем на 2 игроков, но это не проблема. Специально для неё, создадим конфигурацию с двумя игроками (камней оставим 4 штуки):

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

{players
	{player}	South	 {search-engine} Custom-Engine
	{neutral}	West
	{player}	North	 {search-engine} Custom-Engine
	{neutral}	East
	{player}	?Cleaner {random}
players}

{turn-order
	{turn}	South
	{turn}	North
	{turn}	North
	{repeat}
	{turn}  ?Cleaner {of-type} clear-type
	{turn}	South
	{turn}	South
	{turn}	South
	{turn}	North
	{turn}	North
	{turn}	North
turn-order}

{board-setup
	{setup}	South sstone e1
	{setup}	South wizard d2
	{setup}	South dwarf  e2
	{setup}	South troll  f2
	{setup}	South lock   f1

	{setup}	West  wstone a5

	{setup}	North nstone e9
	{setup}	North wizard f8
	{setup}	North dwarf  e8
	{setup}	North troll  d8
	{setup}	North lock   h1

	{setup}	East  estone i5
board-setup}

Также, нам понадобится конфигурация, в которой игроки делают случайные ходы:

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

{players
	{player}	South	 {random}
	{neutral}	West
	{player}	North	 {random}
	{neutral}	East
	{player}	?Cleaner {random}
players}

{turn-order
	{turn}	South
	{turn}	North
	{turn}	North
	{repeat}
	{turn}  ?Cleaner {of-type} clear-type
	{turn}	South
	{turn}	South
	{turn}	South
	{turn}	North
	{turn}	North
	{turn}	North
turn-order}

{board-setup
	{setup}	South sstone e1
	{setup}	South wizard d2
	{setup}	South dwarf  e2
	{setup}	South troll  f2
	{setup}	South lock   f1

	{setup}	West  wstone a5

	{setup}	North nstone e9
	{setup}	North wizard f8
	{setup}	North dwarf  e8
	{setup}	North troll  d8
	{setup}	North lock   h1

	{setup}	East  estone i5
board-setup}

Результаты получились, на удивление, неплохими (хотя для расчета 100 партий потребовалась целая ночь):

Final results:
Player 1 "Random", wins = 13.
Player 2 "Duel", wins = 87.
Draws = 0
100 game(s) played

Почему программа работает так долго? Посмотрим, сколько раз, при вычислении хода, вызывается оценочная функция (данные расчета на 5 ходов в глубину):

Да, 8000 вызовов оценочной функции это безусловно много, но почему здесь три ряда? Попробую объяснить. Вот как мы считаем количество вызовов Eval:

$gameLog        ON

VARIABLE        EvalCount

: Score ( alpha beta turn -- score )
        Depth -- Depth @
        0< IF
                EvalCount ++
                ...
	ELSE
...
;

: Custom-Engine ( -- )
        ...
	BEGIN
                ...
                0 EvalCount !
		BestScore @ 10000 turn-offset next-turn-offset Score
		0 5 $RAND-WITHIN +
		EvalCount @ . CR
                ...
        UNTIL
        DROP
        CR
;

На выходе, получается следующая последовательность:

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

Можно заметить, что числа в группах, в основном, убывают, но иногда случаются нарушающие монотонное убывание «всплески». Попробуем подсчитать их количество:

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

1. У меня отсутствуют эвристики, позволяющие произвести предварительную оценку «качества» ходов в игре Splut!
2. Даже если бы такие эвристики были, предварительная оценка и сортировка списка ходов в Axiom связана с определенными техническими сложностями (и издержками производительности)

Другим методом увеличения глубины перебора мог бы послужить «углубленный» перебор «форсированных» ходов. Также, было бы неплохо отсекать повторяющиеся позиции (с этим мог бы сильно помочь Zobrist hashing ^[13]).

Посмотрим, как изменяется количество просматриваемых позиций, при увеличении глубины перебора:

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

Но давайте подумаем, что такое 5 ходов в игре Splut? Этого недостаточно даже для того, чтобы рассчитать возможные ходы всех игроков! Даже в режиме Duel. Это все равно что рассчитывать игру в Шахматы всего на 1 ход вперед! Сложно ожидать особого интеллекта от такой программы.

Конечно в Splut! гораздо меньше фигур чем в Шахматах, но и ходы более сложные! Чтобы победить, программа должна уметь строить долгосрочные планы, на много ходов вперед. Пока я не знаю, как этого добиться, используя Axiom, но вероятно как то можно.
Я работаю над этим.

Автор: GlukKazan

Источник ^[14]