博弈树之我见

想必各位都听说过人工智能,但未必听说过博弈树.其实博弈树属于比较传统的一种人工智能算法,其一般被运用到对弈的游戏中.通过对棋局作估值,采用极大极小搜索的办法,近似的搜索出最佳的棋局方式,进而模仿人类的下棋方式.
碰巧课设需要设计一个棋类的对弈系统,就刚好将这个算法稍稍了解并记录了下来.

估值函数

使用博弈树的前提是少不了设置估值函数,估值函数指的是,对应当前棋局,你觉得好不好?有多好?将这个设成一个具体的量值.那么就五子棋来说如何判断一个棋局好不好呢?方法如下:
首先是对棋型我们需要提供一个对应的分值.例如,在五子棋中,五个子相连称为“长连”,将其分值设为100000,对于四子相连且没有被封堵的,称为“活四”,对“活四”我们也赋予一个分值1000…当设定完以后,我们采用遍历的方式,搜集整个棋盘的横竖正斜负斜的所有的信息,组合成字符串.通过正则匹配的手段判断是否存在对应的棋型,将分值相加做到评估局面的效果

正则匹配对应的棋型:

如何择点下棋

在有了决策树以后,我们是可以开始下棋了,但是我们想一想,一个棋盘有15*15个点,我们如何去选择一些最佳的点呢?我采取的方法是用对已经下的点周围下的决策,来选取点.具体的策略如下图:

这样既可以保证当前的择点有效,同时也能够让搜索最小化降低时间复杂度.

决策树使用

关于决策树,同我们数据结构中学的树其实类似的你不废话么 唯一不同的是,由于决策树模拟的是双方轮流下棋的决策,因此,需要采用极大极小循环决策,即在己方情况我想获得最大的分值,在对手下的时候我想让他尽可能下的烂.基于这个我们写出了下面的代码:

public float Alpha_Beta(int depth,String color,String anothercolor,Vector<Integer> points,float alpha,float beta) {
   
		/*进行alpha和beta剪枝以及递归的过程*/
		if (depth == MaxDepth) {
   
			/*如果到达了递归深度,直接返回当前局面的值就好了*/
			return Counting_Points(color,anothercolor)-2*Counting_Points(anothercolor,color);
		}
		if(depth%2 == 0) {
   
			for(int k=0;k<points.size()-1;k+=2) {
   
				int i=points.get(k);
				int j=points.get(k+1);
				board[i][j] = super.color;				
				Vector<Integer> newpoints = Found_Points();
				float s = Alpha_Beta(depth+1,anothercolor, color, newpoints,alpha,beta);
				alpha = Math.max(s, alpha);
				board[i][j] = 0;
				if(alpha>=beta) {
   
					/*如果该节点的下确界大于父节点的上确界,则直接剪枝*/
					return alpha;
				}
			}
			return alpha;
		}else {
   
			for(int k=0;k<points.size()-1;k+=2) {
   
				int i=points.get(k);
				int j=points.get(k+1);
				board[i][j] = super.anothercolor;
				Vector<Integer> newpoints = Found_Points();
				float s =  Alpha_Beta(depth+1,anothercolor, color, newpoints,alpha,beta);
				beta = Math.min(s, beta);
				board[i][j] = 0;
				if (alpha>=beta) {
   
					/*如果节点的上确界小于父节点的下确界,则直接剪枝*/
					return beta;
				}
			}
			return beta;
		}
	}

在上面的代码注释中我们可以看到,我使用了剪枝的操作,那么剪枝又是什么呢?

Alpha-Beta剪枝

剪枝其实是为了加快不必要的搜索,由于是交踢采用极大极小决策的树,必定存在着情况如:1.父节点的极小值大于子节点的极大值,2.父节点的极小值大于子节点的极大值.因此这些搜索就没有必要接着进行下去了,即已经可以采取剪枝的策略了.如下图就是一个剪枝的实例:(图片出自转载)


图中的B节点的极小值已经大于C节点的第一个检索值,即存在min>max的情况,故直接搜索了下一棵树

总结

至此,基本的博弈树算法已经介绍完了,对于博弈树的算法优化其实还有很多可用,例如我从论文中看到的使用些许棋谱实现的启发式搜索,通过载入一些已经存在的棋局实现对应的局面,可以加强Ai的智能,其余的优化算法各位可以看我引用的那些论文和博客,都是确实对优化和理解算法实用的干货.
最后,我个人的系统原码也已经放在了我的GitHub上,各位有兴趣可以下载参考,只是记得给我点个star就很好啦.
最后,还得感谢我的组员实现的前端界面和数据库,虽然算法很重要但没有我的队友白凤,夜默,罗同学,也不可能有这个完整的系统.

GitHub原码
基于α-β剪枝算法的智能五子棋
阿尔法α-贝塔β剪枝
[1] 程宇, 雷小锋. 五子棋中Alpha-Beta搜索算法的研究与改进[J]. 计算机工程, 2012, 38(17):186-188.
[2] 张明亮, 吴俊, 李凡长. 五子棋机器博弈系统评估函数的设计[J]. 计算机应用, 2012, 32(07):1969-1972.
[3] 严小卫, 莫建文. 智能五子棋的设计与实现[J]. 广西师范大学学报(自然科学版), 1999(4):11-14.
[4] 王长飞, 蔡强, 李海生. 智能五子棋算法的设计实现[J]. 系统仿真学报, 2009(04):132-135.