Dagaz: Out of the Fog

All this is Queen Mab's rogue.
She in the stables mane braids
And knocks her hair with a pimple ...

William Shakespeare

It was a long release , but a lot was done. A session-manager appeared , allowing you to roll back erroneously made moves. Somewhere where sound design was added. And also, I came up with a cool way to push several alternative options for the initial placement into one game. And most importantly - I finally got to the games with incomplete information.

I will explain what is at stake. In board games we are used to, such as Chess or Checkers , players, at any time of the game, have complete information about the location of the pieces (their own and the opponent), the rules of their movement, the goals of the game, etc. Such games are quite well studied and belong to the category of " games with complete information ." Now imagine that some of this information may be hidden from the player.
')

The Fog of War is a great illustration of the theme. According to the rules of " Chess in the Dark ", players can see not all the opponent's pieces, but only those that are placed on the fields, which can be reached with one move of any of their pieces. I made two additions to this rule:

1. Of course, the player always sees his pieces, but by the way they are displayed - in a normal or translucent form, he can judge whether the opponent sees them.
2. Solely for decorative purposes, I have placed “clouds” on areas that are currently invisible.

Having mastered the general principle , I got a little carried away and made a huge number of games with the "fog of war." In addition to Chess itself , I have “dark” options for Syantsy , Changi , Shatrange , Sittuyin and many other games. There are even " Guns in the dark "! All these games have one thing in common:


However, in general, this is not a very correct approach. I want to see a bot who knows how to manage exactly the data that is available to his opponent - a man. Why is it important? Everything is very simple - by the way a bot plays, sometimes it is very easy to guess whether it has access to hidden information (spies) or not. And, of course, it is much more interesting for a person to play with the bot that does not spy (it is even more interesting to play with another person, but this is a separate story).

And here it is worth picking up a game that is a little different from Chess (since I am not ready to engage in developing an "honest" Chess-playing bot "in the dark"). There are a lot of such games and it’s impossible to say that they are simpler than Chess or Checkers. They are just different and require an individual approach.


To begin with, I decided to stop at BanQi - Chinese "Blind Chess". This is a very original game with hidden information, akin to "Jungle". For me it is important that the developments, in connection with the creation of a bot for this game, can be used in other games, such as Dou Shou Qi , Luzhan Qi , Stratego, or even (possibly) Tafl .


I'll tell you about the rules. The game takes place on the half board for "Chinese chess" ( Xiang Qi ), while the original layout of the board does not play any role. The figures are placed inside the cells (as in traditional), and not at the intersections of the lines (as in Chinese chess). At the beginning of the game, all the figures are carefully mixed and placed on the board face down (since the traditional figures of Xiangqi are sort of barrels, and their number coincides with the number of fields on the half of the board, this does not cause difficulties).

Next, the players alternate their moves. When making a move, the player can turn over any of the closed figures, or move the previously opened figure of his own color. The colors of the players are determined by the very first move. If the black piece is opened first, the player who opened it will play black. All the figures in the game go the same way (except for the “Guns” in the Taiwanese version, which I will talk about later) - one adjacent cell vertically or horizontally. The possibility of taking is determined by the order of precedence of the figures:

General> Counselor> Elephant> Wagon> Horse> Cannon> Soldier

The senior figures beat the younger or equal to them, with one exception: the soldier beats the general (a kind of " Rock-Paper-Scissors "). It remains to say a few words about the Taiwan BanQi:

1. Unlike the Chinese version, in Taiwan BanQi, a general can not beat a soldier.
2. The gun moves according to the rules of XiangQi , that is, to any number of fields orthogonal in a quiet way (like a chariot) or hits any opponent's piece, with a jump through the "carriage", when performing an attacking turn.

There is also a Hong Kong version, but it is practically no different from the Chinese, except that the order of the precedence of the figures has been changed. I decided to focus on the Taiwanese version of the rules, as the most interesting, in tactical terms.


First of all, it is important to understand that effectively using minimax algorithms is unlikely to succeed here. Moves that reveal previously hidden pieces, too radically change the assessment of the position. Without information about hidden figures, it is almost impossible to view a position for many moves ahead. But every cloud has a silver lining, but we can use much more complex (computationally) heuristics to evaluate the moves themselves!

I already have a bot evaluating the moves according to their heuristics (needed for one amusing game ). This is a very simple algorithm. All moves are sorted in descending order of heuristics (moves with a negative value of heuristics are generally discarded), after which they are viewed in order. If the next move leads to the position from which there is no response of the enemy, leading to immediate victory, the bot considers it the best. Using this algorithm, you can not bother with the assessment of the position, but you will have to sweat on heuristics .


Of course, I cache all the intermediate data in the game state, so as not to count them several times. In addition, one trick is used here, which is very useful in calculating connected areas. I iterate through the group array, enclosing additional elements inside the loop, as needed. All difficulties are connected with guns. For them, the targets of the chains are not the figures themselves, but the fields from which the latter can be attacked.


... depending on the length and parity of the chain, as well as the cost of attacking and attacking figures. But this is only half the battle! It is necessary to evaluate each of the possible moves using the constructed chains. I am introducing another intermediate structure - wishes to aggregate the available data. Assessment of the course consists of assessments of wishes, which it satisfies:


As for the getWish function itself , magic begins here (and this is the place where I most likely plowed and more than once). First of all, I share the assessment of moves based on open information and the introduction of new pieces into the game. This is not entirely correct, but for the time being I just don’t know how to reconcile such diverse assessments. If, based on open information, no wishes have been formed, the bot tries to discover new figures (there are also some tricks here).

1. If an enemy cannon is open, surrounded by closed figures, it makes sense to open one of the figures next to it, since it is likely that it will be able to attack the cannon, and the cannon cannot beat it anyway.
2. If the figure is different from the cannon, you can try to open the figure located through the "carriage" from it, because there is a chance that it will be a gun.
3. In the presence of an attacking chain from the side of the enemy, you can open one of the figures, next to the chain, to intercept the attack.
4. If you cannot protect the figure, you can open the figure next to it, trying to reduce the situation to exchange.

The player can estimate probabilities by keeping records of the figures who have left the game. In principle, the bot can do the same, but there is a simpler way - to view the still not open figures in a crowd and, based on the collected information, evaluate the probability of finding the desired one. At the same time, the success of the chosen move is not guaranteed, but if the probability of a favorable outcome is low, the move will not be chosen at all.


And for those who are still reading me, I can offer another funny puzzle game with hidden information:


I played it in my childhood, on a programmable calculator, called Fox Hunting. On the field, 8 foxes are randomly hidden, which must be found using the “spear method”. When you select an empty area, the total number of foxes in all eight directions is displayed. It is impossible to lose, but you can compete for the minimum number of clicks. And if you play in headphones, turn down the sound. Maybe I overdid it with sound effects.