五子棋AI教程第二版一：前言
lihongxun945 opened this issue · 37 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这样的计算顺序。
在有杀之前人下棋是靠感觉和记定式，跟计算机不一样，但在算杀方面计算机和人的思路是一样的，而且计算机明显比人厉害得多。
不厉害啊 我下第一把就赢了。。
你好，非常感谢你的分享，问一下，这份源码在本机运行的话，平均一步需要多长时间？
感谢分享
非常感谢你的教程。
这里我似乎遇到了一个bug，就是我方执白子，AI执黑子的时候，会出现这种情况，似乎在你的AI在搜索的时候额外落了一个子。
呼吁大家，千万别看这篇博客，讲解alpha-beta剪枝、启发式排序，完全是错的。
@weiziyoung 感谢指正，已经更新了。
另外不是完全错误，是其中对剪枝示例的解释有误:smile:
@weiziyoung 感谢指正，已经更新了。
另外不是完全错误，是其中对剪枝示例的解释有误😄
启发式排序也是错的,在max中，需要将结点由大到小排序，而不是从小到大，谢谢。
@weiziyoung 并没有看到我有这样的描述，是在启发式评估函数那一篇么？
马克一下,多谢大神!
非常感谢，看完文章受益匪浅，但是似乎平局（下满整个屏幕）的时候AI会卡住，也没有显示平局
以前没注意到github上还有这个，简单试了几局，发现楼主严重夸大了事实。该ai棋力能达到业余6~7级左右，与专业初段还有相当大的距离。应该只是一个简单的算法demo，既缺乏战术上的算法，更别提战略上的算法了。
好多bug啊，你看我都五子连珠了你怎么还能下，然后我继续下到第六个字，你竟然还是能下，还把我下赢了。AI出老千不算啊哈哈哈
感谢教导！！第一次接触五子棋算法，受益匪浅，我只做到了4层。。速度还需要优化。。无论如何感谢作者分享，好人一生平安~
我下载了您得项目，解压了，然后怎么运行呀，小萌新求教
我下载了您得项目，解压了，然后怎么运行呀，小萌新求教
yarn serve 本地启动。
或者你切换到 build 分支，直接用dist目录作为静态文件根目录启动服务器即可
发现有奇怪的问题啊
我下到第21步时候，电脑下的第22步与6步重合？
您好，非常感谢您的教程，我发现了一个bug，如果我执后手，在输掉后重开一局会直接重现上一局输掉的情况（这里不贴图了，只要后手输掉就会出现）
这ai好像不怎么滴啊，我没怎么学五子棋乱杀它，它黑下不过我白，白下不过我黑
博主，还在吗，请问github上的代码是最新的吗？，代码中的注释是怎么回事啊
按你的走法搞了一遍，真的出问题了哈哈
谢学长
兄弟，可以的，很有用！
代码我就偷走了👻！
大佬你好，想问一下这个v2和v3版本的棋力水平有差异吗？我试了好多次让他们两个互相下都是v2胜，但是v2的ai思考速度会不稳定，有时秒下有时候又要好几秒才反应，而且发现v2的“困难”水平电脑不会下棋。在参考v2版本的代码写的ai在搜索深度为8之后，在手机上运行也会出现卡住的现象，所以想了解一下v2和v3之间的差异
@ViJayPeng 原理是一样的，不过V3修复了一些偶发的bug，电脑走棋会更加稳定，不容易犯低级错误。棋力上差距应该不会太大，谁胜出都正常。
@ViJayPeng 原理是一样的，不过V3修复了一些偶发的bug，电脑走棋会更加稳定，不容易犯低级错误。棋力上差距应该不会太大，谁胜出都正常。
感谢大佬回复，还有就是V2的演示网页上最高难度运行不了