Dagaz: Steps
- I haven't taken checkers for a long time!
- said Chichikov, moving the sword too.
- We know you, how you play badly!
- said Nozdrev, speaking with a sword.
Nikolai Vasilyevich Gogol "Dead Souls"
I very vaguely remember the dialectic of Hegel, which we were given at the institute. Usually, unstoppable drowsiness defeated me at the very beginning of the lectures. I only remember that something was said about the fact that “the history is developing in a spiral”. It seems to be associated with the principle of "denial of denial." I am not quite sure of the universality of this law, but with respect to me it is being carried out. How many can remember, I do the same thing again and again. This is my way to get better. Anyway, I make checkers again. And this is great!
As I have repeatedly said, checkers are difficult! Chess games themselves are possibly and easier Chess (although comparing them is not entirely correct, the games are fundamentally different), it's not about that. Implementing drafts is much more complicated! If Chess is “planted with a pig” with cascading moves ( castling ), then in the games of the drafts family there are at once two even more complex “options”:
- Priorities and ...
- Composite moves!
Priorities are what make checkers special! In almost all checkers games (with very few exceptions), taking is mandatory, whether you like it or not. The whole matching game is built on this. You can "poddat" your checkers, building the opponent's figures in such a way, then to pick them up with one blow (and at the same time hold the queen). Give less to pick more! But this is only the tip of the iceberg!
')
In this game (the position is taken from the book of Y. Barsky and B. Gerzenson “Adventures on the Draftsboard”), White does not just sacrifice pieces, forcing the opponent to walk in a certain way. They use the fact that blacks are obliged to complete all captures and (at this time) freely move their pieces around the board, preparing the final trap. With his moves, whites create "breakthroughs" and this is an excellent illustration of how beautiful positional play in drafts can be.
By the way
Taking in checkers was not always strictly obligatory. And in Russian drafts and in English, and even in an even earlier Alquerque, there existed the “ rule of anger ”, which allowed to pick up a “yawning” figure who had not fulfilled the capture. Such an action was not considered a move and was called “take for a fook” (Huffing - in “English checkers”). I still found this rule in early childhood, but it seems the story has already made a final verdict.
The rule of anger puts an end to any matching game! An experienced draftsman would prefer to lose a “yawning” figure, instead of deliberately getting into the trap, because of which he will lose the entire game. Currently, this rule applies only to some African game varieties, traditionally played on large boards and at high speed.
The rule of anger puts an end to any matching game! An experienced draftsman would prefer to lose a “yawning” figure, instead of deliberately getting into the trap, because of which he will lose the entire game. Currently, this rule applies only to some African game varieties, traditionally played on large boards and at high speed.
For me, priorities are, first of all, optimization. In fact, using Dagaz's “ proprietary magic ”, I can prohibit the execution of any previously formed moves at the post-processing stage (this is exactly what I do in chess games ). Moreover, I can change the generated moves and even add new ones to them. But all this is at the cost of memory and time (and when the UCT bot is taken over, both become very critical). Productivity, in my case, is not so much interactivity, but the rationality of a computer opponent. Working faster, the bot will have time to disassemble a greater number of positions!
In the case of checkers, the generation of moves comes down to two possible situations. When there are no takes, there are not so many "quiet" moves. Everything changes when the take appears. Since I generate all the composite moves entirely, combinatorics is involved. For example, here in this test , a mediocre position with a woman generates 42 possible moves! And these moves would be much more if, according to the rules of " Turkish checkers ", I did not filter the moves with taking the maximum number of pieces! Adding to this list also “quiet” moves, with their subsequent filtering in post-processing, would be a waste.
This is where I caught the first non-trivial bug
Gauntlet is a very dynamic and quite interesting checker game. Developed its Phillip L. Leduc in 1980. The game is asymmetric. White needs to break through (at least one piece) to the last rank. Black - try not to allow this. Takes are similar to checkers, but since all the pieces move only in one direction, full implementation of composite moves is not required (by the way, there is another traditional Hawaiian game with a similar capture mechanism). Priorities in this game, on the contrary, are used, since taking is obligatory and this is an important component of the game.
In certain situations, the model stopped generating moves, which caused the game to immediately stop. It was clear that the error is related to the mechanism for processing priorities, but I did not immediately figure out what was wrong. At first, I even transferred the logic of filtering to an extension, disabling priorities (as I said, this is just a performance issue). When the error began to repeat in checkers, it became clear that the problem needed to be sorted out.
All the player's pieces are moved here and generators are created for each of them, for each possible move. The generators are decomposed into a small hash, in accordance with the priorities of the moves. Then the hash is viewed starting from the highest priority. If it is possible to generate at least one move, the move generators of lower priorities are not considered.
The error was that I marked the course as generated ahead of time, at the first capture. As a result, the generator saw a take, marked a move, and then went further and ran across a busy field, in the place where he was to place the figure. This led to a reset of the nearly completed move, but since the move was already marked, low-priority "quiet" moves were simply discarded. After the correction , AI Gauntlet began to play much better. Performance is important!
Gauntlet is a very dynamic and quite interesting checker game. Developed its Phillip L. Leduc in 1980. The game is asymmetric. White needs to break through (at least one piece) to the last rank. Black - try not to allow this. Takes are similar to checkers, but since all the pieces move only in one direction, full implementation of composite moves is not required (by the way, there is another traditional Hawaiian game with a similar capture mechanism). Priorities in this game, on the contrary, are used, since taking is obligatory and this is an important component of the game.
In certain situations, the model stopped generating moves, which caused the game to immediately stop. It was clear that the error is related to the mechanism for processing priorities, but I did not immediately figure out what was wrong. At first, I even transferred the logic of filtering to an extension, disabling priorities (as I said, this is just a performance issue). When the error began to repeat in checkers, it became clear that the problem needed to be sorted out.
It's all about this code.
var priors = []; _.chain(_.keys(this.pieces)) .filter(function(pos) { return Dagaz.Model.sharedPieces || Dagaz.Model.isFriend(this.pieces[pos], this.player); }, this) .each(function(pos) { var piece = this.pieces[pos]; _.chain(design.pieces[piece.type]) .filter(function(move) { return (move.type == 0); }) .each(function(move) { var g = Dagaz.Model.createGen(move.template, move.params, this.game.design); g.init(this, pos); addPrior(priors, move.mode, g); }, this); }, this); ... for (var i = 0; i <= design.modes.length; i++) { var f = false; if (!_.isUndefined(priors[i])) { while (priors[i].length > 0) { var g = priors[i].pop(); g.generate(); if (g.completed && !g.move.isPass()) { if (cont && (g.moveType == 0)) { CompleteMove(this, g); } f = true; } } } if (f) break; if (i >= design.modes.length) break; } All the player's pieces are moved here and generators are created for each of them, for each possible move. The generators are decomposed into a small hash, in accordance with the priorities of the moves. Then the hash is viewed starting from the highest priority. If it is possible to generate at least one move, the move generators of lower priorities are not considered.
The error was that I marked the course as generated ahead of time, at the first capture. As a result, the generator saw a take, marked a move, and then went further and ran across a busy field, in the place where he was to place the figure. This led to a reset of the nearly completed move, but since the move was already marked, low-priority "quiet" moves were simply discarded. After the correction , AI Gauntlet began to play much better. Performance is important!
I think it's time to talk a little about checkers. Many of us are familiar only with the Russian and, possibly, the international version of this game. In fact, checkers (even if we consider only traditional games) are more. Much more! Games are very similar to each other and, often, differ only in small details.
The picture is clickable. Twice! Take the medieval Alquerque and the Fox and the Geese as a starting point . It seems that this is the first game in which the composite take appeared. The idea here is that by completing the “check” capture, the figure gets the right to continue the move by taking another figure. And so, as long as there is someone to take.
The links in my diagram are rather arbitrary. They do not reflect the historical development (it, in our time, is unlikely to be restored), but rather the interrelationships of the various variants of the rules of the game. For example, the “ Senegalese checkers ” are hardly the forerunners of the “ Turkish checkers ” and, accordingly, the entire “orthogonal” direction. They are more archaic, it is a fact, but most likely there was a parallel development from some unknown common ancestor.
On the part of another family, two important historical events occurred simultaneously - the rejection of orthogonal movements (in favor of the diagonal ones) and the use of the traditional chessboard (in the wake of the growing popularity of Chess, this decision had the most beneficial effect on the spread of the game). We again do not know where and when this happened. Perhaps the link was “ Dan ” - Philippine drafts, hard to say.
" English checkers " are the root of the "diagonal" family, because they use the most primitive version of the rules. Non-transformed figures in them cannot move backwards (even while performing a take), queens differ only in that they have the right to move in any direction. This is a very leisurely game. The Italians "turned" the board 90 degrees and made the ladies inviolable (simple figures can not "chop" them). By the way, there is an interesting kind of game that develops this idea:
In the “ Spanish checkers ”, the board is also rotated 90 degrees, but here “flying” long-range queens appear (simple figures still cannot “chop” back). The ladies become very strong and for the first time the problem of their "catching" arises.
Every drafts player must be able to do it!
Three ladies catch one (provided that she did not occupy the “big one” - the main diagonal of the board). This is an interesting task, for the solution of which you can use at least two tactical constructions: the famous Petrov's Triangle and the less well-known Gonyayev Bayonet .
Those who wish to practice can do it here .
Those who wish to practice can do it here .
The Argentinean and Thai versions of the game limit the mobility of the ladies, allowing them to stop only on the first field behind the taken figure (if it is free, of course). By the way, in exactly the same way “ Greek checkers ” limit the mobility of “Turkish ladies”. Next come the familiar to us variants of the game, allowing "taking back" by simple figures.
More about taking
Practically all variants of drafts with long-range queens (except for “Turkish” and “Greek”) use the “ Turkish strike ” rule, also aimed at restricting the mobility of the queens. Its essence is that the taken pieces are removed from the board only at the end of the turn. This limits the queen, interfering with her movements (of course, repeated taking of figures during the course is prohibited). The second complex bug of the current iteration was associated with this rule.
I decided to do just that - move all the moves of the composite move to its last partial move. It worked as it was intended - the pieces remained on the board for the entire turn and were removed from the board after its completion. Of course, I had to make changes to the model that prevented the re-taking of figures (otherwise, the generator of the moves simply went in cycles and it simply did not reach any “extension magic”). Unfortunately, I forgot to do the main thing - run the tests after this change! As a result, I spent a lot of time. The logic of the compound takes "broke" in a very non-trivial and rather imperceptible way. It was sudden and terrible. It broke!
But time and effort was spent on this very much. Never forget the tests! And yet, never do this:
I decided to do just that - move all the moves of the composite move to its last partial move. It worked as it was intended - the pieces remained on the board for the entire turn and were removed from the board after its completion. Of course, I had to make changes to the model that prevented the re-taking of figures (otherwise, the generator of the moves simply went in cycles and it simply did not reach any “extension magic”). Unfortunately, I forgot to do the main thing - run the tests after this change! As a result, I spent a lot of time. The logic of the compound takes "broke" in a very non-trivial and rather imperceptible way. It was sudden and terrible. It broke!
In the end, I found a solution
ZrfMoveGenerator.prototype.isCaptured = function(pos, level) { if (this.parent) { return this.parent.isCaptured(pos, level); } if (_.isUndefined(this.captured)) { this.captured = []; } if (this.captured[pos] && (this.captured[pos] < level)) return true; _.each(Dagaz.Model.getDesign().allPositions(), function(p) { if (this.captured[p] && (this.captured[p] >= level)) { delete this.captured[p]; } }, this); this.captured[pos] = level; return false; } ZrfMoveGenerator.prototype.capturePiece = function(pos) { if (Dagaz.Model.deferredStrike) { if (this.isCaptured(pos, this.level)) return false; } this.move.capturePiece(pos, this.level); if (!Dagaz.Model.deferredStrike) { this.setPiece(pos, null); } return true; } But time and effort was spent on this very much. Never forget the tests! And yet, never do this:
_.chain(move.actions) .filter(function(action) { return (action[0] !== null) && (action[1] === null); }) .each(function(action) { action[3] = mx; }); The consequences will be wonderful, but you are unlikely to like it! Do not change the fields (even the most innocuous) inside the collection you are iterating. It is better to re-create it, let it remain immutable:
var actions = []; _.each(move.actions, function(action) { var pn = action[3]; if ((action[0] !== null) && (action[1] === null)) { pn = mx; } actions.push([ action[0], action[1], action[2], pn ]); }); move.actions = actions; Russian checkers (by the way, there is another very original way of solving the problem “dam on the big one”) differ from the international (besides the size of the board, of course) by just one significant detail. In Russian drafts, the transformation into a lady happens on the fly. The move is not interrupted and the figure continues to take like a lady (from the point of view of software implementation, this was the most obvious behavior). In international - the figure continues to take, even after hitting the transformation field, but “cuts” like a simple figure, and the transformation itself takes place only if the figure finishes its turn on the last horizontal. Here I had to write a special extension , however, its debugging did not cause any problems.
Meanwhile, Alquerke also evolved. The development took place in parallel with the development of drafts and gathered from the latter such ideas as the course of simple figures “only forward”, “flying ladies” and even the rule of “Turkish strike”. It turned out quite original and very original games " Zamm " and " Harbaga ", I can recommend them to those who are tired of the chessboard.
The Finns have kept another ancient game for us.
This game is much closer to Alquerque. There are no “flying ladies” in it, there is not even a transformation! The game has a "king" and "prince", but these posts are for life. Simple figures can not become "royal persons". Also, they can not threaten "titled" figures (in this respect, the game is similar to the "Italian Checkers"). The game is quite slow, but it has its fans.
For me, Dablot was interested in a more complex system of priorities. Taking in the game is mandatory, but not for the "king" or "prince." That is, if there is a possibility of taking by a simple figure - it is necessary to take (it is possible to take another figure, even a “king”, if there is such a move), but if the threat is created only by the “king” or “prince”, it is allowed to make a “silent” move. All this resulted in a fairly simple extension (at the level of ZRF, priorities had to be turned off). However, even here I managed to plow a little:
This game is much closer to Alquerque. There are no “flying ladies” in it, there is not even a transformation! The game has a "king" and "prince", but these posts are for life. Simple figures can not become "royal persons". Also, they can not threaten "titled" figures (in this respect, the game is similar to the "Italian Checkers"). The game is quite slow, but it has its fans.
For me, Dablot was interested in a more complex system of priorities. Taking in the game is mandatory, but not for the "king" or "prince." That is, if there is a possibility of taking by a simple figure - it is necessary to take (it is possible to take another figure, even a “king”, if there is such a move), but if the threat is created only by the “king” or “prince”, it is allowed to make a “silent” move. All this resulted in a fairly simple extension (at the level of ZRF, priorities had to be turned off). However, even here I managed to plow a little:
if (_.chain(board.moves) .filter(function(move) { return _.isUndefined(move.failed); }) .filter(function(move) { return move.actions.length > 1; }) .filter(function(move) { ... - }).value().length > 1) { + }).value().length >= 1) { _.chain(board.moves) .filter(function(move) { return move.actions.length == 1; }) .each(function(move) { move.failed = true; }); } The culmination of this direction of the games, I think Madagascar " Fanorona ". It is already quite unlike checkers, since it uses a completely different capture mechanism. Of course there are similarities - taking is also compound. At the same time, Fanorona is the only known game in which the player has the right to interrupt the chain of captures (the capture itself still remains obligatory)!
This game has become for me a real test of strength. Everything was there: breaking the model and rewriting the controller and new funny bugs. But all is well that ends well. The iteration is complete and I can go on vacation with a clear conscience!
Source: https://habr.com/ru/post/335228/
All Articles