Dagaz: Details
In the "pi" numbers do not count, "e" - infinitely as.
And if you write them from the end, what will be more?
Martin Gardner "Tic-tac-toe"
For this article, I wanted to choose another 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 take the opponent’s house with your own 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 already 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 the option (detect-loops ), which would be well worth thinking about in advance.
With the bot everything also came out not easy
Главная проблема, с этим семейством игр, заключается в том, что не так-то легко подобрать оценочную функцию, адекватно представляющую ситуацию на доске. Поскольку целью игры является достижение «дома» противника, можно оценивать суммарное расстояние от всех фигур до целевых полей (манхэттенское или евклидово — без разницы), но в Хальме, при удачном стечении обстоятельств, фигуры могут пропрыгать всю доску одним ходом, так что такая оценка мало что даёт.
С целевыми полями тоже не всё ясно. Нельзя направлять все фигуры на одно и то же поле. Первая фигура, которая до него доберётся тут же его и займёт. Идеально было бы определять оптимальные целевые поля для каждой из фигур и двигаться к ним, но это сложно, в вычислительном плане. Кроме того, ситуация на доске с каждым ходом меняется. В общем, я решил не заглядывать далеко вперёд и ограничиться чисто эвристическим алгоритмом.
Не идеальное решение, но для начала вполне рабочее. Если бот видит ход, которым можно «пропрыгать» в «дом» противника, он выбирает его. В противном случае — постепенно уменьшает расстояние до цели, стараясь избегать заторов. Самая печальная ситуация может случиться если один игрок (случайно или умышленно) оставит свою фигуру в «доме», а другой — «запрёт» её двойным рядом своих фигур.
На всякий случай, я запрещаю ходы «запирающие» противника (при отсутствии просмотра на много ходов вперёд, можно позволить себе довольно сложные эвристики), устанавливая им отрицательные оценки, но не менее опасна для бота и ситуация «запирания» пустых целевых полей (особенно это заметно в классической Хальме, с её чисто ортогональными ходами). В общем, этому боту есть куда расти.
В играх, где фигуры разрешается брать, всё ещё более усложняется. И таких игр много! Пожалуй, наиболее известной из них является "Камелот", придуманный Джорджем Паркером в 1930 году. Но лично мне куда больше нравится гораздо менее известная игра, построенная на основе той же механики.
Эта игра — сама история! В далёком 1908 году, Суфражистки придумали её для продвижения своих политических взглядов. Здесь есть всё: Палата общин, Альберт-холл, городская тюрьма и больница. Женщины-суфражистки сражаются с полисменами. Их цель — провести 6 своих человек в Палату общин. В свой штаб — Альберт-холл они заходить не могут. Перемещаются фигуры в любом направлении. Также допускаются прыжки через дружеские и вражеские фигуры.
Серия прыжков, при этом, может быть сколь угодно длинной. Если дело происходит на «арене», вражеские фигуры, при прыжке через них, срубаются и отправляются в тюрьму или больницу. Обычные фигуры рубят только по диагонали, крупные (констебли и лидеры суфражисток) — в любом направлении. Когда в тюрьме и больнице набирается по 6 фигур, их можно «обменять», снова введя в игру. Таким образом, фигуры, как в "Сёги" или "Столбовых шашках", никогда не покидают игру.
С целевыми полями тоже не всё ясно. Нельзя направлять все фигуры на одно и то же поле. Первая фигура, которая до него доберётся тут же его и займёт. Идеально было бы определять оптимальные целевые поля для каждой из фигур и двигаться к ним, но это сложно, в вычислительном плане. Кроме того, ситуация на доске с каждым ходом меняется. В общем, я решил не заглядывать далеко вперёд и ограничиться чисто эвристическим алгоритмом.
С такой вот оценкой качества хода
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;
}
Не идеальное решение, но для начала вполне рабочее. Если бот видит ход, которым можно «пропрыгать» в «дом» противника, он выбирает его. В противном случае — постепенно уменьшает расстояние до цели, стараясь избегать заторов. Самая печальная ситуация может случиться если один игрок (случайно или умышленно) оставит свою фигуру в «доме», а другой — «запрёт» её двойным рядом своих фигур.
Конечно, вероятность такой ситуации довольно низка
Благодаря правилу, предложенному Сидни Сэксоном — изобретателем и коллекционером игр из Нью Йорка. Его предложение заключается в следующем: если фигура имеет возможность покинуть свой «дом», прыжком через фигуру противника или цепочкой прыжков, начинающейся с такого хода — она обязана это сделать. Я опробовал различные варианты правил, исключающих возможность запирания фигур в их собственном «доме» и нашёл правило Сидни Сэксона наиболее удачным. После выхода из своего «дома», фигура более не может в него возвращаться (хотя и имеет право проходить через него, в процессе выполнения хода).
На всякий случай, я запрещаю ходы «запирающие» противника (при отсутствии просмотра на много ходов вперёд, можно позволить себе довольно сложные эвристики), устанавливая им отрицательные оценки, но не менее опасна для бота и ситуация «запирания» пустых целевых полей (особенно это заметно в классической Хальме, с её чисто ортогональными ходами). В общем, этому боту есть куда расти.
В играх, где фигуры разрешается брать, всё ещё более усложняется. И таких игр много! Пожалуй, наиболее известной из них является "Камелот", придуманный Джорджем Паркером в 1930 году. Но лично мне куда больше нравится гораздо менее известная игра, построенная на основе той же механики.
Эта игра — сама история! В далёком 1908 году, Суфражистки придумали её для продвижения своих политических взглядов. Здесь есть всё: Палата общин, Альберт-холл, городская тюрьма и больница. Женщины-суфражистки сражаются с полисменами. Их цель — провести 6 своих человек в Палату общин. В свой штаб — Альберт-холл они заходить не могут. Перемещаются фигуры в любом направлении. Также допускаются прыжки через дружеские и вражеские фигуры.
Серия прыжков, при этом, может быть сколь угодно длинной. Если дело происходит на «арене», вражеские фигуры, при прыжке через них, срубаются и отправляются в тюрьму или больницу. Обычные фигуры рубят только по диагонали, крупные (констебли и лидеры суфражисток) — в любом направлении. Когда в тюрьме и больнице набирается по 6 фигур, их можно «обменять», снова введя в игру. Таким образом, фигуры, как в "Сёги" или "Столбовых шашках", никогда не покидают игру.
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 get them to distinguish the mat from the stalemate, 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 for a long time already exists a mechanism that allows you to encode the current position, passing it through the URL. Taking into account that the descriptions of all game states, in this format, are recorded in 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!
Существует целый ряд игр, игровой процесс которых состоит из множества (возможно разнородных) этапов. В качестве примера, можно привести популярную игру 2008-го года — Kamisado. Каждый этап этой игры (до прохождения одной из фигур на последнюю горизонталь) относительно короткий, но по его завершении, игра продолжается. Игроки, по оговоренным правилам, вновь расставляют свои фигуры на первой линии и снова пытаются достичь последней горизонтали раньше противника (фигура, принесшая победу в предыдущем этапе получает новые способности).
Именно этот аспект игры автоматизирует опция "progressive-levels", выполняющая автоматический переход к следующему этапу игры, при победе одного из игроков. А поскольку начальная расстановка фигур от одного этапа к другому различается, она вычисляется модулем common-setup и передаётся в следующий этап игры через URL.
Рука об руку с этой возможностью идёт другой способ, позволяющий разнообразить начальную расстановку фигур. Опция "selector" позволяет кодировать несколько начальных расстановок (и даже конфигураций доски), в рамках одного JS-файла. Обновите начальную страницу Reversi и вы поймёте, что я имею в виду.
Именно этот аспект игры автоматизирует опция "progressive-levels", выполняющая автоматический переход к следующему этапу игры, при победе одного из игроков. А поскольку начальная расстановка фигур от одного этапа к другому различается, она вычисляется модулем common-setup и передаётся в следующий этап игры через URL.
Рука об руку с этой возможностью идёт другой способ, позволяющий разнообразить начальную расстановку фигур. Опция "selector" позволяет кодировать несколько начальных расстановок (и даже конфигураций доски), в рамках одного JS-файла. Обновите начальную страницу Reversi и вы поймёте, что я имею в виду.
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 game history 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). First implementationturned out to be 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 then another trouble came.
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 (apparently for religious reasons) 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 comprised 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!