臺灣博碩士論文加值系統

一直以來電腦棋類人工智慧的發展主要集中在完全資訊的遊戲，完全資訊的棋類遊戲，盤面的資訊能完全掌握，審局資訊充足，並不含機率的成分。
電腦暗棋是屬於不完全資訊含機率性的棋類遊戲，不像西洋棋、中國象棋是屬於完全資訊的棋類遊戲，如果用一般遊戲樹進行搜尋，在走棋與翻棋夾雜的情況下，若需要對未翻棋子也要作走步搜尋，則需要對所有的未翻棋子都作假設模擬，以求得一個接近的結果。但並不容易準確的審出結果。
經過ICGA 2010、TAAI 2010及台大資工所game theory課程等多次電腦暗棋比賽，由國立東華大學資訊工程所、國立台灣師範大學資訊工程所以及國立臺灣大學資訊工程所等所開發的電腦暗棋程式都有著共同問題，就是走子或翻棋，都還不太理想。
由於無法合理地走子或翻棋，導致走閒步，棋局無進展。這樣的結果使得在電腦暗棋的比賽中，往往優勢的一方也因為無目標，局勢無法進展，而變成平手結果。
本論文主要提出電腦暗棋的一套新的策略以解決局勢無法順利進展的問題。另外提出更準確的棋子間距離影響力之計算方法。實測結果顯示，本程式Black Cat 比起去年ICGA　2010及TAAI　2010的亞軍程式Dark Chess Beta（本校研究生謝政孝所研發）約有五成六的贏率。

Computer chess-playing is an area of artificial intelligence research. Most of the time, it focuses on the design of chess-playing software to play games with complete information in which all of the players know the other players' preferences.
Chinese dark chess is an incomplete information game with probabilities, which is not the same as complete information games, such as chess or Chinese chess. If we use conventional game-tree searching techniques to play Chinese dark chess, then the number of branches will be very large because there are lots of moves for both “dark pieces” and “bright pieces”. Hence, it is impractical to generates all possible moves in a given board position in order to find a good move.
During and after participating in the competitions of ICGA 2010, TAAI 2010 and final project of NTU game theory course, we found that today most state-of-the-art Chinese dark chess programs, including those developed by NTNU, NTU, and NDHU, still could not play well in moving the “bright pieces” or flipping the “dark pieces”. Due to this phenomenon, most of the Chinese dark chess matches result in a draw even if one player has a large material advantage over the other.
In this thesis, we propose some approaches to fix the problem. We provide a path tracing method to compute more accurately the influence among the chess pieces according to their walking distances.
The experimental results indicate that our program "Black Cat" obtained a winning rate of 56.0% against the program "Dark Chess Beta" which won the Silver medals at the ICGA 2010 and TAAI 2010.

摘 要 i
ABSTRACT ii
致 謝 詞 iii
目 錄 iv
表格目錄 v
圖表目錄 v
第一章 緒論 1
第一節 暗棋人工智慧的現況 1
第二節 暗棋的簡單及困難之處 3
第三節 文獻探討 4
第二章 使用的技術介紹 11
第一節 對局樹 11
第二節 alpha-beta搜尋演算法 13
第三節 Transposition Table 20
第四節 允許空步 24
第五節 Iterative Deepening Search 25
第三章 我們對審局評分的作法 26
第一節 翻棋位置的選擇 26
第二節 距離威脅力計算 32
第三節 動態分數調整 42
第四節 配分設計 45
第五節 審局函數設計 47
第六節 走步或翻棋的選擇方法 47
第四章 結論與未來研究方向 51
第一節 結論 51
第二節 未來研究方向 54
參考著作 56

[1] “chessprogramming”，網址：http://chessprogramming.wikispaces.com/.
[2] “象棋百科全書”，網址：http://www.elephantbase.net/index.htm.
[3] 吳身潤，“人工智慧程式設計”，維科圖書，2002年3月。
[4] 王小春，“人機博奕”，重慶大學出版社，2002年6月。
[5] 林子哲，“「深象」象棋軟體平行化之研究”，國立臺灣師範大學資訊工程研究所，碩士論文，2007。
[6] 涂志堅，“電腦象棋的設計與實現”，廣州中山大學，碩士論文，2004。
[7] 黃文樟，“電腦象棋深象中局程式的設計與實作”，國立臺灣師範大學資訊工程研究所，碩士論文，2006。
[8] 郭哲宇，“電腦象棋擴大空步剪裁演算法的設計及實作”，國立臺灣師範大學資訊工程研究所，碩士論文，2007。
[9] 方裕欽，“UCT算法的適用性及改進策略研究－以黑白棋為例”，國立臺灣師範大學資訊工程研究所，碩士論文，2008。
[10] 謝曜安，“電腦暗棋之設計及實作”，國立台灣師範大學資訊工程研究所，碩士論文，2008。
[11] 賴學誠，“電腦暗棋程式與經驗法則之配合與實作”，國立東華大學資訊工程研究所，碩士論文，2008。
[12] 謝政孝，“暗棋中棋種間食物鏈關係之探討與實作”，國立臺灣師範大學資訊工程研究所，碩士論文，2010。
[13] 陳柏年，“電腦對局知識取得與應用”，國立臺灣大學資訊工程研究所，博士論文，2011。