week08

第八周 学习笔记

本周作业

1. 红绿灯

打开：traffic light

使用 async await 实现

2. Tic Tac Toe

打开：Tic Tac Toe

修改 N 棋子数，COLUMN 棋盘格子数，可以修改大小

例如：N 为 5，COLUMN 为 15 可以实现，五子棋，但是 bestChoice 使用递归，会导致溢出（N 为 4，就会溢出）

3. Gobang 五子棋 （未完成）

打开：GoBang

使用 最小最大博弈算法 评估分数，选取最大的数值

总结

指数级的可怕

本周没想到会突然变成一个游戏的编程，井字棋的算法异常简单，直接一个递归算到底。

然后照葫芦画瓢，写了个五子棋的，为了可以自由适配 各种棋子和棋盘的数量，抽象了 N 和 COLUMN，然后检查胜负，willWin 都是自适应。

但是跑 beshChoice 立即卡死。把棋盘缩小，测试了 5x5 的棋盘，我的电脑都会卡死。

感觉很神奇，感觉就加了一两个格子而已，然后搜索了一下棋类的复杂度：

5x5 的棋盘有，3^5x5 种可能，比 3x3 的棋盘：3^3x3 足足大了 4000 万倍 ！！！

就算是 4x4 的棋盘，3^4x4 也比 3^3x3 大了 4万倍 ！

只是增加几个格子，计算量是指数级上升，以前知道这种很难算，只是没想到会差别这么大。

更不用说真正的五子棋：3^15x15，简直是一个天文数字，根本不可能算的出来。

切身体会一下之后，再想想 围棋有300次方的可能性，现在想想 alpha GO 真的厉害。

寻找解决方案

穷举无法解决，只能用别的方式了，作为一个棋类 AI 的小白，选了一个入门：最小最大博弈算法，而且只有一层，看了很多资料，看上去都非常的简单，但实际要写起来和理解起来也不是那么容易。

花了几个小时，写了一个评估分数的函数，基本可以用，但还有些bug，就是自己准备要赢了，但是会去堵别人。

不过很弱，如果布一个双活三的局，稳赢。

如果要进一步提升 AI，还要加深度，但要加深度的话，计算量会指数级上升，因此还要考虑剪枝，启发式 等等优化，时间关系，这里没时间做了。

感想

前端训练营的例子都选的特别有针对性，井字棋做为入门，五子棋作为深入，这个拓展非常的好，指数级的爆炸增加，不得不去寻找其他的算法支撑。继续往深扩展的话，真的可以非常深，但深入之后，发现很多棋类相关的算法都可以涉及到，非常的有意思。