標題: 以區域相關攻擊為主的六子棋搜尋演算法
Dependency-Based Search for Connect6
作者: 康皓華
Kang, Hao-Hua
吳毅成
Wu, I-Chen
資訊科學與工程研究所
關鍵字: 迫著空間搜尋;區域相關攻擊搜尋;六子棋;保守迫著空間搜尋;Threat Space Search;Dependency-Based Search;Connect6;Conservative Threat Space Search
公開日期: 2012
摘要: 六子棋是在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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079955521
http://hdl.handle.net/11536/50437
Appears in Collections:Thesis


Files in This Item:

  1. 552101.pdf
  2. 552101.pdf