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種方式：距離、預先評估該點，排序。