五子棋AI教程第二版一:前言
lihongxun945 opened this issue · 34 comments
为什么出第二版
在 2016年2月的时候,我写了第一版的五子棋AI教程。当时是边写代码边写博客,因此出现了一些理解上有偏差的地方,以及文章中的代码片段和最终的代码有很多不一致的地方。经过两年多的时间,断断续续更新了好多次代码,电脑的棋力更强了,我对AI的理解也更深入了,期间也学习了一些神经网络的知识。因此,我就打算把陈旧的教程完整的更新一遍,主要目的是更新其中的一些错误,以及加入一些新的知识。因为这是我已经完成了代码后写的,所以质量会比之前一边摸索一遍写要高出很多。无论你有没有看过我的第一版的教程,都推荐你看看这个新版教程。
第一版教程的地址:https://blog.csdn.net/lihongxun945/article/category/6089493
本文章的所有代码都是开源的,代码地址: https://github.com/lihongxun945/gobang
我的五子棋AI在线地址,任何现代浏览器打开地址就可以玩: http://gobang.light7.cn/
教程大纲
这篇教程主要会讲解如下几个方面:
- 博弈算法基础知识
- 局势评估
- 极小化极大值搜索
- Alpha-Beta 剪枝
- 迭代加深
- Zobrist缓存
- 启发式评估函数
- 算杀
- 单元测试
- 速度优化
大部分内容在旧版的教程都有涉及,速度优化
这一章是之前没有的,而且这是掌握了基本算法之后,最重要的技能,也是最耗时的地方,我知道很多AI的设计者都是把大部分时间花在了性能优化上。
我能学习到什么知识?
读完这个系列之后,你能掌握棋类AI设计的所有基础知识,虽然本文是以五子棋为例,但是目前除了围棋之外的所有棋类几乎都可以用这个算法来实现,比如常见的象棋、黑白棋、跳棋等。至于围棋为什么不能用本文的算法来实现(或者说只用传统的搜索算法棋力会非常不理想),在下一篇文章会详细解读。
这里用的算法都是非常标准的,非常国际化的算法,并非本人原创,而是经过了几十年的发展,由很多大神发明的算法。所以不用担心学到了“奇怪的,野生的”算法,你在本教程中学到的都是可以让你受益终身的知识,不仅是AI,甚至不仅是博弈。
这是一篇基于传统搜索算法实现的AI教程,并不会详细的讲解神经网络的实现。不过如果你想学习神经网络的AI设计,我强烈建议你依然要完整的弄懂传统的搜索实现。因为目前包括AlphaGO在内的AI使用的是 搜索 + 神经网络 的结合技术。
这个AI的棋力如何
如果你对五子棋有一些研究,强烈建议你和电脑对战几局来体会电脑的棋力。个人并不是一个五子棋高玩,通过和身边以及网络上一些小伙伴的对战结果来看,这个AI已经能战胜大部分业余玩家。专业一点来说,AI的搜索深度是 8~10
层,如果没有特殊的优化技巧,这个深度已经达到了一个比较高的水平。
关于编程语言的问题
如你所见,我是使用JavaScript来实现的,并不是因为JS适合,相反,JS并不擅长进行CPU密集型的计算。只是因为本人是一个专业的前端工程师,所以理所当然选择了JS。相信如果同样的代码使用C语言实现,会大幅提升电脑的计算速度,可能能带来明显的棋力提升。
因为AI算法和浏览器环境无关,源码中的AI模块可以在浏览器和NodeJS中都能运行。如果你不懂JS,也完全不用担心。首先,JS是一个C风格的,非常容易读懂非常容易学习的语言。其次,文章中会很详细的讲解算法的实现原理,即使不参考代码你也完全可以实现一个自己的AI。
当然如果你希望能fork我的项目,并做一些改进,并且你不是一个前端工程师,那么会比较麻烦些。因为这个项目使用了一些目前为止比较先进的前端技术,包括:Vue, Webpack, Web Worker等。因为前端知识的迅速变化,以及前端知识体系的复杂性,不建议非前端工程师去阅读除AI模块外的代码。在后面的文章你会知道这个项目的解构,以及每个模块的作用。
这个项目是完全开源的
在第一版的教程中,有人问是不是github上缺少部分源码。这个我可以肯定的告诉大家,所有代码都在github上开源。之前有部分代码找不到的原因是,后来经过了代码重构,在旧的章节中提到的一些模块可能被移动到其他地方,导致找不到代码。不过请放心,在新版本中不会发生这种情况。
如果你感激作者的工作,希望能做一些回报,那么你可以:
- 把你发现的Bug报告给我
- 通过 pull request 提交你的代码
- 给我点
star
- 告诉身边的小伙伴
关于作者 言川
前端工程师一枚,我的博客地址: https://github.com/lihongxun945/myblog
小哥,有没有兴趣做成小程序版本的?可以帮你优化下界面,我微信 lu6239 ~
@hisuley 感谢,目前没有推出小程序版的想法
建议每篇文章加一个下一篇的链接。
@yough3rt 感谢建议,已经加上了 😄
感谢无私分享,非常感谢通用电气的大神 😄
当初看了博主的第一版,受益匪浅,磕磕碰碰敲完了自己的AI,现在过来继续学习,给博主点赞 :D
受益匪浅,但是感觉ai的棋里还是不行啊,本身我五子棋还是可以的,业务玩家里算厉害了,跟我下有赢有输,比其它的ai强。还有觉得这个下棋太死,都是相同的套路,如果赢了一局按照步骤走还是一样会赢。另外我下着发现了软件一个很简单的失误,才走了十来个子就已经犯了低级错误。好希望能有个像高手人脑一般棋力的ai。
学生党表示感谢2333
666666
专门注册来给作者点赞的!
教程思路清晰、深入浅出,读后觉得受益匪浅!
不过可以看出作者下五子棋应该不怎么样(嘿嘿),所以这个AI的棋力还有待提高。
尤其是作者对算杀比较轻视,所以AI有时候连四三都看不到……
补充一下:
五子棋是一种瞬间决出胜负的游戏,任何时候只要有杀了就赶紧干掉对方结束游戏了,不需要考虑其他任何东西。所以其实应该任何时候都首先算杀,能杀就开杀,不能杀就算对方有没有杀,有的话就必须防守,没有的话才是自己做棋,只有最后这种情况才适合用评分的方式选点。
还有作者说"一般在算杀的时候,我们优先进行 VCT,没有找到结果的时候再进行 VCF",这个是不对的。首先肯定搜VCF,这个是最简单也最确定无疑的,对方没有任何选择,只管搜自己的冲四就行;VCT则对方会有至少两种不同的应对,所以会麻烦一些。所以我觉得应该是己方VCF-对方VCF-己方VCT-对方VCT这样的计算顺序。
在有杀之前人下棋是靠感觉和记定式,跟计算机不一样,但在算杀方面计算机和人的思路是一样的,而且计算机明显比人厉害得多。
不厉害啊 我下第一把就赢了。。
你好,非常感谢你的分享,问一下,这份源码在本机运行的话,平均一步需要多长时间?
感谢分享
呼吁大家,千万别看这篇博客,讲解alpha-beta剪枝、启发式排序,完全是错的。
@weiziyoung 感谢指正,已经更新了。
另外不是完全错误,是其中对剪枝示例的解释有误:smile:
@weiziyoung 感谢指正,已经更新了。
另外不是完全错误,是其中对剪枝示例的解释有误😄
启发式排序也是错的,在max中,需要将结点由大到小排序,而不是从小到大,谢谢。
@weiziyoung 并没有看到我有这样的描述,是在启发式评估函数那一篇么?
马克一下,多谢大神!
以前没注意到github上还有这个,简单试了几局,发现楼主严重夸大了事实。该ai棋力能达到业余6~7级左右,与专业初段还有相当大的距离。应该只是一个简单的算法demo,既缺乏战术上的算法,更别提战略上的算法了。
感谢教导!!第一次接触五子棋算法,受益匪浅,我只做到了4层。。速度还需要优化。。无论如何感谢作者分享,好人一生平安~
我下载了您得项目,解压了,然后怎么运行呀,小萌新求教
我下载了您得项目,解压了,然后怎么运行呀,小萌新求教
yarn serve 本地启动。
或者你切换到 build
分支,直接用dist目录作为静态文件根目录启动服务器即可
您好,非常感谢您的教程,我发现了一个bug,如果我执后手,在输掉后重开一局会直接重现上一局输掉的情况(这里不贴图了,只要后手输掉就会出现)
这ai好像不怎么滴啊,我没怎么学五子棋乱杀它,它黑下不过我白,白下不过我黑
博主,还在吗,请问github上的代码是最新的吗?,代码中的注释是怎么回事啊
谢学长
兄弟,可以的,很有用!
代码我就偷走了👻!