簡易檢索 / 詳目顯示
| 研究生： |
蔡秉倫 Tsai, Ping Lung |
|---|---|
| 論文名稱： |
以棋型分數、開局庫、平行化方法改良 MCTS 外圍開局五子棋程式 Improving an MCTS Outer-Open Gomoku Program with Pattern Scores, Opening Book, and Parallelization |
| 指導教授： |
林順喜
Lin, Shun Shii |
| 口試委員： |
吳毅成
Wu, I-Chen 顏士淨 Yen, Shi-Jim 陳志昌 Chen, Jr-Chang 周信宏 Chou, Hsin-Hung 林順喜 Lin, Shun Shii |
| 口試日期： | 2023/06/28 |
| 學位類別： |
碩士 Master |
| 系所名稱： |
資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年： | 2023 |
| 畢業學年度： | 111 |
| 語文別： | 中文 |
| 論文頁數： | 51 |
| 中文關鍵詞： | 五子棋 、蒙地卡羅樹搜索 、開局庫 |
| 英文關鍵詞： | Gomoku, MCTS, Opening Book |
| 研究方法: | 實驗設計法 |
| DOI URL： | http://doi.org/10.6345/NTNU202300882 |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：61 下載：1 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
五子棋是一個古老的棋類遊戲，它有著簡單易學且豐富多樣的策略和高度的競技性的特點。由於原始規則的不公平性，現在的五子棋有各種不同的棋規，例如交換行棋權的SWAP2、帶有禁手規則的Renju、外圍開局五子棋等。儘管棋規各異，但遊戲的勝利目標始終是達成“連五”。
本論文旨在研究外圍開局五子棋相關的各層面，探討包括現有的遊戲策略和演算法等技術應用。我們的目標是透過設計棋型分數、開局庫的方法來提升傳統MCTS外圍開局五子棋程式的棋力，並利用平行化的方法加速程式的效能。最後，我們將和第三方程式進行比較測試，用來評估其棋力。
Gomoku is an ancient board game characterized by its simplicity, diverse strategies, and high level of competitiveness. Due to the inherent unfairness in the original rules, there are various variations of Gomoku, such as SWAP2, which allows the second player to swap colors, Renju, which incorporates forbidden move rules for the first player, and Outer-Open Gomoku. Despite the rule variations, the objective of the game remains the same: achieving a “five-in-a-row” pattern.
This thesis aims to investigate different aspects of Outer-Open Gomoku, including the game strategies, and algorithms. Our goal is to enhance the playing strength of MCTS Outer-Open Gomoku program by designing scores for some specific patterns and using opening book. Additionally, we improve its performance through parallelization techniques. Finally, we compare and test the program against third-party programs to evaluate its strength.
[1] Crazy Stone, https://www.remi-coulom.fr/CrazyStone/.
[2] UCT (Upper Confidence bounds applied to Trees), https://cs.stackexchange.com/q/111619.
[3] D. Silver et al., “Mastering the Game of Go with Deep Neural Networks and Tree Search,” Nature 2016 529:7587, vol. 529, no. 7587, pp. 484–489, 2016.
[4] D. Silver et al., “Mastering the Game of Go without Human Knowledge,” Nature 2017 550:7676, vol. 550, no. 7676, pp. 354–359, 2017.
[5] L. V. Allis, Searching for Solutions in Games and Artificial Intelligence, Ph.D. Thesis, University of Limburg, Maastricht, 1994.
[6] 陳昌裕，五子棋新棋規及五~七路五子棋勝負問題之研究，國立臺灣師範大學資工所碩士論文，2013。
[7] A. Liu, J. Chen, M. Yu, Y. Zhai, X. Zhou and J. Liu, “Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search,”, https://doi.org/10.48550/arXiv.1810.11755,2018.
[8] F. Duarte, N. Lau, A. Pereira and L. Reis, “A Survey of Planning and Learning in Games,” Applied Sciences, https://doi.org/10.3390/app10134529, 2020.
[9]程式人雜誌，https://programmermagazine.github.io/201407/htm/focus3.html.
[10] C. H. Chen, W. L. Wu, Y. H. Chen, and S. S. Lin, “Some Improvements in Monte Carlo Tree Search Algorithms for Sudden Death Games,” ICGA Journal, vol. 40, no. 4, pp. 460-470, 2018.
[11] Gomocup, https://gomocup.org/.
[12] GitHub – Rapfi-gomocup, https://github.com/dhbloo/Rapfi-gomocup.
[13] KataGomo, http://chiuinan.github.io/game/game/intro/ch/c41/katagomo.htm.
[14] Yixin, https://www.aiexp.info/pages/yixin-cn.html.
[15] Fiver6, http://chiuinan.github.io/game/game/intro/ch/c41/fiver6.htm.
[16] KataGo, https://github.com/lightvector/KataGo.
[17] GTP-Go Text Protocol, https://www.lysator.liu.se/~gunnar/gtp/.
[18] 吳天宇，基於AlphaZero General Framework 實現Breakthrough遊戲，國立台灣師範大學碩士論文，2019。
[19] 劉浩萱，AlphaZero演算法結合快贏策略或迫著空間實現於五子棋，國立台灣師範大學碩士論文，2020。
