Mizar chess engine

Shogi is a Japanese traditional Chess-like game that is played with a 9 by 9 board and 40 pieces that are classified in eight kinds: king, rook, bishop, gold general, silver general, knight, lance, pawn. The goal of Shogi is checkmating the opponent King. Each player plays a move alternately. The first player is Black and the second player is White. The pieces in the lower side of the board are Black’s pieces and other pieces in the upper side of the board are White’s pieces even if except for the kings, opposing pieces are differentiated only by orientation, not by marking or color. We use coordinates files as numbers (1 to 9 from right side of the board to left) and ranks as alphabets (a to i from top of the board to bottom). The squares in rank g to i are Black’s area and the squares in rank a to c is White’s area.

Rules

Board setup

Each player places his pieces in the positions shown below, facing the opponent.

In the rank nearest the player:

• The king is placed in the center file.
• The two gold generals are placed in the adjacent files to the king.
• The two silver generals are placed adjacent to each gold general.
• The two knights are placed adjacent to each silver general.
• The two lances are placed in the corners, adjacent to each knight.

That is, the first rank is |L|N|S|G|K|G|S|N|L|.

In the second rank, each player places:

• The bishop in the same file as the left knight.
• The rook in the same file as the right knight.

In the third rank, the nine pawns are placed one to each file.

Traditionally, even the order of placing the pieces on the board is determined. There are two recognized orders, ohashi and ito. The Japanese-language page Shogi Pineapple indicates the two orders; ohashi is depicted on the left and ito on the right.

Gameplay

The players alternate taking turns, with Black (the side containing the Jeweled General) playing first. The terms “Black” and “White” are used to differentiate the two sides, but there is no actual difference in the color of the pieces. For each turn a player may either move a piece which is already on the board and potentially promote it, capture an opposing piece, or both; or to “drop” a piece that has already been captured onto an empty square of the board. Professional games are timed as in International Chess, but professionals are never expected to keep time in their games. Instead a timekeeper is assigned, typically an apprentice professional. Time limits are much longer than in International Chess (9 hours a side plus extra time in the prestigious Meijin title match), and in addition byoyomi (literally “second counting”) is employed. This means that when the ordinary time has run out, the player will from that point on have a certain amount of time to complete every move (a byoyomi period), typically upwards of one minute. The final ten seconds are counted down, and if the time expires the player to move loses the game immediately. Amateurs often play with electronic clocks that beep out the final ten seconds of a byoyomi period, with a prolonged beep for the last five.

Movement and capture

If an opposing piece occupies a legal destination for a friendly piece (that is, a piece belonging to the player whose turn it is to move), it may be captured by removing it from the board and replacing it with the friendly piece. It is not possible to move to or through a square occupied by another friendly piece, or to move through a square occupied by an opposing piece. It is common to keep captured pieces on a wooden stand (or komadai) which is traditionally placed so that its bottom left corner aligns with the bottom right corner of the board from the perspective of each player. It is not permissible to hide pieces from full view. This is because captured pieces, which are said to be in hand, have a crucial impact on the course of the game. The knight jumps, that is, it passes over any intervening piece, whether friend or foe, without an effect on either. It is the only piece to do this. The lance, bishop, and rook are ranging pieces: They can potentially move any number of squares along a straight line limited by the edge of the board. If an opposing piece intervenes, it may be captured by removing it from the board and replacing it with the moving piece. If a friendly piece intervenes, one is limited to a distance that stops short of that square; if the friendly piece is adjacent, one may not move in that direction at all. All pieces but the knight move either orthogonally (that is, forward, backward, or to the side, in the direction of one of the arms of a plus sign, +), or diagonally (in the direction of one of the arms of a multiplication sign, ×).

King can move to the neighboring squares. The movement is the same as King of Chess.

Rook can move along the rank and file for any number of squares, but cannot jump over any pieces. This movement is the same as Rook of Chess.
Bishop can move along diagonal squares for any number of squares, but cannot jump over any pieces. The movement is the same as Bishop of Chess.
Gold can move one square forward, backward, sideways or diagonally forward.
Silver can move one square forward, diagonally forward or diagonally backward.
Knight can move one square straightforward and then one square diagonally forward, to the right or left. It is the only piece that can jump over other pieces. The movement is not the same with Knight of Chess. The Knight of Chess can move eight directions, but the Knight of Shogi can move only two forward directions.
Lance can move straightforward for any number of squares, but cannot jump over any pieces and never go back.
Pawn can move one square forward. The movement and capturing are different from the Pawn of Chess.

Promotion

In Chess, pawns can be promoted. In Shogi, all pieces except the king and the gold general can be promoted. Promotion can happen at the end of any move in which the piece enters, exits, or moves within the three-row promotion zone. Pawn and lance must be promoted when reaching the 9th row. Knight must be promoted when reaching the 8th or 9th row.

The promoted pawn, promoted lance, promoted knight, and promoted silver general all have the moves of the gold general.

The promoted rook becomes Dragon King (not to be confused with the king). It has the moves of the rook and the king.

The promoted bishop becomes Dragon Horse (not to be confused with the knight). It has the moves of the bishop and the king.

Drops

Captured pieces are truly captured in shogi. They are retained “in hand”, and can be brought back into play under the capturing player’s control. On any turn, instead of moving a piece on the board, a player may take a piece that had been previously captured and place it, unpromoted side up, on any empty square, facing the opposing side. The piece is now part of the forces controlled by that player. This is termed dropping the piece, or just a drop.A drop cannot capture a piece, nor does dropping within the promotion zone result in immediate promotion. However, either capture or promotion may occur normally on subsequent moves by the piece.A pawn, knight, or lance may not be dropped on the far rank, since it would have no legal move on subsequent turns. Similarly, a knight may not be dropped on the penultimate rank.

There are two other restrictions when dropping pawns:

• A pawn cannot be dropped onto the same file (column) as another unpromoted pawn controlled by the same player. (A tokin does not count as a pawn.) A player who has an unpromoted pawn on every file is therefore unable to drop a pawn anywhere. For this reason it is common to sacrifice a pawn in order to gain flexibility for drops.
• A pawn cannot be dropped to give an immediate checkmate. However, other pieces may be dropped to give immediate checkmate, a pawn that is already on the board may be advanced to give checkmate, and a pawn may be dropped so that either it or another piece can give checkmate on a subsequent turn.

It is common for players to swap bishops, which face each other across the board. This leaves each player with a bishop “in hand” to be dropped later, and gives an advantage to the player with the stronger defensive position.

Check and mate

When a player makes a move such that the opposing king could be captured on the following turn, the move is said to give check to the king; the king is said to be in check. If a player’s king is in check and no legal move by that player will get the king out of check, the checking move is also checkmate (tsumi) and effectively wins the game. To give the warning “check!” in Japanese, one says “ote!”. However, this is an influence of international chess and is not required, even as a courtesy. A player is not allowed to give perpetual check.

Winning the game

When a player cannot do any legal moves, that player must resign and the player loses. For example, the one’s king is in checkmate. In professional and serious amateur games, a player who makes an illegal move loses immediately. There are two other possible, if uncommon, ways for a game to end: repetition (sennichite) and impasse (jishogi). If the same game position occurs four (formerly three) times with the same player to play, the game is declared no contest. For two positions to be considered the same, the pieces in hand must be the same as well as the positions on the board. However, if this occurs with one player giving perpetual check, then that player loses. The game reaches an impasse if both kings have advanced into their respective promotion zones and neither player can hope to mate the other or to gain any further material. If this happens, the winner is decided as follows: Each rook or bishop scores 5 points for the owning player, and all other pieces except kings score 1 point each. (Promotions are ignored for the purposes of scoring.) A player scoring less than 24 points loses. Jishogi is considered an outcome in its own right rather than no contest, but there is no practical difference. In professional tournaments the rules typically require drawn games to be replayed with colours (sides) reversed, possibly with reduced time limits. This is rare compared to chess and xiangqi, occurring at a rate of 1-2% even in amateur games. The 1982 Meijin title match between Nakahara Makoto and Kato Hifumi was unusual in this regard, with jishogi in the first game (only the fifth draw in the then 40-year history of the tournament), a game which lasted for an unusual 223 moves (not counting in pairs of moves), with an astounding 114 minutes spent pondering a single move, and sennichite in the sixth and eighth games. Thus this best-of-seven match lasted ten games and took over three months to finish; Black did not lose a single game and the eventual victor was Kato at 4-3.

Strategy

Drops are the most serious departure from International Chess. They entail a different strategy, with a strong defensive position being much more important. A quick offense will leave a player’s home territory open to drop attacks as soon as pieces are exchanged. Because pawns attack head on, and cannot defend each other, they tend to be lost early in the game, providing ammunition for such attacks. Dropping a pawn behind enemy lines, promoting it to a “tokin” (gold general), and dropping a second pawn immediately behind the “tokin” so that they protect each other makes a strong attack; it threatens the opponent’s entire defense, but provides little value if the attack fails and the pieces are captured. Players raised on International Chess often make poor use of drops, but dropping is half the game. If a player has more than a couple of captured pieces in hand, it is likely that dropping attacks are being overlooked. However, it is wise to keep a pawn in hand, and often to exchange pieces if necessary to get one. Compared to International Chess, Shogi players are more likely to sacrifice pieces (even valuable ones), if the resulting capture can be dropped back into play for a specific purpose. There are two openings typically used in Shogi. Players can both move the rook pawn forward, or more commonly, advance the pawn above and to the right of the bishop. The former is known as a rook opening while the latter is a bishop opening. When doing a bishop opening, it’s common to exchange pieces by having one bishop attack the other. This allows each player to return their newly capture bishop into play anywhere on the board. However, it is not always advantageous to exchange bishops, depending on what they intend to do next. Attacking pieces can easily become trapped behind enemy lines, as the opponent can often drop a pawn on a protected square to cut off the line of retreat. For this reason, rooks, which can retreat in only one direction, are commonly kept at a safe distance in the early parts of the game, and used to support attacks by weaker pieces. However, once the game has opened up, a promoted rook is an especially deadly piece behind enemy lines. Kings can also be easily trapped by their own pieces, so a good last-ditch defensive effort is to open a back door through the pawn line to allow kings to escape. Kings are more difficult to checkmate in the open, especially if the opponent does not have many ranged pieces in play. Many common opening attacks involve advancing a silver, and ideally a pawn, along a file protected by the rook. This is the climbing silver attack. Because silvers have more possibilities for retreat, while golds better defend their sides, silvers are generally considered superior as attacking pieces, and golds superior as defensive pieces. It is common practice to defend the king with three generals, two golds and a silver. There are various furibisha or “ranging rook” openings where the rook moves to the center or left of the board to support an attack there, typically with the idea of allowing the opponent to attack while arranging a better defence and aiming for a counterattack. However, as the most powerful piece on the board, the rook invites attack, and in most cases, especially for weaker players, it is a good idea to keep the king well away from the rook. Leaving a king on its original square (igyoku or a “sitting king”) is a particularly dangerous position. Advancing a lance pawn can open up the side of the board for attack. Therefore, when a player first advances a lance pawn, it is usual for the opponent to answer by advancing the opposing pawn, in order to avoid complications later in the game. It also allows the king to escape if attacked from the side. Because defense is so important, and because shogi pieces are relatively slow movers, the opening game tends to be much longer in shogi than in International Chess, commonly with a dozen or more moves to shore up defenses before the initial attack is made. There are several strong defensive fortifications known as castles.

The Yagura castle

The Yagura castle is considered by many to be the strongest defensive position in shogi. It has a strongly protected king; a well fortified line of pawns; and the bishop, rook, and a pawn all support a later attack by the rook’s silver or knight. It is notoriously difficult to break down with a frontal assault, though it is weaker from the side. It is typically used against ibisha or “static rook” openings, which involve advancing the rook’s pawn. However, one’s opponent may just as easily adopt this defense, giving neither side an advantage. Instead of the rook’s pawn being advanced two squares as shown in the diagram, the adjacent silver’s pawn is often advanced one square, allowing both the rook’s silver and knight to move forward. These offensive moves are not properly part of the castle, but the two-square pawn advance must be carried out early if there is to be room for it, and so it is often done while still castling. There is a good deal of flexibility in the order of moves when building the Yagura defense, and the possibilities will not be listed here. The only point to keep in mind is that the generals should move diagonally, not directly forward. However, there is a strong intermediate position called the kani (“crab”). It has the three pawns on the left side advanced to their final Yagura positions, and on the second rank all four generals are lined up next to the bishop, which is still in its starting position: |B|G|S|G|S| bishop-gold-silver-gold-silver. The king is moved one square to the left, behind the middle silver. A common attack against the Yagura defense is to advance the rook’s knight directly forward, with a pawn in hand, to attack the fortifications on either side of the castled king. If the defender has answered a lance’s pawn advance on that side, a pawn may be dropped where the edge pawn had been. If the defending silver has moved or is not yet in position, a pawn may be dropped there.

The Mino-Gakoi castle

A defensive position that is considered easier for beginners, but still popular with professionals, is the Mino-Gakoi castle. The King is placed in a safe position, while the three generals work well to back each other up. This is sometimes used when a player chooses a bishop opening rather than the rook-pawn opening.

The Mino-Gakoi takes six moves to complete, not necessarily in this order:

1. Move the rook to the left side of the board, preferably the fourth rank. This move must be first.
2. Move the king to where the rook started, 3 moves.
3. Move the silver general next to the king up one space.
4. Move the left-side gold general diagonally up and right so that it is protected by the other gold general, which hasn’t moved yet.

Computer Shogi

A typical shogi programs consists of an alpha-beta searcher with a static evaluation function, some forward pruning method, iterative deeping and a tsume shogi solver to look ahead for mating; tsume shogi ia a shogi problem position where the king has to be mated by giving check with each move. The idea is to mate before the opponent has a chance to counterattack, since check is a forcing move. The rule differences between chess and shogi lead to differences in various aspects of game programming:

1. Chess is a converging game, while Shogi id diverging (in the endgame the number of possible moves increases). This is mainly caused by the possibility of drops. However, since chess is slowly converging, the use of endgame databases is non so important as it is for example for mankala games and go-moku. In shogi, no endgame database is of any use, even though a special Tsume Shogi solver is part of almost every shogi computer program.
2. There is a considerable difference in game tree complexity due to the dropping possibility, the extra promotion possibilities and the virtual impossibility of draws. Shogi has an average branching factor of about 80. In chess this is estimated at 35.
3. On Average, a gmae of shogi takes about 115 ply. The maximum game length (in actual games) is more than 500 ply. In chess, the average is about 80 ply, while the record game length is currently 382 ply.
4. Many pieces in shogi have limited movement. This lead to a slow build-up and influences the average game length. It also influences the opening database that is so important in chess. There is a large number of books written on opening theory in shogi, but in general only patterns instead of strict move orders are being discussed. Also, new and interesting opening patterns are being developed until this day. Therefore, building a good opening dtabase is more difficult in shogi

Tsume shogi

One of the most successful results in Computer Shogi is mating search for checkmate problems called Tsume Shogi in Japanese. Tsume Shogi is a kind of puzzles for which the goal is mating the defender’s King by successive checks. There are some problems that are solved over 100 plies of moves because both players can drop captured pieces in Shogi. It is hard to solve such problems by searching with typical depth-first algorithms. Therefore, best-first search algorithms are used to solve those problems. After the depthfirst algorithms that behave like as best-first algorithms were invented, the famous problem entitled “Microcosmos” with the longest solution sequence of 1525 plies were solved in 1997. Nowadays, these algorithms are used not only in computer Shogi but also in other domains and obtain good results. In the field of Tsume Shogi, a computer has the ability for solving problems much better than the human champion. The playing strength of top computer Shogi is regarded as amateur 5th dan on the whole. On the other hand, there are lots of problems to improve in computer Shogi. Especially, the playing strength in the opening game is regarded only as 1st kyu. This weakness of opening play often causes some mistakes in the opening game, and it is hard to compensate such mistakes in the endgame. Therefore, the improvement of opening play becomes one of the biggest assignments for computer Shogi.

Realization-probability search

Realization-probability search was proposed by Tsuruoka et al. and used in their computer Shogi Gekisashi. Gekisashi is one of the strongest computer Shogi programs and won the 12th CSA World Computer Shogi Championship. After their first winning, the realization-probability search has been paid much attention and used in some other Shogi programs including Tacos.

Here a short sketch of the algorithm.

• Classifying moves into some categories. For example, moves are categorized into check moves, profitable capturing moves, attacking two pieces at the same times, and so on.
• From many master games, compute the statistics of the following two frequencies in each position. The one is the number of how many times masters play the moves classified in each category. Another one is the number of how many times the moves classified in a category exist as a legal move. In case where there are some such moves classified in the same category, it is counted as only one.
• Calculating transition probability for each category as follows: Tp =Np/Ne ; where
  • Tp: Transition (move-category) probability.
  • Np: The number of times moves of a category are played.
  • Ne: The number of times moves of a category exist as legal moves.
• In every node visited during a search, realization probability of each node is calculated as follows: RP(n+1) = RP(n) * Tp ; where
  • RPn: realization probability of a node in the depth n.The realization probability of the root node of a game tree is 1:0 because that position is already realized.
• Search stops when realization probability of a node becomes lower than a threshold probability.

This algorithm can be applied with less expensive costs to any game program that uses the minmax-based search. A computer simply needs to decide whether or not it continues searching based not on the depth but on the realization probability in a position considered. With this algorithm, search extensions and selective search are systematically carried out with some good results. It is also possible to incorporate domain knowledge into this search framework.

[from Wikipedia.org; "Towards master-level play of Shogi" by Jun Nagashima; "A gamut of games" by Jonathan Schaeffer; "Chess, Shogi, Go, natural developments in game research" by Hitoshi Matsubara, Hiroyuki Iida, Reijer Grimbergen]