2014.07.08 22:43
简介：
“搜索”与“剪枝”几乎是如影随形的。此处的“搜索”指的是带有回溯算法的深度优先搜索。
在之前的“Minimax策略”中我们给出了一个三连棋的程序，运行后你就知道计算一步棋要花多少时间。
为了计算最优的一步棋，我们可能需要递归9万多次。如果毫无疑问这种阶乘式的穷举过程必须通过剪枝来加速。
本篇介绍一种用于Minimax策略的剪枝思路——α-β剪枝。
剪枝的英语是pruning，所以不要想当然说成trimming。
图示：
在上一篇讲解Minimax策略的博文中我们给出了一棵博弈树：
如果按照这棵树的形状来看，延伸下去应该会造成指数级的时间增长。
那么如果我们想做到“全知全能”，就得在下第一步棋的时候穷举所有可能的结局。因此你走一步棋就得推理9万多次。
按照这种脑力消耗，就是诸葛亮也吃不消，于是我们有两种办法可以偷懒：
1. 截断：我的脑容量没那么大，所以我只考虑三步棋以内的结果。三步棋之外的结果，姑且不管了。
2. 剪枝：有些结局实际上根本不需要分析，因为我们有充分的理由提前放弃那条路径。
本次不考虑截断的问题，只谈剪枝。
我们将刚才那棵博弈树中的两个结点标记为红色：
此处我们强调两条性质：
1. 对于Min层的每个节点，它的任何子节点的值都不小于它自身。
2. 对于Max层的每个节点，它的任何子节点的值都不大于它自身。
这棵树中78和36两个结点下方的节点不会被访问到，因为没有必要。
注意78所处的是Min层，对手为了使我的利益最小化，会尽力找出最小值。而68比78小，因此在78的下方不可能找到小于68的节点。所以没有必要继续深入78中。
36的道理相同，只不过处于Max层，所以解释自然是相反的。
在每一层都可能会有这样的节点，因此随时留意这样的剪枝机会，能极大地提高效率。
如果我没记错，经过这种剪枝的程序最多只需要递归一百多次，和9万多次相比确实快了不少。
因为Min和Max层交替出现，因此这种剪枝也需要两套代码逻辑，分别称为α剪枝与β剪枝。二者合称α-β剪枝。
教材中只给出了其中一个剪枝的伪代码，如果你没想明白，肯定写不出另一个的。
接下来请运行代码吧，看看效率上的差异。不过可能的话，我还是建议你在不看代码的情况下，自己修改三连棋的程序来实现α-β剪枝。
别忘了确保程序的正确性：如果你赢了电脑，那程序肯定是错的。
（提问：对于一个没有必胜策略的游戏，完美的AI是无法打败的，你只能打平手或者输给它，是这样吗？）
实现：
1 // Optimization for Minimax game strategy, using Alpha-Beta Pruning. 2 // You can watch over the ‘function_call_count‘ variable. 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 int function_call_count; 8 9 bool computerWin(const vector<int> &board) 10 { 11 int i, j; 12 13 for (i = 0; i < 3; ++i) { 14 for (j = 0; j < 3; ++j) { 15 if (board[i * 3 + j] != -1) { 16 break; 17 } 18 } 19 if (j == 3) { 20 return true; 21 } 22 } 23 24 for (i = 0; i < 3; ++i) { 25 for (j = 0; j < 3; ++j) { 26 if (board[j * 3 + i] != -1) { 27 break; 28 } 29 } 30 if (j == 3) { 31 return true; 32 } 33 } 34 35 if (board[0] == board[4] && board[4] == board[8] && board[8] == -1) { 36 return true; 37 } 38 39 if (board[2] == board[4] && board[4] == board[6] && board[6] == -1) { 40 return true; 41 } 42 43 return false; 44 } 45 46 bool humanWin(const vector<int> &board) 47 { 48 int i, j; 49 50 for (i = 0; i < 3; ++i) { 51 for (j = 0; j < 3; ++j) { 52 if (board[i * 3 + j] != 1) { 53 break; 54 } 55 } 56 if (j == 3) { 57 return true; 58 } 59 } 60 61 for (i = 0; i < 3; ++i) { 62 for (j = 0; j < 3; ++j) { 63 if (board[j * 3 + i] != 1) { 64 break; 65 } 66 } 67 if (j == 3) { 68 return true; 69 } 70 } 71 72 if (board[0] == board[4] && board[4] == board[8] && board[8] == 1) { 73 return true; 74 } 75 76 if (board[2] == board[4] && board[4] == board[6] && board[6] == 1) { 77 return true; 78 } 79 80 return false; 81 } 82 83 bool fullBoard(const vector<int> &board) 84 { 85 for (int i = 0; i < 9; ++i) { 86 if (board[i] == 0) { 87 return false; 88 } 89 } 90 91 return true; 92 } 93 94 void findComputerMove(vector<int> &board, int &best_move, int &result, 95 int alpha, int beta) 96 { 97 void findHumanMove(vector<int> &, int &, int &, int, int); 98 int dc, i, response; 99 100 ++function_call_count; 101 best_move = -1; 102 103 if (fullBoard(board)) { 104 result = 0; 105 return; 106 } 107 108 if (computerWin(board)) { 109 result = -1; 110 return; 111 } 112 113 result = alpha; 114 for (i = 0; i < 9 && result > beta; ++i) { 115 if (board[i] != 0) { 116 continue; 117 } 118 board[i] = -1; 119 findHumanMove(board, dc, response, result, beta); 120 board[i] = 0; 121 122 if (best_move == -1 || response < result) { 123 result = response; 124 best_move = i; 125 } 126 } 127 } 128 129 void findHumanMove(vector<int> &board, int &best_move, int &result, int alpha, 130 int beta) 131 { 132 void findComputerMove(vector<int> &, int &, int &, int, int); 133 int dc, i, response; 134 135 ++function_call_count; 136 best_move = -1; 137 138 if (fullBoard(board)) { 139 result = 0; 140 return; 141 } 142 143 if (humanWin(board)) { 144 result = 1; 145 return; 146 } 147 148 result = beta; 149 for (i = 0; i < 9 && result < alpha; ++i) { 150 if (board[i] != 0) { 151 continue; 152 } 153 board[i] = 1; 154 findComputerMove(board, dc, response, alpha, result); 155 board[i] = 0; 156 157 if (best_move == -1 || response > result) { 158 result = response; 159 best_move = i; 160 } 161 } 162 } 163 164 void printBoard(const vector<int> &board) 165 { 166 cout << " 1 2 3" << endl; 167 int i, j; 168 169 for (i = 0; i < 3; ++i) { 170 cout << i + 1; 171 for (j = 0; j < 3; ++j) { 172 cout << ‘ ‘; 173 switch(board[i * 3 + j]) { 174 case -1: 175 cout << ‘X‘; 176 break; 177 case 0: 178 cout << ‘.‘; 179 break; 180 case 1: 181 cout << ‘O‘; 182 break; 183 } 184 } 185 cout << endl; 186 } 187 } 188 189 int main() 190 { 191 vector<int> board; 192 int n; 193 int result; 194 195 board.resize(9, 0); 196 while (cin >> n) { 197 if (n < 0 || n >= 9 || board[n]) { 198 cout << "Invalid move" << endl; 199 continue; 200 } 201 202 board[n] = 1; 203 printBoard(board); 204 if (humanWin(board)) { 205 cout << "You win." << endl; 206 break; 207 } 208 209 if (fullBoard(board)) { 210 cout << "Draw." << endl; 211 break; 212 } 213 214 result = 1; 215 function_call_count = 0; 216 findComputerMove(board, n, result, 1, -1); 217 cout << "Number of function calls: " << function_call_count << endl; 218 board[n] = -1; 219 printBoard(board); 220 if (computerWin(board)) { 221 cout << "Computer win." << endl; 222 break; 223 } 224 225 if (fullBoard(board)) { 226 cout << "Draw." << endl; 227 break; 228 } 229 } 230 231 return 0; 232 }
《数据结构与算法分析：C语言描述》复习——第十章“算法设计技巧”——Alpha-Beta剪枝,布布扣,bubuko.com