Dagaz: Details
In the "pi" numbers do not count, “E” is infinitely the same.
And if you write them from the end, which one will be more?
Martin Gardner "Tic-tac-toe"
For this article, I wanted to choose a different epigraph, but found it too pathetic. The next release was delayed again. During this time, I managed to change jobs! Working at a new place takes a lot of energy, but I continue to find time for my little hobby. And I must say that what I have to face in the process is becoming more and more difficult. I will tell you about it. I wanted to start with another epigraph, but this one is also not bad.
At this time, there were new mankaly and " game-transitions " (this is Khalma and her relatives). A kind of race, in which it is necessary to occupy the opponent’s house with his figures, before him. Figures (both own and others) can be jumped (as in checkers ), but there are no takes. What am I explaining to you? Surely, many of you played Corners as a child.
')
At first glance, the game looks simple, but the problems started at the core level. Remember, I was talking about compound moves? For many reasons, it is more convenient to represent them as composite ones - as a whole, and not as a sequence of partial moves. This is more convenient for AI, and from the point of view of design, there are games, the description of which in the form of composite moves looks much more natural. But there is one problem.
In checkers, when performing a composite move, the pieces are removed from the board (possibly at the end of the turn). In Corners - you can jump over your own or your opponent’s figures to infinity. Literally. And no extensions here save, because everything is fixated without reaching them, in the core, even at the stage of generating the list of moves. I had to change this logic by implementing an option ( detect-loops ) there, which I should have thought about beforehand.
With the bot everything also came out not easy
The main problem with this family of games is that it is not so easy to choose an evaluation function that adequately represents the situation on the board. Since the goal of the game is to reach the enemy’s “home”, the total distance from all figures to the target fields ( Manhattan or Euclidean - without a difference) can be estimated, but in Khalm, with a successful set of circumstances, the figures can jump through the entire board in one move, so this assessment gives little.
With the target fields, too, not everything is clear. You can not send all the figures on the same field. The first figure that gets to him right there will take him. It would be ideal to determine the optimal target fields for each of the figures and move towards them, but it is difficult, in terms of computation. In addition, the situation on the board changes with each move. In general, I decided not to look far ahead and limit myself to a purely heuristic algorithm .
Not an ideal solution, but for the beginning quite working. If a bot sees a move that can “jump” into the enemy’s “home”, he chooses it. Otherwise - gradually reduces the distance to the target, trying to avoid congestion. The saddest situation can happen if one player (accidentally or deliberately) leaves his piece in the “house”, and the other - “locks” it with a double row of his pieces.
Just in case, I prohibit the opponent’s “locking” moves (if there is no viewing for many moves ahead, you can afford quite complex heuristics), setting negative evaluations for them, but the situation of “locking” empty target fields is no less dangerous for the bot (especially noticeable in the classical Hulme , with its purely orthogonal moves). In general, this bot has room to grow.
In games where it is allowed to take pieces, it is still more complicated. And there are many such games! Perhaps the most famous of these is the Camelot , invented by George Parker in 1930. But personally, I like a much less well-known game based on the same mechanics.
This game is the story itself! Back in 1908, the Suffragists invented it to promote their political views. Everything is there: the House of Commons, Albert Hall , the city prison and the hospital. Suffragist women are fighting cops. Their goal is to lead 6 of their people to the House of Commons. In their headquarters - Albert Hall, they can not enter. Move the pieces in any direction. Also allowed to jump over friendly and enemy pieces.
A series of jumps, at the same time, can be arbitrarily long. If it happens in the “arena”, the enemy figures, when jumping over them, are felled and sent to prison or hospital. Ordinary figures cut only diagonally, large ones (constables and suffragist leaders) in any direction. When in prison and hospital, 6 figures are recruited, they can be “exchanged” by re-entering the game. Thus, the figures, as in " Shogi " or " Pillar Drafts ", never leave the game.
With the target fields, too, not everything is clear. You can not send all the figures on the same field. The first figure that gets to him right there will take him. It would be ideal to determine the optimal target fields for each of the figures and move towards them, but it is difficult, in terms of computation. In addition, the situation on the board changes with each move. In general, I decided not to look far ahead and limit myself to a purely heuristic algorithm .
With such an assessment of the quality of the move
Dagaz.AI.heuristic = function(ai, design, board, move) { var t = getTargets(design, board, board.player); var m = getMove(move); var r = 1; if (m !== null) { if (!design.inZone(0, board.player, m.start)) { if (_.indexOf(t.first, m.end) >= 0) { r = 1000 + getDistance(t.first, m.start) - getDistance(t.first, m.end); } if (_.indexOf(t.goal, m.end) >= 0) { r = 700 + getDistance(t.first, m.start) - getDistance(t.first, m.end); } if ((r == 1) && (_.indexOf(t.second, m.end) >= 0)) { r = 500 - getDistance(t.second, m.end); } } if (r == 1) { if (design.inZone(2, board.player, m.end) && !design.inZone(2, board.player, m.start)) { r = 300; } } if (bestFound(design, board, 300)) return -1; if (r == 1) { var goals = getGoals(design, board, board.player); if (!_.isUndefined(goals[m.start])) { var goal = goals[m.start]; if (m.next == goal.next) { r = 100 + distance(goal.end, m.start) - distance(goal.end, m.end); } } } if (notBest(design, board, r)) return -1; var b = board.apply(move); if (isRestricted(design, b, board.player)) return -1; } return r; } Not an ideal solution, but for the beginning quite working. If a bot sees a move that can “jump” into the enemy’s “home”, he chooses it. Otherwise - gradually reduces the distance to the target, trying to avoid congestion. The saddest situation can happen if one player (accidentally or deliberately) leaves his piece in the “house”, and the other - “locks” it with a double row of his pieces.
Of course, the likelihood of such a situation is quite low.
Thanks to the rule proposed by Sydney Sachson, the inventor and collector of games from New York. His proposal is this: if a figure has the ability to leave his “home”, by jumping through the opponent’s figure or by a chain of jumps starting from such a move, she must do so. I tried various variants of the rules, excluding the possibility of locking the figures in their own "house" and found the rule of Sidney Sachson the most successful. After leaving his “home”, the figure can no longer return to it (although it has the right to pass through it, in the process of making the turn).
Just in case, I prohibit the opponent’s “locking” moves (if there is no viewing for many moves ahead, you can afford quite complex heuristics), setting negative evaluations for them, but the situation of “locking” empty target fields is no less dangerous for the bot (especially noticeable in the classical Hulme , with its purely orthogonal moves). In general, this bot has room to grow.
In games where it is allowed to take pieces, it is still more complicated. And there are many such games! Perhaps the most famous of these is the Camelot , invented by George Parker in 1930. But personally, I like a much less well-known game based on the same mechanics.
This game is the story itself! Back in 1908, the Suffragists invented it to promote their political views. Everything is there: the House of Commons, Albert Hall , the city prison and the hospital. Suffragist women are fighting cops. Their goal is to lead 6 of their people to the House of Commons. In their headquarters - Albert Hall, they can not enter. Move the pieces in any direction. Also allowed to jump over friendly and enemy pieces.
A series of jumps, at the same time, can be arbitrarily long. If it happens in the “arena”, the enemy figures, when jumping over them, are felled and sent to prison or hospital. Ordinary figures cut only diagonally, large ones (constables and suffragist leaders) in any direction. When in prison and hospital, 6 figures are recruited, they can be “exchanged” by re-entering the game. Thus, the figures, as in " Shogi " or " Pillar Drafts ", never leave the game.
In general, this entire release is about such options. For example, I finally mastered the correct transformation of pieces in Chess (until now, all the pawns turned only into queens, which is, generally speaking, wrong). I did not bother much with this and drew the selection dialog right on the canvas. It turned out not bad (I would like my hands to make them distinguish the mat from the stalemate, so it would be great at all).
Another "nuclear" refinement was associated with the improvement of the user interface and has its own background. In the project, there has been a mechanism for quite some time, which allows to encode the current position, passing it through the URL. Taking into account the fact that descriptions of all game states, in this format, are written to the log, it helps a lot in debugging. That's just the user, knowing nothing who knows about the browser log, there is little benefit from it.
No, no, it's not all good!
There are a number of games whose gameplay consists of a multitude of (possibly heterogeneous) stages. As an example, we can cite the popular game of the year 2008 - Kamisado . Each stage of this game (before passing one of the figures to the last rank) is relatively short, but after it ends, the game continues. Players, according to the agreed rules, once again place their pieces on the first line and again try to reach the last rank before the opponent (the piece that brought victory in the previous stage gets new abilities).
It is this aspect of the game that automates the " progressive-levels " option, which performs an automatic transition to the next stage of the game, when one of the players wins. And since the initial arrangement of figures differs from one stage to another, it is calculated by the common-setup module and passed to the next stage of the game via the URL .
Hand in hand with this opportunity, there is another way to diversify the initial arrangement of the figures. The " selector " option allows you to encode several initial arrangements (and even board configurations), within a single JS file . Update the Reversi homepage and you will understand what I mean.
It is this aspect of the game that automates the " progressive-levels " option, which performs an automatic transition to the next stage of the game, when one of the players wins. And since the initial arrangement of figures differs from one stage to another, it is calculated by the common-setup module and passed to the next stage of the game via the URL .
Hand in hand with this opportunity, there is another way to diversify the initial arrangement of the figures. The " selector " option allows you to encode several initial arrangements (and even board configurations), within a single JS file . Update the Reversi homepage and you will understand what I mean.
The new plug-in is designed to solve the problem. Structurally, this is an ordinary tree, in which all game states that have ever been in a game session are saved (and since this tree, in perspective, the entire history of the game can be uploaded to an SGF file). The user has the ability to "scroll" these states using the buttons that appear at the top of the screen.
This is really convenient, but you can get even more out of the two arrows that occupy a place at the top. This is what the " advisor-mode " option does. If the user thinks longer than the specified time, the bot with which he plays, calculates the move for him and puts the new game state in the “session-manager”. The proposed move can be accepted by simply pressing the “Forward” button. And if you don’t like the move, you can always roll it back.
A lot of joy in the development process, brought the sound (it would seem, what could be simpler). The first implementation was too naive. I do not know what it is connected with, but somewhere in the middle of the game, the sound just stopped playing, without any messages in the log. This manifested itself in all of my browsers until I began to cache the created Sound objects in memory. But here came another misfortune.
If the sound was played for a long time, and the bot understood quickly enough (as in mancala , for example), then the sound of its move was simply “swallowed”, which looked extremely unpleasant. Here the shaman had a long time and the case ended with crutches . With the “clonable” flag set, I still create several Sound instances, one for each player (even if they lose the same sound). Of course, this didn’t help with IE, which refused (for religious reasons, obviously) to deal with both wav and ogg files. This browser, for me, works silently!
Otherwise, the release was without incident. The company " Halme " and mankalam made up a couple of chess games , as well as a great many variations of Shogi , which I read in the next issue of " Il fogliaccio degli astratti " and another simple game from the Chinese comrades. Oh yeah, one more thing:
Just a short-term memory simulator. It is necessary to open the same pair (the lady with the lady, the king with the king, etc.) of the same color. For this points are given and for everything about everything 200 clicks. Since bonuses are awarded to points (for alternating red and black suits, for example), you can compete with friends for who has a better memory. Dare!
And all with Happy New Year!
Source: https://habr.com/ru/post/429494/
All Articles