Wednesday, August 20, 2008

Move homepages here

I have moved the endgame database home pages here. My plan is to host the home pages here so I can modify it more easily. My server will still manage the real database query and displaying work. Other than the advantage of me modifying the pages more easily, it will be also easier to get reader feedback. Let's see if it works out better. For now, the home pages will appear both in my server and this blog space.

Monday, August 4, 2008

Chinese Chess Endgame Databases Query System

[Chinese version of this page]

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]

象棋殘局庫查詢系統

[English version of this page]

象棋殘局庫查詢系統

重要連結:

已有的殘局庫(互動式): 車類, 馬類, 炮類, 卒兵類, 其它

已有的殘局庫: 車類, 馬類, 炮類, 卒兵類, 其它


亞洲規 則(GB)

介紹

根據頁末的三篇論文,我建造了一個殘局庫查詢系統。殘局庫建造須要不少電腦時間,比較大的殘局庫還在建造中。我會慢慢的加到伺服機裏。目前有一些 有趣的殘局庫已經完成。此如馬擒孤士車炮巧勝單車(海底撈月)炮兵仕相對士象全馬兵仕相對士象全。炮兵仕相對士象全共有十個子還在 棋盤上,最長著法紅方須要189步才能吃到第一子。對人來說,這樣的殘局很難掌握。記得天 下第一高手許銀川開課也只教炮兵單缺仕對士象全。

源由

將殘局庫放在網上最主要有二個原因。第一,我也不知道我做得是否完全正確。希望有興趣的人可以幫忙找看看有沒有錯誤。象棋棋規非常複雜,雖然我已經 盡力依照亞洲棋規去建造這些殘局庫,我仍然不確定是否有一些特例被忽視掉。如果你有發現任何錯誤,麻煩你能告知,我將非常感謝。第二個原因是我希望能有更 多人享受到殘局庫帶來的好處。有人曾說研究殘局最能學到如何下棋。當在建造殘局庫的這段時間,我常為殘局庫所發現的一些殘局解法拍案叫絕。有些解法還超乎我理解的能力。希望藉由這網上的殘局庫,能有更多的人能享用它的好處,並能討論一些對人難以掌握的走法。

用法

要瞭解這個殘局庫的用法,你可以打開 這頁做為一個例子。在左邊的爪哇棋盤有殘局的盤面。中間上方告訴你現在輪那方走子。接著是這個盤面的 Order 和 Value 以及所有可走的合法步。在右邊有一些動作的選項。 Order 容後再詳細解釋。對於只有一方有攻擊子的盤面,Order 都是 0。Value 代表到最近吃子或將軍的步數,以及將走子方的勝負情形。奇數(255 除外),代表將走子方為勝。偶數,代表將走子方為負。若是 255,代表這是個和局的盤面。但這些是在雙方都走最佳著法的情況。在所有合法步的後面也都有一對 Order 和 Value。這代表走了該步後新的盤面的值。

攻擊方的目標是走出一步使對方最接近失子或被將軍的負盤面(偶數 Value)。勝的盤面一定最少有一個這樣的步。因為 Value 值會越來越小,終將導致吃子或將軍。在最佳著法的右邊 ,你會看到(*)符號。有(c)符號則是代表該步是吃子步。在負的盤面,可以走的每一個步都會導致對方勝的盤面。因而在負的盤面只能盡量走出大的 Value,拖延對方吃子的時機,增加對手走錯的機會。一樣的,最佳著法右方有(*)符號。

練習攻防模式

在右方有一些動作選項可以選。最有用的大概是“電腦代走”。擊點這個連結,電腦會從最佳步中選一個步替你走至下一個盤面。如果你只想看殘局庫怎麼解 當前的盤面,一直擊點這個連結可以觀看走法。你也可以直接擊點你想要走的步來看你想看的變化。“上一頁”和“下一頁”是用來模擬後退和前進鏈。這樣當你想 反復觀看前後盤面時,滑鼠不用跑大老遠。主頁帶你到這一個說明頁。在右方最上方是很有趣的“練習攻防”連結。它會帶你進入攻防形式的同樣盤面。在這頁你看 不到 Order 和 Value。當你要和殘局庫對殺時,你選一邊移子。當輪到對手走步時,你得擊點”電腦代走”。如此反復運行,便如同和一個強大的對手下棋,達到練習的目 的。這是一個很好練習殘局的工具。在右上方的這個連結,這時變為“查閱解答”。當你實在不知道如何 解局的時候,你可以由此得到答案,看看到底是那一步走錯了。

已有的殘局庫

在已有的殘局庫頁裏,你可以看到所有已建好 的殘局庫,以及一些總結的資料。比如紅勝率、黑和率、以及最長著手。擊點殘局庫名會帶你到更詳細的統計資料。如何解讀這些資料容後再訴。殘局庫名是根據盤 上的子而給。紅先黑後、根據以下的代符表:

將、帥 -- k,(k)ing
士、仕 -- b,(b)ishop
象、相 -- e,(e)lephant
車、車 -- r,(r)ook
馬、馬 -- n,k(n)ight
包、炮 -- c,(c)annon
卒、兵 -- p,(p)awn

先列紅帥,次列紅攻擊子(依序為車、包、馬、兵),接著是紅防守子(仕、相),黑將、黑攻擊子,黑防守子。此如馬擒孤士是 knkb。車炮對車是krckr

當擊點殘局庫名,你可看到詳細的統計資料以及可以看這個殘局是紅例勝,或黑例和。若是有兵,高兵與低兵的結果可以分別查看。若紅走勝率大於 98%,是為紅例勝。若黑走和率大於98%,是為例和。介於中間則是巧勝或巧和,得看當時的盤面而定。

在統計頁裡還有一些有趣的最長著手連結。在每一個 Order 裡,我選了一個最長著手放在表裡。擊點會帶你進入該盤面。你可以一再擊點“電腦代走”連結來觀賞殘局庫的解法。你也可以進入“練習攻防”模式,練習你的殘棋能力。

長將和長捉

Order 須要多一些說明。象棋和西洋棋在重覆盤面的判決有所區別。西洋棋若同樣盤面出現三次判和。而象棋則會因當時的情況而有勝、負、和的不同判決。目前的殘局庫 以亞洲規則為準。簡單的說,當一方長將或長捉另一方時,該方須要改變著法。假如不變則會被判負。相對的另一方則為勝。假如在重覆的情況下,並沒有任何一方 有長將或長捉的情形,若雙方皆不願變著,則判為和。因為象棋和西洋棋在這點不同,因此典型西洋棋的回溯分析法沒辨法一成不變的照搬到象棋來用。就我所知, 一直到方浩任等發表下列的文章之前,殘局庫的製作只限於只有一方有攻擊子。因此,我認為這是一篇很有趣的論文。然而,這篇論文只解決了長將的問題而沒有解 決長捉的問題。起初,當我根據他們的方法建造殘局庫時,我發現還有許多長捉的盤面沒有處理正確。(meifire 幫了很大的忙)。還好,我能將他們的方法延伸到長捉的情況。如此,這殘局庫應遵從所有的象棋亞洲規則。是否如此,希望你能幫忙看看對不對。

因為長將和長捉的規則,除了將死對方以外,一方可以逼迫另一方長將或長捉,如此該方得走向劣勢或維持不變而被宣判為負。這種長將或長捉的情形在雙方 都有攻擊子的時候,可以在被將死之前發生很多次。強勢方除了可以強迫將死對方以外,也可以迫對方長將或長捉而必須變著。在令對方長將或長捉的盤面以及所有 導致該情形的所有盤面,我們給它們指定一個 Order。Value 值在這種情況變成到長將或長捉局面的最少步數。一樣的,奇數代表勝,偶數代表負。當 Value 是 0 時,你只能走到同 Order 而 Value 是 1 的將或捉的盤面,或則是走到 Order 比較小的負的盤面。因為強勢方可以確定讓 Order 一直變小(因為將或捉是有限次的),最終將達到將死對方的目的。

輸入任何盤面

你如果看你瀏覽器的位址欄,你會注意到在“endgame.cgi?”或“play.cgi?”的後面老是跟著一串奇怪的符號。這是用來代表每個各 別盤面的數符。假如你學會如何產生這串數符,你就有辨法輸入任何盤面。假如該盤面已經被包含在已有的殘局庫裏,你就可以看到相對應的爪哇棋盤和勝負情況。 我強烈建議你能學會這個方法。如果以後有公認標準的象棋盤面輸入法,我想會跟這方法大同小異。從最上面一列開始,由左至右。假如是一個空格,將心中假想的 空格計數器加一。假如不是空格,將空格數寫出來(如果是零則省略),然後寫出該棋子的代符(依上表)。紅的是小寫,黑的為大寫。將計數器歸零,然後再重覆 以上的步驟直到列的最右邊。這時將空格計數器值寫出。一樣的,如果是零則省略。如此由上而下直到最後一列。前面馬擒孤士例子的代符是 "4K44B49994n495k399"。跟真的盤面比較一下,看你是否可以瞭解。 這串數符最後面加一個 0,代表輪黑方走子。沒有 0 則代表輪紅走子。如果想翻轉棋盤,則在最最後面加一個(:)符號。擊點以下例子看看有何下同: 4K44B49994n495k3990 , 4K44B49994n495k3990:

待完成

有用的實戰殘局庫。歡迎提供意見。現在的程式能處理攻守方共三個攻擊子外加一些防守子,或四個攻擊子。

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]