Help Needed for Chess Programming

[H.G.Muller]

no mate with queen,

67. a8=Q+ Ke3 68. Kb4 Kd4 69. Ka3 Ke3 70. Ka4 Kd4 71. Qb8 Ke3 72. Qg3+ Kd4 73. Kb5 Ke4 74. Kc5 Kf5 75. Kd5 Kf6 76. Kd6 Kf5 77. Qh4 Kg6 78. Ke6 Kg7 79. Qf6+ Kh7 80. Kd6 Kg8 81. Kd5 Kh7 82. Kd6 Kg8 83. Kd5 Kh7 84. Kd6 1/2-1/2

Amazing! I only looked at the part of the game after the pawn promotion (assuming there were no other pieces on the board, i.e. KQK), and it must have had the mate well within its horizon after 79. ... Kh7. In fact I count only 5 ply to mate (7 to king capture):

80. Qg5 Kh8 81. Kf6 Kh7 82. Qg7+

At this stage of the game the search reaches to 8 ply, and the final capture of the moving king should not even count in the depth. But in stead it backs off its king Kd6, which is a very strange move. The line

Code: Select all

if (p == 4) v += 9 * (e > C ? !((x ^ y) & 68) : -3);


is supposed to provide the mating capability: it ups the score v of a king (p==4) move when the current advantage e is more than ~8 pawns (C) by 9 pts (1 pawn = 99) when the cryptic expression !((x^y)&68) evaluates as true. x is the destination field of the previous ply, y of the current, so the bitwise exclusive or x^y contains 1-bits where these differed, and the &68 (= &0x44) tests the most significant bits of the rank and file bitwise difference, it is zero (and hence ! it is true = 1) if both these bits did not differ between x and y, i.e. if x and y fall in the same 4x4 quarter of the (0x88) board.

The white king thus gets 9 bonuspoints for each move upto the horizon that it can do in the same quarter as the king-to-be-mated, which maks it all the more strange that it steps immeditely out of that quarter! The idea was that once the kings are close enough, the mate would be within the horizon. The few cases I tested, it ated quickly and decisively. Perhaps it got confused here seeing both the mate in 4 and mate in 3, always preferring the former...

I had hoped to prevent that by the line

Code: Select all

if (v > 1500) v -= 50;


which subtracts ~half a pawn for each move you delay a mate (which is about the only move that scores in this range, but this might be an unsafe technique: I should really adapt the window limits as well to prevent false cutoffs if I fiddle with the score afterwards. Thanks for reporting the bug, I will get to the bottom of this...

[H.G.Muller]

OK, I see what the problem is. My evaluation score contains permanent features, such as the material values, and volatile components (e.g. giving points for advancing a pawn) to encourage moves at the time they seem wise, but not supposed to lead to a permanent advantage. Encouraging it to move pawns forward makes for more agressive play, but it is not supposed to think that in the end game a more advanced pawn is really more valuable. So I don't remove the value accumulated by the pawn when the pawn is captured.

I do update the score differentially during the game, though, as a side-effect of the move-legality checking. This means that the score can drift away, it does not depend solely on the position but also on the history through which the position is reached. In the case at hand, the sequence of white moves was considered so good that, although white was only a queen ahead, (~900 pts) it counted its advantage as nearly 2000 pts, increasing it even further by stepping around in the same quarter of the board as the enemy king. The problem is that for a mate an absolute value is returned, and this value is only 2000! Just as the mate came within the horizon, the evaluation score before the move reached 2008, so that mate was no longer the highest score it could achieve!

The fix is easy: the score at the game level (Q) should not be allowed to drift, but be a strict function of the position. Now I update it as:

Q=z;

where z was set before to the internal score after the move:

z=-e-v

But v contains also the inconsitent evaluation elements. So the situation can be fixed by setting z only to the material value of the move, by prefixing it to the line:

z=v=99*W[t&7];

D() is than simply called with argument -e-v (in stead of z=-e-v), and Q is updated as Q=-e-z;

With these modifications the desirability of stale mate is evaluated purely from the material count, not taking any positional elements into account. This might be just as well.

[H.G.Muller]

Well, it is more difficult to squeeze everything in 2KB than I thought. And with 1400 characters for the full-FIDE simple negamax I had such great hopes...

This is a version that does iterative deepening and has a hash table, so that it also has some end-game play strength in stead of playing like an idiot. (It easily wins KPK now.) On my wish-list of features was also null-move and threat-detection in QS, and doing an aspired search based on the score value of the previous iteration, but that does not seem possible within the 2KB limit.

I documented it by filling out almost every line with a comment (which matches the code in cryptic nature...).

Code: Select all

/***************************************************************************/
/*                               micro-Max,                                */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller  */
/***************************************************************************/
/* version 3.1 (1997 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 promotion) 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.*/
{                       /* z=prev.dest.sqr.; J,Z=hash keys; returns score  */
 int j,r,m,v,d,h,i=9,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  */
 W((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,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+50;                              /* 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*/
 }
}


[Dann Corbit]

It might not fit into 2K, but it is still pretty remarkable.
How about 5K?

I saw a contest once about fitting a chess engine into 5K.
http://www.webreference.com/new/020703.html

[H.G.Muller]

Thanks for the reference! I had not heard of this contest. Compared to 2K, 5K of course seems like infinite space. But I've got to stop somewhere...

The rules for the 5K constest seemed to be that new-lines also count, and that would make my source slightly larger than 2K. I did not count them, because they can almost all be deleted without changing program function (at the expense of readibility). The 2K also only applies after the deletion of leading spaces and trailing comments, of course. As I posted it, the file is ~8.5K.

But you are right: the power of a recursive programming language is awe-inspiring, and this is a nice illustration of that fact. (More skeptical persons might of course just say that this shows that chess is a rather trivial silly game... )

[Peter Eizenhammer]

This is a version ...
I documented it ...).

Hello H.G.,

pretty interesting!
(I am too dumb to comment on it technically, but nevertheless)
thx.

Peter

[H.G.Muller]

Oops, from browsing through sources of other chess programs (to see how they handle hash-table replacements) I just realized there is a minor bug in the code I posted above...

The hash does not include e.p. status, so it might retrieve a position from the hash table in which e.p. capture was allowed, and use its score for the identical position where e.p. capture is not allowed, which of course leads to wrong results if the e.p. capture was the best move on which the score was based. The cheapest fix is to replace the line that calculates the hash-table index,

Code: Select all

 j=k^J&U-9;

by

Code: Select all

j=(k*E^J)&U-9;

(2 extra characters).
The index then depends on both the side to move (k, 8 for white or 16 for black) and the e.p. status (a square number between 0 and 128, of the square to which the e.p. move goes). The use of multiplication here should remove any ambiguity, since different outcomes of k*E will differ at least 8 (because k is a multiple of 8), so that a different e.p. status means that the position is stored at least 8 locations away, i.e. outside the range of 8 consecutive locations where a particular position can map to. Also, k*E is unique, because all possible e.p. squares with black to move hapen to have larger square numbers than those that are possible with white to move.

I effected the change in the posting above.