src/movegen.cpp

   1 /* Copyright (C) 2007-2011 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 <assert.h>
  18 #include <iostream>
  19
  20 #include "game.h"
  21
  22 void Moves::generate_pieces(Color c, PieceType t, MoveType mt)
  23 {
  24     const Direction * dirs = PIECES_DIRS[t];
  25     for (int j = 0; j < pieces.count(c, t); ++j) {
  26         Square from = pieces.get_position(c, t, j);
  27         for (int d = 0; d < NB_DIRS[t]; ++d) {
  28             Square to = Square(from + dirs[d]);
  29             while (!board.is_out(to)) {
  30                 if (!board.is_empty(to)) {
  31                     if (board[to].color() == c) break;
  32                     if (mt != QUIET_MOVE) {
  33                         add(Move(from, to, CAPTURE));
  34                     }
  35                     break;
  36                 } else if (mt != CAPTURE) {
  37                     add(Move(from, to, QUIET_MOVE));
  38                 }
  39                 if (t == KNIGHT || t == KING) break; // Leapers
  40                 to = Square(to + dirs[d]); // Sliders
  41             }
  42         }
  43     }
  44 }
  45
  46 void Moves::generate(MoveType mt)
  47 {
  48     Color c = current_position.get_turn_color();
  49
  50     // Pawns moves
  51     for (int j = 0; j < pieces.count(c, PAWN); ++j) {
  52         Square from = pieces.get_position(c, PAWN, j);
  53
  54         // Pawn captures
  55         for (int d = 0; d < 2; ++d) {
  56             if (mt == QUIET_MOVE) break;
  57             Square to = Square(from + PAWN_CAPTURE_DIRS[c][d]);
  58             if (board.is_out(to)) continue;
  59             if (!board.is_empty(to) && board[to].color() != c) {
  60                 if (board.is_pawn_end(c, to)) { // Promotion capture
  61                     add(Move(from, to, KNIGHT_PROMOTION_CAPTURE));
  62                     add(Move(from, to, BISHOP_PROMOTION_CAPTURE));
  63                     add(Move(from, to, ROOK_PROMOTION_CAPTURE));
  64                     add(Move(from, to, QUEEN_PROMOTION_CAPTURE));
  65                 } else { // Capture
  66                     add(Move(from, to, CAPTURE));
  67                 }
  68             } else if (to == current_position.get_en_passant()) { // En passant
  69                 add(Move(from, to, EN_PASSANT));
  70             }
  71         }
  72
  73         if (mt == CAPTURE) continue;
  74         Square to = Square(from + PAWN_PUSH_DIRS[c]);
  75         assert(!board.is_out(to)); // Should never happend
  76         if (!board.is_empty(to)) continue;
  77
  78         // Promotion
  79         if (board.is_pawn_end(c, to)) {
  80             add(Move(from, to, KNIGHT_PROMOTION));
  81             add(Move(from, to, BISHOP_PROMOTION));
  82             add(Move(from, to, ROOK_PROMOTION));
  83             add(Move(from, to, QUEEN_PROMOTION));
  84             continue;
  85         }
  86
  87         // Pawn push
  88         add(Move(from, to, QUIET_MOVE));
  89
  90         // Double pawn push
  91         if (board.is_pawn_begin(c, from)) {
  92             to = Square(to + PAWN_PUSH_DIRS[c]);
  93             if (!board.is_empty(to)) continue;
  94             add(Move(from, to, DOUBLE_PAWN_PUSH));
  95         }
  96     }
  97
  98     // Standard moves
  99     for (const PieceType& t : NOT_PAWN_TYPES) {
 100         generate_pieces(c, t, mt);
 101     }
 102
 103     if (mt == CAPTURE) return;
 104
 105     // Castling
 106     if (current_position.can_castle(c, KING)) {
 107         Square from = Square(E1 + A8 * c);
 108         Square to = Square(G1 + A8 * c);
 109         Square rook = Square(H1 + A8 * c);
 110         if (board.is_empty(Square(F1 + A8 * c)) &&
 111             board.is_empty(to) &&
 112             board[rook].type() == ROOK &&
 113             board[rook].color() == c &&
 114             !board.is_attacked_by(!c, from, pieces) &&
 115             !board.is_attacked_by(!c, to, pieces) &&
 116             !board.is_attacked_by(!c, Square((F1 + A8 * c)), pieces)
 117             ) {
 118             add(Move(from, to, KING_CASTLE));
 119         }
 120     }
 121     if (current_position.can_castle(c, QUEEN)) {
 122         Square from = Square(E1 + A8 * c);
 123         Square to = Square(C1 + A8 * c);
 124         Square rook = Square(A1 + A8 * c);
 125         if (board.is_empty(Square(B1 + A8 * c)) &&
 126             board.is_empty(Square(D1 + A8 * c)) &&
 127             board.is_empty(to) &&
 128             board[rook].type() == ROOK &&
 129             board[rook].color() == c &&
 130             !board.is_attacked_by(!c, from, pieces) &&
 131             !board.is_attacked_by(!c, to, pieces) &&
 132             !board.is_attacked_by(!c, Square((D1 + A8 * c)), pieces)
 133             ) {
 134             add(Move(from, to, QUEEN_CASTLE));
 135         }
 136     }
 137 }
 138
 139 void Game::make_move(Move m)
 140 {
 141     Square orig = m.orig();
 142     Square dest = m.dest();
 143     Square ep = current_position().get_en_passant();
 144     Color c = current_position().get_turn_color();
 145     Piece p = board[orig];
 146     PieceType t = p.type();
 147     Piece capture;
 148     assert(!board.is_out(orig));
 149     assert(!board.is_out(dest));
 150
 151     ++nodes_count;
 152     new_position(); // current_position() is now refering to a new position
 153     Position& pos = current_position();
 154
 155     // Update halfmove counter
 156     if (t == PAWN || m.is_capture()) {
 157         pos.reset_halfmove();
 158     } else {
 159         pos.inc_halfmove();
 160     }
 161
 162     // Null Move
 163     if (m.is_null()) {
 164         pos.set_en_passant(OUT);
 165         return;
 166     }
 167
 168     // Update castling rights
 169     if ((pos.can_castle(c, KING)) &&
 170         (t == KING || (t == ROOK && orig == Square(H1 + A8 * c)))) {
 171         pos.set_castle_right(c, KING, false);
 172         zobrist.update_castle_right(pos.hash(), c, KING);
 173     }
 174     if ((pos.can_castle(c, QUEEN)) &&
 175         (t == KING || (t == ROOK && orig == Square(A1 + A8 * c)))) {
 176         pos.set_castle_right(c, QUEEN, false);
 177         zobrist.update_castle_right(pos.hash(), c, QUEEN);
 178     }
 179
 180     // Capture
 181     if (m.is_capture()) {
 182         Square s = dest;
 183         if (m.is_en_passant()) {
 184             s = (c == BLACK ? Square(ep + UP) : Square(ep + DOWN));
 185         }
 186         assert(!board.is_empty(s) || assert_msg(debug_move(m)));
 187
 188         capture = board[s];
 189         if (capture.type() == ROOK) { // Update opponent's castling rights
 190             if (dest == Square(H1 + A8 * !c)) {
 191                 pos.set_castle_right(!c, KING, false);
 192                 zobrist.update_castle_right(pos.hash(), !c, KING);
 193             } else if (dest == Square(A1 + A8 * !c)) {
 194                 pos.set_castle_right(!c, QUEEN, false);
 195                 zobrist.update_castle_right(pos.hash(), !c, QUEEN);
 196             }
 197         }
 198         del_piece(capture);
 199         assert(board.is_empty(s) || assert_msg(debug_move(m)));
 200     }
 201
 202     // Castling
 203     if (m.is_castle()) {
 204         Square rook_orig, rook_dest;
 205         switch (m.castle_side()) {
 206             case KING:
 207                 rook_orig = Square(H1 + A8 * c);
 208                 rook_dest = Square(F1 + A8 * c);
 209                 break;
 210             case QUEEN:
 211                 rook_orig = Square(A1 + A8 * c);
 212                 rook_dest = Square(D1 + A8 * c);
 213                 break;
 214             default:
 215                 assert(false);
 216                 rook_orig = OUT;
 217                 rook_dest = OUT;
 218                 break;
 219         }
 220         Piece rook = board[rook_orig];
 221         board[rook_orig] = Piece();
 222         board[rook_dest] = rook;
 223         pieces.set_position(rook, rook_dest);
 224         zobrist.update_piece(pos.hash(), c, ROOK, rook_orig);
 225         zobrist.update_piece(pos.hash(), c, ROOK, rook_dest);
 226         pos.set_has_castle(c); // For bonus/malus in eval
 227     }
 228
 229     // Move the piece
 230     board[orig] = Piece(); // FIXME: duplicate in case of promotion?
 231     if (m.is_promotion()) {
 232         add_piece(p.color(), m.promotion_type(), dest);
 233         del_piece(p);
 234     } else {
 235         board[dest] = p;
 236         pieces.set_position(p, dest);
 237         zobrist.update_piece(pos.hash(), c, t, orig);
 238         zobrist.update_piece(pos.hash(), c, t, dest);
 239     }
 240
 241     // Update en passant
 242     pos.set_capture(capture);
 243     if (m.is_double_pawn_push()) {
 244         Square new_ep = Square(orig + (dest - orig) / 2);
 245         pos.set_en_passant(new_ep);
 246         zobrist.update_en_passant(pos.hash(), new_ep);
 247     } else {
 248         pos.set_en_passant(OUT);
 249     }
 250 }
 251
 252 void Game::undo_move(Move m)
 253 {
 254     Square orig = m.orig();
 255     Square dest = m.dest();
 256
 257     // Move back the piece to its origin
 258     Piece p = board[dest];
 259     if (m.is_promotion()) {
 260         add_piece(p.color(), PAWN, orig);
 261         del_piece(p);
 262     } else if (!m.is_null()) {
 263         board[orig] = p;
 264         pieces.set_position(p, orig);
 265     }
 266
 267     // Restore captured piece
 268     if (m.is_capture()) {
 269         Piece capture = current_position().get_capture();
 270         Square s = dest;
 271         if (m.is_en_passant()) {
 272             Color c = current_position().get_turn_color();
 273             s = (c == WHITE ? Square(dest + UP) : Square(dest + DOWN));
 274             board[dest] = Piece();
 275         }
 276         add_piece(capture.color(), capture.type(), s);
 277     } else if (!m.is_null()) {
 278         board[dest] = Piece();
 279     }
 280     del_position();
 281     if (m.is_null()) return;
 282     if (m.is_castle()) {
 283         Square rook_orig, rook_dest;
 284         Color c = current_position().get_turn_color();
 285         switch (m.castle_side()) {
 286             case KING:
 287                 rook_orig = Square(H1 + A8 * c);
 288                 rook_dest = Square(F1 + A8 * c);
 289                 break;
 290             case QUEEN:
 291                 rook_orig = Square(A1 + A8 * c);
 292                 rook_dest = Square(D1 + A8 * c);
 293                 break;
 294             default:
 295                 assert(false);
 296                 rook_orig = OUT;
 297                 rook_dest = OUT;
 298                 break;
 299         }
 300         Piece rook = board[rook_dest];
 301         board[rook_dest] = Piece();
 302         board[rook_orig] = rook;
 303         pieces.set_position(rook, rook_orig);
 304     }
 305 }
 306
 307 /*
 308  * Check the pseudo legality of a move m
 309  */
 310 bool Game::is_legal(Move m)
 311 {
 312     // Null-move is obviously wrong
 313     if (m.is_null()) return false;
 314
 315     Square from = m.orig();
 316     Square to = m.dest();
 317
 318     // There must be a piece to move on the board
 319     if (board.is_empty(from)) return false;
 320
 321     Piece p = board[from];
 322     PieceType t = p.type();
 323     Color c = p.color();
 324
 325     // The piece cannot be one of the opponent
 326     if (c != current_position().get_turn_color()) return false;
 327
 328     // It must be able to do the move
 329     if (!m.is_en_passant() && !m.is_castle()) {
 330         if (!board.can_go(p, from, to)) return false;
 331     }
 332
 333     // Promotion
 334     if (t == PAWN && board.is_pawn_end(c, to) && !m.is_promotion()) {
 335         return false;
 336     }
 337     if (m.is_promotion()) {
 338         if (t != PAWN || !board.is_pawn_end(c, to)) return false;
 339     }
 340
 341     // If it's a capture
 342     if (m.is_capture()) {
 343         Square s = to;
 344
 345         // There are special conditions for en passant
 346         if (m.is_en_passant()) {
 347             // It must be a pawn
 348             if (t != PAWN) return false;
 349
 350             // After a double push
 351             Square ep = current_position().get_en_passant();
 352             if (to != ep) return false;
 353
 354             // from another pawn, the later being captured by the former
 355             s = (c == BLACK ? Square(ep + UP) : Square(ep + DOWN));
 356             if (board[s].type() != PAWN) return false;
 357         }
 358
 359         // An opponent's piece must be captured
 360         if (board.is_empty(s)) return false;
 361         if (c == board[s].color()) return false;
 362
 363     } else if (m.is_castle()) {
 364         Square rook = Square(H1 + A8 * c);
 365         switch (m.castle_side()) {
 366             case KING:
 367                 rook = Square(H1 + A8 * c);
 368                 if (!board.is_empty(Square(F1 + A8 * c)) ||
 369                     !board.is_empty(to) ||
 370                     board[rook].type() != ROOK ||
 371                     board[rook].color() != c ||
 372                     board.is_attacked_by(!c, from, pieces) ||
 373                     board.is_attacked_by(!c, Square((F1 + A8 * c)), pieces) ||
 374                     board.is_attacked_by(!c, to, pieces)) {
 375                         return false;
 376                 }
 377                 break;
 378             case QUEEN:
 379                 rook = Square(A1 + A8 * c);
 380                 if (!board.is_empty(Square(B1 + A8 * c)) ||
 381                     !board.is_empty(Square(D1 + A8 * c)) ||
 382                     !board.is_empty(to) ||
 383                     board[rook].type() != ROOK ||
 384                     board[rook].color() != c ||
 385                     board.is_attacked_by(!c, from, pieces) ||
 386                     board.is_attacked_by(!c, Square((D1 + A8 * c)), pieces) ||
 387                     board.is_attacked_by(!c, to, pieces)) {
 388                         return false;
 389                 }
 390                 break;
 391             default: return false;
 392         }
 393         return true;
 394     } else if (m.is_double_pawn_push()) {
 395         if (t != PAWN) return false;
 396         if (!board.is_pawn_begin(c, from)) return false; // Done by can_go()
 397     } else if (!board.is_empty(to)) {
 398         return false;
 399     }
 400
 401     // TODO: Add check
 402     return true;
 403 }