1.象棋中通常需要推算当前局面下,每走一步之后的局面分,通常我们可以设定考虑几步棋,通常我们所说的算棋,而计算机的AI算法中最常用的就是最大值最小值算法,而剪枝算法是对最大值最小值算法的一种优化。
有点类似于八皇后的深度树
当前局面表示电脑,作为电脑肯定会择当前局面分最大的作为下一步。如果我们的LEVEL为1,也就是我们只算下一步的得分,选最大的那个,对比途中,肯定挑选100作为下一步的走法。但一般类似我们人下象棋的过程。我们一般会去想下几步该怎么下而挑选出最好的一步,就要往下递归了,比如LEVEL为2的时候,第一分支搜索100,这时候轮到人走,人肯定选对电脑不利的局面,也就是最小局面分10,而第二分支80,往下走,人选20,第三分支90,人选30,我们要的肯定是最好的30。这就是最大,最小,最大表示作为电脑方选最大,最小表示人方选最小,最后由电脑方选出最大的一个局面分作为下一步的参考。
我们模拟电脑走法的时候,不论层次为多少,都是以最后一个并且是最大的作为我们的局面分。
将图中的50换成5
剪枝算法是对最大最小算法的优化: 场景模拟level为2:走第一步100,轮到人,人选10(对电脑最为不利),而搜索80的时候,下一步人选5,这时候,80的其他分支就没必要去算了,因为人选的5比走100选的10还小。作为电脑优先选100的这一步,这时候只需要遍历90的分支,继续查找,将100得到的局面分代入到90的遍历中,如果90的分支中有比10小的,那么90的其他分支也不再考虑。
为了方便理解 这边贴上代码
Step* AI::getStep(SceneGame* game, int level) { int highScore = -3000; Step* ret = NULL; // 产生所有可能的移动,遍历 vectorallMove = getAllPossibleMove(game); vector ::iterator it; for (it = allMove.begin(); it != allMove.end(); ++it) { Step* step = *it; fakeMove(game, step); //int score = getScore(game); int score = getMinScore(game, level - 1, highScore); unfakeMove(game, step); if (score > highScore) { highScore = score; ret = step; } } for (it = allMove.begin(); it != allMove.end(); ++it) { Step* step = *it; if (step != ret) delete step; } return ret; }
int AI::getMinScore(SceneGame* game, int level, int curMinScore) { if (level == 0) return getScore(game); int minScore = 3000; // 产生所有可能的移动,遍历 //得到电脑最不利的局面 vectorallMove = getAllPossibleMove(game); vector ::iterator it; for (it = allMove.begin(); it != allMove.end(); ++it) { Step* step = *it; fakeMove(game, step); //下一步得分 int score = getMaxScore(game, level - 1, minScore); unfakeMove(game, step); // 减枝算法 if (score <= curMinScore) { minScore = score; break; } if (score
int AI::getMaxScore(SceneGame* game, int level, int curMaxScore) { if (level == 0) return getScore(game); int maxScore = -3000; // 产生所有可能的移动,遍历 vectorallMove = getAllPossibleMove(game); vector ::iterator it; for (it = allMove.begin(); it != allMove.end(); ++it) { Step* step = *it; fakeMove(game, step); int score = getMinScore(game, level - 1, maxScore); unfakeMove(game, step); if (score >= curMaxScore) { maxScore = score; break; } if (score > maxScore) { maxScore = score; } } for (it = allMove.begin(); it != allMove.end(); ++it) { Step* step = *it; delete step; } return maxScore; }