Dagaz: Faster, Better, Smarter ...
- How angels soar together in a row ... - Together in a row, amicably in a row ...
- Raise your head! And fly! And fly! ..
Sir Terry Pratchett "Night Watch"
Sooner or later, there always comes a point when quantity inevitably turns into quality. New games that need to be comprehended accumulate, the project acquires new possibilities, the possibilities are combined with each other. If everything does not collapse under its own weight, the result may exceed all expectations. What does not kill - makes us stronger!
Here is an example of such a "amount of technology." The game, in general, is not too difficult, but very unexpected. Apocalypse - on the field four horsemen and supporting their infantry. Usual moves of chess pieces . Pawns, having reached the last line, are expectedly turned into riders, but the number of riders on each side cannot exceed two. The player who first lost all his riders loses. The devil, as always, is in the details. Figures walk at the same time!
')
What does this mean in terms of a project?
First of all, like puzzles, this is a “game for one” - the player makes a move, and the bot “mixes” his own into it, not knowing what kind of move the person made. This is a game with incomplete information, although in a form very unusual for us. There are no playing dice or “fog of war” here, but each of the players, performing a move, does not know how his opponent is descending at the same time.
Of course, possible conflicts. For example, both players can simultaneously move to the same empty field, or a pawn can try to eat a piece leaving the same turn from a strike. The rules of the game well describe these nuances. A pawn is allowed to perform a diagonal move, provided that it is going to beat someone, even if the piece has left this position, and the result of the conflict over an empty field is determined by the rank of the pieces. The rider always kills a pawn, but if the pieces are equal, they are both destroyed (which, by the way, makes a draw outcome possible).
The task is not easy, but the “expansion of moves” mechanism copes with it perfectly. Indeed, as I have repeatedly said before, at the post-processing stage, we can not only prohibit the move (violating the game invariant, for example), but also add to it any arbitrary actions, including those obtained from the bot-generated move.
There is a truth, one subtlety - usually, post-processing is performed immediately after generation, for all formed moves. In this case, it is impossible to do this, because it will inevitably lead to a “combinatorial explosion” (the game, though small, is still not enough). Most importantly, this is not necessary. There is a simpler way. No one said that we can not rewrite the controller . Modularity has its advantages.
Of course, possible conflicts. For example, both players can simultaneously move to the same empty field, or a pawn can try to eat a piece leaving the same turn from a strike. The rules of the game well describe these nuances. A pawn is allowed to perform a diagonal move, provided that it is going to beat someone, even if the piece has left this position, and the result of the conflict over an empty field is determined by the rank of the pieces. The rider always kills a pawn, but if the pieces are equal, they are both destroyed (which, by the way, makes a draw outcome possible).
Merge moves
Dagaz.Model.join = function(design, board, a, b) { var x = getPiece(design, board, a); var y = getPiece(design, board, b); if ((x !== null) && (y !== null)) { var r = Dagaz.Model.createMove(); r.protected = []; checkPromotion(design, board, a, x, b); checkPromotion(design, board, b, y, a); var p = a.actions[0][1][0]; var q = b.actions[0][1][0]; if ((p == q) && (x.type > y.type)) { r.actions.push(b.actions[0]); r.actions.push(a.actions[0]); } else { r.actions.push(a.actions[0]); r.actions.push(b.actions[0]); } if (p == q) { if (x.type > y.type) { r.actions[0][2] = [ Dagaz.Model.createPiece(2, 2) ]; r.protected.push(x.player); r.captured = p; } else { if (x.type == y.type) { r.actions[0][2] = [ Dagaz.Model.createPiece(2, 1) ]; r.actions[1][2] = [ Dagaz.Model.createPiece(2, 1) ]; r.capturePiece(p); } else { r.actions[0][2] = [ Dagaz.Model.createPiece(2, 1) ]; r.protected.push(y.player); r.captured = p; } } } return r; } else { return a; } } The task is not easy, but the “expansion of moves” mechanism copes with it perfectly. Indeed, as I have repeatedly said before, at the post-processing stage, we can not only prohibit the move (violating the game invariant, for example), but also add to it any arbitrary actions, including those obtained from the bot-generated move.
There is a truth, one subtlety - usually, post-processing is performed immediately after generation, for all formed moves. In this case, it is impossible to do this, because it will inevitably lead to a “combinatorial explosion” (the game, though small, is still not enough). Most importantly, this is not necessary. There is a simpler way. No one said that we can not rewrite the controller . Modularity has its advantages.
From the point of view of the AI ​​bot, the game, in many respects, “turns out”. There is no need to perform a multi-turn view. It is important to guess how the opponent will walk! Changing tactics of the game. It is almost useless to try to attack the riders who are “under battle” - they will certainly run away. "Forks" are more promising, but you have to choose which of the riders to beat. If the enemy has only one rider left (and you have a complete set of them), you can try to “watch for” him by going to the field chosen by him. Just do not make it a pawn! There are nuances associated with the transformation of figures, but, in general ...
It all comes down to a set of heuristics
... var isCovered = function(design, board, pos, player, type) { var r = false; _.each(Dagaz.Model.GetCover(design, board)[pos], function(pos) { var piece = board.getPiece(pos); if ((piece !== null) && (piece.player == player)) { if (_.isUndefined(type) || (piece.type == type)) { r = true; } } }); return r; } Ai.prototype.getMove = function(ctx) { var moves = Dagaz.AI.generate(ctx, ctx.board); if (moves.length == 0) { return { done: true, ai: "nothing" }; } timestamp = Date.now(); var enemies = 0; var friends = 0; _.each(ctx.design.allPositions(), function(pos) { var piece = ctx.board.getPiece(pos); if ((piece !== null) && (piece.type == 1)) { if (piece.player == 1) { enemies++; } else { friends++ } } }); var eval = -MAXVALUE; var best = null; _.each(moves, function(move) { var e = _.random(0, NOISE_FACTOR); if (move.isSimpleMove()) { var pos = move.actions[0][0][0]; var trg = move.actions[0][1][0]; var piece = ctx.board.getPiece(pos); if (piece !== null) { var target = ctx.board.getPiece(trg); if (piece.type == 1) { if (isCovered(ctx.design, ctx.board, pos, 1)) e += MAXVALUE; if (target === null) { if (isCovered(ctx.design, ctx.board, trg, 1, 0)) e += LARGE_BONUS; if (isCovered(ctx.design, ctx.board, trg, 1, 1)) { if ((enemies == 1) && (friends == 2)) { e += BONUS; } else { e -= MAXVALUE; } } } else { if (target.type == 1) { e += SMALL_BONUS; } else { e += BONUS; } } } else { if (isCovered(ctx.design, ctx.board, pos, 1)) e += SMALL_BONUS; if ((target === null) && isCovered(ctx.design, ctx.board, trg, 1)) e -= MAXVALUE; if (friends == 1) e += BONUS; if (target !== null) e += SMALL_BONUS; if ((move.actions[0][2] !== null) && (move.actions[0][2][0].type != piece.type)) { if (friends == 1) { e += MAXVALUE; } else { e -= MAXVALUE; } } } } } if ((best === null) || (eval < e)) { console.log("Move: " + move.toString() + ", eval = " + e); best = move; eval = e; } }); return { done: true, move: best, time: Date.now() - timestamp, ai: "aggressive" }; } 
The other extreme is that the games are large and complex, so much so that it’s technically impossible to look at it in depth. Here we are forced to use a more casual AI , looking at the position only 1-2 moves ahead, and even at this depth, it will not be possible to view all the available moves! In any case, for a time convenient for a person to search for a bot in 2-3 seconds.
More about performance
Large and complex games expose all the problems associated with performance. Usually, how fast the code is executed is related to the quality of the AI ​​work (the more positions it has to consider in the allotted time, the better it works), but sometimes performance problems become more obvious. While working on Tenjiku shogi , I noticed that in some positions, the user interface response time was simply indecent (about 10-15 seconds).
It's all about the "Fire Demon" (and similar figures). Pay attention to the diagram on the right. In addition to the usual "range" -attack, "demon" has the right, at any time, to perform up to three single-step movements in an arbitrary direction, while he is allowed to return to the previously passed fields. This is a real "combinatorial killer" of performance! In the initial position, when all such pieces are “clamped”, this effect does not manifest itself so much, but when they go to the operational space ... anyone can count the possible options for moves (the diagram below shows graphs of changes in the average number of allowable moves, during the game for several famous games).
Here you should tell a little about the architecture of Dagaz. The main idea is that, before transferring control to the user or bot, the game model generates all possible moves from the current position. This allows us to consider the totality of moves "as a whole" and helps to solve a number of problems of Zillions of Games related to compound moves. In addition, this approach is very convenient for the development of bots. But there is one problem.
For the user, a complex composite move is a sequence of different actions (movements, taking and, possibly, dumping new pieces on the board). Somewhere there should be a code that allows you to select a single move from a previously formed and possibly large list of a sequence of user "clicks". And there is such a code in Dagaz, of course.
See what the problem is? The getStops function builds a list of all trailing fields of each move and, for this, iterates through all the moves in the cycle, but with the smartFrom or smartTo options enabled (options for immediately executing a move on the first click, if there are no alternatives), nested iteration of all moves is performed. A lot of moves formed!
In small games, like checkers or chess, the error did not manifest itself. Even in the initial position of Tenjiku shogi, it was not noticeable. It took "performance killers" to reveal it. And for the error localization, the KPI module was very useful, without which I simply would not know where to look for the problem. Now the bug is fixed and, as a result, the whole code is better.
It's all about the "Fire Demon" (and similar figures). Pay attention to the diagram on the right. In addition to the usual "range" -attack, "demon" has the right, at any time, to perform up to three single-step movements in an arbitrary direction, while he is allowed to return to the previously passed fields. This is a real "combinatorial killer" of performance! In the initial position, when all such pieces are “clamped”, this effect does not manifest itself so much, but when they go to the operational space ... anyone can count the possible options for moves (the diagram below shows graphs of changes in the average number of allowable moves, during the game for several famous games).
Here you should tell a little about the architecture of Dagaz. The main idea is that, before transferring control to the user or bot, the game model generates all possible moves from the current position. This allows us to consider the totality of moves "as a whole" and helps to solve a number of problems of Zillions of Games related to compound moves. In addition, this approach is very convenient for the development of bots. But there is one problem.
For the user, a complex composite move is a sequence of different actions (movements, taking and, possibly, dumping new pieces on the board). Somewhere there should be a code that allows you to select a single move from a previously formed and possibly large list of a sequence of user "clicks". And there is such a code in Dagaz, of course.
It hid a mistake
MoveList.prototype.isUniqueFrom = function(pos) { var c = 0; _.each(this.moves, function(move) { _.each(this.getActions(move), function(action) { if ((action[0] !== null) && (_.indexOf(action[0], pos) >= 0)) c++; }); }, this); return c == 1; } MoveList.prototype.isUniqueTo = function(pos) { var c = 0; _.each(this.moves, function(move) { _.each(this.getActions(move), function(action) { if ((action[1] !== null) && (_.indexOf(action[1], pos) >= 0)) c++; }); }, this); return c == 1; } ... MoveList.prototype.getStops = function() { var result = this.getTargets(); _.each(this.moves, function(move) { var actions = _.filter(this.getActions(move), isMove); if ((actions.length > 0) && (actions[0][0].length == 1) && (actions[0][1].length == 1)) { if (Dagaz.Model.smartFrom) { if (this.isUniqueFrom(actions[0][0][0]) && !this.canPass()) { result.push(actions[0][0][0]); } } if (Dagaz.Model.smartTo) { if (this.isUniqueTo(actions[0][1][0])) { result.push(actions[0][1][0]); } } } else { ... } }, this); return _.uniq(result); } See what the problem is? The getStops function builds a list of all trailing fields of each move and, for this, iterates through all the moves in the cycle, but with the smartFrom or smartTo options enabled (options for immediately executing a move on the first click, if there are no alternatives), nested iteration of all moves is performed. A lot of moves formed!
In small games, like checkers or chess, the error did not manifest itself. Even in the initial position of Tenjiku shogi, it was not noticeable. It took "performance killers" to reveal it. And for the error localization, the KPI module was very useful, without which I simply would not know where to look for the problem. Now the bug is fixed and, as a result, the whole code is better.
So, we are limited in depth and must make the right (or at least not disastrous) decision for a limited time. At the same time, it is highly desirable to ensure the implementation of the following principles:
- Of course, the move must lead to an immediate victory.
- There should not be a move to which there is an answer leading to an immediate victory.
- The selected move should provide the greatest improvement in position.
How to evaluate the position?
The easiest way is to evaluate the material balance. Each type of pieces is assigned a cost, then we add the cost of our pieces and wean the cost of the pieces of the opponent. Estimation is rough, but for really difficult games, perhaps, the only possible one. An improved assessment should take into account the mobility of the figures and their mutual threats (I will discuss this below). For "big" games with complex rules, the assessment of mutual threats may be too expensive.
The second tool is heuristics. It’s just a numerical score of a move , not a position, allowing to distinguish between “bad” moves and “good” moves. Of course, first of all, “good” moves will be considered, and there may simply be no time left for the consideration of “bad” times. The simplest heuristics can include the cost of a taken figure, but in addition, it is desirable to estimate the cost of a figure performing a move, possible transformations, threats, etc.
It is important to understand that the maximum value of heuristics does not mean at all that this particular move will be chosen. Heuristics set only the order of viewing moves. Within the framework of this order, the move is chosen that maximizes the value of the evaluation function (after the opponent’s move with the maximum heuristics is completed). It is possible to forcibly exclude part of the moves from consideration by giving them a negative heuristic value, but this tool should be used with caution, only in cases where there is a 100% certainty that the move in question is not just useless, but harmful.
Remember, above I spoke about the three principles? It makes sense for the royal figures (there can be several types of such figures in the game) to assign a very high cost. With this we kill two birds with one stone: first, the move taking the royal piece will receive the maximum possible heuristics (and will always be considered first), moreover, the absence of a royal figure on the board will significantly affect the value of the evaluation function, which is also very convenient. Unfortunately, as applied to Chess, this trick is not relevant, since the king is never taken in them.
The simplest estimate function
Dagaz.AI.eval = function(design, params, board, player) { var r = 0; _.each(design.allPositions(), function(pos) { var piece = board.getPiece(pos); if (piece !== null) { var v = design.price[piece.type]; if (piece.player != player) { v = -v; } r += v; } }); return r; } The second tool is heuristics. It’s just a numerical score of a move , not a position, allowing to distinguish between “bad” moves and “good” moves. Of course, first of all, “good” moves will be considered, and there may simply be no time left for the consideration of “bad” times. The simplest heuristics can include the cost of a taken figure, but in addition, it is desirable to estimate the cost of a figure performing a move, possible transformations, threats, etc.
Heuristic example
Dagaz.AI.heuristic = function(ai, design, board, move) { var r = 0; var player = board.player; var start = null; var stop = null; var captures = []; _.each(move.actions, function(a) { if ((a[0] !== null) && (a[1] === null)) { var pos = a[0][0]; var piece = board.getPiece(pos); if ((piece !== null) && (piece.player != player)) { r += design.price[piece.type] * ai.params.CAPTURING_FACTOR; if (!_.isUndefined(board.bonus) && (board.bonus[pos] < 0)) { r -= board.bonus[pos]; } } captures.push(pos); } if ((a[0] !== null) && (a[1] !== null)) { if (start === null) { start = a[0][0]; if (!_.isUndefined(board.bonus)) { r += board.bonus[start]; } } stop = a[1][0]; } }); var price = 0; if (start !== null) { var piece = board.getPiece(start); if (piece !== null) { price = design.price[piece.type]; } } _.each(move.actions, function(a) { if ((a[0] !== null) && (a[1] !== null)) { var pos = a[1][0]; var piece = board.getPiece(pos); if (_.indexOf(captures, pos) < 0) { if ((piece !== null) && (piece.player != player)) { r += design.price[piece.type] * ai.params.CAPTURING_FACTOR; if (!_.isUndefined(board.bonus)) { r += Math.abs(board.bonus[pos]); } } if (a[2] !== null) { var promoted = a[2][0]; r -= price * ai.params.SUICIDE_FACTOR; if (promoted.player == player) { r += design.price[promoted.type] * ai.params.PROMOTING_FACTOR; } } } else { r -= price * ai.params.SUICIDE_FACTOR; } } if ((a[0] === null) && (a[1] !== null) && (a[2] !== null) && (_.indexOf(captures, a[1][0]) < 0)) { var pos = a[1][0]; var piece = board.getPiece(pos); if (piece !== null) { if (piece.player != player) { r += design.price[piece.type] * ai.params.CAPTURING_FACTOR; } } piece = a[2][0]; if (piece.player == player) { r += design.price[piece.type] * ai.params.CREATING_FACTOR; } } }); if (!_.isUndefined(board.cover) && (start !== null) && (stop !== null)) { if (isAttacked(design, board, board.player, stop, start, price)) { r -= price * ai.params.SUICIDE_FACTOR; } } return r; } It is important to understand that the maximum value of heuristics does not mean at all that this particular move will be chosen. Heuristics set only the order of viewing moves. Within the framework of this order, the move is chosen that maximizes the value of the evaluation function (after the opponent’s move with the maximum heuristics is completed). It is possible to forcibly exclude part of the moves from consideration by giving them a negative heuristic value, but this tool should be used with caution, only in cases where there is a 100% certainty that the move in question is not just useless, but harmful.
Cost figures
... design.addPiece("King", 32, 10000); design.addPiece("Prince", 33, 10000); design.addPiece("Blind-Tiger", 34, 3); design.addPiece("Drunk-Elephant", 35, 3); design.addPiece("Ferocious-Leopard", 36, 3); design.addPiece("Gold-General", 37, 3); design.addPiece("Silver-General", 39, 2); design.addPiece("Copper-General", 40, 2); design.addPiece("Chariot-Soldier", 41, 18); design.addPiece("Dog", 43, 1); design.addPiece("Bishop-General", 44, 21); design.addPiece("Rook-General", 46, 23); design.addPiece("Vice-General", 48, 39); design.addPiece("Great-General", 49, 45); ... Remember, above I spoke about the three principles? It makes sense for the royal figures (there can be several types of such figures in the game) to assign a very high cost. With this we kill two birds with one stone: first, the move taking the royal piece will receive the maximum possible heuristics (and will always be considered first), moreover, the absence of a royal figure on the board will significantly affect the value of the evaluation function, which is also very convenient. Unfortunately, as applied to Chess, this trick is not relevant, since the king is never taken in them.
It should be noted that the position should always be evaluated only at the end of the opponent’s retaliatory move! If there is a chain of exchanges, you should look through it to the end, otherwise it may turn out that the attacking figure will be given away for the less valuable one.
Games of more than two players - another application of casual "one-way" AI. It's all about the evaluation function. Minimax algorithms work only if the score from the point of view of one player coincides with the score of another, taken with the opposite sign. What one loses gets the other. If there are three players ( or more ), everything breaks down. Of course, you can still use algorithms based on the Monte Carlo method, but other difficulties are associated with them.
Yonin Shogi is a variant of " Japanese chess " for four players. Most of the rules in this game remain the same, but the goal of the game changes. The concept of “mata”, to a certain extent, loses its meaning. In fact, if the "east" threatens the king of the "south" - this is not a reason for protection from the "Shah", until the "west" and "north" say their word. On the other hand, if the threat is not eliminated, the “east” will eat the king by the next move. Thus, in Yonin Shogi it is allowed to take kings (and this is the goal of the game).
In addition, the game does not end with the capture of the king (a similar outcome would be too boring, for the remaining three players). A player losing a king is eliminated from the game, losing the right of his turn. Since kings are allowed to be taken, they, like all other pieces, fall into the reserve and can be put on the board at any time. The player is obliged to put the king from the reserve, if there are no kings left on the board. After all that has been said, the goal of the game becomes obvious - the one who collects all four kings wins (when I made the game for Zillions of Games , Howard McCay helped me realize this nuance).
Everything said above leads to a simple thought.
There are games in which complex depth-first search algorithms cannot be used, and the concept of the evaluation function itself must be rethought. To keep the quality of the AI ​​algorithms acceptable, it is necessary to improve the estimates and heuristics, possibly due to their complexity. The obvious way is the introduction of mobility - the number of all possible moves made by the player, minus the moves of the opponent.
When using "one-way" algorithms, the assessment of mobility works wonders. The stupid game of the bot becomes more "meaningful." There is one minus truth - in order to evaluate mobility, it is necessary to build (or at least recount) all possible moves for each of the players, and this is a very expensive operation. Since we, all the same, are forced to do this, I want to "squeeze" out of the generation of moves everything possible, as well as minimize the number of such operations.
So I came to the idea of ​​"coverage." This is just an array of arrays. For each of the fields (and any field in Dagaz is always encoded with an integer), the list of positions in which the figures are located that can beat this field is preserved, possibly empty. At the same time (and this is important) no distinction is made between empty and occupied fields, as well as the owners of the “batter” figures. The list of possible moves is calculated for all players at the same time , and at the expense of caching, also once.
Of course, the universal algorithm for constructing the "cover" is not suitable for all games. For Chess and Checkers, it works, but for Spock it is already gone (since, in this game, pieces can easily pass through other pieces of their own color). This should not be confusing. As well as the evaluation function and heuristics, the algorithm for constructing a "cover" can be redefined using the name Dagaz.Model.GetCover . Moreover, even in cases where the universal algorithm works, it is useful to think about its customization. Specialized algorithms, as a rule, are more productive.
eval = A * material-balance + B * mobility; A >= 0, B >= 0, A + B = 1
When using "one-way" algorithms, the assessment of mobility works wonders. The stupid game of the bot becomes more "meaningful." There is one minus truth - in order to evaluate mobility, it is necessary to build (or at least recount) all possible moves for each of the players, and this is a very expensive operation. Since we, all the same, are forced to do this, I want to "squeeze" out of the generation of moves everything possible, as well as minimize the number of such operations.
Coating
Dagaz.AI.eval = function(design, params, board, player) { var r = 0; var cover = board.getCover(design); _.each(design.allPositions(), function(pos) { var defended = _.filter(cover[pos], function(p) { var piece = board.getPiece(p); if (piece === null) return false; return piece.player == player; }); if (defended.length > 0) r++; }); return r; } So I came to the idea of ​​"coverage." This is just an array of arrays. For each of the fields (and any field in Dagaz is always encoded with an integer), the list of positions in which the figures are located that can beat this field is preserved, possibly empty. At the same time (and this is important) no distinction is made between empty and occupied fields, as well as the owners of the “batter” figures. The list of possible moves is calculated for all players at the same time , and at the expense of caching, also once.
Of course, the universal algorithm for constructing the "cover" is not suitable for all games. For Chess and Checkers, it works, but for Spock it is already gone (since, in this game, pieces can easily pass through other pieces of their own color). This should not be confusing. As well as the evaluation function and heuristics, the algorithm for constructing a "cover" can be redefined using the name Dagaz.Model.GetCover . Moreover, even in cases where the universal algorithm works, it is useful to think about its customization. Specialized algorithms, as a rule, are more productive.
Here is an example of using "coverage" in a real game. This is still the simplest “one-step” algorithm and is very easy to deceive, but the actions of the bot seem to be meaningful! Analyzing the coverage, the AI ​​never leaves its pieces unprotected and seeks to maximize them on the board, maximizing the number of fields under battle. This is a good tactic, certainly leading to victory when playing against a single Maharaja . Also this algorithm shows itself well in " Charge of the Light Brigade ", " Dunsany's Chess ", " Horde Chess ", " Weak! " And other "small" chess games. For me, it is obvious that the use of "coverage" will help to improve more complex algorithms, but before moving on to them, I need to practice.
Somewhere around 5:39 all movements are dramatically accelerated. This is simply explained. In parallel with the animation of the movement of the dice (just so that the person does not get bored), the bot searches for the target position and after it finds it, goes to it in a straight line, without losing time for additional calculations.
By the way
I did not manage to observe this effect on FireFox 52.6.0. In Chrome and even in IE, the algorithm found a solution in about 5 minutes, and in the “Fire Fox” I continued to slowly move the dies for about fifteen minutes, until I cut it down (while memory guzzled as not in itself). I have not yet found an explanation for this phenomenon.
For me, this is a significant step forward compared to the previous version . The algorithm is a simple search in width (not in depth ! Is this important, are we interested in the shortest solution?). Repeated positions are cut off, with the help of Zobrist hash , which by the way makes possible (although extremely unlikely) a situation in which a solution may not be found as a result of a collision. In addition, the search priority is given to nodes that are descendants of the current animation node (in order to minimize the number of required returns, after finding a solution).
Along the way, I did one more thing.
The fact is that in Zillions of Games there is an option, the purpose of which I never understood. It is called “progressive levels”. As soon as you finish one level of the game, it immediately loads the next one, just in order. Now, I think, I caught what is the point. Try to turn off these lights:
Agree, it delays. And so how someone solves puzzles for you, you can generally look up to infinity . But this is only half the battle! Like almost any Dagaz option, my “progressive levels” can be customized.
This puzzle was devoted to the election of George Washington for the presidency and, initially, I did not realize it correctly. For the right solution, you need to draw a red square through all four corners alternately, but in Dagaz you can only set one goal. This is where the custom “progressive levels” comes into play.
As soon as we reach the next goal, the next level is loaded, but the arrangement of the figures, at the same time, is taken from the previous one! We just continue from where we left off. , , . , , , . URL , «Setup:». !
«progressive levels» , Kamisado . ! , «» , , . , Dagaz ! , . , , .
Agree, it delays. And so how someone solves puzzles for you, you can generally look up to infinity . But this is only half the battle! Like almost any Dagaz option, my “progressive levels” can be customized.
This puzzle was devoted to the election of George Washington for the presidency and, initially, I did not realize it correctly. For the right solution, you need to draw a red square through all four corners alternately, but in Dagaz you can only set one goal. This is where the custom “progressive levels” comes into play.
As soon as we reach the next goal, the next level is loaded, but the arrangement of the figures, at the same time, is taken from the previous one! We just continue from where we left off. , , . , , , . URL , «Setup:». !
«progressive levels» , Kamisado . ! , «» , , . , Dagaz ! , . , , .
. , — . , «» «». — :
- " " " ", , , « » . , . , . ( ), . AI .
- !
Dagaz.AI.eval = function(design, params, board, player) { var r = 0; var white = null; var black = []; for (var pos = 0; pos < design.positions.length - 3; pos++) { var piece = board.getPiece(pos); if (piece !== null) { if (piece.player == 1) { if (white === null) { black.push(pos); } else { r += MAXVAL / 2; } } else { white = pos; } } } if (white !== null) { r += white; } if (black.length == 2) { if ((black[0] + 1 == black[1]) && (black[1] + 1 == white)) { if (board.player == 1) { r = MAXVAL; } else { r = -MAXVAL; } if (player == 1) { r = -r; } } } return r; } Dagaz.AI.heuristic = function(ai, design, board, move) { var b = board.apply(move); return design.positions.length + Dagaz.AI.eval(design, ai.params, b, board.player) - Dagaz.AI.eval(design, ai.params, board, board.player); } ... AbAi.prototype.ab = function(ctx, node, a, b, deep) { node.loss = 0; this.expand(ctx, node); if (node.goal !== null) { return -node.goal * MAXVALUE; } if (deep <= 0) { return -this.eval(ctx, node); } node.ix = 0; node.m = a; while ((node.ix < node.cache.length) && (node.m <= b) && (Date.now() - ctx.timestamp < this.params.AI_FRAME)) { var n = node.cache[node.ix]; if (_.isUndefined(n.win)) { var t = -this.ab(ctx, n, -b, -node.m, deep - 1); if ((t !== null) && (t > node.m)) { node.m = t; node.best = node.ix; } } else { node.loss++; } node.ix++; } return node.m; } 
. . «» , . — , , . , , !
, Tenjiku Shogi , , . , — . AI, . , , Horn Chess , Ko Shogi Gwangsanghui . , «» , " ". .
. , , . , , . " Custodian "- ( " - ") .
!
var eval = Dagaz.AI.eval; Dagaz.AI.eval = function(design, params, board, player) { var r = eval(design, params, board, board.player); var cover = board.getCover(design); var cnt = null; _.each(cover, function(list) { var cn = 0; _.each(list, function(pos) { var piece = board.getPiece(pos); if (piece !== null) { if (piece.player == board.player) { r--; } else { cn++; } } }); if ((cnt === null) || (cnt < cn)) { cnt = cn; } }); r += cnt * 3; if (board.player != player) { return -r; } else { return r; } } var done = function(design, board, player, pos, dir, trace, captured) { var p = design.navigate(player, pos, dir); if (p !== null) { var piece = board.getPiece(p); if (piece !== null) { if (piece.player == player) { _.each(trace, function(pos) { if (_.indexOf(captured, pos) < 0) { captured.push(pos); } }); } else { trace.push(p); done(design, board, player, p, dir, trace, captured); trace.pop(); } } } } var capture = function(design, board, player, pos, dir, dirs, trace, captured) { var p = design.navigate(player, pos, dir); if (p !== null) { var piece = board.getPiece(p); if (piece !== null) { if (piece.player == player) { _.each(trace, function(pos) { if (_.indexOf(captured, pos) < 0) { captured.push(pos); } }); } else { trace.push(p); capture(design, board, player, p, dir, dirs, trace, captured); if (trace.length > 1) { _.each(dirs, function(dir) { var pos = design.navigate(player, p, dir); if (pos !== null) { var piece = board.getPiece(pos); if ((piece !== null) && (piece.player != player)) { trace.push(pos); done(design, board, player, pos, dir, trace, captured); trace.pop(); } } }); } trace.pop(); } } } } var checkCapturing = function(design, board, pos, player, captured) { var trace = []; capture(design, board, player, pos, 3, [0, 1], trace, captured); capture(design, board, player, pos, 1, [3, 2], trace, captured); capture(design, board, player, pos, 2, [0, 1], trace, captured); capture(design, board, player, pos, 0, [3, 2], trace, captured); } Dagaz.Model.GetCover = function(design, board) { if (_.isUndefined(board.cover)) { board.cover = []; _.each(design.allPositions(), function(pos) { board.cover[pos] = []; if (board.getPiece(pos) === null) { var neighbors = []; var attackers = []; _.each(design.allDirections(), function(dir) { var p = design.navigate(1, pos, dir); if (p !== null) { var piece = board.getPiece(p); if (piece !== null) { neighbors.push(piece.player); attackers.push(piece.player); } else { while (p !== null) { piece = board.getPiece(p); if (piece !== null) { attackers.push(piece.player); break; } p = design.navigate(1, p, dir); } } } }); if (neighbors.length > 1) { var captured = []; if ((_.indexOf(attackers, 1) >= 0) && (_.indexOf(neighbors, 2) >= 0)) { checkCapturing(design, board, pos, 1, captured); } if ((_.indexOf(attackers, 2) >= 0) && (_.indexOf(neighbors, 1) >= 0)) { checkCapturing(design, board, pos, 2, captured); } if (captured.length > 0) { board.cover[pos] = _.uniq(captured); } } } }); } return board.cover; } , «», . , :
Dagaz.AI.heuristic = function(ai, design, board, move) { return move.actions.length; } ( ) — ! , :
, «» ( , «» ). , «» !
, , , custodian-:
!
Source: https://habr.com/ru/post/349516/
All Articles