src/chessboard.cpp

   1 /*
   2     This file is part of OmniPerft.
   3     Copyright (C) 2008 Ilari Pihlajisto
   4
   5     OmniPerft is free software: you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation, either version 3 of the License, or
   8     (at your option) any later version.
   9
  10     OmniPerft is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with OmniPerft.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 #include <iostream>
  20 #include <cassert>
  21 #include "chessboard.h"
  22 #include "notation.h"
  23 #include "zobrist.h"
  24
  25 using namespace Chess;
  26
  27
  28 Board::Board(Variant variant)
  29 : m_variant(variant), m_isRandom(false)
  30 {
  31         switch (m_variant) {
  32         case StandardChess:
  33                 m_width = 8;
  34                 m_height = 8;
  35                 break;
  36         case CapablancaChess:
  37                 m_width = 10;
  38                 m_height = 8;
  39                 break;
  40         }
  41
  42         // Allocate the squares, with one 'wall' file on both sides,
  43         // and two 'wall' ranks at the top and bottom.
  44         m_arwidth = m_width + 2;
  45         m_squares.resize(m_arwidth * (m_height + 4), InvalidPiece);
  46
  47
  48         // Initialize the move offsets
  49
  50         m_castleTarget[White][QueenSide] = (m_height + 1) * m_arwidth + 3;
  51         m_castleTarget[White][KingSide] = (m_height + 1) * m_arwidth + m_width - 1;
  52         m_castleTarget[Black][QueenSide] = 2 * m_arwidth + 3;
  53         m_castleTarget[Black][KingSide] = 2 * m_arwidth + m_width - 1;
  54
  55         m_knightOffsets.resize(8);
  56         m_knightOffsets[0] = -2 * m_arwidth - 1;
  57         m_knightOffsets[1] = -2 * m_arwidth + 1;
  58         m_knightOffsets[2] = -m_arwidth - 2;
  59         m_knightOffsets[3] = -m_arwidth + 2;
  60         m_knightOffsets[4] = m_arwidth - 2;
  61         m_knightOffsets[5] = m_arwidth + 2;
  62         m_knightOffsets[6] = 2 * m_arwidth - 1;
  63         m_knightOffsets[7] = 2 * m_arwidth + 1;
  64
  65         m_bishopOffsets.resize(4);
  66         m_bishopOffsets[0] = -m_arwidth - 1;
  67         m_bishopOffsets[1] = -m_arwidth + 1;
  68         m_bishopOffsets[2] = m_arwidth - 1;
  69         m_bishopOffsets[3] = m_arwidth + 1;
  70
  71         m_rookOffsets.resize(4);
  72         m_rookOffsets[0] = -m_arwidth;
  73         m_rookOffsets[1] = -1;
  74         m_rookOffsets[2] = 1;
  75         m_rookOffsets[3] = m_arwidth;
  76 }
  77
  78 void Board::initZobristKey()
  79 {
  80         m_key = 0;
  81
  82         for (int side = White; side <= Black; side++) {
  83                 const int* rookSq = m_castlingRights.rookSquare[side];
  84                 if (rookSq[QueenSide] != 0)
  85                         m_key ^= Zobrist::castling(side, rookSq[QueenSide]);
  86                 if (rookSq[KingSide] != 0)
  87                         m_key ^= Zobrist::castling(side, rookSq[KingSide]);
  88
  89                 int sign = (side == White) ? 1 : -1;
  90                 for (unsigned sq = 0; sq < m_squares.size(); sq++) {
  91                         int piece = m_squares[sq];
  92                         if (piece == InvalidPiece || piece * sign <= 0)
  93                                 continue;
  94
  95                         m_key ^= Zobrist::piece(side, piece * sign, sq);
  96                 }
  97         }
  98
  99         if (m_enpassantSquare != 0)
 100                 m_key ^= Zobrist::enpassant(m_enpassantSquare);
 101         if (m_side == Black)
 102                 m_key ^= Zobrist::side();
 103 }
 104
 105 Variant Board::variant() const
 106 {
 107         return m_variant;
 108 }
 109
 110 uint64_t Board::key() const
 111 {
 112         return m_key;
 113 }
 114
 115 void Board::print() const
 116 {
 117         int i = m_arwidth * 2;
 118         for (int y = 0; y < m_height; y++) {
 119                 i++;
 120                 for (int x = 0; x < m_width; x++) {
 121                         int pc = m_squares[i];
 122                         char c = '.';
 123
 124                         if (pc != NoPiece)
 125                                 c = Notation::pieceChar(pc);
 126                         std::cout << c << " ";
 127
 128                         i++;
 129                 }
 130                 i++;
 131                 std::cout << std::endl;
 132         }
 133         std::cout << "FEN: " << fenString() << std::endl;
 134 }
 135
 136 void Board::printMoves(Chess::MoveNotation notation)
 137 {
 138         std::vector<Move> moves = legalMoves();
 139         std::vector<Move>::iterator it;
 140         for (it = moves.begin(); it != moves.end(); ++it)
 141                 std::cout << moveString(*it, notation) << std::endl;
 142 }
 143
 144 Square Board::chessSquare(int index) const
 145 {
 146         int file = (index % m_arwidth) - 1;
 147         int rank = (m_height - 1) - ((index / m_arwidth) - 2);
 148         Square square = { file, rank };
 149
 150         return square;
 151 }
 152
 153 int Board::squareIndex(const Square& square) const
 154 {
 155         if (square.file < 0 || square.file >= m_width
 156         ||  square.rank < 0 || square.rank >= m_height)
 157                 return 0;
 158
 159         int rank = (m_height - 1) - square.rank;
 160         return (rank + 2) * m_arwidth + 1 + square.file;
 161 }
 162
 163 bool Board::isValidSquare(const Chess::Square& square) const
 164 {
 165         if (square.file < 0 || square.file >= m_width
 166         ||  square.rank < 0 || square.rank >= m_height)
 167                 return false;
 168         return true;
 169 }
 170
 171 bool Board::inCheck(int side, int square) const
 172 {
 173         if (square == 0)
 174                 square = m_kingSquare[side];
 175
 176         int sign = (side == White) ? 1 : -1;
 177         int attacker;
 178
 179         // Pawn attacks
 180         int step = -sign * m_arwidth;
 181         // Left side
 182         attacker  = m_squares[square + step - 1];
 183         if ((attacker * sign) == -Pawn)
 184                 return true;
 185         // Right side
 186         attacker = m_squares[square + step + 1];
 187         if ((attacker * sign) == -Pawn)
 188                 return true;
 189
 190         std::vector<int>::const_iterator it;
 191
 192         // Knight, archbishop, chancellor attacks
 193         for (it = m_knightOffsets.begin(); it != m_knightOffsets.end(); ++it) {
 194                 attacker = m_squares[square + *it];
 195                 switch (attacker * sign) {
 196                 case -Knight: case -Archbishop: case -Chancellor:
 197                         return true;
 198                 }
 199         }
 200
 201         // Bishop, queen, archbishop, king attacks
 202         for (it = m_bishopOffsets.begin(); it != m_bishopOffsets.end(); ++it) {
 203                 int targetSquare = square + *it;
 204                 if (targetSquare == m_kingSquare[!side])
 205                         return true;
 206                 while ((attacker = m_squares[targetSquare]) != InvalidPiece
 207                 &&      attacker * sign <= 0) {
 208                         switch (attacker * sign) {
 209                         case -Bishop: case -Queen: case -Archbishop:
 210                                 return true;
 211                         }
 212                         if (attacker != NoPiece)
 213                                 break;
 214                         targetSquare += *it;
 215                 }
 216         }
 217
 218         // Rook, queen, chancellor, king attacks
 219         for (it = m_rookOffsets.begin(); it != m_rookOffsets.end(); ++it) {
 220                 int targetSquare = square + *it;
 221                 if (targetSquare == m_kingSquare[!side])
 222                         return true;
 223                 while ((attacker = m_squares[targetSquare]) != InvalidPiece
 224                 &&      attacker * sign <= 0) {
 225                         switch (attacker * sign) {
 226                         case -Rook: case -Queen: case -Chancellor:
 227                                 return true;
 228                         }
 229                         if (attacker != NoPiece)
 230                                 break;
 231                         targetSquare += *it;
 232                 }
 233         }
 234
 235         return false;
 236 }
 237
 238 void Board::makeMove(const Move& move)
 239 {
 240         int source = move.sourceSquare();
 241         int target = move.targetSquare();
 242         int promotion = move.promotion();
 243         int piece = m_squares[source] * m_sign;
 244         int capture = m_squares[target];
 245         int epSq = m_enpassantSquare;
 246         int* rookSq = m_castlingRights.rookSquare[m_side];
 247
 248         assert(source != 0);
 249         assert(target != 0);
 250
 251         MoveData md = { move, capture, epSq, m_castlingRights,
 252                         m_key, m_reversibleMoveCount };
 253
 254         m_key ^= Zobrist::piece(m_side, piece, source);
 255
 256         if (epSq != 0) {
 257                 m_key ^= Zobrist::enpassant(epSq);
 258                 m_enpassantSquare = 0;
 259         }
 260
 261         bool isReversible = true;
 262         bool clearSource = true;
 263         if (piece == King) {
 264                 m_kingSquare[m_side] = target;
 265
 266                 // In case of a castling move, make the rook's move
 267                 if (move.castlingSide() != -1) {
 268                         int cside = move.castlingSide();
 269                         int rsource = rookSq[cside];
 270                         int rtarget = (cside == QueenSide) ? target + 1 : target -1;
 271
 272                         if ((rtarget == source) || (target == source))
 273                                 clearSource = false;
 274                         m_squares[rsource] = NoPiece;
 275                         m_squares[rtarget] = Rook * m_sign;
 276                         m_key ^= Zobrist::piece(m_side, Rook, rsource);
 277                         m_key ^= Zobrist::piece(m_side, Rook, rtarget);
 278                         isReversible = false;
 279                 }
 280                 // Any king move removes all castling rights
 281                 for (int i = QueenSide; i <= KingSide; i++) {
 282                         int& rs = rookSq[i];
 283                         if (rs != 0) {
 284                                 m_key ^= Zobrist::castling(m_side, rs);
 285                                 rs = 0;
 286                         }
 287                 }
 288         } else if (piece == Pawn) {
 289                 isReversible = false;
 290
 291                 // Make an en-passant capture
 292                 if (target == epSq) {
 293                         int epTarget = target + m_arwidth * m_sign;
 294                         m_squares[epTarget] = NoPiece;
 295                         m_key ^= Zobrist::piece(!m_side, Pawn, epTarget);
 296                 // Push a pawn two squares ahead, creating an en-passant
 297                 // opportunity for the opponent.
 298                 } else if ((source - target) * m_sign == m_arwidth * 2) {
 299                         m_enpassantSquare = source - m_arwidth * m_sign;
 300                         m_key ^= Zobrist::enpassant(m_enpassantSquare);
 301                 } else if (promotion != NoPiece)
 302                         piece = promotion;
 303         } else if (piece == Rook) {
 304                 // Remove castling rights from the rook's square
 305                 for (int i = QueenSide; i <= KingSide; i++) {
 306                         if (source == rookSq[i]) {
 307                                 m_key ^= Zobrist::castling(m_side, source);
 308                                 rookSq[i] = 0;
 309                                 isReversible = false;
 310                                 break;
 311                         }
 312                 }
 313         }
 314
 315         capture *= m_sign;
 316         // If the move captures opponent's castling rook, remove
 317         // his castling rights from that side.
 318         if (capture == -Rook) {
 319                 int* opCr = m_castlingRights.rookSquare[!m_side];
 320                 if (target == opCr[QueenSide]) {
 321                         m_key ^= Zobrist::castling(!m_side, target);
 322                         opCr[QueenSide] = 0;
 323                 } else if (target == opCr[KingSide]) {
 324                         m_key ^= Zobrist::castling(!m_side, target);
 325                         opCr[KingSide] = 0;
 326                 }
 327         }
 328
 329         if (capture < 0) {
 330                 isReversible = false;
 331                 m_key ^= Zobrist::piece(!m_side, -capture, target);
 332         }
 333         m_key ^= Zobrist::side();
 334         m_key ^= Zobrist::piece(m_side, piece, target);
 335         m_squares[target] = piece * m_sign;
 336         if (clearSource)
 337                 m_squares[source] = NoPiece;
 338
 339         if (isReversible)
 340                 m_reversibleMoveCount++;
 341         else
 342                 m_reversibleMoveCount = 0;
 343
 344         m_history.push_back(md);
 345         m_sign *= -1;
 346         m_side = !m_side;
 347 }
 348
 349 void Board::undoMove()
 350 {
 351         if (m_history.empty())
 352                 return;
 353
 354         const MoveData& md = m_history.back();
 355         const Move& move = md.move;
 356         int target = move.targetSquare();
 357         int source = move.sourceSquare();
 358
 359         m_history.pop_back();
 360         m_sign *= -1;
 361         m_side = !m_side;
 362
 363         m_enpassantSquare = md.enpassantSquare;
 364         m_castlingRights = md.castlingRights;
 365         m_key = md.key;
 366         m_reversibleMoveCount = md.reversibleMoveCount;
 367
 368         if (target == m_kingSquare[m_side]) {
 369                 m_kingSquare[m_side] = source;
 370
 371                 int cside = move.castlingSide();
 372                 if (cside != -1) {
 373                         // Move the rook back after castling
 374                         if (cside == QueenSide)
 375                                 m_squares[target + 1] = NoPiece;
 376                         else
 377                                 m_squares[target - 1] = NoPiece;
 378                         const int* cr = m_castlingRights.rookSquare[m_side];
 379                         m_squares[cr[cside]] = Rook * m_sign;
 380                         m_squares[source] = King * m_sign;
 381                         m_squares[target] = md.capture;
 382                         return;
 383                 }
 384         } else if (target == m_enpassantSquare) {
 385                 // Restore the pawn captured by the en-passant move
 386                 int epTarget = target + m_arwidth * m_sign;
 387                 m_squares[epTarget] = -Pawn * m_sign;
 388         }
 389
 390         if (move.promotion() != NoPiece)
 391                 m_squares[source] = Pawn * m_sign;
 392         else
 393                 m_squares[source] = m_squares[target];
 394
 395         m_squares[target] = md.capture;
 396 }
 397
 398 bool Board::isLegalPosition() const
 399 {
 400         if (inCheck(!m_side))
 401                 return false;
 402
 403         if (m_history.empty())
 404                 return true;
 405
 406         const MoveData& md = m_history.back();
 407         const Move& move = md.move;
 408
 409         // Make sure that no square between the king's initial and final
 410         // squares (including the initial and final squares) are under
 411         // attack (in check) by the opponent.
 412         if (move.castlingSide() != -1) {
 413                 int source = move.sourceSquare();
 414                 int target = move.targetSquare();
 415                 int offset = (move.castlingSide() == KingSide) ? 1 : -1;
 416
 417                 if (source == target) {
 418                         int i = target - offset;
 419                         while (true) {
 420                                 i -= offset;
 421                                 int piece = m_squares[i];
 422                                 if (piece == InvalidPiece)
 423                                         return true;
 424                                 switch (piece * m_sign) {
 425                                 case Rook: case Queen: case Chancellor:
 426                                         return false;
 427                                 }
 428                         }
 429                 }
 430
 431                 for (int i = source; i != target; i += offset) {
 432                         if (inCheck(!m_side, i))
 433                                 return false;
 434                 }
 435         }
 436
 437         return true;
 438 }
 439
 440 bool Board::isLegalMove(const Chess::Move& move)
 441 {
 442         std::vector<Move> moves = legalMoves();
 443         std::vector<Move>::const_iterator it;
 444         for (it = moves.begin(); it != moves.end(); it++) {
 445                 if (it->sourceSquare() == move.sourceSquare()
 446                 &&  it->targetSquare() == move.targetSquare()
 447                 &&  it->promotion() == move.promotion()
 448                 &&  it->castlingSide() == move.castlingSide())
 449                         return true;
 450         }
 451
 452         return false;
 453 }