Dagaz: Kicks to common sense (part 4)

Let the saber whistle the whirlwind!
Kostaki is not a judge for me!
Kostaki is right, so am I!
...

Kozma Prutkov " New Greek Song "

Mat and Pat , castling and taking on the aisle . Can any other game (besides Chess) deliver a big headache to developers? Of course! And I'm sure most of you know this game ...

7. Turkish strike

The basis of the problem again lies forced moves. It would be completely not interesting to play most of the variants of checkers , without following the rule of obligatory capture. If you can eat a player's figure, you need to eat it (even if it is very unprofitable for you)! This principle underlies the whole matching 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 checkers games. Although it uses the "checkered" principle of combat (jumping over the opponent's figure), differences from the usual checkers are perhaps more than similarities. The game does not use a chessboard. There is no transformation of figures. The figures go "only forward" (vertically or diagonally) on one cell and, having reached the last line, lose the ability to perform "quiet moves". From this position, the figures can still continue to move, since it is allowed to beat the opponent’s pieces in any direction. The most important difference from other checkers games is the fact that taking in “Ossetian checkers” is not obligatory. And the main unifying factor is that in one move you can take several enemy pieces at once! The capture is carried out “along the chain” - after completing the “percussion” move, the figure can continue moving, provided that in the next step it takes another figure.


So, taking in checkers games is an integral move, in the process of which the position on the board can change. If you do not see this problem, look again carefully. In the most ancient versions of the game (Ossetian and Turkish), the taken pieces are simply removed from the board as you progress. At the same time, the same board field can be visited several times. The only limitation in force in the “Turkish drafts” is that in the process of fighting figures, the woman cannot change the direction of movement to the opposite. This way of fighting (in honor of the game that gave birth to it) was called the “Turkish strike” and its power (especially in the performance of the long-range lady) is terrifying:



In most modern versions of the game, there are special rules that make the implementation of the "Turkish strike" impossible. Taken pieces remain on the board until the end of the turn and cannot be taken again (in order to distinguish them from other pieces, in the process of making a “stroke” turn, they are usually turned over, and upon completion they are removed from the board all at once). Another important question concerns exactly how the rule of obligatory capture should be interpreted when performing a composite move. And here are possible options ...

It is easiest to assume that at any stage in the execution of a move, taking is mandatory. Having started the “shock” course of one of the figures, we are obliged to continue it as long as there is the possibility of the battle of enemy figures. In other words, the “chain of taking” cannot be interrupted; it must be passed to the end. I know only one game in the family of drafts games (with obligatory take) where this rule does not work. For us, this is exotic, but in Madagascar Fanorón is very popular.



First of all, a completely unusual way of taking figures is striking. Fanorona belongs to a rare variety of “contact” checkers (another interesting representative of this trend is the modern game Bushka ). In order to remove the enemy figure from the board, you need to come close to it, or move away from it. Not only the attacked figure is removed, but also all the enemy figures standing behind it in the direction of the attack. Perhaps, this moment is better to illustrate :



The capture in Fanorone, as well as in checkers, is an integral move. The attacking figure can continue to take more and more new enemy pieces, if it has such an opportunity. The only thing that is forbidden to her is, in the course of the battle, to change the direction of movement to the opposite (almost as in “Turkish drafts”). The unique difference of Fanorona from other checkers games is that the player can interrupt the chain of captures at any time, at his discretion (annoyingly, in some implementations of the Android game, an important element of the game mechanics is missing). In this case, the first take is required. You can not perform a "quiet" move, if there is the possibility of fighting enemy figures.

Some elementary rules, connecting with others, form more and more new types of games. In most of the drafts, the take series must be completed. In many of them, on the last horizontal line, ordinary figures are transformed into queens. But what if the transformation occurred in the process of "cutting"? Different variants of the game approach this issue differently.

In Armenian and Russian drafts, the transformation takes place in the process of combat - the figure that has become a lady, continues to take the new rules. In Turkish, Old French and English checkers, transformation occurs only at the end of a turn. In Turkish drafts, the figure can continue to fight (if there is such an opportunity), but since the "cutting" back is prohibited, the figure remains in the zone of transformation. In the old French and English versions, a simple checker on the last horizontal line just cannot continue moving and stops.


Amusing metamorphosis undergoes this rule in international, 100-cell checkers. The transformation, as before, occurs only at the end of the turn, but “cutting back” is not only allowed, but also obligatory! The figure must continue to fight, 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 another, last question, but it will give odds to all the previous ones. The player is obliged to complete the "chain" of taking, but what to do if there are several such "chains"? Which of the possible moves to choose? Here opinions also diverge. The most liberal rules adhere to the "Russian checkers". In them, the player can choose any of the possible options for taking. In Turkish and international drafts, there is a “majority rule” in its classical interpretation: of all the possible options for taking, the player must choose the one in which the largest number of enemy pieces are taken (simple ones are figures or ladies — it doesn't matter).

In all its glory, "social inequality" appears in the "Italian drafts". In this game, a simple checker not only can not beat the lady, but is also valued below! It is required to beat the maximum possible number of opponent pieces, and with an equal number of them, take the maximum number of queens. This discrimination reaches its apogee in another Italian game. In Damone , in addition to the ladies , there are also "emperors", inviolable for all subordinate figures. By this, the 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 prohibited - a simple checker will never become emperor).



Priority of a different kind operates in the "Portuguese checkers" - if there is a choice between taking a woman or a simple game, the player must cut it with a woman. The most difficult formulation of the “rule of majority” is in the “Old French Checkers”. Let me quote :

• Initially, the choice of two options for taking was voluntary, regardless of the quality and number of checkers, and only in 1653 the majority rule was introduced (for serial taking, the player must chop the maximum possible number).
• 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 drafts removed is the same in both cases, but in one “branch” there are enemy 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.
• In addition, the rank of the removed checkers does not matter, the serial take is subject to the number: you need to take the checkers to the maximum. When choosing to take either 3 simple checkers or 2 queens, the player must take 3 simple ones.

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

• Partial moves implemented by the add-partial command
• Move priorities defined by move-priorities
• A number of clever 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 takes in a long composite move. In addition, this command allows you to transform a piece (for example, checkers into a queen) when completing any partial move (this feature is useful in Russian Checkers). Once the capture is completed, the checkered figure cannot continue moving in a “quiet” movement. She must continue to take the opponent's pieces. Obviously, some kind of possibility is required to separate partial moves by type. And there is such an opportunity:


If the move type is specified in the add-partial command ( jumptype in the example), the composite 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 record means that if there is a possibility of a take, the “quiet” move cannot be performed. More than two types can be listed in the list of priorities, but the possibility of performing a type of a move completely prohibits all moves, the types of which follow 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 should take a greater number of ladies:

 (option "maximal captures" 2) 

This is where the possibilities end. For example, it is impossible to specify that one should take the minimum number of figures (why this may be needed is another question). The option command is useful in the implementation of Fanorona:

 (option "pass partial" true) 

The fact is that a player cannot simply take and stop performing a composite move. This feature must be explicitly resolved. I really do not like both the “magic” of the option command and the implementation, with its help, of skipping moves (in this case, partial ones), but this is perhaps a topic for another conversation.


In general, the mechanisms provided by Zillions of Games are quite efficient, if not for one thing. With their help, it is impossible to implement “Ossetian Kena” mentioned under the first spoiler in this article. The problem is that starting a composite move, we do not know whether the enemy’s figures will be “eaten” in the process of its execution. Ken can jump over the friendly kens and beat the hostile ones, alternating these partial moves in a random order, as part of a composite move.

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

It is less obvious that the option " pass partial " will have to be set to true (the possibility of interrupting the player’s composite move). When jumping, the friendly ken is not deleted. Finding the first closed loop, the program will jump on it forever. In a reduced form, the rules are completely non-playable. Both sides prefer to conduct meaningless maneuvers, rather than risk their pieces, substituting them for the enemy’s battle (this can be seen in the video below the first spoiler).

Of course, I would not have started this whole conversation if I did not know how to fix it. For a start, it is worthwhile to figure out what is stopping us in ZRF. I see several problems:

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

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

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

About the fact that combining the functions of moving figures and completing the generation of a move is not a good idea, I have already written many times before. Fortunately, this has been fixed in Axiom . As for priorities, I generally think this decision is extremely unfortunate. There is a more universal approach, which allows to realize both priorities and the “rule of majority” and much more. Let's see how the definition of “Ossetian Kena” could look like in an ideal world:


Pre- and post actions allow the logic to be divided into relatively independent fragments. For example, a check on the transformation into a woman, in this version of the checkers, should be carried out at the end of any partial move, which has not yet been turned into a figure ( Man ). Although this is a small piece of code, there’s absolutely no need to clutter up the implementation of three different types of moves. By 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 describing the type of figure, looks more logical).

Other checks are located in the global description section of pieces . This code is executed before and after the completion of the entire composite move (it is here that the transformation of the figures into “International Checkers” should be carried out). Here, with the phrase attribute, you can define variables that are available at any stage of the execution of a compound stroke. In capturing-count, we count the total number of pieces 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 is good if the moves are generated in the direction of reducing the number of pieces taken (then new variants will be discarded during the check), but we cannot guarantee such an order of generation of moves! Here you can go for a little trick. In addition to testing, you can create a pending condition associated with each generated move. If, when generating a subsequent move, the value of max-capturing-count changes, it will be necessary to recheck all previously generated moves (they will not have to be regenerated again) and weed out those for which the condition is no longer fulfilled.

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