蒙地卡羅黑白棋程式之設計與開發

Design and Development of Monte Carlo Othello Program

葉銓軒(Quan-Xuan Yeh)

指導教授 ： 周信宏

長榮大學/資訊暨工程學院/資訊管理學系(所)/碩士(2015年)

https://doi.org/10.6833/CJCU.2015.00098

摘要

在黑白棋的研究，大部分還是以傳統遊戲樹的展開搜尋為主，僅少數以蒙地卡羅演算法開發，因為在黑白棋程式裡蒙地卡羅演算法模擬幾乎是以隨機模擬的方式進行，主要的原因在於沒有棋形輔助。在本文中，我們提出了權重陣列引導蒙地卡羅演算法的方法。我們使用權重矩陣來模擬棋盤上各個位置的機率。
我們結合了開局庫以及殘局使用極大極小搜尋演算法，並且建立一個黑白棋程式Mothello。我們使用自由軟體WZebra作為實驗樣板。最後實驗結果顯示權重矩陣引導以及UCB的常數越大對於Mothello的勝率有顯著的影響。

關鍵字

電腦對局 ； 黑白棋 ； 蒙地卡羅演算法 ； 遊戲樹

並列摘要

In the past studies on Othello, most were based on the traditional game tree searching algorithms, but only few were based on Monte Carlo algorithm, because it lacks Othello patterns which derives the simulations in Monte Carlo algorithm being almost pure randomized. In this thesis, we propose a matrix directed approach for Monte Carlo algorithms. We use a weighted matrix to represent the probabilities of the board positions during the simulations. Combining with opening book and MinMax searching in the endgame, we build an Othello program named Mothello. We use an open program WZebra as a template for experiments. The experiments show that the matrix directed approach with larger UCB constant increases the win rate of Mothello.

並列關鍵字

omputer Game ； Othello ； Monte Carlo ； Game Tree

參考文獻

[3] 柯建呈（民國 97），黑白棋完全解之初步研究，長榮大學資訊管理學研究所，碩士論文。

[4] 陳俊傑（民國 96），具備學習能力的6x6 Othello程式之設計與製作，長榮大學資訊管理學研究所，碩士論文。

[6] 游明倫（民國 102），分散式電腦圍棋棋譜搜尋系統之建置，長榮大學資訊管理學研究所，碩士論文。

[1] 王永樂（民國 96），基於UCT之九路電腦圍棋程式Happy GO的設計與實作，國立交通大學資訊學院資訊學程，碩士論文。

[2] 方裕欽（民國 97），UCT算法的適用性及改進策略研究－以黑白棋為例，國立臺灣師範大學資訊工程研究所，碩士論文。