Dagaz: Шажки

— Давненько не брал я в руки шашек!
        — говорил Чичиков, подвигая тоже шашку.
— Знаем мы вас, как вы плохо играете!
        — сказал Ноздрев, выступая шашкой.
 
Николай Васильевич Гоголь «Мёртвые души» 

Я очень смутно помню диалектику Гегеля, которую нам давали в институте. Обычно, неудержимая сонливость побеждала меня в самом начале лекций. Помню только, что-то говорилось о том, что «история развивается по спирали». Вроде бы это связывалось с принципом «отрицания отрицания». Я не вполне уверен в универсальности этого закона, но в отношении меня он выполняется. Сколько себя помню, я снова и снова делаю одно и тоже. Это мой способ стать лучше. Как бы там ни было, я вновь делаю шашки. И это здорово!

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

• Приоритеты и ...
• Составные ходы!

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

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

Для меня, приоритеты — это, прежде всего, оптимизация. В самом деле, используя "фирменную магию" Dagaz, я могу запретить выполнение любых ранее сформированных ходов на стадии пост-обработки (именно так я и поступаю в шахматных играх). Более того, я могу изменять сгенерированные ходы и даже добавлять к ним новые. Но всё это ценой памяти и времени (а когда за дело берётся UCT-бот, и то и другое становится весьма критично). Производительность, в моём случае, это не столько интерактивность, сколько «разумность» компьютерного оппонента. Работая быстрее, бот успеет разобрать большее количество позиций!

В случае шашек, генерация ходов сводится к двум возможным ситуациям. Когда взятий нет — «тихих» ходов не так много. Всё меняется когда взятия появляются. Поскольку я генерирую все составные ходы целиком, в дело включается комбинаторика. Например, вот в этом тесте, заурядная позиция с дамкой генерирует 42 возможных хода! И этих ходов было бы гораздо больше, если бы по правилам "Турецких шашек" я не отфильтровывал ходы со взятием максимального количества фигур! Добавление к этому списку ещё и «тихих» ходов, с их последующей фильтрацией в пост-обработке, было бы пустым расточительством.

var priors = [];
_.chain(_.keys(this.pieces))
 .filter(function(pos)  
    { return Dagaz.Model.sharedPieces || 
             Dagaz.Model.isFriend(this.pieces[pos], this.player); 
    }, this)
 .each(function(pos) {
     var piece = this.pieces[pos];
     _.chain(design.pieces[piece.type])
      .filter(function(move) { return (move.type == 0); })
      .each(function(move) {
          var g = Dagaz.Model.createGen(move.template, move.params, this.game.design);
          g.init(this, pos);
          addPrior(priors, move.mode, g);
      }, this);
  }, this);
...
for (var i = 0; i <= design.modes.length; i++) {
     var f = false;
     if (!_.isUndefined(priors[i])) {
         while (priors[i].length > 0) {
            var g = priors[i].pop();
            g.generate();
            if (g.completed && !g.move.isPass()) {
                if (cont && (g.moveType == 0)) {
                    CompleteMove(this, g);
                }
                f = true;
            }
         }
     }
     if (f) break;
     if (i >= design.modes.length) break;
}

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

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

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

Со стороны другого семейства, произошло одновременно два важных исторических события — отказ от ортогональных перемещений (в пользу диагональных) и использование традиционной шахматной доски (на волне роста популярности Шахмат, это решение самым благотворным образом сказалось на распространении игры). Мы вновь не знаем, где и когда это случилось. Возможно, связующим звеном послужили "Дана" — Филиппинские шашки, сложно сказать.

"Английские шашки" служат корнем «диагонального» семейства, поскольку используют наиболее примитивный вариант правил. Не превращённые фигуры в них не могут двигаться назад (даже выполняя взятие), дамки отличаются только тем, что имеют право двигаться в любую сторону. Это очень неторопливая игра. Итальянцы «повернули» доску на 90 градусов и сделали дамки неприкосновенными (простые фигуры не могут «рубить» их). Кстати, имеется интересная разновидность игры, развивающая эту идею:

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

Аргентинский и тайский варианты игры ограничивают мобильность дамок, разрешая им останавливаться лишь на первом поле за взятой фигурой (если оно свободно, разумеется). Кстати, точно таким же образом "Греческие шашки" ограничивают подвижность «турецких дамок». Далее идут уже привычные нам варианты игры, разрешающие «взятие назад» простыми фигурами.

ZrfMoveGenerator.prototype.isCaptured = function(pos, level) {
  if (this.parent) {
      return this.parent.isCaptured(pos, level);
  }
  if (_.isUndefined(this.captured)) {
      this.captured = [];
  }
  if (this.captured[pos] && (this.captured[pos] < level)) return true;
  _.each(Dagaz.Model.getDesign().allPositions(), function(p) {
      if (this.captured[p] && (this.captured[p] >= level)) {
          delete this.captured[p];
      }
  }, this);
  this.captured[pos] = level;
  return false;
}

ZrfMoveGenerator.prototype.capturePiece = function(pos) {
  if (Dagaz.Model.deferredStrike) {
      if (this.isCaptured(pos, this.level)) return false;
  }
  this.move.capturePiece(pos, this.level);
  if (!Dagaz.Model.deferredStrike) {
      this.setPiece(pos, null);
  }
  return true;
}

_.chain(move.actions)
 .filter(function(action) {
      return (action[0] !== null) && (action[1] === null);
  })
 .each(function(action) {
      action[3] = mx;
  });

var actions = [];
_.each(move.actions, function(action) {
    var pn = action[3];
    if ((action[0] !== null) && (action[1] === null)) {
        pn = mx;
    }
    actions.push([ action[0], action[1], action[2], pn ]);
});
move.actions = actions;

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

Тем временем, Алькуэрк тоже эволюционировал. Развитие происходило параллельно развитию шашек и почерпнуло из последних такие идеи как ход простых фигур «только вперёд», «летающие дамки» и даже правило «турецкого удара». Получились вполне самобытные и весьма оригинальные игры "Замма" и "Харбага", могу порекомендовать их тем, кто устал от шахматной доски.

Финны сохранили для нас ещё одну древнюю игру

Эта игра гораздо ближе к Алькуэрку. В ней нет «летающих дамок», нет даже превращений! В игре есть «король» и «принц», но эти должности пожизненные. Простые фигуры не могут стать «монаршими особами». Также они не могут угрожать «титулованным» фигурам (в этом отношении, игра похожа на «Итальянские шашки»). Игра довольно неторопливая, но имеет своих почитателей.

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

  if (_.chain(board.moves)
       .filter(function(move) {
           return _.isUndefined(move.failed);
        })
       .filter(function(move) {
           return move.actions.length > 1;
        })
       .filter(function(move) {
           ...
-        }).value().length > 1) {
+        }).value().length >= 1) {
        _.chain(board.moves)
         .filter(function(move) {
             return move.actions.length == 1;
          })
         .each(function(move) {
             move.failed = true;
          });
  }

Венцом развития этого направления игр я считаю мадагаскарскую "Фанорону". Она уже совсем непохожа на шашки, поскольку использует совершенно иной механизм взятия. Общие черты конечно есть — взятие тоже составное. При этом, Фанорона — единственная известная мне игра, в которой цепочку взятий игрок имеет право прерывать (само взятие по прежнему остаётся обязательным)!

Эта игра стала для меня настоящей проверкой на прочность. Здесь было всё: и ломка модели и переписывание контроллера и новые забавные баги. Но всё хорошо, что хорошо кончается. Итерация завершена и я могу с чистой совестью отправляться в отпуск!

Автор: GlukKazan

Источник