電腦暗棋之人工智慧改良

Artificial Intelligence Improvement of Chinese Dark Chess

勞永祥(Lou Weng Cheong)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2011年)

摘要

一直以來電腦棋類人工智慧的發展主要集中在完全資訊的遊戲，完全資訊的棋類遊戲，盤面的資訊能完全掌握，審局資訊充足，並不含機率的成分。
電腦暗棋是屬於不完全資訊含機率性的棋類遊戲，不像西洋棋、中國象棋是屬於完全資訊的棋類遊戲，如果用一般遊戲樹進行搜尋，在走棋與翻棋夾雜的情況下，若需要對未翻棋子也要作走步搜尋，則需要對所有的未翻棋子都作假設模擬，以求得一個接近的結果。但並不容易準確的審出結果。
經過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.

並列關鍵字

Chinese dark chess ； incomplete information game ； artificial intelligence

參考文獻

[13] 陳柏年，“電腦對局知識取得與應用”，國立臺灣大學資訊工程研究所，博士論文，2011。

[5] 林子哲，“「深象」象棋軟體平行化之研究”，國立臺灣師範大學資訊工程研究所，碩士論文，2007。

[7] 黃文樟，“電腦象棋深象中局程式的設計與實作”，國立臺灣師範大學資訊工程研究所，碩士論文，2006。

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

[9] 方裕欽，“UCT算法的適用性及改進策略研究－以黑白棋為例”，國立臺灣師範大學資訊工程研究所，碩士論文，2008。