订阅前言隨著計算機技術的發展，人工智能（Artificial intelligence，下文簡稱"AI"）已經成爲世界各國一個熱門的研究方向。對于這一領域的內容，國內起步較晚，目前雖然網絡上各種編程文章很多，但是關于如何編程解決人工智能問題的文章和資料少之又少。
近日，筆者有幸在國外網站上發現了這一篇出色文章，該文通過VC實例來說明如何解決及實現人工智能問題，例子程序雖然相對來說比較簡單，但有一定的代表性，對有愛好研究這一領域的朋友們有借鑒意義。
一、"八迷宮"遊戲簡介
在大學進行AI模塊開發的時候，我就開始著手寫這篇文章，目的是介紹我所了解到的一些讓人感愛好的問題。對于什麽是人工智能，我想沒有任何人願意花費大量時間進行爭論。
當你讀到這裏的時候，推薦你下源代碼，因爲粘貼和拷貝的代碼與源代碼的作用相比是遠遠不及的。在本文中，我將使用一個單人遊戲"八迷宮"作爲一個例子，這個遊戲的規則如下：
有一個3X3的網格，包含1到8這幾個數（因此，有一個格子是空的），最初這8個數的排列是隨機的，例如，下面的排列是一種可能情況：
6 1 7 3 4 5 8 2
遊戲玩家可以向東、南、西、北等方向移動這個空格，移動空格時，空格所占位置的數字將填補到原來空格的位置。例如，對于上圖來說，假如向北移動空格，遊戲的狀態將如下圖所示：
6 1 3 4 7 5 8 2
當遊戲狀態實現如下所示的狀態時，遊戲結束。
1 2 3 8 4 7 6 5
二、解決"八迷宮"問題的方法
解決上述問題的方法主要有以下幾種：
1、Breadth First Search（按照"橫向"原則搜索）.
2、Depth First Search（按照"深度"原則搜索）.
3、Heuristic Search（啓發式搜索）.
4、A* search.
實現這些方法的代碼非常相似，但是它們工作的方式是截然不同的。所有的上述方法都要使用一個鏈表，而且最初的鏈表都只有一個成員，它對應著遊戲網格的最初狀態。這個成員向它所有可能的子狀態進行膨脹（每種移動所産生的結果都被考慮了進去），然後所有這些子狀態都被添加到鏈表中。這種處理將在一個循環中進行持續處理，直到實現目標狀態，也就是說直到遊戲結束爲止。
實現"八迷宮"單人遊戲的僞代碼如下：
Do
Current_Item = Remove_Item_From_List
Child_State_Array = EXPand (Current_State)
Add_to_List(Child_State_Array)
If child_State_Array Holds the solution then IsGameOver = true
Loop while (IsGameOver = false)
這個結構的代碼可以在上述所有的人工智能方法中看到，各種方法的區別僅僅在于它們是如何在鏈表中進行排序。
1、在 breadth first search方法中，各個成員都是按照某一固定的方向被添加到鏈表中，刪除時按相反方向進行。
2、在 depth first search方法中，各個成員的添加和刪除都是在鏈表的同一個方向進行。
3、在heuristic search方法中，各個成員可以在鏈表的任意方向進行添加，然而，在從鏈表中刪除一個成員時，每一個成員被"heuristic"函數進行打分（對于狀態來說，分數越高越接近于最終狀態），得分最高的項目將被從鏈表中刪除。
4、A*方法使用兩個heuristic函數，並將最終的兩個得分加在一起。使用兩個heuristics函數極大地提高了程序發現下步最佳狀態的能力，但是卻降低了程序的運行速度。
其實，三、四方法是第二種方法的延伸和變種，區別僅在于啓發式搜索的方式不同罷了，這一點讀者朋友們可以在後面的代碼中細細體味。實際上"八迷宮"這種遊戲的heuristic函數的可以是這麽一個函數，它計算擁有正確位置的網格個數，或是100-狀態深度。
使用啓發式的搜索有利有弊，在這個例子中，使用啓發式可能使程序的主循環降低10倍速度，然而，它降低了循環的次數，可能從6百萬次降低到了4000次，這節省了內存的負荷，以及例子程序的運行時間。（這提醒了我，我使用的最初的狀態使用了25步解決了問題），這看起來不是很多，但假如沒有啓發式搜索，搜索將1秒鍾處理300兆的內存，除非你使用功能強大的處理機器，（我使用的是1.3G，256兆的機器），否則你可能需要減少結束遊戲所需要的移動次數，要低于10。
三、程序代碼
首先，要聲明的是，遊戲網格在程序中對應著一個擁有10個成員變量的數組，網格每個位置按照從左到右、從上到下的位置排序。對于網格狀態，可實現一個狀態類，它對應著網格的各種狀態，並擁有所有操作網格時所需要的代碼和變量，這個類命名爲CState，代碼如下：
/* 聲明網格中空格所有可能移動的方向，至于爲什麽要包括"NONE"將在後面的代碼中顯現出來；*/
enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST };
// 聲明CState類
class CState {
private:
// 使用1 to 9號索引來對應網格的每個位置, 定義爲 char類型是爲了節省內存；
char Grid[10];
char Depth; //Depth變量對遊戲的最初原始狀態演變到當前狀態所經曆的步數；
//我們需要記錄下父狀態是如何進行移動而得到當前狀態的；
DIRECTION OperatorApplyed;
// 父狀態指針，當程序結束時，我們可以利用它跟蹤所經曆的狀態，從而給出答案；
CState *PrevState;
// 尋找當前網格中的空格位置或某一個具體數字的位置，默認狀態是尋找空格位置；
inline int FindBlank(char Search=0) {
int Blank=1;
while (Grid[Blank] != Search) {
Blank++;
}
return Blank;
}
// 按照規定的方向移動空格；
void MoveBlank(DIRECTION Direction) {
int Blank = FindBlank();
// 我們需要記住本次操作所移動的方向；
OperatorApplyed = Direction;
switch (Direction) {
case NORTH:
Grid[Blank] = Grid[Blank - 3];
Grid[Blank - 3] = 0;
break;
case EAST:
Grid[Blank] = Grid[Blank + 1];
Grid[Blank + 1] = 0;
break;
case SOUTH:
Grid[Blank] = Grid[Blank + 3];
Grid[Blank + 3] = 0;
break;
case WEST:
Grid[Blank] = Grid[Blank - 1];
Grid[Blank - 1] = 0;
break;
}
}
/* 下面的函數將被用于第一種方法的heuristics函數的一部分，它得到兩個索引位置的直角距離，它還用于確定一個數字當前位置與其應該所在位置的直角距離；
int GetDistanceBetween(int Tile1, int Tile2) {
int X1, X2;
int Y1, Y2;
int temp=0;
// 將grid位置轉換爲X,Y坐標；
Y1 = 1;
Y2 = 2;
X1 = Tile1;
X2 = Tile2;
if(Tile1 > 3) { Y1 = 2; X1 = Tile1 - 3; }
if(Tile1 > 6) { Y1 = 3; X1 = Tile1 - 6; }
if(Tile2 > 3) { Y2 = 2; X2 = Tile2 - 3; }
if(Tile2 > 6) { Y2 = 3; X2 = Tile2 - 6; }
//爲了確保距離值爲正說，進行必要的換位處理；
if(Y1 - Y2 < 0) {
temp = Y1;
Y1 = Y2;
Y2 = temp;
}
if(X1 - X2 < 0) {
temp = X1;
X1 = X2;
X2 = temp;
}
return ((Y1 - Y2) + (X1 - X2));
}
public:
// 異常處理；
class ERROR_ILLEGAL_MOVE{};
class ERROR_NO_MORE_DIRECTIONS{};
class ERROR_OUT_OF_BOUNDS{};
//用于heuristic函數；它代表了當前狀態與前一狀態的距離；這個數值越小越好。
int GetDepth() {
return Depth;
}
// CState類構造函數；
CState() {
Depth = 0;
Grid[1] = 6; // for slower machines use 4
Grid[2] = 1; // for slower machines use 1
Grid[3] = 7; // for slower machines use 3
Grid[4] = 3; // for slower machines use 2
Grid[5] = 0; // for slower machines use 0
Grid[6] = 4; // for slower machines use 5
Grid[7] = 5; // for slower machines use 8
Grid[8] = 8; // for slower machines use 7
Grid[9] = 2; // for slower machines use 6
PrevState = 0;
/*由于還沒有以前移動的操作，所以這就是爲什麽我們需要聲明NONE 變量的原因。*/
OperatorApplyed = NONE;
}
void SetPrevState(CState *Set) {
PrevState = Set;
}
CState* GetPrevState() {
return PrevState;
}
// 用于確定移動操作是否合法
bool CanBlankMove(DIRECTION Direction) {
int Blank = FindBlank();
switch (Direction) {
case NORTH:
if (Blank > 3) {
return true;
}
else {
return false;
}
break;
case EAST:
if (Blank != 3 && Blank != 6 && Blank != 9) {
return true;
}
else {
return false;
}
break;
case SOUTH:
if (Blank < 7) {
return true;
}
else {
return false;
}
break;
case WEST:
if (Blank != 1 && Blank != 4 && Blank != 7) {
return true;
}
else {
return false;
}
break;
default:
return false;
break;
}
}
void setgrid(int index, int value) {
Grid[index] = value;
}
/*該函數假如返回"true", 當前狀態將是最終狀態，以前的狀態指針可以用往返退，從而得到解決問題的答案。*/
bool Solution() {
if (Grid[1] == 1 && Grid[2] == 2 && Grid[3] == 3 && Grid[4] == 8 && Grid[5]
== 0 && Grid[6] == 4 && Grid[7] == 7 && Grid[8] == 6 && Grid[9] == 5)
{
return true;
}
else {
return false;
}
}
char GetGridValue(int Index) {
if (Index < 1 Index > 9) {
throw ERROR_OUT_OF_BOUNDS();
}
else {
return Grid[Index];
}
}
// 含一個參數的構造函數；
CState(CState* Init) {
Depth = (Init->GetDepth());
OperatorApplyed = Init->GetLastOperator();
PrevState = Init->GetPrevState();
for (int n=1; n<=9; n++) {
Grid[n] = Init->GetGridValue(n);
}
}
DIRECTION GetLastOperator() {
return OperatorApplyed;
}
// 兩個參數的構造 函數；
CState(CState* Init, DIRECTION Direction) {
int n;
PrevState = Init;
Depth = (Init->GetDepth() + 1);
for (n=1; n<=9; n++) {
Grid[n] = Init->GetGridValue(n);
}
MoveBlank(Direction);
}
// 另外一個heuristic函數，它計算錯誤網格的數量；
int GetWrongTiles() {
return ((Grid[1] != 1) +
(Grid[2] != 2) +
(Grid[3] != 3) +
(Grid[4] != 3) +
(Grid[5] != 3) +
(Grid[6] != 3) +
(Grid[7] != 3) +
(Grid[8] != 3) +
(Grid[9] != 3) +
(Depth )); // 也用于第二種heuristic (A*)的depth
}
/* ManhattanDistance是一個技術術語，它代表了所有當前位置數字與其應該處于的位置的直角距離之和*/
int GetManhattanDistance() {
int Result=0;
Result = GetDistanceBetween(1, FindBlank(1));
Result = Result + GetDistanceBetween(2, FindBlank(2));
Result = Result + GetDistanceBetween(3, FindBlank(3));
Result = Result + GetDistanceBetween(4, FindBlank(8));
Result = Result + GetDistanceBetween(5, FindBlank(0));
Result = Result + GetDistanceBetween(6, FindBlank(4));
Result = Result + GetDistanceBetween(7, FindBlank(7));
Result = Result + GetDistanceBetween(8, FindBlank(6));
Result = Result + GetDistanceBetween(9, FindBlank(5));
Result = Result + Depth;// 也用于第二種heuristic (A*)的depth；
return Result;
}
};
正如你所看到的，這是一個很"巨大"的類，但是，它一點都不複雜，僅僅是一些簡單的數據操作。比較難的部分是跟蹤各種狀態，並按照正確的順序操作它們，這將是我們下面要做的。
這部分與人工智能關系不大，但是人工智能程序不能沒有它。假如你不了解爲什麽我們使用鏈表而不用數組，那末這裏告訴你原因，數組在設計時有固定的尺寸，在運行時不能改變，所以假如程序一開始，你就擁有一個含有6 百萬個Cstates類對象的數組的話，而且這時你還不需要它，那將浪費大量的內存。
鏈表僅在需要時才爲新的對象申請空間，至于它是如何工作的就不具體介紹了，到處都有此類的例子，你只要知道它確實在工作，它是一個可變尺寸的數組。鏈表實際上並不保存狀態，而保存指向各個狀態的指針，這是因爲，鏈表將是一個等待膨脹的狀態隊列，當一個狀態膨脹時，它將從鏈表中刪除，然而，我們需要在內存中保存這個狀態，用于可能發生的回退或是用于報告從最初狀態到解決問題時的解決路徑。
當我們實際編寫主循環代碼時，我們將把膨脹狀態放入到第二個隊列中，這樣我們才能跟蹤它們在那裏，什麽時候從內存中刪除狀態（防止內存泄露） 。
好了，從現在起回到C++代碼，生成一個新的頭文件"Llist.h"，輸入如下代碼：
//列舉鏈表的兩個末端；
enum SIDE { LEFT, RIGHT };
// 鏈表由下面的Link結構對象組成；
strUCt Link {
Link *LeftLink; // 指向鏈表中左端LINK對象的指針；
Link *RightLink; //指向鏈表中右端LINK對象的指針；
CState *Data; // 指向狀態數據的指針；
};
// 鏈表類；
class CLList {
private:
Link* LeFTPointer; // 指向一個永遠是空的，並且是末端的link對象；
Link* RightPointer; //與上面的指針一樣，但方向相反；
double ListLen; // 鏈表的長度；
// 清空內存；
void EmptyUsedMemory() {
CState *temp;
while(!IsListEmpty()) {
temp = Pop(LEFT);
delete temp;
}
}
public:
class ERROR_CANT_POP_EMPTY_LIST{}; // Error Exception
CLList() {
// initialise all private variables
LeftPointer = new Link;
RightPointer = new Link;
ListLen = 0;
LeftPointer->LeftLink = 0;
LeftPointer->RightLink = RightPointer;
RightPointer->RightLink = 0;
RightPointer->LeftLink = LeftPointer;
}
~CLList() {
EmptyUsedMemory();
}
inline double GetListLen() {
return ListLen;
}
inline bool IsListEmpty() {
return (LeftPointer->RightLink == RightPointer);
}
//從鏈表中彈出數據；
CState* Pop(SIDE Side) {
Link ForReturn;
Link* ForDelete;
if (!IsListEmpty()) {
ListLen--;
if (Side == LEFT) {
ForReturn = *(LeftPointer->RightLink);
ForDelete = LeftPointer->RightLink;
LeftPointer->RightLink = ForReturn.RightLink;
ForReturn.RightLink->LeftLink = LeftPointer;
}
else {
ForReturn = *(RightPointer->LeftLink);
ForDelete = RightPointer->LeftLink;
RightPointer->LeftLink = ForReturn.LeftLink;
ForReturn.LeftLink->RightLink = RightPointer;
}
delete ForDelete;
return ForReturn.Data;
}
return 0;
}
//向鏈表中壓入數據
void Push(SIDE Side, CState* What) {
Link* NewLink = new Link;
NewLink->Data = What;
ListLen++;
if (Side == LEFT) {
NewLink->RightLink = LeftPointer->RightLink;
NewLink->LeftLink = LeftPointer;
LeftPointer->RightLink = NewLink;
NewLink->RightLink->LeftLink = NewLink;
}
else {
NewLink->RightLink = RightPointer;
NewLink->LeftLink = RightPointer->LeftLink;
RightPointer->LeftLink = NewLink;
NewLink->LeftLink->RightLink = NewLink;
}
}
//啓發式搜索過程中，從鏈表中搜尋最佳狀態；
CState* PopBestByHeuristics(HEURISTIC heuristic) {
int BestValue=9999;
int Temp=0;
Link* BestState = 0;
Link* Current = LeftPointer;
CState* ForReturn = 0;
if(!IsListEmpty()) {
//啓發式搜索可以使用MANHATTAN_DISTANCE或WrongTile方式來搜尋最佳狀態
while(Current->RightLink != RightPointer) {
Current = Current->RightLink;
if(heuristic == MANHATTAN_DISTANCE) {
Temp = Current->Data->GetManhattanDistance();
}
else {
Temp = Current->Data->GetWrongTiles();
}
if(Temp < BestValue) {
BestValue = Temp;
BestState = Current;
}
}
//從鏈表中刪除最佳狀態；
BestState->RightLink->LeftLink = BestState->LeftLink;
BestState->LeftLink->RightLink = BestState->RightLink;
ForReturn = BestState->Data;
delete BestState;
return ForReturn;
}
return 0;
}
CState* PeekByBestHueristics(HEURISTIC heuristic) {
int BestValue=9999;
int Temp=0;
Link* BestState = 0;
Link* Current = LeftPointer;
CState* ForReturn = 0;
if(!IsListEmpty()) {
// Find BEST State By Wrong tile number heuristic
while(Current->RightLink != RightPointer) {
Current = Current->RightLink;
if(heuristic == MANHATTAN_DISTANCE) {
Temp = Current->Data->GetManhattanDistance();
}
else {
Temp = Current->Data->GetWrongTiles();
}
if(Temp < BestValue) {
BestValue = Temp;
BestState = Current;
}
}
ForReturn = BestState->Data;
return ForReturn;
}
return 0;
}
接下來，創建另外一個頭文件"Eightpuzz.h"，這裏，除了main()，我將放入所有的東西，這些代碼閱讀起來有一定的難度，所以你要堅持住：
void gotoxy(int x, int y); //函數原型，使用光標的xy坐標；
// 枚舉搜索的類型；
enum TYPE {BREADTH_FIRST, DEPTH_FIRST };
// 類舉可能的A* 啓發式方法，第二種啓發式使用深度；
enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES};
// include the header files we are going to need
#include<iostream.h> // for console i/o
#include<windows.h> // for sleep() and gotoxy()
#include"State.h" // for game state class
#include"Llist.h" // for a linked list class
CLList PrevStates; /* 用于跟蹤以前的狀態，程序結束時要及時刪除，以免內存泄露*/
CLList MainQue; // 等待主隊列；
SIDE PushSide;
SIDE PopSide;
// 膨脹函數；
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic);
// 膨脹的步數；
double Expanded = 0;
// 當發現解決方法後，該函數將結果顯示在屏幕上；
void ShowSolution(CState* Solution) {
// 結果是回退得到的，所以實際結果應該是與之反向的，這時候可以使用後入先出的方法；
CLList Reverse;
bool EndLoop=false;
while(!EndLoop) {
Reverse.Push(LEFT, Solution);
if(Solution->GetPrevState() != 0) {
Solution = Solution->GetPrevState();
}
else {
EndLoop = true;
}
}
int NewLine = 0;
CState *Temp;
cout << "\n";
while(!Reverse.IsListEmpty()) {
Temp = Reverse.Pop(LEFT);
NewLine++;
if(NewLine > 10) { cout << "\n"; NewLine=0;}
switch(Temp->GetLastOperator()) {
case NORTH:
cout << "North, ";
break;
case EAST:
cout << "East, ";
break;
case SOUTH:
cout << "South, ";
break;
case WEST:
cout << "West, ";
break;
}
}
cout << "\n\n" << "Expanded: " << Expanded << endl;
}
}
// 設置控制台i/o x,y坐標
void gotoxy(int x, int y) {
// SET CONSOLE CURSOR POSITION.
COORD coord = {x,y};
HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(handle,coord);
}
// 爲主循環做預備；
void GeneralSearch(TYPE Type, HEURISTIC heuristic) {
CState *Solution;
int DepthLimit=0;
switch(heuristic) {
case NOT_USED:
// Breadth First Queing Type
if(Type == BREADTH_FIRST) {
PushSide = RIGHT;
PopSide = LEFT;
}
else {
// Depth First Search
cout << "Enter a Depth Limit :";
cin >> DepthLimit;
PushSide = RIGHT;
PopSide = RIGHT;
}
break;
case MANHATTAN_DISTANCE:
PushSide = RIGHT;
PopSide = RIGHT;
break;
case WRONG_TILES:
PushSide = RIGHT;
PopSide = RIGHT;
}
//將最初的狀態放入鏈表中；
MainQue.Push(PushSide, new CState());
//調用主循環
Solution = GeneralExpand(DepthLimit, heuristic);
// returns pointer to soution.
// or null pointer (failure)
if(Solution != 0) {
cout << "FOUND SOLUTION!" << endl;
ShowSolution(Solution);
cout << "DONE" << endl;
}
else {
//Fail
cout << "FAIL" << endl;
}
}
// 主循環函數(YEP, it BITES !)
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic) {
CState *CurrentState = 0;
CState *TempState = 0;
int LastDepth=-1;
if(PushSide == PopSide) {cout << "THINKING...please wait." << endl;}
// Main loop
while(!MainQue.IsListEmpty()) {
if(heuristic == NOT_USED) {
CurrentState = MainQue.Pop(PopSide);
}
else {
CurrentState = MainQue.PopBestByHeuristics(heuristic);
}
PrevStates.Push(RIGHT, CurrentState);
//對取出的狀態保持跟蹤(需要防止內存)
/*可以讓用戶規定結束遊戲所需要移動的最大步數，這僅限于"breadth first only"方法*/
if(LastDepth < CurrentState->GetDepth() && PushSide != PopSide) {
LastDepth = CurrentState->GetDepth();
cout << "EXPANDING LEVEL " << LastDepth << endl;
}
// 假如當前節點沒有超出depth限制
if((CurrentState->GetDepth() < DepthLimit) (DepthLimit == 0 )) {
if((CurrentState->CanBlankMove(NORTH)) && (CurrentState->GetLastOperator() != SOUTH)) {
TempState = new CState(CurrentState, NORTH);
MainQue.Push(PushSide, TempState);
Expanded++;
if(TempState->Solution()) {
return TempState;
}
}
if((CurrentState->CanBlankMove(EAST)) && (CurrentState->GetLastOperator() != WEST)) {
TempState = new CState(CurrentState, EAST);
MainQue.Push(PushSide, TempState);
Expanded++;
if(TempState->Solution()) {
return TempState;
}
}
if((CurrentState->CanBlankMove(SOUTH)) && (CurrentState->GetLastOperator() != NORTH)) {
TempState = new CState(CurrentState, SOUTH);
MainQue.Push(PushSide, TempState);
Expanded++;
if(TempState->Solution()) {
return TempState;
}
}
if((CurrentState->CanBlankMove(WEST)) && (CurrentState->GetLastOperator() != EAST)) {
TempState = new CState(CurrentState, WEST);
MainQue.Push(PushSide, TempState);
Expanded++;
if(TempState->Solution()) {
return TempState;
}
}
}
}
return 0;
}
下面是主文件"EightPuzz.cpp" 的代碼：
#include"Eightpuzz.h"
int main() {
char Choice=0;
cout << "Choose Search Method...\n"
<< " [1] Blind Breadth First Search\n"
<< " [2] Blind Depth First Search\n"
<< " [3] A*(Tiles in the wrong position)\n"
<< " [4] A*(Manhattan Distance)\n" << endl;
cin >> Choice;
switch(Choice) {
case 』1』:
// call Blind Breadth First Search
GeneralSearch(BREADTH_FIRST, NOT_USED);
break;
case 』2』:
// call Blind Depth First Search
GeneralSearch(DEPTH_FIRST, NOT_USED);
break;
case 』3』:
// call A* with wrong tiles heuristic
GeneralSearch(DEPTH_FIRST, WRONG_TILES);
break;
case 』4』:
// call A* with manhatten heuristic
GeneralSearch(DEPTH_FIRST, MANHATTAN_DISTANCE);
break;
}
return 0;
}
正如我前面所說的，還是推薦你看完本文中的代碼，下載程序的源代碼，並用VC打開，仔細看一看整個程序的結構及流程。通過這個例子程序，你應該明白，編寫一個AI程序，所需要做的是：
1、 一個存儲狀態的方法；
2、 一個膨脹狀態的方法；
3、 一個回退到原始狀態的方法；
4、 一個排序狀態的方法；
5、 一個給狀態評分的函數；
6、 一個主循環，將一個狀態從鏈表中移出，並將其所有的子狀態添加到鏈表中；
上面的每個步驟都很簡單，但將它們組合在一起，並使它易讀易懂卻不那麽輕易了。
