论文部分内容阅读
五子棋游戏深受广大玩家的喜爱,并且对于探究人工智能的编程爱好者来说,编制五子棋游戏因规则简单而大受欢迎。五子棋人机对战的主要原理是根据五子棋的基本规则,要让电脑知道该在哪一点下子,就要根据盘面的形势,为每一个可能落子的点分别计算其重要程度,也就是该点的得分,然后通览全盘选出数值最大的一点,若有多个最大值,则随机选取其中一个,计算机随机选择分值最大的一点,可以保证它在每盘棋中选择的落子点位置有所不同,使得玩家不可能用一种棋局反复赢计算机。近年来,博弈树算法在五子棋中得到了广泛应用。计算机博弈,历来是人工智能的一个重要的研究领域,计算机博弈的研究在一系列领域都产生了大量的科技成果,并且,博弈树搜索算法作为机器博弈中的一个重要组成环节,经过多年发展,也产生了一大批技术成果。但是,国内在这方面的研究与应用却相对滞后,多数情况下仍然沿用基础的极大极小算法,这大大减缓了机器博弈的搜索效率。通过对博弈树算法的研究,可以从不同角度理解提高搜索算法效率的思想,掌握各种思想的方法从而提高对博弈树搜索算法的理解程度,达到改善算法和实际应用开发的目的。本文在基于已有的α-β剪枝和历史启发预估排序的基础之上,针对节点扩展时,搜索范围较大的问题,加入了有限范围限定和底层剪枝的方法。同时,为了增加游戏的趣味性和益智性,五子棋游戏提供了两种对战方式。即人人对战和人机对战。本文的研究工作主要从四个方面着手。首先,对五子棋游戏的基本理论与概念进行了系统的介绍和研究。其次,对博弈树算法进行介绍,并总结当前已有的博弈树的优化方法,包括剪枝、预估排序和历史启发等,并给出有针对性的改进。第三,对五子棋对弈系统进行分析和设计,在人机对战模式下,我们基于博弈树的思想,对每一个局面给定一个估值,轮到计算机下棋时,计算机在一定深度范围内对棋局进行极大极小搜索,找出最佳下棋点,并用α-β技术剪枝和有限范围限定等技术来提高速度;在人人对战模式下,提供友好的操作界面,方便初级五子棋的爱好者锻炼棋力。最后,通过编程实现系统并测试。该五子棋游戏使用java语言编写完成,通过实验测试获得了良好效果,能够满足大部分需求。