臺灣博碩士論文加值系統

暗棋是相當大眾化的棋類遊戲之一，比起其他棋類遊戲多了運氣成分，因此適合做為茶餘飯後的休閒娛樂。
由於具有運氣成分，因此暗棋在實作程式上具有相當的困難度，其翻棋時大量的可能性將會不斷的影響棋局的發展，必須在顧慮到搜尋的速度之下盡可能的將翻棋的所有可能列出來。而在過往alpha-beta裁剪樹搜尋方法對於翻棋的問題處理的並不好，而且因為棋盤上的移動限制，容易造成許多在搜尋上的問題。
本研究議題便是將適合解決機率性問題的蒙地卡羅搜尋樹演算法應用在暗棋程式的搜尋結構上。從開局就使用蒙地卡羅方法一直到棋局結束，並且只使用極少量的經驗法則。我們發現利用蒙地卡羅的特性可以適當並精確的處理翻棋，並正確的判斷棋局的優劣，同時可以避免大量的和棋。

Chinese dark chess is a very popular board game. It differs from Chinese chess or Western chess of the possibility of flipping unknown pieces. It is suitable as a staple of leisure entertainment.
With uncertainty, Chinese dark chess is difficult to implement. Flipping pieces will continue to influence the likelihood result of game. Considering the speed of search, we must consider as much as possible situations at the same time. In the past, alpha-beta pruning search tree method for dealing with the problem of flipping piece is not good enough, because of limitations on movement on the board, likely to cause many search problems.
Our research topic is to solve the problem by Monte Carlo tree search algorithms. We just used a small amount heuristics in our program and got a satisfied result. We found that the characteristics of the use of Monte Carlo can flip pieces accurately and the right to determine the position of games. Furthermore, we can avoid a large number of draw games.

摘要
Abstract
致謝
目錄
表目錄
圖目錄
第一章 緒論
1.1 研究背景與動機
1.2 研究目的
1.3 論文概述
第二章 暗棋簡介
2.1 暗棋規則
2.2 基礎理論與概念
第三章 相關文獻探討
3.1 蒙地卡羅概念簡述
3.2 蒙地卡羅樹狀搜尋演算法
3.3 相關程式
3.3.1 Basic
3.3.2 翻棋策略
3.3.3 更全面的搜尋
3.3.4 對翻棋的各種處理方式
第四章 研究方法與架構
4.1 走棋系統架構
4.2 翻棋系統架構
4.3 較短路徑加權
4.4 模擬的策略
第五章 實驗與結果分析
5.1 實驗軟硬體設備環境
5.2 實驗平台介紹
5.3 實驗設計
5.3.1 模擬次數對勝敗率的影響
5.3.2 較短路徑加權
5.3.3 UCB公式的調整
5.3.4 與alpha-beta程式對照
5.4 實驗結果分析
第六章 結論與未來研究方向
6.1 結論
6.2 未來研究方向
參考文獻
一、英文參考文獻
二、中文參考文獻

【1】 P. Auer, N.C. Bianchi and P. Fischer, “Finite-time Analysis of the Multiarmed Bandit Problem”, Machine Learning, 47, 2002, page 235－256.
【2】 B. Bruegmann, “Monte Carlo Go”, October 9, 1993.
【3】 B.N. Chen, B.J. Shen and T.S. Hsu, “Chinese Dark Chess”, ICGA Journal, June, 2010, page 93－106.
【4】 B.N. Chen, “Knowledge Abstraction and Its Applications in Computer Games”, National Taiwan University Doctoral Dissertation, January, 2011.
【5】 S. Gelly, Y. Wang, R. Munos, O. Teytaud, “Modification of UCT with Patterns in Monte-Carlo Go”, November, 2006.
【6】 M. H. Kalos, P. A. Whitlock, “Monte Carlo Methods”, John Wiley & Sons Inc, November 24, 2008.
【7】 S. J. Yen, Jr-C. Chen, T-N. Yang, and S-C. Hsu, “Computer Chinese Chess”, ICGA Journal, Vol.27, No. 1, March, 2004, page 3－18.
【8】 【Taiwan Computer Game Association】http://tcga.ndhu.edu.tw/
【9】 【Wikipedia】中國象棋變體 http://zh.wikipedia.org/zh-cn/Wikipedia
【10】 【台灣暗棋競賽規則－台灣暗棋規則（標準規則）】, April, 13, 2010. http://www.betcity.com.tw/bbs/viewthread.php?tid=651
【11】 周政緯，｢一個以UCT為基礎的電腦圍棋程式之設計與實作｣，輔仁大學資訊工程研究所碩士論文，2008。
【12】 賴學誠，｢電腦暗棋程式與經驗法則之配合與實作｣，國立東華大學資訊工程研究所碩士論文，2008。
【13】 謝曜安，｢電腦暗棋之設計與實作｣，國立臺灣師範大學資訊工程研究所碩士論文，2008。