背景：
从三月份到现在也自学小一年了。今年的目标本来是搞懂阿法狗怎么回事。但是，期间被很多东西所吸引，比如自然语言处理、神经网络翻译、Cambridge data、文本情感分析。回顾下今年过得很充实，也收获很多。虽然还是时不时地拖更，但是也是因为公众号的存在，让懒散的我觉得我有一种义务感，也行成了一种学习的动力。不过，对于最初的目标还是没有啥进展。当初也是完全因为Alphago的惊艳使得我踏上自学的路程。开启本系列也是为了重拾初心，一方面督促自己学习，另一方面希望能与大家分享我自学过程中的收获。并且由于我自己没有技术、数学、编程背景，所以可能会更贴近及了解大家的疑惑。
Why Minimax
AlphaGo诞生于2016年度，它诞生的一个巨大意义在于用计算机成功的战胜了人类围棋。AlphaGo诞生也很大程度上推动了AI的火爆。而围棋之前一直被认为是不可战胜的。而早在1997年IBM的Deep Blue 就已经在国际象棋项目打败了国际象棋大师。电脑掌握国际象棋与围棋的时间居然相隔了近20年。那么Deep Blue为什么不能在围棋上胜出呢？ AlphaGo 与 Deep Blue的差异在哪里呢？
所以觉得从Deep Blue 的核心算法学习开始学习，从Deep Blue来开启Toward AlphaGo系列更容易被接受。
而Deep Blue的核心算法是 Minimax，而我会用井字棋来讲述Minimax算法。此篇文章的图片和算法描述部分大部分来自于Toward DataScience
井字棋的英文名字是Tic Tac Toe，其规则很简单，就是横、竖、斜 都是同样的图案方获胜。并且井字棋是回合制的
Minimax&Tic Tac Toe
这个游戏中分为两方，X和O。假设我方为X。
如上图所示，假设我们当前的状态为0.0，我们有三种选择的可能（1.0，1.1，1.2）
1.0状态下我方获胜（+1）；
1.1 给了对手方两个可能的选择（2.0，2.1）。 其中2.0状态下，对方直接获胜，所以对于我方来说是落败（-1）；其中2.1后只有一种可能3.0，其状态下我方获胜（+1）
1.2 给了对手方两种可能（2.2，2.3），其中2.2对方获胜，我方落败（-1）；其中2.3只有一种可能性就是3.1，我方获胜（+1）
那么我们怎么用Minimax来理解和解决这种状态呢？
下棋最重要的是关注未来趋势的变化，当然井字棋没那么复杂，因为变化不多。那么我用上图中最简单的一个例子来说明。
比如上图中的状态2.3 之后只有一种可能性就是状态3.1。而状态3.1是X方必赢的局面，那么可以说明状态2.3也是X方必赢的局面（因为之后只有一种可能性）。那这就是一种胜负判断的反向传递的过程。你走到2.3，你就能知道X方是要必赢的局来。那么如果3.1是+1分，那么2.3也相应的是+1分；
但是很多状态下并不是像2.3一样接下来只有一种可能性。对于多种可能性怎么样去做分数的反向传递呢？这里就要讲到Minimax的思想了。
首先，井字棋是一种双方回合制的游戏，那么假设X获胜是 正数分；O方获胜是负数分；
那么，每一层的走向其实取决于下棋方，比如我在状态0.0是选择1.0，1.1，还是1.2呢？ 这取决于X方。那么自然他就会选择正数。比如，在状态0.0肯定车选择1.0咯。
结果，minimax就能解决从 1.0，1.1，1.2 反向传递到0.0的选择。同样的道理，那么也能将分数从3传到2，2传到1.
Minimax 思考
通过上一部分，我们知道了Minimax是通过将分数反向传递的过程，并且假设对方也采用最优解，从而能够对未来的走向做出判断。但是，我最初看到这个方法时，有几个疑问与大家分享：
Q1. Minimax在分数反向传递的过程种有一个前提，就是你构建了整个未来的Game Tree，即你已经算出来了未来所有的可能，从而能进行反向传递。对于井字棋这种简单的游戏（3⁹ = 196839 种可能）可能行得通，对于国际象棋是行不通的；
Q2. 另外，井字棋是将确定的胜负反向传递回去。但是对于象棋来说，可能要50回合才能分胜负，再叠加上50个回合的变化，是没办法算出来的。
对于这些问题，我看了一些文章。大概有两个解释：
A1. 对于Minimax有一种优化的方法，alpha-beta pruning。其大概的思路就是，比如你个人下棋的时候，对于那种送车的棋是不会去下的。所以这也可能减少计算这种无谓的可能性，这个将在下一篇介绍；
A2. 对于井字棋是将最终胜负作为分数来计算。但是，其实可以有其他的方法。比如，我们对于状态的评分可以改为车100分，马50分，兵10分。那么这样我们就能计算任何状态下的分数来。举个例子，你知道如果下某部棋，你会比对方少一个车，那么就应该尽量避免这种选择；
另外，也能通过控制层数来限制计算量。比如我们只需要计算5层，我能够大概肯定在5步之后，我能获得优势，比如比对方多一个马。
当然对于棋局状态的评分，并不能完全依靠子的数量来定，位子也很重要。后续如果讲到Chess Minimax AI，我会再找找资料。
总结
本期作为Toward AlphaGo的开篇，也是从Deep Blue的Minimax学起。看完以上部分大家也能看出来，其实Minimax还是属于Brutal Force强搜，构建一个完成的Game Tree。这个在围棋上应用肯定效果不佳。不过对于井字棋绰绰有余。下面是Github上一个Minimax在Tic Tac Toe的游戏，感兴趣的朋友可以尝试下。https://github.com/Cledersonbc/tic-tac-toe-minimax
閱讀更多 繁林林與機器學習 的文章
