QT五子棋项目详解之六：AI启发式搜索：剪枝算法的更一步优化

前面讲到了剪枝算法作为一种对于极大极小博弈算法的优化，是提高效率的一种好办法。但是我们不满足于此。因为一般的普通人是可以思考到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种方式：距离、预先评估该点，排序。