Dagaz: Kicks to common sense (part 9)

... And everything will repeat as before:
Night ice channel ripples
Pharmacy, street, lantern.

Alexander Blok


Today, I want to talk about the problem, traditionally ignored by most board game developers. If a computer implementation of a game, like checkers or chess, correctly handles situations of winning (or losing) players (and this is also not easy ), the result is considered to be quite satisfactory. But what if the game is at a standstill? Players move pieces, without any hope of winning (and can continue to do so indefinitely).
')
When playing a person with a computer, this is not a problem (it is clear who will get tired first), but what to do if two bots are playing? To compare the “strength” of various AI variants, for example, a large number of games are required to be automatically played. Proper handling of "anyone's" in such a situation is vital. And it is highly desirable that it be carried out in strict accordance with the rules of the game.

2. Repetition

The most straightforward approach is used in games of the "Checkers" family. The party is interrupted if none of the players can win for a given number of moves. So, in our well-known Russian Checkers , a game is considered a drawn game if it cannot be won in 30 moves. More complex rules related to the specifics of "slow-moving ladies" are used in the English Checkers . If each of the opponents has one queen left, it is allowed to make no more than 20 moves, until recognition of a draw. If one opponent has three queens, and another has two, the latter has the right to demand that the game be played in no more than 40 moves. The International Checkers Rules describe all possible situations in more detail :

• If players for 25 moves made moves only with queens, without moving simple checkers and without taking a draw, a draw is declared.
• If a player has 3 queens at the end of the game, 3 queens and 1 simple, 1 lady and 2 simple, 3 simple checkers, 2 queens, 1 lady and 1 simple against a single lady or 1 lady against a single lady or a single lady, the player must 5 In a move, win, otherwise a draw is declared.
• If there are 5 ladies on the board (or 4 ladies and 1 simple checker) against 2 ladies, the strongest side must win 50 moves, otherwise a draw is declared.
• If the same position is repeated three (or more) times (i.e., the same arrangement of the checkers), moreover, the turn of the turn each time after the same side - a draw is also declared.

Variations of the last of the listed rules are often used in other games. In chess, a threefold repetition of the position (taking into account the sequence of the move) is one of the possible reasons for recognizing a " draw ". In some games (for example, Go ) to repeat the position is prohibited. I already wrote about the problem of "Ko" in this game. Briefly recall what is at stake:



If the repetition of the position were allowed, the players could continue this sequence of moves to infinity (by taking more and more new stones from the opponent). This can be fought by forbidding White to play C17, after Black’s move on D17, but repeating the position may be more difficult. In the game, situations of “triple Co.” and even more complex positions of “Eternal Life” are possible:



Inga's rules try to regulate this issue, but the result is difficult to be considered satisfactory. In order to distinguish the "combat" Co. from the "disturbing" requires high qualifications. A beginner is unlikely to handle this. In a simplified version of the rules, the position is simply forbidden to repeat. This approach is called “ superco ” and can determine the repetition of the position in two different ways:

• Positional Superco - an unconditional prohibition on the repetition of positions, without taking into account the sequence of the move
• Super Situational Situation - prohibiting repetition of a position, provided that the turn of the same player turns

In general, it is clear that the ability to compare different positions may be useful when implementing some board games (and vital for AI), but given the fact that you have to compare a lot, a simple element-wise comparison of positions may be too expensive. To solve this problem, well-known computer games developer Albert Lindsey Zobrist developed a simple and elegant method , named after him.

Zobrist hashing is applicable to most board games and its essence is simple. First of all, a table of random numbers is compiled (the more randomly the better), for each possible position of each figure. In the case of Chess, for each of the 64 board fields, 12 random values ​​will be required (one for each type of pieces, taking into account the color). Further, a hash is compiled by " adding modulo 2 " of numbers taken from the table for the corresponding arrangement of the pieces on the board. Of course, if the hash values ​​for the two positions coincide, this does not mean that the positions are the same. The probability of collisions always remains, but the use of this method allows minimizing the number of elementwise comparisons of positions.

It is important that such a hash is obtained additive . It is not necessary to view the entire position each time, building a hash from scratch. We can “move” the piece across the board, using only hash. To do this, you must remove from the hash the value corresponding to the old position of the shape and add a new one (both of which are performed by the xor operation). Zobrist hashing is a very convenient technique and is used in most computer implementations of board games.

Of course, in ZoG it is also used (in Axiom , for sure), but only for internal needs. The condition for stopping the game with a triple repetition of the position “nailed” in the exe! Axiom allows you to redefine the behavior (to complete the game with a defeat instead of a draw) or to detect the first repetition of a position instead of the third, but while working as an engine for ZoG, he cannot cancel this test either. To me personally, such unchangeable “default behavior” has spoiled quite a few nerves.


The absence of any possibility of setting up a repeat position check in ZoG, I consider one of the most serious design errors of this program. Along with “checkmated” and “maximal captures” , this option is worthy of a bronze monument being cast in honor of it, on the theme “never to be done”. With the help of ZRF, you can only override the behavior when a threefold repetition of the position is detected, but no more. By default, the following definition applies:

 (draw-condition (White Black) repetition) 

One thing is that I can’t set up this check in any way (for example, to detect the first repetition of a position, and not the third one) is already very bad, but the fact that I cannot turn off this check when it only hinders is just awful! In my project, I would use (and hopefully still use) something like the following definition:

 (not-situation-repeated? 1 1) 

This is Ko . The first argument determines which counting of the position must be detected, and the second - the depth of the search. And it should be a universal expression that can be used not only in the condition of completing the game (as in ZRF), but also in any invariant used by the move generator (since in Gu the repetition of the position should prohibit the move and not interrupt the game). Of course, it should also be possible to use the predicate * -position-repeated? , to determine the positional Co., along with situational.

Perhaps for the sake of all the above, it would not be worthwhile to plot this article, but Zobrist hashing found another unexpected use. There is one truly legendary game that connects " Checkers " and " Tic-tac-toe ". Also, as in the African " Bolotoudou ", it is required to build lines "3 in a row" from its stones in order to shoot the stones of the enemy, but, unlike the latter, for this game there are options that prohibit taking the build by building the same row two times in a row.



It is easy to notice that in the video implementation , such a check is not performed and it is not accidental! I find it difficult to come up with a requirement that would be more difficult to implement on ZRF. This check should control the repetition of the position, but not all, but only its parts. If three stones make up a line ("the mill"), their repeated location in the same places, in one turn, should be either prohibited or should not lead to taking. But even a hash can be built only partially!


Here, we move along the chosen direction and successively add three positions to the hash if there are friendly stones on them. After that, we check if such a hash was formed two moves back. It is implied that the hash keys of all stones are unique, for example, formed on the basis of the attribute value set when adding stones to the board:


With the removal of enemy stones, everything is also not so simple. Firstly, in most variants of the game, it is impossible to remove stones that make up one of the enemy’s “mills” (in some varieties such stones are allowed to be removed if there are no other options for taking). In addition, if we, under our own power, managed to build several “mills” at the same time, we have the right to take an appropriate number of enemy stones (this rule is also often neglected).


As you can see, the ancient developers of board games have worked hard so that we do not get bored with their implementation. That's probably all that I wanted to tell about the use of Zobrist hashing in the project "Dagaz". I hope that my story was interesting to you.