學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
1 results
Search Results
Item 電腦五子棋程式JacksonFive之設計與實作(2018) 陳羽恆; Chen, Yu-Heng五子棋（Gomoku）是個歷史悠久的棋類遊戲，規則簡單但遊戲複雜度相當高，非常具有研究價值。其中比較常見的搜尋演算法有MiniMax、Alpha Beta Pruning、Iterative Deepening及Monte Carlo Tree Search（MCTS）等等。在這些演算法的實作細節中，存在著一些可以改進搜尋效率或精準度的地方。包括MCTS中的expansion階段可以利用米字型遮罩來減少搜尋廣度、simulation階段加上深度加權的調整，使得不同模擬深度有不同的分數。 在最傳統的MCTS算法中，也存在著一些尚待解決的問題。例如贏率稀釋問題，最優走步的贏率會被其他分支稀釋掉，因此分支愈多的子樹會被稀釋得更嚴重，因此，本論文提出了兩種解決稀釋問題的方法。 MCTS也存在一個缺點，就是不管盤面為何，都要經過固定的搜尋時間、或是一定的模擬次數才會決定走步。因此，本論文提出了一套時間控管機制，可以針對不同的盤面情況，給予不同的MCTS搜尋時間。 透過種種的改良，我所撰寫的程式JacksonFive也參加過數次的電腦對局比賽的外五棋項目，其中在TCGA 2015拿到銅牌、ICGA 2016拿到銅牌、TAAI 2017拿到銅牌、TCGA 2017拿到銀牌、ICGA 2018拿到金牌。另外，本論文的部份成果已發表在The 10th International Conference on Computers and Games (CG 2018)的一篇論文中。