On the verge of insanity

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:


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:


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).


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:


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):




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.