src/movegen.cpp

   1 /* Copyright (C) 2007-2012 Vincent Ollivier
   2  *
   3  * Purple Haze is free software: you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License as published by
   5  * the Free Software Foundation, either version 3 of the License, or
   6  * (at your option) any later version.
   7  *
   8  * Purple Haze is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  15  */
  16
  17 #include <cassert>
  18 #include <iostream>
  19
  20 #include "game.h"
  21
  22 static bool king_castle_allowed(const Color c,
  23                                 const Square from, const Square to,
  24                                 const Board &board, const Pieces &pieces)
  25 {
  26     assert(from == Board::flip(E1, c));
  27     assert(to == Board::flip(G1, c));
  28     const Square rook = Board::flip(H1, c);
  29     return
  30         board.is_empty(Board::flip(F1, c)) &&
  31         board.is_empty(to) &&
  32         board[rook].is(c, ROOK) &&
  33         !board.is_attacked_by(!c, from, pieces) &&
  34         !board.is_attacked_by(!c, to, pieces) &&
  35         !board.is_attacked_by(!c, Board::flip(F1, c), pieces);
  36 }
  37
  38 static bool queen_castle_allowed(const Color c,
  39                                  const Square from, const Square to,
  40                                  const Board &board, const Pieces &pieces)
  41 {
  42     assert(from == Board::flip(E1, c));
  43     assert(to == Board::flip(C1, c));
  44     const Square rook = Board::flip(A1, c);
  45     return
  46         board.is_empty(Board::flip(B1, c)) &&
  47         board.is_empty(Board::flip(D1, c)) &&
  48         board.is_empty(to) &&
  49         board[rook].is(c, ROOK) &&
  50         !board.is_attacked_by(!c, from, pieces) &&
  51         !board.is_attacked_by(!c, to, pieces) &&
  52         !board.is_attacked_by(!c, Board::flip(D1, c), pieces);
  53 }
  54
  55 void Moves::generate_pieces(Color c, PieceType t, MoveType mt)
  56 {
  57     for (int i = 0, n = pieces.count(c, t); i < n; ++i) {
  58         const Square from = pieces.position(c, t, i);
  59         for (const Direction &dir : PIECES_DIRS[t]) {
  60             Square to = static_cast<Square>(from + dir);
  61             while (!board.is_out(to)) {
  62                 if (!board.is_empty(to)) {
  63                     if (board[to].is(c)) {
  64                         break;
  65                     }
  66                     if (mt != QUIET_MOVE) {
  67                         add(Move(from, to, CAPTURE));
  68                     }
  69                     break;
  70                 } else if (mt != CAPTURE) {
  71                     add(Move(from, to, QUIET_MOVE));
  72                 }
  73                 if (t == KNIGHT || t == KING) {
  74                     break; // Leapers
  75                 }
  76                 to = static_cast<Square>(to + dir); // Sliders
  77             }
  78         }
  79     }
  80 }
  81
  82 void Moves::generate(MoveType mt)
  83 {
  84     const Color c = current_position.side();
  85
  86     // Pawns moves
  87     for (int i = 0, n = pieces.count(c, PAWN); i < n; ++i) {
  88         const Square from = pieces.position(c, PAWN, i);
  89
  90         // Pawn captures
  91         if (mt != QUIET_MOVE) {
  92             for (const Direction &dir : PAWN_CAPTURE_DIRS[c]) {
  93                 const Square to = static_cast<Square>(from + dir);
  94                 if (board.is_out(to)) {
  95                     continue;
  96                 }
  97                 if (!board.is_empty(to) && board[to].color() != c) {
  98                     if (board.is_pawn_end(c, to)) {
  99                         // Promotion capture
 100                         add(Move(from, to, KNIGHT_PROMOTION_CAPTURE));
 101                         add(Move(from, to, BISHOP_PROMOTION_CAPTURE));
 102                         add(Move(from, to, ROOK_PROMOTION_CAPTURE));
 103                         add(Move(from, to, QUEEN_PROMOTION_CAPTURE));
 104                     } else {
 105                         // Capture
 106                         add(Move(from, to, CAPTURE));
 107                     }
 108                 } else if (to == current_position.en_passant()) {
 109                     // En passant
 110                     add(Move(from, to, EN_PASSANT));
 111                 }
 112             }
 113         }
 114
 115         if (mt == CAPTURE) {
 116             continue;
 117         }
 118         Square to = static_cast<Square>(from + PAWN_PUSH_DIRS[c]);
 119         assert(!board.is_out(to)); // Should never happend
 120         if (!board.is_empty(to)) {
 121             continue;
 122         }
 123
 124         // Promotion
 125         if (board.is_pawn_end(c, to)) {
 126             add(Move(from, to, KNIGHT_PROMOTION));
 127             add(Move(from, to, BISHOP_PROMOTION));
 128             add(Move(from, to, ROOK_PROMOTION));
 129             add(Move(from, to, QUEEN_PROMOTION));
 130             continue;
 131         }
 132
 133         // Pawn push
 134         add(Move(from, to, QUIET_MOVE));
 135
 136         // Double pawn push
 137         if (board.is_pawn_begin(c, from)) {
 138             to = static_cast<Square>(to + PAWN_PUSH_DIRS[c]);
 139             if (!board.is_empty(to)) {
 140                 continue;
 141             }
 142             add(Move(from, to, DOUBLE_PAWN_PUSH));
 143         }
 144     }
 145
 146     // Standard moves
 147     for (const PieceType& t : NOT_PAWN_TYPES) {
 148         generate_pieces(c, t, mt);
 149     }
 150
 151     if (mt == CAPTURE) {
 152         return;
 153     }
 154
 155     // Castling
 156     const Square from = Board::flip(E1, c);
 157     if (current_position.can_castle(c, KING)) {
 158         const Square to = Board::flip(G1, c);
 159         if (king_castle_allowed(c, from, to, board, pieces)) {
 160             add(Move(from, to, KING_CASTLE));
 161         }
 162     }
 163     if (current_position.can_castle(c, QUEEN)) {
 164         const Square to = Board::flip(C1, c);
 165         if (queen_castle_allowed(c, from, to, board, pieces)) {
 166             add(Move(from, to, QUEEN_CASTLE));
 167         }
 168     }
 169 }
 170
 171 void Game::make_move(Move m)
 172 {
 173     const Square orig = m.orig();
 174     const Square dest = m.dest();
 175     const Square ep = current_position().en_passant();
 176     const Color c = current_position().side();
 177     const Piece p = board[orig];
 178     const PieceType t = p.type();
 179     assert(!board.is_out(orig));
 180     assert(!board.is_out(dest));
 181
 182     ++nodes_count;
 183     new_position(); // current_position() is now refering to a new position
 184     Position& pos = current_position();
 185
 186     // Update halfmove counter
 187     if (t == PAWN || m.is_capture()) {
 188         pos.reset_halfmove();
 189     } else {
 190         pos.inc_halfmove();
 191     }
 192
 193     // Null Move
 194     if (m.is_null()) {
 195         pos.set_en_passant(OUT);
 196         return;
 197     }
 198
 199     // Update castling rights
 200     if (pos.can_castle(c, KING)) {
 201         if (t == KING || (t == ROOK && orig == Board::flip(H1, c))) {
 202             pos.set_castle_right(c, KING, false);
 203             zobrist.update_castle_right(pos.hash(), c, KING);
 204         }
 205     }
 206     if (pos.can_castle(c, QUEEN)) {
 207         if (t == KING || (t == ROOK && orig == Board::flip(A1, c))) {
 208             pos.set_castle_right(c, QUEEN, false);
 209             zobrist.update_castle_right(pos.hash(), c, QUEEN);
 210         }
 211     }
 212
 213     // Capture
 214     if (m.is_capture()) {
 215         Square s = dest;
 216         if (m.is_en_passant()) {
 217             s = static_cast<Square>(ep + PAWN_PUSH_DIRS[!c]);
 218         }
 219         assert(!board.is_empty(s));
 220
 221         Piece capture = board[s];
 222         if (capture.is(ROOK)) { // Update opponent's castling rights
 223             if (dest == Board::flip(H1, !c)) {
 224                 pos.set_castle_right(!c, KING, false);
 225                 zobrist.update_castle_right(pos.hash(), !c, KING);
 226             } else if (dest == Board::flip(A1, !c)) {
 227                 pos.set_castle_right(!c, QUEEN, false);
 228                 zobrist.update_castle_right(pos.hash(), !c, QUEEN);
 229             }
 230         }
 231         del_piece(capture);
 232         pos.set_capture(capture);
 233         assert(board.is_empty(s));
 234     }
 235
 236     // Castling
 237     if (m.is_castle()) {
 238         Square rook_orig;
 239         Square rook_dest;
 240         switch (m.castle_side()) {
 241         case KING:
 242             rook_orig = Board::flip(H1, c);
 243             rook_dest = Board::flip(F1, c);
 244             break;
 245         case QUEEN:
 246             rook_orig = Board::flip(A1, c);
 247             rook_dest = Board::flip(D1, c);
 248             break;
 249         default:
 250             assert(false);
 251             rook_orig = OUT;
 252             rook_dest = OUT;
 253             break;
 254         }
 255         Piece rook = board[rook_orig];
 256         board[rook_orig] = Piece();
 257         board[rook_dest] = rook;
 258         pieces.set_position(rook, rook_dest);
 259         zobrist.update_piece(pos.hash(), c, ROOK, rook_orig);
 260         zobrist.update_piece(pos.hash(), c, ROOK, rook_dest);
 261         pos.set_has_castled(c); // For bonus/malus in eval
 262     }
 263
 264     // Move the piece
 265     if (m.is_promotion()) {
 266         add_piece(p.color(), m.promotion_type(), dest);
 267         del_piece(p);
 268     } else {
 269         board[orig] = Piece();
 270         board[dest] = p;
 271         pieces.set_position(p, dest);
 272         zobrist.update_piece(pos.hash(), c, t, orig);
 273         zobrist.update_piece(pos.hash(), c, t, dest);
 274     }
 275
 276     // Update en passant
 277     if (m.is_double_pawn_push()) {
 278         Square new_ep = static_cast<Square>((orig + dest) / 2);
 279         pos.set_en_passant(new_ep);
 280         zobrist.update_en_passant(pos.hash(), new_ep);
 281     } else {
 282         pos.set_en_passant(OUT);
 283     }
 284 }
 285
 286 void Game::undo_move(Move m)
 287 {
 288     Square orig = m.orig();
 289     Square dest = m.dest();
 290
 291     // Move back the piece to its origin
 292     Piece p = board[dest];
 293     if (m.is_promotion()) {
 294         add_piece(p.color(), PAWN, orig);
 295         del_piece(p);
 296     } else if (!m.is_null()) {
 297         board[orig] = p;
 298         pieces.set_position(p, orig);
 299     }
 300
 301     // Restore captured piece
 302     if (m.is_capture()) {
 303         Piece capture = current_position().capture();
 304         Square s = dest;
 305         if (m.is_en_passant()) {
 306             const Color c = current_position().side();
 307             s = static_cast<Square>(dest + PAWN_PUSH_DIRS[c]);
 308             board[dest] = Piece();
 309         }
 310         add_piece(capture.color(), capture.type(), s);
 311     } else if (!m.is_null()) {
 312         board[dest] = Piece();
 313     }
 314     del_position();
 315     if (m.is_null()) {
 316         return;
 317     }
 318     if (m.is_castle()) {
 319         const Color c = current_position().side();
 320         Square rook_orig;
 321         Square rook_dest;
 322         switch (m.castle_side()) {
 323         case KING:
 324             rook_orig = Board::flip(H1, c);
 325             rook_dest = Board::flip(F1, c);
 326             break;
 327         case QUEEN:
 328             rook_orig = Board::flip(A1, c);
 329             rook_dest = Board::flip(D1, c);
 330             break;
 331         default:
 332             assert(false);
 333             rook_orig = OUT;
 334             rook_dest = OUT;
 335             break;
 336         }
 337         Piece rook = board[rook_dest];
 338         board[rook_dest] = Piece();
 339         board[rook_orig] = rook;
 340         pieces.set_position(rook, rook_orig);
 341     }
 342 }
 343
 344 /*
 345  * Check the pseudo legality of a move m
 346  */
 347 bool Game::is_legal(Move m)
 348 {
 349     // Null-move is obviously wrong
 350     if (m.is_null()) {
 351         return false;
 352     }
 353
 354     Square from = m.orig();
 355     Square to = m.dest();
 356
 357     // There must be a piece to move on the board
 358     if (board.is_empty(from)) {
 359         return false;
 360     }
 361
 362     const Piece p = board[from];
 363     const PieceType t = p.type();
 364     const Color c = p.color();
 365
 366     // The piece cannot be one of the opponent
 367     if (c != current_position().side()) {
 368         return false;
 369     }
 370
 371     // It must be able to do the move
 372     if (!m.is_en_passant() && !m.is_castle()) {
 373         if (!board.can_go(p, from, to)) {
 374             return false;
 375         }
 376     }
 377
 378     // Promotion
 379     if (t == PAWN && board.is_pawn_end(c, to) && !m.is_promotion()) {
 380         return false;
 381     }
 382     if (m.is_promotion()) {
 383         if (t != PAWN || !board.is_pawn_end(c, to)) {
 384             return false;
 385         }
 386     }
 387
 388     // If it's a capture
 389     if (m.is_capture()) {
 390         Square s = to;
 391
 392         // There are special conditions for en passant
 393         if (m.is_en_passant()) {
 394             if (t != PAWN) { // It must be a pawn
 395                 return false;
 396             }
 397             Square ep = current_position().en_passant();
 398             if (to != ep) { // After a double push
 399                 return false;
 400             }
 401             // from another pawn, the later being captured by the former
 402             s = static_cast<Square>(ep + PAWN_PUSH_DIRS[!c]);
 403             if (board[s].type() != PAWN) {
 404                 return false;
 405             }
 406         }
 407
 408         // An opponent's piece must be captured
 409         if (board.is_empty(s)) {
 410             return false;
 411         }
 412         if (c == board[s].color()) {
 413             return false;
 414         }
 415
 416     } else if (m.is_castle()) {
 417         if (from != Board::flip(E1, c)) {
 418             return false;
 419         }
 420         switch (m.castle_side()) {
 421         case KING:
 422             return king_castle_allowed(c, from, to, board, pieces);
 423         case QUEEN:
 424             return queen_castle_allowed(c, from, to, board, pieces);
 425         default:
 426             return false;
 427         }
 428     } else if (m.is_double_pawn_push()) {
 429         if (t != PAWN) {
 430             return false;
 431         }
 432         if (!board.is_pawn_begin(c, from)) {
 433             return false; // Done by can_go()
 434         }
 435     } else if (!board.is_empty(to)) {
 436         return false;
 437     }
 438
 439     // TODO: Add check
 440     return true;
 441 }