genmoves.cpp

   1 /***************************************************************************
   2                           movegen.cpp  -  description
   3                              -------------------
   4     begin                : ven ott 25 2002
   5     copyright            : (C) 2002-2005 by Maurizio Monge
   6     email                : monge@linuz.sns.it
   7  ***************************************************************************/
   8
   9 /***************************************************************************
  10  *                                                                         *
  11  *   This program is free software; you can redistribute it and/or modify  *
  12  *   it under the terms of the GNU General Public License as published by  *
  13  *   the Free Software Foundation; either version 2 of the License, or     *
  14  *   (at your option) any later version.                                   *
  15  *                                                                         *
  16  ***************************************************************************/
  17
  18 #include "board.h"
  19 #include "engine.h"
  20
  21 /* macro to add a move in the move list */
  22 #define ADDSIMPLEMOVE(f,tj)                                            \
  23 {                                                                      \
  24                 register Move* mtmp=mvg_curr++;                     \
  25                 mtmp->from = (f);                                      \
  26                 mtmp->to = (tj);                                       \
  27                 mtmp->capture = 0;                                     \
  28                 mtmp->flags = 0;                                       \
  29                 mtmp->val = 0;                                         \
  30 }
  31
  32 #define ADDMOVE(f,tj,x)                                                \
  33 {                                                                      \
  34                 register Move* mtmp=mvg_curr++;                     \
  35                 mtmp->from = (f);                                      \
  36                 mtmp->to = (tj);                                       \
  37                 mtmp->capture = data[((uint8_t)(tj))];              \
  38                 mtmp->flags = (x);                                     \
  39                 mtmp->val = 0;                                         \
  40 }
  41
  42 #define ADDPROMOTE(f,tj)                                               \
  43 {                                                                      \
  44                 register char kpt = data[(uint8_t)(tj)];            \
  45                 register Move* mtmp=mvg_curr;                       \
  46                 mtmp->from = (f);                                      \
  47                 mtmp->to = (tj);                                       \
  48                 mtmp->capture = (kpt);                                 \
  49                 mtmp->flags = PROMOTEQUEEN;                            \
  50                 mtmp->val = 0;                                         \
  51                 mtmp++;                                                \
  52                 mtmp->from = (f);                                      \
  53                 mtmp->to = (tj);                                       \
  54                 mtmp->capture = (kpt);                                 \
  55                 mtmp->flags = PROMOTEKNIGHT;                           \
  56                 mtmp->val = 0;                                         \
  57                 mtmp++;                                                \
  58                 mtmp->from = (f);                                      \
  59                 mtmp->to = (tj);                                       \
  60                 mtmp->capture = (kpt);                                 \
  61                 mtmp->flags = PROMOTEBISHOP;                           \
  62                 mtmp->val = 0;                                         \
  63                 mtmp++;                                                \
  64                 mtmp->from = (f);                                      \
  65                 mtmp->to = (tj);                                       \
  66                 mtmp->capture = (kpt);                                 \
  67                 mtmp->flags = PROMOTEROOK;                             \
  68                 mtmp->val = 0;                                         \
  69                 mvg_curr+=4;                                           \
  70 }
  71
  72 void
  73 Board::find_knight_moves( uint8_t where)
  74 {
  75     if(pins[where] & NFREE)
  76            return;
  77
  78     KnightMove* hm= &Board::knightmoves[where];
  79     for(int i=hm->numm;i>=0;i--)
  80     {
  81         register uint8_t currpos = hm->jump[i];
  82         if(data[currpos] & color_to_move)
  83             continue;
  84
  85         ADDMOVE(where,currpos,0);
  86     }
  87 }
  88
  89 //-------------------------------------------------------------------------------------
  90 //-------------------------------------------------------------------------------------
  91
  92 void
  93 Board::find_queen_moves( uint8_t where)
  94 {
  95     find_bishop_moves(where);
  96     find_rook_moves(where);
  97 }
  98
  99 //------------------------------------------------------------------------------------
 100 //------------------------------------------------------------------------------------
 101
 102 void
 103 Board::find_king_moves( uint8_t where)
 104 {
 105     uint8_t oldd = data[where];
 106     bool freerg = false;
 107     bool freelf = false;
 108
 109     /* clear the place where the king is, so that the
 110         king is not 'protecting' cases near him */
 111     data[where] = 0;
 112 #if TRACK_ATTACKS
 113     del_attacks(0, where);
 114 #endif //TRACK_ATTACKS
 115
 116     for(int i=7;i>=0;i--)
 117     {
 118         uint8_t currpos = where + kingmoves[i];
 119         if( OUT_OF_BOARD(currpos)
 120                 || (data[currpos] & color_to_move)
 121                 || (pins[currpos]&NFREE && data[currpos]==0)
 122                 || under_attack(currpos,other_color))
 123             continue;
 124         //minimize calls to the expensive "under_attack"
 125         if(kingmoves[i]==RIGHT)
 126                 freerg = true;
 127         else if(kingmoves[i]==LEFT)
 128                 freelf = true;
 129         ADDMOVE(where,currpos,0);
 130     }
 131
 132     /* test if castling is possible */
 133     if(!under_check)
 134     {
 135         if(color_to_move==WHITE)
 136         {
 137             if((castle_passing_mask & WCANCASTLEKS)
 138                 && freerg // ie: !under_attack(POS_XY(5,0),BLACK)
 139                 && data[ first_rank[1]+5 ]==0
 140                 && data[ first_rank[1]+6 ]==0
 141                 && !under_attack( first_rank[1]+6 ,BLACK))
 142             {
 143                 ADDMOVE(where, first_rank[1]+6 ,CASTLEKINGSIDE);
 144             }
 145             if((castle_passing_mask & WCANCASTLEQS)
 146                 && freelf // ie: !under_attack(POS_XY(3,0),BLACK)
 147                 && data[ first_rank[1]+3 ]==0
 148                 && data[ first_rank[1]+2 ]==0
 149                 && data[ first_rank[1]+1 ]==0
 150                 && !under_attack( first_rank[1]+2 ,BLACK))
 151             {
 152                 ADDMOVE(where, first_rank[1]+2 ,CASTLEQUEENSIDE);
 153             }
 154         }
 155         else
 156         {
 157             if((castle_passing_mask & BCANCASTLEKS)
 158                 && freerg // ie: !under_attack(POS_XY(5,7),WHITE)
 159                 && data[ first_rank[0]+5 ]==0
 160                 && data[ first_rank[0]+6 ]==0
 161                 && !under_attack( first_rank[0]+6, WHITE))
 162             {
 163                 ADDMOVE(where, first_rank[0]+6 ,CASTLEKINGSIDE);
 164             }
 165             if((castle_passing_mask & BCANCASTLEQS)
 166                 && freelf // ie: !under_attack(POS_XY(3,7),WHITE)
 167                 && data[ first_rank[0]+3 ]==0
 168                 && data[ first_rank[0]+2 ]==0
 169                 && data[ first_rank[0]+1 ]==0
 170                 && !under_attack( first_rank[0]+2, WHITE))
 171             {
 172                 ADDMOVE(where, first_rank[0]+2 ,CASTLEQUEENSIDE);
 173             }
 174         }
 175     }
 176     data[where] = oldd;
 177 #if TRACK_ATTACKS
 178     add_attacks(0, where);
 179 #endif //TRACK_ATTACKS
 180 }
 181
 182 //-------------------------------------------------------------------------------------
 183 //-------------------------------------------------------------------------------------
 184
 185 void
 186 Board::find_bishop_moves( uint8_t where)
 187 {
 188     /* fast path if the bishop is not pinned */
 189     if( !(pins[where] & NFREE) )
 190     {
 191         for(int i=3;i>=0;i--)
 192         {
 193             register uint8_t currpos = where;
 194             register uint8_t currinc = bishmoves[i];
 195
 196             do
 197             {
 198                 currpos += currinc;
 199
 200                 if(OUT_OF_BOARD(currpos))
 201                     break;
 202
 203                 /* break if out of board or we found a where of the same color (or a stone) */
 204                 if(data[currpos] & color_to_move)
 205                     break;
 206
 207                 ADDMOVE(where,currpos,0);
 208             }
 209             /* exit loop if the square is not empty (don't 'jump') */
 210             while(!IS_OF_COLOR(data[currpos],other_color));
 211         }
 212     }
 213     /* if we are pinned but we can move along the line  */
 214     else if(pins[where] & DIAG)
 215     {
 216         register uint8_t currinc = bishmoves[pins[where]&0x0f];
 217
 218         /* do for the 2 allowed directions (back and forward) */
 219         for(int i=2;i>0;i--)
 220         {
 221             register uint8_t currpos = where;
 222
 223             do
 224             {
 225                 currpos += currinc;
 226                 if(OUT_OF_BOARD(currpos))
 227                     break;
 228                 if(data[currpos] & color_to_move)
 229                     break;
 230                 ADDMOVE(where,currpos,0);
 231             }
 232             while(!IS_OF_COLOR(data[currpos],other_color));
 233
 234             currinc = -currinc;
 235         }
 236     }
 237 }
 238
 239 //-------------------------------------------------------------------------------------
 240 //-------------------------------------------------------------------------------------
 241
 242 void
 243 Board::find_rook_moves( uint8_t where)
 244 {
 245     /* fast path if the rook is not pinned */
 246     if(!(pins[where] & NFREE))
 247     {
 248         for(int i=3;i>=0;i--)
 249         {
 250             register uint8_t currpos = where;
 251             register uint8_t currinc = rookmoves[i];
 252
 253             do
 254             {
 255                 currpos += currinc;
 256
 257                 if(OUT_OF_BOARD(currpos))
 258                     break;
 259
 260                 /* break if out of board or we found a where of the same color (or a stone) */
 261                 if(data[currpos] & color_to_move)
 262                     break;
 263
 264                 ADDMOVE(where,currpos,0);
 265             }
 266             /* exit loop if the square is not empty (don't 'jump') */
 267             while(!IS_OF_COLOR(data[currpos],other_color));
 268         }
 269     }
 270     /* if we are pinned but we can move along the line  */
 271     else if(pins[where] & COLM)
 272     {
 273         register uint8_t currinc = rookmoves[pins[where]&0x0f];
 274
 275         /* do for the 2 allowed directions (back and forward) */
 276         for(int i=2;i>0;i--)
 277         {
 278             register uint8_t currpos = where;
 279
 280             do
 281             {
 282                 currpos += currinc;
 283                 if(OUT_OF_BOARD(currpos))
 284                     break;
 285                 if(data[currpos] & color_to_move)
 286                     break;
 287                 ADDMOVE(where,currpos,0);
 288             }
 289             while(!IS_OF_COLOR(data[currpos],other_color));
 290
 291             currinc = -currinc;
 292         }
 293     }
 294 }
 295
 296 //-------------------------------------------------------------------------------------
 297 //-------------------------------------------------------------------------------------
 298
 299 void
 300 Board::find_pawn_moves(uint8_t where)
 301 {
 302     /*static const uint8_t second_rank[] = { 0x60, 0x10 };
 303     static const uint8_t seventh_rank[] = { 0x10, 0x60 };
 304     static const uint8_t passant_rank[] = { 0x30, 0x40 };*/
 305
 306     uint8_t is_white = IS_WHITE(color_to_move);
 307     uint8_t updir = up_dir[is_white];
 308     uint8_t row_p = ROW_OF(where);
 309
 310     register uint8_t up = where + updir;
 311
 312     uint8_t cginfo=pins[where];
 313     bool free = !(cginfo & NFREE);
 314     bool cangoforw = true;
 315     bool cantakerg = X(where) != 7;
 316     bool cantakelf = X(where) != 0;
 317
 318     /* if the pawn is pinned set a few marks */
 319     if(!free)
 320     {
 321         /* nm is the direction of the pinning
 322             FIXME: theese checks depend on the layout of the bishop/rook moves array */
 323         uint8_t nm = cginfo & 0x0f;
 324         cangoforw = ((cginfo & COLM) && (nm>=2));
 325         cantakerg &= ((cginfo & DIAG)
 326                       && ((nm&1) == 1-is_white));
 327         cantakelf &= ((cginfo & DIAG)
 328                       && ((nm&1) == is_white));
 329     }
 330
 331     /* if the pawn is not going to promote... */
 332     if(row_p != seventh_rank[is_white])
 333     {
 334         /* if can the pawn move forward... */
 335         if(IS_VOID(data[up]) && cangoforw)
 336         {
 337             uint8_t up2 = up + updir;
 338             ADDSIMPLEMOVE(where,up);
 339
 340             /* if the pawn can move of two */
 341             if(row_p == second_rank[is_white] && IS_VOID(data[up2]))
 342                 ADDMOVE(where,up2,PAWNOF2);
 343         }
 344
 345         /* can the pawn capture on the right or take en passant? */
 346         if(cantakerg) //not in the last col
 347         {
 348             uint8_t upright = up + RIGHT;
 349
 350             if(COLOR_OF(data[upright])==other_color)
 351             {
 352                 ADDMOVE(where,upright,0);
 353             }
 354             else if( (row_p == passant_rank[is_white]) &&
 355                      ((castle_passing_mask&0x0f) == COL_OF(upright)))
 356             {
 357                 /*  uff, looks like this odd check is really needed, as the en passant
 358                     cannot be done if there is the king on one side and an enemy
 359                     ROOK (or queen) on the other                                     */
 360                 uint8_t right_piece = 0;
 361                 uint8_t left_piece = 0;
 362                 uint8_t tmp_pos;
 363
 364                 tmp_pos = where + LEFT;
 365                 while(1)
 366                 {
 367                     if(OUT_OF_BOARD(tmp_pos))
 368                         break;
 369                     if(data[tmp_pos])
 370                     {
 371                         left_piece = data[tmp_pos];
 372                         break;
 373                     }
 374                     tmp_pos += LEFT;
 375                 }
 376                 tmp_pos = where + 2*RIGHT;
 377                 while(1)
 378                 {
 379                     if(OUT_OF_BOARD(tmp_pos))
 380                         break;
 381                     if(data[tmp_pos])
 382                     {
 383                         right_piece = data[tmp_pos];
 384                         break;
 385                     }
 386                     tmp_pos += RIGHT;
 387                 }
 388                 if(!(left_piece == (KING|color_to_move)
 389                         && (right_piece&~BISHOP)==(ROOK|other_color))
 390                      && !(right_piece == (KING|color_to_move)
 391                         && (left_piece&~BISHOP)==(ROOK|other_color)))
 392                 {
 393                     ADDMOVE(where,upright,ENPASSANT);
 394                 }
 395             }
 396         }
 397
 398         /* can the pawn capture on the left or take en passant? */
 399         if(cantakelf)   //not in the first col
 400         {
 401             uint8_t upleft  = up + LEFT;
 402
 403             if(COLOR_OF(data[upleft])==other_color)
 404             {
 405                 ADDMOVE(where,upleft,0);
 406             }
 407             else if( (row_p == passant_rank[is_white]) &&
 408                      ((castle_passing_mask & 0x0f) == COL_OF(upleft)))
 409             {
 410                 /*  uff, looks like this odd check is really needed, as the en passant
 411                     cannot be done if there is the king on one side and an enemy
 412                     ROOK (or queen) on the other                                     */
 413                 uint8_t right_piece = 0;
 414                 uint8_t left_piece = 0;
 415                 uint8_t tmp_pos;
 416
 417                 tmp_pos = where + 2*LEFT;
 418                 while(1)
 419                 {
 420                     if(OUT_OF_BOARD(tmp_pos))
 421                         break;
 422                     if(data[tmp_pos])
 423                     {
 424                         left_piece = data[tmp_pos];
 425                         break;
 426                     }
 427                     tmp_pos += LEFT;
 428                 }
 429                 tmp_pos = where + RIGHT;
 430                 while(1)
 431                 {
 432                     if(OUT_OF_BOARD(tmp_pos))
 433                         break;
 434                     if(data[tmp_pos])
 435                     {
 436                         right_piece = data[tmp_pos];
 437                         break;
 438                     }
 439                     tmp_pos += RIGHT;
 440                 }
 441                 if(!(left_piece == (KING|color_to_move)
 442                         && (right_piece&~BISHOP)==(ROOK|other_color))
 443                      && !(right_piece == (KING|color_to_move)
 444                         && (left_piece&~BISHOP)==(ROOK|other_color)))
 445                 {
 446                     ADDMOVE(where,upleft,ENPASSANT);
 447                 }
 448             }
 449         }
 450     }
 451     else
 452     {
 453         /* can we go forw? */
 454         if(IS_VOID(data[up]) && cangoforw)
 455         {
 456             ADDPROMOTE(where,up);
 457         }
 458
 459         if(cantakerg) //not in the last col
 460         {
 461             uint8_t upright = up + RIGHT;
 462
 463             if(COLOR_OF(data[upright])==other_color)
 464             {
 465                 ADDPROMOTE(where,upright);
 466             }
 467         }
 468
 469         if(cantakelf)   //not in the first col
 470         {
 471             uint8_t upleft  = up + LEFT;
 472
 473             if(COLOR_OF(data[upleft])==other_color)
 474             {
 475                 ADDPROMOTE(where,upleft);
 476             }
 477         }
 478     }
 479 }
 480
 481 //-------------------------------------------------------------------------------------
 482 //-------------------------------------------------------------------------------------
 483
 484 /* fill the mvs array (that we suppose to be big enough, etc) with all
 485    the legal moves for the player on move */
 486 int Board::find_moves(Move* mvs)
 487 {
 488     if(under_check == 0xff)
 489         find_check_and_pins();
 490     find_other_pins();
 491
 492     /* setup some useful data */
 493     mvg_curr = mvs;
 494
 495     /* if not double check... */
 496     if(under_check<2)
 497     {
 498         int mt = (color_to_move == BLACK ? -1 : +5);
 499         for(int i=mat_tracking[ROOK+mt].count-1;i>=0;i--)
 500             find_rook_moves( mat_tracking[ROOK+mt].pos[i]);
 501         for(int i=mat_tracking[BISHOP+mt].count-1;i>=0;i--)
 502             find_bishop_moves( mat_tracking[BISHOP+mt].pos[i]);
 503         for(int i=mat_tracking[QUEEN+mt].count-1;i>=0;i--)
 504             find_queen_moves( mat_tracking[QUEEN+mt].pos[i]);
 505         for(int i=mat_tracking[KNIGHT+mt].count-1;i>=0;i--)
 506             find_knight_moves( mat_tracking[KNIGHT+mt].pos[i]);
 507         for(int i=mat_tracking[PAWN+mt].count-1;i>=0;i--)
 508             find_pawn_moves( mat_tracking[PAWN+mt].pos[i]);
 509         for(int i=mat_tracking[KING+mt].count-1;i>=0;i--)  /* ! */
 510             find_king_moves( mat_tracking[KING+mt].pos[i]);
 511
 512         /* if under check select only the moves that protect the king */
 513         if(under_check==1)
 514         {
 515             int n=mvg_curr-mvs;
 516             mvg_curr=mvs;
 517             for(int i=0;i<n;i++)
 518                 if(pins[mvs[i].to]&NFREE   //ok, interposition/capture
 519                    || ((mvs[i].flags == ENPASSANT) && //ok, taking a checking pawn en-passant
 520                         pins[ROW_OF(mvs[i].from) | COL_OF(mvs[i].to)]&NFREE)
 521                    || PIECE_OF(data[mvs[i].from])==KING) //ok, moving king
 522                           *mvg_curr++=mvs[i];
 523         }
 524
 525         return mvg_curr-mvs;
 526     }
 527
 528     /* under double check only generate king moves */
 529     find_king_moves( king_pos[IS_WHITE(color_to_move)]);
 530     return mvg_curr-mvs;
 531 }