— Давненько не брал я в руки шашек! — говорил Чичиков, подвигая тоже шашку.
— Знаем мы вас, как вы плохо играете!
— сказал Ноздрев, выступая шашкой.
Николай Васильевич Гоголь «Мёртвые души»
Я очень смутно помню диалектику Гегеля, которую нам давали в институте. Обычно, неудержимая сонливость побеждала меня в самом начале лекций. Помню только, что-то говорилось о том, что «история развивается по спирали». Вроде бы это связывалось с принципом «отрицания отрицания». Я не вполне уверен в универсальности этого закона, но в отношении меня он выполняется. Сколько себя помню, я снова и снова делаю одно и тоже. Это мой способ стать лучше. Как бы там ни было, я вновь делаю шашки. И это здорово!
Как я уже неоднократно говорил, шашки — это сложно! Сами шашечные игры возможно и проще Шахмат (хотя сравнивать их не совсем корректно, игры принципиально разные), речь не о том. Реализация шашек гораздо сложнее! Если Шахматы «подложили свинью» с каскадными ходами (рокировка), то в играх шашечного семейства имеется сразу две ещё более сложных «опции»:
- Приоритеты и ...
- Составные ходы!
Приоритеты — это то, что делает шашки особыми! Практически во всех шашечных играх (за очень редким исключением), взятие является обязательным, хочется вам того или нет. На этом построена вся комбинационная игра. Вы можете «поддавать» свои шашки, выстраивая фигуры противника таким образом, чтобы потом забрать их одним ударом (а заодно и провести дамку). Отдать меньше, чтобы забрать больше! Но это только верхушка айсберга!
В этой партии (позиция взята из книги Ю.Барского и Б.Герцензона «Приключения на шашечной доске»), белые не просто жертвуют фигуры, вынуждая противника ходить определённым образом. Они пользуются тем, что чёрные обязаны выполнить все взятия и (в это время) свободно перемещают по доске свои фигуры, подготавливая финальную ловушку. Своими ходами белые создают «роздых» и это превосходная иллюстрация того, насколько красивой может быть позиционная игра в шашках.
К слову сказать
Взятия в шашках не всегда были строго обязательными. И в русских шашках и в английских и даже в ещё более раннем Алькуэрке существовало "правило гнева", позволявшее забрать «зевнувшую» фигуру, не выполнившую взятие. Такое действие не считалось ходом и называлось «взять за фук» (Huffing — в «Английских шашках»). Я ещё застал это правило в раннем детстве, но похоже, история уже вынесла окончательный приговор.
Правило гнева ставит крест на любой комбинационной игре! Опытный шашист предпочтёт лишиться «зевнувшей» фигуры, вместо того чтобы сознательно лезть в ловушку, из за которой он проиграет всю партию. В настоящее время, это правило применяется лишь в некоторых африканских разновидностях игры, традиционно играемых на больших досках и на высокой скорости.
Правило гнева ставит крест на любой комбинационной игре! Опытный шашист предпочтёт лишиться «зевнувшей» фигуры, вместо того чтобы сознательно лезть в ловушку, из за которой он проиграет всю партию. В настоящее время, это правило применяется лишь в некоторых африканских разновидностях игры, традиционно играемых на больших досках и на высокой скорости.
Для меня, приоритеты — это, прежде всего, оптимизация. В самом деле, используя "фирменную магию" Dagaz, я могу запретить выполнение любых ранее сформированных ходов на стадии пост-обработки (именно так я и поступаю в шахматных играх). Более того, я могу изменять сгенерированные ходы и даже добавлять к ним новые. Но всё это ценой памяти и времени (а когда за дело берётся UCT-бот, и то и другое становится весьма критично). Производительность, в моём случае, это не столько интерактивность, сколько «разумность» компьютерного оппонента. Работая быстрее, бот успеет разобрать большее количество позиций!
В случае шашек, генерация ходов сводится к двум возможным ситуациям. Когда взятий нет — «тихих» ходов не так много. Всё меняется когда взятия появляются. Поскольку я генерирую все составные ходы целиком, в дело включается комбинаторика. Например, вот в этом тесте, заурядная позиция с дамкой генерирует 42 возможных хода! И этих ходов было бы гораздо больше, если бы по правилам "Турецких шашек" я не отфильтровывал ходы со взятием максимального количества фигур! Добавление к этому списку ещё и «тихих» ходов, с их последующей фильтрацией в пост-обработке, было бы пустым расточительством.
Здесь-то я и словил первый нетривиальный баг
Gauntlet — очень динамичная и довольно интересная шашечная игра. Разработал её Phillip L.Leduc в 1980 году. Игра ассиметрична. Белым необходимо прорваться (хотя бы одной фигурой) на последнюю горизонталь. Чёрные — стараются не допустить этого. Взятия аналогичны шашечным, но, поскольку все фигуры двигаются только в одном направлении, полноценная реализация составных ходов не требуется (кстати, есть ещё одна, традиционная гавайская игра, со сходным механизмом взятия). Приоритеты, в этой игре, напротив, используются, поскольку взятия обязательны и это важная составляющая игры.
В определённых ситуациях, модель переставала генерировать ходы, что приводило к немедленному останову игры. Было понятно, что ошибка связана с механизмом обработки приоритетов, но я не сразу разобрался, в чём дело. Вначале я даже перенёс логику фильтрации в расширение, отключив приоритеты (как я уже сказал, это всего лишь вопрос производительности). Когда ошибка стала повторяться и в шашках, стало понятно, что с проблемой необходимо разобраться.
Здесь перебираются все фигуры игрока и для каждой из них создаются генераторы, для каждого возможного хода. Генераторы раскладываются в небольшой хэш, в соответствии с приоритетами ходов. Затем хэш просматривается, начиная с наиболее высокого приоритета. Если удаётся сгенерировать хотя бы один ход, генераторы ходов более низких приоритетов не рассматриваются.
Ошибка была в том, что я помечал ход как сгенерированный раньше времени, при первом взятии. В результате, генератор видел взятие, помечал ход, а после этого шёл дальше и натыкался на занятое поле, в том месте, где он должен был разместить фигуру. Это приводило к сбросу почти завершённого хода, но поскольку ход был уже помечен, низкоприоритетные «тихие» ходы попросту отбрасывались. После исправления, AI Gauntlet-а стал играть гораздо лучше. Производительность — это важно!
Gauntlet — очень динамичная и довольно интересная шашечная игра. Разработал её Phillip L.Leduc в 1980 году. Игра ассиметрична. Белым необходимо прорваться (хотя бы одной фигурой) на последнюю горизонталь. Чёрные — стараются не допустить этого. Взятия аналогичны шашечным, но, поскольку все фигуры двигаются только в одном направлении, полноценная реализация составных ходов не требуется (кстати, есть ещё одна, традиционная гавайская игра, со сходным механизмом взятия). Приоритеты, в этой игре, напротив, используются, поскольку взятия обязательны и это важная составляющая игры.
В определённых ситуациях, модель переставала генерировать ходы, что приводило к немедленному останову игры. Было понятно, что ошибка связана с механизмом обработки приоритетов, но я не сразу разобрался, в чём дело. Вначале я даже перенёс логику фильтрации в расширение, отключив приоритеты (как я уже сказал, это всего лишь вопрос производительности). Когда ошибка стала повторяться и в шашках, стало понятно, что с проблемой необходимо разобраться.
Всё дело вот в этом коде
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;
}
Здесь перебираются все фигуры игрока и для каждой из них создаются генераторы, для каждого возможного хода. Генераторы раскладываются в небольшой хэш, в соответствии с приоритетами ходов. Затем хэш просматривается, начиная с наиболее высокого приоритета. Если удаётся сгенерировать хотя бы один ход, генераторы ходов более низких приоритетов не рассматриваются.
Ошибка была в том, что я помечал ход как сгенерированный раньше времени, при первом взятии. В результате, генератор видел взятие, помечал ход, а после этого шёл дальше и натыкался на занятое поле, в том месте, где он должен был разместить фигуру. Это приводило к сбросу почти завершённого хода, но поскольку ход был уже помечен, низкоприоритетные «тихие» ходы попросту отбрасывались. После исправления, AI Gauntlet-а стал играть гораздо лучше. Производительность — это важно!
Думаю, настало время немного рассказать о шашках. Многие из нас знакомы только с русской и, возможно, международной версией этой игры. На самом деле, шашек (даже если рассматривать только традиционные игры) больше. Гораздо больше! Игры очень похожи друг на друга и, зачастую, различаются лишь мелкими деталями.
Картинка кликабельна. Дважды! За начало отсчёта возьмём средневековые "Алькуэрк" и "Лису и гусей". Похоже, что это первые игры, в которых появилось составное взятие. Идея здесь в том, что выполнив «шашечное» взятие, фигура получает право продолжить ход, взяв ещё одну фигуру. И так, до тех пор, пока есть кого брать.
Связи на моей диаграмме довольно условны. Они отражают не историческое развитие (его, в наше время, восстановить уже вряд ли удастся), а скорее взаимосвязи различных вариантов правил игры. Так, например, "Сенегальские шашки" вряд ли являются предтечами "Турецких шашек" и, соответственно, всего «ортогонального» направления. Они более архаичны, это факт, но скорее всего, имело место параллельное развитие от какого-то неизвестного общего предка.
Со стороны другого семейства, произошло одновременно два важных исторических события — отказ от ортогональных перемещений (в пользу диагональных) и использование традиционной шахматной доски (на волне роста популярности Шахмат, это решение самым благотворным образом сказалось на распространении игры). Мы вновь не знаем, где и когда это случилось. Возможно, связующим звеном послужили "Дана" — Филиппинские шашки, сложно сказать.
"Английские шашки" служат корнем «диагонального» семейства, поскольку используют наиболее примитивный вариант правил. Не превращённые фигуры в них не могут двигаться назад (даже выполняя взятие), дамки отличаются только тем, что имеют право двигаться в любую сторону. Это очень неторопливая игра. Итальянцы «повернули» доску на 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 приоритеты пришлось отключить). Впрочем, и здесь я умудрился слегка напахать:
Эта игра гораздо ближе к Алькуэрку. В ней нет «летающих дамок», нет даже превращений! В игре есть «король» и «принц», но эти должности пожизненные. Простые фигуры не могут стать «монаршими особами». Также они не могут угрожать «титулованным» фигурам (в этом отношении, игра похожа на «Итальянские шашки»). Игра довольно неторопливая, но имеет своих почитателей.
Для меня 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;
});
}
Венцом развития этого направления игр я считаю мадагаскарскую "Фанорону". Она уже совсем непохожа на шашки, поскольку использует совершенно иной механизм взятия. Общие черты конечно есть — взятие тоже составное. При этом, Фанорона — единственная известная мне игра, в которой цепочку взятий игрок имеет право прерывать (само взятие по прежнему остаётся обязательным)!
Эта игра стала для меня настоящей проверкой на прочность. Здесь было всё: и ломка модели и переписывание контроллера и новые забавные баги. Но всё хорошо, что хорошо кончается. Итерация завершена и я могу с чистой совестью отправляться в отпуск!
