以區域相關攻擊為主的六子棋搜尋演算法

Abstract

六子棋是在2005年由吳毅成教授所發明的一種棋類遊戲，近年來已經發展成為世界性的遊戲。本實驗室也針對六子棋研發了一個AI程式──NCTU6，它曾獲得兩屆六子棋奧林匹亞賽局競賽六子棋項目的金牌，以及在人機競賽中擊敗許多棋士。然而目前NCTU6仍有需改進的地方，當AI在進行迫著空間搜尋時，會花費相當多的時間做一些不必要的搜尋。這篇論文的目的是為了利用區域相關攻擊的搜尋演算法(Dependency-Based Search)的概念來改善NCTU6的迫著空間搜尋演算法(Threat Space Search)。然而要將區域相關攻擊演算法的概念套用於六子棋極為困難，這篇論文提出了一些方法來解決相關的攻擊問題。實驗結果證實了區域相關攻擊演算法應用於六子棋的效果優異，迫著空間搜尋的速度提升了約3倍，尤其是針對某些搜尋量特別大的盤面，能夠有效壓低搜尋時間，最高達到50倍以上的加速。

The Connect6 game, first introduced by Professor I-Chen Wu in 2005, now becomes one of the popular games in the world. NCTU6 is a Connect6 AI program developed in our lab, which has won gold medals in ICGA tournaments twice and defeated many professional players in Man-Machine Connect6 championships. The objective of this thesis is to apply the concept of Dependency-Based Search to Threat Space Search of NCTU6. Though the AI of NCTU6 works very well, it takes a lot of time on Threat Space Search for traversing many unnecessary positions. The result of the experiment shows that Dependency-Based Threat Space Search speeds up by a factor of 3 in average, and about 50 times faster for some hard positions.