臺灣博碩士論文加值系統

　　傳統暗棋是一種機遇型的棋類遊戲，規則簡單、節奏明快並且緊張刺激。探究其不如圍棋、西洋棋那般風行的關鍵因素之一，在於運氣成份影響太大，壓縮了策略施展的空間，造成遊戲缺乏深度，不夠耐玩。對於傳統暗棋的缺陷，我們提出改善其體質的方法，也就是「雙將暗棋」。實驗結果證明，雙將暗棋的遊戲深度優於傳統暗棋。同時，我們對於衍生出來的高和率問題，也提出有效的處理對策。而改良之後的雙將暗棋，其遊戲深度更是遠超過傳統暗棋。雙將暗棋可降低運氣成份的影響，使能運用的策略變多，增加遊戲深度，提升相當程度的耐玩性。未來，希望雙將暗棋能夠被推廣到華人以外的世界，並且廣為流傳。

　　Chinese Dark Chess (CDC) is an exciting fast tempo stochastic board game with simple rule. CDC is not as popular as Go and Chess due to the result heavily influenced by luck. This reduces varied workable player strategies. As a result, lack of varied game depth cannot attract players for long-lasting. "Double King Dark Chess" (DKDC) is proposed to improve its constitution to overcome the drawback of CDC. Experimental results show that the game depth of DKDC is more deeper than CDC game depth. In addition, for solving the derivative problem of high draw rate, effective countermeasures are provided. A modified DKDC game depth is more deeper than CDC one. Therefore, reducing the impact of luck enriches varied workable player strategies, increases game depth and attracts players for long-lasting. In the future, we hope DKDC to be generalized widely in the world.

摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 VI
表目錄 VIII
第一章 簡介 1
1.1 研究背景 1
1.2 研究動機與目的 1
1.3 論文概述 2
第二章 基礎理論與相關文獻 3
2.1 傳統暗棋規則 3
2.2 電腦對局基礎理論 7
2.2.1 Minimax Search 7
2.2.2 Negamax Search 9
2.2.3 蒙地卡羅樹搜尋 11
2.3 實驗使用程式 16
2.4 深度的定義 18
2.5 ELO rating system 21
第三章 雙將暗棋 23
3.1 雙將暗棋 23
3.1.1 傳統暗棋的隱性缺陷 23
3.1.2 傳統暗棋的改良方法 24
3.2 衍生問題研究 26
3.2.1 雙將暗棋的和局問題 26
3.2.2 和局問題的改良方法 30
第四章 實驗與討論 41
4.1 實驗目的 41
4.2 實驗設計 41
4.3 實驗設備環境 41
4.4 實驗結果與數據分析 42
4.5 深度分析 50
第五章 結論與未來研究方向 53
5.1 結論 53
5.2 未來研究方向 54
參考文獻 55

[1] Artificial Intelligence: A Modern Approach 2/E, Stuart Russell, Peter Norvig.
[2] B.N. Chen, B.J. Shen and T.S. Hsu, "Chinese Dark Chess", ICGA Journal, June, 2010, page 93－106.
[3] B.N. Chen, "Knowledge Abstraction and Its Applications in Computer Games", National Taiwan University Doctoral Dissertation, January, 2011.
[4] Bill Robertie, Magazine "Inside Backgammon", Vol. 2, No. 1, p.4, 1991.
[5] M. H. Kalos, P. A. Whitlock, “Monte Carlo Methods”, John Wiley &; Sons Inc, November 24, 2008.
[6] B. Bruegmann, “Monte Carlo Go”, 1993.
[7] C. Browne, E. Powley, D. Whitehouse, S. Lucas, P. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton, “A survey of Monte Carlo Tree Search,” IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 1, 2012.
[8] Van den Broeck, G., Driessens, K., and Ramon, J., Monte-Carlo Tree Search in Poker using Expected Reward Distributions, Adv. Mach. Learn., LNCS 5828, no. 1, 2009, pp. 367–381.
[9] Guillaume Chaslot, Mark Winands, Jaap H. van den Herik, Jos Uiterwijk, and Bruno Bouzy. Progressive Strategies for Monte-Carlo Tree Search. In Joint Conference on Information Sciences, Salt Lake City 2007, 2007.
[10] Arpad Elo, The Rating of Chessplayers,Past and Present. Arco. 1978.ISBN 0-668-04721-6.
[11] Private communication with Professor Olivier Teytaud.
[12] Shi-Jim Yen, Cheng-Wei Chou, Jr-Chang Chen, I-Chen Wu, and Kuo-Yuan Kao, “The Art of the Chinese Dark Chess Program DIABLE,” International Computer Symposium, 2012, Hualien.
[13] 【Wikipedia】，Elo rating system，
http://en.wikipedia.org/wiki/ELO_rating_system。
[14] 周政緯，｢一個以UCT為基礎的電腦圍棋程式之設計與實作｣，輔仁大學資訊工程研究所碩士論文，2008。
[15] 謝曜安，｢電腦暗棋之設計與實作｣，國立臺灣師範大學資訊工程研究所碩士論文，2008。
[16] 賴學誠，｢電腦暗棋程式與經驗法則之配合與實作｣，國立東華大學資訊工程研究所碩士論文，2008。
[17] 龔長偉，「蒙地卡羅樹狀搜尋在暗棋上的應用」，國立東華大學資訊工程研究所碩士論文，2011。
[18] 顏士淨、梁華旻，「雙將暗棋」，2013年全國計算機會議，台中市亞洲大學。
[19] 【Wikipedia】，吃角子老虎，
http://zh.wikipedia.org/wiki/%E8%A7%92%E5%AD%90%E6%A9%9F。
[20] 台灣電腦對局學會，2013, 暗棋比賽規則，http://tcga.ndhu.edu.tw/。