1 /***************************************************************************
2 * (C) 2003 Sune Fischer *
3 * (C) 2005-2006 Marius Roets <roets.marius@gmail.com> *
4 * (C) 2005-2009 Michal Rudolf <mrudolf@kdewebdev.org> *
5 * *
6 * This program is free software; you can redistribute it and/or modify *
7 * it under the terms of the GNU General Public License as published by *
8 * the Free Software Foundation; either version 2 of the License, or *
9 * (at your option) any later version. *
10 ***************************************************************************/
11
12 #include "move.h"
13
14 #ifndef BITBOARD_H_INCLUDED
15 #define BITBOARD_H_INCLUDED
16
17 namespace chessx {
18
19 enum BoardStatus
20 {
21 Valid, NoWhiteKing, NoBlackKing, DoubleCheck,
22 OppositeCheck, TooManyBlackPawns, TooManyWhitePawns,
23 PawnsOn18, TooManyKings, TooManyWhite, TooManyBlack,
24 BadCastlingRights, InvalidEnPassant, MultiCheck
25 };
26
27 typedef uchar CastlingRights;
28 enum
29 {
30 NoRights = 0,
31 WhiteKingside = 1, BlackKingside = 2,
32 WhiteQueenside = 4, BlackQueenside = 8,
33 WhiteBothSides = 5, BlackBothSides = 10,
34 AllRights = 15
35 };
36
37 } // namespace chessx
38
39 /** @ingroup Core
40 * Keep track of the pieces on a chessboard, provide a Move() factory.
41 */
42 class BitBoard
43 {
44 public:
45 BitBoard();
46
47 // Play moves on board
48 //
49 /** Play given move, updating board state appropriately */
50 bool doMove(const Move&);
51 /** Return board to state prior to given move */
52 void undoMove(const Move&);
53
54 // Setup board
55 //
56 /** Remove all pieces and state from board */
57 void clear();
58 /** Set move number in game */
59 void setMoveNumber(unsigned int moveNumber);
60 /** Set initial chess game position on the board */
61 void setStandardPosition();
62 /** Set the given piece on the board at the given square */
63 void setAt(const chessx::Square s, const Piece p);
64 /** Remove any piece sitting on given square */
65 void removeAt(const chessx::Square s);
66 /** Set side to move as that of given color */
67 void setToMove(const Color& c);
68 /** Swap the side to move */
69 void swapToMove();
70 /** Parse given FEN, return true if loaded properly otherwise false */
71 bool fromFen(const QString& fen);
72 /** Set En Passant Square */
73 void setEnPassantSquare(const chessx::Square s);
74 /** Set En Passant in a file */
75 void setEnPassantFile(int f);
76 /** From a FICS representation of a board */
77 bool from64Char(const QString &qcharboard);
78 /** Remove En Passant privilege */
79 void clearEnPassantSquare();
80
81 // Move factories
82 //
83 Move createCastlingQ() const;
84 Move createCastlingK() const;
85
86 /** parse SAN or LAN representation of move, and return proper Move() object */
87 Move parseMove(const QString& algebraic) const;
88 /** Return a proper Move() object given only a from-to move specification */
89 Move prepareMove(const chessx::Square& from, const chessx::Square& to) const;
90
91 // Return a nullMove -- King to the same square
92 Move nullMove() const;
93
94 // Query
95 //
96 /** Is piece sitting on given square moveable ? */
97 bool isMovable(const chessx::Square s) const;
98 /** @return piece sitting at given square on the board */
99 Piece pieceAt(chessx::Square s) const;
100 /* Get the color of a Piece at square @s */
101 Color colorAt(chessx::Square s) const;
102 /** @return number of ply since a pawn move or capture */
103 unsigned int halfMoveClock() const;
104 /** Set number of ply since a pawn move or capture */
105 void setHalfMoveClock(unsigned int i);
106 /** @return the current move number in the game */
107 unsigned int moveNumber() const;
108 /** @return color of side next to move */
109 Color toMove() const;
110 /** @return true if color of side next to move is black */
111 bool blackToMove() const;
112 /** @return true if color of side next to move is black */
113 bool whiteToMove() const;
114 /** @return true if its possible for this position to follow target position */
115 bool canBeReachedFrom(const BitBoard& target) const;
116 /** @return true if position is same, but don't consider Move # in determination */
117 bool positionIsSame(const BitBoard& target) const;
118 /** @return true if neither side can win the game */
119 bool insufficientMaterial() const;
120 /** @return the square at which the king of @p color is located */
121 chessx::Square kingSquare(Color color) const;
122
123 // Query other formats
124 //
125 /** Return a FEN string based on current board position */
126 QString toFen(bool forceExtendedFEN=false) const;
127 /** Return a FEN string in human readable format based on current board position */
128 QString toHumanFen() const;
129
130 // Move formatting
131 /** Maps piece type to short string used in SAN */
132 class PieceNames
133 {
134 public:
135 PieceNames();
136 PieceNames(const QString& k, const QString& q, const QString& r, const QString& b, const QString& n);
137
138 /** @returns abbreviation for piece @p type */
139 QString get(PieceType type) const;
140 /** Set abbreviation for a piece @p type */
141 void set(PieceType type, const QString& name);
142 /** Set abbreviations for all piece types at once
143 * @note This method expects 1 letter per piece.
144 * If called with a string of incompatible length, FAN will be used.
145 */
146 void set(const QString& pieces);
147
148 /** unicode letters (♔♕♖♗♘) aka FAN */
149 static const PieceNames& figurine();
150 /** english convention (KQRBN) */
151 static const PieceNames& english();
152 /** global customizable instance */
153 static PieceNames& custom();
154 private:
155 static const int PieceTypeCount = 7;
156 QString m_names[PieceTypeCount];
157 };
158
159 /** Return a SAN string representation of given move */
160 QString moveToSan(const Move& move, bool translate = false, bool extend = false) const;
161 /** @return a SAN string representing a given move with move number. */
162 QString moveToFullSan(const Move& move, bool translate=false) const;
163
164 // Validation
165 //
166 /** Check current position and return "Valid" or problem */
167 chessx::BoardStatus validate() const;
168 /** Return true if given FEN can be parsed */
169 bool isValidFen(const QString& fen) const;
170
171 /** Set castling rights. */
172 void setCastlingRights(chessx::CastlingRights cr);
173 /** Return the internal castling rights data (used by hash function) */
174 chessx::CastlingRights castlingRights() const;
175 /** Return square where En passant capture may occur, or "NoEPSquare" */
176 chessx::Square enPassantSquare() const;
177
178 bool canTakeEnPassant() const;
179 /** Return true if the side to move is in checkmate */
180 bool isCheckmate() const;
181 /** Return true if the side to move is stalemated */
182 bool isStalemate() const;
183
184 /** Return 1 if Chess960 is selected, 0 otherwise */
185 bool chess960() const;
186 /** Set to 1 if Chess960 is selected, 0 otherwise */
187 void setChess960(bool chess960);
188 /** Setup board according to position number */
189 void fromChess960pos(int value);
190 /** Get the position number from the current position */
191 int chess960Pos() const;
192 quint64 castlingRooks() const;
193 static quint64 standardCastlingRooks();
194
195 void setCastlingRooks(char file000=0, char file00=0);
196 int CastlingRookIndex(chessx::Square rook) const;
197 bool HasRookOnFileForCastling(unsigned char file, bool castle000) const;
198
199 bool hasAmbiguousCastlingRooks(char file000 = 0, char file00 = 0) const;
200 /** Test to see if given color has the right to castle on kingside */
201 bool canCastleShort(const unsigned int color) const;
202 /** Test to see if given color has the right to castle on queenside */
203 bool canCastleLong(const unsigned int color) const;
204 /** Get the castling rook to the given index into m_castlingRook */
205 chessx::Square CastlingRook(int index) const;
206 /** Return the square of the king if in check, InvalidSquare otherwise */
207 chessx::Square kingInCheck() const;
208 /** Return true if the given square is attacked by the given color */
209 bool isAttackedBy(const unsigned int color, chessx::Square square) const;
210 /** Return number of attacks onto a given square by the given color */
211 int numAttackedBy(const unsigned int color, chessx::Square square) const;
212 /** Generate all possible moves in a given position */
213 Move::List generateMoves() const;
214 protected:
215 unsigned int countSetBits(quint64 n) const;
216 private:
217 /** Test if a king is on a certain row to test castling rights */
218 bool isKingOnRow(Piece p, chessx::Square start, chessx::Square stop) const;
219 /** Return true if side to move is in check */
220 bool isCheck() const;
221
222 /** Test to see if given color has any castling rights remaining */
223 bool canCastle(const unsigned int color) const;
224
225 /** Return true if making move would put oneself into check */
226 bool isIntoCheck(const Move& move) const;
227 /** Return true if the given squares are attacked by the given color */
228 bool isAttackedBy(const unsigned int color, chessx::Square start, chessx::Square stop) const;
229
230 /** Return all squares attacked by a knight on given square */
231 quint64 knightAttacksFrom(const chessx::Square s) const;
232 /** Return all squares attacked by a bishop on given square */
233 quint64 bishopAttacksFrom(const chessx::Square s) const;
234 /** Return all squares attacked by a rook on given square */
235 quint64 rookAttacksFrom(const chessx::Square s) const;
236 /** Return all squares attacked by a queen on given square */
237 quint64 queenAttacksFrom(const chessx::Square s) const;
238 /** Return all squares attacked by a king on given square */
239 quint64 kingAttacksFrom(const chessx::Square s) const;
240 /** Return all possible pawn moves from given square */
241 quint64 pawnMovesFrom(const chessx::Square s) const;
242
243 /** Remove impossible moves from given bitboard to aid disambiguation */
244 void removeIllegal(const Move& move, quint64& b) const;
245 /** Update move with castling details, return false if no castle is possible */
246 bool prepareCastle(Move& move) const;
247 /** Update move with castling details for Chess960, return false if no castle is possible */
248 bool prepareCastle960(Move &move) const;
249 /** Test that nothing is inbetween the castling pieces */
250 bool isFreeForCastling960(chessx::Square from, chessx::Square to, chessx::Square rook_from, chessx::Square rook_to) const;
251
252
253 /** Grant castling rights on the kingside to the given color */
254 void setCastleShort(unsigned int color);
255 /** Grant castling rights on the queenside to the given color */
256 void setCastleLong(unsigned int color);
257 /** Revoke all castling rights from the given color */
258 void destroyCastle(unsigned int color);
259 /** Revoke castling rights from the given color */
260 void destroyCastleInDirection(unsigned int color, chessx::Square s);
261 /** Update the epSquare value based on a new epFile value */
262 void epFile2Square();
263
264 /** Setup board according to FEN string */
265 bool fromGoodFen(const QString& fen, bool chess960=false);
266 /** Get the rook with index from castling rook storage */
267 bool HasRookForCastling(int index) const;
268 chessx::Square CastlingKingTarget(int rookIndex) const;
269 chessx::Square CastlingRookTarget(int rookIndex) const;
270 void fixCastlingRooks(bool, char file000=0, char file00=0);
271
272 // Actual Bit-board data
273 quint64 m_pawns, m_knights, m_bishops, m_rooks, m_castlingRooks, m_queens, m_kings;
274 quint64 m_occupied_co[2]; // Square mask of those occupied by each color
275 quint64 m_occupied; // Square is empty or holds a piece
276 quint64 m_occupied_l90; // rotated counter clockwise 90 deg
277 quint64 m_occupied_l45; // an odd transformation, to straighten out diagonals
278 quint64 m_occupied_r45; // the opposite odd transformation, just as messy
279
280 // Extra state data
281 unsigned char m_piece[64]; // type of piece on this square
282 unsigned char m_stm; // side to move
283 chessx::Square m_ksq[2]; // square of the m_kings
284 unsigned char m_epFile; // file of a possible ep capture
285 unsigned char m_epSquare; // This is requested by hash routine enough that we keep it pre calculated
286 unsigned char m_castle; // flags for castle legality (these can be merged)
287 unsigned short m_halfMoves; // Number of moves since last pawn move or capture
288 unsigned int m_moveNumber; // Move number in game (incremented after each black move)
289 unsigned char m_pawnCount[2]; // Number of pawns for each side
290 unsigned char m_pieceCount[2]; // Number of pieces INCLUDING pawns for each side
291 unsigned char m_chess960; // 0 = standard, 1 = Chess960
292 };
293
294 namespace chessx {
295
296 enum Char64Position
297 {
298 C64_ROW8,
299 C64_ROW7,
300 C64_ROW6,
301 C64_ROW5,
302 C64_ROW4,
303 C64_ROW3,
304 C64_ROW2,
305 C64_ROW1,
306 C64_COLOR_TO_MOVE,
307 C64_COL_DOUBLE_PAWN_PUSH,
308 C64_CASTLE_W_00,
309 C64_CASTLE_W_000,
310 C64_CASTLE_B_00,
311 C64_CASTLE_B_000,
312 C64_PLY_50_MOVE,
313 C64_NUM_GAME,
314 C64_NAME_WHITE,
315 C64_NAME_BLACK,
316 C64_GAME_RELATION,
317 C64_INITIAL_TIME_S,
318 C64_INCREMENT_S,
319 C64_MATERIAL_WHITE,
320 C64_MATERIAL_BLACK,
321 C64_REMAINDER_TIME_WHITE,
322 C64_REMAINDER_TIME_BLACK,
323 C64_NEXT_MOVE_NUMBER,
324 C64_LAST_MOVE,
325 C64_ELAPSED_TIME_LAST_MOVE,
326 C64_PP_LAST_MOVE,
327 C64_FLIP_BOARD,
328 C64_CLOCK_RUNNING,
329 C64_LAG
330 };
331
332 enum Char64Relation
333 {
334 C64_REL_ISOLATED = -3, // isolated position, such as for "ref 3" or the "sposition" command
335 C64_REL_OBSERVING_EXAMINE = -2, // I am observing game being examined
336 C64_REL_PLAY_OPPONENT_MOVE = -1, // I am playing, it is my opponent's move
337 C64_REL_OBSERVING_PLAY = 0, // I am observing a game being played
338 C64_REL_PLAY_MY_MOVE = 1, // I am playing and it is my move
339 C64_REL_EXAMINE = 2 // I am the examiner of this game
340 };
341
342 } // namespace chessx
343
344 extern quint64 bb_PawnAttacks[2][64];
345 extern quint64 bb_KnightAttacks[64];
346 extern quint64 bb_R45Attacks[64][64];
347 extern quint64 bb_L45Attacks[64][64];
348 extern quint64 bb_KingAttacks[64];
349 extern quint64 bb_RankAttacks[64][64];
350 extern quint64 bb_FileAttacks[64][64];
351
352 const unsigned int bb_ShiftR45[64] =
353 {
354 1, 58, 51, 44, 37, 30, 23, 16,
355 9, 1, 58, 51, 44, 37, 30, 23,
356 17, 9, 1, 58, 51, 44, 37, 30,
357 25, 17, 9, 1, 58, 51, 44, 37,
358 33, 25, 17, 9, 1, 58, 51, 44,
359 41, 33, 25, 17, 9, 1, 58, 51,
360 49, 41, 33, 25, 17, 9, 1, 58,
361 57, 49, 41, 33, 25, 17, 9, 1
362 };
363
364 const unsigned int bb_ShiftL45[64] =
365 {
366 9, 17, 25, 33, 41, 49, 57, 1,
367 17, 25, 33, 41, 49, 57, 1, 10,
368 25, 33, 41, 49, 57, 1, 10, 19,
369 33, 41, 49, 57, 1, 10, 19, 28,
370 41, 49, 57, 1, 10, 19, 28, 37,
371 49, 57, 1, 10, 19, 28, 37, 46,
372 57, 1, 10, 19, 28, 37, 46, 55,
373 1, 10, 19, 28, 37, 46, 55, 64
374 };
375
isAttackedBy(const unsigned int color,chessx::Square square)376 inline bool BitBoard::isAttackedBy(const unsigned int color, chessx::Square square) const
377 {
378 if(bb_PawnAttacks[color ^ 1][square] & m_pawns & m_occupied_co[color])
379 {
380 return 1;
381 }
382 if(knightAttacksFrom(square) & m_knights & m_occupied_co[color])
383 {
384 return 1;
385 }
386 if(bishopAttacksFrom(square) & (m_bishops | m_queens) & m_occupied_co[color])
387 {
388 return 1;
389 }
390 if(rookAttacksFrom(square) & (m_rooks | m_queens) & m_occupied_co[color])
391 {
392 return 1;
393 }
394 if(kingAttacksFrom(square) & m_kings & m_occupied_co[color])
395 {
396 return 1;
397 }
398 return 0;
399 };
400
isAttackedBy(const unsigned int color,chessx::Square start,chessx::Square stop)401 inline bool BitBoard::isAttackedBy(const unsigned int color, chessx::Square start, chessx::Square stop) const
402 {
403 chessx::Square square = start;
404
405 while(square!=stop)
406 {
407 bool underAttack = isAttackedBy(color, square);
408 if (underAttack) return true;
409 if (square!=stop) square += (start<=stop) ? 1:-1;
410 }
411
412 return isAttackedBy(color, stop);
413 };
414
setCastleShort(unsigned int color)415 inline void BitBoard::setCastleShort(unsigned int color)
416 {
417 m_castle |= 1 << color;
418 }
419
setCastleLong(unsigned int color)420 inline void BitBoard::setCastleLong(unsigned int color)
421 {
422 m_castle |= 4 << color;
423 }
424
destroyCastle(unsigned int color)425 inline void BitBoard::destroyCastle(unsigned int color)
426 {
427 m_castle &= ~(5 << color);
428 }
429
destroyCastleInDirection(unsigned int color,chessx::Square s)430 inline void BitBoard::destroyCastleInDirection(unsigned int color, chessx::Square s)
431 {
432 for (int i = 0; i<4; ++i)
433 {
434 if (CastlingRook(i) == s)
435 {
436 switch(i)
437 {
438 case 0: if (color == 0) m_castle &= (unsigned char) ~4; break;
439 case 1: if (color == 0) m_castle &= (unsigned char) ~1; break;
440 case 2: if (color == 1) m_castle &= (unsigned char) ~8; break;
441 case 3: if (color == 1) m_castle &= (unsigned char) ~2; break;
442 }
443 break;
444 }
445 }
446 }
447
knightAttacksFrom(const chessx::Square s)448 inline quint64 BitBoard::knightAttacksFrom(const chessx::Square s) const
449 {
450 return bb_KnightAttacks[s];
451 }
452
bishopAttacksFrom(const chessx::Square s)453 inline quint64 BitBoard::bishopAttacksFrom(const chessx::Square s) const
454 {
455 return bb_R45Attacks[s][(m_occupied_r45 >> bb_ShiftR45[s]) & 63] |
456 bb_L45Attacks[s][(m_occupied_l45 >> bb_ShiftL45[s]) & 63];
457 }
458
rookAttacksFrom(const chessx::Square s)459 inline quint64 BitBoard::rookAttacksFrom(const chessx::Square s) const
460 {
461 return bb_RankAttacks[s][(m_occupied >> ((s & ~7) + 1)) & 63] |
462 bb_FileAttacks[s][(m_occupied_l90 >> (((s & 7) << 3) + 1)) & 63];
463 }
464
queenAttacksFrom(const chessx::Square s)465 inline quint64 BitBoard::queenAttacksFrom(const chessx::Square s) const
466 {
467 return rookAttacksFrom(s) | bishopAttacksFrom(s);
468 }
469
kingAttacksFrom(const chessx::Square s)470 inline quint64 BitBoard::kingAttacksFrom(const chessx::Square s) const
471 {
472 return bb_KingAttacks[s];
473 }
474
epFile2Square()475 inline void BitBoard::epFile2Square()
476 {
477 if(m_epFile)
478 {
479 m_epSquare = m_epFile + (m_stm == White ? chessx::a6 : chessx::a3) - 1;
480 }
481 else
482 {
483 m_epSquare = chessx::NoEPSquare;
484 }
485 }
486
canCastle(const unsigned int color)487 inline bool BitBoard::canCastle(const unsigned int color) const
488 {
489 return m_castle & (5 << color);
490 }
491
canCastleShort(const unsigned int color)492 inline bool BitBoard::canCastleShort(const unsigned int color) const
493 {
494 return m_castle & (1 << color);
495 }
496
canCastleLong(const unsigned int color)497 inline bool BitBoard::canCastleLong(const unsigned int color) const
498 {
499 return m_castle & (4 << color);
500 }
501
isCheck()502 inline bool BitBoard::isCheck() const
503 {
504 return isAttackedBy(m_stm ^ 1, m_ksq[m_stm]);
505 }
506
kingInCheck()507 inline chessx::Square BitBoard::kingInCheck() const
508 {
509 return isCheck() ? m_ksq[m_stm] : (chessx::Square) chessx::InvalidSquare;
510 }
511
halfMoveClock()512 inline unsigned int BitBoard::halfMoveClock() const
513 {
514 return m_halfMoves;
515 }
516
setHalfMoveClock(unsigned int i)517 inline void BitBoard::setHalfMoveClock(unsigned int i)
518 {
519 m_halfMoves = i;
520 }
521
moveNumber()522 inline unsigned int BitBoard::moveNumber() const
523 {
524 return m_moveNumber;
525 }
526
toMove()527 inline Color BitBoard::toMove() const
528 {
529 return Color(m_stm);
530 }
531
blackToMove()532 inline bool BitBoard::blackToMove() const
533 {
534 return Color(m_stm) == Black;
535 }
536
whiteToMove()537 inline bool BitBoard::whiteToMove() const
538 {
539 return Color(m_stm) == White;
540 }
541
enPassantSquare()542 inline chessx::Square BitBoard::enPassantSquare() const
543 {
544 return chessx::Square(m_epSquare);
545 }
546
castlingRights()547 inline chessx::CastlingRights BitBoard::castlingRights() const
548 {
549 return m_castle;
550 }
551
get(PieceType type)552 inline QString BitBoard::PieceNames::get(PieceType type) const
553 {
554 Q_ASSERT(0 <= type && type < PieceTypeCount);
555 return m_names[type];
556 }
557
set(PieceType type,const QString & name)558 inline void BitBoard::PieceNames::set(PieceType type, const QString &name)
559 {
560 Q_ASSERT(0 <= type && type < PieceTypeCount);
561 m_names[type] = name;
562 }
563
564 #endif // BITBOARD_H_INCLUDED
565