- PVSM.RU - https://www.pvsm.ru -
Рэндзю — удел простолюдинов,
в шахматы играют герои,
Го — игра богов
Японская пословица.
Против глупости сами боги бороться бессильны.
Айзек Азимов.
С приходом осени, хочется странного. Я задумался о том, какой должна быть игра, играть в которую максимально сложно? Меня интересует своего рода аналог Brainfuck [1]-а из мира настольных игр. Хочется, чтобы правила игры были максимально простыми (Ритмомахия [2] под это определение явно не подходит). Го [3] — хорошая кандидатура на эту роль, но в неё люди играют довольно массово (хоть это и непросто). Если Го — игра богов, то хочется увидеть игру, играть в которую самим богам было бы затруднительно. Мощи богов я решил противопоставить своё безумие. В хорошем смысле…
Безусловно, я не буду первым, кто опубликовал пост, посвященный игре "Жизнь [4]" на Хабре. Тема эта обсуждалась неоднократно. Были традиционные посты "… в 30 строк [5]", были и курьезные посты [6]. Рассматривались иные [7] пространства [8] и возможность изменения [9] правил [10]. Уважаемый x0m9k [11] показал как реализовать «Жизнь» на Хаскеле [12], а BarsMonster [13] связал её с преобразованием Фурье [14]. Я, на основе «Жизни», решил реализовать настольную игру (и в этом я вновь не оригинален [15]).
Почему я взял за основу игру «Жизнь»? По двум причинам:
Это хороший задел для по настоящему сложной игры, но не хватает двух важных моментов: интерактивности и возможности игры несколькими игроками. Игра «Жизнь» совершенно не интерактивна. Можно строить очень сложные начальные конфигурации (например целые производственные линии по производству «глайдеров» или даже машину Тьюринга [16]), но как только процесс начался, «игроку» отводится роль наблюдателя. Изменить ничего нельзя. Также, первоначальной концепцией не предусмотрено участие в игре двух (или более) конкурирующих начал (эта тема, правда в несколько иной плоскости, рассматривалась в постах [17] PsiBG [18]).
Проблему добавления интерактивности можно решать по разному. Так abarmot [19], в своём посте [15], предлагал дать возможность игрокам «кидать» на поле противника готовые формы или даже «бомбы», для расчистки территории (также были предложения по «обстрелу» территорий противника движущимися формами, например «глайдерами»). Я думаю, что это слишком сложно. Изменение, вводящее интерактивность в игру должно быть минимальным.
Дадим возможность игрокам, за ход, добавлять на поле ровно один камень своего цвета. В любое место доски, главное, чтобы оно было пустым. На добавляемые таким образом камни будут распространяться все правила игры. Например, если у него окажется менее двух соседей, он погибнет еще до передачи хода следующему игроку (разумеется, за компанию он может прихватить с собой те камни, которые жили бы в его отсутствие).
По правилам игры «Жизнь», новые камни будут создаваться на пустых полях, имеющих ровно трёх соседей. Цвет нового камня будет определяться преобладанием того или иного цвета в этом соседстве. Понятно, что при игре двух игроков, цвет нового камня всегда будет определяться однозначно. Камни, уже имеющиеся на доске, также могут быть перекрашены, в зависимости от преобладания того или иного цвета в соседстве (если цветов поровну, изменений не происходит). Текущий цвет самого камня в расчет не берётся, важен только цвет его соседей.
Теперь, можно сформулировать правила игры:
Я не буду «склеивать» доску в тор, поэтому граничные эффекты будут проявляться. Все поля за пределами доски всегда будут оставаться пустыми. Думаю, это сделает игру более интересной и непредсказуемой.
Эта игра может послужить хорошей иллюстрацией возможностей 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 [20].
Сразу хочу сказать, что эта игра устроила ZoG [21] настоящую проверку на прочность. И 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
Источник [22]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/forth/69179
Ссылки в тексте:
[1] Brainfuck: https://ru.wikipedia.org/wiki/Brainfuck
[2] Ритмомахия: http://habrahabr.ru/post/234587/
[3] Го: http://ru.wikipedia.org/wiki/%D0%93%D0%BE
[4] Жизнь: https://ru.wikipedia.org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_(%D0%B8%D0%B3%D1%80%D0%B0)
[5] … в 30 строк: http://habrahabr.ru/post/202766/
[6] курьезные посты: http://habrahabr.ru/post/218229/
[7] иные: http://habrahabr.ru/post/168421/
[8] пространства: http://habrahabr.ru/post/154753/
[9] изменения: http://habrahabr.ru/post/228203/
[10] правил: http://habrahabr.ru/post/111686/
[11] x0m9k: http://habrahabr.ru/users/x0m9k/
[12] «Жизнь» на Хаскеле: http://habrahabr.ru/post/225473/
[13] BarsMonster: http://habrahabr.ru/users/barsmonster/
[14] преобразованием Фурье: http://habrahabr.ru/post/180135/
[15] не оригинален: http://habrahabr.ru/post/49713/
[16] машину Тьюринга: http://rendell-attic.org/gol/utm/index.htm
[17] постах: http://habrahabr.ru/post/154015/
[18] PsiBG: http://habrahabr.ru/users/psibg/
[19] abarmot: http://habrahabr.ru/users/abarmot/
[20] GitHub: https://github.com/GlukKazan/ZoG/blob/master/Axiom/GoL/Game-Of-Life.4th
[21] ZoG: http://www.zillions-of-games.com/
[22] Источник: http://habrahabr.ru/post/235483/
Нажмите здесь для печати.