On the verge of madness

Renju — the lot of commoners.
play chess heroes,
Go — the game of the gods

Japanese proverb.

Against stupidity the gods themselves are powerless to fight.

Isaac Asimov.


With the advent of autumn and want strange. I thought about what it meant to be a game, a game that is as difficult as possible? I am interested in a kind of analogue of Brainfuck-and from the world of Board games. Want to see the rules of the game are as simple as possible (Rithmomachia under this definition is clearly not appropriate). Go is a good candidate for this role, but her people are playing EN masse (even though it is not easy). If Go — game of gods, you want to see the game, a game in which the gods themselves would be difficult. The power of the gods I decided to oppose his madness. In a good way...

Of course, I'm not the first who published a post dedicated to the game "Jizni" habré. This theme was discussed repeatedly. Was traditional posts "... in 30 lines", was funny posts. Considered other space and the opportunity changes the rules. Dear x0m9k shows how to implement "Life" in Haskell and BarsMonster tied her up Fourier transform. I, on the basis of "Life", decided to implement a Board game (and in this I again the original).

Why have I taken the game "Life"? For two reasons:

the
1. Rules of this game are easy to articulate
the
2. it is Very difficult to predict what will become the initial configuration in just a few moves

This is a good start for a really complex game, but lacks two important aspects: interactivity and the possibility of the game multiple players. The game "Life" is completely interactive. You can build very complicated initial configuration (such as entire production lines for the production of "gliders" or even Turing machine), but once the process began, "the player" plays the role of observer. Change anything. Also, the original concept does not include participation in the game of two (or more) competing started (this topic, albeit in a slightly different plane, was considered in posts PsiBG).

Rules

Problem adding interactivity can be solved in different ways. So abarmot, in his post, offered to give players the opportunity to "throw" the enemy on the field ready shape or even the "bomb" to clear the territory (there were also proposals for "shelling" the enemy's territory moving forms, such as "gliders"). I think it's too hard. Change, introducing interactivity in the game should be minimal.

Give the players the chance, per turn, to add to the field exactly one stone of their color. At any location on the Board, the main thing that it was empty. To add the stones will be subject to all the rules of the game. For example, if it is less than two neighbors, it will die even before the move to the next player (of course, he can take those stones that would have lived in his absence).

The rules of the game "Life", the new gems will be created in the empty fields having exactly three neighbors. The color of the new stone will be determined by the predominance of a particular color in this neighborhood. It is clear that when playing two players, the color of the new stone will be determined uniquely. The stones already on the Board, can also be repainted, depending on the predominance of a particular color in the neighborhood (if the colors equally, change does not happen). The current color of the stone is not taken into account, only the color of its neighbors.
Now, we can formulate the rules of the game:

the

the Game is played on a square Board, initially containing a stable configuration (the game may not start with an empty Board, because, in this case, all players add stones will die immediately after a stroke)

the game involves two players making moves alternately the

• Performing the move, each player must place one stone of their color on any empty square of the Board, and then, all fields of the Board shall be processed in accordance with the following rules
the
• If a blank is adjacent (at a distance of one field of orthogonally or diagonally), exactly three, the next turn it will be a new stone, the color of which is determined by the predominant color among neighboring stones
the
• If the stone less than two neighbours or more than three stones, he dies before the next turn
the
• Stone having two or three neighbors on the next move, acquires color, predominant among neighbors (if the colors equally, the color does not change)
the
• the Game ends when you die all the stones of one colour (the player whose stones are lost — lost)
the
• If you killed all the stones on the Board, draw

I will not "glue" the Board in the top, so boundary effects will occur. All fields outside the Board will always remain empty. I think it will make the game more interesting and unpredictable.

Realization

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

Blank game

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
;

{drop moves-moves
{move} drop-stone
moves}

{pieces
{piece}  S  {drops} drop-moves
pieces}

This code allows the players alternately put their stones on free fields of the Board. Left to implement the rules of "Life". The main difficulty is that changes cannot be made directly on the Board, so they do not affect subsequent calculations. Create an array that will fill in the process of calculating the progress:

Calculation progress

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 rules of the game "Life". The Foundation code is a loop that performs the enumeration of all fields of the Board (due to the fact that the Board in the Axiom displayed in a one-dimensional array, location of each field is determined by a simple numeric index). Based on the result of counting the neighbors of the calc-neighbors decision to change the state of the field. The index you want to change the field is stored in an array new-pos[] and new player[] will remain the color of the created object. To enable removal of the pieces created by the dummy player ?E. I want to note that the players ' names and figures is not so laconic accidentally (why is this important I will discuss later).

Count neighbors

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

ENDIF
my-player W = IF
w-neighbors ++
ENDIF
ENDIF
ENDIF
;

: calc-neighbors ( pos -- )
0 w-neighbors !
0 b-neighbors !
To DUP ['] North calc-direction
To DUP ['] South calc-direction
To DUP ['] West calc-direction
To DUP ['] East calc-direction
To DUP ['] Northeast calc-direction
To DUP ['] Southeast calc-direction
To DUP ['] Northwest calc-direction
To DUP ['] Southwest calc-direction
to
;

Here everything is simple. 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 point — at the time of calculation speed, the state of the Board does not consider the result of a move just made by the player. To resolve this problem, override the system calls the empty? and player (my-empty? and my-player) that performs the field validation on the void and getting color shape located on the field, so to take into account only that the move is made (position of the added stone will be stored in a variable curr-pos).

Vector of changes in the state Board received, left to use:

Change position

: 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 the exec-moves "scrolls" filled previously, the array forming the commands necessary to change the position. The call to drop stone supplemented by the calculation of variations, as well as their application (in that case, if you have something to use). The entire source code is available on GitHub.

Results

Just want to say that this game is staged ZoG the real test of strength. ZoG and this test failed. Because every move can change the state of a large number of fields (up to fields on the Board), the size of the recording speed in the ZSG-notation can be 500 bytes or more (if I didn't care about simply naming players and figures, the amount of recording moves would be much more). Shell ZoG processing moves of this size is clearly not intended and sometimes falls. Fortunately, the implementation of intended for Axiom, which I provided to Greg Schmidt, moves of this size perfectly. Here is a game between two random players:


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

the

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

Wins approximately equally, draws no. More interesting behavior is when specifying a simple evaluation function (similar to the one that was used in Rithmomachia):

Evaluation function

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

Each move was calculated much longer, but have the players to play "smarter" (as a result, a game between two such players has been delayed for almost unlimited time). AutoPlay allows you to check how much better a player plays compared to random:

the

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

You can see that "smart" player surely wins 100 times out of 100. This means that our game can be played purposefully. However for people, it still is not intended.

Article based on information from habrahabr.ru