Dagaz: A new beginning

Runs to the south and turns to the north, turns, wind turns on its run,
And the wind returns to its full circle;
All the rivers run into the sea, - and the sea does not overflow,
To the place where the rivers run, - There they continue to run;

Book of Ecclesiastes .

In 1998, a completely unique, for its time, application was developed, allowing to reduce the process of developing an abstract board game (or puzzle) to a small textual description in a language remotely resembling Lisp . This project was named Zillions of Games and created a real sensation among board game lovers. Currently, more than 2000 applications have been created using this technology.
')
It quickly became clear that ZoG has many flaws. I already wrote about this on Habré and will not be repeated. Let me just say that the developers did not take into account the peculiarities of a huge number of already existing games, and some of the important options were “hard-coded” in such a way that their change became extremely problematic. Greg Schmidt, in 2007, tried to correct the situation by releasing the Axiom Development Kit , but the close integration of this solution with ZoG did not solve all the problems.

The Ludi project has identified new frontiers using a universal game “engine” and genetic algorithms to automate the process of developing new board games. Unfortunately, this approach initially included a conscious simplification of both the game mechanics and the level of AI used. A discussion of the objectives of this project is beyond the scope of this article, but some of its technical solutions undoubtedly served as a starting point for starting my own development.

My goal is to develop a more versatile and easy-to-use "engine" for creating abstract board games. For almost a year I have been studying the possibilities of ZoG and Axiom and learned a lot about their limitations. I think I can solve their problems by creating a more universal and cross-platform solution. I am going to tell you about the progress of this project.

Openness and modularity

Perhaps the main drawback of ZoG is its secrecy. The product is assembled "once and for all" under one single platform - Windows. If the source codes were open, you could try porting them to Linux, Android, iOS ... Another problem is solidity.

ZoG has the beginnings of modularity, allowing you to connect to games DLL containing custom AI implementations. Axiom goes a little further, allowing you to run applications in autoplay mode, without using the ZoG kernel. Even despite the serious limitation of this solution (only two-player applications are supported), this example clearly shows how useful modularity would be! The ability to organize a game of two bots (using different AI settings) and collect statistics on a large number of their games is difficult to overestimate. But how much better it would be if the product were completely modular!

• Move Generation Module
• Progress module
• Control module
• AI module
• Visualization module

All work with the description of the games must be performed by the module for generating moves. This is the "heart" of the project. Transferring all the functionality not related to its tasks to other modules will make it as simple as possible. You can improve this module without looking at questions of AI and user interaction. You can completely change the format of the description of the games or add support for descriptions in the format ZoG , Axiom and Ludi . Modularity is the basis of the flexibility of the solution!

A turn execution module is a game state keeper. Information about the current game state is transmitted to all other modules on demand. For the reasons that I will discuss below, the execution of a move must pass through a generation module whose task is to form a command in terms of the progress execution module. Also, the task of the generation module is the primary configuration of the game space, based on the game description.

The control module is essentially the application itself. He asks the generation module for lists of possible moves and changes the game state, passing the selected turn to the progress module. The control module can connect one or several AI bots to the game. As much as required (and possibly different)! The type of control module used is determined by the tasks to be solved. This can be autoplay for collecting game statistics, a game server (it can manage several state repositories at once, leading a large number of game sessions) or an individual application for playing offline.

The ability to connect various AI implementations will improve the quality of the game. It is clear that the modules for the game of Chess and Go must use different approaches. Games with incomplete information and games using random data also require an individual approach. Universal AI implementation will be equally bad to play all games! The modular connection of the AI ​​will allow you to compare the "power" of the algorithms used, including them in the game mode "between themselves". Since AI is architecturally separated from the game state storage, one implementation of the game bot will be able to support an unlimited number of game sessions simultaneously.

The visualization of the gameplay can also be different. The first thing that comes to mind is 2D and 3D implementations. The platform for which the application is being developed is also important. It is less obvious that visualization can be an important part of the gameplay! For example, in the Surakarta game, the capture of figures will be completely unobvious in the absence of proper animation of the moves.


In general, modularity seems like a good idea for such a project, and open source codes will allow everyone to participate in it. Currently, I do not set myself commercial goals, but I think that, if desired, I will find a way to make money without closing the source codes.

Gaming space

Before starting the performance, it is necessary to prepare the scene. The board is not just a place where figures are placed. In addition, the directions of movement of the figures (in fact, the connection between the board fields), gaming areas (for example, the zones of transformation of figures), forbidden fields, etc. can be determined. Here is the definition of the board in the ZoG chess implementation:


You may notice that in addition to the actual game settings, there are settings associated with visualization. I firmly believe that these settings are not the place. There may be several implementations of the visualization module and they will need different settings. Moreover, the game simulation can work without a visualization module at all (as autoplay in Axiom ). Indeed, since Axiom uses ZoG for visualization, the definition does not contain anything extra:


Unfortunately, it also does not contain definitions of playing areas (the location of playing areas has to be determined in the code manually). This is not the only simplification of the Axiom . The definition of a board in this project cannot contain more than one grid, and this grid must be two-dimensional. A board defined in this way is a one-dimensional array, but for the convenience of the programmer, synonyms are defined for each of the fields, according to the following scheme:


Compared to the more flexible grid definition scheme in ZoG , these restrictions are quite inconvenient (especially since the imposed field naming scheme is also used for visualization). Fortunately, it is possible to define a board of arbitrary shape. Both Axiom and ZoG provide the possibility of element-by-element determination of each position of the board with the possibility of determining the connections between arbitrary pairs of positions. Using this approach, you can define a board of any topology. Its only drawback is the extreme verbosity and complexity of the description.

In addition to the arrangement of the pieces on the board and in the reserve, it must be possible to store attributes for individual pieces as well as for the board’s fields. A good example of the need to use attributes is the " castling " rule in Chess . This is a complex move, which includes the simultaneous movement of the king and one of the rooks, possible under the condition that none of these pieces moved before the execution of this move. The attribute can be used to store a boolean sign that the figure has moved ever. Field attributes can also find some pretty interesting uses.

It should be noted that the attributes are not just variables, but part of the game state. The attribute value can be changed when performing a turn (including the AI ​​module) and should be available for all subsequent moves, but not for moves performed in another branch of the game. Currently, ZoG supports storing boolean attributes of shapes. Axiom does not support attribute storage, but allows adding a description of variables and arrays to the board definition. Such variables can be used, for example, as counters of the number of eaten figures:

 {board 5 18 {grid} {variable} WhitePieces {variable} BlackPieces board} 

Another limitation of both ZoG and Axiom is the rule that each field of the board can contain no more than one figure. If any figure completes a move on a field occupied by another figure, the figure that previously occupied the field is automatically considered “eaten”. This rule is well combined with the “chess” principle of taking figures and simplifies the descriptions of games using it, but makes it difficult to implement such games as Stolovye drafts and Tavreli .


In these games, the pieces can line up in “columns.” Such a "column" can move entirely as a single figure. After some reflection, I decided that it was better not to abandon the automatic implementation of the “chess” capture, but to improve the mechanisms for moving groups of pieces. Indeed, to implement the “columns”, you can always add another dimension to the board (this is all the more simple, since the visualization module will be separated from the modules for generating the moves and AI and it will be possible to use any logic to display the three-dimensional board on its two-dimensional visualization). An additional argument in favor of this decision was that the “columnar” movement of figures is not the only type of group movement. For example, in Pentago , fragments of the board can be rotated, along with the shapes mounted on them.


Summarizing, we can say that for my game framework, I decided to take all the best that was invented in ZoG , Axiom and Ludi and add what, in my opinion, they lack.

Generation

Generating a move is akin to non-deterministic programming . The task of the move generator is to provide, on request, a list of all possible moves from the current position. Which move, from this list, will be chosen by the player or AI is not his business. Consider exactly how the generation of moves in ZoG . As an example, take the macro of the generation of the course by a long-range figure (queen or bishop). Here is how it is used in determining the shape:

 (piece (name Bishop) (image White "images\Chess\SHaag\wbishop.bmp" "images\Chess\wbishop.bmp" Black "images\Chess\SHaag\bbishop.bmp" "images\Chess\bbishop.bmp") (moves (slide ne) (slide nw) (slide se) (slide sw) ) ) 

As a parameter, the direction of movement on the board is transferred to the macro. If you do not consider the possibility of installing new pieces on the board, the generation of the move looks easy. For each of the pieces on the board, all the moves determined by the rules are iterated. Then the magic begins ...

Each of the definitions can add to the list several possible moves! Adding a move to the list is done with the add command (part-time setting the moving figure on the board). I already wrote that such an architectural solution is extremely unfortunate. The formation team must be separated from the teams that manipulate the figures (as was done in Axiom ). Let's see how the macro works:

 (define slide ( $1 (while empty? add $1 ) (verify not-friend?) add )) 

First, a movement is performed one cell in a given direction, after which, in a cycle, the achieved field is checked for the absence of figures in it, a move is formed and another movement is made to another cell in the same direction. If you stop at this, the figure will be able to "slide" on empty cells, but how to take enemy figures?

Very simple! Having executed the verify command, checking that the field is not occupied by a friendly figure, we form another add command, completing the move. If an enemy figure was placed on this cell, it will be taken automatically (since more than one figure cannot be placed on one board field at a time). If the figure was friendly, the calculation of the course is interrupted by the command verify (violation of the conditions specified in this command, immediately interrupts the calculation of the current course).

Both in ZoG and Axiom you can only walk with your own figures (or rather, you can walk with enemy figures, but only if this is indicated in the mode of calculating the turn). I find this restriction extremely inconvenient, since there are many games in which it is possible to walk around the opponent’s pieces (in the “ Stavropol checkers ”, for example). It would be more consistent to perform the calculation of the course for all figures, regardless of their affiliation. It would be necessary to add just one check to the macro defining the move in order to walk only with your own figures:

 (define slide ( (verify friend?) $1 (while empty? add $1 ) (verify not-friend?) add )) 

The ability to make a move consisting of several “partial” moves is important. In implementations of drafts, this feature is used to perform "chains" of taking:

 (define checker-jump ($1 (verify enemy?) capture $1 (verify empty?) (if (not-in-zone? promotion-zone) (add-partial jumptype) else (add-partial King jumptype) ) ) ) 

The partial move is formed by the add-partial command (for it, as for the add command, there is a variant of the move, with the “transformation” of the figure). Such a move is always part of a larger, “composite” move. As a rule, for subsequent moves, a “mode” is set in which the continuation should be carried out. So in checkers, the capture can be continued only by subsequent captures, but not by a “quiet” move.


Such a system for describing rules is very flexible, but sometimes more complex logic is required. For example, if a figure, when performing a “partial” move, does not have to re-pass through previously passed fields, it is logical to use flags associated with the positions on the board. Visiting the field, we will re-flag so that we will not re-enter this field again:

 (verify (not-position-flag? my-flag)) (set-position-flag my-flag true) 

In addition to the “positional”, global flags can be used in ZoG . These features should not be confused with the attributes of shapes. Unlike the latter, they are not part of the game state. Unfortunately, both the attributes of figures and flags in ZoG can only be boolean (in Axiom, attributes are not supported at all). This limitation makes it difficult to perform operations associated with various kinds of calculations. For example, in this small puzzle, I had to use a pair of Boolean flags to “count” the figures that fell into the “plug” (I didn’t need the exact number, as long as there were more than one figure).

Another thing that needs to be corrected is the lack of an intelligible “life cycle” of a turn. All flags are automatically reset before starting a turn, but it would be more convenient to select the initialization phases explicitly. In my opinion, when calculating the course, the following phases should be performed:

1. Variable initialization and check of prerequisites of the compound stroke
2. Variable initialization and partial stroke precondition check
3. Partial stroke generation
4. Partial move postcondition check
5. Generation of completion and verification of post-conditions for a compound course
6. Check the completion of the game

The group of steps from the second to the fourth, when performing a composite move, can be repeated many times. The idea of ​​the pre- and post-conditions, which I call invariants, I took from the Ludi project. However, I will talk more about the use of invariants in the future.

About the importance of notation

Generating all possible moves from a position is only half the battle. To control the game state, a compact form of presentation of the generated moves is required. ZoG uses a ZSG abstract for this purpose. Here is the record of the possible start of a chess game in this form:

 1. Pawn e2 - e4 1. Pawn e7 - e5 2. Knight g1 - f3 2. Knight b8 - c6 3. Bishop f1 - c4 3. Knight g8 - f6 4. King e1 - g1 Rook h1 - f1 @ f1 0 0 @ g1 0 0 4. Pawn d7 - d5 5. Pawn e4 x d5 5. Knight f6 x d5 

Such a record is close to the usual chess notation and, in general, is understandable to the user. Some bewilderment can only be caused by White’s fourth move. So in ZSG castling looks like. Part of the description of the move to the ' @ ' symbol is understandable - this is the simultaneous movement of the rook and the king, but what follows next? Thus, in ZSG , it looks like a reset of the attributes of figures, the execution of which is necessary in order not to give an opportunity to perform castling again.


The record of the move in the ZSG notation should contain complete information sufficient to correctly change the game state. If the information about the attribute changes was not saved, the game, according to this record, could be played incorrectly (for example, the player would have the opportunity to rerun the castling). Unfortunately, in DLL extensions (such as Axiom ), extended information may not be transmitted.

Working with DLL extensions, ZoG is forced to perform a rather cunning manipulation when performing positioning on a selected turn (for example, when rolling back a turn). From the previous position, all possible moves are generated, and then, in the list, the selected move is searched for by its ZSG representation. The generated move applies to the game state, possibly performing side effects that are not reflected in its ZSG presentation.

The situation is aggravated by the fact that the only way to get the game state, at the time of a move in the past, is the consistent application of all moves, from the beginning of the game, to the initial state of the board. In really difficult cases , such navigation is not fast. Another drawback of the ZSG notation can illustrate the following turn from the Go game:

 1. White Stone G19 x A19 x B19 x C19 x D19 x E19 x F19 

Here, in position G19, a white stone is set, which leads to the removal of a group of black stones. Since all the pieces involved in the execution of the turn should be mentioned in the ZSG presentation, the stroke recording can be very long (in Go, up to 360 stones can be taken in one move). What it can lead to, I already wrote earlier . The size of the buffer allocated by ZoG for stroke recording may not be enough. In addition, if for some reason the order of removing the stones changes (during the development of the game this happens), an attempt to use the course, with the old order of taking, will end in error.

Fortunately, there is an easy way to deal with all these problems. Let's look at how the moves of the pieces in ZRF are determined:

 (piece (name Pawn) (image White "images\Chess\SHaag\wpawn.bmp" "images\Chess\wpawn.bmp" Black "images\Chess\SHaag\bpawn.bmp" "images\Chess\bpawn.bmp") (moves (Pawn-capture nw) (Pawn-capture ne) (Pawn-move) (En-Passant e) (En-Passant w) ) ) 

The names of the moves defined in ZoG macros are not available to the move generator. But what prevents us from abandoning macros and making move descriptions named? Here's what the chess game record will look like:

 1. e2 - e4 Pawn-move 1. e7 - e5 Pawn-move 2. g1 - f3 leap2 n nw 2. b8 - c6 leap2 n ne 3. f1 - c4 slide nw 3. g8 - f6 leap2 n nw 4. e1 - g1 OO 4. d7 - d5 Pawn-move 5. e4 x d5 Pawn-capture nw 5. f6 x d5 leap2 w nw 

The benefits of such a record are not obvious, but it has one important advantage. All moves are described in a single form and these descriptions do not contain anything superfluous (the names of the descriptions of the moves, of course, could have been made more “talking”). In the description of the castling, it was possible to get rid of the change of attributes and even the description of the move of the rook (this description no longer depends on the details of the implementation of the move). The usefulness of such a record in the case of a Go game is even more obvious:

 1. G19 drop-to-empty White Stone 

And it's all! If the opponent’s stones are taken in accordance with the rules of the game, there is no need to list them all in the course description. It is enough to specify the initial and final field of the movement (possibly with a sign of taking), the name of the move being executed and the string of parameters passed to it. Of course, in order to execute a move, according to this description, for decoding, you will have to turn to the module for generating moves, but ZoG does just that!


Another feature that should be supported is the functionality of "partial" moves. Here is an example from the Russian Checkers :

 1. Checker g3 - f4 1. Checker f6 - g5 2. Checker e3 - d4 2. partial 2 Checker g5 - e3 = XChecker on f4 2. Checker e3 - c5 = XChecker on d4 x d4 x f4 

Here the blacks, on the second move, take two pieces on d4 and f4. The preliminary "transformation" of the pieces in the XChecker is a feature of the implementation and serves to prevent the possibility of re-taking the "broken" pieces on the same turn. The phrase " partial 2 " describes the beginning of the "composite" move, consisting of two "partial" moves. This form of description is inconvenient, because at the time of generation of the first move, the length of the sequence of “partial” moves may be unknown. This is how the description will look like in the new format:

 1. g3 - f4 checker-shift nw 1. f6 - g5 checker-shift ne 2. e3 - d4 checker-shift nw 2. + g5 - e3 checker-jump nw 2. + e3 - c5 checker-jump sw 2. + 

Implementation details associated with the "transformation" of figures are superfluous. The capture of figures should also not be indicated, since, in checkers, the capture is performed as a “side effect” of the move of the figure, and not according to the “chess principle”. The partial move will be encoded with a " + " at the beginning of the line. A single " + " means the completion of a "composite move" (in fact, this is the usual "partial" move, which contains the omission of a move - an empty line).

Thus, using the named rules for executing moves, we managed to create a universal notation that fully satisfies our requirements. Of course, it has nothing to do with conventional chess with any other notation, but it so happens that the generally accepted notations for chess, checkers and other games also have nothing in common with each other. The visualization module can always perform the conversion of a move record into a more familiar form adopted for a particular game.It can also be converted to some other universal form, for example SGF .

Game life cycle

Along with the information on the placement of pieces on the board, the sequence of turn is an integral part of the state that is changed during the game. In the simplest (and most common) case, one bit is enough to store this information, but ZoG provides slightly more options for implementing more complex cases. This is how the description of the sequence of moves for the game Splut might look ! :

 (players South West North East) (turn-order South West West repeat North North North East East East South South South West West West ) 

In this game, each player makes three moves at a time, but if the first player is given the opportunity to make three moves from the initial position, he will be able to destroy one of the opponent's pieces, which will give him a significant advantage. For this reason, the first player must make one move (this gives the opportunity to prepare for the attack of the player opposite, but not attack him), the second - two moves (this is also not enough to attack the opposing player), after which each player always three moves each.


The repeat label indicates the beginning of a cyclically repeating sequence of moves. If it is absent, the entire description is repeated cyclically. ZoG allows you to use the repeat label no more than once. Another important feature is the determination of the travel mode . Here is how the description of the sequence of moves of the game, in which each of the players performs two moves, may look (the first move is the movement of a piece, the second is the capture of an opponent's piece):

 (players White Black) (turn-order (White normal-move) (White capture-move) (Black normal-move) (Black capture-move) ) 

There is another possibility associated with the description of moves by other figures, but it is extremely inconvenient to use. The fact is that such a description has no alternative. If the description indicates that the move must be carried out by an opponent figure, the player must perform such a move! In ZoG it is impossible to describe the move " to choose " with your own or someone else's figure. If such an opportunity is necessary in the game (as, for example, in the " Stavropol drafts"), you have to neutralize all the pieces (creating for this purpose a player not participating in the game) and determine for all players the possibility of a move with neutral pieces. Above, I have already said that it is much easier to allow players to initially move with any pieces ( and its opponent), adding the necessary checks in the course of generating algorithms.

as can be seen, a set of possibilities offered by ZoG , to describe the sequence of moves is extremely limited. Axiom also adds new features, because (usually) No. lnyaetsya over ZoG . LudiIn this respect, even poorer. In order to maximize the unification of game rules (necessary for the possibility of using genetic algorithms), in this project, all descriptive features are consciously simplified, which leads to the cutting off of whole layers of games.


" Bao Kiswahili " is a good example of a game with a complex life cycle. In this game there are two phases, the rules for performing a turn are significantly different. At the beginning of the game, a part of the stones is “in the hand” of each of the players. While the stones "in hand" are not over, there is a throwing of stones into the holes, one stone each. When the stones “in hand” end, the second phase of the game begins, connected with the redistribution of the stones thrown in. This is not to say that this game cannot be described in ZRF ( ZoG description language ), but due to the limitations of ZoG , such an implementation would turn out to be extremely confusing (which would certainly not have the best effect on the quality of AI work). Let's see how the description of such a game could look like in an “ideal world”:

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (label phase-ii) (turn-order (South p-ii-move) (North p-ii-move) ) ) 

Here, each turn-order list defines its recurring sequence of moves (distinguished by the progress mode). The label keyword defines a label, the transition to which can be formed during the generation of the next move. You may notice that here we proceed from the implicit assumption that such a transition always occurs after the move of the second player (otherwise the sequence of moves will be broken). How to make the transition to the next phase at an arbitrary point in time?

 (players South North) (turn-order (turn-order (South pi-move) (North pi-move) ) (turn-order (labels - phase-ii) (South p-ii-move) (labels phase-ii -) (North p-ii-move) ) ) 

Here the labels are transferred to the body of the loop and contain two names each. The names of the labels in the lists of labels are listed in accordance with the order of enumeration of players in the list of players . The name used for the transition is determined depending on which player performed the move last. If it was North , it will go to the first label, otherwise - to the second. If any of the names in the labels will not be used, the corresponding position can be filled with a dash.


An important point in the management of alternating moves is the possibility of performing a repeated move. In games of the Nard family , such as Ur , for example, the ability to perform repeated moves is an important element of the game tactics. In ZoG, you can use the skip move to emulate this possibility, but this approach essentially confuses the description of the game (especially with the participation of several players). It is much more logical to use the label to repeat the move:

 (players South North) (turn-order (label repeat) South (label repeat) North ) 

After completing the transition to repeat , the player will return to repeating the last move (the label closest to the current position in the list of moves will be valid). I like the Perl approach to implicit definitions. Implicit generation of control structures can significantly simplify the description. Since repeated moves can be used in many games, repeat labels preceding each turn can be implicitly formed:

 (players South North) (turn-order South North ) 

Moreover, since the sequence of moves fully corresponds to the players listed in players , the entire turn-order phrase can be automatically generated :

 (players South North) 

The simpler the description is, the better.

Broken invariant

The main thing that I do not like in ZoG can be expressed in one word - checkmated . At first glance, this is just a condition (quite common in games of the chess family), which relates the completion of the game to the formation of a matte situation . Alas, on closer examination, simplicity is deceptive. The use of this keyword implies not only the execution, after each move, checks the completion of the game, but also imposes a certain "behavior" on the player.

And the module for generating moves and AI must take into account that after completing a move, your king should not be under check . At the same time, it is not enough to perform a check only for a piece that has descended, the check may well be " open". It is not easy to correctly implement all the necessary checks (in ZoG , anyway, this was not possible):



From the usual Shogi, this game differs only in the number of players. Unfortunately, this difference is enough to make the work of checkmated (and all associated with this word "magic") incorrect. The correct check of being in check is performed only in relation to one of the players. As a result, the king may well be under attack and be eaten! Of course, this is not the best way reflected in the work of AI.

If this problem seems insignificant, it is worth remembering the coalitions usually formed in the games of four players “a couple for a couple”. In the case of coalition formation, we must take into account that friendly figures do not threaten the king! For example, two friendly kings may well be placed on the adjacent board fields.


Even more complicated if the player can have several kings. In " Chess of Tamerlan ", the royal pawn turns into a prince (in fact, into the second king). If this happens, you can win only by eating the first king (any of the two) and mating the second. In this game, you can get the third king, having twice spent the transformation of the "pawn pawn"! The expressive possibilities of " checkmated " are not enough to adequately describe this situation.

Another difficulty can be the process of mating. So in the Mongolian version of chess ( Shatar), the result of the matting depends on the order in which the pieces perform successive “shahs”. The result can be both a victory and a draw (for example, when a mate is a pawn) and even a defeat (it is forbidden to mate, but a check can be made). Slightly less exotic, in this regard, Japanese Shogi. In this game, it is forbidden to checkmate a pawn, but you can check with a pawn and mate with a pawn.


Obviously, it is necessary to separate the logic of checking the completion of the game from checking that the king falls under the check, which is, in essence, an invariant that is checked after each turn. Violation of the invariant makes the execution of a move impossible (a move is removed from the list of available moves). This is how (simplistic) the test of the king’s check for Tamerlan Chess may look like:

 (verify (or (> (count (pieces my? (is-piece? King))) 1) (= (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

It is important to understand that this test should be performed only for one’s own kings (I used the my? Predicate , since, with the support of coalitions, the friend attribute will be satisfied not only for one’s own pieces, but also for a friendly player’s pieces). There is a permissible (and desirable) situation in which the enemy king falls under a check after the execution of a turn, but with regard to his own king, such a situation must be impossible! Subject to the support of checking such invariants, checking the completion of the game with a mat becomes trivial. If there are no possible moves and the king is under check, the game is lost:

 (loss-condition (and (= (count moves) 0) (> (count (pieces my? (is-piece? King) is-attacked?)) 0) ) ) 

The ability to define invariants will be useful in other games, such as checkers . The greatest difficulty in the implementation of games of this family is associated with the implementation of the "majority rule". In almost all checkers games, a move with a take is mandatory. Also, for most games of this family, it is typical to perform "chains of take", in the framework of one move. The figure that performed the take continues to take other figures, if possible. In most games, the player is obliged to bring the chain of takeings to the end, but there are exceptions to this rule, for example Fanorona .


Using the mechanism of partial moves, the "chain of take" is quite simple to implement. Difficulties begin when, in addition to this, a condition is imposed, according to which, from all possible options, it is required to choose a chain that takes the maximum number of figures. In ZoG, this logic is re-implemented at the “hardcode” level:

 (option "maximal captures" true) 

This setting is suitable for " International drafts ", but in the " Italian drafts " the majority rule is formulated differently. In this variant of the game, if there are several variants with the same number of takes, it is required to choose the variant in which more turned checkers (ladies) are taken. ZoG developers have foreseen this by entering the following setting value:

 (option "maximal captures" 2) 

When using this setting, not only the number of pieces taken, but also their type is taken into account. Unfortunately, it is impossible to foresee everything. Here is how the “majority rule” is formulated in the “ Old French Checkers ”:

If during a series of takes, you can cut the same number of pieces with a simple piece or a queen, the player must take a queen. However, if the number of checkers removed is the same in both cases, but in one <branch> there are opponent's queens (or there are more of them), the player must choose this option, even if it is then necessary to chop with a simple checker, and not a lady .

Of course, at present, almost no one plays this version of drafts, but its very existence clearly demonstrates the shortcomings of the “hardcode” implementation. Using the mechanism of invariants allows you to implement all possible variants of the "rule of the majority" in a universal way. For the "Old French Drafts" implementation will be as follows:

 (verify (>= capturing-count max-capturing-count) ) (if (> capturing-count max-capturing-count) (let max-capturing-count capturing-count) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= capturing-sum max-capturing-sum) ) (if (> capturing-sum max-capturing-sum) (let max-capturing-sum capturing-sum) (let max-attacking-value attacking-value) ) (verify (>= attacking-value max-attacking-value) ) (let max-attacking-value attacking-value) 

Here, we proceed from the assumption that the rules for generating a stroke correctly fill local variables:

• capturing-count - the number of pieces taken
• capturing-sum - the total value of the figures taken
• attacking-value - the dignity of the figure performing the move

Each of these variables is associated with a battery value, stored in a variable with the prefix max . Three checks are performed sequentially. Violation of any of the verify conditions immediately terminates the generation of the next turn (the turn is not saved in the list of possible moves). Since the checks performed are related to the values ​​being changed, this is not enough for the conditions to work correctly. Each such check forms a “broken invariant” associated with the generated move. After each change in the value of the battery, all associated invariants are re-checked. If any of the conditions are violated, the previously generated move is removed from the list of possible moves.

Conclusion

In this article, I tried to talk about my plans to create a new universal "engine" for the development of abstract logic games and puzzles. I am aware that this work is not for one month (maybe even not for a year), but, in this case, the process, for me, is much more important than the result. I do not plan to extract any benefits from this work and, even more so, I do not plan to close the source codes of the project. If any license will be used, I will try to find the most liberal option. I will be glad if someone joins my work, but if I don’t find any, I won’t worry too much.

Viam supervadet vadens .