禁圍棋程式設計與研究

Abstract

禁圍棋是圍棋的一種變形，在2011年BIRS會議上被提出，任何一方先吃棋子或自殺，則該方判輸。本篇論文是以MCTS演算法為基礎開發禁圍棋程式，名為HappyNoGo。採用Upper Confidence Bound (UCB)和Rapid Action Value Estimation (RAVE)作法，並研發的一些啟發式(heuristic)方法，加上暴力搜尋與調整參數等方式，來增強HappyNoGo，同時也分析成效。本篇論文也證明禁圍棋5x5盤面為黑方(先手)必勝。 BobNoGo是一個強的公開禁圍棋程式，它分別在2011年BIRS與電腦奧林匹亞競賽中獲得冠軍，因此將之作為我們的實驗分析對象。在執行八萬次模擬的情況下，HappyNoGo對BobNoGo達到81.6%的勝率。當在BobNoGo有八倍模擬次數時，HappyNoGo對BobNoGo仍有66.5%的勝率。

NoGo is a variant of Go proposed in BIRS conference at 2011. The first player who either suicides or captures string loses the game. This thesis is to develop a NoGo program named HappyNoGo based on MCTS algorithm. HappyNoGo is improved by UCB, RAVE, heuristic, brute force search and some parameters adjustment. This thesis also proves that Black wins on NoGo 5x5. Since BobNoGo is a strong and open source NoGo program, winning at BIRS 2011 and Computer Olympiad 2011, it is our target of experiments. HappyNoGo has 81.6% win rate against BobNoGo with the 80000 simulations per move. If BobNoGo has eight times simulations per move, HappyNoGo also has 66.5% win rate against BobNoGo.