QT五子棋項目詳解之五：AI人機對戰Alpha-Beta剪枝算法
前面介紹了單純的max-min算法，其效率是很低的，只能思考四層。沒有看過的，先去看看，才能理解後面的。
只能思考4層是由於可能的走法太多了，如第一步電腦有225種走法，每一種走法都會導致玩家有224種走法............就像是一顆龐大的樹。由於可能性太多，所以優化是必須的。優化的第一種辦法就是剪枝。
沒有看過的，先去看看，才能理解後面的。
QT五子棋項目詳解之四：AI人機對戰max-min極大極小值博弈算法：
http://blog.csdn.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;
}