最近过年放假，想来时间比较充裕，于是研究了一下棋类游戏制作的原理。我们所熟悉的棋类游戏有五子棋、跳棋、象棋、围棋等，我们在制作这些棋类游戏时，如果是两个玩家对弈，则游戏代码很容易写出来，只要按照下棋规则设计程序即可。但如果是玩家与电脑对弈，则难度就很大了，因为电脑不可能像玩家一样那么智能，如果电脑真能和人一样聪明的话，那么电影<<终结者>>中的画面在我们的现实社会中就要重现了。
任何棋类游戏都要定义一棵有根的树，即博弈树，一个节点就代表下棋的一个局面，子节点就是这个局面再走一步可以到达的下一个局面。博弈树的一层就表示下棋一方的所有着子的棋局。如下图是一个井子棋游戏，偶数层代表了"×"下子的所有可能局面，奇数层代表了"Ο"下子的所有可能局面。对弈双方轮流着子，某一方下子将会使的博弈树增加一层，直到某一方赢棋或是和棋(叶子节点)，棋局结束时，博弈树不再增加。
在下棋时，对弈双方的目的就是将死对方，或者避免被将死，如果甲棋手在下子时能找到一步无论乙棋手怎么下子都会输的棋局，那么甲棋手一定会走这步堪称完美的棋法。下子的一方总是会这样考虑下棋:"如果我将子下在这里，对方会将子下在哪里使得他自已最有利，然后我又应该怎么下子使我最有利。。。"，下子的一方会这样考虑许多不同的下子位置，然后选择一个对自已最有利，而使对方最不利的下子棋局。
如果棋手在考虑下棋时能够考虑到棋局结束时情况，也就是说他能够将上图中的那棵博弈树在脑海中完全展开，看到叶子节点，那他就一定能够赢得这盘棋，因为他对于棋局的所有变化都可以知道，任何局面他都可以保证找到一步最佳着法。其实井字棋的博弈树既不烦琐也不深，所以整个树可以遍历展开，但如果是国际象棋，每一局都有35个左右的合理着法，即一个节点有35个子节点，第一层是35个局面，两层就有35*35个局面，六层就接近二十亿个局面，而十层就超过两千万亿个局面了。想要展开这棵博弈树，这是任何一位象棋大师也不可能做到的，甚至动用最强大的计算机也不可能做到。
我们在下棋时其实只会考虑几步之后的棋局，这个时候棋局没有结束，肯定是看不出来谁赢谁输的，但是我们可以估计谁最有可能赢，至少我们可以估计赢的概率大不大，容不容易赢。初学者可能只能看1，2步之后的棋局，而高手则可以看几步，甚至十几步之后的棋局，也就是说高手可以将博弈树展开的更大更深。在程序中，我们会用"评价函数"来估计棋局的好与坏，如果甲方赢棋或者很有希望赢，那么评价函数通常会返回正数；如果乙方是赢棋或者很有希望赢，那么返回负数；如果棋局是均势或者是和棋，那么返回在零左右的数值。
如下图所示，我们设定
评价值总是站在"×"的立场来看的，"×"总是希望棋局到达评价值大的局面，评价值越大，表明"×"越有优势，图中+1000表明优势最大("×"赢)；而"Ο"总是希望棋局到达评价值小的局面，评价值越小，表明"×"越不利，其实就是"Ο"越有优势，图中-1000表明优势最小("×"输，即"Ο"赢)。
对于人机博弈的程序，程序主要趋向于遵循一个被称为极小极大的算法，又名MiniMax算法，是一种找出失败的最大可能性中的最小值的算法。该算法是一种零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，而另一方则选择令对手优势最小化的方法。如上图可见，可以通过树状搜索找到棋局中对双方来说都最好的着法，即是MinMax算法的关键。另外由于博弈树无法全部展开，我们只能展开部分博弈树，即我们只能向前查看几步后的棋局，因此在极小极大算法中我们限制对博弈树估算的深度。在很多运行在标准PC硬件的国际象棋程序中，极小极大搜索的深度被限制在6层左右——包含了十亿个可能的博弈位置。超过这个层数会导致的分析博弈位置的耗时更长，这是不现实的。例如，以1百万/s的比率分析博弈位置，6层的深度需要耗费约一刻钟。
极小极大算法及参考图示：
int MinMax(int depth)
{
if (SideToMove() =="×") { // 如果轮到"×"走棋
return Max(depth); // "×"是先下棋者，取最大评估值
} else { // 如果轮到"Ο"走棋
return Min(depth); // 取最小评估值
}
}
int Max(int depth) { //取最大评估值函数
int best = -INFINITY; // 初始化最优值best = 负无穷大
if (depth <= 0) {
return Evaluate(); // 返回向前走depth步之后棋局的评价值
}
GenerateLegalMoves(); // 生成当前"×"所有合理的走法
while (MovesLeft()) { // 遍历"×"的所有走法
MakeNextMove(); // 执行走法
val = Min(depth - 1);// 取"Ο"走子的最小评估值
UnmakeMove(); // 撤销走法
if (val > best) { // 获取"×"的最大评估值
best = val;
}
}
return best; // 返回best最大值
}
int Min(int depth) { // 取最小评估值函数
int best = INFINITY; //初始化最优值best = 正无穷大，注意这里不同于“最大”算法
if (depth <= 0) {
return Evaluate();// 返回向前走depth步之后棋局的评价值
}
GenerateLegalMoves();// 生成当前"Ο"所有合理的走法
while (MovesLeft()) { // 遍历"Ο"的所有走法
MakeNextMove();// 执行走法
val = Max(depth - 1);// 取"×"走子的最大评估值
UnmakeMove();// 撤销走法
if (val < best) { //获取"Ο"的最大评估值，注意这里不同于“最大”算法
best = val;
}
}
return best;// 返回best最小值
}
上面的代码可以这样调用：
val = MinMax(5);
这样可以返回当前局面的评价，它是向前看5步的结果。
上面的算法，大家可以参照下面的图加以理解。
图1（向前走2步的搜索树）
图2（向前走3步的搜索树）
负值最大搜索：
负值最大只是对最小-最大的优化，它的代码更短，同时减少了移植代码时出错的可能，代码维护起来也比较方便。一个局面对"×"的优势为D，那么对"Ο"的优势就是-D；一个局面对"×"的优势为-D，那么对"Ο"的优势就是D。在负值最大算法中，没有了最小值，只有最大值，算法中用一个求最大值的操作代替了最小值和最大值交替的过程。需要注意的是，为了能使负值最大搜索算法得到正确的评价，必须修改局面评价函数的返回值，原来在极大极小搜索算法中始终返回的是"×"的优势，现在要改为当前走棋方的优势，占优返回正数，反之返回负数，最后这个值返回后必须加上负号，因为返回以后就是对另一方而言了。
负值最大算法及参考图示：
int NegaMax(int depth) { // 负值最大函数，求最大值的操作代替了最小值和最大值交替的过程
int best = -INFINITY; //初始化最优值best = 负无穷大
if (depth <= 0) {
return Evaluate(); //返回向前走depth步之后，要走子一方的评价值
}
GenerateLegalMoves(); //生成要走子一方所有合理的走法
while (MovesLeft()) {// 遍历要走子一方的所有走法
MakeNextMove();// 执行走法
val = -NegaMax(depth - 1); // 获取另一方的评价值，注意这里有个负号
UnmakeMove(); // 撤销走法
if (val > best) { // 获取走子一方的最大评价值
best = val;
}
}
return best;// 返回best最大值
}
