AI for playing shogi (Japanese chess). Japanese chess (Shogi, Shogi)

Shogi board - 9x9 cells, numbered from top to bottom and from right to left. Cells are rectangular in shape, not marked in any way and have no color. "Above" are placed in three rows of white figures - pentagonal plates with hieroglyphic inscriptions, names of figures, "below" - in identical order, black figures. Two players play. "White" and "black" are the designation of the players, the figures in shogi of the same color, the belonging of the latter is determined by the direction of the acute angle of the board. The piece is always set with the sharp side towards the opponent. Each player has 20 pieces of 8 names, differing from each other in their value, strength and pattern of moves.

Each side has one king, one rook, one bishop, two gold generals, two silver generals, two knights, two spears, and nine pawns. In the extreme row, next to the spears, horses are located. Next to the horses are silver generals. Next to the silver generals are the gold generals. In the center, between the two golden generals, is the king. On the second row - only two figures. There is an elephant in front of the horse on the left side. Before the horse right side- rook. There are nine pawns in the third row.

Game order

Players take turns taking turns. Black moves first. A move is the movement of one of the pieces of its color available on the board to any allowed square according to the rules for moving pieces or (discarding) a piece in reserve. Pieces “in reserve” (or in other words “in hand”) are pieces taken (knocked down) from the enemy.

In shogi, when the pieces reach (enemy camp), they can be strengthened (transformed). When transformed, the figure is flipped. In shogi, any piece can be strengthened except for the king and the golden general.

The goal of the game is to checkmate the opponent's king. It is believed to have been placed mat, when the king is attacked by an enemy piece, i.e. is in a square where an enemy piece can move, but there is no opportunity to defend or leave.

Piece moves

Each player has 20 pieces: a king, a rook, a bishop, two gold generals, two silver generals, two knights, two spears, and nine pawns. All figures are marked with hieroglyphs on both sides, except for one-sided ones: the king and the golden general.

Figure		Stroke pattern
	- Japanese designation K - Latin designation	King moves
Just like in chess king moves one square in any direction, except for the square under the check of the opponent (eight different moves). shah- this is the position when the king is attacked by an enemy piece, i.e. is in a square where an enemy piece can move.		King moves
	Golden General (Kin) - Japanese designation G - Latin designation	Golden General Moves
Golden General can move one space horizontally or vertically in any direction, as well as diagonally forward (six different moves).		Golden General Moves
	- Japanese designation S - Latin designation	Silver General Moves
	- Japanese designation +S - Latin designation
Silver General can move one space diagonally in any direction, or one space vertically forward (five different moves). Upon reaching the enemy camp, can be turned into a golden general.
	- Japanese designation N - Latin designation	Knight moves
	- Japanese designation +N - latin designation
Like its chess counterpart, horse walks with the letter G, but only forward and without the possibility of retreat. Those. The knight's move is one square forward vertically, then one square diagonally to the right or left (two possible moves). This is the only piece that can jump over the pieces in the way. Upon reaching the enemy camp, can be turned into a golden general.
	- Japanese designation L - Latin designation	Spear moves
	- Japanese designation +L - latin designation
A spear moves only forward vertically to any number of squares not occupied by other pieces. Can't walk back. Upon reaching the enemy camp, it can be turned into a golden general.
	- Japanese designation P - Latin designation	pawn moves
	- Japanese designation +P - latin designation
Pawn moves one space forward vertically. Beats enemy pieces not obliquely, as in chess, but directly in front of him. Upon reaching the enemy camp, it can be turned into a golden general.
	- Japanese designation R - Latin designation	Rook moves
	- Japanese designation +R - latin designation
Rook moves horizontally and vertically to any number of squares not occupied by other pieces (similar to the chess Rook). Upon reaching the enemy camp, it can be turned into dragon king- a piece that, while retaining the capabilities of the Rook, can additionally move one square diagonally in any direction.
	- Japanese designation B - Latin designation	Elephant moves
	- Japanese designation +B - Latin designation
Elephant moves diagonally in any direction to any number of squares not occupied by other pieces (similar to a chess bishop). Upon reaching the enemy camp, can be turned into dragon horse- a piece that, while retaining the capabilities of the bishop, can additionally move one square vertically or horizontally in any direction.

The value of the pieces

In traditional chess, there is famous formula values of the pieces: where the pawn is taken as a unit of measurement, and then the knight and bishop are valued at three, the rook at five, and the queen at nine pawns. And every chess player in the world uses this formula to determine the material advantage, the achievement of which is the main strategic task in a chess game. In shogi, the material is not the same cornerstone like in chess.

When making exchanges, you should always consider specific situation On the desk. Depending on the degree of fortification of the royal fortresses, tactical possibilities and the general strategic pattern of the game, the strength of the pieces in shogi may vary. The ambiguity of the scale of values is also illustrated by some proverbs about the game. For example: "One pawn is worth more than a thousand golden generals", "A transformed elephant is worth three generals" or “At the end of the game, speed is more important than material”.

However, despite the ambiguity, the material balance is one of the most important criteria position evaluation. Koji Tanigawa, the 17th Lifetime Meijin, in his book How to Think to Win at Shogi, suggests the following scale of piece values:

Pawn - 1 point;
Spear - 5;
Horse - 6;
Silver General - 8;
Golden General - 9;
Converted silver. general - 9;
Transformed spear - 10;
Transformed horse - 10;
Promoted pawn - 12;
Elephant - 13;
Rook - 15;
Transformed elephant - 15;
Promoted rook - 17.

Taking pieces

A "capture" is a move to a square occupied by an opponent's piece. In this case, the opponent's piece is removed from the board and placed next to it. Unlike chess, where captured pieces are removed until the end of the game, in shogi they can later be used as one's own. These pieces are in the "reserve" ("in hand") and at any time such a piece can be placed (discarded) on any free field. In the diagrams, the captured pieces are shown off the board.

transformation

When a figure reaches the enemy camp (transformation zone) (see it has the opportunity to become transformed (the only exceptions are the king and the golden general, who cannot transform). But the transformation is not mandatory, it can be carried out at any next move (first move , then transform), but only if this piece is still in the opponent's camp. A piece can also be transformed outside the zone of transformation - at the moment it leaves it. When transforming, the piece is flipped immediately after the move and acquires the properties of the promoted piece. For most pieces these are the abilities of the golden general, the rook and bishop transform into the dragon king and dragon knight respectively (see) Reverse transformation is not allowed.

Promotion is mandatory for pieces that cannot continue the game with the properties of unpromoted pieces, such cases are possible for a pawn, a lance and a knight.

If the transformed figure is taken by the enemy, then it loses its abilities and acquires its original properties.

exhibiting

A piece that is “in hand” can be placed (discarded) on any free field of the board, which is considered the next move. A piece is only discarded in an unpromoted state (even if it was promoted before being captured). You can not put up on the field occupied by an opponent's piece. After being placed, a piece acquires the same rights as those on the board. If a piece is dropped into the opponent's camp, it can only transform by making the next move, even if it is made on a field outside the promotion zone.

Forbidden moves

The following moves are prohibited:

Doubling pawns (nifu). When there is an unpromoted pawn on one of the files, it is not allowed to place another pawn on the same file.
Exposing a pawn with checkmate (uchi-fu-tsume). It is not allowed to checkmate the opponent's king. However, it is allowed to declare checkmate by the next move of a pawn on the board.
Prohibited moves also include:
Wrong moves (kinte).
1. Exposed figure is locked. It is forbidden to discard pieces in such a way that they will not have the possibility of a move in the future. This situation occurs when a pawn, lance or knight is placed on the last rank, and for a knight - also when dropped to the penultimate rank.
2. The exhibited figure is immediately turned upside down.
3. The move was not made according to the rules.

The player who made the illegal move may be awarded a defeat.

Draw

Most shogi games end in either a checkmate or an acknowledgment of defeat by one of the players, but a draw is also possible.

Repetition. Trying to avoid losing or worsening the position, which is possible for both sides, players can consciously repeat moves.

A draw is declared when the following matches are repeated four times at the same time. three conditions:

position on the board;
figures "in hand";
sequence of moves;

Stalemate. Such a situation occurs extremely rarely, in the case when both kings have entered the opponent's camp and there is no possibility to checkmate.

In this case, the figures are counted. a rook and a bishop count as 5 points, the rest count as one. If both players have more than 24 points in total, then a draw is awarded. If one of the players has less than 24 points, he loses.

Perpetual check. In shogi, you cannot force a draw by perpetual check, as in chess. If, as a result of a series of checks by one of the opponents, the position was repeated three times, then the checker must change his move, otherwise he will be considered defeated.

Game history

Shogi is an ancient intellectual game. Its prototype originated in India. Later the game came to the territory of Europe and turned into modern classical chess. Around this time, the game made its way to China, and from there to Japan.

Shogi acquired its modern look only in the 16th century. It was then that the practice of the game adopted the unique system of iemoto (inherited headship) that is typical of Japanese schools. traditional arts. The position of shogi-dokoro was established - the main court teacher of shogi, who was identified in the course of constantly held championships. Only shogi-dokoro had the right to assign master titles.

In the 19th and 20th centuries, shogi began to develop actively. The rules of the game were fixed, the European Shogi Federation (FESA) was created. Now about 20 million people play shogi. 100 thousand constantly take part in tournaments. The top player is Yoshiharu Habu, with $1 million a year in sponsorship and advertising revenue.

Chess board

Chessboard 9x9 cells;
Cells of a rectangular shape, the same color;
Board numbering starts from the top right corner.

figures

King	Golden General	Transformed Silver General
Silver General	Horse	Transformed horse
A spear	Transformed spear	Pawn
promoted pawn	Rook	dragon king
Elephant	dragon horse

Rules of the game

Each figure, except for the king and the golden general, entering the transformation zone, can be replaced at any convenient moment with the corresponding transformed figure. Pawn, spear and knight must be promoted without fail. The reverse transformation is not possible for figures;
The “captured” piece can at any time return to the board and play on the side of the player who took it. Such a figure becomes simple. If a piece is placed in the transformation zone, then it must make at least one move in order to carry out the transformation;
Forbidden:
- Place a pawn on the same file as the unpromoted pawn;
- Checkmate with the exposed pawn. She must make at least one move;
- Position a piece in such a way that it cannot make a single move.

game over

If the moves of the opponents are repeated 4 times, then a draw is declared;
If the kings are in the camps of the opponents and checkmate is not possible, then the game ends. The total number of points is calculated (each figure has its own number of points). If both players have more than 24, then a draw is declared. If one has less, then he has lost;
If a player, declaring check, repeats the position 3 times, then he must either change it or be declared a loser.

Chess players about shogi

G. Kasparov:“Shogi is a unique game. I will try to study it in depth and go to Japan.”

R. Ponomarev:"I'm also fond of Chinese and Japanese chess, so I can try to become the first in them."

J. Lautier:“The world of shogi players made a deep impression on me. The well-known FIDE slogan "Gens Una Sumus" (we are all one family) absolutely corresponds to the world of shogi. I play shogi and enjoy it a lot. I'm just a beginner (probably a 1st dan amateur in my best form), but I loved the game from the very beginning, especially the idea of landing pieces near the enemy king... There are two important implications here that are very attractive to the traditional chess player: no simplification is possible, since no material is exchangeable, and more importantly, in games have a very low percentage of draws.

V.Kramnik:"Behind last years shogi became well known among chess players all over the world. I sincerely wish that a strong and fruitful friendship continues between the chess and shogi communities.”

According to modern historians, shogi is a separate branch of chess. Neither the moment of the appearance of this game, nor its original version is known exactly, but, apparently, in the second half of the first millennium of our era, it was widespread on Arab East shatranj came to China, where it became the basis for the game xiangqi (sinqi), from which, in turn, shogi originated.

The first documented evidence of a chess game in Japan dates back to the 8th century, but it is not known exactly what kind of game it was. It can only be reliably stated that at that time the Chinese version of chess, xiangqi, came to Japan from China, but at the same time other chess-type games appeared in the country. Among these games was the 9x9 board game on which modern shogi is played. Descriptions of the games of that time have not been preserved, so one can only guess about their form. The Korean version of chess is known - changi, which in many respects is between shogi and xiangqi, so it can be assumed that shogi was the result of a gradual transformation of Chinese xiangqi, not avoiding the influence of European chess (for example, the rules for turning pieces that have reached the last horizontals into more strong, could not have been borrowed from the Chinese - there are simply no such rules in xiangqi; on the other hand, there is no documentary evidence that this feature was introduced into shogi by analogy with European chess - the Japanese could well have invented it independently, especially since the transformation mechanism quite different from the European one).

The first archaeological finds of shogi figures date back to the 11th century. These figures already have quite modern look- pentagonal flat chips with hieroglyphic designations. More or less detailed descriptions shogi appeared in documents from the Heian era. At this time, there were "small shogi" and "big shogi". "Small" were played on a 9x9 board, "large" - on a 13x13 board. The pieces and moves were the same as now, but the main difference between modern shogi and chess was missing - the possibility of re-introducing captured enemy pieces on one's side into the game. In subsequent centuries, attempts were made to play shogi on large boards:

Medium shogi - board 12x12, 92 pieces.
Large shogi - board 15x15, 130 pieces.
Big-big shogi - board 17x17, 192 pieces.
Maka big-big shogi - board 19x19, 192 pieces.
Tai shogi - board 25x25, 354 pieces.

Finally, in the 16th century, Emperor Go-Nara created the game of shogi that is known today. Taking “small shogi” on a 9x9 board as a basis, he reduced the number of pieces to 40 and introduced a fundamentally new rule - now the opponent’s pieces taken by the player passed to the taker and he could at any moment, instead of his next move, put any of these pieces on the board as his own . This innovation radically changed the strategy and tactics of the game. From him, in fact, the history of modern shogi should be counted.

In the 17th century, shogi, along with go, received a privileged status due to the fact that they were fond of the then military leaders and rulers of Japan - Oda Nobunaga, Toyotomi Hideyoshi and Tokugawa Ieyasu. In the days of the shogunate, there was even a court position shogidokoro (shogi minister) - the strongest player was appointed to it, he was in charge of organizing shogi at the court, distributed government subsidies schools, authorized the assignment of the highest ranks. At the same time, the title Meijin ("great master") appeared, which was used to mark the strongest shogi player, similar to Meijin in go. The Meijin rank was for life - having received it once, the player remained a Meijin for the rest of his days, regardless of changes in the level of the game. At first, the post of Minister of Go and Shogi was held by one person - Hongimbo Sansa, on high level played both games. Then Sokei Ohashi (- ), defeated Hongimbo Sansa in a match. He became the first shogidokoro and Meijin in shogi. Until the 19th century, the development of shogi proceeded in the “iemoto” system - in the form of “family” schools, where skill was inherited, from older masters to young ones.

Shogi was actively developed, to XIX century the theory of the game was already quite well developed, there were several schools, literature came out. When, during the Meiji Restoration, shogi lost state support, this did not become a serious shock for them - newspapers began to actively organize tournaments and print games. By 1924, the Tokyo Shogi Federation was established, which later became the All Japan Professional Shogi League. In 1935, the Meijin title for life was abolished, and instead the title was played at an annual championship.

Rules of the game

Board and starting position

There are two players, black and white (sente 先手 and gote 後手). The board is divided into rectangular cells or fields. The size of the board is 9x9 cells. Cells are not marked in any way and have no color.

Each player has a set of twenty pieces. The figure is a flat block of wood in the form of an obelisk (an elongated pentagon), on both surfaces of which the name of the main and transformed figure is written in hieroglyphs. All the pieces are of the same color, and differ only in their orientation on the board: the piece is always placed with its sharp side towards the opponent. The figures vary slightly in size: the more important the figure, the larger it is.

Basic figures with which the game starts:

Moves similarly to a chess king - one square in any direction. - - - Rook- Hee (hisya) - (1 each).

	｜
―	飛	―
	｜

It moves similarly to a chess rook - to any number of squares horizontally and vertically. royal dragon (The Dragon) - Ryu. Converted rook.

○	｜	○
―	竜	―
○	｜	○

It has moves of the usual rook and king, i.e. it can protect itself from attacks from neighboring diagonal cells. Elephant- Kaku (kakugyo) - (1 each).

＼		／
	角
／		＼

It moves similarly to a chess elephant - to any number of squares diagonally. dragon horse (Horse) - Uma. Transformed elephant.

＼	○	／
○	馬	○
／	○	＼

It has moves of the usual bishop and king. Accordingly, it protects itself from attacks from adjacent horizontal and vertical cells. Golden General(briefly Gold) - Kin (kinsho) - (2 each).

○	○	○
○	金	○
	○

Moves one space horizontally or vertically in any direction, as well as one space forward diagonally. That is, it has moves of the king, except for two squares back diagonally. - - - Silver General (Silver) - Gin (ginsho) - (2 each).

○	○	○
	銀
○		○

Moves one space diagonally in any direction, as well as one space forward vertically. That is, it has the moves of the king, except for three fields vertically down and horizontally to the left and right. In early versions of shogi, this figure was called an elephant (4 legs - diagonally and a trunk - one cell forward). Transformed Silver- Narigin.

○	○	○
○	全	○
	○

Walks like a golden general. Horse- Kei (keyma) - (2 each).

☆		☆

	桂

It moves forward with the letter “G”, that is, two fields forward vertically, after which one field to the right or left horizontally (that is, unlike a chess knight, it has only two possible moves and moves only forward). Like a chess horse, it can jump over its own and enemy pieces during the move. Transformed horse- Narike. Moves to any number of unoccupied fields only forward vertically. Doesn't come back. Transformed Spear- Narikyo.

○	○	○
○	杏	○
	○

Walks like a golden general. * Pawn- Fu (fuhyo) - (9 each).

	○
■	歩	■

Moves one field only forward vertically. Unlike a chess pawn, it beats in the same way as it moves. Tokin- That (Tokin). Converted pawn.

moves

The player can put any piece from the reserve on the board instead of his next move. It is forbidden:

to place a pawn on a square where it checkmates the opponent's king;
place a piece on a field where it will not be able to move according to the rules;
place a pawn on a board vertical on which an unpromoted pawn of the same player already stands.

A reserve piece can only be placed on the field in an unpromoted state.

The player who made the illegal move immediately loses

transformations

Transformation Zone (green)

The king and golden general do not transform.
The Silver General, Knight, Spear and Pawn turn into a Gold General. In order not to confuse the promoted golden generals with the unpromoted ones, the transformed pieces of the silver general, knight, spear and pawn have their own names and are depicted in other hieroglyphs, although according to the rules of moves all these pieces are a golden general.
The rook turns into the dragon king (Ryu), which, in addition to the capabilities of the rook, gains the ability to move one square diagonally in any direction.
The bishop turns into a horse-dragon (Uma), which, in addition to the capabilities of the bishop, can walk one field vertically or horizontally in any direction.

When transformed, the figure simply turns over to the other side, where the sign of the transformed figure is depicted. Transformation is one-time - once a figure has been transformed, it can no longer be transformed.

The transformation is usually not necessary: the piece can remain the same and be transformed on one of the following moves (at the request of the player). To transform, the player must make a move with this piece, and the initial or final field of the move must be in the transformation zone. Promotion is mandatory if, after the move, the unpromoted piece is no longer able to move according to the rules - for example, when a pawn reaches the last rank or a knight reaches the penultimate or last rank. If the promoted piece is taken by the opponent, he can only remove it from the reserve as an ordinary (non-transformed) one, and it is allowed to transform it only on the next move.

Outcome of the game

As in chess, the threat of taking the king - check - requires the player to either take the king to another square or cover it with his piece. You can't leave the King in check. The game ends when one of the sides checkmates the opponent's king, that is, it creates a position where the opponent's king is in check, and the opponent cannot eliminate this check with any move. The checkmate wins. Stalemate is not possible in shogi.

Besides, in professional games additional rules that limit the possibility of delaying games apply:

If the same position is repeated four times, the game ends without announcing the result and must be replayed.
If the position is repeated three times as a result of a series of checks (analogous to the perpetual check in classical chess), then for the fourth time the player who announced the checks must choose some other move, otherwise he will lose.
If the king of one of the players went to the enemy's camp, it becomes almost impossible to checkmate him. When both kings have advanced to the opponent's camp, the game can continue indefinitely, since it seems that neither player will be able to checkmate. This situation is called "ji-shogi" ("dead end"). The game is terminated if both players (and the observer or referee, if we are talking about an official game) agree that the current position is a dead end. The result is determined by scoring. Points are awarded for all the player's pieces, including reserve ones, except for kings. Bishops and rooks are worth 5 points, all other pieces are worth 1 point. If one of the players has less than 24 points, then he is declared the loser. If both players have at least 24 points, a draw is declared. In unofficial games, this rule does not always apply: by agreement of the players, a dead-end position can simply lead to a draw.

Analysis

Yagura Fortress - known in theory defensive formation when the king is tightly surrounded by pieces

Pieces in shogi move short distances, so the game usually lasts a long time. Often dozens of moves, both opponents slowly rebuild the pieces in their zone before starting to approach.

Due to the presence of a reserve, in tactical terms, shogi is more similar not to classical chess, but to Swedish chess or to

In many openings, bishops are exchanged on the first moves, which immediately sharpens the situation.

A typical tactic is an attack with spare pieces, in which first several pieces are sacrificed to make room around the enemy king, and then the last one checkmates. Often both sides try to carry out such combinations at the same time, which leads to exchanges and further aggravation of the situation. Nevertheless, a relatively calm positional play is also possible if one of the sides chooses “passive tactics”, trying to protect the king to the maximum and not create sharp situations. In such cases, the party may be delayed.

Because the pieces never leave the game, there is no distinct endgame. Theoretically, the party can last indefinitely. Shogi theory recommends special formations ("fortresses") when the king is surrounded large quantity figures, and the assault on such a fortress is extremely difficult. If neither side shows a clear desire for attack and combinations, but focuses on defense, it can be extremely difficult to win. This is considered a disadvantage of the game of shogi - that the defensive strategy makes it almost impossible for the opponent to win with the right defense.

Building programs that can play mind games is a very interesting task of great practical and scientific value.

The first attempts to create machines for playing intellectual games (primarily chess) appeared long before the advent of computers. Around 1769, the well-known chess apparatus "mechanical Turk" appeared. The machine played quite well, but its whole secret lay in a strong chess player hidden inside.

In the 20th century mechanical machines lost ground to digital computers. A pioneer in this field (as in many others) can be called the famous mathematician Alan Turing. By modern standards, the algorithm he developed was very primitive, and due to the lack of access to real computers, the algorithm had to be executed manually.

Around the same time, Claude Shannon justified the existence best move for any position. He even proposed an algorithm for finding such a move for any game on a finite board. Unfortunately, despite the existence optimal algorithm, his practical implementation impossible due to limited hardware and time resources.

Since the time of Shannon, the task of programming mind games has moved from the field of entertainment to the field of serious research. In recent years, based on Shannon's research, practical algorithms have been built, with the help of which computers have learned to play checkers accurately and achieve outstanding success in chess and go.

Japanese shogi chess is one of the few games where a person is still stronger than a computer. First of all, this is due to the possibility of returning captured pieces to the game, this rule dramatically increases the number of possible moves, which means that it makes it difficult to analyze the game. If in chess you can make about 40 moves from an arbitrary position, then in shogi the number of possible moves is measured in hundreds.

Rules of the game

Before talking about building algorithms for playing shogi, it is necessary to describe the rules of this game.

figures

There are 8 different pieces in shogi (if you count the inverted pieces, then 14). The rules of moves for various pieces are presented in the table:

If we analyze the table, we can make the following observations:

There are only two long-range pieces in shogi: a rook and a bishop;
Retreat options for many pieces are limited or non-existent.

These observations allow us to divide all the figures into four groups:

A king of absolute value;
Senior pieces (rook and bishop) capable of long-range attacks and quick retreats;
Generals (gold and silver) whose offensive capabilities greatly exceed those of retreat;
Minor pieces (knight, arrow, pawn) unable to retreat.

Initial arrangement and turn order

Shogi is played by two players, commonly referred to as sente (go first) and gote (go second), on a 9x9 square board. The initial arrangement of the figures is shown in the figure:

Also, each player has a special stand (komadai), where the pieces taken from the enemy are placed. It is also customary to say that captured pieces are "in hand".

Coups

The last three ranks (relative to each player) are the flip zone. Any non-flipped piece (except gold and king) that starts or ends its turn inside this zone can flip and turn into another piece. The transformation rules are fixed and shown in the table:

It is important to note that the player decides whether to flip the piece or not. Cases where a flip is necessary are described in the illegal moves section.

Resets

The reset rule is what makes the game of shogi one of the most challenging games invented by mankind. The essence of the rule is that any figure eaten from the enemy can be put on any free field as his own.

There are a few restrictions on the reset rule, but they are quite simple:

All pieces are discarded not flipped (even if they are dropped into the flip zone);
It is not allowed to drop a pawn on the vertical where there is already a pawn (tokin is not considered a pawn);
You can't drop a checkmate pawn.

Forbidden moves

If the opponent made an illegal move, he will immediately lose, so it is extremely important to know the list of illegal moves:

Moves that violate the rules (for example, missing gold diagonally);
Violation of the reset rules (for example, dropping the second pawn to the vertical);
A move after which the piece cannot make a single move. This rule needs some explanation. You cannot move a pawn to the last rank without a flip or a knight to the last or penultimate rank without a flip. Obviously, it is impossible to drop pieces in this way.

The situation with leaving the king in check is not entirely clear. If the player did not notice the check to his king, then on the next move, the opponent can (but is not required to) eat the king. In this case, the game is considered over.

End of the game

The game ends when one of the players checkmates or makes an illegal move. But in shogi, there are additional rules for ending the game:

If the position is repeated three times as a result of a continuous series of checks (the so-called "perpetual check"), then on the fourth time the attacking player must make a different move, otherwise he will be defeated.
If the position is repeated 4 times without the announcement of a check, then the players replay the game without announcing the results, but with a change of color for the remaining time.

The above rules make a draw extremely rare for shogi (no more than 3% of all games played). But nevertheless, a draw is possible in one case: if both kings entered the opponent's camp and fortified there. If both players agree that the situation that has arisen is a deadlock, then scoring occurs. All pieces (including those in the hand) except for the king, bishop and rook are valued at 1 point, the bishop and rook - at 5 points, the king does not participate in the calculation.

In professional games, the player who has less than 24 points loses, if both players have at least 24 points, then a draw is declared. In amateur games, the one who has at least 27 points wins, if both players have 27 points, then the victory is awarded by the gote.

Algorithm for finding the best move

MiniMax Algorithm

For the first time, the strategy of finding the best move for any given position was described by Claude Shannon. If you think a little, you can see that this strategy is quite simple and applicable to any game.

Suppose we have some position in which we need to make an optimal move. First, you need to generate all the moves allowed by the rules. Then each of the correct moves must be evaluated. Moves leading to victory will be rated +1, leading to defeat will be -1, and moves leading to draw positions will be rated 0.

In order to determine what result the move in question will lead us to, we must assume that the opponent will respond to each of our moves with the best possible way. Those. will actually use the algorithm under consideration: it will generate all its correct moves and choose the best among them, and to assess how good its move is, it will assume that we will answer in the best possible way, etc.

It turns out that in the procedure for finding the best move on our part, the procedure for finding the best answer from the opponent will be called, from which the procedure for finding our best answer to the opponent’s answer will be called, etc.

The search function for the best move will recursively call itself until a mating or draw situation occurs.

At the same time, the evaluation of the final position is not difficult, and when evaluating parent nodes, the following rules are used:

The move score for the first player is computed as the maximum scores of the child nodes;
The move score for the second player is calculated as the minimum of the scores of the child nodes.

This algorithm is called MiniMax. If you graphically depict the chain of calls, you get the so-called. game tree:

Each node in this tree represents one analyzed move. The score of a node will be equal to the maximum score of its child nodes. The following shows the order in which the nodes will be analyzed (green - win, red - defeat, yellow - draw):

Alpha-Beta clipping

In the example above, in order to obtain the final score of node Y0, we had to obtain estimates for all other nodes Y1-Y16, but in fact this was not necessary: as soon as we learned that node Y1 leads to victory, the need to analyze the nodes Y7- U16 disappears, because. any estimates obtained for those nodes will not exceed the estimate of node U1 (because it is maximum), which means that there is simply no move better than U1. Given this, the analyzed tree will look like this:

It is obvious that such an abbreviated analysis does not worsen the accuracy of the solution, but significantly reduces the search time for the best move. It is the idea of \u200b\u200b"pruning" unpromising tree branches that underlies the Alpha-Beta pruning algorithm.

When using cutoffs, two additional variables are introduced: the minimum for sente (A) and the maximum for gote (B). The Alpha-Beta clipping algorithm itself is similar to the MiniMax algorithm, except for the following points:

1. If the estimate of any move is out of range , then the analysis of the branch can be terminated ahead of schedule, because the players have moves leading to a better position.

If at any time the score of the first player becomes greater than A, then the value of A is updated;
The same is done with the score B for the second player.

An important point when using this algorithm is the order in which the moves are viewed. If we first consider those moves that narrow the range the most, then the number of cut branches will be quite large. Returning to the tree discussed above, it is easy to see that the order of viewing Y7, Y12, Y1 will give a much smaller performance gain. Therefore, before using cut-off algorithms, moves are pre-sorted according to the expected efficiency.

Of course, it is impossible to know in advance which move will be the best, but there are some heuristics. For example, moves-captures, checks, moves that improve the position, etc. are considered good.

Position evaluation function

All the algorithms described above scan game tree to the full depth, but it is almost impossible to implement such algorithms in practice, so the viewing depth is artificially limited: recursive calls are stopped not only in cases of checkmate and draws, but also when the maximum analysis depth is reached. Mats when viewing a tree at a limited depth are relatively rare, and all non-mat positions have to be assigned some heuristic estimate, which is obtained using the methods described below.

Material valuation

In most chess-like games, a very accurate evaluation of a position is the evaluation of the material. In this case, each piece is assigned a certain value, and the assessment of the position for the player is the difference between the sum of his pieces and the sum of the opponent's pieces. Shogi also uses material valuation, the figure cost table is given below:

All pieces in the hand are valued at 30% more. their mobility due to the possibility of resetting increases significantly.

The high cost of the king and tokin requires some explanation. Such a high cost of the king is explained by the fact that the king is a figure of absolute importance, the game ends with his loss, therefore the king is valued more than all other pieces combined. And the cost of tokin is so high because tokin is the best piece for exchanges: when exchanging token-silver, one player gets a silver general in his hand, and the second player gets just a pawn.

Strategic assessment

Before talking about the importance of strategic evaluation, it is necessary to reiterate the fact that pieces never leave the game and all captured pieces can return at any time. This fact radically changes the approach to assessing a position.

First, the exchange heuristic, which is extremely effective in chess-like games, becomes not only ineffective, but also harmful. If in chess you win one pawn and constantly go for equivalent exchanges, then in the endgame the advantage of one pawn often turns out to be decisive. In shogi, such exchanges can result in enemy pieces being thrown into your camp.

Secondly, victims are very popular in shogi. For example, at the end of the game, it is often necessary to give up a senior piece for a golden general or a knight in order to get a piece in hand that can be checked out or an effective fork made.

If you look at what these two situations have in common, you can see that the enemy took advantage of the unfortunate arrangement of your pieces. In such cases, it is customary to say that the pieces are in "bad shape". In shogi, form is often more important than material advantage, so the characteristics of form must necessarily be evaluated when evaluating a position. The figures below show examples of bad and good forms (unprotected generals are highlighted in red):

A further development of the idea of "good forms" are fortresses - fortifications for the king, providing him with security and protecting him from checks. Examples of common fortresses are shown in the table:

It is clear that good shape should give some plus to the strategic assessment, and bad forms, respectively, worsen the assessment, but in addition to the form, it is also necessary to take into account the control of the board, the proximity of the generals to their own or enemy king, the presence of locked pieces, etc...

Summing up the above, it should be noted once again that in the function of assessing a position, it is necessary to take into account not only the material component, but also the strategic one.

Selective renewal algorithm

The already considered MiniMax and Alpha-Beta cutting algorithms always find the best move at a given depth, but the problem is that the analysis depth (8-10 moves) is not enough for a strong game. Professionals calculate positions for 12-14 moves, and some positions for more than 20 moves. Such a depth for computers is still unattainable.
Some compromise is to scan only some branches of the tree to a significant depth, while other branches will be scanned to a reduced depth. This approach is called the selective renewal method.

In chess programs, checks, pawn moves to the last rank, and strong captures are usually extended. But in shogi, this approach is ineffective. It was decided to search without a fixed depth, increasing the depth step by step. In this case, all possible moves can theoretically be considered at different depths, so it is necessary to additionally memorize the depth to which each move was considered.

Initially, the depth of each move is 0, and the score of the move is -INF (i.e. loss). At the first iteration, the position is analyzed to depth 1 for all moves, while each move receives its own efficiency score, and its viewing depth is increased by 1. Then all moves are ordered by efficiency, and the best moves are analyzed to depth 2. If during the next extension it turns out that the move with the maximum score has already been analyzed to the maximum depth, then this move is excluded from further consideration. The deepening process continues until all moves have been scanned to the minimum depth. The figure below shows an approximate tree construction order when using selective extensions ( maximum depth- 4, minimum depth - 2, the nodes show the estimated position at the current viewing depth):

An additional advantage of this algorithm is its effectiveness in games with a time limit: when the time allotted for a move expires, you can return the best of the calculated results.

caching

It is known that caching is one of the most effective ways increase the speed of programs. In the context of building game algorithms, caching is used to search for already analyzed positions.

Indeed, while searching for the best move, some positions may be repeated within the same branch or occur in different branches of the tree. The classical algorithm would consider each such position anew. Such multiple calculations significantly reduce the overall performance. Caching is designed to eliminate the need to perform repeated calculations.

The search for a position in the cache is based on comparing the hash function of the position in question with the hash functions of positions already in the cache. A feature of most hash functions is the presence of collisions (situations where different inputs give same value). For games, this behavior of hash functions is unacceptable, because even the slightest change in position greatly affects the optimal move. Given the above, it was decided to use as a hash function a string that uniquely describes the position.

To use results caching, the following changes must be made to the algorithm for finding the best move:

Before starting the calculation, check the presence of a position in the cache;
If the position is contained in the cache, then stop the calculation and return the previously obtained value;
When the calculation is completed, write the result to the cache;

There is another rather subtle point. If the cache already contains the desired position, calculated to a small depth, this result can also be used. Recall that the Alpha-Beta clipping algorithm is very sensitive to move order. Practice shows that an estimate obtained with a small calculation depth is a fairly high-quality heuristic estimate of the quality of a move. Those. the values stored in the cache can be used to sort moves before calling Alpha-Beta cuts.

The effectiveness of cache usage can be estimated using the following graph, which shows the dependence of the position calculation depth depending on the time and number of repeated accesses.

The graph shows that the use of cache significantly increases the depth of calculation for repeating positions. For example, with a time limit of 5 seconds per move, using the cache allows you to achieve the same depth of analysis as a 100-second analysis without using the cache.

That. it can be concluded that the use of caching significantly increases the speed of analysis, but requires significant memory costs for storing processed positions.

And as a conclusion small example games developed by the program against the program Shogi Lvl. 100:

What do you know about Shogi (将棋), a Japanese board game logic game related to chess.

Shogi can be translated as "game of generals". Ka and chess are played by two players, black and white (sente 先手 and gote 後手). The board is also divided into rectangular cells or fields. The size of the board is 9×9 cells. Cells are not marked in any way and have no color.

The total number of participating figures is forty; 20 figures for each participant.
The figure is a flat block of wood in the form of an obelisk (an elongated pentagon), on both surfaces of which the name of the main and transformed figure is written in hieroglyphs. All the pieces are of the same color, and differ only in their orientation on the board: the piece is always placed with its sharp side towards the opponent. The figures vary slightly in size: the more important the figure, the larger it is.
As in chess, the main pieces are the king (王将), rook (飛車), bishop (角行), golden general (金将), silver general (銀将), knight (桂馬), spear (香車), and pawns. (歩兵) moving according to the rank rules.

Moves are made in turn, the first move is made by black. On each move, a player can move one of his pieces in accordance with the rules of its move. When moving to a field occupied by an opponent's piece, this piece is taken - removed from the board and put into the reserve for the player who took it. A reserve piece can only be placed on the field in an unpromoted state. The player who made the illegal move immediately loses.
As in chess, the game ends when one of the sides checkmates the opponent's king, that is, it creates a position where the opponent's king is in check, and the opponent cannot eliminate this check with any move. The checkmate wins. Unlike chess, the king is not in check. If the player whose king was under attack did not notice this and did not defend his king, the opponent has the right to take the king on the next move, which also brings a win.

The last three horizontals of the board (relative to each of the players) are the so-called "transformation zone". A piece that moves into or out of the promotion zone can be promoted. The transformation is not a separate move, it occurs on the same move as the movement of the piece. Unlike chess, the transformation of pieces is not at the choice of the player, but certain rules- when transformed, the figure simply turns over to the other side, where the sign of the transformed figure is depicted.
Transformation is one-time - once a figure has been transformed, it can no longer be transformed.
The most important difference between shogi and chess is that there is no pronounced endgame, since the pieces never leave the game. Theoretically, the party can last indefinitely. Shogi theory recommends special formations ("fortresses"), when the king is surrounded by a large number of pieces, and the assault on such a fortress is extremely difficult.

Today, the game is widely played in Japan (by some estimates, there are at least 20 million people playing it), surpassing all other board games, including Go and Renju, in popularity.

The organization of sports shogi is very close to the organization of go - in the same way there is a professional shogi league that conducts professional tournaments and assigns ranks to players, there is also a system of ranks "kyu-dan", indicating the strength of the player, and in two versions - amateur and professional. The lowest rank is 15 kyu, with an increase in the level, the kyu rank decreases. After 1st kyu, 1st dan follows, with further growth, the rank of dan increases. The traditional limit for amateur ranks is 7 dan.

The professional shogi league selects players according to very strict criteria: only a player no older than 20 years old who has already reached the level of 5 amateur dan can enter it. Thus, only those who have shown outstanding abilities and a penchant for the game from childhood get into the professionals. Upon admission to the league, the player is assigned 5 professional kyu. With a successful game, a professional reaches 1 kyu, then receives 1 professional dan. The maximum rank for a professional is 9 dan.

Every year 7 professional shogi titles are played in Japan: Ryuo, Meijin, Kisei, Oi, Oza, Kio, Osyo. The incomes of professionals are quite high - the best Japanese player earns about $1 million a year, the players of the top ten - about 250-300 thousand, ordinary professionals - about 100 thousand dollars.
If you have a talent for Shogo, then aim for fifth dan by making history as the first professional foreigner to play Shogo. So far, no foreigner has been able to become a Japanese shogi professional. So keep it up!

If you are in Tokyo and you are interested in the Shogo game, then visit the Headquarters of the Japan Shogi Association (Shogi Kaikan) in the Sendagai area, where you can learn everything about this game.