标题: 以区域相关攻击为主的六子棋搜寻演算法
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
显示于类别:Thesis


文件中的档案:

  1. 552101.pdf
  2. 552101.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.