On the verge of madness

Renju - the lot of commoners
heroes play chess
Go - the game of gods

Japanese proverb.

Against stupidity, the gods themselves fight powerless.
')
Isaac Asimov.


With the arrival of autumn, I want a strange one. I thought about what should be the game, which is the most difficult to play? I am 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 ( rhythmology for this definition is clearly not appropriate). Go is a good candidate for this role, but people play it quite massively (although it is not easy). If Go is a game of gods, then you want to see a game that would be difficult for the gods themselves to play. I decided to oppose the relics of the gods. In a good way ...

Certainly, I will not be the first to publish a post dedicated to the game " Life " on Habré. This topic has been discussed repeatedly. There were traditional posts " ... in 30 lines ", there were also funny posts . Considered other spaces and the possibility of changing the rules . Dear x0m9k showed how to implement "Life" on Haskell , and BarsMonster connected it with the Fourier transform . I, on the basis of "Life", decided to implement a board game (and in this I am again not original ).

Why did I base the game "Life"? For two reasons:

1. The rules of this game are easy to articulate.
2. It is very difficult to predict what the initial configuration will become in just a few turns.

This is a good start for a truly challenging game, but two important points are missing: interactivity and the ability of the game to be played by several players. The game "Life" is completely interactive. You can build very complex initial configurations (for example, entire production lines for the production of "gliders" or even a Turing machine ), but once the process has begun, the "player" plays the role of an observer. You can not change anything. 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 enemy's field, for clearing the territory (there were also proposals to "shoot" enemy territories with moving forms, for example, "gliders"). I think it is too difficult. The change introducing interactivity into the game should be minimal.

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

According to the rules of the game "Life", 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 or another color in this neighborhood. It is clear that when playing two players, the color of the new stone will always be determined unequivocally. The stones that are already on the board can also be repainted, depending on the prevalence of one or another color in the neighborhood (if the colors are equal, no changes occur). 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 stable configuration (the game cannot start from an empty board, because, in this case, all stones added by players will die immediately after the turn has been completed)
• The game involves two players making turns in turn.
• When making a move, each player must place exactly one stone of his own color on any free board field, after which all board fields are processed in accordance with the rules listed below.
• If exactly three stones are adjacent to an empty field (at a distance of one field orthogonal or diagonal), a new stone will appear on the next turn, the color of which is determined by the prevailing color among neighboring stones
• If less than two or more than three stones are adjacent to a stone, it dies before the next turn.
• A stone having two or three neighbors, on the next move, acquires a color that prevails 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 have died, 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 possibilities of ForthScript. It is not so complicated that you can get confused in the details of implementation and, at the same time, not too trivial. The basis is the code of placing stones on the board:


This code allows players to alternately place their stones on the free board fields. It remains to implement the rules of "Life." The main difficulty lies in the fact that the changes can not be made directly on the board, so that they do not affect the subsequent calculations. Create an array that will be filled in the process of calculating the course:


Here the rules of the game "Life" are formulated. The basis of the code is a loop that iterates through all the board fields (as a result of the fact that the board in Axiom is mapped to a one-dimensional array, the location of each field is determined by a simple numeric index). Based on the counting result of the calc-neighbors neighbors , a decision is made to change the state of the field. The index of the field to be changed is saved to the array new-pos [] , and the color of the created figure will be saved in new-player [] . To allow the removal of pieces, a dummy player ? E has been created . I want to note that the names of players and figures are not accidentally so concise (why is this 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 of calculating the move, the state of the board does not take into account the result of the move just made by the player. To solve this problem, override the empty? and player (to my-empty? and my-player ), checking the field for emptiness and getting the color of the figure located on the field, so as to take into account the move just made (the position of the added stone will be stored in the variable curr-pos ).

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


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

results

Just want to say that this game gave ZoG a real test of strength. And ZoG failed 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 had not taken care of the laconic naming of players and figures, the size of the record of moves would be much more ). The ZoG shell for processing moves of this size is clearly not designed and sometimes falls. Fortunately, the implementation intended for Axiom programs, which was provided to me by Greg Schmidt, copes with moves of this size. This is how the game of two random players looks like:


The party ends very quickly. AutoPlay also shows nothing unexpected:

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

There are almost equal victories, no draws. Behavior becomes more interesting when setting the simplest evaluation function (similar to the one used in Ritmomachia):




Each turn 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 almost unlimited time). AutoPlay allows you to check how much such a player plays better than randomly:

 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.