Previous Next
One of the problems of micro-Max versions is that it is rather naive with respect to passed Pawns. It sees no harm in letting the opponent advance these to 7th rank, and only starts to take action against them when promotion becomes an acute threat. By that time the opponent has the Pawn usually well secured on the 7th rank, and is it just a matter of time before he comes with enough material to clear the promotion square.
Unfortunately, detecting passers is too difficult with a reasonable number of characters. As a poor man's solution, we consider every Pawn on the 6th or 7th rank a serious danger. Pawns on the 7th are of course always passers, but Pawns on the 7th can still be blocked by a Pawn directly in front of them. (Pawns diagonally in front of them are no obstacle, as they can be captured.) But in practice micro-Max loses many games by letting such a blocking Pawn be captured (naively swapping it for an enemy Pawn somewhere else on the board), or move it away (with a capture).
So under the motto "better safe than sorry" it also combats the appearence of any Pawn on the 6th. As it is not so easy to get or maintain a Pawn on the 6th, and the bonus for having a Pawn there is smaller than that for one on the 7th, this creates no adverse side effects. (i.e. micro-Max does not devote an unreasonable wasted effort to creating blocked Pawns on the 6th.) A necessary condition, though, is that the bonus for Pushing Pawns to 6th or 7th is implemented consistently, i.e. the bonus should be taken back if the Pawns are captured (or promote). Otherwise it would just try to sacrifice Pawns on the 6th or 7th, (which is quite easy), and think it had a good deal.
The Pawn-push bonus is chosen slightly smaller than the value of a Pawn, (64 vs 2*37=74) so that no Pawns are sacrificed to get a Pawn on the 6th, and a Pawn on the 7th is worth nearly 3 Pawns. As a Knight is worth 3.33 Pawns with the new piece values, this will not lead to outright spontaneous sacrifice of a piece for a passer on the 7th, giving more time for winning the passer (or swapping it for a more harmless Pawn) to come within the horizon if promotion is not yet an acute threat.
The new promotion code in micro-Max 4.5 is full of trickery and obfuscation.
The key to understanding it is that the total bonus of the promotion
(nominally the difference between the value of a Pawn and a Queen)
is chosen such that it can also be added to the piece encoding of a Pawn on the board,
changing it into a Queen!
Now the encoding of Queen is 7, and that of a Pawn 1 or 2
(depending on the color),
so that only 6 of 5 has to be added to the piece encoding.
On the other hand, scores are measured in centi-Pawns,
making the classical difference between P and Q around 800.
The pieces on the board are encoded as char, however,
and thus only see the low-order 8 bits of the added value.
Now 800 ~ 768 = 3*256 has its lowest 8 bits all zero,
and so can be added to the piece encoding without changing it.
We thus add 774 or 773
(in general 775-p, as p is the piece-type of the moving piece, 1 or 2),
and on the board representation this has the same effect as adding 6 or 5.
But on the score, which is an integer,
the added value V is close enough to the difference of the piece value of P and Q (37*23-37*2) = 777
that the difference is without consequence.
We thus can do both i+=V; (score) and b[y]+=V; (piece type) with the same V.
Due to the gradual promotion this bonus of 775-p is spread out over 3 moves:
the pushes to the 6th and 7th rank already earn 64 points each,
so the final promotion has to earn 647-p.
In case the promotion condition
(y+r+1&S != 0, which measures if the next step would fall of the end of the board)
is not fulfilled, a Pawn move should thus get a bonus of either 0 or 64,
the latter only if it is pushed to 6th or 7th rank.
To determine this, the '32' bit of the rank number (y), shifted by one rank (+16) is tested.
It is nonzero for ranks 2, 3, 6 and 7.
To prevent that single steps from the initial Pawn position earn the bonus,
this bit is further masked with the virgin bit of the moving piece (u).
This bit is only set if the Pawn already moved before,
i.e. the bonus will be suppressed for a move from 2nd to 3rd rank of a white Pawn.
Since white Pawns can never move to 2nd rank, and the virgin bit also happened to be the '32' bit,
the expression u&y+16&32 delivers thus 32 if and only if the Pawn moves to 6th or 7th rank.
This then only has to be multiplied by 2 to give the intended bonus V for a non-promotion move.
Now the bonus of 64 is also added to the piece encoding on the board, where it can add upto 128 to the encoding by the time the Pawn reaches 7th rank. This does fall within the low-order byte that is added to the piece encoding, in bits that were formerly unused. These bits (extracted by masking with 192 = 0xC0 in the captured-piece t) are then added to the piece value i when such a Pawn is captured, providing the required consistency. The high-order 'value modifier' bits in the piece code revert to zero when finally the full promotion bonus is added, as the choice of the full bonus guarantees that. So the Queen that finally results will be worth just as much on capture as any other Queen.
The listing below highlights the 'gradual promotion' code in micro-Max 4.6. They take 25 extra charactes, but provide an ELO gain of ~100 against approximately equal opponents in 2 min blitz games.
/***************************************************************************/
/* micro-Max, */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller */
/***************************************************************************/
/* version 4.6 (1909 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 */
/* - R=2 null-move pruning */
/* - keep hash and repetition-draw recognition at game level */
/* - evaluation distinguishing B/N, and more distributed promotion bonus */
/* - 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,Q,O,K,N,R,J,Z,k=8,*p,c[9]; /* M=0x88 */
char L,
w[]={0,2,2,7,-1,8,12,23}, /* 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,E,n) /* recursive minimax search, k=moving side, n=depth*/
int k,q,l,e,E,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,V,P,f=J,g=Z;
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|l>I| /* 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 */
l>I&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*/
P=d<3?-I:D(24-k,-l,1-l,-e,S,d-3); /* Search null move */
m=-P<l|R>35?d-2?-I:e:-P; /* Prune or stand-pat */
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=37*w[t&7]+(t&192); /* 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 */
-(R>>2); /* Pawn-push bonus in ending*/
V=y+r+1&S?647-p:2*(u&y+16&32); /* Promotion or 6/7th bonus */
b[y]+=V;i+=V;} /* upgrade, or promote to Q */
J+=J(0);Z+=J(8)+G-S; /* update hash key(s) */
v+=e+i;V=m>q?m:q; /* new eval and alpha */
v=d>3|v>V?-D(24-k,-l,-V,-v, /* recursive eval. of reply */
F,d-1):v; /* or fail low if futile */
if(K-I&&v+I&&l>I&x==K&y==L) /* move pending. if legal, */
{Q=-e-i;O=F; /* in root & found, exit D */
R+=i>>7;return I; /* captured non-P material */
}
J=f;Z=g; /* restore hash key(s) */
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|P==I?m:0; /* best loses K: (stale)mate*/
if(a->D<99) /* protect game history */
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(l>I)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()
{
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]+799,L=c[2]-16*c[3]+799; /* parse entered move */
k^=D(k,-I,I+1,Q,O,3)-I?0:24; /* think or check & do*/
}
}
Previous Next