結合單迫著與雙迫著搜尋之六子棋程式之研發

Abstract

六子棋(Connnect6)，又名連六棋，為國立交通大學資訊工程系吳毅成教授於第十一屆國際電腦賽局研討會(11th Advances in Computer Games Conference，ACG11)中提出和發展。六子棋的提出是有鑑於五子棋(Go-Moku)和連珠棋(Renju)在幾經改善後仍無法完全消除先手方的優勢而提出的另一種較公平的棋類。 2007年，由劉思源及顏士淨博士設計的六子棋程式「X6」，主要使用雙迫著搜尋，在ICGA(International Computer Games Association)六子棋競賽中取得金牌，顯示出迫著搜尋對棋力影響的強度；2007年及2009年，由Theo van der Storm先生所設計的六子棋程式「MeinStein」，使用淺層的alpha-beta search取得兩面銀牌，可見其審局函數之準確性。 不同於雙迫著搜尋的單迫著搜尋，在實作上難以兼顧成功率、準確性與誤判風險。本論文利用「MeinStein」開放原始碼中之其審局函數來提升單迫著搜尋在成功率、準確性、誤判風險之間的平衡。由此我們所研發出來的程式已能在實戰時較X6與MeinStein更強。Connect6, also called Connective6, was proposed and developed by Professor I-Chen Wu in the 11th Advances in Computer Games Conference. Connect6 is similar to Go-Moku and Renju, and the reason why Connect6 is proposed is to eliminate the dominant position of the first player. In 2007, a Connect6 program 「X6」 got the gold metal at a computer Connect6 competition which was conducted by ICGA(International Computer Games Association.) X6 used a technical search named 「DTS(double threats search algorithm),」 which demonstrates the strength in the competitions; Another Connect6 program 「MeinStein,」 was developed by Mr. Theo van der Storm, by using alpha-beta search. In 2007 and 2009, MeinStein won two silver metals respectively, so that it showed the accuracy of evaluate function. STS(Single threat search algorithm) is different from DTS. The main challenge is that it』s hard to balance hit-rate, reliability and risk. This thesis will try to balance the three properties by combining the evaluation function of MeinStein with STS. Experimental results show that our program can beat both X6 and MeinStein.