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

Dependency-Based Search for Connect6

康皓華(Hao-Hua Kang)

指導教授 ： 吳毅成

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00785

摘要

六子棋是在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.

並列關鍵字

Threat Space Search ； Dependency-Based Search ； Connect6 ； Conservative Threat Space Search

參考文獻

[1] L.V. Allis, Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands, 1994.

[3] Thomas Anantharaman, Murray Campbell and Feng-hsung Hsu. ¡§Singular Extensions: Adding Selectivity to Brute-Force Searching¡¨, Artificial Intelligence, vol. 43, no. 1, pp. 99-109, 1990.

[4] T. Cazenave, A Generalized Threats Search Algorithm. Computers and Games, Vol. 2883 of Lecture Notes in Computer Science, pp. 75¡V87, 2003.

[7] Lin, P.-H., and Wu, I.-C., NCTU6 Wins Man-Machine Connect6 Championship 2009, ICGA Journal, Vol. 32(4), pp. 230¡V232, 2009.

[10] T. Thomsen, Lambda-search in game trees - with application to Go, ICGA Journal, Vol. 23 203¡V217, 2000.