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

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

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

Для этой статьи, я хотел выбрать другой эпиграф, но счёл его излишне пафосным. Очередной релиз ^[1] вновь затянулся. За это время, я успел сменить работу! Работа на новом месте отнимает уйму сил, но я продолжаю находить время для своего маленького увлечения. И надо сказать, то, с чем мне приходится сталкиваться в процессе, становится всё сложнее и сложнее. Я расскажу вам об этом. Я хотел начать с другого эпиграфа, но этот тоже неплох.

В этот раз, случились новые манкалы ^[2] и "игры-переходы ^[3]" (это Хальма ^[4] и её родственники). Своего рода гонки, в которых надо занять своими фигурами дом противника, раньше него. Фигуры (и свои и чужие) можно перепрыгивать (как в шашках ^[5]), но никаких взятий нет. Да что я вам объясняю? Наверняка, многие из вас в детстве играли в "Уголки ^[6]".

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В остальном, релиз прошёл без приключений. Компанию "Хальме ^[28]" и манкалам ^[2] составили пара игр ^[29] шахматных ^[30], а также ^[31] великое ^[32] множество ^[33] вариаций ^[34] Сёги ^[35], вычитанных мной в очередном номере "Il fogliaccio degli astratti ^[36]" и ещё одна простенькая игра ^[37] от китайских товарищей. Ах да, вот ещё что:

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

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

Автор: GlukKazan

Источник ^[38]