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

Linus Torvalds

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

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

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

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

С выполнением первого пункта этого плана мне, обычно, помогает Internet. В этот раз, объектом для своих бесчеловечных экспериментов я выбрал Splut!. Вот его описание на 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 

Помните, в прошлой статье, я сетовал на то, что не удаётся использовать имена объектов (в данном случае фигур) до их определения? 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 

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

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

Эта запись означает, что игра должна вестись до мата Королю любого из игроков. Увы, этот подход не работает! Я уже писал о том, что команда 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), скажу только, что в ней, в настоящее время, учитываются следующие моменты:

• Количество вражеских Магов (наша основная цель — уменьшение этого значения)
• Количество дружественных Магов (если эта величина изменится с 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).

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

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

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

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