Хабрахабр

Dagaz: Подробности

imageВ «пи» цифр не пересчитать,
«е» — бесконечно столь же.
А если их с конца писать, какое будет больше?

Мартин Гарднер «Крестики-нолики»

Очередной релиз вновь затянулся. Для этой статьи, я хотел выбрать другой эпиграф, но счёл его излишне пафосным. Работа на новом месте отнимает уйму сил, но я продолжаю находить время для своего маленького увлечения. За это время, я успел сменить работу! Я расскажу вам об этом. И надо сказать, то, с чем мне приходится сталкиваться в процессе, становится всё сложнее и сложнее. Своего рода гонки, в которых надо занять своими фигурами дом противника, раньше него. Я хотел начать с другого эпиграфа, но этот тоже неплох.
В этот раз, случились новые манкалы и "игры-переходы" (это Хальма и её родственники). Да что я вам объясняю? Фигуры (и свои и чужие) можно перепрыгивать (как в шашках), но никаких взятий нет. Наверняка, многие из вас в детстве играли в "Уголки".

На первый взгляд, игра выглядит простой, но проблемы начались уже на уровне ядра. Помните, я рассказывал о составных ходах? По многим причинам, их удобнее представлять именно составными — в виде единого целого, а не в виде последовательности частичных ходов. Это более удобно для AI, да и с точки зрения дизайна, существуют игры, описание которых в форме составных ходов выглядит гораздо естественнее. Но есть одна проблема.

В Уголках — можно прыгать через свои или противника фигуры до бесконечности. В шашках, при выполнении составного хода, фигуры убираются с доски (возможно по завершении хода). И никакие расширения здесь не спасают, поскольку всё зацикливается не доходя до них, в ядре, ещё на этапе генерации списка ходов. Буквально. Пришлось изменять эту логику, реализуя там опцию (detect-loops), о которой вполне стоило бы подумать заранее.

С ботом всё тоже вышло непросто

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

Нельзя направлять все фигуры на одно и то же поле. С целевыми полями тоже не всё ясно. Идеально было бы определять оптимальные целевые поля для каждой из фигур и двигаться к ним, но это сложно, в вычислительном плане. Первая фигура, которая до него доберётся тут же его и займёт. В общем, я решил не заглядывать далеко вперёд и ограничиться чисто эвристическим алгоритмом. Кроме того, ситуация на доске с каждым ходом меняется.

С такой вот оценкой качества хода

Dagaz.AI.heuristic = function(ai, design, board, move) if (_.indexOf(t.goal, m.end) >= 0) { r = 700 + getDistance(t.first, m.start) - getDistance(t.first, m.end); } if ((r == 1) && (_.indexOf(t.second, m.end) >= 0)) { r = 500 - getDistance(t.second, m.end); } } if (r == 1) { if (design.inZone(2, board.player, m.end) && !design.inZone(2, board.player, m.start)) { r = 300; } } if (bestFound(design, board, 300)) return -1; if (r == 1) { var goals = getGoals(design, board, board.player); if (!_.isUndefined(goals[m.start])) { var goal = goals[m.start]; if (m.next == goal.next) { r = 100 + distance(goal.end, m.start) - distance(goal.end, m.end); } } } if (notBest(design, board, r)) return -1; var b = board.apply(move); if (isRestricted(design, b, board.player)) return -1; } return r;
}

Не идеальное решение, но для начала вполне рабочее. Если бот видит ход, которым можно «пропрыгать» в «дом» противника, он выбирает его. В противном случае — постепенно уменьшает расстояние до цели, стараясь избегать заторов. Самая печальная ситуация может случиться если один игрок (случайно или умышленно) оставит свою фигуру в «доме», а другой — «запрёт» её двойным рядом своих фигур.

Конечно, вероятность такой ситуации довольно низка

Его предложение заключается в следующем: если фигура имеет возможность покинуть свой «дом», прыжком через фигуру противника или цепочкой прыжков, начинающейся с такого хода — она обязана это сделать. Благодаря правилу, предложенному Сидни Сэксоном — изобретателем и коллекционером игр из Нью Йорка. После выхода из своего «дома», фигура более не может в него возвращаться (хотя и имеет право проходить через него, в процессе выполнения хода).
Я опробовал различные варианты правил, исключающих возможность запирания фигур в их собственном «доме» и нашёл правило Сидни Сэксона наиболее удачным.

На всякий случай, я запрещаю ходы «запирающие» противника (при отсутствии просмотра на много ходов вперёд, можно позволить себе довольно сложные эвристики), устанавливая им отрицательные оценки, но не менее опасна для бота и ситуация «запирания» пустых целевых полей (особенно это заметно в классической Хальме, с её чисто ортогональными ходами). В общем, этому боту есть куда расти.

И таких игр много! В играх, где фигуры разрешается брать, всё ещё более усложняется. Но лично мне куда больше нравится гораздо менее известная игра, построенная на основе той же механики. Пожалуй, наиболее известной из них является "Камелот", придуманный Джорджем Паркером в 1930 году.

Эта игра — сама история! В далёком 1908 году, Суфражистки придумали её для продвижения своих политических взглядов. Здесь есть всё: Палата общин, Альберт-холл, городская тюрьма и больница. Женщины-суфражистки сражаются с полисменами. Их цель — провести 6 своих человек в Палату общин. В свой штаб — Альберт-холл они заходить не могут. Перемещаются фигуры в любом направлении. Также допускаются прыжки через дружеские и вражеские фигуры.

Если дело происходит на «арене», вражеские фигуры, при прыжке через них, срубаются и отправляются в тюрьму или больницу. Серия прыжков, при этом, может быть сколь угодно длинной. Когда в тюрьме и больнице набирается по 6 фигур, их можно «обменять», снова введя в игру. Обычные фигуры рубят только по диагонали, крупные (констебли и лидеры суфражисток) — в любом направлении. Таким образом, фигуры, как в "Сёги" или "Столбовых шашках", никогда не покидают игру.

Вообще, весь этот релиз как раз на тему подобных опций. Например, я наконец-то осилил правильное превращение фигур в Шахматах (до сих пор, все пешки превращались только в ферзей, что вообще говоря, неправильно). Я не стал сильно с этим заморачиваться и отрисовал диалог выбора прямо на канвасе. Получилось неплохо (ещё бы руки дошли сделать так, чтобы они мат от пата отличали, так было бы вообще замечательно).

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

Нет-нет, это не вся польза!

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

Именно этот аспект игры автоматизирует опция "progressive-levels", выполняющая автоматический переход к следующему этапу игры, при победе одного из игроков. А поскольку начальная расстановка фигур от одного этапа к другому различается, она вычисляется модулем common-setup и передаётся в следующий этап игры через URL.

Рука об руку с этой возможностью идёт другой способ, позволяющий разнообразить начальную расстановку фигур. Опция "selector" позволяет кодировать несколько начальных расстановок (и даже конфигураций доски), в рамках одного JS-файла. Обновите начальную страницу Reversi и вы поймёте, что я имею в виду.

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

Это действительно удобно, но из двух стрелочек, занимающих место наверху, можно извлечь ещё больше пользы. Именно этим и занимается опция "advisor-mode". Если пользователь думает дольше заданного времени, бот, с которым он играет, рассчитывает ход за него и помещает новое игровое состояние в «session-manager». Предложенный ход можно принять, просто нажав кнопку «вперёд». А если ход не понравится, то его всегда можно откатить.

Первая реализация оказалась слишком наивной. Много радости, в процессе разработки, принёс звук (казалось бы, чего уж проще). Это проявлялось во всех имеющихся у меня браузерах, пока я не стал кэшировать созданные объекты Sound в памяти. Не знаю с чем это связано, но где-то посредине игры, звук просто переставал проигрываться, без каких либо сообщений в логе. Но тут пришла другая беда.

Здесь шаманить пришлось долго и дело кончилось костылями. Если звук проигрывался продолжительный, а бот соображал достаточно быстро (как в манкалах, например), то звук его хода просто «проглатывался», что выглядело крайне неприятно. Конечно, это никак не помогло с IE, отказывавшимся (очевидно, по религиозным соображениям) иметь дело как с «wav», так и с «ogg» файлами. При установленном флаге «clonable», я всё таки создаю несколько экземпляров Sound, по одному на каждого игрока (пусть и проигрывают они один и тот же звук). Этот браузер, у меня, работает бесшумно!

Компанию "Хальме" и манкалам составили пара игр шахматных, а также великое множество вариаций Сёги, вычитанных мной в очередном номере "Il fogliaccio degli astratti" и ещё одна простенькая игра от китайских товарищей. В остальном, релиз прошёл без приключений. Ах да, вот ещё что:

Просто небольшой тренажёр кратковременной памяти. Надо открывать одинаковые пары (дама с дамой, король с королём и т.п.) одинакового цвета. За это даются очки и на всё про всё 200 кликов. Поскольку к очкам начисляются бонусы (за чередование красной и чёрной масти, например), можно посоревноваться с друзьями на предмет того, у кого память лучше. Дерзайте!

И всех с Наступающим Новым Годом!

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть