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).

[Alexlaw1964]

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).

Help me implement this approach In the FEN reader.
Add a castling test to the existing test for expanding the king and pawn line.
Thanks.

[Alexlaw1964]

I did it this way, but I don’t like it.

Code: Select all

#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 b - -";
//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,E1,E2,E3,E4,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;
 E1=E2=E3=E4=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':E1=((8 - ('1' - '0')) * 16) + ('f' - 'a'); break;
        case 'Q':E2=((8 - ('1' - '0')) * 16) + ('d' - 'a'); break;
        case 'k':E3=((8 - ('8' - '0')) * 16) + ('f' - 'a');  break;
        case 'q':E4=((8 - ('8' - '0')) * 16) + ('d' - 'a');  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[] */
 {
    A:y=x;//F=G=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 */
      if(p==4&&k==8&&y==E1){y=y+1;}
      if(p==4&&k==8&&y==E2){y=y-1;}
      if(p==4&&k==16&&y==E3){y=y+1;}
      if(p==4&&k==16&&y==E4){y=y-1;}
      cnt++;
      printf("%c%c%c%c\n",
       'a' + (x % 16),
       '0' + (8 - (x / 16)),
       'a' + (y % 16),
       '0' + (8 - (y / 16))
      );
      if(p==4&&k==8&&y==E1+1){E1=0;goto A;}
      if(p==4&&k==8&&y==E2-1){E2=0;goto A;}
      if(p==4&&k==16&&y==E3+1){E3=0;goto A;}
      if(p==4&&k==16&&y==E4-1){E4=0;goto A;}
      //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 */
               ){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);
  }
}

[hgm]

Well, I don't know what your criteria are for liking things. Your choice of using micro-Max as a basis for your project is peculiar, because the source code of it was not written for clarity, but for minimizing character count, leading to some pretty obscure programming tricks. One of these tricks was to treat castling on the same footing as the initial double-push of Pawns, as if it were a double-push of the King (which then could be e.p.-captured by any piece that attacked the square it passed through). But you removed that trick from the inner-most move-generation loop (which runs over distance), thus deleting castling from the move repertoire entirely.

Note that this approach would consider castling through or out of check as pseudo-legal. Which might or might not be what you want; there is no rigurous definition of pseudo-legality. The definition I adhere to is that pseudolegality is determined purely by occupancy of squares in the path of a move, and rules involving pieces elsewhere then define the difference between legal and pseudo-legal. So if there are pieces between King and Rook a castling would not even be pseudo-legal, but if these squares are attacked by pieces elsewhere, this only affects legality.

To handle it is style with the original micro-Max code you should keep the code in the while-clause of the range loop, which undoes the suppression of the next step in the current direction that leapers (or captures) would suffer for Kings under a host of conditions (such as presence of virgin corner Rooks, emptiness of the intervening squares). In the FEN reader you can then control the right to castle by manipulating the virginity of those Rooks. But I cannot know if that is something you would like.

[Alexlaw1964]

My goal is to create an interactive electronic chessboard using STM32F103C6T6.

Dear HGM, would you mind if I used Miro‑Max as the basis for the engine?

[Alexlaw1964]

I’ll try to explain my goal at this stage. Why do I need a move generator in this form? In my understanding, an interactive chessboard is just a regular board on which the user moves the pieces. Sensors read the movement of the piece from one place to another, and the generated move is transmitted to Micro‑Max (STM32). I implemented the tracking of the sensor positions on the Attiny2213/4313. And the move generator will also be added to the Attiny. Therefore, the code size is important to me. The move generator is needed to eliminate as many incorrect moves as possible, both user-generated and hardware-based. The final move check will be performed by Micro-max(STM).
One of the games played with Micro-Max on STM32.Don't judge me harshly))

[hgm]

Micro-Max is public domain, so you can use it for whatever purpose you like.

[Alexlaw1964]

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.

Your code works, thank you.
I’m checking it now.