Dagaz: Шажки

Автор: admin от 10-08-2017, 15:55, посмотрело: 310

Dagaz: Шажки[b] — Давненько не брал я в руки шашек!

        — говорил Чичиков, подвигая тоже шашку.

— Знаем мы вас, как вы плохо играете!

        — сказал Ноздрев, выступая шашкой.

 

Николай Васильевич Гоголь «Мёртвые души» 

[/b]

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



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




  • [b]Приоритеты[/b] и ...

  • [b]Составные ходы![/b]



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





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





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



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





Gauntlet — очень динамичная и довольно интересная шашечная игра. Разработал её Phillip L.Leduc в 1980 году. Игра ассиметрична. Белым необходимо прорваться (хотя бы одной фигурой) на последнюю горизонталь. Чёрные — стараются не допустить этого. Взятия аналогичны шашечным, но, поскольку все фигуры двигаются только в одном направлении, полноценная реализация составных ходов не требуется (кстати, есть ещё одна, традиционная гавайская игра, со сходным механизмом взятия). Приоритеты, в этой игре, напротив, используются, поскольку взятия обязательны и это важная составляющая игры.



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





Здесь перебираются все фигуры игрока и для каждой из них создаются генераторы, для каждого возможного хода. Генераторы раскладываются в небольшой хэш, в соответствии с приоритетами ходов. Затем хэш просматривается, начиная с наиболее высокого приоритета. Если удаётся сгенерировать хотя бы один ход, генераторы ходов более низких приоритетов не рассматриваются.



Ошибка была в том, что я помечал ход как сгенерированный раньше времени, при первом взятии. В результате, генератор видел взятие, помечал ход, а после этого шёл дальше и натыкался на занятое поле, в том месте, где он должен был разместить фигуру. Это приводило к сбросу почти завершённого хода, но поскольку ход был уже помечен, низкоприоритетные «тихие» ходы попросту отбрасывались. После исправления, AI Gauntlet-а стал играть гораздо лучше. Производительность — это важно!



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



Dagaz: Шажки



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



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



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



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





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





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





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



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









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

Источник: Хабрахабр

Категория: Программирование » Веб-разработка

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *