Полно, голубь, не греши!
Убери свои гроши.
Я ведь это не для денег.
Я ведь это для души.
Леонид Филатов "Сказка про Федота-стрельца, удалого молодца"
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, несёт в себе слишком много «магии». В частности, она определяет, что Король всегда должен уходить из под шаха (и никогда не вставать под шах). В целом, это работает… до тех пор пока в игре участвуют два игрока. Видео иллюстрирует проблему:
Как можно заметить, 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
;
На выходе, получается следующая последовательность:
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 нарушений монотонного убывания. Если бы было возможно просматривать ходы в более оптимальной последовательности, наверняка удалось бы улучшить показатели производительности (и возможно добиться большей глубины перебора). К сожалению, следующие два пункта мешают мне это сделать:
- У меня отсутствуют эвристики, позволяющие произвести предварительную оценку «качества» ходов в игре Splut!
- Даже если бы такие эвристики были, предварительная оценка и сортировка списка ходов в Axiom связана с определенными техническими сложностями (и издержками производительности)
Другим методом увеличения глубины перебора мог бы послужить «углубленный» перебор «форсированных» ходов. Также, было бы неплохо отсекать повторяющиеся позиции (с этим мог бы сильно помочь Zobrist hashing).
Посмотрим, как изменяется количество просматриваемых позиций, при увеличении глубины перебора:
Поскольку среднее время ожидания завершения ходов всех противников (при глубине просмотра 5 ходов) составляет около 1 минуты, очевидно, что это максимальная глубина перебора, на которую можно рассчитывать, при текущей реализации алгоритма (любое ее увеличение сделает игру человека с программой совершенно не комфортной).
Но давайте подумаем, что такое 5 ходов в игре Splut? Этого недостаточно даже для того, чтобы рассчитать возможные ходы всех игроков! Даже в режиме Duel. Это все равно что рассчитывать игру в Шахматы всего на 1 ход вперед! Сложно ожидать особого интеллекта от такой программы.
Конечно в Splut! гораздо меньше фигур чем в Шахматах, но и ходы более сложные! Чтобы победить, программа должна уметь строить долгосрочные планы, на много ходов вперед. Пока я не знаю, как этого добиться, используя Axiom, но вероятно как то можно.
Я работаю над этим.
Автор: GlukKazan
