基于博弈树的五子棋算法研究

摘要

在人工智能领域内,博弈是很重要的一个研究分支.通过对博弈的研究,可以解决很多实际问题,使电脑智能向人类智能迈进一大步.1997年,世界头号国际象棋大师卡斯帕罗夫与IBM的超级计算机"深蓝"较量后不得不俯首称臣,让人脑第一次尝到了在电脑面前失败的滋味.博弈理论在这场人机大战中起了关键性的作用.博弈理论已被用于很多棋类游戏的设计中.本文以五子棋问题为例,讨论了一个基于博弈树的五子棋算法及其具体实现,在实现中应用了α-β剪枝法和最大最小树原理进行搜索发现最好的下子位置.针对广度搜索层数的增加所带来的五子棋算法的低效性,进而提出了基于多线程搜索策略和分布式搜索策略的改进方法.