Java咖啡馆(13): 终结者

　　通过各种试验，科学家发现自然界中许多被认为聪明的动物的聪明仍然无法与人类幼儿时期的相比拟。而天天面对的计算机，虽然使得人类的生产力发生翻天覆地变化，但冰冷的它，是否有一天能够模拟甚至达到人类的聪明呢？

计算机的聪明

　　如何定义人类的聪明，即使最睿智的哲学家也只能望洋兴叹。不过，我们不妨由浅入深。假如一向自信十足的你在网上与网友对弈楚汉时，碰到一个与你杀得难解难分甚至略胜一筹的高手，当你英雄惜英雄，邀请那高人红茶馆小聚一番，却被告知那是某公司象棋程序2.0而不是一个真人在下棋时，你一定会由衷发出赞叹——计算机真是聪明啊！

　　所以，从休闲的棋牌游戏入手，是探究计算机聪明有益的第一步。实际上，早在1950年，Claude Shannon和Alan Turing已编写过下棋的程序，前者是信息论的创始人，而以后者名字命名的图灵奖更是计算机科学中的最高奖项。

　　当时的工作是基于两个玩家互相博弈的基础上的。计算机科学家们把棋局的状态看作结点，把从当前棋局走一步而变化出来的新的棋局当做结点的子结点，假如把原始棋局看作树根，就可以把棋局的所有变化演化成一棵倒置的树来，我们称之为游戏树。这样，便可以从最底部的结果来倒推，从而决定走对自己最有利的一步棋。

　　游戏树的想法很直观，但这棵树实在太庞大了。比如西洋跳棋，完整的游戏树将达到10的40次方个结点的量级，假设一台计算机每秒能处理300个结点，将会花费10的21次方个世纪来构建这棵游戏树！而国际象棋更加复杂，按照每步平均35个可供选择的下法，平均每个玩家下50步棋，国际象棋的游戏树将会达到35的100次方的量级。盛行于中日韩三国的围棋更是比国际象棋复杂得多。

　　由于时间限制而游戏树几近无限，我们的可行方法不外乎两个字——砍树，也就是在游戏树的构建过程中只计算那些感爱好的结点，而不管那些不怎么有意思的结点，结果相当于只生成了部分的游戏树，这样便可以把计算时间控制住。仔细想想，下棋也是这样的，当别人将军的时，你自然只考虑如何解围，而不是如何去吃对方的子。当然，如何砍树并且砍得好，那是一门大学问。


教计算机玩Tic-Tac-Toe

　　相对于西洋跳棋、国际象棋和围棋，我们的Tic-Tac-Toe游戏可要简单得多，虽然手动构造游戏树也不是不可行，但那样的做法实在太逊了啦！我们要砍树！

　　下面我们手动模拟计算机执大叉在开局时进行MiniMax算法的演算过程，让大家有个直观的理解。其中，MiniMax算法的估计函数就是上文介绍的，游戏树的深度为三层(见图2)。

　　最底层的结点的赋值都是根据估计函数得到的。在Min层，每个值都是底层结点中值的最小值，这表示布满聪明的对手可能使自己落到的最窘迫的下场。当Min层生成以后，计算机自然知道Min最右边的哪个结点是最划算的，无论对手如何走，自己走正中的那一格总会占有相当的优势。


Tic-Tac-Toe加强版

　　上一版的Tic-Tac-Toe智商肯定无法令人满足，既然有了MiniMax算法，为什么不动手实现一下呢？