Dagaz: Kicks to Common Sense (Part 4)

    imageLet the sword whistle with a whirlwind!
    Kostaki is not my judge!
    Kostaki is right, and I am right!
    ...

    Kozma Prutkov " Greek song "
     

    Mat and stalemate , castling and taking on the aisle . Can any other game (except Chess) cause a big headache to developers? Of course! And I’m sure that most of youknow this game ...

    7. Turkish strike


    At the heart of the problem are again forced moves. To play most of the checkers without fulfilling the rule of compulsory capture would not be interesting at all. If you can eat a player’s figure, you need to eat it (even if it’s very disadvantageous for you)! This principle underlies the whole combinational game of checkers. I know only one game from this family in which the mandatory take rule is not used (and this is a good example of excluding only the confirming rule).

    Ossetian checkers, apparently, are one of the oldest drafts games. Although it uses the "checkerboard" principle of combat (by jumping over the opponent’s piece), there are probably more differences from the usual drafts than similarities. The game does not use a chessboard. There is no transformation of figures. The pieces move “only forward” (vertically or diagonally) by one cell and, having reached the last line, lose the ability to perform “silent moves”. From this position, the figures can still continue to move, since it is allowed to beat enemy figures in any direction. The most important difference from other checkers games is the fact that taking in the "Ossetian drafts" is not mandatory. And the main unifying factor is that you can take several enemy pieces at once with one move! The capture is carried out "along the chain" - by performing a "shock" move, 

    To the question of Ken
    Currently, in the territory of Ossetia, another interesting checkers game is common. In Qena play our usual 8x8 board. The initial placement is similar to Turkish Drafts . On the last horizontal, the figures are transformed into long-range dams (Pepper). The moves of the pieces are also carried out according to the rules similar to those used in the “Turkish Drafts”, except that the unconverted figure (Ken) is allowed to beat back, as well as jump over friendly kenas (without a fight, of course), standing nearby (there is no similar rule in none of the other traditional checkers games).

    The rule of jumping over friendly pieces can be understood in different ways. Can I jump back (if taking back is allowed)? Is it allowed to jump over several of your pieces “in a chain” and, if so, is it possible to cross jump over your pieces with the capture of the enemy? Unfortunately, all the descriptions of Kenov that I managed to find bypass these questions. The only thing they agree on is that such jumps are not allowed to turned ladies (you must not jump over your ladies either). To sort this out somehow, I developed my Kenov implementation and uploaded a video on YouTube:



    A few days ago, my expectation was a success. Sultan Ratrout provided me with detailed comments on this game. Here is what he writes:

    There are some similarities between the two checkers games "Kena" and "Kens" Your implementation of the game is correct. It's called Ossetian Kena or simply Kena.
    ...
    Kens is a game influenced by the Osseitan Kena. As for Kens rules, they are found on the websites “di.fc and boardgamsgeek”. Kens has the same rules of Turkish checkers except that Kens cant jump a friendly piece backwards and kens cant jump more than one friendly piece consecutively.
    ...

    It turned out that there was not one but two similar games, “Kens” and “Kena” (it is possible that this separation occurred precisely because of an insufficiently detailed description of the rules). In one of them, jumping back and down the chain is not allowed, in the other it is allowed. Apparently, in both cases, capture is mandatory.

    Having detailed descriptions of games in publicly available sources is really a sore point. We almost lost Petteia and Latrunculi simply because the ancient Greeks and Romans, with all our love for these games, simply did not bother to describe their rules! Though somehow (and most likely wrong) we can play Khnefatafl only thanks to the notes of Karl Linnaeus. Attempts to reconstruct ancient games resemble an intricate detective story .

    We have already lost many board games and continue to lose them. The complete rules of " Air Battle " are now known to only one nameless collector. We know that Stalin , apparently, loved board games, but it seems that now no one will remember how these figures walk . I appeal to all readers. If you know the rules of exotic and even the most ordinary board games - share with them. Check the descriptions in Wikipedia and other publicly available sources. Write to people collecting game rules, do not hesitate to correct them if they are mistaken. Do not give this knowledge an abyss irrevocably!

    So, taking in checkers games is a composite move, during which the position on the board may change. If you do not see this as a problem, look carefully again. In the most ancient versions of the game (Ossetian and Turkish), the pieces taken are simply removed from the board as the move progresses. At the same time, the same board field can be visited several times. The only restriction in force in Turkish Checkers is that in the process of the battle of pieces, the lady cannot change the direction of movement to the opposite. This method of battle (in honor of the game that gave rise to it) was called the “Turkish strike” and its power (especially in the performance of a long-range lady) is horrifying:



    In most modern versions of the game, special rules apply that make the execution of the “Turkish strike” impossible. Taken pieces remain on the board until the end of the move and cannot be taken again (to distinguish them from other pieces, during the execution of the “shock” move, they are usually turned over, and when it is finished, they are removed from the board all at once). Another important question concerns how exactly the rule of compulsory capture should be interpreted when performing a compound move. And here are the options ...

    It is easiest to assume that at any stage of the execution of a move, capture is mandatory. Having started the “shock” move of one of the pieces, we are obliged to continue it until there is a possibility of the battle of the enemy pieces. In other words, the “chain of captures” cannot be interrupted; it must be completed to the end. In the family of checkers games, I know of only one game (with a mandatory capture) where this rule does not apply. For us, this is exotic, but in Madagascar Fanorona is very popular.



    The first one that catches the eye is a completely unusual way for us to take figures. Fanorona is a rare variety of “contact” checkers (another interesting representative of this trend is the modern Bushka game ). In order to remove the opponent’s piece from the board, you need to come close to it, or move away from it. Not only the attacked figure is deleted, but also all the enemy figures standing behind it in the direction of the attack. Perhaps this moment is better illustrated :



    Taking in Fanoron, as well as in checkers, is an integral move. The attacking piece can continue to take more and more enemy pieces, if it has such an opportunity. The only thing that is forbidden to her is, during the battle, to change the direction of movement to the opposite (almost like in Turkish Drafts). A unique difference between Fanorona and other checkers games is that the player can interrupt the chain of tricks at any time, at his discretion (it’s unfortunate that in some implementations of the Android game such an important element of the game mechanics is missing). In this case, the first take is mandatory. You cannot perform a “silent” move if there is the possibility of battle of enemy figures.

    Some elementary rules, connecting with others, form more and more new varieties of games. In most of the checkers variations, a series of captures must be completed. In many of them, on the last horizontal, there is a transformation of ordinary figures into damsels. But what if the transformation occurred in the process of “cutting”? Different versions of the game approach this issue in different ways.

    In Armenian and Russian drafts, the transformation takes place during the battle - the figure who has become a lady continues to capture according to the new rules. In Turkish, Old French and English drafts, the transformation occurs only at the end of the course. In Turkish drafts, the figure can continue the battle (if there is such an opportunity), but since the “cutting” is prohibited back, the figure remains in the transformation zone. In the old French and English versions, a simple checker on the last horizontal simply cannot continue to move and stops.

    By the way
    This problem is originally solved in another ancient game system - " Senegalese Checkers ". The transformation of figures in this game does not occur. Felling and backward moves are prohibited - pieces can only move and “chop” forward and sideways. Checkers that have reached the last horizontal are simply removed from the board! This rule completely deprives players of the incentive to advance figures. It is beneficial to play the game in the center of the board as long as possible! As soon as the pieces lose the ability to chop each other - the game ends. The player with the most pieces left wins.

    This rule undergoes a funny metamorphosis in international, 100-cell checkers. The transformation, as before, occurs only at the end of the course, but the “felling” back is not only allowed, but also mandatory! The figure must continue the battle and if in its process it leaves the last horizontal - there will be no transformation, it will remain a simple figure!

    We have not considered one more, the last question, but it will give odds to all the previous ones. The player must complete the “chain” of captures, but what if there are several such “chains”? Which of the possible moves to choose? Opinions also differ here. The most liberal rules are followed by Russian Drafts. In them, the player can choose any of the possible options for taking. In Turkish and international drafts, the “majority rule” applies in its classical interpretation: of all possible capture options, the player must choose the one in which the greatest number of opponent’s pieces are taken (it’s simple figures or queens - it does not matter).

    In all its glory, “social inequality” appears in “Italian Checkers”. In this game, a simple checker can not only beat the lady, but is also valued lower! It is required to beat the maximum possible number of opponent's figures, and if their number is equal, take the maximum number of queens. This discrimination reaches its climax in another Italian game. In Damone , in addition to the ladies , there are also "emperors", untouchable for all lower figures. This game resembles Dablot , but, unlike the latter, transformations in it are still possible. Simple checkers can turn into ladies, and ladies into emperors (repeated transformations are forbidden - a simple checker will never become an emperor).



    A priority of a different kind is valid in “Portuguese Checkers” - if there is a choice between taking a queen or a simple checker, the player must chop with a queen. The most complex wording of the "majority rule" is valid in the "Old French Checkers". Let me quote you :

    • Initially, the choice of two capture options was voluntary, regardless of the quality and number of drafts, and only in 1653 the Rule of majority was introduced (in case of serial capture, the player must cut the maximum possible amount).
    • 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 in one “branch” there are opponent's dames (or there are more of them), the player must choose this option, even if then he has to cut with a simple checker, not a dame.
    • In addition, the rank of the removed checkers does not matter, the serial capture is subordinate to the number: to take the checkers to the maximum. When choosing to take either 3 simple checkers or 2 queens, the player must take 3 simple.

    I think you already understood that, in terms of implementation, checkers games are no easier than chess. What does Zillions of Games provide to make life easier for developers? Consider these features:

    • Partial moves implemented by add-partial
    • Move priorities determined by move-priorities
    • A number of tricky settings supported by the option command

    Without the support of partial moves, there would be no talk of any implementation of checkers. The add-partial command allows you to combine a sequence of captures into a long composite move. In addition, this command allows you to turn a piece (for example, checkers into a queen) at the end of any partial move (this feature is useful in Russian Drafts). Once having completed the capture, the piece in checkers cannot continue the move with a "silent" movement. She must continue to take enemy pieces. Obviously, some kind of opportunity is required to separate partial moves by type. And there is such an opportunity:

    Types of moves
    (define man-jump-add (
       if (not-in-zone? promotion-zone)
          (add-partial jumptype)
       else
          (add-partial King jumptype)
    ))
    ...
    (piece
       (name Man)
       ...
       (moves
          (move-type jumptype)
          (man-capture nw) (man-capture ne)(man-capture sw)(man-capture se)
          (move-type nonjumptype)
          (man-shift nw) (man-shift ne)
       )
    )
    


    If the type of move is specified in the add-partial command ( jumptype in the example), a compound move can be continued only by moves of this type. Types are also used to set the priority of moves:

    (move-priorities jumptype nonjumptype)
    

    This entry means that if there is a possibility of capture, a “silent” move cannot be performed. You can list more than two types in the priority list, but the ability to execute a move of any type completely prohibits all moves, the types of which follow further down the list. How is the "majority rule" defined? Very simple and hardcore:

    (option "maximal captures" true)
    

    You can specify that with an equal number of figures you should take a larger number of ladies:

    (option "maximal captures" 2)
    

    The possibilities end there. For example, you cannot specify that you should take the minimum number of figures (why this might be needed is another question). The option command is also useful in the Fanorona implementation:

    (option "pass partial" true)
    

    The fact is that a player cannot just pick up and stop executing a compound move. This possibility must be explicitly allowed. I really do not like the “magic” of the option command itself or the implementation, with its help, of skipping moves (in this case, partial), but this is perhaps a topic for another discussion.

    But what about the Turkish strike?
    This is all complicated. Taken, during the execution of the composite move, the figures must be marked (in order to exclude the possibility of their repeated capture) using the attributes or the transformation of the figures. Upon completion of the composite move, all marked pieces are removed from the board. The problem is that the ZoG move generator does not provide any post-processing capabilities. As a result, it is necessary to determine which of the partial moves is performed last.

    The code is very confusing (and in the case of Fanorona, for example, it is not feasible at all, since the player decides to complete the move). Not surprisingly, such implementations are full of errors. I often saw how part of the pieces taken is not removed from the board at the end of the composite move. There are more complex cases. Can you find the error in the following code?

    Russian checkers
    (define international-checker-add
       (if (not-flag? more-captures-found?)
           (if (in-zone? promotion-zone) (change-type King) )
           add
          else  
             (add-partial jumptype)    
       ) 
    )
    (define international-checker-jump-find
       mark
       (if (on-board? $1)  
         $1    
         (if (and enemy? (empty? $1)(not captured?) ) 
            (set-flag more-captures-found? true)
         )
       )
       back
    )
    (define shashki-jump   
     (
       $1 
       (verify enemy?) 
       (verify (not captured?))    
       (set-attribute captured? true)
       (set-flag more-captures-found? false)              
       (set-flag short-jump? true)              
       $1                                   
       (international-checker-jump-find $1)
       (international-checker-jump-find $2)
       (international-checker-jump-find $3)           
       (opposite $1)               
       (if (flag? more-captures-found?)                    
           (set-attribute captured? true)     
        else  
           mark  
           capture                            
           a0 
           (while (on-board? nxt) 
             nxt
             (if captured? capture (set-flag short-jump? false))           
           )
           back  
         )
       $1 to
       (verify empty?) 
       (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
       (if (in-zone? promotion-zone) (change-type King))
       (international-checker-add) 
     ) 
    )
    ...
    (variant
       (title "Shashki (Russian Draughts)")
       ...
       (piece
          (name Checker)
          ...
          (attribute captured? false)
          (moves
             (move-type jumptype)
                 (shashki-jump nw ne sw)
                 (shashki-jump ne nw se)
                 (shashki-jump sw nw se)
                 (shashki-jump se sw ne)
            (move-type nonjumptype)
                 (checker-shift nw)
                 (checker-shift ne)
          )
       )
       ...
    )
    


    This is part of a very successful package of "checkers" games, including Belarusian chess "(with the correctly working" checkmate ") and" Liberian checkers "(with a very witty ban on completing the game with a three-fold repetition of the position), but the implementation of" Russian Checkers "in it contains an annoying mistake.

    Answer

    In the first case, everything is fine. The white checker takes two black ones and turns into a lady. The second diagram illustrates the error. The white checker takes the black one, turns into a queen and remains on the last line, although it should , according to the rules of the “Russian Drafts”, take the next piece with the queen’s move.

    By locating the error, fixing it is simple. It is all about the international-checker-jump-find checks that determine if the move has a continuation. This macro checks whether it is possible to take the next figure from the target position, but does it according to the rules of an unformed figure. This works for International Drafts, but in Russian Drafts it does not take into account all the possibilities. My fix is ​​not too elegant, but solves the problem:

    Correction
    +(define shashki-checker-jump-find
    +   mark
    +   (while (and (on-board? $1) (empty? $1))
    +     $1
    +   )
    +   (if (on-board? $1)  
    +     $1    
    +     (if (and enemy? (empty? $1)(not captured?) ) 
    +        (set-flag more-captures-found? true)
    +     )
    +   )
    +   back
    +)
    (define shashki-jump   
     (
       $1 
       (verify enemy?) 
       (verify (not captured?))    
       (set-attribute captured? true)
       (set-flag more-captures-found? false)              
       (set-flag short-jump? true)              
       $1                                   
    +   (if (in-zone? promotion-zone)
    +       (shashki-checker-jump-find $1)
    +       (shashki-checker-jump-find $2)
    +       (shashki-checker-jump-find $3)           
    +    else
           (international-checker-jump-find $1)
           (international-checker-jump-find $2)
           (international-checker-jump-find $3)           
    +   )
       (opposite $1)               
       (if (flag? more-captures-found?)                    
           (set-attribute captured? true)     
        else  
           mark  
           capture                            
           a0 
           (while (on-board? nxt) 
             nxt
             (if captured? capture (set-flag short-jump? false))           
           )
           back  
         )
       $1 to
       (verify empty?) 
       (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
       (if (in-zone? promotion-zone) (change-type King))
       (international-checker-add) 
     ) 
    )
    


    If the figure is in the transformation zone, we use a special check, with the omission of empty fields in the direction of the enemy figure. The next partial move will already be calculated according to the rules of the dam move, so there will be no changes required.

    By the way, I already mentioned in previous articles that the descriptions of the moves of the ladies look simply monstrous. For some reason, the add-partial command does not work inside the loop (the program crashes), and the lady, in all variants of checkers with long-range dams (except for Thai ones ), must have a choice of which free field, after the figure taken to her to land. Of course, the solution was found:

    The course of the ladies
    (define international-king-jump1      
     ( 
       (international-king-work) 
       to
       (verify (position-flag? allowed?)) 
       (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
       (international-checker-add)
     )  
    )
    (define international-king-jump2      
     ( 
       (international-king-work)
        $1 (verify empty?) to
       (verify (position-flag? allowed?)) 
       (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
       (international-checker-add)
     )  
    )
    (define international-king-jump3      
     ( 
       (international-king-work)
        $1 (verify empty?) $1 (verify empty?) to
       (verify (position-flag? allowed?)) 
       (verify (or (not-flag? short-jump?) (flag? more-captures-found?)))
       (international-checker-add)
     )  
    )
    ...
    (variant
       (title "Shashki (Russian Draughts)")
       ...
       (piece
          (name King)
          ...
          (moves
             (move-type jumptype)
               (international-king-jump1 nw se ne sw)
               (international-king-jump1 ne sw se nw)
               (international-king-jump1 sw ne nw se)
               (international-king-jump1 se nw sw ne)
               (international-king-jump2 nw se ne sw)
               (international-king-jump2 ne sw se nw)
               (international-king-jump2 sw ne nw se)
               (international-king-jump2 se nw sw ne)
               (international-king-jump3 nw se ne sw)
               (international-king-jump3 ne sw se nw)
               (international-king-jump3 sw ne nw se)
               (international-king-jump3 se nw sw ne)
               (international-king-jump4 nw se ne sw)
               (international-king-jump4 ne sw se nw)
               (international-king-jump4 sw ne nw se)
               (international-king-jump4 se nw sw ne)
               (international-king-jump5 nw se ne sw)
               (international-king-jump5 ne sw se nw)
               (international-king-jump5 sw ne nw se)
               (international-king-jump5 se nw sw ne)
               (international-king-jump6 nw se ne sw)
               (international-king-jump6 ne sw se nw)
               (international-king-jump6 sw ne nw se)
               (international-king-jump6 se nw sw ne)
               ...
          )
       )
    )
    


    The choice of the field on which the queen stops is transferred to the upper level, directly into the cycle of generation of the move. It works, but the abundance of "copy-paste" crawls out beyond all reasonable limits. Of course, there is also a cure for this, but it is even worse than the disease .

    In general, the mechanisms provided by Zillions of Games are quite functional, if not one but. It is impossible to implement the “Ossetian Kena” mentioned under the first spoiler in this article. The problem is that when we start the compound move, we don’t know whether the enemy’s pieces will be “eaten” during its execution. Ken can jump over friendly kenas and beat hostile ones, alternating these partial moves in random order, as part of a composite move.

    Obviously, “jumping” and “fighting” with ken must have the same type of move (otherwise it will not be possible to build a composite move, since add-partialcan take only one type), but this type of move cannot be given a higher priority, because, otherwise, simple movements will not be performed almost never. This means that the rule of “mandatory take” cannot be determined.

    Less obvious is that the " pass partial " option will have to be set to true (the ability to interrupt a compound move by a player). When jumping, the friendly ken is not deleted. Having discovered the first closed loop, the program will jump on it forever. In a reduced form, the rules become completely non-playable. Both sides prefer to conduct meaningless maneuvers, rather than risking their own figures, substituting them for an enemy battle (this can be seen in the video under the first spoiler).

    Of course, I would not have started this whole conversation if I did not know how to fix it. For starters, it's worth figuring out what is stopping us in ZRF. I see several problems:

    • Lack of pre- and post-processing during the generation of moves (complicates the logic, prevents implementation of the opposition to the “Turkish strike” in games like Fanorone)
    • Combining the functions to complete the generation of the move and move the pieces in the add and add-partial commands (one of the reasons why add-partial cannot accept several types of moves)
    • Using types of moves both to control the construction of a composite move and to set priorities (the priority mechanism acts only on the first partial move, but not on the composite move as a whole)
    • Lack of a universal mechanism for implementing the "majority rule" (using ZRF, correctly implementing the "Old French Checkers" is unlikely to succeed)

    In ZRF, the definition of a move generation algorithm is monolithic. There is no way to execute a single code (before or after the main algorithm), within the framework of generating an arbitrary move (possibly from some group), but there is a real need for this! Countering the “Turkish strike” is an excellent illustration of this.

    Due to the need to determine the last partial move (as part of a composite move), the code becomes completely unreadable and prone to various errors. Moreover, this approach is not compatible with premature interruption of a compound move (option " pass partial "). Of course, in Fanoron it is not required to fight the “Turkish strike” (due to the specifics of the mechanism of taking pieces, it is impossible), but games in which such an opportunity may be needed have a right to life.

    Regarding the fact that combining the functions of moving the pieces and completing the generation of the move is not the best idea, I have already written several times before. Fortunately, this has been fixed in Axiom . As for priorities, I generally consider this decision to be extremely unsuccessful. There is a more universal approach that allows you to implement both priorities and the “majority rule" and much more. Let's see how the definition of “Ossetian Kena” might look like in an ideal world:

    Broken Invariant
    (define invariant
       (check (>= capturing-count max-capturing-count))
       (set! max-capturing-count capturing-count)
    )
    (define goals
       (check-loss no-moves?)
    )
    (define check-promotion
       (if (in-zone? promotion)
           (promote King)
       )
    )
    (define check-friend
       (check is-friend?)
       take-piece
    )
    (define (man-move direction)
       (check direction)
       (check is-empty?)
       drop-piece
       add-move
    )
    (define (man-jump direction)
       (check direction)
       (check is-friend?)
       (check direction)
       (check is-empty?)
       drop-piece
       (add-move-part jump-type)
    )
    (define (man-capture direction)
       (check direction)
       (check is-enemy?)
       (increment! capturing-count)
       capture
       (check direction)
       (check is-empty?)
       drop-piece
       (add-move-part jump-type)
    )
    ...
    (game
       (title "Ossetian Kena")
       ...
       (pieces
          (attribute capturing-count 0)
          (pre  goals)
          (post invariant)
          (piece 
                (name Man)
                (pre  check-friend)
                (post check-promotion)
                (moves
                    (mode normal-type)
                    (man-move n)  (man-move w)  (man-move e)
                )
                (moves
                    (mode jump-type)
                    (man-jump n) (man-jump w) (man-jump e) (man-jump s)
                    (man-capture n) (man-capture w) (man-capture e) (man-capture s)
                )
          )
          (piece 
                (name King)
                ...
          )
       )
    )
    


    Pre- and post-actions allow you to break the logic into relatively independent fragments. For example, a check for turning into a queen, in this version of the checkers, should be performed at the end of any partial move by an unformed figure ( Man ). Although this is a small piece of code, there is absolutely no need to litter it with the implementation of three different types of moves. Repeating the same fragment three times, it is three times easier to make a mistake (of course, you can use macros, but in this case, using the phrase post in the description of the shape type looks more logical).

    Other types of checks are located in the global section of the description of pieces. This code is executed before and after the completion of the entire composite move (it is here that the figures should be transformed into "International Drafts"). Here, with the attribute phrase you can define variables that are available at any stage of the composite move. In capturing-count, we count the total number of figures taken. The invariant is that this value should not be less than the maximum number of pieces taken in all generated moves.

    But how can this work? It’s good if the moves are generated in the direction of reducing the number of pieces taken (then new options will be discarded during verification), but we cannot guarantee this order of generation of moves! Here you can go for a little trick. In addition to checking, you can create a pending condition associated with each generated move. If, during the generation of the next move, the value of max-capturing-count changes, you will need to re-check all previously generated moves (they will not have to be regenerated again) and weed out those for which the condition is no longer fulfilled. Is

    this mechanism similar to the one I proposed for the “optimized” calculation of the no-moves termination condition ?. It is too expensive each time to generate the moves only to determine the player’s loss. It is much more reasonable to register a pending check, generate moves in the usual way, and record the defeat after the fact, if the list of moves is empty. In the case of invariants, this mechanism is not used for optimization purposes, but to ensure their correct calculation. This is what I call the “ violated invariant ” and I believe that this concept will be very useful to me in developing the move generator. In any case, it is much more universal than the mechanisms offered by Zillions of Games and Axiom Development Kit.

    Also popular now: