回溯算法（井字游戏）

一、问题描述

三连棋双方都是智力卓越的话，很容易完成平局；在人机对战情况下， 计算机的策略是保证自己不输，并等待玩家失误的机会，当玩家失误时候， 计算机抓住这个失误并取得胜利； ** 极大极小策略** 使用一个求值函数来对一个位置的好坏量化；能使得计算机获胜的位置，其值+1； 平局为0； 计算机输的-1；通过考察盘面能够确定这局棋输赢的位置叫做终端位置（终端位置：有时候只下到一半，计算机发现玩家失误了，计算机一定能赢了，不用等到完全落完棋子）； 终端位置是使用immediateHumanWin函数或是immediateCompWin函数能判断的；

如果一个位置不是终端位置， 该位置的值通过递归假设双方都选择最优棋步确定（计算机和玩家都不失误），叫做极大极小策略；计算机试图使这个位置极大化， 玩家试图使这个位置极小化；

每次轮到计算机下棋的时候， 计算机都对棋盘中的空位做挨个做测试，得到每一个空位的值，从中选择最大的作为这一步的下子点； 每次轮到玩家要下棋的时候， 计算机都对棋盘的所有空位都挨个做测试，得到每一个空位的值，从中选择一个最小的值作为这一步的下子点；

二、代码分析

一个井字游戏代码的链接： https://github.com/YinWenAtBIT/Data-Structure/tree/master/tic_tac_toe https://blog.csdn.net/yw8355507/article/details/48868173 下面是自己写的代码，但是这个代码有错误，还没有找出，上面链接的代码是正确的，可以参考；

假设当前棋盘的情况如下图所示，将棋盘的9个空间分为两个集合， 其中Q表示已经落子的集合， S表示空闲集合；假设接下来轮到计算机下棋，计算机会在集合S中选择一个i点用于防止本轮的棋子；如何从集合中选择i点执行以下的策略——极大极小策略： 判断的标准是value变量，有三个取值： 1） 当计算机赢，设置COM_WIN为 1 2） 当平局， 设置DRAW为0 3） 当计算机输， 设置COM_LOSS为-1

#include <stdio.h> #include <stdlib.h> #define N 3 char Chess[N][N] = {0}; const char COMP = 'O'; const char HUMAN = 'X'; //极大极小策略 //是计算机获胜的位置，可以得到值1； 平局0； 人获胜的值-1； #define COMP_LOSS -1 #define DRAW 0 #define COMP_WIN 1

对于计算机，使用findCompMove返回S集合的value值 findCompMove函数分为三部分； 1） 当前集合Q和S导致棋子落满了， 是平局，返回value = DRAW； 2）在当前的棋面上， 在S集中选择一个i位置放置COMP， 如果放置之后计算机胜利，就返回，并且将i赋值给bestMove返回上一层调用； 3）如果本次无论如何放置都不会成功，就需要在集合S中的value值来判断； 假设value一开始为最低的COM_LOSS， 循环尝试S集合中的每一个点i， 递归调用计算(S - i)的value值得到responseValue， 得到最大的value值为value = max(value, respenseValue); 当能够得到一个最大的value的时候，记录下点i的位置为bestMove表明本次轮流下应该下子的点；最后， 将value的值做函数返回； 轮到计算机放置棋子时候findCompMove的函数， findCompMove 的目的是在集合S中找到一个点来放置COMP， 这个点就是bestMove；findCompMove 函数返回的是极大极小策略的比较标准，在递归调用中， 一般将比较标准的值的结果作为递归函数的返回值； 回溯算法在实现上需要循环与递归调用的结合， 循环保证对当前所有可能情况都去尝试， 递归保证了在不符合标准的时候（尝试失败的时候），递归调用函数返回，重新选择下一种情况重新尝试； findCompMove 函数的代码如下：

int findCompMove(int *bestMove) { int i, responseValue; int dc; //无用的值 int value; //空闲点的值 if (fullChess()) value = DRAW; //在空闲点集合S中选择一个点放置COMP，然后测试计算机是否胜利 else if (immediateCompWin(bestMove)) return COMP_WIN; else { value = COMP_LOSS;//空闲点的值初始化为最小 *bestMove = 1; for (i = 1; i <= N * N; i++) { if (isEmpty(i)) {//S集合是现在棋盘上的空闲点 place(i, COMP); //假设在i位置落子 responseValue = findHumanMove(&dc);//测试(S-i) 空闲点的值 unPlace(i); //恢复位置i //responseValue表示空闲点(S-i)时候的空闲点值 //value表示空闲点S时候的空闲先值 //根据极大极小值策略， 计算机是想让空闲点的值最大化，因此取得max(value, responseValue) //如果在空闲点S中选择一个点i能使的value增大为responseValue，就在位置i上落子 //如果当前空闲空间S中任何一个i都不能使得空闲值增加, 就返回 if (responseValue > value) { value = responseValue; *bestMove = i; } } } } //函数返回空闲点的值 //value = 1， 表示剩余空闲点中又让计算机赢的组合，计算机有赢的可能 //value = 0， 计算机有平局的可能 //value = -1 计算机有输的可能 //由于有value = max(value, responseValue),因此上述三种情况有优先级 //只要存在计算机赢的可能， value就返回1 //当不存在计算机赢的机会， 但是只要存在平局的机会， value就返回0 //当即不存在计算机赢的机会， 也不存在平局的机会，value才返回-1； return value; }

findHumanMove 函数的代码实现如下：

int findHumanMove(int *bestMove) { int i, responseValue; int dc; int value; if (fullChess()) value = DRAW; else if (immediateHumanWin(bestMove)) return COMP_LOSS; else { value = COMP_WIN; *bestMove = 1; for (i = 1; i <= N * N; i++) { if (isEmpty(i)) { place(i, HUMAN); responseValue = findCompMove(&dc); unPlace(i); if (responseValue < value) { value = responseValue; *bestMove = i; } } } } return value; }

辅助函数canHumanWin 用于判断当前棋盘玩家是否获胜 辅助函数canCompWin 用于判断当前期盼计算机是否获胜 immediateCompWin 函数用于在空闲集合S中找到一点放置COMP，然后判断是否会胜出； immediateHumanWin 函数在空闲集合S中找到一个点放置HUMAN， 然后判断是否会生出； 此外还有其他辅助函数：

//判断当前棋盘上的情况，电脑是否赢 int canCompWin() { //先判断每一行是否是COMP for (int i = 0; i < N; i++) { if (Chess[i][0] != COMP) continue; if (Chess[i][1] == COMP && Chess[i][2] == COMP) return 1; } //判断每一列是否是COMP for (int j = 0; j < N; j++) { if (Chess[0][j] != COMP) continue; if (Chess[1][j] == COMP && Chess[2][j] == COMP) return 1; } //判断对角线的 if (Chess[0][0] == COMP && Chess[1][1] == COMP && Chess[2][2] == COMP) return 1; if (Chess[0][2] == COMP && Chess[1][1] == COMP && Chess[2][0] == COMP) return 1; //以上条件都不符合，当前棋盘不能赢 return 0; } int canHumanWin() { //先判断每一行是否是HUMAN for (int i = 0; i < N; i++) { if (Chess[i][0] != HUMAN) continue; if (Chess[i][1] == HUMAN && Chess[i][2] == HUMAN) return 1; } //判断每一列是否是HUMAN for (int j = 0; j < N; j++) { if (Chess[0][j] != HUMAN) continue; if (Chess[1][j] == HUMAN && Chess[2][j] == HUMAN) return 1; } //判断对角线 if (Chess[0][0] == HUMAN && Chess[1][1] == HUMAN && Chess[2][2] == HUMAN) return 1; if (Chess[0][2] == HUMAN && Chess[1][1] == HUMAN && Chess[2][0] == HUMAN) return 1; //以上条件都不符合， 当前棋盘不能赢 return 0; } //判断棋盘是否为满 int fullChess() { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (Chess[i][j] == 0) return 0; return 1; } int isEmpty(int i) { int row = (i-1) / N; int col = (i-1) % N; if (Chess[row][col]== 0) return 1; return 0; } void place(int i, char c) { int row = (i - 1) / N; int col = (i - 1) % N; Chess[row][col] = c; } void unPlace(int i) { int row = (i - 1) / N; int col = (i - 1) % N; Chess[row][col] = 0; } int immediateCompWin(int* bestMove) { for (int i = 1; i <= N * N;i++) { if (isEmpty(i)) { place(i, COMP); if (canCompWin()) { unPlace(i); *bestMove = i; return 1; } unPlace(i); } } return 0; } int immediateHumanWin(int* bestMove) { for (int i = 1; i <= N * N; i++) { if (isEmpty(i)) { place(i, HUMAN); if (canHumanWin()) { unPlace(i); *bestMove = i; return 1; } unPlace(i); } } return 0; } void printChess() { printf("\n-------------\n"); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { printf("| %c ", Chess[i][j]); } printf("|\n"); } printf("\n-------------\n"); }

在主函数中， 可以选择让玩家决定谁先下第一子； 函数humanFirst 是玩家先下第一子的启动函数， 函数compFirst 是电脑先下第一子的启动函数；

humanFirst 函数的代码实现：

void humanFirst() { int bestStep = 9; //int value; int result = -2; int humanStep; //一次循环中， 玩家下一步棋， 电脑下一步棋 while (result == -2) { printf("now board is:"); printChess(); printf("#################################\n"); //本来第一次下棋可以不用测试棋盘是否为空，但考虑可能给的是一个残棋 do { printf("Please choose your step: \n"); scanf_s("%d", &humanStep); } while (!isEmpty(humanStep)); place(humanStep, HUMAN);//将玩家的选择下到棋盘上 printf("#################################\n"); printf("The player place: %c at %d\n", HUMAN, humanStep); if (canHumanWin())//玩家下完之后， 判断棋盘是否是玩家胜出 result = -1; //否则， 递归调用findCompMove得到电脑的最佳下棋位置bestStep //在电脑在bestStep位置落棋之后，判断是否电脑获胜, //如果电脑获胜， result = 1 else if (!fullChess()) { findCompMove(&bestStep); place(bestStep, COMP); printf("The computer place: %c at %d\n", COMP, bestStep); if (canCompWin()) result = 1; } //如果玩家下完棋之后，玩家不能赢， 并且棋盘满了，就是平局 else result = 0; } printf("Game over\n"); printChess(); }

compFirst 函数的代码实现：

void compFirst() { int bestStep = -1; int result = -2; int humanStep; int firstStep = rand() % 9 +1; place(firstStep, COMP);//放置电脑的棋子 while (result == -2) { if (!fullChess()) {//前提是棋盘没满， 才可以执行下面的 printf("now the board is:\n"); printChess(); printf("#################################\n"); do { printf("please choose your step: \n"); scanf_s("%d", &humanStep); } while (!isEmpty(humanStep)); place(humanStep, HUMAN);//放置玩家的棋子 printf("#################################\n"); printf("The player place: %c at %d\n", HUMAN, humanStep); if (canHumanWin()) result = -1; //玩家胜出，返回-1 else { findCompMove(&bestStep); //找到电脑的放置最佳位置 place(bestStep, COMP); printf("The computer place: %c at %d\n", COMP, bestStep); if (canCompWin()) result = 1; } } else//如果棋盘满了， 就是平局 result = 0; } printf("game over!\n"); printChess(); }

简单的主函数

int main() { srand((unsigned)time(NULL)); //compFirst(); humanFirst(); return 0; }

三、剪枝优化

1） Alpha 剪枝 首先考虑Alpha 剪枝， 如下图所示， 当上层电脑正在模拟的时候，会使用value值记录下层玩家模拟的返回值中的最大值，表明了人类玩家的返回值肯定是大于value的，图中的大于44； 上层电脑模拟的时候会将这个value值传递给人类模拟中的Alpha形参；在人类模拟中， 需要去循环遍历中的每个最小值，如果人类模拟中的值中存在一个 value <= Alpha（图中的40< 44), 则人类模拟返回的值肯定小于40，上一层的电脑模拟返回44；因此人类模拟中讯在一个值小于44， 就不需要继续剩下的循环遍历，直接返回； 更进一步的分析，回溯算法是循环与递归调用的结合。循环保证对所有可能的情况都做尝试， 递归执行尝试，并将尝试的结果做函数返回值返回； 例如空闲点集S有数据S(a, n), 使用循环for(int i = a; i <= b; i++)遍历所有的点， 在循环体内递归调用；如果执行到k点， 对于(i, k-1)的点其value已经确定， 将这个value传递给对k点的递归调用，如果在对k点的递归调用中的值小于value， 调用直接返回， 并且可以裁减对(k+1, j) 这些点的递归调用，这就是Alpha剪枝

2） Beta 剪枝 在人类模拟的循环遍历中， 记录下从下层电脑模拟返回的值中的最小值，如图中的value = 44，并将value的值传递给下一层的电脑模拟的Beta 在进行下一次的电脑模拟中， 如果发现一个value值大于Beta，就不需要继续试探了，直接返回， 人类模拟直接返回值44； 具体的代码实现如下：

int findCompMove(int *bestMove, int Alpha, int Beta) { int i, responseValue; int dc; //无用的值 int value; //空闲点的值 if (fullChess()) value = DRAW; //在空闲点集合S中选择一个点放置COMP，然后测试计算机是否胜利 else if (immediateCompWin(bestMove)) return COMP_WIN; else { value = Alpha;//空闲点的值初始化为最小 *bestMove = 1; for (i = 1; i <= N * N && value < Beta; i++) { if (isEmpty(i)) {//S集合是现在棋盘上的空闲点 place(i, COMP); //假设在i位置落子 responseValue = findHumanMove(&dc, value, Beta);//测试(S-i) 空闲点的值 unPlace(i); //恢复位置i //responseValue表示空闲点(S-i)时候的空闲点值 //value表示空闲点S时候的空闲先值 //根据极大极小值策略， 计算机是想让空闲点的值最大化，因此取得max(value, responseValue) //如果在空闲点S中选择一个点i能使的value增大为responseValue，就在位置i上落子 //如果当前空闲空间S中任何一个i都不能使得空闲值增加, 就返回 if (responseValue > value) { value = responseValue; *bestMove = i; } } } } //函数返回空闲点的值 //value = 1， 表示剩余空闲点中又让计算机赢的组合，计算机有赢的可能 //value = 0， 计算机有平局的可能 //value = -1 计算机有输的可能 //由于有value = max(value, responseValue),因此上述三种情况有优先级 //只要存在计算机赢的可能， value就返回1 //当不存在计算机赢的机会， 但是只要存在平局的机会， value就返回0 //当即不存在计算机赢的机会， 也不存在平局的机会，value才返回-1； return value; } int findHumanMove(int *bestMove, int Alpha, int Beta) { int i, responseValue; int dc; int value; if (fullChess()) value = DRAW; else if (immediateHumanWin(bestMove)) return COMP_LOSS; else { value = Beta; *bestMove = 1; for (i = 1; i <= N * N && value > Alpha; i++) { if (isEmpty(i)) { place(i, HUMAN); responseValue = findCompMove(&dc, Alpha, Beta); unPlace(i); if (responseValue < value) { value = responseValue; *bestMove = i; } } } } //printf("********%d\n", value); return value; }