一種基于攻防估分算法的智能五子棋游戲設(shè)計

潘雨馨，李文彬

（1.岳陽市一中，岳陽414006；2.湖南理工學院，岳陽414006）

0 引言

五子棋是一種兩人對弈的純策略型棋類游戲，是世界智力運動會競技項目之一，是一種增強思維、趣味橫生、大眾喜愛的智力游戲。五子棋對弈雙方分別使用黑白兩色的棋子，下在棋盤直線與橫線的交叉點上，先形成5子連線者獲勝[1]。

設(shè)計和研發(fā)智能型五子棋游戲程序，可以在休閑時為人們提供對戰(zhàn)的樂趣，可以幫助新手在一定程度上提高棋藝。目前，關(guān)于五子棋游戲的智能算法主要有：估分函數(shù)[2-3]、博弈樹搜索[4-5]、深度學習[6]等。其中，博弈樹是基于未來可能的所有或部分棋局進行搜索而做出有利的判斷，由于博弈樹的規(guī)模龐大，需要設(shè)計復雜的算法進行狀態(tài)空間剪枝。深度學習則是通過與海量棋局中進行強化學習，從而使程序具備不斷改進的自我學習能力，但學習過程需要先進的高性能計算設(shè)備的支持。而估分函數(shù)主要是基于當前棋局的有利形勢判斷進行落子決策，計算量較小，易于實現(xiàn)，非常適合大眾型智力游戲設(shè)計。

現(xiàn)有基于估分函數(shù)的五子棋算法，主要通過棋型判斷計算攻防得分，并根據(jù)攻防得分的大小確定進攻或防守的落子位置。這類算法往往在攻防策略選擇上比較單一，很容易被對手適應。本文提出基于多種攻防策略的估分選擇算法，考慮在棋型分值較高時，選擇最有利進攻或防守位置的落子；在整體棋型分值較低時，選擇在攻防差距最大的位置落子，使棋局朝最有利于AI方發(fā)展。

1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

AI版五子棋游戲的主要數(shù)據(jù)結(jié)構(gòu)包括五個矩陣：棋盤狀態(tài)矩陣currBoard、進攻得分矩陣offScore、防守得分矩陣defScore、連子空位矩陣conBlank、棋型矩陣chessSituation。其中：

（1）棋盤狀態(tài)矩陣currBoard是一個15×15的二維矩陣，每個元素的值表示棋盤上每個下棋點的狀態(tài)：1表示黑棋，-1表示白棋，0表示沒有棋子。

圖1 五子棋游戲棋盤結(jié)構(gòu)

（2）進攻得分矩陣offScore是一個15×15的二維矩陣，記錄AI方的進攻得分，每個元素的值表示AI方在該位置放置棋子的得分。若該位置已有棋子，則置為0。

（3）防守得分矩陣offScore是一個15×15的二維矩陣，記錄AI方的防守得分，每個元素的值表示棋手方在該位置放置棋子的得分。若該位置已有棋子，則置為0。

（4）連子空位矩陣conBlank是一個4×3的二維矩陣，記錄從當前空位沿橫、豎、撇、捺四個方向的連子和空位情況。例如，假設(shè)AI方是白棋，位置（4,4）的棋型說明如表1所示（紅色圓圈標記），在行（橫）方向，它的左空位數(shù)是3，連子數(shù)是2，右空位數(shù)是1。

表1 位置(4,4)的連子和空位情況

（5）棋型矩陣chessSituation是一個2×5的二維矩陣，記錄某位置成5、活4、死4、活3等棋型情況。五子棋的得分棋型大致可以分為以下幾種：

成5：五子連珠。

活4：兩邊均不被攔截的四子連珠。

死4：一邊被攔截的四子連珠。

活3：兩邊均不被攔截的三字連珠。

死3：一邊被攔截的三字連珠，且另一邊空位數(shù)不小于2。

活2：兩邊均不被攔截的二子連珠，且兩邊空位總數(shù)不小于3。

死2：一邊被攔截的二子連珠，且另一邊空位數(shù)不小于3。

活1：兩邊均不被攔截的單子，且兩邊空位總數(shù)不小于4。

死1：一邊被攔截的單子，且另一邊空位數(shù)不小于4。

例如，假設(shè)AI方是白棋，位置（6,6）的進攻得分棋型如表2所示（藍色圓圈標記），橫方向是死2，豎方向是死2，撇方向是活3，捺方向是活1。棋型矩陣chess-Situation矩陣的總和等于4。

表2 位置(6,6)的得分棋型情況

2 核心算法設(shè)計

AI版五子棋游戲的核心算法包括：勝負判斷算法、棋型估分算法和攻防選擇算法。

2.1 勝負判斷算法

在不考慮禁手的情況下，五子棋勝負判斷算法主要通過橫、豎、撇、捺四個方向是否存在五子連珠的情況。勝負判斷算法判斷每一次落子是否會導致棋局的輸贏。勝負判斷算法主要由兩個子算法組成：獲取落子位置連珠范圍算法getRange()和五子連珠算法cont-Five()。其中g(shù)etRange()取落子位置橫、豎、撇、捺四個方向的棋子狀態(tài)情況（用一維數(shù)組表示）；contFive()判斷是否存在五子連珠。

算法1落子位置連珠范圍算法getRange()public boolean getRange(int row,int col){

//行

if(contFive(currBoard[row]))

return true;

//列

int b[]=new int[15];

for(int k=0,i=0;i

b[k]=currBoard[i][col];

if(contFive(b))

return true;

//主對角線

int c[]=new int[15];

for(int k=0,i=Math.max(0,row-col),j=Math.max(0,col-row);i

c[k]=currBoard[i][j];

if(contFive(c))

return true;

//副對角線

int d[]=new int[15];

for(int k=0,i=Math.min(14,row+col),j=Math.max(0,col+row-14);i>=0&&j

d[k]=currBoard[i][j];

if(contFive(d))

return true;

return false;

}

算法2五子連珠算法contFive()public boolean contFive(int[]a){

for(int i=0;i<=a.length-5;i++){

int s=0;

for(int k=0;k<5;k++)

s=s+a[i+k];//連續(xù)5個之和

if(s==5||s==-5)

return true;

}

return false;

}

2.2 棋型估分算法

棋型估分算法計算空子位置的攻、防得分，給AI程序提供落子參考。棋型估分算法主要由三個子算法組成：連子空位計算calc_conBlank()、棋型評估算法calc_situation()、攻防計分算法scoring()。其中，calc_conBlank()計算落子位置的連子情況及兩端的空位情況；calc_situation()計算沿橫、豎、撇、捺四個方向出現(xiàn)的成5、活4、死4等各種棋型的統(tǒng)計情況；scoring()根據(jù)落子位置的棋型統(tǒng)計情況計算該位置的進攻、防守得分。

算法3連子空位算法calc_conBlank()

public void calc_conBlank(int f){//f表示棋子類型

if(currBoard[i][j]==0){//行

int k=1;//左

temp[0][0]=1;//temp表示連子空位矩陣con-Blank

while(j-k>=0&&currBoard[i][j-k]==f){//連子

temp[0][0]++;

k++;

}

while(j-k>=0&&(currBoard[i][j-k]==0||currBoard[i][j-k]==f)){//左空位或同色棋子

temp[0][1]++;

k++;

}

k=1;

while(j+k<15&&currBoard[i][j+k]==f){

temp[0][0]++;

k++;

}

while(j+k<15&&(currBoard[i][j+k]==0

||currBoard[i][j+k]==f)){

temp[0][2]++;

k++;

}

}

}

算法4棋型評估算法calc_situation()public void calc_situation(int[][]temp){

for(int h=0;h<4;h++){

if(temp[h][0]>=5)

s[4][0]++;

else if(temp[h][0]==4&&(temp[h][1]>=1&&temp[h][2]>=1))

s[3][1]++;//活4

else if(temp[h][0]==4&&(temp[h][1]>=1||temp[h][2]>=1))

s[3][0]++;//死4

else if(temp[h][0]==3&&(temp[h][1]>=1&&temp[h][2]>=1))

s[2][1]++;//活3

else if(temp[h][0]==3&&(temp[h][1]+temp[h][2]>=2))

s[2][0]++;//死3

else if(temp[h][0]==2&&(temp[h][1]+temp[h][2]>=3&&

temp[h][1]>=1&&temp[h][2]>=1))

s[1][1]++;//活2

else if(temp[h][0]==2&&temp[h][1]+temp[h][2]>=3)

s[1][0]++;//死2

else if(temp[h][0]==1&&(temp[h][1]>=3&&temp[h][2]>=3))

s[0][1]++;//兩端空位均超過3的單子

else if(temp[h][0]==1&&temp[h][1]+temp[h][2]>=4)

s[0][0]++;//單子}}

算法5攻防計分算法scoring()public void scoring(int f){

if(s[4][0]>=1)//成5

b=100;

else if(s[3][1]>=1||s[3][0]>=2||s[2][0]>=2||(s[3][0]>=1&&s[2][1]>=1))

b=90;

else if(s[2][1]==1&&s[2][0]>=1)//活 3死 3

b=80;

else if(s[3][0]==1)//死4

b=70;

else if(s[2][1]==1)//活3

b=60;

else if(s[1][1]>=2)//雙活2

b=50;

else if(s[2][0]==1)//死3

b=40;

else if(s[1][1]==1)

b=30;

else if(s[1][0]>=1)

b=20;

else if(s[0][1]>=1)

b=15;

else if(s[0][0]>=1)

b=5;

//將得分保存到進攻、防守矩陣

if(f==-1)

offScore[i][j]=b;

else

defScore[i][j]=b;

}

2.3 攻防選擇算法

攻防選擇算法off_def_choice()提供了4種策略進行攻防選擇：在最大進攻得分位置落子、在最大防守得分位置落子、在最大攻防得分正差位置落子、在最大攻防得分負差位置落子。當最大攻防得分大于等于80時，根據(jù)最大攻防得分的大小，選擇在最大進攻或防守位置落子。當最大攻防得分小于80時，根據(jù)最大攻防正負差得分的大小，選擇在最大正差或最大負差位置落子。

算法6攻防選擇算法off_def_choice()public void off_def_choice(){

int max1=0;//最大進攻得分

int max2=0;//最大防守得分

int max3=0;//最大進攻防守得分正差

int max4=0;//最大進攻防守得分負差

//進攻防守得分

max1=scoring(-1);

max2=scoring(1);

//進攻防守差距計分

int[][]gap=new int[15][15];

for(int i=0;i<15;i++)

for(int j=0;j<15;j++){

gap[i][j]=offScore[i][j]-defScore[i][j];

if(gap[i][j]>max3)max3=gap[i][j];

if(gap[i][j]

max4=gap[i][j];

}

//進攻防守選擇

if(max2>=80||max1>=80){

if(max2>=max1)

System.out.println("在最大防守得分位置落子");

else

System.out.println("在最大進攻得分位置落子");

}else if(Math.abs(max3)>Math.abs(max4))

System.out.println("在最大攻防得分正差位置落子");

else

System.out.println("在最大攻防得分負差位置落子");

}}

3 結(jié)語

本文針對五子棋游戲，設(shè)計了一種基于攻防得分的智能評估算法。對每個可落子的位置，計算該位置連子數(shù)和兩端空位數(shù)，統(tǒng)計該位置出現(xiàn)成5、活4等各種棋型的情況，進一步計算該位置進攻和防守得分，并設(shè)計攻防選擇四種策略，指導AI程序完成落子。與其他基于單一攻防策略的算法相比，該算法具有更好的棋局判斷能力。

[1]劉瑞.五子棋人工智能算法設(shè)計與實現(xiàn)[D].華南理工大學,2012.

[2]徐建.五子棋的一種價值的估算[J].智能計算機與應用,2016,6(5):90-92.

[3]卓明敏,黃正亮,廖小于.五子棋級數(shù)算法[J].福建電腦,2012,28(4):94-96.

[4]張明亮,吳俊,李凡長.五子棋機器博弈系統(tǒng)評估函數(shù)的設(shè)計[J].計算機應用,2012,32(7):1969-1972.

[5]王長飛,蔡強,李海生.智能五子棋算法的設(shè)計實現(xiàn)[J].系統(tǒng)仿真學報,2009,21(4):1051-1054.

[6]史忠植.突破通過機器進行學習的極限[J].科學通報,2016(33):3548-3556.