QT五子棋項目詳解之七：Alpha-Beta剪枝算法前使用算殺
Alpha-Beta剪枝算法的缺陷是比較明顯。
1、最多隻能搜索有限層，目前優化之後我可以搜索到8層。即電腦4步，人4步後的情況。但是還是不夠的。看不到有限步數之後的棋。
2、電腦在思考第8層的時候，假定玩家是按照第8層走的。其實，相同棋力的玩家的在下一步的時候也會思考8層，是按照8層後的局面來選擇的。如下圖，假設電腦思考3層，電腦實際假設了玩家只思考了2層。其實玩家也會思考到最後的藍色層。
一種優化的辦法是使用算殺。也就是一旦發現了電腦存在殺棋，如活3，衝4的情況。電腦可以一直搜索到10層以上，來判斷是否電腦能夠一直算殺到贏棋。一旦玩家能夠成功封堵就說明失敗。能夠計算到10層以上的原因是節點少。只關注活3衝4這種棋。並且，玩家能夠封堵就會返回，不再計算下去。所以速度很快。
依然是max-min的思路來實現。
testKill函數是用來找到能組成或3或者衝4的空棋，將其存儲在kill中。
void Game::evalute_kill()
{
resultPoint = QPoint(-1,-1); //保存能夠算殺的點
int deeplength = 10;
QVector<QPoint> kill;
testKill(kill,computerColor);
if(kill.count()==0)
{
return;
}
for(int i= 0;i<kill.count();i++)
{
chess[kill[i].x()][kill[i].y()] = computerColor;
int m = min_kill(kill[i],deeplength-1);
chess[kill[i].x()][kill[i].y()] = 0;
if(!m)
{
continue;
}else{
resultPoint = kill[i];
kill.clear();
return;
}
}
}
int Game::max_kill(QPoint point,int deep)
{
if(ifWin(point.x(),point.y()))
{
return false;
}
if(deep < 0) return false;
QVector<QPoint> kill;
testKill(kill,computerColor);
if(kill.count()<=0)
{
return false;
}
for(int i = 0 ;i<kill.count();i++)
{
chess[kill[i].x()][kill[i].y()] = computerColor;
int m = min_kill(kill[i],deep-1);
chess[kill[i].x()][kill[i].y()] = 0;
if(!m)
{
continue;
}else{
kill.clear();
return true;
}
}
kill.clear();
return false;
}
int Game::min_kill(QPoint point,int deep)
{
if(ifWin(point.x(),point.y()))
{
return true;
}
if(deep < 0) return false;
QVector<QPoint> kill;
testKill(kill,computerColor);
testKill(kill,computerColor==4?5:4);
if(kill.count()<=0)
{
return false;
}
for(int i = 0 ;i<kill.count();i++)
{
chess[kill[i].x()][kill[i].y()] = computerColor==4?5:4;
int m = max_kill(kill[i],deep-1);
chess[kill[i].x()][kill[i].y()] = 0;
if(!m)//堵住了
{
kill.clear();
return false;
}
}
kill.clear();
return true;
}
將算法應用在Alpha-Beta剪枝算法前判斷是否能夠一殺到底即可。