黑白棋規(guī)則介紹
黑白棋是由黑方和白方兩人進行的益智游戲。棋盤為N×N方格，黑白棋總共使用N2個棋子，每個棋子分正反兩面，分別是黑色和白色。輪到一方下棋時，必須把棋下在與對方棋子相鄰的空位上，要求所下的棋子和原有的已方棋子夾住對方的至少一個棋子(橫豎斜夾均可)，然后把被夾住的子變成己方的顏色(也叫吃子)。下棋過程中，任何棋子既不會從棋盤上拿走，也不會從一個格子移到另一個格子,吃子時，不會發(fā)生連鎖反應，吃進的棋子不能再夾吃其他的子。當雙方都無棋可下，或者方格全部占滿后，棋局結束，子多的一方為勝方。
黑白棋人工智能的實現(xiàn)
我們這里取棋盤大小為10×10個方格，用數組int state[10][10]來表示棋盤的狀態(tài)，其中0表示方格為空，－1表示用黑方的棋，1表示白方的棋。
在10×10的棋盤上，除了那些已經有子的地方不能走子外，那些不能吃子的點也不能走。如何判斷某個點（x, y）能不能走子呢？通過分析黑白棋的規(guī)則我們知道，在這一個方格上的八個方向的任何一個方向上只要滿足：在這個方向與之相鄰的有連續(xù)若干個對方的棋子，接著有一個己方的子，我們就可以肯定這一點能夠走子。所以我定義了一個數組int dirstate[8]（數組從右逆時針開始，如dirstate[0]表示右，dirstate[1]表示右上，以此類推）來表示個方向的狀態(tài),值1表示在這個方向上可以吃掉對方的子，值0則表示不能，同時定義一個函數movedir(int x,int y,int mover)來判斷各方向的狀態(tài)，函數movedir的具體實現(xiàn)見源代碼，這里以右方向為例說明，其他各個方向類似，右方向的判斷可以用以下語句實現(xiàn)：
int tx=x+1,ty=y,step=0;//tx,ty分別用來表示右方向各點在數組中的索引
dirstate[0]=0;//初始化為不能吃子
while(1)
{
if(tx>9) break;//處于邊界，退出循環(huán)，該方向不能吃子
if(state[ty][tx]==0) break; //空子，退出循環(huán)，該方向不能吃子
if(state[ty][tx]!=mover) step++;//（tx,ty）所在的方格上的棋不一樣，step加1，有連
//續(xù)step個對方的棋子與（x，y）上的棋相鄰
else {if(step>0) dirstate[0]=1;break;}// （tx,ty）所在的方格上的棋一樣，同時在(tx,ty)
//和(x,y)之間如果有連續(xù)step個對方的棋子，則、
//表示該方向上可以吃子，修改dirstate[0]狀態(tài)。
tx++;
}
我們需要讓計算機自己決定下一步走哪兒，必須讓它知道走哪兒對它自己最有利，解決這個問題的基本思想就是對這個有利進行量化，我們有一個非常簡單的方法就可以實現(xiàn)這個量化，那就是下該子能吃掉對方子的數目為該步的有利值，為了讓計算機算出該值，我定義了一個int movetotal(int x,int y,int mover)函數，該函數返回該步能吃掉對方的子數，他的主要實現(xiàn)跟movedir類似，也是對各個方向進行統(tǒng)計，因此也可以用此函數來判斷該位置能不能放子：
int total=0;//total用來統(tǒng)計總的能夠吃掉對方的子數，函數最后返回此值
int tx=x+1,ty=y,step=0;
while(1)
{
if(tx>9) break;
if(state[ty][tx]==0) break;
if(state[ty][tx]!=mover) step++;
else {if(step>0) total+=step;break;}//與movedir不同的地方，這里將step加到
//total這個統(tǒng)計整數里面
tx++;
}
有了這些函數，電腦就可以用這個有利值選擇一個位置下棋，因此接下來我們就要考慮黑白棋的下棋后棋盤狀態(tài)的變化了。我們知道，當我們在（x，y）這個位置上下一個棋后，就會引起這個位置的八個方向上的符合條件（棋子和原有的已方棋子夾住對方的至少一個棋子）的方格上棋子狀態(tài)的改變。為此我們定義了函數move (int x,int y,int mover)實現(xiàn)這個功能，其中x，y為下棋的位置， mover為-1表示己方用黑棋，1表示己方用白棋，函數move的主要實現(xiàn)如下（以右方向為例，詳細請看源代碼）：
movedir(x,y,mover);//調用movedir函數，得到dirstate數組表示各個方向的狀態(tài)
state[y][x]=mover;//在該位置上下棋，改變棋盤在該位置的狀態(tài)，將空狀態(tài)改為mover
int tx=x,ty=y;
if(dirstate[0]==1)//為1則表示該方向可以吃掉對方的棋子，將已方棋子夾住對方棋子改
//為己方
{
while(state[ty][++tx]==mover*(-1))//循環(huán)直到遇到己方的棋子
{
state[ty][tx]=mover;//將對方的棋子改為己方的棋子
}
}
至此，一個非常簡單的黑白棋就已經完成了，看到這里聰明的你當然會說，這樣的電腦不是太容易贏了，沒錯，如果只看到當前能夠吃掉對方子的個數最大數就下認為該步是最優(yōu)的話，那明顯是不對的，因為下一步對方有可能吃掉你更多的子，這樣就得不償失，所以我們必須增加一些算法，使計算機得到的位置接近最優(yōu)，我們就必須判斷該步后的幾步，預測對方可能下的位置，計算機的高速運算能力和高存儲能力為我們提供了實現(xiàn)的條件，這里我們采用了深度優(yōu)先的方法，生成一棵解樹，找出比較接近最優(yōu)的解，預測的步數就是深度優(yōu)先方法的深度，也就是解樹的深度，這就要看具體計算機的速度內存的大小，深度越深，得到的也就越接近最優(yōu)解，這里不可能遞推太深，不然計算機每下一步會慢的你無法忍受，同時內存的限制了你遞推的深度。遞推函數的實現(xiàn)如下：
1. int getbenefit (int x,int y,int mover,int n)
2. {
3. int benefit=0;
4. benefit=movetotal(x,y,mover);
5. if(benefit<=0)return 0;
6. if(n==1)
7. {
8. return benefit;
9. }
10. else
11. {
12. int tempstate[10][10];
13. int good[10][10];
14. int i=0,j=0;
15. for(i=0;i<10;i++)
16. {
17. for(j=0;j<10;j++)
18. {
19. tempstate[i][j]=state[i][j];
20. good[i][j]=0;
21. }
22. }
23. move(x,y,mover);
24. mover=mover*(-1);
25. n-=1;
26. for(i=0;i<10;i++)
27. {
28. for(j=0;j<10;j++)
29. {
30. if(state[i][j]!=0)continue;
31. if(movetotal(j,i,mover)>0)
32. {
33. if(i==0&&j==0||i==9&&j==0||i==0&&j==9||i==9&&j==9)
34. {
35. if(mover==computermover)
36. benefit+=n+5;
37. if(mover!=computermover)
38. benefit-=n-5;
39. }
40. good[i][j]=getbenefit(j,i,mover,n);
41. }
42. }
43. }
44. benefit=findmax(good,10,10)*mover+benefit;
45. for(i=0;i<10;i++)
46. {
47. for(j=0;j<10;j++)
48. {
49. state[i][j]=tempstate[i][j];
50. }
51. }
52. return benefit;
53. }
54. }
函數說明：
1：函數的參數中（x，y）表示當前要下的位置，mover為-1表示己方用黑棋，1表示己方用白棋，n為遞推的深度。
4～5：計算下（x，y）能夠吃掉對方棋子的數放到benefit里，并判斷（x，y）能不能放子，benefit大于0表示可以，否則退出遞推函數，返回0表示不能放子。
6～11：判斷是否達到所要求的遞推深度，當n等于1是表示完成遞推，返回該位置能吃掉對方的棋子數benefit，否則繼續(xù)進行遞推。
12～22：數組int tempstate[10][10]對當前棋盤的狀態(tài)進行備份，使遞推函數退出時可以恢復原來的棋盤狀態(tài)，數組int good[10][10]用來存儲下該子后對方在棋盤各個位置上下棋分別能吃掉己方的棋子數，初始化為0。
23：在（x，y）位置上下棋，調用move函數實現(xiàn)，改變棋盤的狀態(tài)，以前進行遞推運算對方下一步的吃掉己方的子數，當然這種改變是暫時的，在最后還要用數組tempstate備份的棋盤狀態(tài)進行恢復。
24～25：改變下棋方，同時遞推深度減一
26～43：對棋盤可以下棋位置進行遞推調用getbenefit函數，這是本函數的主要部分，將各個位置的調用getbenefit函數的返回值保存到good數組上，以便找到對方能夠吃掉己方最多子的位置。
33～39：這是對本智能函數的一個優(yōu)化部分，考慮到占領四個角對整盤棋起著至關重要的作用，所以只要可以占領四個角，便對該位置增加或減少（看當前遞推是處于遞推己方還是對方）一個權值，在這里我將這個權值設為n＋5，與遞推的深度有關，越深表示最后下到那里的機會越小，所以權值就越小。
44：用findmax求出good數組中最大的值，乘以mover的作用就是要根據當前遞推是處于遞推黑方還是白方來判斷good數組中表示的是黑方還是白方的加權值，用mover可以巧妙的分辨出當前遞推是處于遞推黑方還是白方，這里mover已經在24行那里改變了，所以good得到的是與前面用movetotal函數得到benefit值相反。
45～51：恢復棋盤到進入遞推函數前的狀態(tài)。
至此，該程序的核心部分已經完成，整合上面的函數，我們可以得到一個電腦選擇位置下棋子的函數computerAI ()，他的實現(xiàn)如下：
1. int i=0,j=0,mx=0,my=0,max;
2. int benefit[10][10];
3. for(i=0;i<10;i++)
4. {
5. for(j=0;j<10;j++)
6. {
7. benefit[i][j]=-1000;
8. }
9. }
10. for(i=0;i<10;i++)
11. {
12. for(j=0;j<10;j++)
13. {
14. if(state[i][j]!=0)continue;
15. if(i==0&&j==0||i==0&&j==9||i==9&&j==0||i==9&&j==9)
16. {
17. if(movetotal(j,i,computermover)>0)
18. {
19. move(j,i,computermover);
20. return;
21. }
22. }
23. if(movetotal(j,i,computermover)>0)
24. benefit[i][j]=getbenefit(j,i,computermover,AI);
25. if(i==1||i==8||j==1||j==8)benefit[i][j]+=1;
26. }
27. }
28. max=benefit[0][0];
29. for(i=0;i<10;i++)
30. {
31. for(j=0;j<10;j++)
32. {
33. if(benefit[i][j]>max)
34. {
35. max=benefit[i][j];
36. mx=j;
37. my=i;
38. }
39. }
40. }
41. if(movetotal(mx,my,computermover)>0)
42. move(mx,my,computermover);
函數說明：
2～9：數組benefit[10][10]用來存放各點所能得到的權值，類似于getbenefit的good數組，初始化為一個比較大的負值，這里取－1000，因為權值不會大于1000。
10～27：循環(huán)嘗試各個位置，分別調用getbenefit函數進行遞推，將各個位置上得到的值存放到benefit數組。
14：當前點已經有棋，不用考慮，進行下一循環(huán)。
15～22：如果當前可以下四個對角點，則下對角點，不用調用遞推函數。
23～24：當前位置可以下，則調用getbenefit遞推函數進行遞推，所得結果送到數組benefit相應的位置上。
28～40：查找數組benefit上的最大值，并將最大值的位置放在mx和my上。
41～42：下棋，調用move函數實現(xiàn)
得到computerAI ()函數，本程序基本完成了，對于黑白棋的界面則可以根據state數組畫出棋盤。當然這樣的AI還是不夠的，一些比較簡單的陷阱就可以讓電腦毫不猶豫的跳進去，同時通過預測未來幾步，計算機可以相應的求出最佳解。但是由于“預測步數”不可能無限制擴大，我們得到的解永遠是近似的。為了補償這種缺憾，我們可以把我們人類思考而得來的一些規(guī)律性的東西告訴電腦，使它在理性思考的同時把經驗考慮進去，讓它更聰明一些、更接近人類思維一些，在我的源代碼里面就有一些這樣的經驗函數，通過與寫好的黑白棋程序進行對弈，你就可以發(fā)現(xiàn)他的不足，然后分析這些不足的地方，將他們寫成經驗函數，每當遇到這些情況，就對他增加或減少一個權值，這樣，這個程序也會隨著你的經驗函數的增加AI越來越厲害。更深的考慮，你可以為此建立一個數據庫，將一些棋局存進去，這樣你的程序會隨著下的次數越多，AI也就越厲害，但實現(xiàn)起來已經出了本文要討論的了，有興趣的可以看看人工智能關于專家系統(tǒng)方面的介紹。
黑白棋程序源代碼的組成
主要由兩個類加一個主程序實現(xiàn)，分別是Chess類和Show類。
Chess類實現(xiàn)有關棋盤狀態(tài)，人工智能函數，經驗函數的封裝，主要組成如下：
class CHESS
{
public:
CHESS(int x,int y);//構造函數，x表示電腦用黑子還是白紙，y是所使用的人工
//智能函數選擇
~CHESS();//析構函數
void move(int x,int y,int mover);//下棋，作用具體見上面
void humanmove(int x,int y);//游戲者下棋，將游戲者所要下的位置傳到此函數
int movetotal(int x,int y,int mover);//吃子總數，具體見上
int getbenefit(int x,int y,int mover,int n);//遞推函數，具體見上
void movedir(int x,int y,int mover);//判斷各個方向的狀態(tài)到dirstate數組，具體
//見上
int dirstate[8];// 各個方向的狀態(tài)
int computermover;//計算機下黑子還是白子，－1黑子，1白子
int AI; //所要使用的AI的等級
int state[10][10]; //棋盤的狀態(tài)
private:
int findmax(int data[][10],int xsize,int ysize);//查找data數組的最大值
void computerAI(char a);//根據a的值，選擇下面四個AI函數之一
void computerAI1();//第一級AI函數
void computerAI2();//第二級AI函數
void computerAI3();//第三級AI函數
void computerAI4();//第四級AI函數
int addAI6(int x,int y,int mover); //經驗函數
int addAI5(int x,int y); //經驗函數
int addAI4(int x,int y,int mover); //經驗函數
int addAI3(int x,int y); //經驗函數
int addAI2(int x,int y); //經驗函數
int addAI(int x,int y);//經驗函數
int checkbd(int x,int y);//邊界經驗函數
int checkbd2(int x,int y); //邊界經驗函數
int checkbd3(int x,int y,int mover); //邊界經驗函數
};
Show類主要是封裝黑白棋的界面實現(xiàn)，具體如下：
class SHOW
{
public:
void move();//封裝了游戲者選擇要下棋時位置變化動畫
void draw(int data[][10]);//根據data數組畫棋盤上的子
void drawbk(int computermover);//畫背景和棋盤方格
void drawbkrect(int x,int y,int width,int height);//畫背景矩形
SHOW();
virtual ~SHOW();
int act;
int x,y;
void drawcircle(int x,int y,int mover);//封裝了畫圓函數
void drawrect(int x,int y);//封裝了畫矩形函數
};
主程序則由一個循環(huán)實現(xiàn)，在里面實現(xiàn)功能選擇與用戶交互，具體可以看源程序。
|
