電腦暗棋程式Dancing的設計與實作
No Thumbnail Available
Date
2013
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
暗棋，又稱盲棋，只使用中國象棋棋盤的一半(所以也叫半棋)，傳說發明者為"棋壇總司令"謝俠遜。因為要輪流翻棋走子，所以也叫"翻翻棋"。
電腦暗棋是屬於不完全資訊含機率性的棋類遊戲，不像西洋棋、中國象棋是 屬於完全資訊的棋類遊戲。如果用一般遊戲樹進行搜尋，在走棋與翻棋夾雜的情 況下，若需要對未翻棋子也要作走步搜尋，則需要對所有的未翻棋子都作假設模 擬，以求得一個接近的的結果。但並不容易準確且有效率地計算出結果。
本論文主要提出天敵、半天敵以及兵與卒數量三項策略，作為評估棋子的子力在動態設置模式下的考量因素，以達到更準確的棋子的子力之計算，並且使用選擇性展開遊戲樹以及不同的時間控制方法以提升遊戲樹搜尋速度及中盤搜尋層數提升的效果。實測結果顯示，本程式Dancing比起去年TAAI 2015 的亞軍暗棋程式 Observer（本所研究生-徐大開所研發）約有五成至六成的贏率。
我們已經分別實作出暗棋程式TsaiB8以及Dancing並且分別參與TAAI 2015、TCGA 2016、ICGA 2016的對局比賽。
Chinese Dark Chess, also known as blind chess or half chess, only uses half of the Chinese chess board. It is said that the inventor is the "Chinese chess commander" Jia-Syun Sie. Because it must take turns revealing or moving pieces, it is also called "revelation chess". Chinese dark chess is an incomplete information game with probabilities, which is not the same as the 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 within a reasonable time. In this thesis, we propose three approaches, i.e. natural enemies, half natural enemies, and the number of soldiers, to evaluate the values of all pieces in dynamic setting mode. We also use selective game tree search and different time control methods to improve the game tree search efficiency and the midgame search depth. The experimental results indicate that our program "Dancing" got about 50% ~ 60% win rate against the program "Observer" which won the silver medals at the TAAI 2015. We have designed the Chinese dark chess programs TsaiB8 and Dancing and have attended the computer game tournaments in TAAI 2015, TCGA 2016, and ICGA 2016.
Chinese Dark Chess, also known as blind chess or half chess, only uses half of the Chinese chess board. It is said that the inventor is the "Chinese chess commander" Jia-Syun Sie. Because it must take turns revealing or moving pieces, it is also called "revelation chess". Chinese dark chess is an incomplete information game with probabilities, which is not the same as the 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 within a reasonable time. In this thesis, we propose three approaches, i.e. natural enemies, half natural enemies, and the number of soldiers, to evaluate the values of all pieces in dynamic setting mode. We also use selective game tree search and different time control methods to improve the game tree search efficiency and the midgame search depth. The experimental results indicate that our program "Dancing" got about 50% ~ 60% win rate against the program "Observer" which won the silver medals at the TAAI 2015. We have designed the Chinese dark chess programs TsaiB8 and Dancing and have attended the computer game tournaments in TAAI 2015, TCGA 2016, and ICGA 2016.
Description
Keywords
電腦對局, 暗棋, 不完全資訊, Computer Games, Chinese Dark Chess, Imperfect Information Games