Dagaz: A New Beginning

    Runs south and circles north, circles, wind circles on its run,
    And the wind returns to its circles;
    All rivers
    run into the sea, but 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 application was developed for its time, allowing to reduce the development process of an abstract board game (or puzzle) to a small textual description in a language that remotely resembles Lisp . This project is called Zillions of Games and made a splash among fans of board games. Currently, more than 2000 applications have been created using this technology.

    It quickly became clear that ZoGhas many disadvantages. I already wrote about it on Habré and I will not repeat. I can only say that the developers did not take into account the features of a huge number of existing games, and some of the important options were “hardcoded” in such a way that changing them became extremely problematic. Greg Schmidt, in 2007, tried to rectify the situation by launching the Axiom Development Kit , but the close integration of this solution with ZoG did not solve all the problems. Ludi

    project marks new frontiers using universal game engine and genetic algorithmsto automate the process of developing new board games. Unfortunately, this approach initially provided for a deliberate 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 its individual technical solutions undoubtedly served as a starting point for the start of my own development.

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

    Open and modular


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

    In ZoG there are the beginnings of modularity, allowing you to connect to a game DLL , containing a custom implementation of the AI. Axiom goes a bit 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 modular it would be useful! The ability to organize a game of two bots (using different AI settings) and collect statistics on a large number of their games can hardly be overestimated. 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 should be performed by the module for generating moves. This is the "heart" of the project. Transferring all functionality not related to its tasks to other modules will make it as simple as possible. You can improve this module without looking at AI and user interaction issues. You can completely change the format of the description of the games or add support for the descriptions in the format of ZoG , Axiom and Ludi . Modularity is the basis of solution flexibility!

    The progress module is the keeper of the game state. Information about the current game state is transmitted to all other modules upon request. For the reasons that I will discuss below, the execution of a move must pass through the generation module, the task of which is to form a team in terms of the module of the execution of the move. Also, the task of the generation module is the initial configuration of the game space, based on the description of the game.

    The control module is, in fact, the application itself. He asks the lists of possible moves from the generation module and changes the game state, passing the selected move to the move execution module. The control module can connect one or more AI bots to the game. As many as required (and possibly different)! The type of control module used is determined by the tasks being solved. It can be autoplay for collecting game statistics, a game server (it can manage several state stores at once, conducting 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 modules for playing Chess and Go should use different approaches. Games with incomplete information and games using random data also require an individual approach. A universal AI implementation will play all games equally badly! Modular AI connection will allow you to compare the "strength" of the algorithms used, including them in the game mode "among themselves." Because the AI ​​is architecturally separate from the game state repository, one game bot implementation 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 also matters. Less obvious is that visualization can be an important part of the gameplay! So, for example, in the Surakarta game , taking the pieces will be completely unobvious in the absence of the correct animation of the moves.


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

    Game space


    Before starting the performance, it is necessary to prepare the stage. A board is not just a place on which pieces are placed. In addition, the direction of movement of the figures (in fact, the relationship of the board's fields to each other), game zones (for example, zones for turning shapes), forbidden fields, etc. can be determined. Here's how the board looks at the definition of ZoG -realization chess:

    Board Definition in ZoG
    (define Board-Definitions
      (image "images\Chess\SHaag\Chess8x8.bmp" "images\Chess\Chess8x8.bmp")
      (grid
         (start-rectangle 5 5 53 53)
         (dimensions
             ("a/b/c/d/e/f/g/h" (49 0)) ; files
             ("8/7/6/5/4/3/2/1" (0 49)) ; ranks
         )
         (directions (n 0 -1) (e 1 0) (s 0 1) (w -1 0)
    			     (ne 1 -1) (nw -1 -1) (se 1 1) (sw -1 1)
         )
      )
      (symmetry Black (n s)(s n) (nw sw)(sw nw) (ne se)(se ne))
      (zone
         (name promotion-zone)
         (players White)
         (positions a8 b8 c8 d8 e8 f8 g8 h8)
      )
      (zone
         (name promotion-zone)
         (players Black)
         (positions a1 b1 c1 d1 e1 f1 g1 h1)
      )
      (zone
         (name third-rank)
         (players White)
         (positions a3 b3 c3 d3 e3 f3 g3 h3)
      )
      (zone
         (name third-rank)
         (players Black)
         (positions a6 b6 c6 d6 e6 f6 g6 h6)
      )
    )
    


    You may notice that in addition to the actual game settings, there are settings related to visualization. I am firmly convinced that these settings do not belong here. There can be several implementations of the visualization module, and they will need different settings. Moreover, a game simulation can work without a visualization module in general (like autoplay in Axiom ). Indeed, since Axiom uses ZoG to render , the definition contains nothing more:

    Axiom board definition
    {board
    	8 8 {grid}
    board}
    {directions
    	-1  0  {direction} n
    	 1  0  {direction} s
    	 0  1  {direction} e
    	 0 -1  {direction} w
    	-1 -1  {direction} nw
    	 1 -1  {direction} sw
    	-1  1  {direction} ne
    	 1  1  {direction} se
    directions}
    {symmetries 
    	Black {symmetry} n s
    	Black {symmetry} nw sw
    	Black {symmetry} ne se
    symmetries}
    


    Unfortunately, it also does not contain a definition of game zones (the location of game zones must be determined manually in the code). This is not the only simplification Axiom makes . The board definition in this project cannot contain more than one grid, and this grid must be two-dimensional. The 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 limitations are rather inconvenient (especially considering that the imposed field naming scheme is also used in visualization). Fortunately, it is possible to define a board of arbitrary shape. Both Axiom and ZoG provide the possibility of elementwise determination of each position of the board with the ability to determine the relationship between arbitrary pairs of positions. Using this approach, you can define a board of any topology. Its only minus is the extreme verbosity and the complexity of the description.

    In addition to arranging the pieces on the board and in the reserve, it should be possible to store attributes for both individual pieces and board fields. A good example of the need to use attributes is the “ castling ” rule in Chess . This is a difficult move, including the simultaneous movement of the king and one of the rooks, possible provided that none of these pieces moved before this move was completed. The attribute can be used to store a Boolean sign that the figure has ever moved. Field attributes can also find quite interesting uses.

    It should be noted that attributes are not just variables, but part of the game state. The attribute value can be changed during a move (including the AI ​​module) and should be available for all subsequent moves, but not for moves made in another branch of the game. Currently, ZoG supports storing Boolean attributes of shapes. Axiom does not support attribute storage, but allows you to add 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 board field can contain no more than one piece. If any piece completes the move on the field occupied by another figure, the figure that previously occupied the field is automatically considered “eaten”. It usually goes well with the "checkerboard" the principle of taking the figures and to simplify the description of using his games, but difficult to implement such games as " Pole-checkers " and " tavreli ".


    In these games, the figures can line up in “columns”. Such a “column” can move as a whole, as a single figure. After some thought, I decided that it was better not to abandon the automatic implementation of “chess” capture, but to improve the mechanisms for moving groups of pieces. Indeed, for the implementation of 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 moves and AI and any logic of mapping a three-dimensional board to its two-dimensional visualization can be used in it). An additional argument in favor of this decision was that the “column” movement of the figures is not the only type of group movement. For example, in the Pentagon"fragments of the board may be rotated, together with the pieces mounted on them.


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

    Cogeneration


    The generation of a move is akin to non-deterministic programming . The task of the move generator is to provide, upon request, a list of all possible moves from the current position. Which move from this list will be selected by the player or AI is not his business. Consider exactly how the generation of moves in ZoG is performed . As an example, take a macro to generate a move with a long-range piece (queen or bishop). Here's how it is used in defining a 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 along 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 simple. For each of the pieces on the board, it enumerates all the moves defined by the rules. Then the magic begins ...

    Each of the definitions can add several possible moves to the list! Adding a move to the list is done by the add command (concurrently sets the moved piece onto the board). I already wrote that such an architectural solution is extremely unsuccessful. The move formation team must be separated from the pieces manipulating teams (just like Axiom did ). Let's see how the macro works:

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

    First, a movement is made 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 one more cell is moved in the same direction. If we dwell on this, the figure will be able to "glide" over empty cells, but how to take enemy figures?

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

    Both in ZoG and Axiom you can only walk with your own pieces (or rather, you can walk with enemy pieces, but only if it is indicated in the course calculation mode). I find this restriction extremely inconvenient, since there are many games in which you can play with enemy pieces (in Stavropol Checkers , for example). It would be more consistent to calculate the course for all figures, regardless of their affiliation. In the macro that defines the move, you would need to add only one check, so that you could walk only with your own pieces:

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

    What is important is the ability to complete a move consisting of several "partial" moves. In implementations of checkers, this feature is used to perform “chains” of captures:

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

    A partial move is formed by the add-partial command (for it, like 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, “compound” move. As a rule, for subsequent moves, a “mode” is established in which to continue. So in checkers, the capture can be continued only by subsequent captures, but not by a "quiet" move.

    Note
    In ZoG , the implementation of partial moves leaves much to be desired. Attempting to execute the add-partial command in a loop results in an error. As a result, the capture performed by the lady can only be realized in the following, very awkward manner:

    (define king-jump-1
        ($1 (while empty?
                $1
            )
            (verify enemy?)
            capture
            $1
            (verify empty?)
            (add-partial jumptype)
        )
    )
    (define king-jump-2
        ($1 (while empty?
                $1
            )
            (verify enemy?)
            capture
            $1
            (verify empty?)
            $1
            (verify empty?)
            (add-partial jumptype)
        )
    )
    

    And so on, right up to king-jump-7! Let me remind you that in most varieties of checkers, with "long-range" ladies, the lady, having completed the capture, can stop on any field from a continuous chain of empty fields following the figure taken. There is, however, one version of this game in which the rule of the “chain” of captures is formulated differently. This is exactly what I like about checkers - everyone can find an option to their liking.

    Such a rule description system is very flexible, but sometimes more complex logic is required. For example, if a piece, when performing a “partial” move, does not have to re-pass through previously passed fields, it is logical to use flags associated with positions on the board. Having visited the field, we cock the flag so as not to re-enter this field later:

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

    In addition to “positional”, global flags can also 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, the attributes of shapes and flags in ZoG can only be Boolean (in Axiom, attributes are not supported at all). This limitation makes it difficult to perform operations related to various kinds of calculations. For example, in this small puzzle, I had to use a couple of Boolean flags to “count” the figures that fell into the “plug” (I did not need the exact number, most importantly, there should be more than one figure).

    Another thing to fix is ​​the lack of a clear “life cycle” for completing the move. All flags are automatically reset before the start of the move, but it would be more convenient to highlight the initialization phases explicitly. In my opinion, when calculating the course, the following phases should be performed:

    1. Initializing variables and checking preconditions for a compound move
    2. Initialization of variables and verification of partial stroke preconditions
    3. Partial Stroke Generation
    4. Partial stroke postcondition checking
    5. Generation of completion and verification of postconditions of a compound move
    6. Verification of the completion of the game

    The group of steps two through four, when performing a compound move, can be repeated many times. I took the idea of ​​pre- and postconditions, called invariants by me, from the Ludi project . However, I will discuss the use of invariants in more detail later.

    About the importance of notation


    Generating all the moves possible from a position is only half the battle. To control the game state, a compact form of representing the generated moves is required. In ZoG , for this purpose, a ZSG abstract is used. Here is what a record of a possible start of a chess game looks like 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. Only the fourth move of White can cause some bewilderment. So in ZSG looks like castling . Part of the description of the move to the ' @ ' symbol is quite understandable - this is the simultaneous movement of the rook and king, but what follows? Thus, in ZSG , looks like a reset of the attributes of the figures, the implementation of which is necessary in order to prevent the ability to perform castling again.

    Note
    ZoG uses ZSG -notation also to show the course of the game in a form understandable to the player. To the right of the board image, the “Moves List” sub window can be opened. This list can be used to navigate through the recording of a game (not very convenient, since the tree view of alternative branches of the game is not supported). The part of the move record associated with changing the attributes of the pieces is not displayed to the user.

    The move record in the ZSG -notation should contain complete information sufficient to correctly change the game state. If the information on the change of attributes were not saved, the game, according to such a record, could be played incorrectly (for example, the player would have the opportunity to re-perform castling). Unfortunately, in DLL extensions (such as Axiom ), extended information may not be transmitted.

    When working with DLL extensions, ZoG is forced to perform rather tricky manipulations when performing positioning on a selected move (for example, when a move is rolled back). From the previous position, all possible moves are generated , after which, in the list, the selected move is searched by its ZSGto the presentation. The generated move is applied to the game state, possibly performing side actions that are not reflected in its ZSG representation.

    The situation is aggravated by the fact that the only way to get a game state, at the time of some move in the past, is to apply all the moves from the beginning of the game to the initial state of the board. In really difficult cases , such navigation does not happen quickly. Another drawback of the ZSG notation can illustrate the recording of the next move from the Go game :

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

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

    Fortunately, there is an easy way to deal with all these problems. Let's look at how the moves of 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 moves defined in ZoG macros are not available to the move generator. But what prevents us from abandoning macros and making descriptions of moves named? Here is what a 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 O-O
    4. d7 - d5 Pawn-move
    5. e4 x d5 Pawn-capture nw
    5. f6 x d5 leap2 w nw
    

    Note
    Attentive readers may notice that in the moves “for black” I used directions that did not correspond to the directions on the chessboard. This is due to the fact that “symmetry” is defined for black:

    (symmetry Black (n s)(s n) (nw sw)(sw nw) (ne se)(se ne))
    

    Roughly speaking, what is “north” for white is “south” for black, and vice versa.

    The usefulness of such a record is not obvious, but it has one important advantage. All the 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 be made more "speaking"). 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 the Go game is even more obvious:

    1. G19 drop-to-empty White Stone
    

    And it's all! If enemy stones are taken, in accordance with the rules of the game, there is no need to list them all in the description of the move. It is enough to indicate the initial and final displacement field (possibly with a sign of capture), the name of the move to be performed and the string of parameters passed to it. Of course, in order to complete the move, according to such a description, for decryption, you will have to turn to the module for generating moves, but ZoG does it!

    Note
    In very rare, one might say exotic cases , it may be necessary to complete a move consisting only in taking a piece (one's own or one's opponent). A record of such a move, in a new notation, will look like this:

    1. x G19 capture-piece
    


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

    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 Black, on the second move, takes two pieces on d4 and f4. The preliminary “transformation” of figures into XChecker is a feature of the implementation and serves to prevent the possibility of re-taking “broken” figures on the same move. The phrase " partial 2 " describes the beginning of a "composite" move consisting of two "partial" moves. This form of description is inconvenient, because at the time of generating the first move, the length of the sequence of "partial" moves may not be known. Here's what this 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 the figures are superfluous. The capture of pieces should also not be indicated, since, in checkers, the capture is performed as a “side effect” of the move of the piece, and not according to the “chess principle”. A partial move will be encoded with a “ + ” at the beginning of the line. A single “ + ” signifies the completion of a “compound move” (in fact, this is a normal “partial” move containing a skip move - an empty line).

    Thus, using the named rules for executing moves, it was possible to create a universal notation that fully meets our requirements. Of course, it has nothing to do with either conventional chess or any other notation, but it so happened that the generally accepted notations for chess, checkers and other games also have nothing to do with each other. The visualization module can always convert the progress record to a more familiar form adopted for a particular game. Also, conversion to some other universal form, such as SGF , can be performed .

    Game life cycle


    Along with information on the placement of pieces on the board, the sequence of moves is an integral part of the state that changes during the game. In the simplest (and most common) case, one bit is enough to store this information, but ZoG provides a bit more options for implementing more complex cases. Here's what a sequence of moves for a Splut game might look like ! :

    (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 starting position, he will be able to destroy one of the opponent’s pieces, which will give him a serious advantage. For this reason, the first player must make one move (this makes it possible to prepare for the attack of the player located opposite, but not attack him), the second - two moves (this is also not enough to attack the opposing player), after which each player always makes three moves each.


    The label repeat 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 opportunity is to determine the course of movement. Here's what the description of the sequence of game moves may look like in which each player performs two moves (the first move is moving the piece, the second is taking the opponent’s piece):

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

    There is another possibility related to the description of moves by other people's pieces, 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 the opponent’s piece, the player must complete such a move! In ZoG it is impossible to describe the move " to choose " with your own or someone else's piece. If such an opportunity is necessary in the game (for example, in " Stavropol Checkers""), you have to make all the pieces neutral (by creating a player who is not participating in the game for this purpose) and determine for all players the ability to move with neutral pieces. As I said earlier, it’s much easier to initially allow players to move with any pieces (like 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 . Ludi, in 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 possibilities are deliberately simplified, which leads to cutting off entire 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 the execution of the course in which differ significantly. At the beginning of the game, part of the stones is "in the hand" of each of the players. Until the stones "in the hand" have run out, stones are thrown into the holes, one stone at a time. When the stones "in the hand" end, the second phase of the game begins, associated with the redistribution of the thrown stones. This is not to say that this game cannot be described in ZRF (the ZoG description language ), but due to the limitations of ZoG , such an implementation would be extremely confusing (which would certainly not affect the quality of AI work in the best way). Let's see how a description of such a game might look in an “ideal world”:

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

    Here, each turn-order list defines its own repeating sequence of moves (differing in the mode of execution of the move). The label keyword defines a label, a transition along which can be formed when generating the next move. You can notice that here we proceed from the implicit assumption that such a transition always occurs after the second player’s move (otherwise, the sequence of moves will be violated). How to move to the next phase at an arbitrary point in time?

    (players South North)
    (turn-order
        (turn-order 
             (South p-i-move)
             (North p-i-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. The names of the labels in the labels lists are listed in accordance with the order in which the players are listed in the players list . The name used for the transition is determined depending on which of the players completed the move last. If it was North , it will go to the first label, otherwise to the second. If any of the names in labels will not be used, the corresponding position can be filled with a dash.


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

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

    Having made the transition to repeat , the player will return to repeat the last move (the label closest to the current position in the list of moves will be valid). I like Perl 's implicit definition approach . Implicit generation of control structures can greatly simplify the description. Since repeat moves can be used in many games, repeat labels preceding each move can be implicitly generated:

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

    Moreover, since the sequence of moves is fully consistent with the enumeration of players in players , you can automatically generate the entire phrase turn-order :

    (players South North)
    

    The simpler the description, the better.

    Broken Invariant


    The main thing that I don't like about ZoG can be expressed in one word - checkmated . At first glance, this is just a condition (very common in games of a chess family) that connects the end of a game with the formation of a dull situation . Alas, upon closer inspection, simplicity is deceiving. The use of this keyword implies not only performing, after each turn, checks of the completion of the game, but also imposing a certain “behavior” on the player.

    And the module for generating moves and AI should take into account that after completing a move, your king should not be under the check . At the same time, it is not enough to check only for a converging piece, the check may well be " open". Correctly implementing all the necessary checks is not easy (in any case, this was not possible in ZoG ):



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

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


    Everything becomes even more complicated if a player can have several kings. In Tamerlane's Chess , the royal pawn turns into a prince (in fact, into a second king). If this happened, you can only win by eating the first king (any of the two) and matting the second. In this game, you can get the third king by spending twice on the field of transformation "pawn pawn"! The expressive capabilities of " checkmated " are not enough to adequately describe this situation.

    Another difficulty may be the matting process itself. So in the Mongolian version of chess ( Shatar), the result of matting depends on the order in which the pieces perform sequential “checkers”. The result may be a victory and a draw (for example, with a mate pawn) and even defeat (it is forbidden to use a knight to checkmate, but you can check). A little less exotic, in this regard, are Japanese Shogi. In this game, it is forbidden to checkmate with a pawn reset, but you can check with a pawn reset and also checkmate with a pawn move.

    Note
    Стоит упомянуть о ещё одном важном моменте. В некоторых играх, таких как Ритмомахия, вариантов завершения может быть несколько. Наиболее очевидный способ одержать победу, связанный с уничтожением фигур противника, в то же время, является наименее предпочтительным. Для более значимой победы, следует выстроить фигуры, на территории противника, определённым образом.

    Следует различать типы побед (а также поражений и ничьих) на уровне описания игры, поскольку тип завершения игры может потребоваться игроку. Кроме того, должна иметься возможность назначения числовых приоритетов различным вариантам завершения. При одновременном выполнении различных условий завершения, должно рассматриваться то из них, которое имеет максимальный приоритет.

    Obviously, it is necessary to separate the logic of checking the completion of the game from checking the king’s hit under the check, which is, in fact, an invariant checked after each move. Violation of the invariant makes the execution of the move impossible (the move is removed from the list of available moves). Here's how (simplified) a check of a king’s hit under the check for “Tamerlane Chess” might look:

    (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 check should be performed only for my own kings (I used the predicate my?, Because, with the support of coalitions, the friend? Attribute will be satisfied not only for my own figures, but also for the figures of a friendly player). A situation is permissible (and desirable) in which an enemy king falls under the check after completing a move, but with respect to his own king, such a situation should be impossible! Provided that the verification of such invariants is supported, checking the completion of the game becomes obscene. 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 the games of this family is associated with the implementation of the "majority rule". In almost all checkers games, a move with capture is mandatory. Also, for the majority of games of this family, the execution of “chains of captures” is characteristic, within one move. The figure who performed the capture continues to take other pieces, if possible. In most games, the player must complete the chain of captures, but there are exceptions to this rule, such as Fanorona .


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

    (option "maximal captures" true)
    

    This setting is suitable for " International Drafts ", but in " Italian Drafts " the majority rule is formulated differently. In this version of the game, if there are several options with the same number of captures, you need to choose the option in which more turned checkers (dames) are taken. ZoG developers have envisioned this by entering the following setting value:

    (option "maximal captures" 2)
    

    When using this setting, not only the number of figures taken is taken into account, but also their type. Unfortunately, it is impossible to foresee everything. Here is how the "majority rule" is formulated in " Old French Checkers ":
    If during a series of captures it is possible to chop the same number of pieces with a simple checker or queen, the player must take the queen. However, if the number of checkers to be removed is the same in both cases, but there are opponent’s dames in one <branch> (or there are more of them), the player must choose this option, even if then you have to cut with a simple checker, not a dame .
    Of course, at present, almost no one plays this option of checkers, but its very existence clearly demonstrates the shortcomings of the "hardcode" implementation. Using the invariant mechanism allows you to implement all possible variants of the "majority rule" in a universal way. For the "Old French Checkers" 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 the move correctly fill in the local variables:

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

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

    Note
    Есть еще одна возможность ZoG, используемая в реализации шашек. В случае если есть возможность взятия или «тихого хода», ход, выполняющий взятие, считается более приоритетным:

    (move-priorities jumptype nonjumptype)
    (piece
          (name Checker)
          (image Red "images\Checkers\Shaag\chkrRM.bmp" "images\Checkers\chkrRM.bmp"
                 Black "images\Checkers\Shaag\chkrBM.bmp" "images\Checkers\chkrBM.bmp")
         (moves
             (move-type jumptype)
             (checker-jump nw)
             (checker-jump ne)
             (move-type nonjumptype)
             (checker-shift nw)
             (checker-shift ne)
          )
    )
    

    Подобное объявление приоритетов также становится излишним, при использовании механизма нарушаемых инвариантов.

    Заключение


    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 not even for a year), but, in this case, the process, for me, is much more important than the result. I do not plan to derive any benefits from this work and, especially, I do not plan to close the source codes of the project. If some kind of license will be used, then I will try to find the most liberal option. I will be glad if someone joins my work, but if there are none, I will not worry too much.

    Viam supervadet vadens .

    Also popular now: