Программирование «для души»
Полно, голубь, не греши! Убери свои гроши.Я ведь это не для денег.Я ведь это для души.Леонид Филатов «Сказка про Федота-стрельца, удалого молодца»
Just for Fun.
Linus Torvalds
Не секрет, что люди получают удовольствие по-разному. Одним нравится смотреть телевизор, другие собирают квадрокоптеры. Я хочу поделиться своим рецептом. Вряд ли он будет полезен всем, но возможно кого-то заинтересует. Мне нравится писать программы (и думаю, что это не редкость, даже среди профессиональных программистов), но мне не очень нравится, когда этот процесс превращается в унылую рутину.
Чтобы быть интересным, программирование должно представлять собой, своего рода «зарядку для ума». Хорошим примером такого (полезного) развлечения является, известный многим ресурс, посвященный совершенствованию навыков составления SQL-запросов. Но не SQL-ем единым жив программист! Недавно, я нашел отличный способ усовершенствовать свои навыки владения Фортом. Axiom позволяет напрограммироваться на Форте вволю!
Мой рецепт получения Fun-а, при помощи Axiom, прост:
Выбираем любую игру, с правилами позаковыристее, из числа ещё не реализованных ZoG-сообществом Пытаемся её воплотить в жизнь, используя Axiom Получаем удовольствие, в процессе решения возникающих при этом задач В случае, если в полученное приложение интересно играть, выработанный 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, несёт в себе слишком много «магии». В частности, она определяет, что Король всегда должен уходить из под шаха (и никогда не вставать под шах). В целом, это работает… до тех пор пока в игре участвуют два игрока. Видео иллюстрирует проблему:[embedded content]
Как можно заметить, 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, игра для нас закончится) Количество вражеских Гномов (всегда приятно связать противнику руки) Количество дружественных Гномов (не то чтобы мы без него не обошлись, но своя фигура все-таки) Штраф за нахождение дружественного Мага на одной линии с Камнем (это действительно опасно) Бонусы за нахождение вражеских Магов на одних линиях с Камнями (по той же причине) Суммарное количество шагов от Троллей до Камней (стараемся уменьшить для своих и увеличить для чужих) Это конечно не идеальный вариант. Весовые значения стоит подобрать более оптимально, да и сам факт, к примеру, нахождения Мага на одной линии с Камнем, сам по себе, ни о чем не говорит. Линия броска может быть перекрыта, например Троллем, да и до камня надо еще добраться, чтобы его кинуть. Так или иначе, мы написали код и можем посмотреть, как он работает:[embedded content]
Как и ожидалось, 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 ; На выходе, получается следующая последовательность: Результат 99265514737492212222222211
33613250
382422133539221624049
146518911111115291
1227550
15092074637492249800415877963
56089044444444
Каждая группа чисел (отделенная пустой строкой) содержит результаты просмотра всех возможных ходов игрока из текущей позиции. В графике, представленном выше, первый ряд показывает минимальное значение в группе, второй — среднее, третий — максимальное. Разница между максимальным и минимальным значением определяется эффективностью альфа-бета отсечения. Среднее значение — определяет производительность, на которую мы можем рассчитывать, при заданной глубине перебора.Можно заметить, что числа в группах, в основном, убывают, но иногда случаются нарушающие монотонное убывание «всплески». Попробуем подсчитать их количество:
Слишком много! В некоторых группах более 16 нарушений монотонного убывания. Если бы было возможно просматривать ходы в более оптимальной последовательности, наверняка удалось бы улучшить показатели производительности (и возможно добиться большей глубины перебора). К сожалению, следующие два пункта мешают мне это сделать:
У меня отсутствуют эвристики, позволяющие произвести предварительную оценку «качества» ходов в игре Splut! Даже если бы такие эвристики были, предварительная оценка и сортировка списка ходов в Axiom связана с определенными техническими сложностями (и издержками производительности) Другим методом увеличения глубины перебора мог бы послужить «углубленный» перебор «форсированных» ходов. Также, было бы неплохо отсекать повторяющиеся позиции (с этим мог бы сильно помочь Zobrist hashing).Посмотрим, как изменяется количество просматриваемых позиций, при увеличении глубины перебора:
Поскольку среднее время ожидания завершения ходов всех противников (при глубине просмотра 5 ходов) составляет около 1 минуты, очевидно, что это максимальная глубина перебора, на которую можно рассчитывать, при текущей реализации алгоритма (любое ее увеличение сделает игру человека с программой совершенно не комфортной).
Но давайте подумаем, что такое 5 ходов в игре Splut? Этого недостаточно даже для того, чтобы рассчитать возможные ходы всех игроков! Даже в режиме Duel. Это все равно что рассчитывать игру в Шахматы всего на 1 ход вперед! Сложно ожидать особого интеллекта от такой программы.
Конечно в Splut! гораздо меньше фигур чем в Шахматах, но и ходы более сложные! Чтобы победить, программа должна уметь строить долгосрочные планы, на много ходов вперед. Пока я не знаю, как этого добиться, используя Axiom, но вероятно как то можно.Я работаю над этим.
P.S. Я хочу выразить признательность разработчику Axiom. Greg Schmidt — настоящий энтузиаст компьютерной разработки настольных игр. Он поддерживает код Axiom уже почти 10 лет, постоянно улучшая его и добавляя что то новое. С того момента, как я выложил Axiom-реализацию игры Ур в ZoG, он ведёт со мной оживленную переписку, помогая и объясняя тонкости работы Axiom. Буквально вчера, с его помощью, мне удалось обнаружить и исправить весьма неприятную ошибку в реализации Ур-а. Я очень благодарен ему за поддержку!
P.P. S. При оформлении статьи, использован фрагмент работы известного российского художника-комиксиста Даниила Кузьмичева.
