Programming "for the soul"

Full, pigeon, sin not!
Take away your pennies.
I'm not for money.
I'm after all this for the soul.

Leonid Filatov " The Tale of Fedot-Archer, Daring Fellow "

Just for Fun.
')
Linus torvalds

It's no secret that people enjoy themselves in different ways. One likes to watch TV, others collect quadrocopters. I want to share my recipe. It is unlikely that it will be useful to everyone, but perhaps someone will be interested. I like to write programs (and I think that this is not uncommon, even among professional programmers), but I don’t really like it when this process turns into a dull routine.

To be interesting, programming has to be a kind of “charge for the mind”. A well-known example of such (useful) entertainment is a well-known resource dedicated to improving SQL query writing skills. But not a single programmer alive in SQL! Recently, I have found a great way to improve my Fort skills. Axiom allows you to program on the Forte ad libitum!

My recipe for getting fun with Axiom is simple:

1. Choose any game, with the rules of pozakovyristee, from among those not yet implemented ZoG-community
2. We are trying to bring it to life, using Axiom
3. We enjoy in the process of solving the problems arising in this case.
4. In the event that it is interesting to play the resulting application, Fun produced automatically doubles!

With the implementation of the first paragraph of this plan, I usually help the Internet. This time, I chose Splut! As the object for my inhuman experiments . . Here is its description on the IG Game Center. Without going into the retelling of the rules, I will try to explain how this game attracted me:

• It is played by more than two players (which is, to a certain extent, a challenge for AI algorithms)
• A player's move involves the sequential movement of several (from 1 to 3) pieces.
• The moves leading to the winnings are not straightforward (you can’t just take a piece and eat it, you need to complete a sequence of moves united by one goal)
• The rules of this game are very thoughtful and very original.

Exposure Magic

Let's get down to making fun. Let's start with the simple - with the moves of the Troll. The usual course of the figure is no difficulty. Its implementation is obvious and well suited to explain the concepts of Axiom:


Just want to advise, pay attention to the comments (in parentheses). They will help not to get confused in what is happening on the stack (this is really important in Forte). Also worth paying attention to the spaces. A space, not set, in a bad place, can make you spend a lot of time.

By the code itself, I think everything is clear. We perform the transition in the direction (taken from the stack), using the EXECUTE command, and then we check the boolean result of the transition (if not TRUE , we finish the calculation of the course). Then, we check that the target cell is empty, after which we move the shape. The move command that performs the move takes two values ​​from the stack — the starting point ( from ) and the position we are in after moving ( here ). The add-move command completes the formation of a move.

A little more complicated move, with the movement of the stone:


Here we put two directions on the stack at once - the direction of movement and the opposite to it. The code itself looks more complicated due to stack manipulations, but you can get used to this. It is very important that all “side” actions for capturing or creating shapes should be performed after moving the main shape. It is also important to remember that and in what order is on the stack after each command. A detailed description of the teams themselves can always be found in the Axiom manual.

At one point, however, it is worth staying particularly. The check that the figure in the current cell is a stone is performed by the is-stone predicate ? . Of course, this is not the built-in Axiom function, but ours. Here is how its implementation looks like:


Remember, in the last article , I complained that it was not possible to use the names of objects (in this case, figures) before they were defined? DEFER allows you to cope with this problem. The only bad thing is that this important pattern is not described in the Axiom documentation.

But why do we have four types of stone? Couldn't one do without one? Alas, the rules of Splut! arranged in such a way that we can not do without the "individuality" of stones. I will show later what it is for.

Now the Troll can move and (optionally) carry the Stone along, but it seems that we have forgotten something. The fact is that the only way to natural loss of figures in Splut! due to the fact that the Trolls will throw stones at them! Add the missing functionality, putting the code together:


I will not describe auxiliary functions. Their implementation can be found here . I will stop only on throws. A troll can take a stone with a take-stone move (the implementation of this function is trivial), after which the partial-move-type command enables the move to continue, with the specified type ( continue-type ). Under this type, the only type of move registered is a throw ( drop ) of a stone on the board.

You can not throw anyhow, but in strictly defined places! According to the rules, the stone flies from the Troll in a straight line (vertical or horizontal), flying over the head of the Dwarfs, to an obstacle (Mage, edge of the board or another Troll). The magician knocks down immediately, in other cases, falls to the board. If there was a Gnome in this place - he simply had no luck. This is a difficult rule to implement and it will be more convenient to bring it to life, starting from the other end. We will search for the fields bordering on the obstacle and move away from them, in the opposite direction, along empty cells or cells occupied by Dwarves. If we meet our Troll on the way, it means that you can throw a stone at the place where we started to move.

In addition, the code implements the associated rules. For example, the fact that when you kill a magician, his entire team is removed from the field, and also that after throwing a stone, the move immediately passes to another player. I will not dwell on this in detail.

A slightly different puzzle is the special move of the Gnome. A dwarf, under its own power, can move any number of figures (including Stones) in front of it in a row. In order to store all these figures, we obviously need a stack. For everything else, you can use variables:


Yes, it is more difficult to understand this than in the previous code, but the essence of the action performed is simple. We move in one direction, putting the pieces on the stack, to an empty cell, and then return, recreating them on the board, shifted by one step (since there can be no more than one piece on one cell, you can not take care of deleting the figures - ZoG will remove them independently). Try to understand how this code works, this is a good “mind gymnastics”.

Of course, Mages would not be Mages if they didn’t give us the most trouble. Mages can levitate stones. Any, but ... under certain conditions. For example, you cannot levitate a stone that moved (in any way) on a previous turn. Here the question immediately arises: what is considered the previous move? Unfortunately, the rules do not decipher this moment. In my code, I implemented the clearing of signs of moving stones (this is where individuality is needed, each stone has its own flag) immediately before passing the turn to the first player. Of course, this gives him a significant advantage (he can move any Stones, and the following players are only those that he did not move), but other possible implementations of this rule are also not perfect.


It is easy to make a mistake here, considering that we have implemented everything you need. But not all features are realized! Can the Magician move to the cell occupied by the Stone, if there is an empty cell next to the Stone? The rules of the game say that yes, and the code considers otherwise. In fact, the magician can also "push" the stones in front of him. This is just a type of levitation!


This code is simpler because you don’t have to search for Stones around the field If we want to get on the field occupied by the Stone, then the only Stone that can be levitated is it.

A and B were sitting on the pipe

As I said above, the implementation of AI, for games with more than two players, is associated with some difficulties. Problems begin when determining the condition of the completion of the game. For example, in the recently developed game Yonin Shogi (a variant of Japanese chess for 4 people) developed by me, it would be tempting to define the defeat condition as follows:

 (loss-condition (South North West East) (checkmated King)) 

This record means that the game must be played before the mat to the King of any player. Alas, this approach does not work! I already wrote that the checkmated command carries too much “magic”. In particular, she determines that the King must always leave the check (and never stand under the check). In general, it works ... as long as two players participate in the game. The video illustrates the problem:



As you can see, checkmated works fine for only one of 4 players. For the rest of the players, protection from the shah is not considered a mandatory move! Of course, in the next move, such a king may be eaten, but this fact only aggravates the situation. Anyway, a normal mat in this game will not be able to deliver.

In Splut! the situation is even worse. The game must be played until only one team remains on the board. But ZoG does not allow you to change the order of turns during the game! This means that each retired team must make its move when it comes to its turn (of course, it will fold, since there is no other way to make a move). Also in Splut! Each team makes several moves in a row (1-2 at the beginning of the game and 3 in the middle of the game). In general, it did not come as a surprise to me that the staff AI Axiom did not cope with this game.

Of course, it works, the program makes moves (rather stupid in my opinion), but after one of the players is eliminated, problems begin. When calculating each skip move, the program begins to "think" longer and longer, not fitting into any of the specified time frames. The addition of its evaluation function ( OnEvaluate ) does not fix the situation. In general, I considered this to be a sufficient reason to try to implement my own AI algorithm, since there is such an opportunity in Axiom (looking ahead, I’ll say that it wasn’t very good, but it was worth trying).

I took as a basis the following algorithm known to many from the book “Programming Chess and Other Logic Games” by Evgeny Kornilov:


As is easy to see, in its original form, this algorithm does not suit us at all. We have more than two players, and with the alternation of moves everything is much more complicated. But this algorithm is a good starting point for developing your own version.

Thinking a little, you can understand that in the worst case, the three players who are opposed to the one for which we are counting the move will combine their efforts. In other words, for us this is one hostile player (if they do not unite, so much the worse for them). Another important point is the calculation of the evaluation function. When calculating a move, the evaluation function should always be calculated “from the point of view” of the same player (the one for which the turn is calculated). For hostile players, the score must be taken with the opposite sign (the better for us, the worse for them). Taking these considerations into account, you can rewrite the algorithm as follows:


There are a lot of “magic” of the Fort and Axioms associated with the generation of moves and positions, but, with a certain voltage, the original algorithm is quite visible. To unload the stack, we had to emulate several stacks with variables used in recursive calls. On the stack itself, in the process of computing, there are only two alpha and beta values. In recursive calls ( RECURSE ), they are always transmitted in the same order, but if the calculation is performed for a hostile player, we change their sign, then, change these values ​​in places. We also change the mark of the assessment obtained in assessing the position of a hostile player.

This function is called from the Custom Engine implementation already familiar to us, according to the previous article:


It can be noted that in this code we add a random number from 1 to 5 to the value of the evaluation. This is done so that the program does not always go the same way when the scores of the moves differ slightly.

As usual, the main difficulty lies in the construction of the evaluation function. I will not download the article by listing the current version of it (anyone can always look at the code on GitHub ), I will only say that the following points are now taken into account in it:

• The number of enemy Mages (our main goal is to reduce this value)
• The number of friendly Mages (if this value changes from 1 to 0, the game will end for us)
• The number of enemy Gnomes (it is always pleasant to tie the opponent's hands)
• The number of friendly Dwarfs (not that we could not do without him, but his figure still)
• The penalty for finding a friendly magician on the same line with the Stone (this is really dangerous)
• Bonuses for finding enemy Mages on the same lines with Stones (for the same reason)
• The total number of steps from the trolls to the stones (try to reduce for their own and increase for others)

This is certainly not ideal. Weight values ​​should be chosen more optimally, and the fact itself, for example, finding the Magician in one line with the Stone, in itself, does not mean anything. The cast line can be blocked, for example, by the Troll, and even the stone must also be reached to throw it. Anyway, we wrote the code and can see how it works:



As expected, AI does not shine with intelligence (and works terribly slowly), but at least tries to “pass for clever”. At least you can play it.

Counted - wept

Of course, to assess the quality of AI, you can play with it many times and build an “expert assessment”, but this is not our method. Included with Axiom comes a great utility AutoPlay, allowing you to automate this process. Unfortunately, she still does not know how to work with games designed for more than 2 players, but this is not a problem. Especially for her, we will create a configuration with two players (we will leave 4 pieces of stones):


Also, we need a configuration in which players make random moves:


The results were surprisingly good (although it took an entire night to calculate 100 batches):

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

Why does the program work so long? Let's see how many times, when calculating the course, the evaluation function is called (data of calculation for 5 moves deep):



Yes, there are certainly a lot of 8,000 calls to the evaluation function, but why are there three rows here? I'll try to explain. Here is how we count the number of calls to Eval:


At the output, the following sequence is obtained:


Each group of numbers (separated by an empty line) contains the results of viewing all possible moves of a player from the current position. In the graph presented above, the first row shows the minimum value in the group, the second - the average, the third - the maximum. The difference between the maximum and minimum value is determined by the effectiveness of alpha-beta clipping. Average - determines the performance on which we can count at a given depth of search.

It can be noted that the numbers in the groups generally decrease, but sometimes there are “bursts” breaking the monotonous decrease. Let's try to count their number:



Too much! In some groups, more than 16 violations monotonous decrease.If it were possible to view the moves in a more optimal sequence, it would certainly be possible to improve the performance indicators (and it is possible to achieve a greater depth of enumeration). Unfortunately, the following two points prevent me from doing this:

1. I do not have heuristics that allow to make a preliminary assessment of the "quality" of moves in the game Splut!
2. Even if such heuristics were, a preliminary assessment and sorting of the list of moves in Axiom is associated with certain technical difficulties (and performance costs)

Another method of increasing the depth of the search could be the “in-depth” search of the “forced” moves. Also, it would be nice to cut off repetitive positions ( Zobrist hashing could help a lot with this ).

Let's see how the number of viewed positions changes as the depth of enumeration increases:



Since the average waiting time for the completion of moves of all opponents (with a depth of 5 moves) is about 1 minute, it is obvious that this is the maximum search depth that you can count on during the current implementation of the algorithm (any increase in it will make a person’s game with the program completely uncomfortable).

But let's think about what 5 moves are in the game Splut? This is not even enough to calculate the possible moves of all players! Even in Duel mode. It's like counting the game of Chess just 1 turn ahead! It is difficult to expect special intelligence from such a program.

Of course in Splut! There are far fewer pieces than in Chess, but the moves are more complicated! To win, the program must be able to make long-term plans for many moves ahead. While I do not know how to achieve this, using the Axiom, but probably as it is possible.
I'm working on it.