簡易檢索 / 詳目顯示
| 研究生： |
徐大開 |
|---|---|
| 論文名稱： |
電腦暗棋程式Observer的設計與實作 The Design and Implementation of the Chinese Dark Chess Program Observer |
| 指導教授： | 林順喜 |
| 學位類別： |
碩士 Master |
| 系所名稱： |
資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年： | 2014 |
| 畢業學年度： | 102 |
| 語文別： | 中文 |
| 論文頁數： | 56 |
| 中文關鍵詞： | 電腦對局 、暗棋 、不完全資訊遊戲 |
| 英文關鍵詞： | Computer Games, Chinese Dark Chess, Imperfect Information Games |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：186 下載：13 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
近幾年來電腦暗棋程式逐漸發展，目前已具有一定程度的棋力。暗棋程式下棋時需要考慮走子和翻子之間的選擇。如果選擇翻子，還要考慮期望值的問題。
本程式會評估各個子力的價值，並使用搜尋尋求一個好的走法，另外有時候要做特殊處理以解決一些盤面上的問題。在翻子的問題上我們除了算出期望值之外，還做了一些額外的調整。
在殘局時由於棋子可走的空間通常較大，使得搜尋時每一層會有較多的步數。當每一層的步數變多時，能搜尋的層數就下降了。如果有殘局庫，程式搜尋的過程在找到殘局庫的內容後可以馬上知道結果，以提高殘局時程式搜尋的效率。我們實作出可以有一個暗子的五子以內的殘局庫，使得程式在殘局的處理上更有方向性。
本程式在TCGA 2014的比賽中得到銅牌。希望讀者能夠從本文所使用的方法中發現一些值得參考的地方。
Chinese Dark Chess programs have become more and more powerful for several years. When a program plays the game, it chooses among the normal moves and the revealing moves. If it chooses a revealing move, it should calculate its expectations.
Program finds a good move by evaluating the values of each pieces and by searching. Sometimes it makes special arrangements to deal with some problems on the board. In order to reveal a piece correctly, we did some adjustments besides calculating expectations in this thesis.
There is usually more space in the endgame, thus there are more moves for each side to play and the search space will become larger. If an endgame database exists, the program can find the results directly from the endgame database and then it can improve the efficiency in the endgame. In this study, we made an endgame database for the boards with at most five pieces containing zero or one dark piece. This makes our program more competitive in the endgame.
Our program has won the bronze medal of TCGA 2014. We hope that readers can find some benefits from the methods described in this thesis.
[1] 龔長偉，蒙地卡羅樹狀搜尋在暗棋上的應用，國立東華大學資訊工程研究所碩士論文，2011。
[2] 謝曜安，電腦暗棋之設計及實作，國立台灣師範大學資訊工程研究所碩士論文，2008。
[3] 賴學誠，電腦暗棋程式與經驗法則之配合與實作，國立東華大學資訊工程研究所碩士論文，2008。
[4] 謝政孝，暗棋中棋種間食物鏈關係之探討與實作，國立臺灣師範大學資訊工程研究所碩士論文，2010。
[5] 勞永祥，電腦暗棋之人工智慧改良，國立臺灣師範大學資訊工程研究所碩士論文，2011。
[6] 施宣丞，電腦暗棋程式DarkCraft的設計與實作，國立臺灣師範大學資訊工程研究所碩士論文，2012。
[7] 詹凱翔，電腦暗棋程式Darkness的設計與實作，國立臺灣師範大學資訊工程研究所碩士論文，2013。
[8] 林庭羽，電腦暗棋殘局庫之研究，中原大學應用數學系碩士論文，2013。
[9] ICGA Tournaments網站，http://www.grappa.univ-lille3.fr/icga/，2014。
[10] 維基百科，http://zh.wikipedia.org/，2014。
[11] Chess Programming網站，https://chessprogramming.wikispaces.com/，2014。
[12] D. E. Knuth and R. W. Moore, “An Analysis of Alpha-Beta Pruning”, Artificial Intelligence 6(4), pp. 293-326, 1975.
