基于“博弈树”的AI五子棋
python讨论qq群：996113038
代码及相关资源获取：
后台回复：五子棋，获取源代码
开发工具：
python3.6.4。
需要安装的库：graphics，time。
可以联系群主安装
效果演示：
基本原理
我们用到了博弈论的算法，下面我简单介绍一下博弈树：
博弈树类似于状态图和问题求解搜索中使用的搜索树。在AI五子棋中，博弈树的节点对应于某一个器具，其分支表示走一步棋。根部对应于开始位置。其叶节点表示对弈到此处结束。竞赛的结果可以是赢，输，平。下面就是一棵典型的博弈树：
如果按照暴力算法，将一局五子棋的所有可能性全部列举出来，理论上讲肯定是可以赢的。但是这样会耗费巨量的计算力。所以枚举法是不可行的。剪枝就是减去一些完全没有意义的走法。大大降低计算量。
部分代码
我们需要设定一个目标函数，计算未来几步怎么走能够使这个目标函数最大化。这样我们就需要对每一种走法的“分”做一个评估，这里的“分”代表的是这个走法产生的棋局优势。
首先我们要写函数评估局势，下面是一个例子：这是判断四个方向里，活四局势的个数。
#该点四个方向里(即v不区分正负)，活四局势的个数 def liveFour(x,y): key=num[x][y]; s=0 for u in range(4): samekey=1 samekey,i=numofSamekey(x,y,u,1,key,samekey) if(not downOk(x+dx[u]*i,y+dy[u]*i)): continue samekey,i=numofSamekey(x,y,u,-1,key,samekey) if(not downOk(x+dx[u]*i,y+dy[u]*i)): continue if(samekey==4): s=s+1 return s我们还要写出：冲四局势个数，四个方向里活三，以及八个方向里断三的个数，该点在四个方向里，是否有六子或以上连线，统计在u方向上，和key值相同的点的个数，即和key同色的连子个数。
估价函数基本规则如下：
我们不断让机器的分数越来越高就行了。
参考资料：
论文：《基于博弈树的五子棋算法研究》---罗景，叶俊民，赵良等
参考来源：https://github.com/hfq0219/wuziqi
扫描下方二维码，关注公众号
作者：剑心211
