臺灣博碩士論文加值系統

電腦暗棋於2010 年正式加入電腦奧林匹亞競賽，從此開始有許多團隊加入研究的行列。其共通課題皆為：走步與翻子的時機如何掌握？這個問題是相當困難的，想要完滿的解決並不容易。
我們的目的是開發出一款能夠處理翻走問題的暗棋程式，目前來說顯然這是不實際的。在折衷處理之下，本程式以速度為優先考量，同時也希望能夠具有一定水準的棋力。
暗棋程式的棋力強弱，與搜尋的深度息息相關，而搜尋的深度又受電腦硬體以及演算法限制，所以我們的核心目標就是使用各種手段為程式加速，來加強棋力。
本程式使用Alpha-beta pruning以及Bitboard，並搭配Transposition table加速，擁有高速運算的能力，能夠在大部分的局面下走出較好的走步，並在搜尋中避開大量的重複盤面來節省時間。
目前本程式已於TAAI 2012 以及TCGA 2013 分別取得銅牌，比賽中也發現仍然有可修正的部分，接下來將全力發展後續改良設計，期望能於未來的比賽取得更好的成績。

　　Computer Dark Chess officially became a competition item in the computer Olympiad in 2010. From then on, there are many teams joined this research area. Its common topics are: what's the strategy to choose to "Move" or "Reveal"? This topic is quite difficult; hence perfect solution is not easy to be derived.
　　Our aim is to develop a program which can solve this topic. But, it is clearly not practical at present time. In a compromise deal, speed is the first priority in our consideration. We hope that our program has a stronger ability than others.
　　The ability of Dark Chess program is decided by its searching depth. The searching depth is limited by computer hardware and the algorithms used in the program. Here our core goal is to use a variety of means to speed up and improve the ability of our program.
　　Our program uses alpha-beta pruning algorithm, bitboard structure, and transposition table to achieve a high performance objective. And it can output better moves in most cases, and avoids a huge amount of repeated boards during the search to save time.
　　So far our program has won the bronze medals in TAAI 2012 and TGCA 2013. We still found our many deficiencies during the competitions. We hope that we can continuously improve our program and get good scores in the future competitions.

摘要.................................i
ABSTRACT ........................... ii
第一章 緒論......................... 1
1.1 研究背景........................ 1
1.2 研究目的........................ 2
1.3 研究意義........................ 3
第二章 文獻探討..................... 5
2.1 暗棋棋規介紹.................... 5
2.2 相關論文及程式介紹.............. 6
第三章 資料結構與演算法............. 19
3.1 BitBoard ....................... 19
3.2 程式的搜尋演算法................ 23
3.2 審局函數........................ 31
3.3 後續發展........................ 33
第四章 改良方法與步驟............... 34
4.1 基本概念........................ 34
4.2 重複盤面處理.................... 34
4.3 Zobrist Hashing ................ 35
4.4 Transposition Table ............ 37
4.5 Collision 避免 ................. 38
4.6 同分步情形處理.................. 42
4.7 翻棋............................ 43
4.8 循環盤面處理.................... 44
第五章 結論與未來研究方向........... 46
5.1 結論............................ 46
5.2 未來研究方向.................... 46
參考文獻.............................47

[1]謝曜安，電腦暗棋之設計及實作，國立台灣師範大學資工所碩士論文，2008。
[2]賴學誠，電腦暗棋程式與經驗法則之配合與實作，國立東華大學資工所碩士論文，2008。
[3]謝政孝，暗棋中棋種間食物鏈關係之探討與實作，國立臺灣師範大學資工所碩士論文，2010。
[4]勞永祥，電腦暗棋之人工智慧改良，國立臺灣師範大學資工所碩士論文，2011。
[5]施宣丞，電腦暗棋程式DarkCraft的設計與實作，國立臺灣師範大學資工所碩士論文，2012。
[6] D. E. Knuth and R. W. Moore, "An Analysis of Alpha–Beta Pruning", Artificial Intelligence 6(4), pp. 293–326, 1975.
[7] Albert Lindsey Zobrist, "A New Hashing Method with Application for Game Playing", Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, 1969.
[8] J.-C. Chen, T.-Y. Lin, S.-C. Hsu and T.-S. Hsu, "Design and Implementation of Computer Chinese Dark Chess Endgame Database", Proceeding of TCGA Workshop 2012, Hualien, Taiwan, pp. 5–9, 2012.
[9] 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", Proceeding of TAAI Workshop 2012, Tainan, 2012.

[10] Shi-Jim Yen, Shih-Yuan Chiu and I-Chen Wu, "MODARK Wins Chinese Dark Chess Tournament," ICGA Journal, vol. 33, no. 4, 2010, pp. 230-231, 2010.
[11] B.N. Chen, B.-J. Shen and T.S. Hsu, "Chinese Dark Chess", ICGA Journal 33(2), pp. 93–106, 2010.