電腦暗棋程式Observer的設計與實作

Abstract

近幾年來電腦暗棋程式逐漸發展，目前已具有一定程度的棋力。暗棋程式下棋時需要考慮走子和翻子之間的選擇。如果選擇翻子，還要考慮期望值的問題。 本程式會評估各個子力的價值，並使用搜尋尋求一個好的走法，另外有時候要做特殊處理以解決一些盤面上的問題。在翻子的問題上我們除了算出期望值之外，還做了一些額外的調整。 在殘局時由於棋子可走的空間通常較大，使得搜尋時每一層會有較多的步數。當每一層的步數變多時，能搜尋的層數就下降了。如果有殘局庫，程式搜尋的過程在找到殘局庫的內容後可以馬上知道結果，以提高殘局時程式搜尋的效率。我們實作出可以有一個暗子的五子以內的殘局庫，使得程式在殘局的處理上更有方向性。 本程式在TCGA 2014的比賽中得到銅牌。希望讀者能夠從本文所使用的方法中發現一些值得參考的地方。

Chinese Dark Chess programs have become more and more powerful for several years. When a program plays the game, it chooses among the normal moves and the revealing moves. If it chooses a revealing move, it should calculate its expectations. Program finds a good move by evaluating the values of each pieces and by searching. Sometimes it makes special arrangements to deal with some problems on the board. In order to reveal a piece correctly, we did some adjustments besides calculating expectations in this thesis. There is usually more space in the endgame, thus there are more moves for each side to play and the search space will become larger. If an endgame database exists, the program can find the results directly from the endgame database and then it can improve the efficiency in the endgame. In this study, we made an endgame database for the boards with at most five pieces containing zero or one dark piece. This makes our program more competitive in the endgame. Our program has won the bronze medal of TCGA 2014. We hope that readers can find some benefits from the methods described in this thesis.