Move Generation: Castling - micro-Max by H.G. Muller

[Alexlaw1964]

Hello. Please help add castling to the move generator. I’m trying to generate all pseudo‑legal moves from a position obtained from a FEN string.

Code: Select all

// version 3.2 micro-Max by H.G. Muller
#include <stdio.h>
#define W while
#define WHITE 8
#define BLACK 16
//char *FEN = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w QKqk";
//char *FEN = "r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - ";
//char *FEN = "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -";
//char *FEN = "r3k2r/p2pqpb1/bn2pnp1/2pPN3/Pp2P3/2N2Q1p/1PPBBPPP/R3K2R w - c6";
char *FEN = "8/2p5/3p3k/1P5r/1R3pP1/1K6/4P3/8 b - g3";
char 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 */
char n[]=".?+nkbrq?*?NKBRQ"; /* piece symbols on printout*/
char b[129],t,x,y,u,p,H;
int M=136,r;
int K,N,cnt;
int E,F,S=128,V=112; /*E=e.p. sqr.*/
int ReadFEN(char *FEN){
 int row, file, i, col, nr, cc;
 char c, *p, epSqr[2];
 p = FEN;
 for(i=0; i<128; i++) b[i&0x77]=0;
 nr=0;
 cc=0;
 for(row=7; row>=0; row--)
    {   /* read one row of the FEN */
        file = 0;
        do{
          c = *p++;
          if(c>='1' && c<='8') { file += c - '0'; }
          else
          {
            col = WHITE;
            cc=8*(7-row)+file+nr;
            if(c >= 'a') { c += 'A'-'a'; col = BLACK; }
                        switch(c)
            {
            //{1,2,3,4,5,6,7} = {P+,P-,N,K,B,R,Q}
            case 'K':
                b[cc]=4|col;
                break;
            case 'R':
                b[cc]=6|col;
                break;
            case 'Q':
                b[cc]=7|col;
                break;
            case 'B':
                b[cc]=5|col;
                break;
            case 'P':
                b[cc]=9<<(1&(col>>4));
                break;
            case 'N':
                b[cc]=3|col;
                break;
            //default: return -15;
            }
          file++;
          }
          }while(file < 8);
        if(file >  8) return (-10); /* bad format */
        if(file == 8)
        {   c = *p++;
            nr+=8;
            if(row > 0 && c != '/') return(-10); /* bad format */
            if(row==0  && c != ' ') return (-10); /* bad format */
        }
    }
        while(c = *p++)
    {
        if(c>='0' && c<='9') continue; /* ignore move counts */
        if(c>='a' && c<='h') /* might be e.p. square */
        {    if(*p == '3' || *p == '6')
             {
                 epSqr[0]=c;
                 epSqr[1]=*p;
                 E=((8 - (epSqr[1] - '0')) * 16) + (epSqr[0] - 'a');
                 p++;
                 continue;
             }
             //else if(c != 'b') continue;
        }
        switch(c)
        {
        case 'K': break;
        case 'Q': break;
        case 'k': break;
        case 'q': break;
        case 'w': col = WHITE; break;
        case 'b': col = BLACK; break;
        case ' ':
        case '-': break;
        //default: return -10;
        }
    }

return col;
}
int main()
{
 int j,k=8;//k=8;  k=16; 

 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*/

 }
 k=ReadFEN(FEN);
   W(1)
 {
   N=-1;W(++N<121)
   printf(" %c",N&8&&(N+=7)?10:n[b[N]&15]);          /* print board        */
 W((getchar())>10); /* read input line */

 x=0;cnt=0;
 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*/
 while(r=p>2&r<0?-r:-o[++j]) /* loop over directions o[] */
 {
    y=x;F=S;
    do{
      H=y+=r; /* y traverses ray */
      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 */
      cnt++;
      printf("%c%c%c%c\n",
       'a' + (x % 16),
       '0' + (8 - (x / 16)),
       'a' + (y % 16),
       '0' + (8 - (y / 16))
      );
      //printf(" %d-%d\n",x,y);
      t+=p<5; /* fake capt. for nonsliding*/
       if(p<3&6*k+(y&V)==S /* pawn on 3rd/6th, or */
          ){F=y;t--;} /* unfake capt., enable e.p.*/
    }while(!t); /* if not capt. continue ray*/
 }
 }}W(x=x+9&~M);/* next sqr. of board, wrap */
 printf("cnt=%d\n",cnt);
  }
}

[thomasahle]

Here's what you can do.

While parsing the `KQkq` field, store the castling right in a spare bit of the corresponding corner rook:

Code: Select all

W((c=*p++)>32)
    b[7*(c&34^32)/2] |= c&64;

This maps:

Code: Select all

K -> h1
Q -> a1
k -> h8
q -> a8

Then fold castling into the existing king/pawn ray-extension test:

Code: Select all

t += p<5
   ^ p<3 & 6*k+(y&V)==S
   ^ j<8 & y
     & b[H=x^3^r>>1&7]==u+66
     & !b[H^1] & !b[H^2];

Normally `p<5` stops a king after one square. The last part cancels that stop when the corresponding rook has the castling flag and the squares between king and rook are empty.

So the king ray can continue:

Code: Select all

e1 -> f1 -> g1
e1 -> d1 -> c1

e8 -> f8 -> g8
e8 -> d8 -> c8

For example, with Kiwipete:

Code: Select all

r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -

you should get both:

Code: Select all

e1c1
e1g1

and `cnt=48`.

This is for pseudo-legal generation, so it only checks the castling right, rook presence and empty path. Whether the king is in check or crosses an attacked square can be handled later in the legality test.

[hgm]

In the FEN reader as it is, with seperate cases for K,Q,k,q, it might be easier to just have each case set the virgin bit on the corresponding corner Rook (and always set it for a King).