Как мы Ур делали

       Виктор Пелевин «Generation П»

Дорога в тысячу ли начинается с первого шага.

       Лао Цзы

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

Разумеется, все мои наработки для ZoG оказались здесь совершенно бесполезны. ZRF настолько своеобразный язык, что все его решения и идиомы имеют ценность лишь для ZRF-разработчиков и ни для кого больше (по большей части, все они решают проблемы самого ZRF). По счастью, у Алексея уже был готовый framework, позволивший запрограммировать игровую логику в рекордно короткие сроки. Моей задачей стала сверка игровых правил и разработка принципов работы AI, для этой игры.

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

Напомню правила

В вашем распоряжении 7 бойцов-новичков. Ваша задача — провести их через реку и вернуть домой. Боги помогут вам в пути.

• Если белый цвет выпал на одной из костей, вы можете сделать один шаг.
• Две белых кости означают, что любой из ваших бойцов может переместиться на два шага.
• Если белый цвет выпал на трёх костях, вы можете передвинуть любого из своих бойцов на три шага.
• Три чёрных кости дают право сходить на четыре шага вперёд.

Если ни один из ваших бойцов не может ходить, вы пропускаете ход.

Не все места, через которые вы пройдете одинаковы.

Это врата Иштар — покровительницы воинов.
Остановившись здесь, вы имеете право сделать ещё один ход.

Здесь можно разбить лагерь. В лагере могут находиться не более 4 ваших бойцов.
Пока в лагере есть хотя бы один боец, враг не может войти в это место.

Это святое место. Враг не может напасть на вас здесь, но и вы не можете напасть на него. Не более 4 бойцов (ваших и вашего противника) могут пребывать в этом месте. Помните, первым уходит тот, кто вошёл последним!

Пройдя через это место, бойцы-новички превращаются в воинов-ветеранов. Новичек не может одолеть в бою ветерана, но и ветераны не нападают на новичков.

Никто не может одолеть ветерана, пока он находится в этом месте.
         

Выйдя из лагеря, вы встретитесь с врагом. Если один из ваших бойцов будет убит, вы получите ещё одного новичка.

Семь воинов должны перейти реку и вернуться домой.
Враг не должен вас опередить!

Одной из «изюминок» этого варианта правил является процесс «переворачивания» фишек. Напомню, что фишки переворачиваются для того, чтобы игрок не запутался в направлении их движения. Обычные фишки двигаются по направлению к «малому» блоку, перевернутые — от него. Но «переворачивание» фишек влияет и на игровой процесс. Друг друга могут «рубить» только одинаковые фишки. Обычные фишки не могут «срубать» перевернутые и наоборот. Это весьма разнообразит игровой процесс, но создаёт угрозу «заторов». Например, в процессе отладки ZoG-приложения, у меня возникла следующая ситуация:

Это реальная позиция, возникшая в процессе тестового прогона варианта игры «Simple Ur», в котором поля доски, кроме «розеток», не обладают никакими особыми свойствами. Этот затор совсем не просто разобрать (если бы в резерве не оставалось фишек, игра бы на этом и закончилась). Сколько бы очков не выкинул любой из игроков, ни одна из заблокировавших друг друга фишек не сможет сдвинуться с места. Я думаю, это главная причина, по которой Дмитрий ввёл в игру специальные поля. Поля c2 и f2 (в шахматной нотации) призваны разгрузить «трафик».

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

По правилам Дмитрия, фишка переворачивается не тогда, когда она встаёт на поле превращения (h1 для белых и h3 для чёрных), а проходя через него! В результате, белая фишка не может срубить чёрную на h3, поскольку она должна быть перевёрнута, сделав любой ход с h1. Зато она легко бьёт перевернутую черную фишку на h2, переворачиваясь в процессе хода! Это правило, фактически, делает безопасными поля g1, h1, g3 и h3. Эти поля — идеальное место для «засады».

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

Другой важной особенностью игры являются поля с «розетками», позволяющие, при остановке на них, сделать дополнительный ход. Введение этих полей придаёт игре поистине ураганный характер. Если мы играем группой фишек, не обязательно каждый раз выкидывать «четверки», для того, чтобы «ходить по розеткам». Очень часто удаётся сделать по 2-3 хода, до того, как ход перейдёт к противнику.

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

Если вы думаете, что на этом сюрпризы игры из Ура заканчиваются, вы ошибаетесь! Почему для игры используются три «кости» D2, а не одна D4? Игровые кости типа D4 (с четырьмя гранями) были широко распространены в древнем мире. Почему в игре не была использована одна «кость» вместо трёх? Это не очевидно на первый взгляд, но при использовании такой игровой схемы, выбрасываемые очки не равновероятны. Единички и двойки выпадают в три раза чаще чем тройки и четверки.

Это самым непосредственным образом влияет на игровой процесс. Позиции на удалении 3-4 клеток, от догоняющей фишки противника, гораздо более безопасны чем расстояние в 1-2 клетки. А ведь нас может догонять не одна, а несколько фишек, кроме того, надо учитывать «безопасные» поля. В общем, эта игра совсем не такая простая, какой кажется на первый взгляд.

Отдельно стоит поговорить об игровом AI. Очень важно, чтобы программа играла примерно на одном уровне с человеком. ZoG-овская реализация, например, играет очень слабо. Часто удаётся выиграть у неё «всухую». Играть с ней не очень интересно. Но если программа будет постоянно выигрывать, это также может «отпугнуть» пользователя. Мы постарались соблюсти баланс. В игре имеется четыре уровня сложности. На самом высоком уровне, мне удаётся выиграть примерно в половине партий, с отрывом в 1-2 фишки. Низкий уровень сложности, возможно, будет интересен для «казуальщиков».

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

- Segment 1 вес = 0.5   - level >= 3     - level < 8       - Если есть ходы на "розетки", выбрать из них ход, расположенный дальше от старта     - level >= 8       - Если есть ход на "розетку" не оставляющий g2 пустой, выбрать ход расположенный дальше от старта  - Segment 2 вес = 0.3   - level >= 5     - Если имеются ходы со срубанием перевернутых фишек, выбрать наиболее удаленный от старта     - Если имеются ходы со срубанием обычных фишек, выбрать ближайший к старту   - level = 4     - Если имеются ходы со срубанием, выбрать из них ход, расположенный дальше от старта   - level >= 8     - Если есть возможность хода на g2 и поле пусто, идти туда   - level >= 9     - Если есть возможность занять g1 или h1, ходим туда   - level >= 6     - Если можно вывести фишку с поля, выбрать этот ход   - level >= 5     - Если на первых четырёх клетках нет фишек, выбрать ход со стартовой позиции   - level >= 4     - Если имеются ходы с блокированием, выбрать случайный из них  - Segment 3 вес = 0.2   - level < 8     - level >= 7       - Если имеется ход на поле не под боем, выбрать любой из них     - level >= 2       - Xод фишкой, расположенной дальше от старта     - level = 1       - Ход случайно выбранной фишкой   - level >= 8     - level = 8       - Ход на максимальном расстоянии от старта на поле не под боем, не оставляющий g2 пустой       - Ход на максимальном расстоянии от старта, не оставляющий g2 пустой     - level = 9       - Ход на максимальном расстоянии от старта на поле не под боем, не оставляющий g2 пустой, не с g1 или h1       - Ход на максимальном расстоянии от старта, не оставляющий g2 пустой, не с g1 или h1     - Любой оставшийся ход 

Здесь определено 9 игровых уровней, учитывающих различные аспекты текущей позиции. Фактически, в более сложной игре, наподобие Шахмат, подобные эвристики управляли бы порядком перебора ходов (для просмотра «наилучших» ходов в первую очередь). Наша игра проще. В ней эвристики могут использоваться непосредственно для выбора «лучшего» хода. Как я уже говорил выше, этого вполне достаточно, чтобы программа играла, примерно, на одном уровне с человеком.

Вот она, «Забытая игра Ур», которую мы получили в результате:

В эту игру действительно приятно играть! Она возвращает меня в те времена, когда мы ходили друг к другу в гости не только для того, чтобы выпить и закусить. Да, тогда и трава была зеленее и деревья выше, но дело не в этом. Мы почти перестали играть в Шахматы и Шашки. Мы не собираемся семьями, чтобы сыграть в Бридж. Го и Сёги, для большинства из нас — недостижимая экзотика. Даже старички-доминошники куда-то пропали со двора. Homo Ludens — «Человек играющий» позабыл про настольные игры. Конечно, разработка всего одной игры под iOS и Android этого не исправит, но, возможно, в какой-то мере, поможет вернуть интерес к настольным играм? Я надеюсь на это.