【博弈树MAX-MIN和α-β剪枝那些事】从零开始====五子棋制作的详细记录

mythqiu · 发表于 2022-10-25 00:12

我下不赢它。。。。。。。

mythqiu · 发表于 2022-10-25 00:14

#If VBA7 And Win64 Then
Private Declare PtrSafe Function timeGetTime Lib "winmm.dll" () As Long '调用WINDOWS的API
#Else
Private Declare Function timeGetTime Lib "winmm.dll" () As Long '调用WINDOWS的API
#End If
改这个适合64位excel

cjh-01 · 发表于 2022-10-25 20:03

thank you very much

王小雨830518 · 发表于 2022-10-26 22:21

mythqiu 发表于 2022-10-25 00:14
#If VBA7 And Win64 Then
Private Declare PtrSafe Function timeGetTime Lib "winmm.dll" () As Long '调 ...

又学到知识了，感谢测试，
下个版本我改成用Timer延时，应该就没有这个问题了
我是小白，那会儿不知道VBA自带Timer

mythqiu · 发表于 2022-10-27 00:38

王小雨830518 发表于 2022-10-26 22:21
又学到知识了，感谢测试，
下个版本我改成用Timer延时，应该就没有这个问题了
我是小白，那会儿不知道V ...

代码同时兼容了64和32OFFICE。ai计算有时长达数秒，应该有优化空间。不过我是完全看不懂AI代码

王小雨830518 · 发表于 2022-11-24 21:57

五子棋_Beta1.30.rar (153.86 KB, 下载次数: 23)

这是接触VBA学的头一个完整的代码，历时半个月终于算完成了吧
自己想实现的功能基本实现了，如果计算机执黑反正我一不小心就会输掉
3岁（预判4个棋子，深度4层）的AI执黑基本完胜不搜索的基础AI了。

整个代码的一点一点写下感觉涵盖了太多的细节
太多值得思考的知识点，不实实在在自己写一写，真的很难真正理解
卡的最久的还是决策树的建立，如何把MAXMIN算法和α-β剪枝融入递归
但是写到最后发现最难的还是局势评估函数
即每个叶子节点对局势的评估打分
评估函数的水平直接决定了AI的质量，悲哀
好在这也不是咱学习VBA的初衷
AI和自动化办公本质上差异并不大，安慰自己吧
或许哪天回头看看，这些代码肯定是漏洞百出
但“纸上得来终觉浅，绝知此事要躬行”就是收获吧

这楼把不好理解的东西做个总结记录

1、博弈树建立
首先非常感谢山菊花版主的帮助
其实说白了，这个AI算法就是一个树形结构的递归深度搜索
每个节点的孩子和父节点都是对方玩家
所有的节点被分为极大值（我方）节点和极小值（对方）节点
个人感觉是学习递归的非常好的一个例子
可惜弱智的我还是不是很懂，说几个关键字把

栈（理解递归思想的前提）
二叉树的先序、后序
传递的变量
节点概念

2、MINMAX算法

该算法需要满足零和博弈，初略的解释就是若有两个玩家进行游戏
如果其中一方得到利益那么另一方就会失去利益
游戏利益的总和为0（某些情况下为常数）
因此，零和的约束条件也使得该算法在很多游戏中图体现出很好的效果
比如大多数的棋类游戏。
以上来自百度百科

网上有很多讲这个的，关键点在于无论MAX还是MIN
它的选择都是相对于子节点
并且它的选择是从叶子节点开始，自下而上最终到根节点
这个理解起来不难，见下图：

3、α-β剪枝
同样这个网上好多讲的，感觉很多都是断章取义的
包括各种教授的视频（讲的真的云里雾里......一言难尽）
很多说法都这样单独介绍α剪枝、β剪枝，其实个人理解这两个不能分开的
我们只说实现的过程：

首先子节点继承父节点α、β的数值
如果节点的父节点α>β，发生剪枝
如果是MAX节点，根据子节点更新α的值
如果是MIN节点，根据子节点更新β的值

就这点事，没了（盗图一张）
αβ剪枝.jpg

cjh-01 · 发表于 2023-5-7 20:02

开启新思路，谢谢

		自动登录	找回密码
密码			免费注册

[分享] 【博弈树MAX-MIN和α-β剪枝那些事】从零开始====五子棋制作的详细记录