人工智能课程项目报告
基于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
人工智能课程项目报告
图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 = beta
for place in possiblePlaces: chess[place] = enemy
wight = findMax(alpha, min, step-1) chess[place] = empty if wight < min: min = wight
2
人工智能课程项目报告
if min <= alpha: // alpha剪枝 return min return min
function findMax(alpha, beta, step) // 寻找当前棋局的最大估值 if step == 0:
return evaluate() max = alpha
for place in possiblePlaces: chess[place] = my
wight = findMin(max, beta, step-1) chess[place] = empty if wight > max: max = wight
if max >= beta: // beta剪枝 return max return max
function putOne(): alpha = - Infinity beta = Infinity max = -Infinity maxPlace = null
for place in possiblePlaces: chess[place] = my
wight = findMin(alpha, beta, step) chess[place] = empty if max < wight: max = wight
maxPlace = place chess[maxPlace] = my
在以上伪代码中，step记录搜索的深度，alpha为当前得到的最大值，beta为当前得到的最小值，my表示己方（AI方）棋子，enemy表示敌方棋子，empty表示空。 2.3 利用局部搜索对算法进行优化 在五子棋博弈的搜索中，所有空白位置都是合法的位置。对于大小为15x15的棋盘，传统算法中计算机每走一步都要遍历整个棋盘，这意味着搜索的节点数十分庞大。而根据五子棋的特点，通过仔细分析可以看出，在某个时刻，棋盘上很多位置都可以不用考虑，而只考虑已有棋子周围的局部棋盘。提取出局部棋盘后再进行搜索，可以大大提高算法的效率。 为了确定边界，设置变量x_max, x_min, y_max, y_min分别代表边界的最大最小坐标，在第一步落子时，对它们进行初始化，假设棋盘大小为15x15，第一步落子位置为(x, y)，则初始化过程为：
if x-1 >= 0:
x_min = x - 1 if x+1 <= 15: x_max = x + 1
3
人工智能课程项目报告
if y-1 >= 0:
y_min = y - 1 if y+1 <= 15: y_max = y + 1
在进行每一步落子到(x, y)位置后，需要通过resetMaxMin函数更新边界值：
function resetMaxMin(x, y):
if x-1 >= 0:
x_min = min(x_min < x–1)
if x+1 <= 15:
x_max = max(x_max > x+1)
if y-1 >= 0:
y_min = min(y_min < y-1)
if y+1 <= 15:
y_max = max(y_max > y+1)
在上述伪代码中，默认棋盘大小为15x15，扩展边界大小为1，在实际应用中，可以根据实际情况更改扩充边界值。
2.4 通过优先值启发优化算法
由Alpha-Beta搜索算法原理可知，搜索的广度决定每一层所扩展的节点数，而且越早搜索到较优者，那么剪枝的效率越高。对此，可以优先搜索一层，对这一层的节点的值进行排序，选取对己方最有利的节点作为最优扩展节点。
仅对第一层节点进行搜索，虽然可能不是在多层搜索的基础上的最佳位置，但是它往往是一个较优的位置。通过对第一层扩展节点进行最优值排序，优先选择最优节点进行扩展，可以使Alpha-Beta剪枝尽早发生，提高Alpha-Beta剪枝的效率。 2.5 限制搜索广度
在进行优先值启发排序后，会发现大部分优先值低的节点会在之后的Alpha-Beta剪枝中被剪去，而且即使在多层搜索之后，最优节点也往往在头几个进行一层搜索得到的最优节点中。基于以上分析，在扩展节点时，可以只选择头几个进行一层搜索的优先值高的节点，这样限制了搜索的广度，提高了剪枝算法的效率。
3 实验或测试结果
通过实际测试，可以看出算法可以正确运行。如图3所示，当人持黑棋先行，算法对白棋的落子位置进行搜索，剪枝节点与预期吻合，算法最后给出的落子位置符合算法逻辑。
4
人工智能课程项目报告
图3 算法执行部分结果测试
4 结论
本文探讨了针对五子棋游戏的Alpah-Beta算法，通过Alpha-Beta搜索实现了人机博弈的AI部分。为了进一步提高效率，根据五子棋博弈的特性，在传统算法的基础上提出了局部搜索、优先值启发、限制广度等优化措施，提高了Alpha-Beta搜索算法的效率。虽然采用了以上的优化措施，但在实验中，搜索的层数被最终确定为3层，当层数继续增加时，每一步的搜索平均节点数将增加，并且可以明显感觉到延时。因此，在现在的基础上，如何进行进一步的优化将是今后的主要任务。
参考文献
[1] Shannon C E. Programming a Computer for Playing Chess[J].Philosophical Magazine, 1950, 41(314): 256-275.
[2] 王永庆. 人工智能原理与方法[M]. 西安: 西安交通大学出版社,1998: 288-290.
[3] Russell, Stuart J.; Norvig, Peter. Artificial Intelligence: A Modern Approach 3rd. Upper Saddle River, New Jersey: Pearson Education, Inc. 2010: 167. ISBN 0-13-604259-7
5
基于alphabeta算法的智能五子棋
