move.cpp

   1 /***************************************************************************
   2                           move.cpp  -  description
   3                              -------------------
   4     begin                : lun ott 21 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
  19 #include "engine.h"
  20 #include "board.h"
  21 #include <stdio.h>
  22
  23 #define HASH_KEY(piece, square) hash_keys[ PIECE_TO_12(piece)*64 + SQUARE_TO_64(square) ]
  24
  25 //-------------------------------------------------------------------------------------
  26
  27 /* return a 14 bits integer with the move */
  28 uint16_t Board::compress_move(const Move& m) const
  29 {
  30     uint16_t retv = SQUARE_TO_64(m.from) | (SQUARE_TO_64(m.to)<<6);
  31
  32     if(m.flags >= PROMOTE_FIRST && m.flags <= PROMOTE_LAST)
  33     {
  34         retv |= (m.flags-PROMOTE0)<<12;
  35     }
  36     return retv;
  37 }
  38
  39 Move Board::uncompress_move(uint16_t m) const
  40 {
  41     Move retv;
  42     retv.from = SQUARE_FROM_64(m);
  43     retv.to = SQUARE_FROM_64(m>>6);
  44     retv.capture = data[retv.to];
  45     retv.flags = 0;
  46
  47     if(PIECE_OF(data[retv.from]) == PAWN)
  48     {
  49         if(ABS(Y(retv.from)-Y(retv.to))==2)
  50             retv.flags = PAWNOF2;
  51         else if(X(retv.from) != X(retv.to) && !retv.capture)
  52             retv.flags = ENPASSANT;
  53         else if(Y(retv.to) == (color_to_move==WHITE?7:0))
  54             retv.flags = (m>>12) + PROMOTE0;
  55     }
  56     else if(PIECE_OF(data[retv.from]) == KING)
  57     {
  58         if(X(retv.from)==4 && X(retv.to)==6)
  59             retv.flags = CASTLEKINGSIDE;
  60         else if(X(retv.from)==4 && X(retv.to)==2)
  61             retv.flags = CASTLEQUEENSIDE;
  62     }
  63     return retv;
  64 }
  65
  66 void Board::recalc_hash()
  67 {
  68     hash = HashKey(0,0);
  69
  70     int piece_pos = 128;
  71     for(int i=7;i>=0;i--)
  72     {
  73         piece_pos -= 8;
  74         for(int j=7;j>=0;j--)
  75         {
  76             piece_pos--;
  77
  78             if(data[piece_pos])
  79                 hash ^= HASH_KEY( data[piece_pos],  piece_pos );
  80         }
  81     }
  82
  83     /* adjust castle and en-passant */
  84     hash ^= hash_keys[ 12*64 + castle_passing_mask ];
  85
  86     /* adjust player to move */
  87     if(color_to_move == BLACK)
  88         hash ^= hash_key_toggle;
  89 }
  90
  91 /* return the hash key that the board would have after playing the move */
  92 HashKey Board::move_hash(const Move& m) const
  93 {
  94     uint8_t newcpm;
  95
  96     /* adjust hash key */
  97     HashKey h =  hash ^ hash_key_toggle
  98             ^ HASH_KEY( data[m.from],  m.to )
  99             ^ HASH_KEY( data[m.from],  m.from );
 100     if(m.capture)
 101             h ^= HASH_KEY( m.capture,  m.to );
 102
 103
 104     /* reset castle/en passant flags*/
 105     newcpm = 12 | (castle_passing_mask & castle_adj[m.from] & castle_adj[m.to]);
 106
 107     /* handle special moves */
 108     switch(m.flags)
 109     {
 110         case PAWNOF2:
 111             newcpm ^= 12^X(m.to);
 112             break;
 113
 114         case ENPASSANT:
 115         {
 116             uint8_t place = ROW_OF(m.from)+COL_OF(m.to);
 117             h ^= HASH_KEY( PAWN|other_color,  place );
 118             break;
 119         }
 120
 121         case CASTLEKINGSIDE:
 122         {
 123             uint8_t p1 = ROW_OF(m.from)+5;
 124             uint8_t p2 = ROW_OF(m.from)+7;
 125             h ^= HASH_KEY( color_to_move|ROOK,  p1 )
 126                     ^ HASH_KEY( color_to_move|ROOK,  p2 );
 127             break;
 128         }
 129
 130         case CASTLEQUEENSIDE:
 131         {
 132             uint8_t p1 = ROW_OF(m.from)+3;
 133             uint8_t p2 = ROW_OF(m.from);
 134             h ^= HASH_KEY( color_to_move|ROOK,  p1 )
 135                     ^ HASH_KEY( color_to_move|ROOK,  p2 );
 136             break;
 137         }
 138
 139         case PROMOTEROOK ... PROMOTEKNIGHT:
 140         {
 141             uint8_t p = (m.flags-4)|color_to_move;
 142             h ^= HASH_KEY( color_to_move|PAWN,  m.to )
 143                     ^ HASH_KEY( p,  m.to );
 144             break;
 145         }
 146     }
 147
 148     if(newcpm != castle_passing_mask)
 149         h ^= hash_keys[ 12*64 + newcpm ]
 150             ^ hash_keys[ 12*64 + castle_passing_mask ];
 151
 152     return h;
 153 }
 154
 155 void
 156 Board::do_null_move()
 157 {
 158     old_hashes[num_old_hashes++] = hash;
 159     hash ^= hash_key_toggle;
 160
 161     SWITCH(color_to_move, other_color);
 162     num_moves += IS_WHITE(color_to_move);
 163
 164     flags_stack[flags_stack_ptr++] = castle_passing_mask;
 165     flags_stack[flags_stack_ptr++] = fifty;
 166     castle_passing_mask = 12 | (castle_passing_mask & 0xf0);
 167
 168     /* adjust the hash key for the new castle/en passant flags*/
 169     if(flags_stack[flags_stack_ptr-2] != castle_passing_mask)
 170     {
 171         hash ^= hash_keys[ 12*64 + flags_stack[flags_stack_ptr-2] ]
 172                 ^ hash_keys[ 12*64 + castle_passing_mask ];
 173     }
 174
 175     /* mark that now we do not know anything about pinnings */
 176     under_check = 0xff;
 177 }
 178
 179 void
 180 Board::undo_null_move()
 181 {
 182     hash = old_hashes[--num_old_hashes];
 183
 184     num_moves -= IS_WHITE(color_to_move);
 185     SWITCH(color_to_move, other_color);
 186
 187     fifty = flags_stack[--flags_stack_ptr];
 188     castle_passing_mask = flags_stack[--flags_stack_ptr];
 189
 190     /* mark that now we do not know anything about pinnings */
 191     under_check = 0xff;
 192 }
 193
 194
 195 #ifdef DEBUG
 196     #define HEAVY_DEBUG
 197 #endif
 198
 199 //do move m and adjust hashkey
 200 void
 201 Board::do_move(const Move& m)
 202 {
 203     A88 data = this->data;
 204
 205 #ifdef HEAVY_DEBUG
 206     check_line_pawns();
 207     check_mat_tracking();
 208 #if TRACK_ATTACKS
 209     check_attacks();
 210 #endif //TRACK_ATTACKS
 211 #endif //HEAVY_DEBUG
 212     ASSERT(COLOR_OF(data[m.from]) == color_to_move);
 213     ASSERT(data[king_pos[1]] == WK);
 214     ASSERT(data[king_pos[0]] == BK);
 215     ASSERT(DISTANCE(king_pos[0], king_pos[1]) >= 2);
 216
 217     /* save the hash key */
 218     old_hashes[num_old_hashes++] = hash;
 219
 220     /* save all flags about the position */
 221     flags_stack[flags_stack_ptr++] = castle_passing_mask;
 222     flags_stack[flags_stack_ptr++] = fifty;
 223
 224 #if TRACK_ATTACKS
 225     /* attacking info, 1/2 */
 226     del_attacks(data[m.from], m.from);
 227 #endif //TRACK_ATTACKS
 228
 229     data[m.to] = data[m.from];
 230     data[m.from] = 0;
 231
 232 #if TRACK_ATTACKS
 233     /* attacking info, 2/2 */
 234     if(m.capture)
 235         replace_attacks(m.capture,data[m.to], m.to);
 236     else
 237         add_attacks(data[m.to], m.to);
 238 #endif //TRACK_ATTACKS;
 239
 240     /* update material tracking */
 241     if(m.capture)
 242         mat_remove(m.capture, m.to);
 243     mat_move( data[m.to], m.from, m.to);
 244
 245     /* update pawn tracking */
 246     if(PIECE_OF(data[m.to])==PAWN)
 247     {
 248         del_pawn(color_to_move, m.from);
 249         if(m.flags <= 4) //readd pawn to tracking structure, unless promoting
 250             add_pawn(color_to_move, m.to);
 251     }
 252     if(PIECE_OF(m.capture)==PAWN)
 253         del_pawn(other_color, m.to);
 254
 255     /* adjust hash key */
 256     hash ^= HASH_KEY( data[m.to],  m.to )
 257             ^ HASH_KEY( data[m.to],  m.from )
 258             ^ hash_key_toggle;
 259     if(m.capture)
 260         hash ^= HASH_KEY( m.capture,  m.to );
 261
 262     /* reset fifty moves count */
 263     if(m.capture || (PIECE_OF(data[m.to])==PAWN) )
 264         fifty = 0;
 265     else
 266         fifty++;
 267
 268     /* reset castle/en passant flags*/
 269     castle_passing_mask = 12 | (castle_passing_mask & castle_adj[m.from] & castle_adj[m.to]);
 270
 271     /* update king position */
 272     if(PIECE_OF(data[m.to])==KING)
 273         king_pos[IS_WHITE(data[m.to])] = m.to;
 274
 275     /* handle special moves */
 276     switch(m.flags)
 277     {
 278         case PAWNOF2:
 279             castle_passing_mask ^= 12^X(m.to);
 280             break;
 281
 282         case ENPASSANT:
 283         {
 284             uint8_t place = ROW_OF(m.from)+COL_OF(m.to);
 285             data[place] = 0;
 286             mat_remove( PAWN|other_color, place);
 287             del_pawn(other_color, place);
 288 #if TRACK_ATTACKS
 289             del_attacks(PAWN|other_color, place);
 290 #endif //TRACK_ATTACKS
 291             hash ^= HASH_KEY( PAWN|other_color,  place );
 292             break;
 293         }
 294
 295         case CASTLEKINGSIDE:
 296         {
 297             uint8_t p1 = ROW_OF(m.from)+5;
 298             uint8_t p2 = ROW_OF(m.from)+7;
 299             data[p1] = data[p2];
 300             data[p2] = 0;
 301             mat_move( data[p1], p2, p1 );
 302 #if TRACK_ATTACKS
 303             del_attacks( data[p1], p2);
 304             add_attacks( data[p1], p1);
 305 #endif //TRACK_ATTACKS
 306             hash ^= HASH_KEY( data[p1],  p1 )
 307                     ^ HASH_KEY( data[p1],  p2 );
 308             break;
 309         }
 310
 311         case CASTLEQUEENSIDE:
 312         {
 313             uint8_t p1 = ROW_OF(m.from)+3;
 314             uint8_t p2 = ROW_OF(m.from);
 315             data[p1] = data[p2];
 316             data[p2] = 0;
 317             mat_move( data[p1], p2, p1 );
 318 #if TRACK_ATTACKS
 319             del_attacks( data[p1], p2);
 320             add_attacks( data[p1], p1);
 321 #endif //TRACK_ATTACKS
 322             hash ^= HASH_KEY( data[p1],  p1 )
 323                     ^ HASH_KEY( data[p1],  p2 );
 324             break;
 325         }
 326
 327         case PROMOTE_FIRST ... PROMOTE_LAST:
 328         {
 329             uint8_t p = (m.flags-PROMOTE0)|color_to_move;
 330             hash ^= HASH_KEY( data[m.to],  m.to )
 331                     ^ HASH_KEY( p,  m.to );
 332             mat_remove( data[m.to], m.to );
 333             data[m.to] = p;
 334             mat_add( data[m.to], m.to );
 335 #if TRACK_ATTACKS
 336             replace_attacks( 0, p, m.to );
 337 #endif //TRACK_ATTACKS
 338         }
 339     }
 340
 341     /* adjust the hash key for the new castle/en passant flags*/
 342     if(flags_stack[flags_stack_ptr-2] != castle_passing_mask)
 343     {
 344         hash ^= hash_keys[ 12*64 + flags_stack[flags_stack_ptr-2] ]
 345                 ^ hash_keys[ 12*64 + castle_passing_mask ];
 346     }
 347
 348     /* switch side and increase move count */
 349     SWITCH(color_to_move, other_color);
 350     num_moves += IS_WHITE(color_to_move);
 351
 352     /* mark that now we do not know anything about pinnings */
 353     under_check = 0xff;
 354
 355     ASSERT(data[king_pos[1]] == WK);
 356     ASSERT(data[king_pos[0]] == BK);
 357     ASSERT(DISTANCE(king_pos[0], king_pos[1]) >= 2);
 358 #ifdef HEAVY_DEBUG
 359     check_line_pawns();
 360     check_mat_tracking();
 361 #if TRACK_ATTACKS
 362     check_attacks();
 363 #endif //TRACK_ATTACKS
 364 #endif //HEAVY_DEBUG
 365 }
 366
 367 //-------------------------------------------------------------------------------------
 368 //-------------------------------------------------------------------------------------
 369
 370 void
 371 Board::undo_move(const Move& m)
 372 {
 373     A88 data = this->data;
 374
 375 #ifdef HEAVY_DEBUG
 376     check_line_pawns();
 377     check_mat_tracking();
 378 #if TRACK_ATTACKS
 379     check_attacks();
 380 #endif //TRACK_ATTACKS
 381 #endif //HEAVY_DEBUG
 382     ASSERT(COLOR_OF(data[m.to]) == other_color);
 383     ASSERT(data[king_pos[1]] == WK);
 384     ASSERT(data[king_pos[0]] == BK);
 385     ASSERT(DISTANCE(king_pos[0], king_pos[1]) >= 2);
 386
 387 #if TRACK_ATTACKS
 388     /* attacking info, 1/2 */
 389     if(m.capture)
 390         replace_attacks(data[m.to], m.capture, m.to);
 391     else
 392         del_attacks(data[m.to], m.to);
 393 #endif //TRACK_ATTACKS
 394
 395     data[m.from] = data[m.to];
 396     if(m.capture)
 397         data[m.to] = m.capture;
 398     else
 399         data[m.to] = 0;
 400
 401 #if TRACK_ATTACKS
 402     /* attacking info, 2/2 */
 403     add_attacks(data[m.from], m.from);
 404 #endif //TRACK_ATTACKS
 405
 406     mat_move( data[m.from], m.to, m.from);
 407     if(m.capture)
 408         mat_add(m.capture, m.to);
 409
 410     /* update king position */
 411     if(PIECE_OF(data[m.from])==KING)
 412         king_pos[IS_WHITE(data[m.from])] = m.from;
 413
 414     /* handle special moves */
 415     switch(m.flags)
 416     {
 417         case ENPASSANT:
 418         {
 419             uint8_t place = ROW_OF(m.from)+COL_OF(m.to);
 420             data[place] = PAWN|color_to_move;
 421             mat_add( PAWN|color_to_move, place);
 422             add_pawn(color_to_move, place);
 423 #if TRACK_ATTACKS
 424             add_attacks( PAWN|color_to_move, place);
 425 #endif //TRACK_ATTACKS
 426             break;
 427         }
 428
 429         case CASTLEQUEENSIDE:
 430         {
 431             uint8_t p1 = ROW_OF(m.from)+3;
 432             uint8_t p2 = ROW_OF(m.from);
 433             data[p2] = data[p1];
 434             data[p1] = 0;
 435             mat_move( data[p2], p1, p2 );
 436 #if TRACK_ATTACKS
 437             del_attacks( data[p2], p1);
 438             add_attacks( data[p2], p2);
 439 #endif //TRACK_ATTACKS
 440             break;
 441         }
 442
 443         case CASTLEKINGSIDE:
 444         {
 445             uint8_t p1 = ROW_OF(m.from)+5;
 446             uint8_t p2 = ROW_OF(m.from)+7;
 447             data[p2] = data[p1];
 448             data[p1] = 0;
 449             mat_move( data[p2], p1, p2 );
 450 #if TRACK_ATTACKS
 451             del_attacks( data[p2], p1);
 452             add_attacks( data[p2], p2);
 453 #endif //TRACK_ATTACKS
 454             break;
 455         }
 456
 457         case PROMOTE_FIRST ... PROMOTE_LAST:
 458         {
 459             uint8_t p = PAWN|other_color;
 460 #if TRACK_ATTACKS
 461             replace_attacks( data[m.from], 0, m.from );
 462 #endif //TRACK_ATTACKS
 463             mat_remove( data[m.from], m.from );
 464             data[m.from] = p;
 465             mat_add( data[m.from], m.from );
 466         }
 467     }
 468
 469     if(PIECE_OF(data[m.from])==PAWN)
 470     {
 471         if(m.flags <= 4)
 472             del_pawn(other_color, m.to);
 473         add_pawn(other_color, m.from);
 474     }
 475     if(PIECE_OF(m.capture)==PAWN)
 476         add_pawn(color_to_move, m.to);
 477
 478     /* load saved flags */
 479     fifty = flags_stack[--flags_stack_ptr];
 480     castle_passing_mask = flags_stack[--flags_stack_ptr];
 481     hash = old_hashes[--num_old_hashes];
 482
 483     /* switch side and increase move count */
 484     num_moves -= IS_WHITE(color_to_move);
 485     SWITCH(color_to_move, other_color);
 486
 487     /* mark that now we do not know anything about pinnings */
 488     under_check = 0xff;
 489
 490     ASSERT(data[king_pos[1]] == WK);
 491     ASSERT(data[king_pos[0]] == BK);
 492     ASSERT(DISTANCE(king_pos[0], king_pos[1]) >= 2);
 493 #ifdef HEAVY_DEBUG
 494     check_line_pawns();
 495     check_mat_tracking();
 496 #if TRACK_ATTACKS
 497     check_attacks();
 498 #endif //TRACK_ATTACKS
 499 #endif //HEAVY_DEBUG
 500 }