На межі божевілля

    Рендзю — доля простолюдинів,
в шахи грають герої,
Го — гра богів
 
& Nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; Японське прислів'я.
 
Проти дурості самі боги боротися безсилі.
 
& Nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; Айзек Азімов.

 

& Nbsp;
З приходом осені, хочеться дивного. Я задумався про те, якою має бути гра, грати в яку максимально складно? Мене цікавить свого роду аналог Brainfuck -а зі світу настільних ігор. Хочеться, щоб правила гри були максимально простими (Рітмомахія під це визначення явно не підходить). Го — хороша кандидатура на цю роль, але в неї люди грають досить масово (хоч це і непросто). Якщо Го — гра богів, то хочеться побачити гру, грати в яку самим богам було б скрутно. Мощі богів я вирішив протиставити своє безумство. У хорошому сенсі…
 
Безумовно, я не буду першим, хто опублікував пост, присвячений грі & quot; Життя & quot; на Хабре. Тема ця обговорювалася неодноразово. Були традиційні пости & quot; … в 30 рядків & quot ;, були і курйозні пости . Розглядалися інші простору і можливість зміни правил . Шановний 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. Це означає, що в нашу гру можна грати цілеспрямовано. Правда для людей вона все одно не призначена.
 
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.