标题: | 以区域相关攻击为主的六子棋搜寻演算法 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 |
文件中的档案:
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.