臺灣博碩士論文加值系統

暗棋，又稱盲棋，只使用中國象棋棋盤的一半(所以也叫半棋)，傳說發明者為"棋壇總司令"謝俠遜。因為要輪流翻棋走子，所以也叫"翻翻棋"。
電腦暗棋是屬於不完全資訊含機率性的棋類遊戲，不像西洋棋、中國象棋是 屬於完全資訊的棋類遊戲。如果用一般遊戲樹進行搜尋，在走棋與翻棋夾雜的情 況下，若需要對未翻棋子也要作走步搜尋，則需要對所有的未翻棋子都作假設模 擬，以求得一個接近的的結果。但並不容易準確且有效率地計算出結果。
本論文主要提出天敵、半天敵以及兵與卒數量三項策略，作為評估棋子的子力在動態設置模式下的考量因素，以達到更準確的棋子的子力之計算，並且使用選擇性展開遊戲樹以及不同的時間控制方法以提升遊戲樹搜尋速度及中盤搜尋層數提升的效果。實測結果顯示，本程式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.

第一章 緒論 1
1.1 研究背景 1
1.2 暗棋的困難之處 1
1.3 研究意義 2
1.4 論文架構 4
第二章 暗棋相關介紹 6
2.1暗棋棋規介紹 6
2.2 電腦暗棋對局競賽介紹 7
2.3相關論文介紹 8
第三章 搜尋演算法與資料結構 15
3.1 搜尋演算法 15
3.1.1 MiniMax Search 16
3.1.2 Alpha-beta Pruning 18
3.2 Bitboard 19
3.3 Transposition Table 23
3.4 逐層加深搜尋法 26
第四章 設計方法 27
4.1翻子與走子的抉擇 27
4.2先吃重要子 31
4.3審局函數設計 34
4.4遊戲樹搜尋加速 41
4.4.1走步排序 41
4.4.2遊戲樹的選擇性展開搜尋 41
4.5時間控管 44
4.6電腦暗棋程式TsaiB8的設計 47
4.6.1互斥鎖 47
4.6.2 Master-Worker架構 48
4.6.3搜尋深度的平衡 49
4.6.4搜尋時間分配 50
第五章 結論與未來展望 51
5.1 結論 51
5.2 未來方向 52
附錄 53
參考資料 56

[1] 謝曜安，電腦暗棋之設計及實作，國立台灣師範大學資工所碩士論文，2008。
[2] 謝政孝，暗棋中棋種間食物鏈關係之探討與實作，國立臺灣師範大學資工所碩士論文，2010。
[3] 施宣丞，電腦暗棋程式DarkCraft的設計與實作，國立臺灣師範大學資工所碩士論文，2012。
[4] 詹凱翔，電腦暗棋程式Darkness的設計與實作，國立臺灣師範大學資工所碩士論文，2013。
[5] 徐大開，電腦暗棋程式Observer的設計與實作，國立國立台灣師範大學資工所碩士論文，2014。
[6] 林庭羽，電腦暗棋殘局庫之研究，中原大學應用數學所碩士論文，2013。
[7] 龔建銓，使用GPU平行運算加速電腦象棋之走子產生器，國立成功大學資工所碩士論文，2009。
[8] 黃士傑，應用於電腦圍棋之蒙地卡羅樹搜尋法的新啟發式演算法，國立台灣師範大學資工所博士論文，2011。
[9] 劉孟謙，電腦象棋程式Shark的設計與實作，國立國立台灣師範大學資工所碩士論文，2014。
[10] 程式人雜誌網站，http://programmermagazine.github.io/201407/htm/focus3.html，2014。
[11] 維基百科，http://zh.wikipedia.org/，2016。
[12] Chess Programming網站，https://chessprogramming.wikispaces.com/，2014。
[13] N. Jouandeau and T. Cazenay, "Small and Large MCTS Playouts Applied to Chinese Dark Chess Stochastic Game", In: Tristan Cazenav, Winands, CGW 2014. CCIS, vol.504, pp.78-89. Springer, Heidelberg(2014).
[14] B. N. Chen, B. J. Shen, and T. S. Hsu, "Chinese Dark Chess," ICGA Journal, Vol. 33, No. 2, January 2010.
[15] B. N. Chen, and T. S. Hsu, "Automatic Generation of Opening Books for Dark Chess," Computer and Games, Vol. 8427, July 2014, pp 221-232.
[16] J. C. Chen, T. Y. Lin, B. N. Chen, and T. S. Hsu, " Equivalence Classes in Chinese Dark Chess Endgames," IEEE Transactions on Computational Intelligence and AI in Games, April 2014.
[17] N. Jouandeau, "Varying Complexity in Chinese Dark Chess Stochastic Game," 2014 TCGA Conference, Taipei, Taiwan, June 2014.
[18] S. J. Yen, C. W. Chou, J. C. Chen, I. C. Wu, and K. Y. Kao, "Design and Implementation of Chinese Dark Chess Programs," IEEE Transactions on Computational Intelligence and AI in Game, Vol. 7, No. 1, March 2015.