基于alphabeta算法的智能五子棋

基于Alpha-Beta算法的五子棋游戏班级：，学号：，姓名： 摘要：博弈是人工智能的主要研究领域之一，而五子棋是经典的双agent博弈游戏。本文对针对五子棋游戏的Alpha-Beta搜索算法进行研究，设计实际算法，并使用Java完成程序设计实现人机博弈。为了提高算法效率，在传统的Alpha-Beta算法的基础上，根据五子棋的特点，通过局部搜索、优先值启发搜索、限制广度等方法减少搜索的分支数，极大地提升了算法的效率。关键词：人工智能；Alpha-Beta搜索；五子棋本组成员：马猛，马攀，宋浩宇本人分工：针对五子棋游戏的Alpha-Beta算法的设计实现与优化1 引言人工智能是一门综合性很强的边缘科学，它研究如何使计算机去做那些过去只能靠人的智力才能完成的工作。而双agent博弈是人工智能的重要分支，主要研究如何在博弈问题中提高机器的智能水平。敌对搜索对这一问题的经典解决方法，而极大极小算法是敌对搜索中最为基础的算法，为了提高极大极小搜索的效率，在极大极小搜索算法的基础上使用Alpha-Beta剪枝所产生的Alpha-Beta搜索算法则是其中最重要的算法之一。本文针对如何实现人机博弈中的五子棋游戏，探讨了Alpha-Beta搜索算法的设计与实现，并在此基础上，实现了改进的Alpha-Beta搜索算法，即利用局部搜索、优先值启发、限制广度等方法来提高Alpha-Beta搜索算法的效率。2 算法原理与系统设计2.1 极大极小算法在人机博弈问题中，博弈程序的搜索过程即是人类走棋的思考过程。命名两个博弈者为Max和Min，博弈程序的任务是为Max寻找最佳的移动位置。因此，深度为偶数的节点，对应于Max的下一步移动位置，成为Max节点；深度为奇数的节点对应于Min的下一步移动的位置，称为Min节点。Max作为博弈程序一方，选择价值极大的子节点走棋，而Min方作为对方，为了钳制Max方，选择价值极小的子节点走棋，这就产生了一个极大极小过程。在决定下一步之前，对这个过程进行一定深度的推理，就会形成博弈树，Max可以通过极大极小搜索在博弈树中寻找最佳的走法。Shannon在1950年首先提出了极大极小算法1 ，从此奠定了计算机博弈的理论基础。2.2 Alpha-Beta搜索算法在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会产生十分庞大的博弈树2。这时如果只进行极大极小搜索，博弈树会存在着一定的数据冗余。如图1所示，节点下方的数字代表该节点的值，方框节点为极大值，圆形框节点为极小值。当A节点搜索下一步位置时，它要取B、C中的最小值，而此时已搜索得B节点值为5，而在搜索C节点时得知D节点值为4，此时可剪去E、F节点，因为C节点的得值必定小于等于4，说明A节点的值为max(B, C) = 5。这种当先辈层的alpha值大于等于后辈beta值而进行的剪枝称为Alpha剪枝。图1 Alpha剪枝同理，在图2中，由于在搜索过程中，已知B节点的值为5，而C的子节点D的值为6，则max(C)大于等于6，A的值为min(B, C)等于5，则可剪去E、F节点。这种已知先辈层beta值小于等于后辈层alpha值的剪枝称为Beta剪枝。 图2 Beta剪枝将Alpha剪枝与Beta剪枝加入极大极小搜索中，可以极大地提升极大极小搜索效率，称新的算法为Alpha-Beta搜索算法。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝 3 。下面为本次游戏中采用的Alpha-Beta算法的伪代码，其中findMin将当前棋局视为极小层，并返回当前棋局的值；同理，findMax将当前棋局视为极大层，并返回当前棋局的值；putOne为初始函数，它得出己方（AI方）的下一步落子位置，并进行落子：function findMin(alpha, beta, step) / 寻找当前棋局的最小估值if step = 0:return evaluate()min = betafor place in possiblePlaces:chessplace = enemywight = findMax(alpha, min, step-1)chessplace = emptyif wight min:min = wightif min max:max = wightif max = beta: / beta剪枝return maxreturn maxfunction putOne():alpha = - Infinitybeta = Infinitymax = -InfinitymaxPlace = nullfor place in possiblePlaces:chessplace = mywight = findMin(alpha, beta, step)chessplace = emptyif max = 0: x_min = x - 1 if x+1 = 0: y_min = y - 1 if y+1 = 0: x_min = min(x_min x1)if x+1 x+1)if y-1 = 0: y_min = min(y_min y-1)if y+1 y+1)在上述伪代码中，默认棋盘大小为15x15，扩展边界大小为1，在实际应用中，可以根据实际情况更改扩充边界值。2.4 通过优先值启发优化算法由Alpha-Beta搜索算法原理可知，搜索的广度决定每一层所扩展的节点数，而且越早搜索到较优者，那么剪枝的效率越高。对此，可以优先搜索一层，对这一层的节点的值进行排序，选取对己方最有利的节点作为最优扩展节点。仅对第一层节点进行搜索，虽然可能不是在多层搜索的基础上的最佳位置，但是它往往是一个较优的位置。通过对第一层扩展节点进行最优值排序，优先选择最优节点进行扩展，可以使Alpha-Beta剪枝尽早发生，提高Alpha-Beta剪枝的效率。2.5 限制搜索广度在进行优先值启发排序后，会发现大部分优先值低的节点会在之后的Alpha-Beta剪枝中被剪去，而且即使在多层搜索之后，最优节点也往往在头几个进行一层搜索得到的最优节点中。基于以上分析，在扩展节点时，可以只选择头几个进行一层搜索的优先值高的节点，这样限制了搜索的广度，提高了剪枝算法的效率。3 实验或测试结果通过实际测试，可以看出算法可以正确运行。如图3所示，当人持黑棋先行，算法对白棋的落子位置进行搜索，剪枝节点与预期吻合，算法最后给出的落子位置符合算法逻辑。 图3 算法执行部分结果测试4 结论本文探讨了针对五子棋游戏的Alpah-Beta算法，通过Alpha-Beta搜索实现了人机博弈的AI部分。为了进一步提高效率，根据五子棋博弈的特性，在传统算法的基础上提出了局部搜索、优先值启发、限制广度等优化措施，提高了Alpha-Beta搜索算法的效率。虽然采用了以上的优化措施，但在实验中，搜索的层数被最终确定为3层，当层数继续增加时，每一步的搜索平均节点数将增加，并且可以明显感觉到延时。因此，在现在的基础上，如何进行进一步的优化将是今后的主要任务。参考文献1 Shannon C E. Programming a Computer for Playing ChessJ.Philosophical Magazine, 1950, 41(314): 256-275.2 王永庆. 人工智能原理与方法M. 西安: 西安交通大学出版社,1998: 288-290.3 Russel