潘雨馨，李文彬

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

（5）棋型矩陣chessSituation是一個(gè)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）的進(jìn)攻得分棋型如表2所示（藍(lán)色圓圈標(biāo)記），橫方向是死2，豎方向是死2，撇方向是活3，捺方向是活1。棋型矩陣chess-Situation矩陣的總和等于4。

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

2 核心算法設(shè)計(jì)

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

2.1 勝負(fù)判斷算法

在不考慮禁手的情況下，五子棋勝負(fù)判斷算法主要通過橫、豎、撇、捺四個(gè)方向是否存在五子連珠的情況。勝負(fù)判斷算法判斷每一次落子是否會(huì)導(dǎo)致棋局的輸贏。勝負(fù)判斷算法主要由兩個(gè)子算法組成：獲取落子位置連珠范圍算法getRange()和五子連珠算法cont-Five()。其中g(shù)etRange()取落子位置橫、豎、撇、捺四個(gè)方向的棋子狀態(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;

//主對(duì)角線

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;

//副對(duì)角線

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個(gè)之和

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

return true;

}

return false;

}

2.2 棋型估分算法

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

算法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棋型評(píng)估算法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攻防計(jì)分算法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;

//將得分保存到進(jìn)攻、防守矩陣

if(f==-1)

offScore[i][j]=b;

else

defScore[i][j]=b;

}

2.3 攻防選擇算法

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

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

int max1=0;//最大進(jìn)攻得分

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

int max3=0;//最大進(jìn)攻防守得分正差

int max4=0;//最大進(jìn)攻防守得分負(fù)差

//進(jìn)攻防守得分

max1=scoring(-1);

max2=scoring(1);

//進(jìn)攻防守差距計(jì)分

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];

}

//進(jìn)攻防守選擇

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

if(max2>=max1)

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

else

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

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

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

else

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

}}

3 結(jié)語

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

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

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

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

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

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

[6]史忠植.突破通過機(jī)器進(jìn)行學(xué)習(xí)的極限[J].科學(xué)通報(bào),2016(33):3548-3556.