Shogi AI (Japanese Chess)
There is one old Japanese game of shogi . Sometimes it is called Japanese chess. I will not argue that there is something in common with these games, but shogi is much more difficult. I first learned about this game from the commentary on Habré, where it was claimed that this is one of the most difficult games, and the best computer programs still cannot beat the strongest human players. Of course, I became interested and started playing. During the year I achieved some success and even won second place among newcomers to the official tournament. Given my love of programming, the next step was obvious - to write my own AI. This will be the story below.
Immediately I did not dare to write AI for real shogi on the 9 by 9 field and decided to start with a simplified version of the game on the 5 by 5 field (this field is often used by beginners). If you read the full rules of the game on Wikipedia, then the following section will be much easier to understand.
Let's agree that from now on, I will write “shogi”, but imply a simplified version of the game on the field 5 by 5.
The first thing you need to figure out when learning a new game is the moves. There are 10 different shapes in shogi. The designations of figures, their names and possible moves are presented in the table below:
Surely, you have noticed that among the figures there are “turned doubles”, which are often stronger than the original. The principle of gaining in shogi is similar to chess, but if in chess, only a pawn turns, and it turns into an arbitrary piece, then all pieces except for gold and the king turn over in shogi. To achieve a coup, you must start or end the course on the opponent’s last line. In general, the coup is arbitrary: i.e. You can walk the rook to the last rank, but not turn it over, and return to your camp with a coup next turn (because you started the turn on the last diagonal). Naturally, the pawn is obliged to roll over if it has reached the coup zone.
If you have read this far, you may think that shogi are some kind of chess or checkers, but I assure you that it is not. In Shogi there is one nuance that immediately makes this game several orders of magnitude more difficult.
Any figure eaten by an opponent can be put on any free field as your own. Such an action is called a reset (although I personally like the word “space marines”, which was first used in this context by Andrei Vasnetsov).
True, there are a few limitations when resetting, but they are quite simple:
The reset rule may seem insignificant to you, but it radically changes the whole strategy of the game. If in chess or checkers it is enough to get a small material advantage, and then constantly go for exchanges and win in the endgame, then in sego exchanges lead to a more tense position and complication of miscalculation.
The game takes place on a square field with a side of 5 cells. At the beginning of the game on the field is as follows:
For reasons unknown to me, black is the first to begin in shogi and whites defend themselves. In order not to be confused with the terms, let's agree that the party that starts the game is called sente, and the defending party is gote.
')
Before proceeding to the actual programming, it is necessary to note one more important thing. In Shogi, there is no shah, i.e. your king is threatened, you do not have to defend or run away. You may well start your attack. True, the next move is likely to be eaten up by your king, and the game will end.
Entry was quite long, but believe me, it was impossible to do without it. Once upon a time I wrote a post on the game trees. The main advantage of game trees is that they can be applied to any game: to noughts and checkers, and to chess, and even to shogi. Let's try to remember the main ideas.
Let us play shogi and at some point an interesting position arose on the board in which we need to find the best move for sente. Since the computer is essentially a stupid player, we can order him to go through all the possible moves and evaluate them. Then the best move will be the move with the highest score. But we still do not know how to evaluate the moves.
Here you can make a small digression and notice that if in some position, sente has an advantage in conventional units, then gota in the same position lose conventional units. It turns out that the function of assessing the position both from the side of Saint and from the side of Goth will give the same modulo result, and the difference will be only in the sign.
Then, the score of each move for the senta can be obtained by inverting the estimate of the best response for the gota. And the evaluation of the best move for Gote is obtained by evaluating the best response stroke for Sep, etc. Those. it turns out that the move evaluation function is essentially recursive. These recursive estimates of the position should ideally continue until the game ends with obscenities in each branch of the tree. The figure below shows a small part of the game tree that occurs when playing shogi:
Obviously, this tree grows extremely fast. Even for noughts and crosses, a full tree will contain more than a quarter of a million knots, what can we say about chess and shogi. In real algorithms, the depth of recursion is artificially limited, and if the maximum depth of recursion is reached, then the function of static position estimation is called, which, for example, simply calculates the material advantage. Thus, the search function for the best move can be written as follows:
It is clear that this algorithm does not give a complete assessment of the position, but only an assessment of the position that will arise through the Depth of the moves. Therefore, if it is necessary to strengthen the game program, first of all it is necessary to increase the depth of recursion, and this in turn leads to an increase in the tree, and hence an increase in the time of the account.
In fact, there is an algorithm that allows you to go far from the whole tree, but only a small part of it, and at the same time give estimates of the same accuracy as with full enumeration. This algorithm is called alpha-beta clipping.
The algorithm is based on the idea that some branches of the tree may be considered ineffective even before they are fully considered. For example, if the evaluating function in some node is guaranteed worse than in the previously considered branches, then consideration of this node can be terminated early.
Such a situation arises in the following cases: let us consider the position for September, and, having considered, some branch received an assessment of the position. Then, in the depth of the tree, when considering another possible move, we noticed that the estimate for whites became greater or equal to the previously obtained maximum. Obviously, there is no point in further considering this node, and all the branches that go out of it will not bring any improvement in position.
You may have already noticed that this algorithm only allows branches to be cut off if a better move was previously considered. If we assume that when viewing all the moves were checked in sequence from worst to best, then the alpha-beta algorithm will not give any gain compared to brute force. If at the beginning the best moves were considered, then the alpha-beta algorithm instead of the full tree of N nodes will consider only the root of N nodes, with the same accuracy of estimation.
The main problem is that it is impossible to determine in advance which moves are really good and which turns out to be bad. In this case, you have to resort to heuristics. If, when evaluating a position, only a material advantage is taken into account, then it makes sense to first consider moves-captures. Moreover, it makes sense to first of all consider those moves where a heavy piece is taken by a heavy one. In addition, inverted figures play a huge role in shogi, so for preliminary turns it is also possible to increase the preliminary heuristic estimate.
By the way, about coups. It is important to understand that if a coup is possible, it does not always have to be done. For example, at the end of the game, silver, which is able to retreat sideways, sometimes turns out to be more effective than gold, which is much less maneuverable during retreat. But for pawns, rooks and elephants, the coup is always executed, because The coup leaves all the original moves and adds new ones.
As a result, after all the moves have been generated and their heuristic evaluation has been carried out, it is necessary to sort them by this evaluation, and input the alpha-beta algorithm, which looks like this:
As a result, I wrote a small program ( download ), which in my opinion, plays very well in shogi. Of course, it is far from perfect, and there are many things in it that require correction and improvement. It would be nice to add moves - threats to the king in the heuristic assessment, it would be great to refine the program and teach it to play full-fledged shogi, but these are all plans for the future, but for now you can try your hand at this interesting game.
Immediately I did not dare to write AI for real shogi on the 9 by 9 field and decided to start with a simplified version of the game on the 5 by 5 field (this field is often used by beginners). If you read the full rules of the game on Wikipedia, then the following section will be much easier to understand.
Rules of the game
Let's agree that from now on, I will write “shogi”, but imply a simplified version of the game on the field 5 by 5.
Figures
The first thing you need to figure out when learning a new game is the moves. There are 10 different shapes in shogi. The designations of figures, their names and possible moves are presented in the table below:
Coups
Surely, you have noticed that among the figures there are “turned doubles”, which are often stronger than the original. The principle of gaining in shogi is similar to chess, but if in chess, only a pawn turns, and it turns into an arbitrary piece, then all pieces except for gold and the king turn over in shogi. To achieve a coup, you must start or end the course on the opponent’s last line. In general, the coup is arbitrary: i.e. You can walk the rook to the last rank, but not turn it over, and return to your camp with a coup next turn (because you started the turn on the last diagonal). Naturally, the pawn is obliged to roll over if it has reached the coup zone.
Discharges
If you have read this far, you may think that shogi are some kind of chess or checkers, but I assure you that it is not. In Shogi there is one nuance that immediately makes this game several orders of magnitude more difficult.
Any figure eaten by an opponent can be put on any free field as your own. Such an action is called a reset (although I personally like the word “space marines”, which was first used in this context by Andrei Vasnetsov).
True, there are a few limitations when resetting, but they are quite simple:
- All figures are reset unturned;
- If you drop a piece into the coup zone, then it can roll over only after it makes a turn;
- You cannot drop a pawn to the vertical where your pawn already exists (the tokin is not considered a pawn);
- You cannot reset the pawn to the last rank;
- You can’t fold a pawn with a checkmate.
The reset rule may seem insignificant to you, but it radically changes the whole strategy of the game. If in chess or checkers it is enough to get a small material advantage, and then constantly go for exchanges and win in the endgame, then in sego exchanges lead to a more tense position and complication of miscalculation.
The sequence of moves and the initial arrangement
The game takes place on a square field with a side of 5 cells. At the beginning of the game on the field is as follows:
For reasons unknown to me, black is the first to begin in shogi and whites defend themselves. In order not to be confused with the terms, let's agree that the party that starts the game is called sente, and the defending party is gote.
')
Before proceeding to the actual programming, it is necessary to note one more important thing. In Shogi, there is no shah, i.e. your king is threatened, you do not have to defend or run away. You may well start your attack. True, the next move is likely to be eaten up by your king, and the game will end.
Game programming
Entry was quite long, but believe me, it was impossible to do without it. Once upon a time I wrote a post on the game trees. The main advantage of game trees is that they can be applied to any game: to noughts and checkers, and to chess, and even to shogi. Let's try to remember the main ideas.
Bust game trees
Full search of game trees
Let us play shogi and at some point an interesting position arose on the board in which we need to find the best move for sente. Since the computer is essentially a stupid player, we can order him to go through all the possible moves and evaluate them. Then the best move will be the move with the highest score. But we still do not know how to evaluate the moves.
Here you can make a small digression and notice that if in some position, sente has an advantage in conventional units, then gota in the same position lose conventional units. It turns out that the function of assessing the position both from the side of Saint and from the side of Goth will give the same modulo result, and the difference will be only in the sign.
Then, the score of each move for the senta can be obtained by inverting the estimate of the best response for the gota. And the evaluation of the best move for Gote is obtained by evaluating the best response stroke for Sep, etc. Those. it turns out that the move evaluation function is essentially recursive. These recursive estimates of the position should ideally continue until the game ends with obscenities in each branch of the tree. The figure below shows a small part of the game tree that occurs when playing shogi:
Enumeration of game trees with limited recursion depth
Obviously, this tree grows extremely fast. Even for noughts and crosses, a full tree will contain more than a quarter of a million knots, what can we say about chess and shogi. In real algorithms, the depth of recursion is artificially limited, and if the maximum depth of recursion is reached, then the function of static position estimation is called, which, for example, simply calculates the material advantage. Thus, the search function for the best move can be written as follows:
function SearchBestMove ( Depth : byte ; color : TColor ) : real ;
var
r , tmpr : real ;
i , N : word ;
Moves : TAMoves ;
begin
if Depth = 0 then
r : = EstimatePos
else
begin
real : = - 100,000 ;
N : = GenerateAllMoves ( Moves ) ;
for i : = 1 to N do
begin
Make a move Moves [ i ] ;
tmpr : = - SearchBestMove ( Depth - 1 , opcolor ( color ) ) ;
Cancel Moves [ i ] ;
if tmpr> r then
r : = tmpr ;
end ;
end ;
SearchBestMove : = r ;
end ;
It is clear that this algorithm does not give a complete assessment of the position, but only an assessment of the position that will arise through the Depth of the moves. Therefore, if it is necessary to strengthen the game program, first of all it is necessary to increase the depth of recursion, and this in turn leads to an increase in the tree, and hence an increase in the time of the account.
Alpha beta clipping
In fact, there is an algorithm that allows you to go far from the whole tree, but only a small part of it, and at the same time give estimates of the same accuracy as with full enumeration. This algorithm is called alpha-beta clipping.
The algorithm is based on the idea that some branches of the tree may be considered ineffective even before they are fully considered. For example, if the evaluating function in some node is guaranteed worse than in the previously considered branches, then consideration of this node can be terminated early.
Such a situation arises in the following cases: let us consider the position for September, and, having considered, some branch received an assessment of the position. Then, in the depth of the tree, when considering another possible move, we noticed that the estimate for whites became greater or equal to the previously obtained maximum. Obviously, there is no point in further considering this node, and all the branches that go out of it will not bring any improvement in position.
You may have already noticed that this algorithm only allows branches to be cut off if a better move was previously considered. If we assume that when viewing all the moves were checked in sequence from worst to best, then the alpha-beta algorithm will not give any gain compared to brute force. If at the beginning the best moves were considered, then the alpha-beta algorithm instead of the full tree of N nodes will consider only the root of N nodes, with the same accuracy of estimation.
Sort moves
The main problem is that it is impossible to determine in advance which moves are really good and which turns out to be bad. In this case, you have to resort to heuristics. If, when evaluating a position, only a material advantage is taken into account, then it makes sense to first consider moves-captures. Moreover, it makes sense to first of all consider those moves where a heavy piece is taken by a heavy one. In addition, inverted figures play a huge role in shogi, so for preliminary turns it is also possible to increase the preliminary heuristic estimate.
By the way, about coups. It is important to understand that if a coup is possible, it does not always have to be done. For example, at the end of the game, silver, which is able to retreat sideways, sometimes turns out to be more effective than gold, which is much less maneuverable during retreat. But for pawns, rooks and elephants, the coup is always executed, because The coup leaves all the original moves and adds new ones.
As a result, after all the moves have been generated and their heuristic evaluation has been carried out, it is necessary to sort them by this evaluation, and input the alpha-beta algorithm, which looks like this:
function AB ( POS : TRPosition ; color : TColor ; Depth : byte ; A , B : real ) : real ;
var
Moves : TAMoves ;
i , MovesCount : byte ;
OLDPos : TRPosition ;
begin
MovesCount : = 0 ;
if ( Depth = 0 ) or Mate ( POS . HandSente , POS . HandGote , color ) then
A : = EstimatePos
else
begin
if color = sente then
MovesCount : = GenerateMoves ( POS . Board , color , POS . HandSente , Moves )
else
MovesCount : = GenerateMoves ( POS . Board , color , POS . HandGote , Moves ) ;
for i : = 1 to MovesCount do
begin
if A> = B then
Break ;
OLDPOS : = POS ;
MakeMove ( POS , Color , Moves [ i ] ) ;
Moves [ i ] . r : = - AB ( POS , opcolor ( color ) , Depth - 1 , - B , - A ) ;
POS : = OLDPos ;
if Moves [ i ] . r > A then
A : = Moves [ i ] . r ;
end ;
end ;
AB : = A ;
end ;
Final implementation
As a result, I wrote a small program ( download ), which in my opinion, plays very well in shogi. Of course, it is far from perfect, and there are many things in it that require correction and improvement. It would be nice to add moves - threats to the king in the heuristic assessment, it would be great to refine the program and teach it to play full-fledged shogi, but these are all plans for the future, but for now you can try your hand at this interesting game.
Source: https://habr.com/ru/post/156233/
All Articles