On the verge of insanity

  • Tutorial
Renju is the lot of commoners,
heroes play chess,
Guo is a game of the gods

       Japanese proverb.

Against stupidity, the gods themselves are powerless to fight.

       Isaac Asimov.


 
With the advent of autumn, I want something strange. I thought about what should be the game, play which is as difficult as possible? I'm interested in a kind of analogue of Brainfuck from the world of board games. I would like the rules of the game to be as simple as possible ( Rhythmachy clearly does not fit this definition). Go- A good candidate for this role, but people play it in large numbers (although this is not easy). If Go is a game of the gods, then you want to see a game that it would be difficult for the gods to play. I decided to contrast the power of the gods with my madness. In a good way ...

Of course, I will not be the first to post on the game " Life " on Habré. This topic has been discussed repeatedly. There were traditional posts " ... in 30 lines ", there were funny posts . We considered other space and the opportunity to change the rules . Dear x0m9k showed how to implement "Life" on Haskell , and BarsMonsterconnected it with the Fourier transform . Based on Life, I decided to implement a board game (and in this I am not original again ).

Why did I take the Life game as the basis? For two reasons:

  1. The rules of this game are easy to formulate.
  2. It is very difficult to predict what the initial configuration will turn into in just a few moves

This is a good groundwork for a truly complex game, but two important points are missing: interactivity and the ability to play with multiple players. The game "Life" is completely non-interactive. You can build very complex initial configurations (for example, entire production lines for the production of “gliders” or even a Turing machine ), but as soon as the process has begun, the “player” is assigned the role of an observer. Nothing can be changed. Also, the initial concept does not provide for the participation in the game of two (or more) competing principles (this topic, although in a slightly different plane, was considered in the posts of PsiBG ).

rules


The problem of adding interactivity can be solved in different ways. So abarmot , in his post , offered to give players the opportunity to “throw” ready-made forms or even “bombs” on the opponent’s field to clear the territory (there were also proposals for “shelling” the enemy’s territories with moving forms, for example, “gliders”). I think this is too complicated. The change introducing interactivity into the game should be minimal.

Let's give players the opportunity to add exactly one stone of their color to the field per turn. In any place on the board, the main thing is that it is empty. The stones added in this way will be subject to all the rules of the game. For example, if he has less than two neighbors, he will die before the next player is handed the move (of course, for company he can take with him those stones that would live in his absence).

According to the rules of the “Life” game, new stones will be created on empty fields with exactly three neighbors. The color of the new stone will be determined by the predominance of one color or another in this neighborhood. It is clear that when playing two players, the color of the new stone will always be determined uniquely. Stones that are already on the board can also be repainted, depending on the predominance of a particular color in the neighborhood (if the colors are even, there are no changes). The current color of the stone itself is not taken into account, only the color of its neighbors is important.

Now, you can formulate the rules of the game:

  • The game is played on a square board, initially containing some kind of stable configuration (the game cannot start from an empty board, because, in this case, all stones added by the players will die immediately after the move is completed)
  • The game involves two players making moves in turn
  • Performing a move, each player must place exactly one stone of his color on any free field of the board, after which, all the fields of the board are processed in accordance with the rules listed below
  • If there are exactly three stones adjacent to the empty field (at the distance of one field along the orthogonal or diagonal), the next move a new stone will appear on it, the color of which is determined by the prevailing color among the neighboring stones
  • If less than two or more than three stones are adjacent to a stone, it dies before the start of the next turn
  • The stone with two or three neighbors, on the next turn, acquires the color prevailing among the neighbors (if the colors are equal, the color does not change)
  • The game ends when all the stones of one of the colors die (the player whose stones died - lost)
  • If all the stones on the board die, a draw is declared.

I will not “glue” the board into a torus, so the boundary effects will appear. All fields outside the board will always remain empty. I think this will make the game more interesting and unpredictable.

Implementation


This game can serve as a good illustration of the capabilities of ForthScript. It is not so complex that you can get confused in the details of the implementation and, at the same time, is not too trivial. The basis is the code for putting stones on the board:

Game blank
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}


This code allows players to alternately place their stones on the free fields of the board. It remains to implement the rules of "Life". The main difficulty is that changes cannot be made directly on the board so that they do not affect subsequent calculations. Create an array that we will fill in during the course calculation:

Stroke calculation
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
;


Here are the rules of the game "Life". The basis of the code is a cycle that enumerates all the board fields (as a result of the board being mapped to a one-dimensional array in Axiom, the location of each field is determined by a simple numerical index). Based on the result of the calculation of neighbors calc-neighbors , a decision is made to change the state of the field. The index of the field to be changed is saved in the new-pos [] array , and the color of the created figure will be saved in new-player [] . To enable the removal of figures, a fictitious player ? E has been created . I want to note that the names of players and figures are not accidentally so concise (why it is important I will say later).

Neighbor Count
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
;


Everything is simple here. We move from the current position in eight different directions, counting the number of black and white neighbors in b-neighbors and w-neighbors, respectively. There is only one subtle point - at the time the move was calculated, the state of the board does not take into account the result of the move just made by the player. To solve this problem, redefine the empty? and player (on my-empty? and my-player ), which check the field for emptiness and obtain the color of the figure located on the field, so as to take into account the move just made (we will save the position of the added stone in the curr-pos variable ).

The vector of state changes of the board is received, it remains to apply it:

Position change
: 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
;


Here you can see that exec-moves “scrolls” the previously filled array, forming the commands necessary to change the position. The drop-stone call is complemented by the calculation of changes, as well as their application (in the event that there is something to apply). Entire source code is available on GitHub .

results


I want to say right away that this game gave ZoG a real test of strength. And ZoG did not pass this test. Since each move can change the state of a large number of fields (up to all board fields), the size of the move record in ZSG notation can reach 500 or more bytes (if I did not take care of the concise naming of players and pieces, the size of the move record would be much larger ) The ZoG shell for processing moves of this size is clearly not designed and sometimes falls. Fortunately, the implementation intended for Axiom programs, which Greg Schmidt provided me with, works well with moves of this size. Here's what the game of two random players looks like:


The party ends very quickly. AutoPlay also does not show anything unexpected:

Final results:
Player 1 "Random", wins = 54.
Player 2 "Random", wins = 46.
Draws = 0
100 game(s) played

There are approximately equal victories, there are no draws. Behavior becomes more interesting when defining the simplest evaluation function (similar to that used in Rhythmachy):

Evaluation function
: OnEvaluate ( -- score )
	current-player material-balance
;




Each move began to be calculated much longer, but the players began to play “smarter” (as a result, the game between two such players was delayed for an almost unlimited time). AutoPlay allows you to check how much better this player plays compared to a random one:

Final results:
Player 1 "Random", wins = 0.
Player 2 "Eval", wins = 100.
Draws = 0
100 game(s) played

You can see that the “smart” player confidently wins in 100 cases out of 100. This means that our game can be played purposefully. True, for people it is still not intended.

Also popular now: