QT五子棋项目详解之五：AI人机对战Alpha-Beta剪枝算法
前面介绍了单纯的max-min算法，其效率是很低的，只能思考四层。没有看过的，先去看看，才能理解后面的。
只能思考4层是由于可能的走法太多了，如第一步电脑有225种走法，每一种走法都会导致玩家有224种走法............就像是一颗庞大的树。由于可能性太多，所以优化是必须的。优化的第一种办法就是剪枝。
没有看过的，先去看看，才能理解后面的。
QT五子棋项目详解之四：AI人机对战max-min极大极小值博弈算法：
http://blog.****.net/weixin_39788534/article/details/79499966
我接着前面的讲，如下图，思考两层的情况：计算的顺序是这样的：
先遍历了A分支的D，E，又遍历其他分支。F,G.........
我们可以考虑一下下面的这种情况：即当计算到H的时候，我已经没有必要去计算C节点的其他分支I....了
为什么，你想一下，当电脑走了C节点后，玩家会选择一个对玩家最不利的点，如果I的值大于1，那玩家就会选择1.
如果I的值等于0，那玩家就会选择0这个点，导致C的分数变成了0.不管I的值是什么，玩家都会选择前面的3这个节点，这样就大大的提高了效率。
因此，对于剪枝需要保留这一层的最值，对于电脑这一层来说，就是需要保留最大的3，如果后面的节点如C的节点比3小就不用再判断了。
就像是模拟人的思考方式一下，真的很简单。一切都是合理的方式。
代码也很简单，多加了几行。：
QPoint Game::maxmin2(int deep)
{
int best = INT_MIN;
QVector<QPoint> points = gen(deep,computerColor);
for(int i = 0;i<points.count();i++)
{
chess[points[i].x()][points[i].y()] = computerColor;
int v = min2(deep-1,best > INT_MIN ? best : INT_MIN,INT_MAX,points[i]);
if(v==best)
{
bestpoints.push_back(points[i]);
}
if(v>best)
{
best = v;
bestpoints.clear();
bestpoints.push_back(points[i]);
}
chess[points[i].x()][points[i].y()] = 0;
}
srand((unsigned)time(NULL));
points.clear();
return bestpoints[rand()%bestpoints.count()];
}
int Game::max2(int deep,int alpha, int beta,QPoint point)
{
if(deep <= 0 || ifWin(point.x(),point.y()))
{
int k =evalute();
return k;
}
int best = INT_MIN;
QVector<QPoint> points = gen(deep,computerColor);
for(int i = 0;i<points.count();i++)
{
chess[points[i].x()][points[i].y()] = computerColor;
int v = min2(deep-1,best > alpha ? best : alpha, beta,points[i]);
if(v>best)
{
best = v;
}
chess[points[i].x()][points[i].y()] = 0;
if(v >beta)
{
break;
}
}
points.clear();
return best;
}
int Game::min2(int deep,int alpha, int beta,QPoint point)
{
if(deep <= 0 || ifWin(point.x(),point.y()))
{
int k =evalute();
return k;
}
int best = INT_MAX;
QVector<QPoint> points = gen(deep,computerColor==4?5:4);
for(int i = 0;i<points.count();i++)
{
chess[points[i].x()][points[i].y()] = computerColor==4?5:4;
int v = max2(deep-1,alpha,best < beta ? best : beta,points[i]);
if(v<best)
{
best = v;
}
chess[points[i].x()][points[i].y()] = 0;
if(v<alpha)
{
break;
}
}
points.clear();
return best;
}