前面讲到了剪枝算法作为一种对于极大极小博弈算法的优化，是提高效率的一种好办法。但是我们不满足于此。因为一般的普通人是可以思考到6层以上。为了对效率进行提高，我们还有两种办法。想象一下如下图，电脑可能走棋如果从4个变为2个，那么效率的提升就会提高一倍。
其实深入下去就会发现，这些优化都是理所当然。因为有一些明显的不好的点直接就可以排除掉。就比如在最开始的时候，没有人会在最左上的0,0下子一样。在实际中，我进行的优化包括：
1、我只会在已有点不超过距离2的区域内下子。如下图可能的下子范围，直接缩小区域
bool Game::hasNeighbor(int x,int y) //距离为2之类返回true
{
bool flag =false;
int redirect[8][2] = {{1,0},{1,1},{1,-1},{0,1},{0,-1},{-1,0},{-1,1},{-1,-1}};
for(int j = 1;j<=2;j++)
{
for(int i = 0;i<8;i++)
{
int m = j*redirect[i][0]+x;
int n = j*redirect[i][1]+y;
if(m>=0 && m<15 && n >=0 && n<15 && chess[m][n])
{
flag = true;
break;
}
}
}
return flag;
}
2、启发式搜索：
在实际中，你可以使用一些手段来判断一些点明显的好坏。还记得之前讲的策略表，我使用的策略表就有判断一个点好坏的公式。如果一个优秀的策略表，最优选择点有超大概率会是排名在前10的这些点钟。所以我直接就可以将每一步可能的节点都锁定在10个之类，大大提高了效率。
3、对于剪枝算法的优化，还有一点非常重要的就是对于节点的排序。考虑我们之前用到的图。
如果顺序是这样的：
那么我们就可以直接排除掉2个分支，这就是初略排序的威力。
这里使用了插入排序的方式，来求得10个最大的点，并进行了排序。你也可以使用快排。但是一定要释放内存。
这样效率就能大大提升。
QVector<QPoint> Game::gen(int deep,int type) //返回可能选择的点
{
int top= -1;
bool first =true;
QVector<node * > result(12);
for(int x = 0;x<15;x++)
{
for(int y= 0;y<15;y++)
{
if(chess[x][y]==0 && hasNeighbor(x,y))
{
int flag = 1;
for(int i= 0;i<=top;i++)
{
if(result[i]->point.x()==x && result[i]->point.y()==y)
{
flag=0;
break;
}
}
if(!flag)
{
continue;
}
node * snode = new node;
snode->point =QPoint(x,y);
int tmpscore = snode->sscore = evaluteScore2(QPoint(x,y),type);
//evaluteScore2是一个评估函数，和我之前策略表使用的判断方法相似，就是判断改点组成的所有五元组的得分
if(first)
{
result[0] =snode;
first=!first;
top=0;
}
else
{
if( top==9 && tmpscore <result[9]->sscore)
{
continue;
}
int tmp = top;
while(tmp>=0 && result[tmp]->sscore<tmpscore)
{
result[tmp+1] = result[tmp];
tmp--;
}
result[tmp+1] = snode;
top++;
if(top>9)
{
top=9;
}
}
}
}
}
QVector<QPoint> temp;
for(int i =0 ;i<10;i++)
{
if(i<=top)
temp.push_back(result[i]->point);
}
for(int i =0 ;i<=top;i++)
{
free(result[i]);
}
return temp;
}
总结：1、通过以上方式我进行6层的搜索也毫不费力，可以接受的时间内甚至可以达到8层。可以很轻松的战胜低端玩家。
2、在QT中，一定要释放内存，不释放后果严重。我在开发中发现，由于这个gen函数会一直在min-max算法的递归中调用，我下一步棋如果不释放内存，就会增加200M。
3、优化的3种方式：距离、预先评估该点，排序。