QT五子棋详解之八：min-max优化的负极大值算法兼谈qt内存泄露
负极大值搜索作为min-max博弈算法的优化，其本质上没有任何区别。
负极大值搜索它的效率也不会快多少，只是它的代码更加优雅简洁。更好进行代码的移植。
我们将min-max博弈算法与负极大值算法的伪代码发出来比较一下。不加那个剪枝的
int MinMax(int depth) {
if (SideToMove() == WHITE) { // 白方是“最大”者
return Max(depth);
}
else { // 黑方是“最小”者
return Min(depth);
}
}
int Max(int depth) {
int best = -INFINITY;
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Min(depth - 1);
UnmakeMove();
if (val > best) {
best = val;
}
}
return best;
}
int Min(int depth) {
int best = INFINITY; // 注意这里不同于“最大”算法
if (depth <= 0) {
return Evaluate();
}
GenerateLegalMoves();
while (MovesLeft()) {
MakeNextMove();
val = Max(depth - 1);
UnmakeMove();
if (val < best) { // 注意这里不同于“最大”算法
best = val;
}
}
return best;
}
上面的代码可以这样调用：
val = MinMax(5);
对比负极大值算法的伪代码是不是代码更加风骚：
要从极大极小值过渡到负极大值搜索，需要理解几个方面：
1、极大极小值对每一个点的评估都是对于电脑来说的。而负极大值是对于本层来说的。如第一层是黑棋，那么这一层的分数是对于黑棋来说的，下一层是白棋层，那么这些点的分数是对于白棋的角度来看的。
2、max(deep-1)=-min(deep-1).假设本层为黑棋层，求本层某个点对于黑棋的分数，实际是求下一层白棋对于下一点的分数的负数。
3、每一层都是选的最大值，因为这个值是当前玩家的角度对于局势的评价。
看图说话：在这个局面，下面的点的得分是白棋对于局面的评价。
那么对于黑棋来说，上面的点的得分又是多少呢？
首先对于白棋来说，其会选择对其最有利的一个点：
黑棋对其取负数，就变成了黑棋对这个局势的评价：
所以最后黑棋也会选择对其最大的值-3。
也就是说在每一层，都会选择最大的一个值，因为这个值是当前玩家的角度对于局势的评价。
接下来，看一下加入了剪枝的负极大值的伪代码：
下图中的最后的1节点直接就被减掉了，因为最大的节点-3去取负数为3。而6大于3，就此节点就废了，因为白棋一定会选择6胡大于6的值。再去了反就是-6不会比-3大，而已经有-3这个节点了，所以对于黑棋来说，这个节点就废掉了。
最后看一下我qt的代码：
多加了maxmin是因为我想对其进行一些拓展，核心是对于negamax函数的理解。
唯一使算法感到复杂的是，Alpha和Beta是不断互换的。当函数递归时，Alpha和Beta不但取负数而且位置交换了，但是可以证明它只是比最小-最大算法更好而已。我已经把这个算法的精髓用图展现出来了。QPoint Game::maxmin(int deep)
{
int alpha = -INT_MAX;
int beta = INT_MAX;
QVector<QPoint> points = gen(deep,computerColor);
for(int i = 0;i<points.count();i++)
{
chess[points[i].x()][points[i].y()] = computerColor;
int val =-negamax(deep-1,-beta,-alpha,points[i],computerColor==4?5:4);
if(val>alpha)
{
alpha = val;
resultbestpoint = points[i];
}
chess[points[i].x()][points[i].y()] = 0;
}
QVector<QPoint>().swap(points);
Q_ASSERT(points.capacity() == 0);
qDebug()<<"resultbestpoint"<<resultbestpoint.x()<<" "<<resultbestpoint.y()<<endl;
return resultbestpoint;
}
int Game::negamax(int deep,int alpha, int beta,QPoint point,int role)
{
if(deep <= 0 || ifWin(point.x(),point.y()))
{
int k =evalute(role);
return k;
}
QVector<QPoint> points = gen(deep,role);
for(int i = 0;i<points.count();i++)
{
chess[points[i].x()][points[i].y()] = role;
int v = -negamax(deep-1,-beta,-alpha,points[i],role==4?5:4);
chess[points[i].x()][points[i].y()] = 0;
if(v>=beta)
{
return beta;
}
if(v >alpha)
{
alpha = v;
}
}
QVector<QPoint>().swap(points);
Q_ASSERT(points.capacity() == 0);
return alpha;
}
最后谈一下qt的内存泄漏，
1、主要是对于vector来说的，其使用clear（）函数不会释放内存，需要使用如下方式释放内存。
一定要注意，特别是像我做的8层搜索，会有上千万的节点的时候。内存的泄露是致命的问题。
QVector<T> v ...;
QVector<T>().swap(v);
Q_ASSERT(v.capacity() == 0);
2、vector中一定要存指针。
3、函数返回的时候，尽量不要直接返回vector