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