В «пи» цифр не пересчитать,
«е» — бесконечно столь же.
А если их с конца писать, какое будет больше?
Мартин Гарднер «Крестики-нолики»
Для этой статьи, я хотел выбрать другой эпиграф, но счёл его излишне пафосным. Очередной релиз вновь затянулся. За это время, я успел сменить работу! Работа на новом месте отнимает уйму сил, но я продолжаю находить время для своего маленького увлечения. И надо сказать, то, с чем мне приходится сталкиваться в процессе, становится всё сложнее и сложнее. Я расскажу вам об этом. Я хотел начать с другого эпиграфа, но этот тоже неплох.
В этот раз, случились новые манкалы и "игры-переходы" (это Хальма и её родственники). Своего рода гонки, в которых надо занять своими фигурами дом противника, раньше него. Фигуры (и свои и чужие) можно перепрыгивать (как в шашках), но никаких взятий нет. Да что я вам объясняю? Наверняка, многие из вас в детстве играли в "Уголки".
На первый взгляд, игра выглядит простой, но проблемы начались уже на уровне ядра. Помните, я рассказывал о составных ходах? По многим причинам, их удобнее представлять именно составными — в виде единого целого, а не в виде последовательности частичных ходов. Это более удобно для AI, да и с точки зрения дизайна, существуют игры, описание которых в форме составных ходов выглядит гораздо естественнее. Но есть одна проблема.
В шашках, при выполнении составного хода, фигуры убираются с доски (возможно по завершении хода). В Уголках — можно прыгать через свои или противника фигуры до бесконечности. Буквально. И никакие расширения здесь не спасают, поскольку всё зацикливается не доходя до них, в ядре, ещё на этапе генерации списка ходов. Пришлось изменять эту логику, реализуя там опцию (detect-loops), о которой вполне стоило бы подумать заранее.
С целевыми полями тоже не всё ясно. Нельзя направлять все фигуры на одно и то же поле. Первая фигура, которая до него доберётся тут же его и займёт. Идеально было бы определять оптимальные целевые поля для каждой из фигур и двигаться к ним, но это сложно, в вычислительном плане. Кроме того, ситуация на доске с каждым ходом меняется. В общем, я решил не заглядывать далеко вперёд и ограничиться чисто эвристическим алгоритмом.
Dagaz.AI.heuristic = function(ai, design, board, move) {
var t = getTargets(design, board, board.player);
var m = getMove(move);
var r = 1;
if (m !== null) {
if (!design.inZone(0, board.player, m.start)) {
if (_.indexOf(t.first, m.end) >= 0) {
r = 1000 + getDistance(t.first, m.start) - getDistance(t.first, m.end);
}
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. С учётом того, что описания всех состояний игры, в этом формате, записываются в лог, он неплохо помогает в отладке. Вот только пользователю, знать ничего не знающему про лог браузера, пользы от него мало.
Именно этот аспект игры автоматизирует опция "progressive-levels", выполняющая автоматический переход к следующему этапу игры, при победе одного из игроков. А поскольку начальная расстановка фигур от одного этапа к другому различается, она вычисляется модулем common-setup и передаётся в следующий этап игры через URL.
Рука об руку с этой возможностью идёт другой способ, позволяющий разнообразить начальную расстановку фигур. Опция "selector" позволяет кодировать несколько начальных расстановок (и даже конфигураций доски), в рамках одного JS-файла. Обновите начальную страницу Reversi и вы поймёте, что я имею в виду.
Новый подключаемый модуль призван решить проблему. Конструктивно — это обычное дерево, в котором сохраняются все игровые состояния, фигурировавшие когда либо в игровой сессии (а поскольку это дерево, в перспективе, всю историю игры можно будет выгружать в SGF-файл). Пользователь имеет возможность «листать» эти состояния, используя кнопки, появляющиеся вверху экрана.
Это действительно удобно, но из двух стрелочек, занимающих место наверху, можно извлечь ещё больше пользы. Именно этим и занимается опция "advisor-mode". Если пользователь думает дольше заданного времени, бот, с которым он играет, рассчитывает ход за него и помещает новое игровое состояние в «session-manager». Предложенный ход можно принять, просто нажав кнопку «вперёд». А если ход не понравится, то его всегда можно откатить.
Много радости, в процессе разработки, принёс звук (казалось бы, чего уж проще). Первая реализация оказалась слишком наивной. Не знаю с чем это связано, но где-то посредине игры, звук просто переставал проигрываться, без каких либо сообщений в логе. Это проявлялось во всех имеющихся у меня браузерах, пока я не стал кэшировать созданные объекты Sound в памяти. Но тут пришла другая беда.
Если звук проигрывался продолжительный, а бот соображал достаточно быстро (как в манкалах, например), то звук его хода просто «проглатывался», что выглядело крайне неприятно. Здесь шаманить пришлось долго и дело кончилось костылями. При установленном флаге «clonable», я всё таки создаю несколько экземпляров Sound, по одному на каждого игрока (пусть и проигрывают они один и тот же звук). Конечно, это никак не помогло с IE, отказывавшимся (очевидно, по религиозным соображениям) иметь дело как с «wav», так и с «ogg» файлами. Этот браузер, у меня, работает бесшумно!
В остальном, релиз прошёл без приключений. Компанию "Хальме" и манкалам составили пара игр шахматных, а также великое множество вариаций Сёги, вычитанных мной в очередном номере "Il fogliaccio degli astratti" и ещё одна простенькая игра от китайских товарищей. Ах да, вот ещё что:
Просто небольшой тренажёр кратковременной памяти. Надо открывать одинаковые пары (дама с дамой, король с королём и т.п.) одинакового цвета. За это даются очки и на всё про всё 200 кликов. Поскольку к очкам начисляются бонусы (за чередование красной и чёрной масти, например), можно посоревноваться с друзьями на предмет того, у кого память лучше. Дерзайте!
И всех с Наступающим Новым Годом!
Автор: GlukKazan
