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

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

    Леонид Филатов "Сказка про Федота-стрельца, удалого молодца"

    Just for Fun.

    Linus Torvalds


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

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

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

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


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

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

    Ремарка
    Вот что пишет автор, по поводу прав на свою игру:

    The SPLUT game idea and design are copyrighted. You cannot use any of the ideas or contents of this publication for commercial purposes without written authorization of the designer Tommy De Coninck.

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

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


    Приступим к выработке 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 такая возможность имеется (забегая вперёд, скажу, что получилось не очень здорово, но попробовать то стоило).

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

    Alpha-Beta отсечение с амортизацией отказов
    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;
    }
    


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

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

    Обобщенное Alpha-Beta отсечение
    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:

    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 штуки):

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


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

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


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

    Результат
    992
    655
    147

    3749
    22
    1
    22
    22
    22
    22
    1
    1

    336
    132
    50

    382
    42
    213
    35
    392
    21
    62
    40
    49

    1465
    189
    1
    1
    1
    1
    1
    1
    1
    52
    91

    122
    75
    50

    1509
    2074
    637
    492
    249
    800
    415
    877
    963

    5608
    90
    4
    4
    4
    4
    4
    4
    4
    4

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

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



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

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

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

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



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

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

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

    P.S.
    Я хочу выразить признательность разработчику Axiom. Greg Schmidt — настоящий энтузиаст компьютерной разработки настольных игр. Он поддерживает код Axiom уже почти 10 лет, постоянно улучшая его и добавляя что то новое. С того момента, как я выложил Axiom-реализацию игры Ур в ZoG, он ведёт со мной оживленную переписку, помогая и объясняя тонкости работы Axiom. Буквально вчера, с его помощью, мне удалось обнаружить и исправить весьма неприятную ошибку в реализации Ур-а. Я очень благодарен ему за поддержку!

    P.P.S.
    При оформлении статьи, использован фрагмент работы известного российского художника-комиксиста Даниила Кузьмичева.

    • +36
    • 25.9k
    • 2
    Share post

    Similar posts

    Comments 2

      0
      I don't even…

      Эпический труд, а почему форт, аксиом, а не что-то более ширпотребное? В чем смысл использовния имеено этих средств?
        0
        Ну в эпиграфе, в принципе написано.

        Если серьезно, я не знаю альтернативы ZoG-у и Axiom-е, на сегодняшний день. Есть масса специализированных (например шахматных) движков всех форм и размеров, но эти два претендуют на то, чтобы называться универсальными. Насколько хорошо у них это получается — тема для отдельного разговора, но это своего рода монополисты (или просто я о других не знаю). А раз монополисты — они и определяют язык. В случае ZoG это что-то лиспоподобное, в случае Axiom — ForthScript.

        У меня конечно есть в планах писать что-то подобное на чем нибудь более удобоваримом (на Java например), но это дело не быстрое. Очень много писать надо. В общем, то что я сейчас пишу, своего рода быстрый прототип.

      Only users with full accounts can post comments. Log in, please.