正在阅读：Java咖啡馆(13): 终结者Java咖啡馆(13): 终结者

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

计算机的智慧

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

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

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

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

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

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

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

/**
* 估计函数。
* @param board 要被估计的棋盘
* @return 估计值
*/
private int evalauate(int[] board) {
int x2 = 0， o2 = 0， x1 = 0， o1 = 0;

for (int i = 0; i < lines.length; i++) {
int[] line = lines[i];
int sum = 0;
for (int j = 0; j < line.length; j++) {
sum += board[line[j]];
}
switch (sum) {
case 3:
// 圆圈联通
return -100;
case 12:
// 大叉联通
return 100;
case 8:
x2++;
break;
case 4:
x1++;
break;
case 2:
o2++;
break;
case 1:
o1++;
break;
}
}
return 3 * (x2 - o2) + x1 - o1;
}

/**
* 拥有职业选手棋力的机器人下一步棋。
*/
public void professional() {
ArrayList blanks = new ArrayList();
// 获取当前棋局所有可以下的位置
for (int i = 0; i < 9; i++) {
if (board[i] == 0) {
blanks.add(new Integer(i));
}
}
// 若已经没有空格可以下了便和局
if (blanks.size() == 0) {
message = "平局";
gameover = true;
return;
}
// 利用MiniMax算法找出计算机最可能赢的一步棋
// 枚举Min的每一种可能下法
int minBoards[][] = new int[blanks.size()][9];
int max = -100， best = 0;
for (int i = 0; i < minBoards.length; i++) {
// 复制当前棋局
int[] minBoard = (int[]) board.clone();
// 测试下第一步棋
minBoard[((Integer) (blanks.get(i))).intValue()] = CROSS;
minBoards[i] = minBoard;
// 剩下的空格就是Max的落子范围
ArrayList maxBlanks = (ArrayList) blanks.clone();
maxBlanks.remove(i);
// 根据当前的测试棋局枚举Max的每一种可能下法
int min = 100;
for (int j = 0; j < maxBlanks.size(); j++) {
// 复制当前棋局
int[] maxBoard = (int[]) minBoard.clone();
// 测试下第一步棋
maxBoard[((Integer) (maxBlanks.get(j))).intValue()] = NOUGHT;
// Min将取这些Max的取值中最小者
int value = evalauate(maxBoard);
if (value < min) {
min = value;
}
}
if (min > max) {
max = min;
best = i;
}
}
board = minBoards[best];
}