Previous Next Version 4.5
The evaluation consists of two kind of terms. Permanent terms are functions of the position, like material. These can be differentially updated. Transient terms are bonuses or penalties given to encourage or prevent certain behavior. For instance, in the middle game we could put a penalty on King moves. This is not entirely consistent: if the same position can be reached through 2 King moves (say after checks) or 3 King moves (with the opponent also wasting one move in checking) that position would be considered better when it is reached by the first sequence. In a consistent evaluation the score is only dependent on position, not on history. It would not be so easy, though, to make a function of position that discourages King moves, or moving the same piece twice in the opening.
In Micro-Max the evaluation is updated differentially all the way from the start position. The inconsistent transient terms could accumulate to a large value over the game, leading to undesired effects. Even a small penalty on King moves could raise the evaluation to a large score if one of the opponents was forced to do only King moves (because he has just King and some blocked Pawns), while the other can aimlessly push his Bishop around. If the game lasts long enough, the imbalance created by this can raise the score even above that for checkmate, so that the winning side will start to avoid the checkmate because he thinks it a bad deal, and judge it better to pursue the advantage of forcing more King moves out of the opponent!
To avoid such problems, the update of the evaluation score is split in two parts.
The permanent part i is added to the evaluation e on any move,
both in the search tree and at the game level.
It consists only of material, acording to the usual 1:3:3:5:9-rule.
These values are stored in the initialized array w[].
The value of a Pawn is set to 99 (to save 1 character over 100...),
and the value retrieved from the array is multiplied by that
(to avoid a list of multi-digit numbers in the initializer).
A King is represented by a negative value in w[],
so that it can be easily tested for, and capture of it can result in special action:
immediate return of an 'infinity' score I.
It would not suffice to give the King merely a huge value and let the normal desire of the engine
to avoid losses protect the King without such special action:
the engine would then see no harm in exchange of Kings, and answer check with check!
The positional score (see next page) is not implemented consistently, because it is not subtracted when a piece is captured. This might lead to strange play, where the computer tries to earn some positional improvement with a piece that is lost anyway. It prefers to have it captured on a good square, rather than a bad one! In practce this is no big problem, since the desire to avoid the loss in the first place avoids situations like this. But due to the inconsistency, the center score is considered a transient term, and accounted in v. Such transient terms are used to update e in the tree, but not the evauation score Q at the game level.
The evaluation of Pawn structure is very minimal. It just discourages moving pawns if there is no other Pawn (of the same color) two squares to the left or right from its initial position. The idea is that in that case moving the Pawn irreversably gives away control over the square(s) it defended. To make the rule consistent you would also have to encourage moves that do cover a square that was not defended by other Pawns before. But in practice this is less important: you always can do that later, when really forced by the tactical situation, while there is no way to move the Pawn back if you regret its move. A worse inconsitency is the fact that no penalty is given when Pawn control over a square is lost due to capture of that Pawn. Anyway, because of all these inconsistencies Pawn structure is treated as a transient term. The main disadvantage of having so many transient terms is that all these aspects are not contributing to the score at the game level, so that the engine will never go for a draw (e.g. if it can force stalemate) if it is equal in material, but badly behind positionally. But in practice stalemates occur only on a bare King, when there is enough material advantage to want to avoid them.
The thing that is most lacking in the evaluation of Pawn structure is doubled Pawns. Probably the most efficient way to make the program better at avoiding doubled Pawns is to give a penalty for blocking your own Pawn by standing directly in front of it with whatever piece. Putting his own pieces in front of his Pawns is the most common source of doubled Pawns. It usually leads to bad Pawn structure even if the piece can not be captured, because the blocked Pawn usually ends up as a severely backward Pawn.
Castling and Queening had special conditional statements to perform them anyway, making it easy to award them appropriately. The score for Queening - being a material advantage - is permanent, that for castling transient. The score for Queening is a little bit off, because it uses a constant (C) that was needed anyway and had nearly the correct value (799, in stead of (9-1)*99 = 792). Never mind the inconsistency: you won't queen often enough to have it build up to a large value. If you are the only side that can force Queening the game is quickly won, if both sides queen, the inconsitencies cancel.
Below the code that implements the various evaluation terms is highlighted:
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 3.2 (2000 characters) features: */
/* - recursive negamax search */
/* - quiescence search with recaptures */
/* - recapture extensions */
/* - (internal) iterative deepening */
/* - best-move-first 'sorting' */
/* - a hash table storing score and best move */
/* - full FIDE rules (expt minor ptomotion) and move-legality checking */
#define F(I,S,N) for(I=S;I<N;I++)
#define W(A) while(A)
#define K(A,B) *(int*)(T+A+(B&8)+S*(B&7))
#define J(A) K(y+A,b[y])-K(x+A,u)-K(H+A,t)
#define U 16777224
struct _ {int K,V;char X,Y,D;} A[U]; /* hash table, 16M+8 entries*/
int V=112,M=136,S=128,I=8e3,C=799,Q,N,i; /* V=0x70=rank mask, M=0x88 */
char O,K,L,
w[]={0,1,1,3,-1,3,5,9}, /* relative piece values */
o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0, /* step-vector lists */
7,-1,11,6,8,3,6, /* 1st dir. in o[] per piece*/
6,3,5,7,4,5,3,6}, /* initial piece setup */
b[129], /* board: half of 16x8+dummy*/
T[1035], /* hash translation table */
n[]=".?+nkbrq?*?NKBRQ"; /* piece symbols on printout*/
D(k,q,l,e,J,Z,E,z,n) /* recursive minimax search, k=moving side, n=depth*/
int k,q,l,e,J,Z,E,z,n; /* (q,l)=window, e=current eval. score, E=e.p. sqr.*/
{ /* e=score, z=prev.dest; J,Z=hashkeys; return score*/
int j,r,m,v,d,h,i=8,F,G;
char t,p,u,x,y,X,Y,H,B;
struct _*a=A;
/* lookup pos. in hash table*/
j=(k*E^J)&U-9; /* try 8 consec. locations */
while((h=A[++j].K)&&h-Z&&--i); /* first empty or match */
a+=i?j:0; /* dummy A[0] if miss & full*/
if(a->K) /* hit: pos. is in hash tab */
{d=a->D;v=a->V;X=a->X; /* examine stored data */
if(d>=n) /* if depth sufficient: */
{if(v>=l|X&S&&v<=q|X&8)return v; /* use if window compatible */
d=n-1; /* or use as iter. start */
}X&=~M;Y=a->Y; /* with best-move hint */
Y=d?Y:0; /* don't try best at d=0 */
}else d=X=Y=0; /* start iter., no best yet */
N++; /* node count (for timing) */
W(d++<n|z==8&N<1e7&d<98) /* iterative deepening loop */
{x=B=X; /* start scan at prev. best */
Y|=8&Y>>4; /* request try noncastl. 1st*/
m=d>1?-I:e; /* unconsidered:static eval */
do{u=b[x]; /* scan board looking for */
if(u&k) /* own piece (inefficient!)*/
{r=p=u&7; /* p = piece type (set r>0) */
j=o[p+16]; /* first step vector f.piece*/
W(r=p>2&r<0?-r:-o[++j]) /* loop over directions o[] */
{A: /* resume normal after best */
y=x;F=G=S; /* (x,y)=move, (F,G)=castl.R*/
do{H=y+=r; /* y traverses ray */
if(Y&8)H=y=Y&~M; /* sneak in prev. best move */
if(y&M)break; /* board edge hit */
if(p<3&y==E)H=y^16; /* shift capt.sqr. H if e.p.*/
t=b[H];if(t&k|p<3&!(r&7)!=!t)break; /* capt. own, bad pawn mode */
i=99*w[t&7]; /* value of capt. piece t */
if(i<0||E-S&&b[E]&&y-E<2&E-y<2)m=I; /* K capt. or bad castling */
if(m>=l)goto C; /* abort on fail high */
if(h=d-(y!=z)) /* remaining depth(-recapt.)*/
{v=p<6?b[x+8]-b[y+8]:0; /* center positional pts. */
b[G]=b[H]=b[x]=0;b[y]=u&31; /* do move, strip virgin-bit*/
if(!(G&M)){b[F]=k+6;v+=30;} /* castling: put R & score */
if(p<3) /* pawns: */
{v-=9*(((x-2)&M||b[x-2]!=u)+ /* structure, undefended */
((x+2)&M||b[x+2]!=u)-1); /* squares plus bias */
if(y+r+1&S){b[y]|=7;i+=C;} /* promote p to Q, add score*/
}
v=-D(24-k,-l-(l>e),m>q?-m:-q,-e-v-i, /* recursive eval. of reply */
J+J(0),Z+J(8)+G-S,F,y,h); /* J,Z: hash keys */
v-=v>e; /* delayed-gain penalty */
if(z==9) /* called as move-legality */
{if(v!=-I&x==K&y==L) /* checker: if move found */
{Q=-e-i;O=F;return l;} /* & not in check, signal */
v=m; /* (prevent fail-lows on */
} /* K-capt. replies) */
b[G]=k+38;b[F]=b[y]=0;b[x]=u;b[H]=t; /* undo move,G can be dummy */
if(Y&8){m=v;Y&=~8;goto A;} /* best=1st done,redo normal*/
if(v>m){m=v;X=x;Y=y|S&G;} /* update max, mark with S */
} /* if non castling */
t+=p<5; /* fake capt. for nonsliding*/
if(p<3&6*k+(y&V)==S /* pawn on 3rd/6th, or */
||(u&~24)==36&j==7&& /* virgin K moving sideways,*/
G&M&&b[G=(x|7)-(r>>1&7)]&32 /* 1st, virgin R in corner G*/
&&!(b[G^1]|b[G^2]) /* 2 empty sqrs. next to R */
){F=y;t--;} /* unfake capt., enable e.p.*/
}W(!t); /* if not capt. continue ray*/
}}}W((x=x+9&~M)-B); /* next sqr. of board, wrap */
C:if(m>I/4|m<-I/4)d=99; /* mate is indep. of depth */
m=m+I?m:-D(24-k,-I,I,0,J,K,S,z,1)/2; /* best loses K: (stale)mate*/
if(!a->K|(a->X&M)!=M|a->D<=d) /* if new/better type/depth:*/
{a->K=Z;a->V=m;a->D=d;A->K=0; /* store in hash,dummy stays*/
a->X=X|8*(m>q)|S*(m<l);a->Y=Y; /* empty, type (limit/exact)*/
} /* encoded in X S,8 bits */
/*if(z==8)printf("%2d ply, %9d searched, %6d by (%2x,%2x)\n",d-1,N,m,X,Y&0x77);*/
}
if(z&8){K=X;L=Y&~M;}
return m;
}
main()
{
int j,k=8,*p,c[9];
F(i,0,8)
{b[i]=(b[i+V]=o[i+24]+40)+8;b[i+16]=18;b[i+96]=9; /* initial board setup*/
F(j,0,8)b[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5); /* center-pts table */
} /*(in unused half b[])*/
F(i,M,1035)T[i]=random()>>9;
W(1) /* play loop */
{F(i,0,121)printf(" %c",i&8&&(i+=7)?10:n[b[i]&15]); /* print board */
p=c;W((*p++=getchar())>10); /* read input line */
N=0;
if(*c-10){K=c[0]-16*c[1]+C;L=c[2]-16*c[3]+C;}else /* parse entered move */
D(k,-I,I,Q,1,1,O,8,0); /* or think up one */
F(i,0,U)A[i].K=0; /* clear hash table */
if(D(k,-I,I,Q,1,1,O,9,2)==I)k^=24; /* check legality & do*/
}
}
Previous Next