Previous   Next   Version 4Search: Iterative DeepeningMove orderingThe efficiency of the alpha-beta search is strongly enhanced (in terms of the number of nodes searched) if the best move is tried first, and trying idiotic moves first (such as both Queens getting berserk) can easily lead to an explosion of the search. Rather than aggressively starting a search of the required depth, proceed carefully and first invest some time doing a search of shallower depth. Then use the result to determine the order in which you are going to try the moves in the full search. The time you save because of the good move ordering pays back many times the time you invested in the shallower search.
Iterative DeepeningThis concept, known as internal iterative deepening, works like a charm, because the completely stupid full-width search in principle tries anything, even the most idiotic moves like taking a defended Pawn with a Queen. Such moves can cause tremendous tactical complications if you refrain from taking the Queen back immediately, a move that a one-ply search would already recommend. So the power of iterative deepening is that it immediately finds the solutions for problems that do have trivial solutions, so that in the deeper searches their subtrees are quickly and decisively pruned though the alpha-beta mechnism. Going into the search 'depth first', on the other hand, tends to dive deep into idiotic variations before realizing they were idiotic, when accidentally hitting upon the proper refutation.
Of course one could implement a satic way to find out what likely refutations are for idiotic moves, but there are many levels of idiocy. Some, like taking a defended piece with a higher one, are refuted in the next ply, but if the apparently defending piece happened to be a pinned one, it is the opponent who turns out to be the idiot on ply number two. Judging this statically becomes progressively more difficult. With iterative deepening the results vary wildly with depth until the entire relevant tactics are within the horizon (e.g. including the capture of the piece on which the defender was pinned), and stabilize after that.
To implement the iterative deepening there is (of course) a loop around the search code, that executes it with a depth left d running from 1 to n-1, rather than just for d=n-1, like this:
int D(int k, int q, int l, int n){        int m,                          /* score of best move so far    */            d=0,                        /* iteratively improved depth   */        while(++d<n)        {        m = d>1 ? -I : EVAL();                  /* if d==1 no moves will be tried       */                INITIALIZE_MOVE_GENERATION(B);          /* start with moves that go from B      */                DO{{{                        GENERATE_NEXT_MOVE;                        IF_KING_CAPTURE m=I;                        if(m>=l) goto C;                        h = d-1;                        /* new depth left                       */                                                if(h)                        {        DO_MOVE;                                v = -D(24-k, -l, q>m?-q:-m, h);                                UNDO_MOVE;                                                                if(v>m) { m=v; }        /*   account maximum                    */                        }                }}} WHILE_MOVES_LEFT;            C:        ;        }        return m;}The information returned by the pevious, shallower searches can be used in two ways. The score obtained can be used to set the window more appropriately, leading to a more efficient search. In addition the order of looking at the moves can be inspired by it. Micro-Max uses only the second method, in a minimal way: it tries the best move from the previous iteration first, but all other moves in the order they hppen to be generated. There are no manipulations with the window.
Maximum DepthIn internal nodes the maximum depth is set by the caller, but at the root we want to deepen until time runs out. How many ply that is depends strongly on the position and the stage of the game. To take account of this micro-Max deepens in the root node (which is recognized because it is the only instance of D() that is called with the invalid square code 8 for the 'recapture square' z) until a certain number of nodes, counted in N, has been reached. In the sample listing this is after 10 million nodes (1e7), to change the average time per move this number should be changed. To prevent problems with stack overflow in a tree that does not branch, an absolute maximum of 98 ply is set to the depth. One could also set a fixed depth here, by simply writing while(d++<n)), and calling D() from main with n set to the required value (saving many characters...). But then micro-Max starts to play very fast (and poorly) in the end-game.
Game EndsIterative deepening makes no sense if the search has already reached the legal end of the game, through checkmate. If mate-in-three is certain, nothing can be gained by looking deeper, we are not interested anymore in mate-in-four. So if the score tells us that a checkmate is discovered, we immediately set the depth d to the maximum (i.e. 99), so that no new iterations are started.
Below the code that implements the iterative deepening 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 16777224struct _ {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=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)  */ while(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=(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=random()>>9; W(1)                                                /* play loop          */ {F(i,0,121)printf(" %c",i&8&&(i+=7)?10:n[b&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.K=0;                                  /* clear hash table   */  if(D(k,-I,I,Q,1,1,O,9,2)==I)k^=24;                 /* check legality & do*/ }}Previous   Next   Version 4

Previous   NextSearch: Move SortingMove OrderingSearching the tree successively deeper is just a waste of time if we don't somehow use what we learned. Micro-Max only uses one piece of information, namely what the best move of the previous iteration was, for the purpose of searching that first.
To implement this, apart from remembering the score of the best move in m, we also keep track of what this best move was at any level, in the local variables X and Y. When a new iteration starts, we sneak in this best move before any of the other moves is considered. To this end the outer loop of the move generator, that runs through all pieces, is modified to start at the piece that could do the best move previously, rather than in the corner of the board. A local variable B keeps track of where we started the board scan, so that we know when we're done (remember the scan wraps around). This makes it easier to slip in the best move before all others, because the piece and square of origin are already that of the best move.
After generating the first target square y for this piece, we replace it by the target square of the previous best move. After searching the sub-tree for this move, we intercept the control flow, (based on the '8'-bit of Y being set) recording the score as the maximum found (since this was the first move we considered we don't have to compare with any previous best) and clearing the '8'-bit of Y to indicate that the best move is now considered. We then jump back to the beginning of the loop-over-directions of the move generator, to redo everything for the move that would have been originally generated as the first move for that piece.
Somewhat later, possibly even immediately, the best move will be generated a second time, in the course of normal move generation. To prevent it from being evaluated again (which would be quite inefficient, since it is likely to still be the best move, which will not trivially fail), we would have to test every move for being this best one (prepending an if(x!=B|y!=Z) before the code that considers the generated moves). Once transposition tables are implemented we don't have to bother with this, since re-searching this move will take the value of the original search immediately from the transposition table, an acceptable overhead.
int D(int k, int q, int l, int n){        int m,                          /* score of best move so far    */            d=0,                        /* iteratively improved depth   */            X=0,Y=0,                    /* best move                    */            B,Z;                        /* move to skip, already done   */        while(++d<>n)        {        m = d>1 ? -I : EVAL();                  /* note there is no best to try if d==1 */                B = X;                                  /* start move generation with piece here*/                Z = 8;                                  /* nothing to skip yet: invalid square  */                Y |= 8&Y>>4;                            /* copy 128-bit of Y to 8-bit, to ask   */                                                        /* priority for a valid prev. best move */            A:                INITIALIZE_MOVE_GENERATION(B);          /* start with moves that go from B      */                DO{{{                        GENERATE_NEXT_MOVE;                        if(Y&8) y=Y;                    /* overrule generated move with best    */                        IF_KING_CAPTURE m=I;                        if(m>=l) goto C;                        h = d-1;                        /* new depth left                       */                                                if(x-B|y-Z)                     /* skip if already done as best         */                        if(h)                        {        DO_MOVE;                                v = -D(24-k, -l, q>m?-q:-m, h);                                UNDO_MOVE;                                                                if(Y&8)                                {        m=v;            /* first is always best, m was -I       */                                        Z=y;            /* set this move for future skipping    */                                        Y=y|S;          /* clears 8-bit now best is tried       */                                        goto A;         /* try normal moves                     */                                }                                if(v>m)                                {        m=v;                                        X=x;Y=y|S;      /* remember best, set 128-bit of Y to   */                                }                       /*   indicate a best move is available  */                        }                }}} WHILE_MOVES_LEFT;            C:        ;        }        return m;}If the best move from the previous iteration turns out not so good after all, searching other moves of the same piece (as will be done next) often does provide a new best move quickly: In many cases the best move is to withdraw a threatened piece, and if one escape route turns out bad, another might still be good.
Castling ProblemsTo properly perform a castling move, the variables F and G for the Rook part have to be set, and this is only the case if the move is generated in the normal way: These variables are not remembered together with the best move. So castling can not be eligible for being sorted in front. This nuisance is solved by deriving the 'S'-bit in Y, which indicates that there is a best move that should be tried first in the next iteration, from the casting variable G. This prevents setting the 'S'-bit (i.e. the '128'-bit) when the best move is a castling. The 'S'-bit is copied to the '8'-bit of the same variable before the beginning of the next iteration, and acts as a request to sneak in the move. So castlings will not be sorted first.
However, the generation of moves will start at the King, in that case. Because the first directions in which moves are generated are the lateral ones, the castling will be found quite early, though.
Below the code that controls move ordering (by determining the best move, and make it jump the queue in the next iteration) 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 16777224struct _ {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=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-(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,Z,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=(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=random()>>9; W(1)                                                /* play loop          */ {F(i,0,121)printf(" %c",i&8&&(i+=7)?10:n[b&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.K=0;                                  /* clear hash table   */  if(D(k,-I,I,Q,1,1,O,9,2)==I)k^=24;                 /* check legality & do*/ }}Previous   Next

Previous   Next   Version 4Hash Table: LookupTranspositionsThe same position can occur in many places in the search tree. Not only can positions be reached by the same set of moves played in a different order, pieces can also reach the same destination square through a different route. This in particular happens with the King in the end-game. The purpose of the hash table is to store the useful information about a position, so that the computer does not have to search it again if it is encountered a second time. The Hash Table EntryAn entry of the hash table in micro-Max is a struct _. It contains a more or less unique (4-byte) key K derived from the position, in order to identify it. The actual information that is stored contains of the score V found for that position (4 bytes), the best move X,Y (2 bytes) and the depth D of the search at which this score was found. Since the size is rounded to a multiple of 4 bytes, (for memory-word alignment), the entry occupies 12 bytes in memory, and wastes some space.
In an Alpha-Beta search most nodes are not completely searched, and as a consequence the scores are only upper or lower bounds. This is indicated by the bits in the field X that are not used in valid square codes, the '8'- and the 'S'-bit. (In the destination field Y these bits are used to indicate if the move was a castling.) The '8'-bit is set if a result is above alpha, the 'S'-bit if it is below beta, so that exact results (within the window) have both bits set. Exact results, after all, are both upper and lower limit.
The Zobrist KeysTo make sure we make no retrieval errors, two 32-bit Zobrist-like hash keys are used. They are differentially updated, and passed along up the tree from the root as arguments J and Z to D(). The Zobrist scheme requires a table of random numbers for each piece-square pair. In micro-Max this table is packed by having the 4-byte random numbers overlap three bytes out of four, i.e. we have a table T[1035] of (about) nr_of_pieces x nr_of_squares bytes, and acces that table like it were integers, retreiving four bytes at a time. (Bad for memory alignment, but much better than having L1-cache misses because the table is too big...) Since this is done a number of times, the rather awkward syntax is spelled out in a macros J and K. Since T[] is indexed by square number, the holes in the 0x88 board are used for storing the random numbers for the other color. The two Zobrist keys swap the numbers for the black and white pieces.
The low-order bits of One key is used to determine where we store (and look for) the position in the table, the other key is stored in the table as the id K. If the entry is already occupied by another position that happened to map to the same address (but with different K) - something which will hapen quite often if the table fills up - we try to put it in the next entry ('rehash') up to eight times. Together, this gives a 1 in 2^53 probability for mis-identification: 1 in 2^32 that two different positions have the same id number, 8 in 2^24 (=16M) that they are sought in the same place (because a position can be stored in 8 locations of a table of 16M entries). This seems small enough: even with 16M entries stored there are 2^47 pairs of entries, so the probability that 2 positions from a full table are accidentally confused is 1 in 64. OK, so it can occasionally happen...
Castling, E.P., and Side to MoveCastling rights, the ability to make an e.p. capture somewhere on the board, and who is to move are all part of the 'state' of a chess game, and two positions that differ in this respect sould never be confused, even if they have all pieces on the same location. The Zobrist keys would only take care of the latter aspect. The castling rights are incorporated by adding G-S (which is 0 for non-castlings) to one of the keys in the differential update. (OK, so it does consider a position reached by castling as different from the same one that was reached by normal moves, who cares?) The e.p. capture and side to move, which are not lasting features, are xor'ed to the key directly before retreival, (i.e. not differentially updated), as (k*E^J). The product k*E produces values that differ at least 8 from each other for any legal combination of k and E, so there can be no confusion even after re-hashing. (Note that neither k nor E can be zero, and k is a multiple of 8.)
Below the code that implements the hashing scheme 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 16777224struct _ {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=(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=random()>>9; W(1)                                                /* play loop          */ {F(i,0,121)printf(" %c",i&8&&(i+=7)?10:n[b&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.K=0;                                  /* clear hash table   */  if(D(k,-I,I,Q,1,1,O,9,2)==I)k^=24;                 /* check legality & do*/ }}Previous   Next   Version 4

Previous   NextHash Table: HitsUsing the Retrieved DataUpon entering D() for scoring a new position, we first look in the hash table to see what we know about this position. A retrieved table entry that was calculated at sufficient depth that contains an appropriate type result (i.e. exact within the window, or the proper bound type when outside the current window) is immediately used by returning the value without any further search.
If the position was found in the table, it can also be of insifficient depth, or it can be incompatibility with the current window (e.g. an upper bound above beta, where we need lower bounds). In both cases we use the best move from the table as a first try in the search that we now have to do. We then start the iterative deepening at the depth of the table result, or the requested depth if that was lower (and we could not accept the table value because of bad window). After all, the only thing used from previous iterations is the best move, and we already have one from the table. (This might be unjustified if the table value was a fail low, where all moves considered but all were deemed so bad that they were not even worth figuring out how bad. We then might have no idea at all what the best move is. A move from fail high at least must have some merit... The behavior when the the hash value is incompatible with the window is clearly a weak spot in micro-Max, much more advanced algorithms are concievable, deciding with which depth to start the iteration based on the positioning of the table value compared to the current window, and the likelyhood this implies for the 'best move' to be a useful guess.)
If the depth of the table result was that of QS, we don't even use the best move, because there might be none (in which case the table score represents the static evaluation). If the position was not in the table at all, (the entry is empty, as seen from a->K being zero), or if the table is 'full' (i.e. in the 8 accessible places, in which case the dummy entry A[0] was retrieved, also empty) iteration starts at a depth of zero, with no best move. Just as in normal iterative deepening without a hash table.
Below the code that implements the hash-table retrieval 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 16777224struct _ {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,Z,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=(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=random()>>9; W(1)                                                /* play loop          */ {F(i,0,121)printf(" %c",i&8&&(i+=7)?10:n[b&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.K=0;                                  /* clear hash table   */  if(D(k,-I,I,Q,1,1,O,9,2)==I)k^=24;                 /* check legality & do*/ }}Previous   Next

Previous   NextHash Table: ReplacementClearingThe hash table is completely cleared before every move. This is good for debugging, because it makes the move independent of the history that might have filled the hash table. It also means that the Zobrist keys don't have to be conserved between moves, and they can start at any value.
ReplacementMicro-Max uses a very simple replacement scheme. For every position only one result is stored. If this result is not exact, it is always replaced, no matter what its depth was. If it was an exact result, it is only replaced by results of better or equal depth. Also equal, because it is more recent, and therefore might be more reliable: a re-search at the same depth does not necessarily return the same result as before, because the hash table is learning all the time (deepening the entry for all positions), so a newer search might benefit from hits to deeper, and therefore more reliable, other positions.
This scheme worked dramatically better than any other I tried in my benchmark, the KPK end-game. Especially clinging on to deep non-exact results produced very poor performance: the bounds stored in the table might have no use after a major re-adjustment of the score (e.g. because the promotion gets within the horizon), after which the new situation has to be searched without the benefit of the hash table, because it is crammed with useless data that refuses to make way. And without the aid of the hashing of shallow nodes the search will never get as deep as before, so it will never get to replace the obsolete entries.
By the way, there is no reason to assume that 'deep' results are more valuable than shallower searches: it is more work to perform such a deep search if it was not in the table, but you won't need to do it that often, while shallow searches are quickly done, but need to be done in very any nodes deep in the tree. In the end that kind of balances.
Below the code that implements the hash-table replacement 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 16777224struct _ {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;        &nb