Рэндзю — удел простолюдинов,
в шахматы играют герои,
Го — игра богов
Японская пословица.
Против глупости сами боги бороться бессильны.
Айзек Азимов.
С приходом осени, хочется странного. Я задумался о том, какой должна быть игра, играть в которую максимально сложно? Меня интересует своего рода аналог Brainfuck-а из мира настольных игр. Хочется, чтобы правила игры были максимально простыми (Ритмомахия под это определение явно не подходит). Го — хорошая кандидатура на эту роль, но в неё люди играют довольно массово (хоть это и непросто). Если Го — игра богов, то хочется увидеть игру, играть в которую самим богам было бы затруднительно. Мощи богов я решил противопоставить своё безумие. В хорошем смысле…
Безусловно, я не буду первым, кто опубликовал пост, посвященный игре "Жизнь" на Хабре. Тема эта обсуждалась неоднократно. Были традиционные посты "… в 30 строк", были и курьезные посты. Рассматривались иные пространства и возможность изменения правил. Уважаемый x0m9k показал как реализовать «Жизнь» на Хаскеле, а BarsMonster связал её с преобразованием Фурье. Я, на основе «Жизни», решил реализовать настольную игру (и в этом я вновь не оригинален).
Почему я взял за основу игру «Жизнь»? По двум причинам:
- Правила этой игры легко сформулировать
- Очень сложно предсказать во что превратится начальная конфигурация всего за несколько ходов
Это хороший задел для по настоящему сложной игры, но не хватает двух важных моментов: интерактивности и возможности игры несколькими игроками. Игра «Жизнь» совершенно не интерактивна. Можно строить очень сложные начальные конфигурации (например целые производственные линии по производству «глайдеров» или даже машину Тьюринга), но как только процесс начался, «игроку» отводится роль наблюдателя. Изменить ничего нельзя. Также, первоначальной концепцией не предусмотрено участие в игре двух (или более) конкурирующих начал (эта тема, правда в несколько иной плоскости, рассматривалась в постах PsiBG).
Правила
Проблему добавления интерактивности можно решать по разному. Так abarmot, в своём посте, предлагал дать возможность игрокам «кидать» на поле противника готовые формы или даже «бомбы», для расчистки территории (также были предложения по «обстрелу» территорий противника движущимися формами, например «глайдерами»). Я думаю, что это слишком сложно. Изменение, вводящее интерактивность в игру должно быть минимальным.
Дадим возможность игрокам, за ход, добавлять на поле ровно один камень своего цвета. В любое место доски, главное, чтобы оно было пустым. На добавляемые таким образом камни будут распространяться все правила игры. Например, если у него окажется менее двух соседей, он погибнет еще до передачи хода следующему игроку (разумеется, за компанию он может прихватить с собой те камни, которые жили бы в его отсутствие).
По правилам игры «Жизнь», новые камни будут создаваться на пустых полях, имеющих ровно трёх соседей. Цвет нового камня будет определяться преобладанием того или иного цвета в этом соседстве. Понятно, что при игре двух игроков, цвет нового камня всегда будет определяться однозначно. Камни, уже имеющиеся на доске, также могут быть перекрашены, в зависимости от преобладания того или иного цвета в соседстве (если цветов поровну, изменений не происходит). Текущий цвет самого камня в расчет не берётся, важен только цвет его соседей.
Теперь, можно сформулировать правила игры:
- Игра ведётся на квадратной доске, первоначально содержащей некую стабильную конфигурацию (игра не может начинаться с пустой доски, поскольку, в этом случае, все добавляемые игроками камни будут погибать сразу же после выполнения хода)
- В игре участвуют два игрока, совершающие ходы поочерёдно
- Выполняя ход, каждый игрок должен разместить ровно один камень своего цвета на любом свободном поле доски, после чего, все поля доски обрабатываются в соответствии с перечисленными ниже правилами
- Если с пустым полем соседствует (на расстоянии одного поля по ортогонали или диагонали) ровно три камня, на следующем ходу на ней возникнет новый камень, цвет которого определяется преобладающим цветом среди соседствующих камней
- Если с камнем соседствует менее двух или более трёх камней, он погибает до начала следующего хода
- Камень имеющий двух или трёх соседей, на следующем ходу, приобретает цвет, преобладающий среди соседей (если цветов поровну, цвет не меняется)
- Игра заканчивается когда погибают все камни одного из цветов (тот игрок, камни которого погибли — проиграл)
- Если погибли все камни на доске, объявляется ничья
Я не буду «склеивать» доску в тор, поэтому граничные эффекты будут проявляться. Все поля за пределами доски всегда будут оставаться пустыми. Думаю, это сделает игру более интересной и непредсказуемой.
Реализация
Эта игра может послужить хорошей иллюстрацией возможностей ForthScript. Она не настолько сложная, чтобы можно было запутаться в деталях реализации и, в то же время, не слишком тривиальна. Основой является код выставления камней на доску:
19 CONSTANT R
19 CONSTANT C
{board
R C {grid}
board}
{directions
-1 0 {direction} North
1 0 {direction} South
0 1 {direction} East
0 -1 {direction} West
-1 1 {direction} Northeast
1 1 {direction} Southeast
-1 -1 {direction} Northwest
1 -1 {direction} Southwest
directions}
{players
{player} B
{player} W
players}
{turn-order
{turn} B
{turn} W
turn-order}
: drop-stone ( -- )
empty? IF
drop
add-move
ENDIF
;
{moves drop-moves
{move} drop-stone
moves}
{pieces
{piece} S {drops} drop-moves
pieces}
Этот код позволяет игрокам поочередно выставлять свои камни на свободные поля доски. Осталось реализовать правила «Жизни». Главная сложность заключается в том, что изменения нельзя производить непосредственно на доске, чтобы они не влияли на последующие расчеты. Создадим массив, который будем заполнять в процессе расчета хода:
R C * CONSTANT SIZE
VARIABLE new-cnt
SIZE [] new-pos[]
SIZE [] new-player[]
{players
{neutral} ?E
{player} B
{player} W
players}
: gen-move ( pos player -- )
new-cnt @ SIZE < IF
new-cnt @ new-player[] !
new-cnt @ new-pos[] !
new-cnt ++
ELSE
2DROP
ENDIF
;
: life-tick ( -- )
here
SIZE
BEGIN
1-
DUP calc-neighbors
w-neighbors @ b-neighbors @ +
my-empty? IF
DUP 3 = IF
here
w-neighbors @ b-neighbors @ > IF W ELSE B ENDIF
gen-move
ENDIF
ELSE
DUP 2 < OVER 3 > OR IF
here ?E gen-move
ELSE
w-neighbors @ b-neighbors @ > IF
my-player W <> IF
here W gen-move
ENDIF
ENDIF
b-neighbors @ w-neighbors @ > IF
my-player B <> IF
here B gen-move
ENDIF
ENDIF
ENDIF
ENDIF
DROP
DUP 0=
UNTIL
DROP
to
;
Здесь сформулированы правила игры «Жизнь». Основой кода является цикл, выполняющий перебор всех полей доски (в результате того, что доска в Axiom отображается на одномерный массив, расположение каждого поля определяется простым числовым индексом). На основе результата подсчёта соседей calc-neighbors принимается решение об изменении состояния поля. Индекс подлежащего изменению поля сохраняется в массив new-pos[], а в new-player[] будет сохраняться цвет создаваемой фигуры. Для обеспечения возможности удаления фигур, создан фиктивный игрок ?E. Хочу отметить, что имена игроков и фигур не случайно столь лаконичны (почему это важно я скажу позже).
VARIABLE w-neighbors
VARIABLE b-neighbors
VARIABLE curr-pos
: my-empty? ( -- ? )
here curr-pos @ = IF
FALSE
ELSE
empty?
ENDIF
;
: my-player ( -- player )
here curr-pos @ = IF
current-player
ELSE
player
ENDIF
;
: calc-direction ( 'dir -- )
EXECUTE IF
my-empty? NOT IF
my-player B = IF
b-neighbors ++
ENDIF
my-player W = IF
w-neighbors ++
ENDIF
ENDIF
ENDIF
;
: calc-neighbors ( pos -- )
0 w-neighbors !
0 b-neighbors !
DUP to ['] North calc-direction
DUP to ['] South calc-direction
DUP to ['] West calc-direction
DUP to ['] East calc-direction
DUP to ['] Northeast calc-direction
DUP to ['] Southeast calc-direction
DUP to ['] Northwest calc-direction
DUP to ['] Southwest calc-direction
to
;
Здесь всё просто. Двигаемся от текущей позиции в восьми различных направлениях, подсчитывая количество чёрных и белых соседей в b-neighbors и w-neighbors соответственно. Есть только один тонкий момент — на момент расчёта хода, состояние доски не учитывает результат хода, только что сделанного игроком. Чтобы решить эту проблему, переопределим системные вызовы empty? и player (на my-empty? и my-player), выполняющие проверку поля на пустоту и получение цвета фигуры расположенной на поле, таким образом, чтобы учитывать только что сделанный ход (позицию добавляемого камня будем сохранять в переменной curr-pos).
Вектор изменений состояния доски получен, осталось его применить:
: exec-moves ( -- )
BEGIN
new-cnt --
new-cnt @ new-player[] @
DUP ?E = IF
DROP
new-cnt @ new-pos[] @
capture-at
ELSE
STONE
new-cnt @ new-pos[] @
create-player-piece-type-at
ENDIF
new-cnt @ 0=
UNTIL
;
: drop-stone ( -- )
empty? IF
SIZE curr-pos !
here calc-neighbors
w-neighbors @ b-neighbors @ + 0> IF
0 new-cnt !
here curr-pos !
drop
life-tick
new-cnt @ 0> IF
exec-moves
ENDIF
add-move
ENDIF
ENDIF
;
Здесь можно видеть, что exec-moves «прокручивает» заполненный ранее массив, формируя команды, необходимые для изменения позиции. Вызов drop-stone дополнен расчётом изменений, а также их применением (в том случае, если есть что применять). Целиком исходный код доступен на GitHub.
Результаты
Сразу хочу сказать, что эта игра устроила ZoG настоящую проверку на прочность. И ZoG эту проверку не выдержал. Поскольку каждый ход может изменять состояние большого количества полей (вплоть до всех полей доски), размер записи хода в ZSG-нотации может достигать 500 и более байт (если бы я не позаботился о лаконичном именовании игроков и фигур, размер записи ходов был бы гораздо больше). Оболочка ZoG на обработку ходов такого размера явно не рассчитана и временами падает. К счастью, реализация, предназначенная для Axiom-программ, которую мне предоставил Greg Schmidt, с ходами такого размера прекрасно справляется. Вот как выглядит игра двух рандомных игроков:
Партия заканчивается очень быстро. AutoPlay также не показывает ничего неожиданного:
Final results:
Player 1 "Random", wins = 54.
Player 2 "Random", wins = 46.
Draws = 0
100 game(s) played
Побед приблизительно поровну, ничьих нет. Более интересным поведение становится при задании простейшей оценочной функции (аналогичной той, что была использована в Ритмомахии):
: OnEvaluate ( -- score )
current-player material-balance
;
Каждый ход стал рассчитываться гораздо дольше, но и игроки стали играть «умнее» (в результате чего, партия между двумя такими игроками затягивается на практически неограниченное время). AutoPlay позволяет проверить насколько лучше играет такой игрок по сравнению с рандомным:
Final results:
Player 1 "Random", wins = 0.
Player 2 "Eval", wins = 100.
Draws = 0
100 game(s) played
Можно видеть, что «умный» игрок уверенно выигрывает в 100 случаях из 100. Это означает, что в нашу игру можно играть целенаправленно. Правда для людей она всё равно не предназначена.
Автор: GlukKazan
