На грани безумия
Рэндзю — удел простолюдинов, в шахматы играют герои, Го — игра богов Японская пословица.
Против глупости сами боги бороться бессильны.
Айзек Азимов.
С приходом осени, хочется странного. Я задумался о том, какой должна быть игра, играть в которую максимально сложно? Меня интересует своего рода аналог 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, с ходами такого размера прекрасно справляется. Вот как выглядит игра двух рандомных игроков:[embedded content]Партия заканчивается очень быстро. 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 ; [embedded content]Каждый ход стал рассчитываться гораздо дольше, но и игроки стали играть «умнее» (в результате чего, партия между двумя такими игроками затягивается на практически неограниченное время). AutoPlay позволяет проверить насколько лучше играет такой игрок по сравнению с рандомным:
Final results: Player 1 «Random», wins = 0. Player 2 «Eval», wins = 100. Draws = 0 100 game (s) played Можно видеть, что «умный» игрок уверенно выигрывает в 100 случаях из 100. Это означает, что в нашу игру можно играть целенаправленно. Правда для людей она всё равно не предназначена.
