Chinese Chess Endgame Databases Query System
Important links:
Available endgames (Interactive): rook type, knight type, cannon type, pawn type, misc
Available endgames (Java): rook type, knight type, cannon type, pawn type, misc
Asian rules for Chinese chess (Chinese version,GB)
Introduction
Based on the three papers listed at the end of this page, I have put together a Chinese chess endgame databases query system. It takes q long time to construct larger endgame database, so I will put them in the server as they are constructed. There are many interesting databases available already, such as knight vs single bishop, rook-cannon vs rook, cannon-pawn-bishop-elephant vs full defense, and knight-pawn-bishop-elephant vs full defense. The cannon-pawn-bishop-elephant vs full defense endgame has total 10 pieces on the board (king, 1 cannon, 1 pawn, 1 bishop, 1 elephant vs king, 2 bishops, 2 elephants), and it takes 189 moves before the strong side captures the first piece when both sides play perfectly -- a feat very hard for humans to duplicate. As matter of a fact, the best Chinese chess player would only give a lesson on how to beat the full defense with one cannon, one pawn, one bishop, and TWO elephants.
Reasons
The major reasons to put the databases on line are two fold. First, I don't know if my implementation is 100% correct, and I would like anyone who is interested to look into them to see if there are still stained positions (the ones with incorrect information accoording to rules). Rules for Chinese chess are pretty complicated. Although I try to construct the databases to fully conform to Asian rules of Chinese chess, I am afraid that some special situations are overlooked. If you find any stained position, please let me know. I will appreciate it a lot. The second reason is to let more people enjoy the benefits of the endgame databases. It has been said that one learns chess best with endgame study. During the course of making these endgame databases, I am fascinated by the various ways to win a certain endgame as discovered by the databases. A lot of plays are still beyond my comprehension. By putting the databases on line, I am hoping people can enjoy the benefits and in the mean time discuss the intriguing plays that are hard for humans to grasp.
Instructions
To use the database, I assume the users know the Chinese characters of the pieces and traditional notation for the moves. (If it is a problem according to feedback, I will consider providing English notation.) To use the database, you can look at this page as an example. At the left is a java chessboard representing the board position. At the top of the middle column is the indication of which side will make the next move, followed by order and value of the current position, followed by all the legal moves. There are selections for various actions at the right column.
The order and value are the key information for using the database. Order will be explained later. For the endgames which only one side has attacking pieces, the orders are always zero. Value represents the steps to the nearest capture as well as win or loss for the side to move. When the value is odd number (except 255), it means the current position is a win for the side to move. When it is even number, it means the side to move will eventually lose if both sides play perfectly. Value 255 indicates it is a draw position. The current version of databases adapt distance-to-capture method, so the number indicates the distance to the nearest capture. At the right of each legal move, there is an order and value pair of information (oo-vvv). It indicates the order and value of the position after the move is made.
The objective of the winning side is to choose a move which is a loss position for the opposite side with the fewest steps toward the capture. A winning position means there is at least one move that will lead to the opposite side's loss. The smaller value number guarantees it will eventually lead to a capture. At the right side of each best move, there is a "*" sign. A "c" at the right side indicates it is a capture move. For our example, (n5+7) is the recommended move. A losing position means of all the available moves, all of them will lead to winning position for the opposite side. The objective is to choose a move that will delay the winning side's capture of a piece as long as possible. The best move will be the biggest of all the odd values. Again, they are followed by "*" sign.
There are several actions to choose at the right side. The most usable one should be the "Suggested move" link. It will choose one of the best moves (the ones with "*") from the legal moves and make the move for you. To just enjoy how the endgame databases solve a position, you can keep hitting this link to see the suggested line. You can also choose the move you want to make from available legal moves to see the line you are interested. "Previous page" and "Next page" are to simulate the "Back" and Forward" buttons for your browser. It is there to save the mouse traveling distance. "Home page" will lead to this page for explanations.
Playing mode
At the top of the action links is the interesting "Playing mode" link, which will link you to the corresponding playing mode page. In playing mode, the order and value information is hidden. To play with endgame databases, you make the move for one side, and hit "Suggested move" when it is the opposite side's turn to move. Alternating between these two actions will feel like you are playing with an almost invincible enemy. It is a great way to practice your endgame skills. I highly recommend it. Hope you will enjoy it. In the playing mode, this link becomes "Look up answers". When you are frustrated enough that you can not find the solution, you can always look the answer up and examine what you have missed.
Available endgames
In the available endgame page, you will find a list of all the endgame databases currently available and some summary information, such as biggest distance-to-capture number, the winning percentage for the red side. Click on the database name will lead you to more detail information about that database. The explanation will be given at later section. The name for the database is given according to the pieces on the board.
K, k -- (k)ing
B, b -- (b)ishop, assistant, guard
E, e -- (e)lephant, minister
R, r -- (r)ook, chariot, car
N, n -- k(n)ight, horse
C, c -- (c)annon, gun
P, p -- (p)awn
Red is listed first, followed by black. The piece order should be k > r > c > n > b > e. knkb means red has king and knight; black has king and bishop.
Statistics
Click database name in the available endgame page will bring you to the corresponding statistic page. Here, you can learn what kind of endgame outcome this endgame belong to. Usually, there are three typical outcomes for any given endgame -- red win, black draw, and non-determined. By remembering the usually outcome of certain endgame combination, player can simplify the board combination and lead to the situations more advantageous to himself. If red win percentage is greater than 98%, it means red will win this endgame except very rare situations. If the black draw percentage is greater than 98%, it means this combination will lead to draw.
One of the more interesting items in the statistic page is the longest win position. For each order, I place one of the longest lines and put it in the table. Click on it can lead you to the corresponding javaboard. You can use "Suggested move" to just go through it to enjoy the intricate play, or you can use "Play mode" to test your endgame solving skill.
Indefinite checking/chasing
The "Order" needs to be explained further. In Chinese chess, it is different from western chess in dealing the repeat positions. In western chess, the repeat positions should be declared as draw according to the rules. However, in Chinese chess, repeat positions could be win, loss, or draw depending on the specific situation. The current databases try to conform asian rules of Chinese chess. In short, when one side is checking/chasing opponent indefinitely, the side is required to change the pattern, otherwise he will be declared as loss according to asian rules. On the other hand, the side that forces the opponent to checking/chasing indefinitely can win by this rule. If the repeat situations do not form indefinitely checking/chasing, they will be declared as draw if neither side is willing to break the pattern. Because of this difference between western chess and Chinese chess, the typical retrograde analysis method can not be applied to Chinese chess without modifications. It is not until the publication of Fang et al., 2002 (as far as I know), the endgame database construction is limited only to the endgames when only one side has attacking pieces. Hence, I think it is a very interesting paper. However, the paper only solved the indefinitely checking situations while left out indefinitely chasing situations. While I was making the endgame databases following their method, I found, with the great help from meifire, that substantial amount of positions will be stained by indefinitely chasing situations if not taken care of. Fortunately, I was able to extend the method of Fang et al., and made it also working with indefinitely chasing situations. With this, the databases should conform all the asian rules of Chinese chess. I hope you will help me find out if it is the case.
In order for one side to win, other than wining by checking opponent's king, one can also lead the opponent to an indefinitely checking/chasing situations where the opponent has to choose either the moves that lead to eventual demise or keeps the pattern and declared as loss. This indefinitely checking/chasing situation can happen many times before the strong side checkmate the opponent when both sides have attacking pieces. Instead of driving the game to checkmate, now one can also drive the game to indefinitely checking/chasing. To each indefinitely checking/chasing condition and the positions leading to it, an order is assigned. The value becomes the shortest distance to indefinitely checking/chasing. Again, odd numbers mean win, even number loss. The side in the positions that have value 0 can either check/chase again to the value 1 of the same order, or he can go to the loss positions with lower orders. By making sure the order will get smaller (checking/chasing moves are limited), the strong side can eventually reach checkmate position.
Input any position
If you look at the address bar in your browser for any given endgame position in these pages, you will see a string of strange characters right after "endgame.cgi?" or "play.cgi?". It is the notation to indicate a specific position. If you learn this notation, you can input any position that you are interested and query the database. If it is among the available ones, you will get corresponding board shown with win/loss/draw information. I highly recommend you to learn this notation. If there will be a standard way to represent a Chinese chess board position in the future, it should not be too far away from this form. Starting from the top row, scan through the row from left to right. If it is a space, add one to the space counter. If it is not a space, write out the value of the space counter (omit it if it is 0), then the piece encountered according to the table given above. If it is a black piece, it should be the capital version. If red, use small letter. Reset the space counter and continue the procedure until you reach the right side of the row. At that point, write out the space counter number and reset it to zero. Again, omit it if the space counter is zero. Continue this procedure for the next row until the last row. The example knkb endgame board has the notation as "4K44B49994n495k399". Compare it to the real board position to see if you understand it. It is red to move if the string is without a "0" at the end. Put a "0" to indicate it is black to move. Finally, if you put a ":" at the very end, it will invert the board so you will be seeing from black side. Click on these link to see the difference: 4K44B49994n495k3990 , 4K44B49994n495k3990:
Thanks
To do
Welcome you to suggest endgames to construct.
Have fun!
Jih-tung Pai
jpai@rocketmail.com
References
Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. "Indefinite Sequence of Moves in Chinese Chess Endgames", Proc. 3rd International Conference on Computers and Games (CG), to appear in a Springer-Verlag LNCS volume, 2002. [pdf]
Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. "Construction of Chinese Chess Endgame databases by Retrograde Analysis" Proc. 2nd International Conference on Computers and Games (CG), Springer-Verlag LNCS# 2063, pages 96--114, 2000. [pdf]
Ren Wu and Donald F. Beal. "A Memory Efficient Retrograde Algorithm and Its Application To Chinese Chess Endgames" More Games of No Chance MSRI Publications Volume 42 , 2002. [pdf]
