Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

五子棋AI教程第二版一:前言 #11

Open
lihongxun945 opened this issue Jul 16, 2018 · 37 comments
Open

五子棋AI教程第二版一:前言 #11

lihongxun945 opened this issue Jul 16, 2018 · 37 comments

Comments

@lihongxun945
Copy link
Owner

lihongxun945 commented Jul 16, 2018

为什么出第二版

在 2016年2月的时候,我写了第一版的五子棋AI教程。当时是边写代码边写博客,因此出现了一些理解上有偏差的地方,以及文章中的代码片段和最终的代码有很多不一致的地方。经过两年多的时间,断断续续更新了好多次代码,电脑的棋力更强了,我对AI的理解也更深入了,期间也学习了一些神经网络的知识。因此,我就打算把陈旧的教程完整的更新一遍,主要目的是更新其中的一些错误,以及加入一些新的知识。因为这是我已经完成了代码后写的,所以质量会比之前一边摸索一遍写要高出很多。无论你有没有看过我的第一版的教程,都推荐你看看这个新版教程。

第一版教程的地址:https://blog.csdn.net/lihongxun945/article/category/6089493

本文章的所有代码都是开源的,代码地址: https://github.com/lihongxun945/gobang

我的五子棋AI在线地址,任何现代浏览器打开地址就可以玩: http://gobang.light7.cn/

ss

教程大纲

这篇教程主要会讲解如下几个方面:

  1. 博弈算法基础知识
  2. 局势评估
  3. 极小化极大值搜索
  4. Alpha-Beta 剪枝
  5. 迭代加深
  6. Zobrist缓存
  7. 启发式评估函数
  8. 算杀
  9. 单元测试
  10. 速度优化

大部分内容在旧版的教程都有涉及,速度优化 这一章是之前没有的,而且这是掌握了基本算法之后,最重要的技能,也是最耗时的地方,我知道很多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

下一篇 五子棋AI设计教程第二版二:博弈算法的前世今生

@hisuley
Copy link

hisuley commented Jul 17, 2018

小哥,有没有兴趣做成小程序版本的?可以帮你优化下界面,我微信 lu6239 ~

@lihongxun945
Copy link
Owner Author

@hisuley 感谢,目前没有推出小程序版的想法

@yough3rt
Copy link

建议每篇文章加一个下一篇的链接。

@lihongxun945
Copy link
Owner Author

@yough3rt 感谢建议,已经加上了 😄

@erdong-fe
Copy link

感谢无私分享,非常感谢通用电气的大神 😄

@keyu-tian
Copy link

当初看了博主的第一版,受益匪浅,磕磕碰碰敲完了自己的AI,现在过来继续学习,给博主点赞 :D

@fengxiaojie
Copy link

受益匪浅,但是感觉ai的棋里还是不行啊,本身我五子棋还是可以的,业务玩家里算厉害了,跟我下有赢有输,比其它的ai强。还有觉得这个下棋太死,都是相同的套路,如果赢了一局按照步骤走还是一样会赢。另外我下着发现了软件一个很简单的失误,才走了十来个子就已经犯了低级错误。好希望能有个像高手人脑一般棋力的ai。

@JoeXu1997
Copy link

学生党表示感谢2333

@panco95
Copy link

panco95 commented Nov 12, 2018

666666

@juliusyork
Copy link

专门注册来给作者点赞的!
教程思路清晰、深入浅出,读后觉得受益匪浅!

不过可以看出作者下五子棋应该不怎么样(嘿嘿),所以这个AI的棋力还有待提高。
尤其是作者对算杀比较轻视,所以AI有时候连四三都看不到……

@juliusyork
Copy link

补充一下:

五子棋是一种瞬间决出胜负的游戏,任何时候只要有杀了就赶紧干掉对方结束游戏了,不需要考虑其他任何东西。所以其实应该任何时候都首先算杀,能杀就开杀,不能杀就算对方有没有杀,有的话就必须防守,没有的话才是自己做棋,只有最后这种情况才适合用评分的方式选点。

还有作者说"一般在算杀的时候,我们优先进行 VCT,没有找到结果的时候再进行 VCF",这个是不对的。首先肯定搜VCF,这个是最简单也最确定无疑的,对方没有任何选择,只管搜自己的冲四就行;VCT则对方会有至少两种不同的应对,所以会麻烦一些。所以我觉得应该是己方VCF-对方VCF-己方VCT-对方VCT这样的计算顺序。

在有杀之前人下棋是靠感觉和记定式,跟计算机不一样,但在算杀方面计算机和人的思路是一样的,而且计算机明显比人厉害得多。

@dongYzzz
Copy link

不厉害啊 我下第一把就赢了。。

@liqiniuniu
Copy link

你好,非常感谢你的分享,问一下,这份源码在本机运行的话,平均一步需要多长时间?

@ouyangcamel
Copy link

感谢分享

@Dentioner
Copy link

1
非常感谢你的教程。
这里我似乎遇到了一个bug,就是我方执白子,AI执黑子的时候,会出现这种情况,似乎在你的AI在搜索的时候额外落了一个子。

@weiziyoung
Copy link

呼吁大家,千万别看这篇博客,讲解alpha-beta剪枝、启发式排序,完全是错的。

@lihongxun945
Copy link
Owner Author

lihongxun945 commented Jan 7, 2019

@weiziyoung 感谢指正,已经更新了。
另外不是完全错误,是其中对剪枝示例的解释有误:smile:

@weiziyoung
Copy link

@weiziyoung 感谢指正,已经更新了。
另外不是完全错误,是其中对剪枝示例的解释有误😄

启发式排序也是错的,在max中,需要将结点由大到小排序,而不是从小到大,谢谢。

@lihongxun945
Copy link
Owner Author

@weiziyoung 并没有看到我有这样的描述,是在启发式评估函数那一篇么?

@weiziyoung
Copy link

weiziyoung commented Jan 8, 2019 via email

@name-used
Copy link

马克一下,多谢大神!

@2005czq
Copy link

2005czq commented Jun 8, 2019

非常感谢,看完文章受益匪浅,但是似乎平局(下满整个屏幕)的时候AI会卡住,也没有显示平局

@viogel4
Copy link

viogel4 commented Jul 12, 2019

以前没注意到github上还有这个,简单试了几局,发现楼主严重夸大了事实。该ai棋力能达到业余6~7级左右,与专业初段还有相当大的距离。应该只是一个简单的算法demo,既缺乏战术上的算法,更别提战略上的算法了。

@weiziyoung
Copy link

image
image
好多bug啊,你看我都五子连珠了你怎么还能下,然后我继续下到第六个字,你竟然还是能下,还把我下赢了。AI出老千不算啊哈哈哈

@jasonnima
Copy link

感谢教导!!第一次接触五子棋算法,受益匪浅,我只做到了4层。。速度还需要优化。。无论如何感谢作者分享,好人一生平安~

@ghost
Copy link

ghost commented Dec 6, 2020

我下载了您得项目,解压了,然后怎么运行呀,小萌新求教

@lihongxun945
Copy link
Owner Author

我下载了您得项目,解压了,然后怎么运行呀,小萌新求教

yarn serve 本地启动。
或者你切换到 build 分支,直接用dist目录作为静态文件根目录启动服务器即可

@ylzxztc
Copy link

ylzxztc commented Jan 2, 2021

发现有奇怪的问题啊
17 (电脑18)
19 (电脑20)
21 (电脑bug??? 22与6重合)

我下到第21步时候,电脑下的第22步与6步重合?

@King-ty
Copy link

King-ty commented Apr 27, 2021

您好,非常感谢您的教程,我发现了一个bug,如果我执后手,在输掉后重开一局会直接重现上一局输掉的情况(这里不贴图了,只要后手输掉就会出现)

@pickmoneyplease
Copy link

这ai好像不怎么滴啊,我没怎么学五子棋乱杀它,它黑下不过我白,白下不过我黑

@Sakura761
Copy link

博主,还在吗,请问github上的代码是最新的吗?,代码中的注释是怎么回事啊

@nonusx
Copy link

nonusx commented Dec 3, 2022

image image 好多bug啊,你看我都五子连珠了你怎么还能下,然后我继续下到第六个字,你竟然还是能下,还把我下赢了。AI出老千不算啊哈哈哈

按你的走法搞了一遍,真的出问题了哈哈

@uerytytieuri
Copy link

谢学长

@BytefishMedium
Copy link

兄弟,可以的,很有用!
代码我就偷走了👻!

@ViJayPeng
Copy link

ACF376296646D93C8CD2FF06FC1FCF70
大佬你好,想问一下这个v2和v3版本的棋力水平有差异吗?我试了好多次让他们两个互相下都是v2胜,但是v2的ai思考速度会不稳定,有时秒下有时候又要好几秒才反应,而且发现v2的“困难”水平电脑不会下棋。在参考v2版本的代码写的ai在搜索深度为8之后,在手机上运行也会出现卡住的现象,所以想了解一下v2和v3之间的差异

@lihongxun945
Copy link
Owner Author

@ViJayPeng 原理是一样的,不过V3修复了一些偶发的bug,电脑走棋会更加稳定,不容易犯低级错误。棋力上差距应该不会太大,谁胜出都正常。

@ViJayPeng
Copy link

@ViJayPeng 原理是一样的,不过V3修复了一些偶发的bug,电脑走棋会更加稳定,不容易犯低级错误。棋力上差距应该不会太大,谁胜出都正常。

感谢大佬回复,还有就是V2的演示网页上最高难度运行不了

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests