Previous Next
In the end-game the knowledge that centralizing the King is good, and as a consequence being driven to the board edge is bad, is essentiel. Without is, micro-Max could not perform most mates against a bare King, or win Pawn endings. For this purpose the King uses the same piece-square table as light pieces. A King stroll to the center in the middle-game is fatal, though. Unfortunately, micro-Max regularly gets the idea to do just that, when it sees nothing better and tries to 'optimize' its position further through centralizing its King.
This leads to many unnecessary lost games, for if the King is not checkmated in the center, it is only because huge material sacrifices could prevent it. Something is badly needed to suppress this suicidal tendency.
In order to provide better King safety, without severely impairing end-game ability, it is essential to somehow recognize these various game stages. To this end micro-Max 4.3 keeps track of the total captured non-Pawn material. The idea is that if enough material is captured, at some point it becomes safe to involve the King actively into play. (It would be slightly more accurate to only look at the opponent's material, but the assumption is that the material is more or less evenly divided. If not, the game is decided anyway. Promotions are also not taken into account, but promotions are usually also quite decisive.)
In micro-Max 4.3 a new variable R keeps track of the total capturen non-Pawn material,
according to the formula minor Piece=2, Rook=3, Queen=6;
These values are obtained from dividing the piece value (1 Pawn=99) by 128 and rounding down
(in practice a right-shift of 7 bits).
Total capturable material on this scale is 20 for each side,
so without promotions R=40 would mean we are in a Pawn ending.
The criterion micro-Max uses for involving the King is that captured material should be at least 30, meaning that there can be two Rooks and two minor Pieces on the board. When the opponent is down to R+N the King than takes its chances. In case the material was unevenly divided, (say R+R against B+N) it might be slightly unsafe, but on the other hand our army needs the assistance of the King badly. Note that Q vs Q is over the limit; the King keeps hiding as much as possible in that case.
The first component of King safety, applied only in the middle game, is to simply penalize all King moves, so that only castlings (which recieve their own bonus) are attractive. This has a lot of indirect effects: it will be considered very bad by micro-Max if it can be forced to move its King to evade a check that could not be solved otherwise. It will automatically arrange its pieces in such a way to prevent such checks, thereby providing better King safety. When in trouble, it will tend to seek cover by the shortest route. An unintended side effect is that because of this evaluation term, perpetual checks earns an enormous score, and micro-Max will go for it without thinking, even if it is far ahead. This drives up the draw percentage enormously.
Freezing the King is not the whole story, though.
If a King ends up after castling in its nice and cozy corner of, say, g1,
we don't want micro-Max to start an assault with the Pawns in front of it.
The resulting open lines would be just as fatal as strolling to the center.
As a minimal solution,
the Pawn that is standing in front of a non-virgin King gets a penalty when it is moved.
In practice it looks not behind it, but at its 'partnet square' x^16.
For virgin Pawns this is on the first row, though,
and has the advantage that is a color-independent way of finding what is 'behind'.
The listing below indicates the changes to micro-Max 4.2 to implement the King safety that makes version 4.3. This change is quite expensive: it took 43 characters. Version 4.3 scores 65% against version 4.2, (corresponding to a difference of 80 ELO points), despite the large fraction of draws, so I guess it is still worth having.
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 4.3 (1830 characters) features: */
/* - recursive negamax search */
/* - all-capture MVV/LVA quiescence search */
/* - (internal) iterative deepening */
/* - best-move-first 'sorting' */
/* - a hash table storing score and best move */
/* - futility pruning */
/* - king safety through magnetic, frozen king in middle-game */
/* - full FIDE rules (expt under-promotion) and move-legality checking */
#define W while
#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 (1<<24)
struct _ {int K,V;char X,Y,D;} A[U]; /* hash table, 16M+8 entries*/
int M=136,S=128,I=8e3,C=799,Q,O,K,N,R; /* M=0x88 */
char 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,F,G,f;
char t,p,u,x,y,X,Y,H,B;
struct _*a=A+(J+k*E&U-1); /* lookup pos. in hash table*/
q--; /* adj. window: delay bonus */
d=a->D;m=a->V;X=a->X;Y=a->Y; /* resume at stored depth */
if(a->K-Z| /* miss: other pos. or empty*/
!(m<=q|X&8&&m>=l|X&S)) /* or window incompatible */
d=Y=0; /* start iter. from scratch */
X&=~M; /* start at best-move hint */
W(d++<n||d<3|| /* iterative deepening loop */
z==8&K==I&&(N<1e6&d<98|| /* root: deepen upto time */
(K=X,L=Y&~M,d=3))) /* time's up: go do best */
{x=B=X; /* start scan at prev. best */
h=Y&S; /* request try noncastl. 1st*/
m=d-2?-I:e; /* unconsidered:static eval */
N++; /* node count (for timing) */
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{ /* y traverses ray, or: */
H=y=h?Y^h:y+r; /* sneak in prev. best move */
if(y&M)break; /* board edge hit */
m=E-S&b[E]&&y-E<2&E-y<2?I:m; /* bad castling */
if(p<3&y==E)H^=16; /* shift capt.sqr. H if e.p.*/
t=b[H];if(t&k|p<3&!(y-x&7)-!t)break; /* capt. own, bad pawn mode */
i=99*w[t&7]; /* value of capt. piece t */
m=i<0?I:m; /* K capture */
if(m>=l&d>1)goto C; /* abort on fail high */
v=d-1?e:i-p; /* MVV/LVA scoring */
if(d-!t>1) /* remaining depth */
{v=p<6?b[x+8]-b[y+8]:0; /* center positional pts. */
b[G]=b[H]=b[x]=0;b[y]=u|32; /* do move, set non-virgin */
if(!(G&M))b[F]=k+6,v+=50; /* castling: put R & score */
v-=p-4|R>29?0:20; /* penalize mid-game K move */
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 */
+(b[x^16]==k+36)); /* kling to non-virgin King */
if(y+r+1&S)b[y]|=7,i+=C; /* promote p to Q, add score*/
}
v+=e+i;f=m>q?m:q; /* new eval and alpha */
v=d>3|v>f?-D(24-k,-l,-f,-v, /* recursive eval. of reply */
J+J(0),Z+J(8)+G-S,F,y,d-1):v; /* or fail low if futile */
if(z&8&&K-I) /* move pending: check legal*/
{if(v+I&&x==K&y==L) /* if move found in root */
{Q=-e-i;O=F; /* & not in check, signal */
R+=i>>7;return l;} /* captured non-P material */
v=m; /* (prevent fail-lows on */
} /* K-capt. replies) */
b[G]=k+6;b[F]=b[y]=0;b[x]=u;b[H]=t; /* undo move,G can be dummy */
}
if(v>m) /* new best, update max,best*/
m=v,X=x,Y=y|S&F; /* mark double move with S */
if(h){h=0;goto A;} /* redo after doing old best*/
if(x+r-y|u&32| /* not 1st step,moved before*/
p>2&(p-4|j-7|| /* no P & no lateral K move,*/
b[G=x+3^r>>1&7]-k-6 /* no virgin R in corner G, */
||b[G^1]|b[G^2]) /* no 2 empty sq. next to R */
)t+=p<5; /* fake capt. for nonsliding*/
else F=y; /* 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-M|m<M-I)d=98; /* mate holds to any depth */
m=m+I?m:-D(24-k,-I,I,0,J,Z,S,S,1); /* best loses K: (stale)mate*/
a->K=Z;a->V=m;a->D=d; /* always store in hash tab */
a->X=X|8*(m>q)|S*(m<l);a->Y=Y; /* move, type (bound/exact),*/
/*if(z==8)printf("%2d ply, %9d searched, score=%6d by %c%c%c%c\n",d-1,N-S,m,
'a'+(X&7),'8'-(X>>4),'a'+(Y&7),'8'-(Y>>4&7)); /* uncomment for Kibitz */
} /* encoded in X S,8 bits */
return m+=m<e; /* delayed-loss bonus */
}
main()
{
int j,k=8,*p,c[9];
K=8;W(K--)
{b[K]=(b[K+112]=o[K+24]+8)+8;b[K+16]=18;b[K+96]=9; /* initial board setup*/
L=8;W(L--)b[16*L+K+8]=(K-4)*(K-4)+(L-3.5)*(L-3.5); /* center-pts table */
} /*(in unused half b[])*/
N=1035;W(N-->M)T[N]=rand()>>9;
W(1) /* play loop */
{N=-1;W(++N<121)
printf(" %c",N&8&&(N+=7)?10:n[b[N]&15]); /* print board */
p=c;W((*p++=getchar())>10); /* read input line */
K=I; /* invalid move */
if(*c-10)K=*c-16*c[1]+C,L=c[2]-16*c[3]+C; /* parse entered move */
k^=D(k,-I,I,Q,1,j++,O,8,3)-I?0:24; /* think or check & do*/
}
}
Previous Next