Пользователь
0,0
рейтинг
8 сентября 2014 в 14:30

Разработка → На грани безумия tutorial

Рэндзю — удел простолюдинов,
в шахматы играют герои,
Го — игра богов

       Японская пословица.

Против глупости сами боги бороться бессильны.

       Айзек Азимов.


 
С приходом осени, хочется странного. Я задумался о том, какой должна быть игра, играть в которую максимально сложно? Меня интересует своего рода аналог Brainfuck-а из мира настольных игр. Хочется, чтобы правила игры были максимально простыми (Ритмомахия под это определение явно не подходит). Го — хорошая кандидатура на эту роль, но в неё люди играют довольно массово (хоть это и непросто). Если Го — игра богов, то хочется увидеть игру, играть в которую самим богам было бы затруднительно. Мощи богов я решил противопоставить своё безумие. В хорошем смысле…

Безусловно, я не буду первым, кто опубликовал пост, посвященный игре "Жизнь" на Хабре. Тема эта обсуждалась неоднократно. Были традиционные посты "… в 30 строк", были и курьезные посты. Рассматривались иные пространства и возможность изменения правил. Уважаемый x0m9k показал как реализовать «Жизнь» на Хаскеле, а BarsMonster связал её с преобразованием Фурье. Я, на основе «Жизни», решил реализовать настольную игру (и в этом я вновь не оригинален).

Почему я взял за основу игру «Жизнь»? По двум причинам:

  1. Правила этой игры легко сформулировать
  2. Очень сложно предсказать во что превратится начальная конфигурация всего за несколько ходов

Это хороший задел для по настоящему сложной игры, но не хватает двух важных моментов: интерактивности и возможности игры несколькими игроками. Игра «Жизнь» совершенно не интерактивна. Можно строить очень сложные начальные конфигурации (например целые производственные линии по производству «глайдеров» или даже машину Тьюринга), но как только процесс начался, «игроку» отводится роль наблюдателя. Изменить ничего нельзя. Также, первоначальной концепцией не предусмотрено участие в игре двух (или более) конкурирующих начал (эта тема, правда в несколько иной плоскости, рассматривалась в постах 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
карма
119,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (21)

  • +1
    Обалдеть. Признаюсь, что в сами алгоритмы не вчитался, но сама идея отличная, и наводит на очень умные мысли.

    АПД: Вопрос автору: а можно ли написать такую модификацию, чтобы в среднем случайная стратегия была бы очень сложно одолеваемой?
    • +2
      Алгоритмы достаточно простые (если отвлечься от Forth-а), да и идея в общем то лежит на поверхности.
      Просто как то в голову стрельнуло, дай думаю сделаю (помню температура у меня была под 40)
    • 0
      а можно ли написать такую модификацию, чтобы в среднем случайная стратегия была бы очень сложно одолеваемой?


      На неё ведь всегда можно ответить такой же случайной стратегией. Если нет необходимости в минимаксе (как в Ур-е, например) то всё и будет крутиться вокруг рандома. IMHO, разумеется
      • 0
        >>На неё ведь всегда можно ответить такой же случайной стратегией.

        Это-то да! Но тогда вероятность победы будет 50%! А это только ничья.

        Мотивация тут очень простая: обычно «случайный» игрок играет хуже всех. Ну, в большинстве игр. (за исключением игрока, целенаправленно пытающегося проиграть)

        В реальной же жизни (ну, в некоторых её аспектах) случайная стратегия на самом деле является довольно неплохой. Читал я давеча статью в Форбс, где иллюстрировалось, что биржевая стратегия, составленная по результатам работы высококлассных банковских специалистов, предсказывает реальность всего на 1-3% лучше, чем «случайный прогноз».

        Тем не менее, специалисты стоят своих денег, потому что даже эти 1-3% — это, в отличие от 50%, стабильное доминирование в бесконечных последовательностях игр. То есть, стабильная прибыль.
        • 0
          Затруднюсь ответить. Честно говоря, не думал в этом направлении.
        • 0
          В реальной же жизни (ну, в некоторых её аспектах) случайная стратегия на самом деле является довольно неплохой.

          Это да, есть же даже алгоритм для игры «Го», основанный на отыгрывании случайных партий: UCT. Правда он не просто случайный, а в нем скомбинирован метод Монте-Карло и дерево поиска. Он считает довольно неплохо.
  • +3
    Вот это хардкор! Мое почтение! )

    Годная задачка для AI contest.

    Проблема с длительностью игры, имхо, обусловлена тем, что нет более-менее монотонного инварианта. К примеру, в шахматах кол-во фигур только уменьшается, а в Го (почти всегда) уменьшается свободная территория. В данном случае можно было бы считать накапливающуюся сумму кол-ва всех точек своего цвета за всю историю игры и ввести победный лимит — кто первый достиг — тот и выиграл.
    • 0
      Ну в случае Axiom-ы проблема замедления чисто техническая. Слишком много расчетов на каждую позицию, в результате не может адекватно оценить глубину (даже прогрессбар нормально не отрисовывает). В Ритмомахии, кстати та же история. Но отсутствие монотонного инварианта это безусловно очень неудобно (особенно в долгосрочной перспективе).
  • +3
    Вот пример онлайн версии игры «Жизнь». Можно в любой момент времени добавлять новые элементы (если у вас они есть), довольно интерактивно получилось.
    • 0
      Connect почему-то не проходит. Возможно habr-эффект
    • 0
      Любопытная штука. Народ с Хабра уже поналетел: в чате объединяются во фракции против всех остальных.
      • 0
        Да, из дома зашло нормально
  • 0
    Могу подкинуть идейку локального изменения условий игры игроками.

    Например — взять расширенное соседство (8-мь ближних соседей, и 12 дальних), и учитывать их при расчёте хода. Игрок может локально сказать, что нарождаются не только клетки, имеющие 3-х ближних соседей, но и клетки, имеющие 2-х ближних и от 3-х до 6-ти дальних. И все рождающиеся по новым правилам клетки — цвета игрока. Правила смерти тоже можно подкручивать, разумеется.

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

    В такую игру играть будет ещё труднее. Вот уж действительно — предсказать последствия собственных действий будет нереально
    • 0
      Человеку и в эту играть трудно невозможно, а для машины не очень то много изменится. Правила Конвея хороши своей простотой и сбалансированностью (что не исключает возможного существования других, не менее интересных вариантов правил).
      • 0
        Основная мысль как раз состоит в том, что игра осуществляется не изменением игровой конфигурации (поставить ещё одну фишку), а изменением самих правил игры. Это сложнее, но не до невозможности. Человек такое может освоить, осваивает-же этюдный справочник.
        • 0
          Ага, теперь понял мысль. Да это интересно. И сложно.
          Все равно что сказать, что здесь, например, в течение дня, пи будет равно четырём.
      • 0
        Может быть человеку будет играть не очень трудно. В Жизни не так уж много паттернов, из которых строят свои конструкции. Если их узнавать, играть будет возможно.
        • 0
          Да, знание этих паттернов помогает играть. Я уверенно выигрываю рандомного оппонента, но предсказать влияние того или иного хода все равно очень сложно.
  • +3
    Астрологи объявили неделю Жизни, количество статей о Conway's Life удваивается?

    Идея интересная, но хочется какой-то живой (желательно веб) прототип, в который можно самому попробовать, ибо руки чешутся и в слова о том что «человеку играть невозможно» не верится.

    Также, мне кажется разумным ввести новые правила:

    1) игра начинается с пустого поля, первые Х ходов итерацию жизни пропускаем, просто ставим камни.
    2) в свой ход можно совершить одно из трех действий, вместо одного: поставить камень в пустое место, убрать камень из любого места, перекрасить чужой камень.

    Первое правило увеличит вариабельность «дебюта», а второе добавит стратегии.
    • 0
      С прототипом есть сложности. AutoPlay скачать и запустить можно, но обе графические оболочки увы покупные. Я могу переговорить с Грегом, чтобы пустить его вариант UI в массы бесплатно, но это exe-программа под Windows. Впрочем, кто-то более сведущий в web-программировании чем я вполне может сделать web-реализацию. Правила совсем не сложные (можно добавить свои варианты правил).
  • –3
    уже было
    lifecompetes.com/ — очень похожая игра на описываему в статье: многопользовательская онлайнова веб-игра на основе игры «жизнь»

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