大家好，欢迎来到IT知识分享网。【编程开发】简单五子棋

【研究报告】简单五子棋 AI 设计

社会研讨课做的研究课题，有空了来完善一下算法吧，基础 \(\text{UI}\) 直接搬的 \(ckj\) 的，已获得本人允许。

【Github】

一：【探究目标】

学习、设计、部分实现一只基础五子棋 \(\text{AI}\)，调整参数并简单测试对弈能力（考虑最简单的无禁手五子棋）。

二：【设计算法】

算法核心问题：落子决策（择优）。

1.【暴力出奇迹】

“精确记忆”能力是计算机相较于人类的优势之一，自然引入“棋谱记录”。

(1).【全棋谱记忆】

在大小为 \(19\times 19\) 的棋盘上，每个格子有 “黑”、“白”、“无” 三种状态，共 \(3^{361}\) 种棋局状态，对于每种状态记录走法。

储存空间有限、算力不足，不具备可实践性。

(2).【部分棋谱记忆】

利用有限的储存空间和算力记录部分棋谱。

查找开局谱，使用优势走法到有限步数停止
中间局使用单步决策算法进行临场决策
根据残局谱，检测是否出现必胜局

2.【单步决策-落子估价】

开局和残局有棋谱参考，中间局则需“临场应变”。

每次落子前，扫描当前棋局，选择最优落点

何为最优？

设计“估价函数”，以当前棋局状态为参数，为可落子位置估计“落点价值”，择其大者

影响落点价值的因素构成？

【特殊情况】下回合必胜/败

【攻/防】攻防分数占比

【当前局面】根据连子点数给予不同分数

【\(^{*}\)全局估价】赢法数组（\(f_{(横、竖)}=2*19*(19-5+1)=570\)、\(g_{(斜)}=2*\sum_{k=5}^{19}(k-5+1)=240\)，总情况数：\(570+240=810\)）

【对手的价值盘】用相同的估价方法计算对手的价值盘，提前断绝对方的优势落点

3.【预言决策-对抗搜索】

(1).【深度搜索】

【Min-Max 搜索算法】

分数从终点往起点方向累加（叶节点为 \(0\)），我方落子加正分，对方落子加负分，我方希望最后总分最大，对方希望总分最小。

\(\text{findmax}\) 层：\(s(x)=\max\{s(y)+v(x,y)|y\in son(x)\}\)

\(\text{findmin}\) 层：\(s(x)=\min\{s(y)-v(x,y)|y\in son(x)\}\)

两者相互递归调用。

(2).【算法优化】

【Alpha-beta 剪枝】

对于 \(\text{findmax}(x)\)：
设 \(son(x)=\{y_1,y_2…\}\)，当前检索到 \(y_k\) 的位置，设 \(alpha=\max\{s(y_i)+v(x,y_i)|1\leqslant i < k\}\)。
设 \(son(y_k)=\{z_1,z_2…\}\)，当前检索到 \(z_l\) 的位置，若 \(s(z_l)-v(y_k,z_l)\leqslant alpha-v(x,y_k)\)，则 \(s(y_k)=\min\{s(z)+v(y_k,z)|z\in son(y_k)\}\) \(\leqslant s(z_l)-v(y_k,z_l)\) \(\leqslant alpha-v(x,y_k)\)，而 \(alpha\) 在不断寻找更大的分数更新自己，所以 \(s(y_k)\) 必对 \(alpha\) 无影响，\(y_k\) 剩下的子节点 \(\{z_{l+1},…z_{m}\}\) 不必再检索。

对于 \(\text{findmin}\) 层类似。

//（完整代码1000+行，不作展示）
inline LL findmin(Re deep,LL alpha,Re op);//对手想让我尽量小
inline LL findmax(Re deep,LL beta,Re op) {//我想尽量大
	if(...)return -inf;//对手赢了
	if(...)return 0;//平局
	if(deep>MAX_deep)return 0;//搜索深度限制
	LL ans=-dfs_inf;//准备一个对于我来说的最坏情况（低分）
	for(i;;){//枚举状态
		luozi();//试探落子
		ans=max(ans,v+findmin(deep+1,ans-v,op^1));//搜下一层
		luozi_back();//撤销落子
		if(ans>=beta)return ans;//alpha-beta剪枝
	}
	return ans;
}

【棋盘局部搜索】不需要搜索棋盘上所有位置

**(3).【\(^{*}\)更好的落子估价-更多影响因素构成】**

【\(^{*}\)未来局面】

【\(^{*}\)空步预测】

4.【参数调整】

调整各种参数，不同参数下的机器相互对战。

【*估价函数】各种不同的连子局面，分别设置什么参数

【攻防比】我攻：我防：敌攻：敌防

【搜索参数】深度、广度

三：【对弈测试】

对弈参与者：

\(\text{AI}_{ckj}\)：由 \(ckj\) 同学提供，使用单步决策算法
\(\text{AI}_0\)：采用估价函数进行单步决策
\(\text{AI}_1\)：采用搜索算法进行预言决策
\(\text{Human}_1\)：为避免实力差距过大，粗略限制了思考时间

1.【调整参数】

(1).【攻防比】

【对弈对象】我方：\(\text{AI}_0\)，敌方：\(\text{AI}_{ckj}\)

【先手开局最佳成绩】我攻：我防：敌攻：敌防=2:4:3:1 胜：败：平=316:129:55

【后手开局最佳成绩】我攻：我防：敌攻：敌防=3:4:2:1 胜：败：平=271:165:64

(2).【搜索范围】

【对弈对象】

我方：\(\text{AI}_1\)（估价函数攻防比取 3:4:2:1），敌方：\(\text{AI}_{ckj}\)

【先手开局最佳成绩】deep=1,wide=9 胜：败：平=322:125:53

【后手开局最佳成绩】deep=2,wide=4 胜：败：平=342:83:75

2.【AI 对弈】

【对弈对象】我方：\(\text{AI}_1\)，敌方：\(\text{AI}_{0}\)

【先手开局】胜：败：平=125:49:326

【后手开局】胜：败：平=6:84:410

3.【人机对弈】

(1).单步决策

【对弈对象】我方：\(\text{AI}_0\)，敌方：\(\text{Human}_1\)

【先手开局】胜：败：平=11:9:0

【后手开局】胜：败：平=8:12:0

(2).预言决策

【对弈对象】我方：\(\text{AI}_1\)，敌方：\(\text{Human}_1\)

【先手开局】胜：败：平=16:4:0

【后手开局】胜：败：平=11:9:0

四：【数据分析】

调整参数时，更多地是在趋于”如何击败 \(\text{AI}_{ckj}\)“，所以先手最佳成绩为”deep=1″，后手最佳成绩为”deep=2″（\(\text{AI}_{ckj}\) 为单步决策算法）
\(\text{AI}_0\) 与 \(\text{AI}_1\) 对弈时两者差异不大、平局居多，推测原因为：估价函数参数设置对强度影响较大，而两者估价函数同源
人机对弈时，搜索预测明显比单步预测更强

五：【总结】

1.【对弈算法一般性】

简单棋类博弈均可采用“估价函数+对抗搜索”的方法设计 \(\text{AI}\)。对于局面状态数量较少的类型，可以一次搜索找到必胜策略；较多者则辅以“部分棋谱记忆”。
设计估价函数方案需要大量时间调整参数，“部分棋谱记忆”需要大量棋谱数据。

2.【算法改进空间】

录入开局谱、残局谱
与较强 \(\text{AI}\) 对弈，寻找最佳估价函数参数方案
优化复杂度

六：【致谢】

感谢 \(ckj\) 同学提供基础 \(\text{UI}\) 代码。

七：【参考资料】

五子棋入门级 AI 的设计与实现——Dylan (https://zhuanlan.zhihu.com/p/25650252)
【编程开发】简单五子棋 AI 设计
【编程开发】简单五子棋 AI 设计
对抗搜索与 Alpha-Beta 剪枝——皎月半撒花 (https://www.luogu.com.cn/blog/pks-LOVING/zhun-bei-tou-ri-bao-di-fou-qi-yan-di-blog)
博弈五子棋（人机对战）——ckj (https://codebus.cn/kevin/wuziqi)

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/33076.html

【编程开发】简单五子棋 AI 设计