遺傳演算法用於黑白棋
作者:張新岳 資料來源: http://www.cis.nctu.edu.tw/~gis86540/ 參考資料: 基本遺傳演算法
http://cindy.cis.nctu.edu.tw/EC/GA/index.html 為什麼使用 GA(遺傳演算法) 使用 GA 的原因: 這個程式最主要的，就是在 weight 的決定。
其它就是 game tree 的 minmax search，
藉由 wieght 的和來決定下一步棋的位置。
所以我認為，利用 GA 的演算法，可以在不斷
的比較和演化中，找出較好的 weight 值。 基本演化構想: 我的想法是將 GA 的觀念用在決定Heuristic function
的 weight 值。因此，所要更動的部份並不算太多。
一般來說，只需要了解 heuris.C 和 minmax.C 的做法即可。
heuris.C
#include "heuris.hpp" #include
#include
#include short position_weight[10]={10,2,-5,7,1,1,7,1,1,1};
short weight_of_feature[6]={3,2,1,-1,1,-3}; signed char dir< >[ >< >,>=8) || (jj>=8)) continue;
if ((state_in[ii][jj]==player) && (x) ){
return(TRUE);
}
}
return(FALSE);
} void Heuris::init_pos(void){
int i,j;
for (i=0;i<4;i )
for (j=0;j<4;j ){
if (i<=j){
pos_value[i][j]=position_weight[(j 1)*j/2 i];
} else {
pos_value[i][j]=position_weight[(i 1)*i/2 j];
}
} /* map j 4-7 from 0-3 */
for (i=0;i<4;i )
for (j=4;j<8;j )
pos_value[i][j]=pos_value[i][7-j]; /* map i 4-7 from 0-3 */
for (i=4;i<8;i )
for (j=0;j<8;j )
pos_value[i][j]=pos_value[7-i][j];
} #define WIN_LOSE 2147483550L /* *************************************************************************
Heuristic Function Feature:
0 : position value.
1 : our piece number - opponent piece number. (mobility)
2 : our legal move number.
3 : opponent's legal move number.
4 : number of opponent pieces adjecent to empty square.(possible mobility)
5 : number of empty square adjecent to opponent piece. (possible mobility) ************************************************************************* */
long Heuris::hf(BYTE state< >< >,BYTE move_no)
{
int ww=0,bb=0;
int sum0=0,sum1=0,sum3=0,sum4=0,sum5=0;
int step=0; int i,j,k;
BYTE ii,jj;
BYTE p,x;
int seekp1,seekp2;
// ***** Feature 1: mobility
for (i=0;i<8;i )
for (j=0;j<8;j )
if (state[i][j]==White)
{ sum1 ;
step ;
}
else if (state[i][j]==Black)
{ step ;
sum1--;
} for (i=0;i<8;i )
{
for (j=0;j<8;j )
{
if (state[i][j]==White)
{
for (k=0;k<8;k )
{
ii=i dir[k][0]; jj=j dir[k][1];
if ( (ii<8) &&
(jj<8) &&(state[ii][jj]==Empty) )
{
sum4--;
break;
}
}
// ***** Feature 0: positional value
sum0 =pos_value[i][j];
}
else if (state[i][j]==Black)
{
for (k=0;k<8;k )
{
ii=i dir[k][0];
jj=j dir[k][1];
if ( (ii<8) &&
(jj<8)&&(state[ii][jj]==Empty))
{
sum4 ;
break;
}
}
sum0-=pos_value[i][j];
} else
{
if (check(state,i,j,White))
{
ww ; /* White move number */
}
else if (check(state,i,j,Black))
{
bb ; /* Black move number */
}
else
{
x=p=0;
for (k=0;k<8;k )
{
ii=i dir[k][0]; jj=j dir[k][1];
if ((ii<8) && (jj<8))
{
if ((!x) &&
(state[ii][jj]==Black))
{
x=1;
sum5 ;
if (p) break;
}
else if ((!p) &&
(state[ii][jj]==White))
{
p=1;
sum5--;
if (x) break;
}
}
}
}
}
}
} if ((ww==0) && (bb==0)){
if (sum1>0) return(WIN_LOSE sum1);
else return(-WIN_LOSE sum1);
} p=0;
while (p<16){
if (state[pos[p][0]] [pos[p][1]]!=Empty){
p ;
while( (p&3)>0 ){ /* p % 4 > 0 */
i=pos[p][0];
j=pos[p][1];
if (state[i][j]==White) sum0-=pos_value[i][j];
else if (state[i][j]==Black) sum0 =pos_value[i][j];
p ;
}
} else p =4;
} return((long) (weight[0]*sum0
weight[1]*move_no*sum1/60
(weight[2]*ww weight[3]*bb)/(ww bb 2)
weight[4]*sum4
weight[5]*sum5));
}
minmax.C
#include "minmax.hpp" #ifdef debug
#include
#endif #define MAXDEPTH 20 // Max search depth // TIME_INTERVAL is a constant related how much time shold
// be used in a ply. #define TIME_INTERVAL 3 // Unit: in second extern BYTE my;
extern unsigned int counter;
extern "C"
{
extern int sigblock(int);
extern int sigsetmask(int);
}; #define MINI -2147483647L
// 8 direction of othello
// game play
extern signed char dir< >[ >< >, >![]()
,
>[>=>= >< >, >< >,>>= >< >, >< >;
> >< >,> 如何使用 >網<>路志<>工聯盟---- href="http://www.vista.org.tw">http://www.vista.org.tw
---[ 發問前請先找找舊文章 ]---
發表時間：2002-08-23 10:08:43
IP:61.218.xxx.xxx 未訂閱
