電腦暗棋殘局庫之研究

A Study of Computer Dark Chess Endgame Databases

林庭羽(Ting-Yu Lin)

指導教授 ： 徐讚昇 ； 陳志昌

中原大學/理學院/應用數學研究所/碩士(2013年)

https://doi.org/10.6840/cycu201300331

摘要

電腦棋類為人工智慧發展的重要領域之一，目前電腦對局的研究方向，仍著重於完全資訊的棋類遊戲（Perfect Information Game），如西洋棋、象棋、圍棋等，暗棋因翻子的不確定性，屬於不完全資訊帶有機率的遊戲（Imperfect Information Game），為較新的研究方向。
目前在電腦弈棋的研究中，對於暗棋的理解程度尚不足，無論是暗子的翻子機率、子力關係和炮／包的使用等，都是一個很好的研究方向。本文希望藉由建立暗棋殘局資料庫，觀察在各種局勢當中，紅黑方應該採取的正確應對方式，從中能夠找到兵種之間的關係、攻防的固有模式，達到棋力提升與暗棋知識研究的目的。
本文針對暗棋的殘局階段，以盤面上存活的棋子數來劃分，並排除帶有機率性的暗子，設計了暗棋殘局資料庫。首先窮舉出所有可能出現的兵種組合與盤面，再利用回朔分析演算法(Retrograde Analysis)，將不同兵種所組成的殘局盤面，棋子數由少至多，逐一推算勝、負、和的結果，並建構於殘局庫中。只要存在於殘局庫中的兵種組合，都能夠明確的掌握其正確的勝負狀態和最佳著手。
目前這套暗棋殘局資料庫，已經建構出紅黑方棋子總數五子以內的所有兵種組合。並從中找出了幾項特殊的實際例子，與過去我們對於暗棋的理解有截然的不同情況。除了增進暗棋的棋力與知識之外，也能幫助修改現行的暗棋棋規。

關鍵字

殘局資料庫 ； 暗棋

並列摘要

Computer Games is one of the important areas in the development of artificial intelligence. Currently, the research direction of computer games focuses on perfect information game, such as Western Chess, Chinese Chess and Go. Because of the uncertainty of flipping pieces, Dark Chess, an imperfect information game with probabilistic, is a recent research topic.
In current computer games, dark chess has few research findings. The probabilistic behavior of flipping, the relation of pieces and the usage of cannons are all good research directions. By means of constructing an endgame database in dark chess, we can obtain more knowledge about dark chess.
In this thesis, the endgame phase is defined according to the number of remaining pieces on the board. Without considering dark pieces, we designed an endgame database for dark chess. First, we enumerate all possible material combinations and positions. Then, we use the retrograde analysis algorithm to calculate the win, loss, draw of all positions in different material combinations and construct them into the endgame database. We can know the correct result and the best move of any given position in our endgame database.
The built endgame database contains all material combinations of five pieces. We also found several interesting examples that are different to our knowledge. Constructing the endgame database not only increases the playing strength and knowledge, but also helps the revision of current rule of dark chess.

並列關鍵字

Endgame Databases ； DarkChess

參考文獻

【5】 陳志昌（2005）。電腦象棋知識庫系統之研製。國立臺灣大學資訊工程研究所，博士論文。

【6】 陳柏年（2011）。電腦對局知識取得與應用。國立臺灣大學資訊工程研究所，博士論文

【3】 李明臻 （2011）。台灣直棋的勝負問題之研究。國立臺灣大學資訊工程研究所，碩士論文

【8】 郭哲宇（2007）。電腦象棋擴大空步剪裁演算法的設計與實作，國立臺灣師範大學資訊工程研究所，碩士論文

【12】 勞永祥（2011）。電腦暗棋之人工智慧改良，國立臺灣師範大學資訊工程研究所，碩士論文