新手立體四子棋AI教程(4)——啟發式搜索與主程序

05-05

通過前面幾篇文章的學習，我們的四子棋程序已經有了框架、搜索幾大部分，但是還有著不少問題，我們的程序只能迭代很有限的步驟，導致棋力低下，在這一篇我們將通過啟發式搜索極大的優化搜索效率。

一、原因

我們之前的產生走子位置的函數很簡單，即找到棋盤上的空餘位置。它的不合理性體現在兩方面：

沒有對結果進行排序，完全是按照數組的遍歷順序的。而Alpha Beta 剪枝的效率是非常依賴節點順序的，這個我們馬上就會講一下。
沒有排除不需要節點。如果能減少一些不必要的節點，那麼其實就是優化了 M^N 中的M，優化效果是非常明顯的。

還是前一章的那張圖，上面可以看到在第二層中，第一個節點的值是3，因為他其實是本層中的極小值，導致後面的兩個節點都可以進行剪枝（這裡第二個節點的第二個孩子也可以剪掉的）。這是最好的一種情況，即在MIN層中極小值是第一個節點，那麼後序的所有節點都可以根據這個極小值進行剪枝，即使極小值不在第一個節點，只要大致能按照從小到大的順序排列，也會剪掉很多節點。如果很不幸，這一層的節點是從大到小排列的，那麼剪枝就完全沒有用。

對於Beta 剪枝也是同樣的道理。所以說Alpha Beta剪枝的效率是取決於每一層節點的順序的。我們肯定是無法精確排序的，因為每一個節點的值並不能直接計算出來，需要遞歸計運算元節點。但是我們依然能對節點進行大致的一個排序。前面說過了，只要有一個大致的排序其實就能很好的提升剪枝效率。

那麼如何排序呢？就是給所有待搜索的位置進行打分，按照分數的高低來排序。注意這個打分演算法是對某一個空位進行打分，在第一張中我們已經有所提到。

有了打分之後，我們就可以按照分數高低進行排序了。

在實現演算法前，我們先回顧一下之前的內容。

struct PicesPos{ int x; int y; int z; chessPicesStatus type; int value;};

每個落子位置都有相應的value，我們要做的就是在list中將棋子按照一定順序排列。

二、實現啟發式搜索

我們採用stl自帶的排序演算法，對每個棋子進行排序：

bool comp(const PicesPos &A, const PicesPos &B){ return A.value > B.value;}

首先，我們按照sort的要求自定義一個排序函數。然後在相應的位置插入排序語句。

...else { int maxVal = -1000000; PicesPosList list = getAvailablePos(board,chessPicesStatus::white); sort(list.begin(),list.end(),comp); for(auto iter = list.begin();iter != list.end();iter++) { board[iter->x][iter->y][iter->z] = chessPicesStatus::white;...

至此，整個搜索演算法就完成啦。

三、主程序

我們的程序已經完成了80%，最後就剩下把他們連接起來了。

int main(int argc, char *argv[]){ QCoreApplication a(argc, argv); ChessBoard cb; cb.init(); cb.printBoard(); int x,y; while(std::cin>>x>>y) { if(!cb.insertPices(x,y,chessPicesStatus::black)) { std::cout<<"error "; continue; } cb.dfs(cb.chessBoard,2); cout<<endl<<"*******Insert x:"<<cb.targetPos.x<<" y:"<<cb.targetPos.y<<" z:" <<cb.targetPos.z<<"********"<<endl<<endl; cb.insertPices(cb.targetPos.x, cb.targetPos.y, chessPicesStatus::white); int whiteScore = cb.getSideScore(cb.chessBoard,chessPicesStatus::white); int blackScore = cb.getSideScore(cb.chessBoard,chessPicesStatus::black); cout<<"whiteScore:"<<whiteScore<<" blackScore:"<<blackScore<<endl; cout<<"whiteTargetPos x:"<<cb.whiteTargetPos.x<<" y:"<<cb.whiteTargetPos.y<< " z:"<<cb.whiteTargetPos.z<<endl; cout<<"blackTargetPos x:"<<cb.blackTargetPos.x<<" y:"<<cb.blackTargetPos.y<< " z:"<<cb.blackTargetPos.z<<endl; int status = cb.isWin(cb.chessBoard); if(status == chessPicesStatus::white) { cb.printBoard(); cout<<"******White Win!******"<<endl; break; } else if(status == chessPicesStatus::black) { cb.printBoard(); cout<<"******Black Win!******"<<endl; break; } else { cb.printBoard(); } } return a.exec();}

我們的四子棋程序就這樣完成了，事實證明根本下不過啊…

本文首發於我的博客：新手立體四子棋AI教程(4)--啟發式搜索與主程序 - Scobbing - 博客園

參考文獻:

http://blog.csdn.net/lihongxun945/article/details/50668253

http://blog.csdn.net/lihongxun945/article/details/50668622

https://www.zhihu.com/question/27221568/answer/127599152

https://www.cnblogs.com/pangxiaodong/archive/2011/05/26/2058864.html

致謝！