Programming "for the soul"

Full, dove, do not sin!
Take away your pennies.
I’m not for the money.
I’m for the soul.

Leonid Filatov " The Tale of Fedot the Sagittarius, a daring young man "

Just for Fun.

Linus Torvalds

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

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

My recipe for getting Fun with Axiom is simple:

1. We choose any game with rules that are more complete, from among those not yet implemented by the ZoG community
2. We are trying to bring it to life using Axiom
3. We enjoy in the process of solving problems arising from this
4. In case the application is fun to play, the generated Fun will automatically double!

With the implementation of the first paragraph of this plan, the Internet usually helps me. This time, I chose Splut as an object for my inhuman experiments . . Here is his description on the IG Game Center. Without going into a retelling of the rules, I will try to explain what attracted me to this game:

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

Revealing Magic

Let's start developing Fun. Let's start with a simple one - with the moves of the Troll. The usual move of the figure does not present any difficulties. Its implementation is obvious and well suited to explain Axiom concepts:


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

According to the code itself, I think everything is clear. We perform the transition in the direction (taken from the stack) using the EXECUTE command , after which we check the Boolean result of the transition (if not TRUE , complete the calculation of the move). Then, we check that the target cell is empty, after which we move the figure. The move command that performs the move takes two values ​​from the stack - the start point of the move ( from) and the position we are in after moving ( here ). The add-move command completes the formation of the move.

A slightly 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. The code itself looks more complicated due to manipulations with the stack, but you can get used to it. It is very important that all “side” actions for capturing or creating figures must be performed after moving the main figure. It is also important to remember what and in what order lies on the stack after each command. A detailed description of the commands themselves can always be found in the Axiom manual.

At one point, however, it is worth stopping especially. Does the is-stone predicate verify that the shape in the current cell is Stone ? . Of course, this is not a built-in Axiom function, but ours. Here's what 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, shapes) before defining them? DEFER allows you to cope with this problem. The only bad part is that this important pattern is not described in the Axiom documentation.

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

Now the Troll can move and (optionally) drag the Stone behind it, but it seems we forgot something. The fact is that the only way to naturally decrease shapes in Splut! due to the fact that trolls will throw stones at them! Add the missing functionality, collecting the code together:


I will not describe helper functions. Their implementation can be seen here . I will dwell only on the throws. The troll can take the stone with the take-stone move (the implementation of this function is trivial), after which the partial-move-type command enables the continuation of the move, with the specified type ( continue-type ). Under this type, the only type of move registered is the drop of the Stone onto the board.

You can throw not anyhow, but in strictly defined places! According to the rules, a stone flies from the Troll in a straight line (vertically or horizontally), flying above the head of the Dwarves, to an obstacle (Mage, edge of the board or another Troll). The magician knocks right away, in other cases, falls on the board. If the Dwarf ended up in this place, he was just out of 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 look for the fields bordering the obstacle and move away from them, in the opposite direction, along empty cells or cells occupied by the Dwarves. If we meet our Troll along the road, it means you can throw a stone at the place from which we started the movement.

In addition, related rules are implemented in the code. For example, the fact that when the Mage is killed, his entire team is removed from the field, as well as the fact that after a stone is thrown, the move immediately passes to another player. I will not dwell on this in detail.

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


Да, разобраться в этом сложнее, чем в предыдущем коде, но суть выполняемого действия проста. Мы двигаемся в одном направлении, складывая фигуры в стек, до пустой клетки, а потом возвращаемся, воссоздавая их на доске, сдвинутыми на один шаг (поскольку на одной клетке не может находиться более одной фигуры, об удалении фигур можно не заботиться — ZoG удалит их самостоятельно). Попробуйте понять, как работает этот код, это неплохая «гимнастика для ума».

Of course, the Mages would not be Mages if they did not cause us maximum trouble. Mages can levitate stones. Any, but ... under certain conditions. For example, you cannot levitate a stone that was moving (in any way) on the previous move. Here the question immediately arises: what to consider as the previous move? Unfortunately, the rules do not decipher this moment. In my code, I implemented the cleaning of signs of moving stones (it is here that you need individuality, each stone has its own flag) immediately before passing the move to the first player. Of course, this gives him a serious advantage (he can move any Stones, and the following players 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 we need. But not all possibilities are realized! Can the Mage move to the cell occupied by the Stone if there is an empty cell next to the Stone? The rules of the game say yes, but the code considers otherwise. In fact, the Mage can also “push” the Stones in front of him. This is just a kind of levitation!


This code is simpler because you do not have to search for Stones all over the field. If we want to stand on the field occupied by the Stone, then the only Stone that can be levitated is this.

A and B were sitting on a pipe

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

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

This entry means that the game must be played up to checkmate to the King of any of the players. 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 shah (and never stand under the shah). All in all, 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 the 4 players. For other players, the defense against the check is not considered a mandatory move! Of course, on the next move, such a king may be eaten, but this fact only exacerbates the situation. Like it or not, you won’t be able to put a normal mat in such a game.

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 changing the order of moves during the game! This means that each outgoing team must make its move when it comes to it (of course, it will pass, 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 was not a surprise for me that the regular AI Axiom could not cope with this game.

It certainly works, the program makes moves (rather stupid in my opinion), but, after one of the players is eliminated, problems begin. When calculating each missed move, the program begins to “think” longer and longer, without falling into any of the specified time frames. Redefining your evaluation function ( OnEvaluate ) does not correct the situation. In general, I considered this a good reason to try to implement my own AI algorithm, fortunately there is such an opportunity in Axiom (looking ahead, I’ll say that it turned out not very cool, but it was worth trying).

As a basis, I took the following, well-known to many, algorithm from the book by Evgeni Kornilov “Programming Chess and Other Logic Games”:


As you can easily see, in its original form, this algorithm is completely unsuitable for us. We have more than two players, and alternating moves is much more complicated. But this algorithm is a good starting point for developing your own version.

If you think a little, you can understand that in the worst case scenario, the three players who oppose the one for whom we count the move will join forces. In other words, for us this is onehostile player (if they do not unite - so much the worse for them). Another important point is the calculation of the estimated function. When calculating a move, the evaluation function should always be calculated “from the point of view” of the same player (the one for whom the move is calculated). For hostile players, the score should be taken with the opposite sign (the better we are, the worse they feel). Taking these considerations into account, we can rewrite the algorithm as follows:


There is a lot of “magic” of the Fort and Axiom associated with the generation of moves and positions, but, with some tension, 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, during the calculation process, there are only two values alpha and beta . 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, after which we change these values. We also change the mark of the evaluation obtained when evaluating a position by an enemy player.

This function is called from the implementation of Custom Engine, already familiar to us, in the last article:


You may notice that in this code we add a random number from 1 to 5 to the evaluation value. This is done so that the program does not always go the same in cases where the evaluation of the moves differ slightly.

As usual, the main difficulty lies in constructing an evaluation function. I will not download the article by listing its current version (those who wish can always see the code on GitHub ), I can only say that it currently takes into account the following points:

• 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 Dwarves (it is always nice to tie the hands of the enemy)
• The number of friendly Dwarves (not that we could not do without it, but our own figure anyway)
• The penalty for finding a friendly Mage on a 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 Trolls to Stones (we try to reduce for our own and increase for others)

This is certainly not an ideal option. Weight values ​​should be selected more optimally, and the fact itself, for example, the Magician being on the same line with the Stone, by itself, does not mean anything. The cast line can be blocked, for example, by the Troll, and one must still get to the stone in order to throw it. One way or another, we wrote the code and can see how it works:



As expected, AI does not sparkle with intelligence (and works terribly slowly), but at least tries to "pass for the smart." At least this can already be played.

Counted - wept

Of course, in order to evaluate 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 wonderful AutoPlay utility that allows 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’ll create a configuration with two players (we’ll leave 4 stones):


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


The results were, surprisingly, not bad (although it took a whole night to calculate 100 games):

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

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



Yes, 8000 calls of the evaluation function are certainly many, but why are there three rows? I’ll try to explain. Here's how we count the number of Eval calls:


At the output, the following sequence is obtained:


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

You may notice that the numbers in the groups are mainly decreasing, but sometimes “bursts” violating the monotonous decrease. Let's try to calculate their number:



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

1. I have no heuristics that allow me to make a preliminary assessment of the “quality” of moves in the game Splut!
2. Even if there were such heuristics, the preliminary evaluation and sorting of the move list in Axiom is associated with certain technical difficulties (and performance overheads)

Другим методом увеличения глубины перебора мог бы послужить «углубленный» перебор «форсированных» ходов. Также, было бы неплохо отсекать повторяющиеся позиции (с этим мог бы сильно помочь Zobrist hashing).

Посмотрим, как изменяется количество просматриваемых позиций, при увеличении глубины перебора:



Поскольку среднее время ожидания завершения ходов всех противников (при глубине просмотра 5 ходов) составляет около 1 минуты, очевидно, что это максимальная глубина перебора, на которую можно рассчитывать, при текущей реализации алгоритма (любое ее увеличение сделает игру человека с программой совершенно не комфортной).

Но давайте подумаем, что такое 5 ходов в игре Splut? This is not enough even to calculate the possible moves of all players! Even in Duel mode. It's like counting a game of Chess just 1 turn ahead! It is difficult to expect special intelligence from such a program.

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