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 "bitboard.h"
13 #include "square.h"
14 #include "bitfind.h"
15
16 #ifdef _MSC_VER
17 #include <intrin.h>
18 #endif
19
20 #include <QtCore>
21
22 #if defined(_MSC_VER) && defined(_DEBUG)
23 #define DEBUG_NEW new( _NORMAL_BLOCK, __FILE__, __LINE__ )
24 #define new DEBUG_NEW
25 #endif // _MSC_VER
26
27 // Global data that is initialized early on and only read afterward
28 quint64 bb_PawnAttacks[2][64];
29 quint64 bb_PawnF1[2][64];
30 quint64 bb_PawnF2[2][64];
31 quint64 bb_PawnALL[2][64];
32 quint64 bb_PromotionRank[2];
33 quint64 bb_KnightAttacks[64];
34 quint64 bb_R45Attacks[64][64];
35 quint64 bb_L45Attacks[64][64];
36 quint64 bb_KingAttacks[64];
37 quint64 bb_RankAttacks[64][64];
38 quint64 bb_FileAttacks[64][64];
39 quint64 bb_fileMask[8];
40 quint64 bb_rankMask[8];
41 quint64 bb_Mask[64];
42 quint64 bb_MaskL90[64];
43 quint64 bb_MaskL45[64];
44 quint64 bb_MaskR45[64];
45
46 using namespace chessx;
47
48 BitBoard getStandardPosition();
49 // Calling the function getStandardPosition for initialization avoids
50 // initialization side effects when using BitBoards in other translation
51 // units.
52 BitBoard standardPosition = getStandardPosition();
53 BitBoard clearedPosition;
54
55
56 bool bitBoardInitRun;
57 void bitBoardInit();
58
59
60 const quint64 A1 = 1, B1 = A1 << 1, C1 = B1 << 1, D1 = C1 << 1, E1 = D1 << 1, F1 = E1 << 1, G1 = F1 << 1, H1 = G1 << 1;
61 const quint64 A2 = H1 << 1, B2 = A2 << 1, C2 = B2 << 1, D2 = C2 << 1, E2 = D2 << 1, F2 = E2 << 1, G2 = F2 << 1, H2 = G2 << 1;
62 const quint64 A3 = H2 << 1, B3 = A3 << 1, C3 = B3 << 1, D3 = C3 << 1, E3 = D3 << 1, F3 = E3 << 1, G3 = F3 << 1, H3 = G3 << 1;
63 const quint64 A4 = H3 << 1, B4 = A4 << 1, C4 = B4 << 1, D4 = C4 << 1, E4 = D4 << 1, F4 = E4 << 1, G4 = F4 << 1, H4 = G4 << 1;
64 const quint64 A5 = H4 << 1, B5 = A5 << 1, C5 = B5 << 1, D5 = C5 << 1, E5 = D5 << 1, F5 = E5 << 1, G5 = F5 << 1, H5 = G5 << 1;
65 const quint64 A6 = H5 << 1, B6 = A6 << 1, C6 = B6 << 1, D6 = C6 << 1, E6 = D6 << 1, F6 = E6 << 1, G6 = F6 << 1, H6 = G6 << 1;
66 const quint64 A7 = H6 << 1, B7 = A7 << 1, C7 = B7 << 1, D7 = C7 << 1, E7 = D7 << 1, F7 = E7 << 1, G7 = F7 << 1, H7 = G7 << 1;
67 const quint64 A8 = H7 << 1, B8 = A8 << 1, C8 = B8 << 1, D8 = C8 << 1, E8 = D8 << 1, F8 = E8 << 1, G8 = F8 << 1, H8 = G8 << 1;
68
69 const unsigned int RotateL90[64] =
70 {
71 h1, h2, h3, h4, h5, h6, h7, h8,
72 g1, g2, g3, g4, g5, g6, g7, g8,
73 f1, f2, f3, f4, f5, f6, f7, f8,
74 e1, e2, e3, e4, e5, e6, e7, e8,
75 d1, d2, d3, d4, d5, d6, d7, d8,
76 c1, c2, c3, c4, c5, c6, c7, c8,
77 b1, b2, b3, b4, b5, b6, b7, b8,
78 a1, a2, a3, a4, a5, a6, a7, a8,
79 };
80
81 const unsigned int RotateR45[64] =
82 {
83 a1, b8, c7, d6, e5, f4, g3, h2,
84 a2, b1, c8, d7, e6, f5, g4, h3,
85 a3, b2, c1, d8, e7, f6, g5, h4,
86 a4, b3, c2, d1, e8, f7, g6, h5,
87 a5, b4, c3, d2, e1, f8, g7, h6,
88 a6, b5, c4, d3, e2, f1, g8, h7,
89 a7, b6, c5, d4, e3, f2, g1, h8,
90 a8, b7, c6, d5, e4, f3, g2, h1
91 };
92
93 const unsigned int RotateL45[64] =
94 {
95 a2, b3, c4, d5, e6, f7, g8, h1,
96 a3, b4, c5, d6, e7, f8, g1, h2,
97 a4, b5, c6, d7, e8, f1, g2, h3,
98 a5, b6, c7, d8, e1, f2, g3, h4,
99 a6, b7, c8, d1, e2, f3, g4, h5,
100 a7, b8, c1, d2, e3, f4, g5, h6,
101 a8, b1, c2, d3, e4, f5, g6, h7,
102 a1, b2, c3, d4, e5, f6, g7, h8
103 };
104
105 const unsigned char Castle[64] =
106 {
107 0xFB, 255, 255, 255, 0xFA, 255, 255, 0xFE,
108 255, 255, 255, 255, 255, 255, 255, 255,
109 255, 255, 255, 255, 255, 255, 255, 255,
110 255, 255, 255, 255, 255, 255, 255, 255,
111 255, 255, 255, 255, 255, 255, 255, 255,
112 255, 255, 255, 255, 255, 255, 255, 255,
113 255, 255, 255, 255, 255, 255, 255, 255,
114 0xF7, 255, 255, 255, 0xF5, 255, 255, 0xFD
115 };
116
117 const quint64 fileA = A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8;
118 const quint64 fileB = B1 | B2 | B3 | B4 | B5 | B6 | B7 | B8;
119 const quint64 fileG = G1 | G2 | G3 | G4 | G5 | G6 | G7 | G8;
120 const quint64 fileH = H1 | H2 | H3 | H4 | H5 | H6 | H7 | H8;
121 const quint64 rank4 = A4 | B4 | C4 | D4 | E4 | F4 | G4 | H4;
122 const quint64 rank5 = A5 | B5 | C5 | D5 | E5 | F5 | G5 | H5;
123 const quint64 fileNotA = ~ fileA;
124 const quint64 fileNotH = ~ fileH;
125 const quint64 fileNotAB = ~(fileA | fileB);
126 const quint64 fileNotGH = ~(fileG | fileH);
127
128 #define SetBitL90(s) (bb_MaskL90[s])
129 #define SetBitL45(s) (bb_MaskL45[s])
130 #define SetBitR45(s) (bb_MaskR45[s])
131 #define ShiftDown(b) ((b)>>8)
132 #define Shift2Down(b) ((b)>>16)
133 #define ShiftUp(b) ((b)<<8)
134 #define Shift2Up(b) ((b)<<16)
135 #define ShiftRight(b) (((b)<<1)&fileNotA)
136 #define Shift2Right(b) (((b)<<2)&fileNotAB)
137 #define ShiftLeft(b) (((b)>>1)&fileNotH)
138 #define Shift2Left(b) (((b)>>2)&fileNotGH)
139 #define ShiftUpLeft(b) (((b)<<7)&fileNotH)
140 #define ShiftUpRight(b) (((b)<<9)&fileNotA)
141 #define ShiftDownLeft(b) (((b)>>9)&fileNotH)
142 #define ShiftDownRight(b) (((b)>>7)&fileNotA)
143 #define SetBit(s) (bb_Mask[s])
144
append(Move::List & list)145 static inline Move& append(Move::List& list)
146 {
147 list.push_back(Move());
148 return list.back();
149 }
150
PieceNames(const QString & k,const QString & q,const QString & r,const QString & b,const QString & n)151 BitBoard::PieceNames::PieceNames(const QString& k, const QString& q, const QString& r, const QString& b, const QString& n)
152 :m_names {"", k, q, r, b, n, ""}
153 {}
154
PieceNames()155 BitBoard::PieceNames::PieceNames()
156 :PieceNames("K", "Q", "R", "B", "N")
157 {}
158
figurine()159 const BitBoard::PieceNames& BitBoard::PieceNames::figurine()
160 {
161 static PieceNames names("♔", "♕", "♖", "♗", "♘");
162 return names;
163 }
164
english()165 const BitBoard::PieceNames& BitBoard::PieceNames::english()
166 {
167 static PieceNames names("K", "Q", "R", "B", "N");
168 return names;
169 }
170
custom()171 BitBoard::PieceNames& BitBoard::PieceNames::custom()
172 {
173 static PieceNames names(figurine());
174 return names;
175 }
176
set(const QString & pieces)177 void BitBoard::PieceNames::set(const QString &pieces)
178 {
179 const int expectedLength = PieceTypeCount - 1; // without pawn
180 if (pieces.length() == expectedLength)
181 {
182 set(King, pieces.at(King));
183 set(Queen, pieces.at(Queen));
184 set(Rook, pieces.at(Rook));
185 set(Bishop, pieces.at(Bishop));
186 set(Knight, pieces.at(Knight));
187 }
188 else
189 {
190 *this = figurine();
191 }
192 }
193
194 /** Initialize a new bitboard, and ensure global data has been initialized */
BitBoard()195 BitBoard::BitBoard()
196 {
197 memset(this, 0, sizeof(BitBoard));
198 if(!bitBoardInitRun)
199 {
200 bitBoardInit();
201 }
202 m_epSquare = NoEPSquare;
203 }
204
isCheckmate() const205 bool BitBoard::isCheckmate() const
206 {
207 Move::List moves(generateMoves());
208 for(int i = 0; i < moves.size(); ++i)
209 {
210 if(!isIntoCheck(moves[i]))
211 {
212 return false;
213 }
214 }
215 return isCheck();
216 }
217
isStalemate() const218 bool BitBoard::isStalemate() const
219 {
220 Move::List moves(generateMoves());
221 for(int i = 0; i < moves.size(); ++i)
222 {
223 if(!isIntoCheck(moves[i]))
224 {
225 return false;
226 }
227 }
228 return !isCheck();
229 }
230
removeIllegal(const Move & move,quint64 & b) const231 void BitBoard::removeIllegal(const Move& move, quint64& b) const
232 {
233 quint64 mask = 1;
234 Move m = move;
235 for(int sq = 0; sq < 64; ++sq)
236 {
237 if(b & mask)
238 {
239 m.setFrom(Square(sq));
240 if(isIntoCheck(m))
241 {
242 b &= ~mask;
243 }
244 }
245 mask <<= 1;
246 }
247 }
248
moveToSan(const Move & move,bool translate,bool extend) const249 QString BitBoard::moveToSan(const Move& move, bool translate, bool extend) const
250 {
251 const PieceNames& abbrev = translate? PieceNames::custom(): PieceNames::english();
252 QString san;
253 Square from = move.from();
254 Square to = move.to();
255 bool isPawn = m_piece[from] == Pawn;
256 if (extend)
257 {
258 san = QString("%1.").arg(m_moveNumber);
259 if (blackToMove())
260 {
261 san += "..";
262 }
263 }
264 if(move.isNullMove())
265 {
266 san += "--";
267 return san;
268 }
269
270 if(move.isCastling())
271 {
272 if (File(to)==File(g1))
273 {
274 san += "O-O";
275 }
276 else
277 {
278 san += "O-O-O";
279 }
280 }
281 else
282 {
283 if(!isPawn)
284 {
285 san += abbrev.get(PieceType(m_piece[from]));
286
287 // We may need disambiguation
288 quint64 others = 0;
289 switch(m_piece[from])
290 {
291 case Knight:
292 others = m_knights & knightAttacksFrom(to);
293 break;
294 case Bishop:
295 others = m_bishops & bishopAttacksFrom(to);
296 break;
297 case Rook:
298 others = m_rooks & rookAttacksFrom(to);
299 break;
300 case Queen:
301 others = m_queens & queenAttacksFrom(to);
302 break;
303 case King:
304 others = m_kings & kingAttacksFrom(to);
305 break;
306 default:
307 break; // Something really wrong
308 }
309
310 others ^= SetBit(from);
311 others &= m_occupied_co[m_stm];
312 // Do not disambiguate with moves that put oneself in check.
313 // This is an expensive operation of dubious value, but people seem to want it
314 if(others)
315 {
316 removeIllegal(move, others);
317 }
318 if(others)
319 {
320 bool row = false, column = false;
321 if(others & bb_rankMask[Rank(from)])
322 {
323 column = true;
324 }
325 if(others & bb_fileMask[File(from)])
326 {
327 row = true;
328 }
329 else
330 {
331 column = true;
332 }
333 if(column)
334 {
335 san += 'a' + File(from);
336 }
337 if(row)
338 {
339 san += '1' + Rank(from);
340 }
341 }
342 }
343
344 //capture x
345 if(m_piece[to] || (move.isEnPassant()))
346 {
347 if(isPawn)
348 {
349 san += 'a' + File(from);
350 }
351 san += 'x';
352 }
353
354 //destination square
355 san += 'a' + File(to);
356 san += '1' + Rank(to);
357 }
358
359 if(move.isPromotion())
360 {
361 san += '=';
362 san += abbrev.get(PieceType(move.promoted()));
363 }
364
365 BitBoard check(*this);
366 check.doMove(move);
367 if(check.isCheck())
368 {
369 if(check.isCheckmate())
370 {
371 san += '#';
372 }
373 else
374 {
375 san += '+';
376 }
377 }
378
379 return san;
380 }
381
clear()382 void BitBoard::clear()
383 {
384 *this = clearedPosition;
385 }
386
setStandardPosition()387 void BitBoard::setStandardPosition()
388 {
389 *this = standardPosition;
390 }
391
clearEnPassantSquare()392 void BitBoard::clearEnPassantSquare()
393 {
394 m_epFile = 0;
395 m_epSquare = NoEPSquare;
396 }
397
setEnPassantSquare(const Square s)398 void BitBoard::setEnPassantSquare(const Square s)
399 {
400 m_epSquare = s;
401 m_epFile = File(s);
402 }
403
setEnPassantFile(int f)404 void BitBoard::setEnPassantFile(int f)
405 {
406 if ((f>=0) && (f<=7))
407 {
408 m_epFile = f+1;
409 epFile2Square();
410 }
411 else
412 {
413 clearEnPassantSquare();
414 }
415 }
416
isMovable(const Square from) const417 bool BitBoard::isMovable(const Square from) const
418 {
419 Q_ASSERT(from < 64);
420
421 if(m_occupied_co[m_stm] & SetBit(from))
422 {
423 quint64 squares = 0;
424 switch(m_piece[from])
425 {
426 case Pawn:
427 squares = pawnMovesFrom(from);
428 break;
429 case Knight:
430 squares = knightAttacksFrom(from);
431 break;
432 case Bishop:
433 squares = bishopAttacksFrom(from);
434 break;
435 case Rook:
436 squares = rookAttacksFrom(from);
437 break;
438 case Queen:
439 squares = queenAttacksFrom(from);
440 break;
441 case King:
442 squares = kingAttacksFrom(m_ksq[m_stm]);
443 if (m_stm == White)
444 {
445 squares |= SetBit(g1);
446 squares |= SetBit(c1);
447 }
448 else if (m_stm == Black)
449 {
450 squares |= SetBit(g8);
451 squares |= SetBit(c8);
452 }
453 break;
454 default:
455 break;
456 }
457 squares &= ~m_occupied_co[m_stm];
458 while(squares)
459 {
460 Square to = getFirstBitAndClear64<Square>(squares);
461 if(prepareMove(from, to).isLegal())
462 {
463 return true;
464 }
465 }
466 }
467 return false;
468 }
469
setAt(const Square s,const Piece p)470 void BitBoard::setAt(const Square s, const Piece p)
471 {
472 Q_ASSERT(s < 64);
473 Q_ASSERT(isValidPiece(p) || p == Empty);
474
475 quint64 bit = SetBit(s);
476 if(m_occupied & bit)
477 {
478 removeAt(s);
479 }
480
481 PieceType pt = pieceType(p);
482 if(pt == None)
483 {
484 return;
485 }
486
487 Color _color = pieceColor(p);
488 ++m_pieceCount[_color];
489 switch(pt)
490 {
491 case Pawn:
492 m_pawns |= bit;
493 ++m_pawnCount[_color];
494 break;
495 case Knight:
496 m_knights |= bit;
497 break;
498 case Bishop:
499 m_bishops |= bit;
500 break;
501 case Rook:
502 m_rooks |= bit;
503 break;
504 case Queen:
505 m_queens |= bit;
506 break;
507 case King:
508 if(m_kings & m_occupied_co[_color])
509 {
510 removeAt(m_ksq[_color]);
511 }
512 m_kings |= bit;
513 m_ksq[_color] = s;
514 break;
515 default:
516 break; // ERROR
517 }
518
519 m_piece[s] = pt;
520 m_occupied ^= bit;
521 m_occupied_co[_color] ^= bit;
522 m_occupied_l90 ^= SetBitL90(s);
523 m_occupied_l45 ^= SetBitL45(s);
524 m_occupied_r45 ^= SetBitR45(s);
525 }
526
removeAt(const Square s)527 void BitBoard::removeAt(const Square s)
528 {
529 Q_ASSERT(s < 64);
530
531 quint64 bit = SetBit(s);
532 if(!(m_occupied & bit))
533 {
534 return;
535 }
536
537 Color _color = (m_occupied_co[White] & bit) ? White : Black;
538 --m_pieceCount[_color];
539 switch(m_piece[s])
540 {
541 case Pawn:
542 m_pawns ^= bit;
543 --m_pawnCount[_color];
544 break;
545 case Knight:
546 m_knights ^= bit;
547 break;
548 case Bishop:
549 m_bishops ^= bit;
550 break;
551 case Rook:
552 m_rooks ^= bit;
553 if (!chess960())
554 {
555 m_castle &= Castle[s];
556 }
557 else
558 {
559 if (m_castlingRooks & bit)
560 {
561 destroyCastleInDirection(_color, s);
562 }
563 }
564 break;
565 case Queen:
566 m_queens ^= bit;
567 break;
568 case King:
569 m_kings ^= bit;
570 m_ksq[_color] = InvalidSquare;
571 destroyCastle(_color);
572 break;
573 default:
574 break; // ERROR
575 }
576
577 m_piece[s] = Empty;
578 m_occupied ^= bit;
579 m_occupied_co[_color] ^= bit;
580 m_occupied_l90 ^= SetBitL90(s);
581 m_occupied_l45 ^= SetBitL45(s);
582 m_occupied_r45 ^= SetBitR45(s);
583 }
584
isValidFen(const QString & fen) const585 bool BitBoard::isValidFen(const QString& fen) const
586 {
587 return BitBoard().fromGoodFen(fen, chess960());
588 }
589
fromFen(const QString & fen)590 bool BitBoard::fromFen(const QString& fen)
591 {
592 if(isValidFen(fen))
593 {
594 return fromGoodFen(fen, chess960());
595 }
596 return false;
597 }
598
validate() const599 BoardStatus BitBoard::validate() const
600 {
601 unsigned int wk = 0, bk = 0, wp = 0, bp = 0, bo = 0, wo = 0;
602 for(unsigned int i = 0; i < 64; ++i)
603 {
604 Piece p = pieceAt(Square(i));
605 if(p == WhiteKing)
606 {
607 ++wk;
608 }
609 else if(p == BlackKing)
610 {
611 ++bk;
612 }
613 else if(p == WhitePawn)
614 {
615 if(i <= h1 || i >= a8) // Pawns on 1st or 8th
616 {
617 return PawnsOn18;
618 }
619 else
620 {
621 ++wp;
622 }
623 }
624 else if(p == BlackPawn)
625 {
626 if(i <= h1 || i >= a8) // Pawns on 1st or 8th
627 {
628 return PawnsOn18;
629 }
630 else
631 {
632 ++bp;
633 }
634 }
635 else if(isWhite(p))
636 {
637 ++wo;
638 }
639 else if(isBlack(p))
640 {
641 ++bo;
642 }
643 }
644
645 Q_ASSERT(wp == m_pawnCount[White]);
646 Q_ASSERT(bp == m_pawnCount[Black]);
647 Q_ASSERT(wp + wk + wo == m_pieceCount[White]);
648 Q_ASSERT(bp + bk + bo == m_pieceCount[Black]);
649
650 // Exactly one king per side
651 if(wk == 0)
652 {
653 return NoWhiteKing;
654 }
655 if(bk == 0)
656 {
657 return NoBlackKing;
658 }
659 if(wk != 1 || bk != 1)
660 {
661 return TooManyKings;
662 }
663
664 // No more than 8 pawns per side
665 if(wp > 8)
666 {
667 return TooManyWhitePawns;
668 }
669 if(bp > 8)
670 {
671 return TooManyBlackPawns;
672 }
673
674 // Maximum 16 pieces per side
675 if((wk + wp + wo) > 16)
676 {
677 return TooManyWhite;
678 }
679 if((bk + bp + bo) > 16)
680 {
681 return TooManyBlack;
682 }
683
684 // Bad checks
685 bool check = isAttackedBy(m_stm ^ 1, m_ksq[m_stm]);
686 bool check2 = isAttackedBy(m_stm, m_ksq[m_stm ^ 1]);
687 if(check && check2)
688 {
689 return DoubleCheck;
690 }
691 if(check2)
692 {
693 return OppositeCheck;
694 }
695
696 // Can't castle with missing rook
697 if (!m_chess960)
698 {
699 if(canCastleLong(White) && pieceAt(a1) != WhiteRook)
700 {
701 return BadCastlingRights;
702 }
703 if(canCastleShort(White) && pieceAt(h1) != WhiteRook)
704 {
705 return BadCastlingRights;
706 }
707 if(canCastleLong(Black) && pieceAt(a8) != BlackRook)
708 {
709 return BadCastlingRights;
710 }
711 if(canCastleShort(Black) && pieceAt(h8) != BlackRook)
712 {
713 return BadCastlingRights;
714 }
715
716 // Can't castle if king has moved
717 if(canCastle(White) && pieceAt(e1) != WhiteKing)
718 {
719 return BadCastlingRights;
720 }
721 if(canCastle(Black) && pieceAt(e8) != BlackKing)
722 {
723 return BadCastlingRights;
724 }
725 }
726 else
727 {
728 // Can't castle if king is not on row 1 / 8
729 if(canCastle(White) && !(SetBit(m_ksq[White]) & 0x00000000000000FFuLL))
730 {
731 return BadCastlingRights;
732 }
733 if(canCastle(Black) && !(SetBit(m_ksq[Black]) & 0xFF00000000000000uLL))
734 {
735 return BadCastlingRights;
736 }
737
738 if(canCastleLong(White) && !HasRookForCastling(0))
739 {
740 return BadCastlingRights;
741 }
742 if(canCastleShort(White) && !HasRookForCastling(1))
743 {
744 return BadCastlingRights;
745 }
746 if(canCastleLong(Black) && !HasRookForCastling(2))
747 {
748 return BadCastlingRights;
749 }
750 if(canCastleShort(Black) && !HasRookForCastling(3))
751 {
752 return BadCastlingRights;
753 }
754
755 if (canCastle(White) && canCastle(Black))
756 {
757 if (File(m_ksq[White]) != File(m_ksq[Black]))
758 {
759 return BadCastlingRights;
760 }
761 }
762
763 if (canCastleShort(White) && canCastleShort(Black))
764 {
765 if (File(CastlingRook(1)) != File(CastlingRook(3)))
766 {
767 return BadCastlingRights;
768 }
769 }
770 if (canCastleLong(White) && canCastleLong(Black))
771 {
772 if (File(CastlingRook(0)) != File(CastlingRook(2)))
773 {
774 return BadCastlingRights;
775 }
776 }
777 }
778
779 // Detect unreasonable ep square
780 if(m_epSquare != NoEPSquare)
781 {
782 if(m_stm == White && (m_epSquare < a6 || m_epSquare > h6))
783 {
784 return InvalidEnPassant;
785 }
786 if(m_stm == Black && (m_epSquare < a3 || m_epSquare > h3))
787 {
788 return InvalidEnPassant;
789 }
790 }
791
792 // Don't allow triple(or more) checks.
793 // FIXME -- need code here to return MultiCheck
794
795 return Valid;
796 }
797
isKingOnRow(Piece p,Square start,Square stop) const798 bool BitBoard::isKingOnRow(Piece p, Square start, Square stop) const
799 {
800 for (Square square=start; square<=stop; ++square)
801 {
802 if (pieceAt(square) == p) return true;
803 }
804 return false;
805 }
806
canTakeEnPassant() const807 bool BitBoard::canTakeEnPassant() const
808 {
809 if(m_stm == Black)
810 {
811 quint64 movers = m_pawns & m_occupied_co[Black];
812 if(m_epSquare != NoEPSquare)
813 {
814 quint64 moves = bb_PawnAttacks[White][m_epSquare] & movers;
815 return (moves != 0);
816 }
817 }
818 else
819 {
820 quint64 movers = m_pawns & m_occupied_co[White];
821 if(m_epSquare != NoEPSquare)
822 {
823 quint64 moves = bb_PawnAttacks[Black][m_epSquare] & movers;
824 return (moves != 0);
825 }
826 }
827 return 0;
828 }
829
830 // Why QString throws asserts for access past end of string and
831 // refuses to return a real c++ char type is beyond me...
832 class SaneString : public QString
833 {
834 public:
SaneString(const QString & q)835 SaneString(const QString& q) : QString(q) {};
operator [](const int index) const836 char operator[](const int index) const
837 {
838 if(index < this->length())
839 {
840 return QString::operator[](index).toLatin1();
841 }
842 return 0;
843 }
844 };
845
fromGoodFen(const QString & qfen,bool chess960)846 bool BitBoard::fromGoodFen(const QString& qfen, bool chess960)
847 {
848 SaneString fen(qfen);
849 int i;
850 unsigned int s;
851 char c = fen[0];
852
853 memset(this, 0, sizeof(BitBoard));
854 setChess960(chess960);
855 m_moveNumber = 1;
856 m_epSquare = NoEPSquare;
857
858 // Piece position
859 i = 0;
860 s = 56;
861 while(c && c != ' ' && s <= 64)
862 {
863 switch(c)
864 {
865 case '/':
866 s -= 16;
867 break;
868 case '1':
869 s += 1;
870 break;
871 case '2':
872 s += 2;
873 break;
874 case '3':
875 s += 3;
876 break;
877 case '4':
878 s += 4;
879 break;
880 case '5':
881 s += 5;
882 break;
883 case '6':
884 s += 6;
885 break;
886 case '7':
887 s += 7;
888 break;
889 case '8':
890 s += 8;
891 break;
892 case 'p':
893 m_piece[s] = Pawn;
894 m_pawns |= SetBit(s);
895 m_occupied_co[Black] |= SetBit(s);
896 ++m_pawnCount[Black];
897 ++m_pieceCount[Black];
898 s++;
899 break;
900 case 'n':
901 m_piece[s] = Knight;
902 m_knights |= SetBit(s);
903 m_occupied_co[Black] |= SetBit(s);
904 ++m_pieceCount[Black];
905 s++;
906 break;
907 case 'b':
908 m_piece[s] = Bishop;
909 m_bishops |= SetBit(s);
910 m_occupied_co[Black] |= SetBit(s);
911 ++m_pieceCount[Black];
912 s++;
913 break;
914 case 'r':
915 m_piece[s] = Rook;
916 m_rooks |= SetBit(s);
917 m_occupied_co[Black] |= SetBit(s);
918 ++m_pieceCount[Black];
919 s++;
920 break;
921 case 'q':
922 m_piece[s] = Queen;
923 m_queens |= SetBit(s);
924 m_occupied_co[Black] |= SetBit(s);
925 ++m_pieceCount[Black];
926 s++;
927 break;
928 case 'k':
929 m_piece[s] = King;
930 m_kings |= SetBit(s);
931 m_occupied_co[Black] |= SetBit(s);
932 m_ksq[Black] = Square(s);
933 ++m_pieceCount[Black];
934 s++;
935 break;
936 case 'P':
937 m_piece[s] = Pawn;
938 m_pawns |= SetBit(s);
939 m_occupied_co[White] |= SetBit(s);
940 ++m_pawnCount[White];
941 ++m_pieceCount[White];
942 s++;
943 break;
944 case 'N':
945 m_piece[s] = Knight;
946 m_knights |= SetBit(s);
947 m_occupied_co[White] |= SetBit(s);
948 ++m_pieceCount[White];
949 s++;
950 break;
951 case 'B':
952 m_piece[s] = Bishop;
953 m_bishops |= SetBit(s);
954 m_occupied_co[White] |= SetBit(s);
955 ++m_pieceCount[White];
956 s++;
957 break;
958 case 'R':
959 m_piece[s] = Rook;
960 m_rooks |= SetBit(s);
961 m_occupied_co[White] |= SetBit(s);
962 ++m_pieceCount[White];
963 s++;
964 break;
965 case 'Q':
966 m_piece[s] = Queen;
967 m_queens |= SetBit(s);
968 m_occupied_co[White] |= SetBit(s);
969 ++m_pieceCount[White];
970 s++;
971 break;
972 case 'K':
973 m_piece[s] = King;
974 m_kings |= SetBit(s);
975 m_occupied_co[White] |= SetBit(s);
976 m_ksq[White] = Square(s);
977 ++m_pieceCount[White];
978 s++;
979 break;
980 default:
981 return false;
982 }
983 c = fen[++i];
984 }
985 if(s != 8)
986 {
987 return false;
988 }
989
990 // Set remainder of bitboard data appropriately
991 m_occupied = m_occupied_co[White] + m_occupied_co[Black];
992 for(int i = 0; i < 64; ++i)
993 {
994 if(SetBit(i)&m_occupied)
995 {
996 m_occupied_l90 |= SetBitL90(i);
997 m_occupied_l45 |= SetBitL45(i);
998 m_occupied_r45 |= SetBitR45(i);
999 }
1000 }
1001
1002 // Side to move
1003 c = fen[++i];
1004 if(c == 'w')
1005 {
1006 m_stm = White;
1007 }
1008 else if(c == 'b')
1009 {
1010 m_stm = Black;
1011 }
1012 else if(c == 0)
1013 {
1014 return true;
1015 }
1016 else
1017 {
1018 return false;
1019 }
1020 ++i;
1021
1022 // Castling Rights
1023 c = fen[++i];
1024 if(c == 0)
1025 {
1026 return true;
1027 }
1028
1029 m_castlingRooks = 0;
1030
1031 if(c != '-')
1032 {
1033 while(c != ' ')
1034 {
1035 switch(c)
1036 {
1037 case 'K':
1038 setCastleShort(White);
1039 break;
1040 case 'Q':
1041 setCastleLong(White);
1042 break;
1043 case 'k':
1044 setCastleShort(Black);
1045 break;
1046 case 'q':
1047 setCastleLong(Black);
1048 break;
1049 default:
1050 {
1051 if (c>='a' && c<='h')
1052 {
1053 Square x = SquareFromRankAndFile(7,c);
1054 if (x<m_ksq[Black])
1055 {
1056 setChess960(true);
1057 m_castlingRooks |= SetBit(x);
1058 setCastleLong(Black);
1059 }
1060 else if (x>m_ksq[Black])
1061 {
1062 setChess960(true);
1063 m_castlingRooks |= SetBit(x);
1064 setCastleShort(Black);
1065 }
1066 }
1067 else if (c>='A' && c<='H')
1068 {
1069 Square x = SquareFromRankAndFile(0,c);
1070 if (x<m_ksq[White])
1071 {
1072 setChess960(true);
1073 m_castlingRooks |= SetBit(x);
1074 setCastleLong(White);
1075 }
1076 else if (x>m_ksq[White])
1077 {
1078 setChess960(true);
1079 m_castlingRooks |= SetBit(x);
1080 setCastleShort(White);
1081 }
1082 }
1083 else
1084 {
1085 return false;
1086 }
1087 }
1088 break;
1089 }
1090
1091 c = fen[++i];
1092 }
1093 }
1094 else
1095 {
1096 ++i; // Bypass space
1097 }
1098
1099 if (!m_castlingRooks)
1100 {
1101 setCastlingRooks();
1102 }
1103 else
1104 {
1105 fixCastlingRooks(true);
1106 }
1107
1108 // EnPassant Square
1109 c = fen[++i];
1110 if(c == 0)
1111 {
1112 return true;
1113 }
1114 if(c != '-')
1115 {
1116 bool epgood = true;
1117 if(c >= 'a' && c <= 'h')
1118 {
1119 m_epFile = c - 'a' + 1;
1120 }
1121 else if(c >= 'A' && c <= 'H')
1122 {
1123 m_epFile = c - 'A' + 1;
1124 }
1125 else if(c < '0' || c > '9')
1126 {
1127 return false;
1128 }
1129 else
1130 {
1131 epgood = false;
1132 }
1133 if(epgood)
1134 {
1135 c = fen[++i];
1136 if(m_stm == White && c != '6')
1137 {
1138 return false;
1139 }
1140 else if(m_stm == Black && c != '3')
1141 {
1142 return false;
1143 }
1144 }
1145 }
1146 epFile2Square();
1147 ++i;
1148
1149 // Half move clock
1150 c = fen[++i];
1151 if(c == 0)
1152 {
1153 return true;
1154 }
1155 if (c=='-')
1156 {
1157 m_halfMoves = 0; // Workaround for some lazy generators
1158 ++i; // Eat ws
1159 }
1160 else
1161 {
1162 if(c < '0' || c > '9')
1163 {
1164 return false;
1165 }
1166 int j = i;
1167 while(c >= '0' && c <= '9')
1168 {
1169 c = fen[++i];
1170 }
1171 m_halfMoves = fen.midRef(j, i - j).toInt();
1172 }
1173
1174 // Move number
1175 c = fen[++i];
1176 if(c == 0)
1177 {
1178 return true;
1179 }
1180 if (c=='-')
1181 {
1182 m_moveNumber=1; // Workaround for some lazy generators
1183 }
1184 else
1185 {
1186 if(c < '0' || c > '9')
1187 {
1188 return false;
1189 }
1190 m_moveNumber = fen.midRef(i).toInt();
1191 while(c >= '0' && c <= '9')
1192 {
1193 c = fen[++i];
1194 }
1195
1196 if(m_moveNumber == 0)
1197 {
1198 // Silently fix illegal movenumber
1199 m_moveNumber = 1;
1200 }
1201 }
1202
1203 return true;
1204 }
1205
setCastlingRooks(char file000,char file00)1206 void BitBoard::setCastlingRooks(char file000, char file00)
1207 {
1208 if (chess960())
1209 {
1210 m_castlingRooks = m_rooks; // Keep a copy of the original rook positions for castling rights
1211 }
1212 else
1213 {
1214 m_castlingRooks = BitBoard::standardCastlingRooks();
1215 return;
1216 }
1217
1218 Color canCastleColor = NoColor;
1219 if (canCastle(White))
1220 {
1221 canCastleColor = White;
1222 }
1223 else if (canCastle(Black))
1224 {
1225 canCastleColor = Black;
1226 }
1227 if (canCastleColor == NoColor)
1228 {
1229 m_castlingRooks = BitBoard::standardCastlingRooks();
1230 return;
1231 }
1232
1233 fixCastlingRooks(false, file000, file00);
1234 }
1235
fixCastlingRooks(bool onlyMissingSections,char file000,char file00)1236 void BitBoard::fixCastlingRooks(bool onlyMissingSections, char file000, char file00)
1237 {
1238 Square Sections[4][2] = { { a1, m_ksq[White] },
1239 { h1, m_ksq[White] },
1240 { a8, m_ksq[Black] },
1241 { h8, m_ksq[Black] }};
1242
1243 Square filesForSection[4] =
1244 {
1245 file000 ? SquareFromRankAndFile(0,file000) : Square(InvalidSquare),
1246 file00 ? SquareFromRankAndFile(0,file00) : Square(InvalidSquare),
1247 file000 ? SquareFromRankAndFile(7,file000) : Square(InvalidSquare),
1248 file00 ? SquareFromRankAndFile(7,file00) : Square(InvalidSquare)
1249 };
1250
1251 for (int section=0; section<4; ++section)
1252 {
1253 Square start = Sections[section][0];
1254 Square stop = Sections[section][1];
1255 Square iter = start;
1256 do
1257 {
1258 quint64 x = SetBit(iter);
1259 if (m_castlingRooks & x)
1260 {
1261 if (filesForSection[section] != InvalidSquare)
1262 {
1263 if (iter != filesForSection[section])
1264 {
1265 m_castlingRooks &= ~x;
1266 }
1267 else
1268 {
1269 break;
1270 }
1271 }
1272 else
1273 {
1274 break;
1275 }
1276 }
1277 iter += (start<stop) ? +1 : -1;
1278 } while (iter != stop);
1279
1280 if (iter == stop)
1281 {
1282 // No bit set in section, fix this with arbitrary square
1283 m_castlingRooks |= SetBit(start);
1284 }
1285 else if (!onlyMissingSections)
1286 {
1287 // One bit is set, clear all others
1288 do
1289 {
1290 iter += (start<stop) ? +1 : -1;
1291 quint64 x = SetBit(iter);
1292
1293 if (m_castlingRooks & x)
1294 {
1295 m_castlingRooks &= ~x;
1296 }
1297 } while (iter != stop);
1298 }
1299 }
1300 }
1301
hasAmbiguousCastlingRooks(char file000,char file00) const1302 bool BitBoard::hasAmbiguousCastlingRooks(char file000, char file00) const
1303 {
1304 if (!chess960()) return false;
1305
1306 Square Sections[4][2] = { { a1, m_ksq[White] },
1307 { h1, m_ksq[White] },
1308 { a8, m_ksq[Black] },
1309 { h8, m_ksq[Black] }};
1310
1311 bool testRequired[4] =
1312 {
1313 canCastleLong(White),
1314 canCastleShort(White),
1315 canCastleLong(Black),
1316 canCastleShort(Black)
1317 };
1318
1319 Square filesForSection[4] =
1320 {
1321 file000 ? SquareFromRankAndFile(0,file000) : Square(InvalidSquare),
1322 file00 ? SquareFromRankAndFile(0,file00) : Square(InvalidSquare),
1323 file000 ? SquareFromRankAndFile(7,file000) : Square(InvalidSquare),
1324 file00 ? SquareFromRankAndFile(7,file00) : Square(InvalidSquare)
1325 };
1326
1327 for (int section=0; section<4; ++section)
1328 {
1329 if (!testRequired[section]) continue;
1330 bool found = false;
1331 Square start = Sections[section][0];
1332 Square stop = Sections[section][1];
1333 Square iter = start;
1334 do
1335 {
1336 quint64 x = SetBit(iter);
1337 if (m_rooks & x)
1338 {
1339 if (filesForSection[section] != InvalidSquare )
1340 {
1341 if (iter != filesForSection[section])
1342 {
1343 return true;
1344 }
1345 else
1346 {
1347 // Outer rook is allowed rook -> unambiguous
1348 break;
1349 }
1350 }
1351 else
1352 {
1353 if (found) return true;
1354 found = true;
1355 }
1356 }
1357 iter += (start<stop) ? +1 : -1;
1358 } while (iter != stop);
1359 }
1360 return false;
1361 }
1362
countSetBits(quint64 n) const1363 unsigned int BitBoard::countSetBits(quint64 n) const
1364 {
1365 unsigned int count = 0;
1366 while (n)
1367 {
1368 n &= (n-1);
1369 count++;
1370 }
1371 return count;
1372 }
1373
fromChess960pos(int i)1374 void BitBoard::fromChess960pos(int i)
1375 {
1376 setChess960(true);
1377
1378 if (i<0 || i>959)
1379 {
1380 setStandardPosition();
1381 return;
1382 }
1383
1384 #define scanc(x) {while (f[c] != 0) c++; while (n>0) if (f[++c] == 0) n--;f[c] = x;}
1385
1386 int n, c, knights[10][2] = {{0,0},{0,1},{0,2},{0,3},{1,0},{1,1},{1,2},{2,0},{2,1},{3,0}};
1387 char f[9];
1388 memset(&f[0],0,sizeof(f));
1389
1390 n = i % 4; i /= 4; f[n*2+1]='b';
1391 n = i % 4; i /= 4; f[n*2]='b';
1392 n = i % 6; i /= 6; c = 0; scanc('q');
1393 n = knights[i][0]; c=0; scanc('n');
1394 n = knights[i][1]; scanc('n');
1395 c=0; scanc('r'); c=0; scanc('k'); c=0; scanc('r');
1396
1397 QString fen(f);
1398 QString qfen = QString("%1/pppppppp/8/8/8/8/PPPPPPPP/%2 w KQkq - 0 1")
1399 .arg(fen, fen.toUpper());
1400
1401 fromGoodFen(qfen, true);
1402 }
1403
chess960Pos() const1404 int BitBoard::chess960Pos() const
1405 {
1406 int ccPos = 0;
1407
1408 if (m_occupied & 0x0000FFFFFFFF0000uLL)
1409 {
1410 return -1;
1411 }
1412
1413 if (((m_pawns & m_occupied_co[White]) != 0x000000000000FF00uLL) ||
1414 ((m_pawns & m_occupied_co[Black]) != 0x00FF000000000000uLL))
1415 {
1416 return -1;
1417 }
1418
1419 if ((m_pieceCount[White] != 16) || (m_pieceCount[Black] != 16))
1420 {
1421 return -1;
1422 }
1423
1424 if (countSetBits(m_bishops) != 4) return -1;
1425 if (countSetBits(m_rooks) != 4) return -1;
1426 if (countSetBits(m_knights) != 4) return -1;
1427 if (countSetBits(m_queens) != 2) return -1;
1428 if (countSetBits(m_kings) != 2) return -1;
1429
1430 quint64 x = (m_bishops & (2+8+32+128));
1431 if (x==0)
1432 return -1;
1433 quint64 bs1 = (getFirstBitAndClear64<Square>(x)-1)/2;
1434 ccPos += bs1;
1435 x = m_bishops & (1+4+16+64);
1436 if (x==0)
1437 return -1;
1438 quint64 bs2 = getFirstBitAndClear64<Square>(x)*2;
1439 ccPos += bs2;
1440
1441 int q = 0;
1442 bool qf = false;
1443 int n0 = 0;
1444 int n1 = 0;
1445 bool n0f = false;
1446 bool n1f = false;
1447 int rf = 0;
1448 int n0s[] = { 0,4,7,9 };
1449 for (Square square=a1; square<=h1; ++square)
1450 {
1451 if (pieceAt(square) == WhiteQueen)
1452 {
1453 qf = true;
1454 }
1455 else if ((pieceAt(square) == WhiteRook) || (pieceAt(square) == WhiteKing))
1456 {
1457 if (pieceAt(square) == WhiteKing)
1458 {
1459 if (rf!=1) return -1;
1460 }
1461 else
1462 {
1463 ++rf;
1464 }
1465 if (!qf) { ++q; };
1466 if (!n0f) { ++n0; } else { if (!n1f) ++n1; }
1467 }
1468 else if (pieceAt(square) == WhiteKnight)
1469 {
1470 if (!qf) { ++q; };
1471 if (!n0f) { n0f = true; } else { n1f = true; }
1472 }
1473 }
1474
1475 if ((n0<4) && n1f && qf)
1476 {
1477 ccPos += q*16;
1478 int krn = n0s[n0]+n1;
1479 ccPos += krn*96;
1480 return ccPos;
1481 }
1482
1483 return -1;
1484 }
1485
chess960() const1486 bool BitBoard::chess960() const
1487 {
1488 return m_chess960;
1489 }
1490
setChess960(bool chess960)1491 void BitBoard::setChess960(bool chess960)
1492 {
1493 m_chess960 = chess960;
1494 }
1495
generateMoves() const1496 Move::List BitBoard::generateMoves() const
1497 {
1498 // This function is not ready for Chess960
1499 // don't care the way it is used for the moment
1500
1501 Square from, to;
1502 quint64 moves, movers;
1503
1504 Move::List p;
1505
1506 if(m_stm == White)
1507 {
1508 // castle moves
1509 if(canCastle(White))
1510 {
1511 if(canCastleShort(White) && !((F1 | G1)&m_occupied))
1512 if(!isAttackedBy(Black, e1) &&
1513 !isAttackedBy(Black, f1)
1514 && !isAttackedBy(Black, g1))
1515 {
1516 append(p).genWhiteOO();
1517 }
1518 if(canCastleLong(White) && !((B1 | C1 | D1)&m_occupied))
1519 if(!isAttackedBy(Black, c1) &&
1520 !isAttackedBy(Black, d1)
1521 && !isAttackedBy(Black, e1))
1522 {
1523 append(p).genWhiteOOO();
1524 }
1525 }
1526
1527 // pawn en passant moves
1528 movers = m_pawns & m_occupied_co[White];
1529 if(m_epSquare != NoEPSquare)
1530 {
1531 moves = bb_PawnAttacks[Black][m_epSquare] & movers;
1532 while(moves)
1533 {
1534 from = getFirstBitAndClear64<Square>(moves);
1535 append(p).genEnPassant(from, m_epSquare);
1536 }
1537 }
1538
1539 // pawn captures
1540 moves = ShiftUpRight(movers) & m_occupied_co[Black];
1541 while(moves)
1542 {
1543 to = getFirstBitAndClear64<Square>(moves);
1544 if(Rank(to) != 7)
1545 {
1546 append(p).genPawnMove(to - 9, to, m_piece[to]);
1547 }
1548 else
1549 {
1550 append(p).genCapturePromote(to - 9, to, Queen, m_piece[to]);
1551 append(p).genCapturePromote(to - 9, to, Knight, m_piece[to]);
1552 append(p).genCapturePromote(to - 9, to, Rook, m_piece[to]);
1553 append(p).genCapturePromote(to - 9, to, Bishop, m_piece[to]);
1554 }
1555 }
1556 moves = ShiftUpLeft(movers) & m_occupied_co[Black];
1557 while(moves)
1558 {
1559 to = getFirstBitAndClear64<Square>(moves);
1560 if(Rank(to) != 7)
1561 {
1562 append(p).genPawnMove(to - 7, to, m_piece[to]);
1563 }
1564 else
1565 {
1566 append(p).genCapturePromote(to - 7, to, Queen, m_piece[to]);
1567 append(p).genCapturePromote(to - 7, to, Knight, m_piece[to]);
1568 append(p).genCapturePromote(to - 7, to, Rook, m_piece[to]);
1569 append(p).genCapturePromote(to - 7, to, Bishop, m_piece[to]);
1570 }
1571 }
1572
1573 // pawns 1 forward
1574 moves = ShiftUp(movers) & ~m_occupied;
1575 movers = moves;
1576 while(moves)
1577 {
1578 to = getFirstBitAndClear64<Square>(moves);
1579 if(Rank(to) != 7)
1580 {
1581 append(p).genOneForward(to - 8, to);
1582 }
1583 else
1584 {
1585 append(p).genPromote(to - 8, to, Queen);
1586 append(p).genPromote(to - 8, to, Knight);
1587 append(p).genPromote(to - 8, to, Rook);
1588 append(p).genPromote(to - 8, to, Bishop);
1589 }
1590 }
1591 // pawns 2 forward
1592 moves = ShiftUp(movers) & rank4 & ~m_occupied;
1593 while(moves)
1594 {
1595 to = getFirstBitAndClear64<Square>(moves);
1596 append(p).genTwoForward(to - 16, to);
1597 }
1598
1599 }
1600 else
1601 {
1602 // castle moves
1603 if(canCastle(Black))
1604 {
1605 if(canCastleShort(Black) && !((F8 | G8)&m_occupied))
1606 if(!isAttackedBy(White, e8) &&
1607 !isAttackedBy(White, f8) &&
1608 !isAttackedBy(White, g8))
1609 {
1610 append(p).genBlackOO();
1611 }
1612 if(canCastleLong(Black) && !((B8 | C8 | D8)&m_occupied))
1613 if(!isAttackedBy(White, e8) &&
1614 !isAttackedBy(White, d8) &&
1615 !isAttackedBy(White, c8))
1616 {
1617 append(p).genBlackOOO();
1618 }
1619 }
1620
1621 // pawn en passant moves
1622 movers = m_pawns & m_occupied_co[Black];
1623 if(m_epSquare != NoEPSquare)
1624 {
1625 moves = bb_PawnAttacks[White][m_epSquare] & movers;
1626 while(moves)
1627 {
1628 from = getFirstBitAndClear64<Square>(moves);
1629 append(p).genEnPassant(from, m_epSquare);
1630 }
1631 }
1632
1633 // pawn captures
1634 moves = ShiftDownLeft(movers) & m_occupied_co[White];
1635 while(moves)
1636 {
1637 to = getFirstBitAndClear64<Square>(moves);
1638 if(Rank(to) != 0)
1639 {
1640 append(p).genPawnMove(to + 9, to, m_piece[to]);
1641 }
1642 else
1643 {
1644 append(p).genCapturePromote(to + 9, to, Queen, m_piece[to]);
1645 append(p).genCapturePromote(to + 9, to, Knight, m_piece[to]);
1646 append(p).genCapturePromote(to + 9, to, Rook, m_piece[to]);
1647 append(p).genCapturePromote(to + 9, to, Bishop, m_piece[to]);
1648 }
1649 }
1650 moves = ShiftDownRight(movers) & m_occupied_co[White];
1651 while(moves)
1652 {
1653 to = getFirstBitAndClear64<Square>(moves);
1654 if(Rank(to) != 0)
1655 {
1656 append(p).genPawnMove(to + 7, to, m_piece[to]);
1657 }
1658 else
1659 {
1660 append(p).genCapturePromote(to + 7, to, Queen, m_piece[to]);
1661 append(p).genCapturePromote(to + 7, to, Knight, m_piece[to]);
1662 append(p).genCapturePromote(to + 7, to, Rook, m_piece[to]);
1663 append(p).genCapturePromote(to + 7, to, Bishop, m_piece[to]);
1664 }
1665 }
1666
1667 // pawns 1 forward
1668 moves = ShiftDown(movers) & ~m_occupied;
1669 movers = moves;
1670 while(moves)
1671 {
1672 to = getFirstBitAndClear64<Square>(moves);
1673 if(Rank(to) != 0)
1674 {
1675 append(p).genOneForward(to + 8, to);
1676 }
1677 else
1678 {
1679 append(p).genPromote(to + 8, to, Queen);
1680 append(p).genPromote(to + 8, to, Knight);
1681 append(p).genPromote(to + 8, to, Rook);
1682 append(p).genPromote(to + 8, to, Bishop);
1683 }
1684 }
1685 // pawns 2 forward
1686 moves = ShiftDown(movers) & rank5 & ~m_occupied;
1687 while(moves)
1688 {
1689 to = getFirstBitAndClear64<Square>(moves);
1690 append(p).genTwoForward(to + 16, to);
1691 }
1692 }
1693
1694 // knight moves
1695 movers = m_knights & m_occupied_co[m_stm];
1696 while(movers)
1697 {
1698 from = getFirstBitAndClear64<Square>(movers);
1699 moves = knightAttacksFrom(from) & ~m_occupied_co[m_stm];
1700 while(moves)
1701 {
1702 to = getFirstBitAndClear64<Square>(moves);
1703 append(p).genKnightMove(from, to, m_piece[to]);
1704 }
1705 }
1706 // bishop moves
1707 movers = m_bishops & m_occupied_co[m_stm];
1708 while(movers)
1709 {
1710 from = getFirstBitAndClear64<Square>(movers);
1711 moves = bishopAttacksFrom(from) & ~m_occupied_co[m_stm];
1712 while(moves)
1713 {
1714 to = getFirstBitAndClear64<Square>(moves);
1715 append(p).genBishopMove(from, to, m_piece[to]);
1716 }
1717 }
1718 // rook moves
1719 movers = m_rooks & m_occupied_co[m_stm];
1720 while(movers)
1721 {
1722 from = getFirstBitAndClear64<Square>(movers);
1723 moves = rookAttacksFrom(from) & ~m_occupied_co[m_stm];
1724 while(moves)
1725 {
1726 to = getFirstBitAndClear64<Square>(moves);
1727 append(p).genRookMove(from, to, m_piece[to]);
1728 }
1729 }
1730 // queen moves
1731 movers = m_queens & m_occupied_co[m_stm];
1732 while(movers)
1733 {
1734 from = getFirstBitAndClear64<Square>(movers);
1735 moves = queenAttacksFrom(from) & ~m_occupied_co[m_stm];
1736 while(moves)
1737 {
1738 to = getFirstBitAndClear64<Square>(moves);
1739 append(p).genQueenMove(from, to, m_piece[to]);
1740 }
1741 }
1742 // king moves
1743 moves = kingAttacksFrom(m_ksq[m_stm]) & ~m_occupied_co[m_stm];
1744 while(moves)
1745 {
1746 to = getFirstBitAndClear64<Square>(moves);
1747 if(!isAttackedBy(m_stm ^ 1, to))
1748 {
1749 append(p).genKingMove(m_ksq[m_stm], to, m_piece[to]);
1750 }
1751 }
1752
1753 return p;
1754 }
1755
isIntoCheck(const Move & move) const1756 bool BitBoard::isIntoCheck(const Move& move) const
1757 {
1758 BitBoard peek(*this);
1759 peek.doMove(move);
1760 peek.swapToMove();
1761 return peek.isCheck();
1762 }
1763
1764 // Create a null move (a2a2)
1765 // A Null Move is represented in pgn by a "--" although illegal
1766 // it is often used in ebooks to annotate ideas
nullMove() const1767 Move BitBoard::nullMove() const
1768 {
1769 Move m;
1770 m.setNullMove();
1771 if(m_stm == Black)
1772 {
1773 m.setBlack();
1774 }
1775 m.u = m_halfMoves;
1776 m.u |= (((unsigned short) m_castle & 0xF) << 8);
1777 m.u |= (((unsigned short) m_epFile & 0xF) << 12);
1778 return m;
1779 }
1780
strncmpi(QByteArray a,QByteArray b,int n)1781 static int strncmpi(QByteArray a, QByteArray b, int n)
1782 {
1783 return strncmp(a.toLower(), b.toLower(), n);
1784 }
1785
createCastlingK() const1786 Move BitBoard::createCastlingK() const
1787 {
1788 Square k = m_chess960 ? m_ksq[m_stm] : ((m_stm == White) ? e1 : e8);
1789 Square to = m_chess960 ? CastlingRook(1+2*(int)m_stm) : ((m_stm == White) ? g1 : g8);
1790 return prepareMove(k, to);
1791 }
1792
createCastlingQ() const1793 Move BitBoard::createCastlingQ() const
1794 {
1795 Square k = m_chess960 ? m_ksq[m_stm] : ((m_stm == White) ? e1 : e8);
1796 Square to = m_chess960 ? CastlingRook(2*(int)m_stm) : ((m_stm == White) ? c1 : c8);
1797 return prepareMove(k, to);
1798 }
1799
parseMove(const QString & algebraic) const1800 Move BitBoard::parseMove(const QString& algebraic) const
1801 {
1802 const QByteArray& bs(algebraic.toLatin1());
1803 const char *san = bs.constData();
1804 const char* s = san;
1805 char c = *(s++);
1806 quint64 match;
1807 Square fromSquare = InvalidSquare;
1808 Square toSquare = InvalidSquare;
1809 int fromFile = -1;
1810 int fromRank = -1;
1811 Move move;
1812 unsigned int type;
1813
1814 if (algebraic=="none")
1815 return move;
1816
1817 // Castling
1818 if(c == 'o' || c == 'O' || c == '0')
1819 {
1820 if (strlen(san)>=5)
1821 {
1822 if(strncmpi(san, "o-o-o", 5) == 0 || strncmp(san, "0-0-0", 5) == 0)
1823 {
1824 return createCastlingQ();
1825 }
1826 }
1827 else if (strlen(san)==3)
1828 {
1829 if(strncmpi(san, "o-o", 3) == 0 || strncmp(san, "0-0", 3) == 0)
1830 {
1831 return createCastlingK();
1832 }
1833 else if(strncmp(san, "000", 3) == 0)
1834 {
1835 return createCastlingQ();
1836 }
1837 }
1838 else if (strlen(san)==2)
1839 {
1840 if ((strncmp(san, "00", 2) == 0) || (strncmpi(san, "0K", 2) == 0))
1841 {
1842 return createCastlingK();
1843 }
1844 else if (strncmpi(san, "0Q", 2) == 0)
1845 {
1846 return createCastlingQ();
1847 }
1848 }
1849 return move;
1850 }
1851
1852 // Null Move
1853 if(c == '-')
1854 {
1855 if(strncmp(san, "--", 2) == 0)
1856 {
1857 return nullMove();
1858 }
1859 }
1860 else if (c == 'Z')
1861 {
1862 if(strncmp(san, "Z0", 2) == 0)
1863 {
1864 return nullMove();
1865 }
1866 }
1867
1868 // Piece
1869 switch(c)
1870 {
1871 case 'Q':
1872 type = Queen;
1873 c = *(s++);
1874 break;
1875 case 'R':
1876 type = Rook;
1877 c = *(s++);
1878 break;
1879 case 'B':
1880 type = Bishop;
1881 c = *(s++);
1882 break;
1883 case 'N':
1884 type = Knight;
1885 c = *(s++);
1886 break;
1887 case 'K':
1888 type = King;
1889 c = *(s++);
1890 break;
1891 case 'P':
1892 c = *(s++); // Fall through
1893 type = Pawn;
1894 break;
1895 default:
1896 type = Empty;
1897 break;
1898 }
1899
1900 // Check for disambiguation
1901 if(isFile(c))
1902 {
1903 fromFile = c - 'a';
1904 c = *(s++);
1905 if(isRank(c))
1906 {
1907 fromSquare = Square((c - '1') * 8 + fromFile);
1908 fromFile = -1;
1909 c = *(s++);
1910 }
1911 }
1912 else if(isRank(c))
1913 {
1914 fromRank = c - '1';
1915 c = *(s++);
1916 }
1917
1918 // Capture indicator (or dash in the case of a LAN move)
1919 if(c == 'x' || c == '-' || c == ':')
1920 {
1921 c = *(s++);
1922 }
1923
1924 // Destination square
1925 if(isFile(c))
1926 {
1927 int f = c - 'a';
1928 c = *(s++);
1929 if(!isRank(c))
1930 {
1931 return move;
1932 }
1933 toSquare = Square((c - '1') * 8 + f);
1934 c = *(s++);
1935 }
1936 else
1937 {
1938 toSquare = fromSquare;
1939 fromSquare = InvalidSquare;
1940 }
1941
1942 if(toSquare == InvalidSquare)
1943 {
1944 return move;
1945 }
1946
1947 if (type == Empty)
1948 {
1949 // either a pawn or a piece, is determined by source location
1950 if (fromSquare == InvalidSquare)
1951 {
1952 type = Pawn;
1953 }
1954 else
1955 {
1956 type = m_piece[fromSquare];
1957 if (type == Empty)
1958 {
1959 return move; // There is no piece here
1960 }
1961 }
1962 }
1963
1964 if(type == Pawn)
1965 {
1966 PieceType promotePiece = None;
1967
1968 // Promotion as in bxc8=Q or bxc8(Q) or bxc8(Q)
1969 if(c == '=' || c == '(' || QString("QRBN").indexOf(toupper(c))>=0)
1970 {
1971 if(c == '=' || c == '(')
1972 {
1973 c = *(s++);
1974 }
1975 switch(toupper(c))
1976 {
1977 case 'Q':
1978 promotePiece = Queen;
1979 break;
1980 case 'R':
1981 promotePiece = Rook;
1982 break;
1983 case 'B':
1984 promotePiece = Bishop;
1985 break;
1986 case 'N':
1987 promotePiece = Knight;
1988 break;
1989 default:
1990 {
1991 int lastRank = (m_stm == White ? 7 : 0);
1992 if (lastRank == Rank(toSquare))
1993 {
1994 return move;
1995 }
1996 }
1997 break;
1998 }
1999 }
2000 if(fromSquare == InvalidSquare)
2001 {
2002 int base = (m_stm == White ? -8 : 8);
2003 if(fromFile < 0)
2004 {
2005 if (((m_stm == White) && (Rank(toSquare) > 1)) ||
2006 ((m_stm == Black) && (Rank(toSquare) < 7)))
2007 {
2008 fromSquare = toSquare + base;
2009 quint64 bit = SetBit(fromSquare);
2010 if(!(m_occupied_co[m_stm] & bit))
2011 {
2012 if (((m_stm == White) && (Rank(toSquare) > 1)) ||
2013 ((m_stm == Black) && (Rank(toSquare) < 7)))
2014 {
2015 fromSquare += base;
2016 }
2017 }
2018 }
2019 }
2020 else if(fromFile <= (int) File(toSquare))
2021 {
2022 fromSquare = toSquare + (base - 1);
2023 }
2024 else
2025 {
2026 fromSquare = toSquare + (base + 1);
2027 }
2028 }
2029 if ((fromSquare != InvalidSquare) && (m_piece[fromSquare] == Pawn))
2030 {
2031 // This isn't a hugely efficient way to go from here
2032 move = prepareMove(fromSquare, toSquare);
2033 if(move.isPromotion() && promotePiece)
2034 {
2035 move.setPromoted(promotePiece);
2036 }
2037 }
2038 return move;
2039 }
2040
2041 if(fromSquare == InvalidSquare)
2042 {
2043 switch(type)
2044 {
2045 case Queen:
2046 match = queenAttacksFrom(toSquare) & m_queens;
2047 break;
2048 case Rook:
2049 match = rookAttacksFrom(toSquare) & m_rooks;
2050 break;
2051 case Bishop:
2052 match = bishopAttacksFrom(toSquare) & m_bishops;
2053 break;
2054 case Knight:
2055 match = knightAttacksFrom(toSquare) & m_knights;
2056 break;
2057 case King:
2058 match = kingAttacksFrom(toSquare) & m_kings;
2059 break;
2060 default:
2061 return move;
2062 }
2063
2064 match &= m_occupied_co[m_stm];
2065 if(fromRank >= 0)
2066 {
2067 match &= bb_rankMask[fromRank];
2068 }
2069 else if(fromFile >= 0)
2070 {
2071 match &= bb_fileMask[fromFile];
2072 }
2073
2074 if(match)
2075 {
2076 fromSquare = getFirstBitAndClear64<Square>(match);
2077 }
2078 else
2079 {
2080 return move;
2081 }
2082
2083 // If not yet fully disambiguated, all but one move must be illegal
2084 // Cycle through them, and pick the first legal move.
2085 while(match)
2086 {
2087 if(prepareMove(fromSquare, toSquare).isLegal())
2088 {
2089 break;
2090 }
2091 fromSquare = getFirstBitAndClear64<Square>(match);
2092 }
2093 }
2094
2095 if(type != m_piece[fromSquare])
2096 {
2097 return move;
2098 }
2099
2100 return prepareMove(fromSquare, toSquare);
2101 }
2102
doMove(const Move & m)2103 bool BitBoard::doMove(const Move& m)
2104 {
2105 Square from = m.from();
2106 Square to = m.to();
2107 unsigned int sntm = m_stm ^ 1; // side not to move
2108 quint64 bb_from = SetBit(from);
2109 quint64 bb_to = SetBit(to);
2110 Square rook_from = InvalidSquare, rook_to = InvalidSquare;
2111
2112 m_epFile = 0;
2113 m_halfMoves++; // Number of moves since last capture or pawn move
2114 bool cleanupFrom = true;
2115
2116 unsigned int action = m.action();
2117 if (!m.isNullMove()) switch(action)
2118 {
2119 case Pawn:
2120 m_halfMoves = 0;
2121 m_pawns ^= bb_from ^ bb_to;
2122 m_piece[to] = Pawn;
2123 break;
2124 case Knight:
2125 m_knights ^= bb_from ^ bb_to;
2126 m_piece[to] = Knight;
2127 break;
2128 case Bishop:
2129 m_bishops ^= bb_from ^ bb_to;
2130 m_piece[to] = Bishop;
2131 break;
2132 case Rook:
2133 m_rooks ^= bb_from ^ bb_to;
2134 m_piece[to] = Rook;
2135 if(canCastle(m_stm) && (m_castlingRooks & bb_from)) // a rook is moving, destroy castle flags if needed
2136 {
2137 destroyCastleInDirection(m_stm, from);
2138 }
2139 break;
2140 case Queen:
2141 m_queens ^= bb_from ^ bb_to;
2142 m_piece[to] = Queen;
2143 break;
2144 case King:
2145 m_kings ^= bb_from ^ bb_to;
2146 m_ksq[m_stm] = to;
2147 m_piece[to] = King;
2148 destroyCastle(m_stm); // king is moving so definitely destroy castle stuff!
2149 break;
2150 case Move::CASTLE:
2151 destroyCastle(m_stm);
2152 if (!m_chess960)
2153 {
2154 switch(to)
2155 {
2156 case c1:
2157 rook_from = a1;
2158 rook_to = d1;
2159 break;
2160 case g1:
2161 rook_from = h1;
2162 rook_to = f1;
2163 break;
2164 case c8:
2165 rook_from = a8;
2166 rook_to = d8;
2167 break;
2168 case g8:
2169 rook_from = h8;
2170 rook_to = f8;
2171 break;
2172 default:
2173 return false;
2174 }
2175 }
2176 else
2177 {
2178 switch(to)
2179 {
2180 case c1:
2181 rook_from = CastlingRook(0);
2182 rook_to = d1;
2183 break;
2184 case g1:
2185 rook_from = CastlingRook(1);
2186 rook_to = f1;
2187 break;
2188 case c8:
2189 rook_from = CastlingRook(2);
2190 rook_to = d8;
2191 break;
2192 case g8:
2193 rook_from = CastlingRook(3);
2194 rook_to = f8;
2195 break;
2196 default:
2197 return false;
2198 }
2199 }
2200 if (bb_from != bb_to)
2201 {
2202 m_kings ^= bb_from ^ bb_to;
2203 m_ksq[m_stm] = to;
2204 m_piece[to] = King;
2205 }
2206 else
2207 {
2208 cleanupFrom = false;
2209 }
2210 if (from == rook_to) cleanupFrom = false;
2211 if (rook_from != rook_to)
2212 {
2213 if (to != rook_from) m_piece[rook_from] = Empty;
2214 m_piece[rook_to] = Rook;
2215 m_rooks ^= SetBit(rook_from) ^ SetBit(rook_to);
2216 m_occupied_co[m_stm] ^= SetBit(rook_from) ^ SetBit(rook_to);
2217 m_occupied_l90 ^= SetBitL90(rook_from) ^ SetBitL90(rook_to);
2218 m_occupied_l45 ^= SetBitL45(rook_from) ^ SetBitL45(rook_to);
2219 m_occupied_r45 ^= SetBitR45(rook_from) ^ SetBitR45(rook_to);
2220 }
2221 break;
2222 case Move::TWOFORWARD:
2223 m_halfMoves = 0;
2224 m_pawns ^= bb_from ^ bb_to;
2225 m_piece[to] = Pawn;
2226 // According to PGN standard, ep square should be always set.
2227 m_epFile = File(to) + 1;
2228 break;
2229 case Move::PROMOTE:
2230 m_halfMoves = 0;
2231 m_pawns ^= bb_from;
2232 --m_pawnCount[m_stm];
2233 switch(m.promoted())
2234 {
2235 case Knight:
2236 m_knights ^= bb_to;
2237 m_piece[to] = Knight;
2238 break;
2239 case Bishop:
2240 m_bishops ^= bb_to;
2241 m_piece[to] = Bishop;
2242 break;
2243 case Rook:
2244 m_rooks ^= bb_to;
2245 m_piece[to] = Rook;
2246 break;
2247 case Queen:
2248 m_queens ^= bb_to;
2249 m_piece[to] = Queen;
2250 break;
2251 default: // can't promote to other piece types;
2252 break;
2253 }
2254 break;
2255 }
2256
2257 switch(m.removal())
2258 {
2259 case Empty:
2260 if (to != from)
2261 {
2262 m_occupied_l90 ^= SetBitL90(to); // extra cleanup needed for non-captures
2263 m_occupied_l45 ^= SetBitL45(to);
2264 m_occupied_r45 ^= SetBitR45(to);
2265 }
2266 break;
2267 case Pawn:
2268 --m_pawnCount[sntm];
2269 --m_pieceCount[sntm];
2270 m_halfMoves = 0;
2271 m_pawns ^= bb_to;
2272 m_occupied_co[sntm] ^= bb_to;
2273 break;
2274 case Knight:
2275 --m_pieceCount[sntm];
2276 m_halfMoves = 0;
2277 m_knights ^= bb_to;
2278 m_occupied_co[sntm] ^= bb_to;
2279 break;
2280 case Bishop:
2281 --m_pieceCount[sntm];
2282 m_halfMoves = 0;
2283 m_bishops ^= bb_to;
2284 m_occupied_co[sntm] ^= bb_to;
2285 break;
2286 case Rook:
2287 --m_pieceCount[sntm];
2288 m_halfMoves = 0;
2289 m_rooks ^= bb_to;
2290 m_occupied_co[sntm] ^= bb_to;
2291 if(canCastle(sntm) && (m_castlingRooks & bb_to))
2292 {
2293 destroyCastleInDirection(sntm, to);
2294 }
2295 break;
2296 case Queen:
2297 --m_pieceCount[sntm];
2298 m_halfMoves = 0;
2299 m_queens ^= bb_to;
2300 m_occupied_co[sntm] ^= bb_to;
2301 break;
2302 case Move::ENPASSANT:
2303 --m_pawnCount[sntm];
2304 --m_pieceCount[sntm];
2305 m_halfMoves = 0;
2306 unsigned int epsq = to + (m_stm == White ? -8 : 8); // annoying move, the capture is not on the 'to' square
2307 m_piece[epsq] = Empty;
2308 m_pawns ^= SetBit(epsq);
2309 m_occupied_co[sntm] ^= SetBit(epsq);
2310 m_occupied_l90 ^= SetBitL90(to) ^ SetBitL90(epsq);
2311 m_occupied_l45 ^= SetBitL45(to) ^ SetBitL45(epsq);
2312 m_occupied_r45 ^= SetBitR45(to) ^ SetBitR45(epsq);
2313 break;
2314 } // ...no I did not forget the king :)
2315
2316 if(!m.isNullMove())
2317 {
2318 if (cleanupFrom)
2319 {
2320 m_piece[from] = Empty;
2321 }
2322 if (bb_from != bb_to)
2323 {
2324 m_occupied_co[m_stm] ^= bb_from ^ bb_to;
2325 m_occupied_l90 ^= SetBitL90(from);
2326 m_occupied_l45 ^= SetBitL45(from);
2327 m_occupied_r45 ^= SetBitR45(from);
2328 }
2329 m_occupied = m_occupied_co[White] + m_occupied_co[Black];
2330 }
2331
2332 if(m_stm == Black)
2333 {
2334 ++m_moveNumber;
2335 }
2336
2337 m_stm ^= 1; // toggle side to move
2338 epFile2Square();
2339 return true;
2340 }
2341
undoMove(const Move & m)2342 void BitBoard::undoMove(const Move& m)
2343 {
2344 Square from = m.from();
2345 Square to = m.to();
2346 unsigned int sntm = m_stm ^ 1; // side not to move
2347 quint64 bb_from = SetBit(from);
2348 quint64 bb_to = SetBit(to);
2349 Square rook_from = InvalidSquare, rook_to = InvalidSquare;
2350
2351 bool cleanupFrom = true;
2352
2353 unsigned int action = m.action();
2354 if(!m.isNullMove()) switch(action)
2355 {
2356 case Pawn:
2357 case Move::TWOFORWARD:
2358 m_pawns ^= bb_from ^ bb_to;
2359 m_piece[from] = Pawn;
2360 break;
2361 case Knight:
2362 m_knights ^= bb_from ^ bb_to;
2363 m_piece[from] = Knight;
2364 break;
2365 case Bishop:
2366 m_bishops ^= bb_from ^ bb_to;
2367 m_piece[from] = Bishop;
2368 break;
2369 case Rook:
2370 m_rooks ^= bb_from ^ bb_to;
2371 m_piece[from] = Rook;
2372 break;
2373 case Queen:
2374 m_queens ^= bb_from ^ bb_to;
2375 m_piece[from] = Queen;
2376 break;
2377 case King:
2378 m_kings ^= bb_from ^ bb_to;
2379 m_ksq[sntm] = from;
2380 m_piece[from] = King;
2381 break;
2382 case Move::CASTLE:
2383 if (bb_from != bb_to)
2384 {
2385 m_kings ^= bb_from ^ bb_to;
2386 m_ksq[sntm] = from;
2387 m_piece[from] = King;
2388 }
2389 else
2390 {
2391 cleanupFrom = false;
2392 }
2393 if (!chess960())
2394 {
2395 switch(to)
2396 {
2397 case c1:
2398 rook_from = a1;
2399 rook_to = d1;
2400 break;
2401 case g1:
2402 rook_from = h1;
2403 rook_to = f1;
2404 break;
2405 case c8:
2406 rook_from = a8;
2407 rook_to = d8;
2408 break;
2409 case g8:
2410 rook_from = h8;
2411 rook_to = f8;
2412 break;
2413 default:
2414 return;
2415 }
2416 }
2417 else
2418 {
2419 switch(to)
2420 {
2421 case c1:
2422 rook_from = CastlingRook(0);
2423 rook_to = d1;
2424 break;
2425 case g1:
2426 rook_from = CastlingRook(1);
2427 rook_to = f1;
2428 break;
2429 case c8:
2430 rook_from = CastlingRook(2);
2431 rook_to = d8;
2432 break;
2433 case g8:
2434 rook_from = CastlingRook(3);
2435 rook_to = f8;
2436 break;
2437 default:
2438 return;
2439 }
2440 }
2441 if (rook_from == to) cleanupFrom = false;
2442 if (rook_from != rook_to)
2443 {
2444 if (rook_to != from) m_piece[rook_to] = Empty;
2445 m_piece[rook_from] = Rook;
2446 m_rooks ^= SetBit(rook_from) ^ SetBit(rook_to);
2447 m_occupied_co[sntm] ^= SetBit(rook_from) ^ SetBit(rook_to);
2448 m_occupied_l90 ^= SetBitL90(rook_from) ^ SetBitL90(rook_to);
2449 m_occupied_l45 ^= SetBitL45(rook_from) ^ SetBitL45(rook_to);
2450 m_occupied_r45 ^= SetBitR45(rook_from) ^ SetBitR45(rook_to);
2451 }
2452 break;
2453 case Move::PROMOTE:
2454 m_pawns ^= bb_from;
2455 m_piece[from] = Pawn;
2456 ++m_pawnCount[sntm];
2457 switch(m.promoted())
2458 {
2459 case Knight:
2460 m_knights ^= bb_to;
2461 break;
2462 case Bishop:
2463 m_bishops ^= bb_to;
2464 break;
2465 case Rook:
2466 m_rooks ^= bb_to;
2467 break;
2468 case Queen:
2469 m_queens ^= bb_to;
2470 break;
2471 default: // can't promote to other piece types;
2472 break;
2473 }
2474 break;
2475 }
2476
2477 unsigned int replace = m.capturedType();
2478 switch(m.removal()) // Reverse captures
2479 {
2480 case Empty:
2481 if (to != from)
2482 {
2483 m_occupied_l90 ^= SetBitL90(to); // extra cleanup needed for non-captures
2484 m_occupied_l45 ^= SetBitL45(to);
2485 m_occupied_r45 ^= SetBitR45(to);
2486 }
2487 break;
2488 case Pawn:
2489 ++m_pawnCount[m_stm];
2490 ++m_pieceCount[m_stm];
2491 m_pawns ^= bb_to;
2492 m_occupied_co[m_stm] ^= bb_to;
2493 break;
2494 case Knight:
2495 ++m_pieceCount[m_stm];
2496 m_knights ^= bb_to;
2497 m_occupied_co[m_stm] ^= bb_to;
2498 break;
2499 case Bishop:
2500 ++m_pieceCount[m_stm];
2501 m_bishops ^= bb_to;
2502 m_occupied_co[m_stm] ^= bb_to;
2503 break;
2504 case Rook:
2505 ++m_pieceCount[m_stm];
2506 m_rooks ^= bb_to;
2507 m_occupied_co[m_stm] ^= bb_to;
2508 break;
2509 case Queen:
2510 ++m_pieceCount[m_stm];
2511 m_queens ^= bb_to;
2512 m_occupied_co[m_stm] ^= bb_to;
2513 break;
2514 case Move::ENPASSANT:
2515 ++m_pawnCount[m_stm];
2516 ++m_pieceCount[m_stm];
2517 replace = Empty;
2518 unsigned int epsq = to + (sntm == White ? -8 : 8); // annoying move, the capture is not on the 'to' square
2519 m_piece[epsq] = Pawn;
2520 m_pawns ^= SetBit(epsq);
2521 m_occupied_co[m_stm] ^= SetBit(epsq);
2522 m_occupied_l90 ^= SetBitL90(to) ^ SetBitL90(epsq);
2523 m_occupied_l45 ^= SetBitL45(to) ^ SetBitL45(epsq);
2524 m_occupied_r45 ^= SetBitR45(to) ^ SetBitR45(epsq);
2525 break;
2526 } // ...no I did not forget the king :)
2527
2528 if(!m.isNullMove())
2529 {
2530 if (cleanupFrom)
2531 {
2532 m_piece[to] = replace;
2533 }
2534 if (bb_from != bb_to)
2535 {
2536 m_occupied_co[sntm] ^= bb_from ^ bb_to;
2537 m_occupied_l90 ^= SetBitL90(from);
2538 m_occupied_l45 ^= SetBitL45(from);
2539 m_occupied_r45 ^= SetBitR45(from);
2540 }
2541 m_occupied = m_occupied_co[White] + m_occupied_co[Black];
2542 }
2543
2544 m_stm ^= 1; // toggle side to move
2545
2546 if(m_stm == Black)
2547 {
2548 --m_moveNumber;
2549 }
2550
2551 m_halfMoves = m.u & 0xFF;
2552 m_castle = (m.u >> 8) & 0xF;
2553 m_epFile = (m.u >> 12) & 0xF;
2554 epFile2Square();
2555 }
2556
HasRookForCastling(int index) const2557 bool BitBoard::HasRookForCastling(int index) const
2558 {
2559 quint64 cr = m_castlingRooks;
2560 Square x = InvalidSquare;
2561 for (int i=0; i<=index; ++i)
2562 {
2563 x = getFirstBitAndClear64<Square>(cr);
2564 }
2565 return (m_rooks & SetBit(x));
2566 }
2567
CastlingRook(int index) const2568 Square BitBoard::CastlingRook(int index) const
2569 {
2570 quint64 cr = m_castlingRooks;
2571 Square x = InvalidSquare;
2572 for (int i=0; i<=index; ++i)
2573 {
2574 x = getFirstBitAndClear64<Square>(cr);
2575 }
2576 return x;
2577 }
2578
CastlingRookIndex(Square rook) const2579 int BitBoard::CastlingRookIndex(Square rook) const
2580 {
2581 quint64 cr = m_castlingRooks;
2582 for (int i=0; i<=3; ++i)
2583 {
2584 Square x = getFirstBitAndClear64<Square>(cr);
2585 if (x == rook) return i;
2586 }
2587 return -1;
2588 }
2589
HasRookOnFileForCastling(unsigned char file,bool castle000) const2590 bool BitBoard::HasRookOnFileForCastling(unsigned char file, bool castle000) const
2591 {
2592 if (castle000)
2593 {
2594 if (file > File(m_ksq[White]) && (file > File(m_ksq[Black]))) return false;
2595 }
2596 else
2597 {
2598 if (file < File(m_ksq[White]) && (file < File(m_ksq[Black]))) return false;
2599 }
2600 Square w = SquareFromRankAndFile(0,file);
2601 Square b = SquareFromRankAndFile(7,file);
2602 quint64 x = SetBit(w) | SetBit(b);
2603 return (m_rooks & x);
2604 }
2605
CastlingKingTarget(int rookIndex) const2606 Square BitBoard::CastlingKingTarget(int rookIndex) const
2607 {
2608 if ((rookIndex<0) || (rookIndex>3)) return InvalidSquare;
2609 static const Square kingTargets[] = { c1,g1,c8,g8 };
2610 return kingTargets[rookIndex];
2611 }
2612
CastlingRookTarget(int rookIndex) const2613 Square BitBoard::CastlingRookTarget(int rookIndex) const
2614 {
2615 if ((rookIndex<0) || (rookIndex>3)) return InvalidSquare;
2616 static const Square rookTargets[] = { d1,f1,d8,f8 };
2617 return rookTargets[rookIndex];
2618 }
2619
castlingRooks() const2620 quint64 BitBoard::castlingRooks() const
2621 {
2622 return m_castlingRooks;
2623 }
2624
standardCastlingRooks()2625 quint64 BitBoard::standardCastlingRooks()
2626 {
2627 return (A1 | H1 | A8 | H8);
2628 }
2629
pawnMovesFrom(const Square s) const2630 quint64 BitBoard::pawnMovesFrom(const Square s) const
2631 {
2632 quint64 targets = bb_PawnF1[m_stm][s] & ~m_occupied;
2633 if(targets)
2634 {
2635 targets |= bb_PawnF2[m_stm][s] & ~m_occupied;
2636 }
2637 if(m_epSquare == NoEPSquare)
2638 {
2639 targets |= bb_PawnAttacks[m_stm][s] & m_occupied_co[m_stm ^ 1];
2640 }
2641 else
2642 {
2643 targets |= bb_PawnAttacks[m_stm][s] & (m_occupied_co[m_stm ^ 1] | SetBit(m_epSquare));
2644 }
2645 return targets;
2646 }
2647
prepareMove(const Square & from,const Square & to) const2648 Move BitBoard::prepareMove(const Square& from, const Square& to) const
2649 {
2650 if ((from >= 64) || (to >= 64))
2651 {
2652 return Move();
2653 }
2654
2655 quint64 src = SetBit(from);
2656 quint64 dest = SetBit(to);
2657 Move move(from, to);
2658
2659 unsigned char p = m_piece[from];
2660
2661 bool nullMove = Move(from,to).isNullMove();
2662
2663 if (!nullMove)
2664 {
2665 // Check for Illegal Move
2666 // first the source square must not be vacant
2667 if(!(m_occupied_co[m_stm] & src))
2668 {
2669 return move;
2670 }
2671
2672 // Check for Illegal Move
2673 // If the destination square is a piece of the moving color
2674 if(m_occupied_co[m_stm] & dest)
2675 {
2676 if ((p!=King) || (m_piece[to] != Rook))
2677 {
2678 // Can't be castling move
2679 return move;
2680 }
2681 move.SetCastlingBit();
2682 }
2683
2684 move.setPieceType(p);
2685 unsigned char pCaptured = m_piece[to];
2686 move.setCaptureType(pCaptured);
2687
2688 if(p == King)
2689 {
2690 if (move.isCastling())
2691 {
2692 if (!prepareCastle(move))
2693 {
2694 return move;
2695 }
2696 }
2697 else if (!prepareCastle(move) && !(kingAttacksFrom(to) & src))
2698 {
2699 return move;
2700 }
2701 }
2702 else if(p == Pawn)
2703 {
2704 if(!(pawnMovesFrom(from) & dest))
2705 {
2706 return move;
2707 }
2708 else if(to == m_epSquare)
2709 {
2710 move.setEnPassant();
2711 }
2712 else if(dest & bb_PawnF2[m_stm][from])
2713 {
2714 move.setTwoForward();
2715 }
2716 else if(dest & bb_PromotionRank[m_stm])
2717 {
2718 move.setPromoted(Queen);
2719 }
2720 }
2721 else
2722 {
2723 quint64 reach = 0;
2724 if(p == Queen)
2725 {
2726 reach = queenAttacksFrom(to);
2727 }
2728 else if(p == Rook)
2729 {
2730 reach = rookAttacksFrom(to);
2731 }
2732 else if(p == Bishop)
2733 {
2734 reach = bishopAttacksFrom(to);
2735 }
2736 else if(p == Knight)
2737 {
2738 reach = knightAttacksFrom(to);
2739 }
2740 if(!(reach & src))
2741 {
2742 return move;
2743 }
2744 }
2745 }
2746
2747 BitBoard peek(*this);
2748 peek.doMove(move);
2749 peek.swapToMove();
2750 if(peek.isCheck()) // Don't allow move into check even if its a null move
2751 {
2752 return move;
2753 }
2754
2755 if(m_stm == Black)
2756 {
2757 move.setBlack();
2758 }
2759 move.u = m_halfMoves;
2760 move.u |= (((unsigned short) m_castle & 0xF) << 8);
2761 move.u |= (((unsigned short) m_epFile & 0xF) << 12);
2762 move.setLegalMove();
2763 return move;
2764 }
2765
prepareCastle(Move & move) const2766 bool BitBoard::prepareCastle(Move& move) const
2767 {
2768 if(!canCastle(m_stm))
2769 {
2770 return false;
2771 }
2772
2773 if (chess960())
2774 {
2775 if (!move.isCastling())
2776 {
2777 return false;
2778 }
2779 return prepareCastle960(move);
2780 }
2781
2782 Square to = move.to();
2783 if(m_stm == White)
2784 {
2785 if((((to == h1) && (H1&m_occupied)) || (to == g1)) && canCastleShort(White) && !((F1 | G1)&m_occupied))
2786 {
2787 if(!isAttackedBy(Black, e1) && !isAttackedBy(Black, f1))
2788 {
2789 move.genWhiteOO();
2790 return true;
2791 }
2792 }
2793 else if((((to == a1) && (A1&m_occupied)) || (to == c1)) && canCastleLong(White) && !((B1 | C1 | D1)&m_occupied))
2794 {
2795 if(!isAttackedBy(Black, e1) && !isAttackedBy(Black, d1))
2796 {
2797 move.genWhiteOOO();
2798 return true;
2799 }
2800 }
2801 }
2802 else
2803 {
2804 if((((to == h8) && (H8&m_occupied)) || to == g8) && canCastleShort(Black) && !((F8 | G8)&m_occupied))
2805 {
2806 if(!isAttackedBy(White, e8) && !isAttackedBy(White, f8))
2807 {
2808 move.genBlackOO();
2809 return true;
2810 }
2811 }
2812 else if((((to == a8) && (A8&m_occupied)) ||to == c8) && canCastleLong(Black) && !((B8 | C8 | D8)&m_occupied))
2813 {
2814 if(!isAttackedBy(White, e8) && !isAttackedBy(White, d8))
2815 {
2816 move.genBlackOOO();
2817 return true;
2818 }
2819 }
2820 }
2821
2822 return false;
2823 }
2824
isFreeForCastling960(Square from,Square to,Square rook_from,Square rook_to) const2825 bool BitBoard::isFreeForCastling960(Square from, Square to, Square rook_from, Square rook_to) const
2826 {
2827 Square square = from;
2828
2829 while(square!=to)
2830 {
2831 if ((square != from) && (square != rook_from))
2832 {
2833 if (pieceAt(square) != Empty) return false;
2834 }
2835 if (square!=to) square += (from<=to) ? 1:-1;
2836 }
2837
2838 if ((to != from) && (to != rook_from))
2839 {
2840 Piece p = pieceAt(to);
2841 if (p != Empty) return false;
2842 }
2843
2844 square = rook_from;
2845
2846 while(square!=rook_to)
2847 {
2848 if ((square != rook_from) && (square != from))
2849 {
2850 if (pieceAt(square) != Empty) return false;
2851 }
2852 if (square!=rook_to) square += (rook_from<=rook_to) ? 1:-1;
2853 }
2854
2855 if ((rook_from != rook_to) && (rook_to != from))
2856 {
2857 Piece p = pieceAt(rook_to);
2858 if (p != Empty) return false;
2859 }
2860
2861 return true; // Both ways, king and rook to target are free except for king/rook themselves
2862 }
2863
prepareCastle960(Move & move) const2864 bool BitBoard::prepareCastle960(Move& move) const
2865 {
2866 int n = CastlingRookIndex(move.to());
2867 if (n<0) return false; // No castling rook on target square (even though there is a rook)
2868
2869 Square to = CastlingKingTarget(n);
2870 Square rook_to = CastlingRookTarget(n);
2871 Square from = move.from();
2872 Square rook_from = move.to();
2873
2874 if(m_stm == White)
2875 {
2876 if((to == g1 && canCastleShort(White)) ||
2877 (to == c1 && canCastleLong(White)))
2878 {
2879 if (isFreeForCastling960(from, to, rook_from, rook_to))
2880 {
2881 if(!isAttackedBy(Black, from, to))
2882 {
2883 move.genKingMove(from, to, false);
2884 move.SetCastlingBit();
2885 return true;
2886 }
2887 }
2888 }
2889 }
2890 else
2891 {
2892 if((to == g8 && canCastleShort(Black)) ||
2893 (to == c8 && canCastleLong(Black)))
2894 {
2895 if (isFreeForCastling960(from, to, rook_from, rook_to))
2896 {
2897 if(!isAttackedBy(White, from, to))
2898 {
2899 move.genKingMove(from, to, false);
2900 move.SetCastlingBit();
2901 return true;
2902 }
2903 }
2904 }
2905 }
2906
2907 return false;
2908 }
2909
canBeReachedFrom(const BitBoard & target) const2910 bool BitBoard::canBeReachedFrom(const BitBoard& target) const
2911 {
2912 if(m_pieceCount[White] > target.m_pieceCount[White] ||
2913 m_pieceCount[Black] > target.m_pieceCount[Black] ||
2914 m_pawnCount[White] > target.m_pawnCount[White] ||
2915 m_pawnCount[Black] > target.m_pawnCount[Black])
2916 {
2917 return false;
2918 }
2919
2920 return true;
2921 }
2922
insufficientMaterial() const2923 bool BitBoard::insufficientMaterial() const
2924 {
2925 if (m_pawnCount[White]==0 && m_pawnCount[Black]==0)
2926 {
2927 if ((m_pieceCount[White] <= 2) && (m_pieceCount[Black] <= 2))
2928 {
2929 // now test for KB-K KN-K and KB-KB where the bishops have same color
2930 if (m_queens || m_rooks)
2931 {
2932 return false;
2933 }
2934 if (m_pieceCount[White]+m_pieceCount[Black] == 3)
2935 {
2936 return true;
2937 }
2938 if (m_knights)
2939 {
2940 return false; // Knights allow a mate always
2941 }
2942 if (!m_bishops)
2943 {
2944 return true; // bare kings
2945 }
2946 // Finally KB-KB
2947 quint64 n = m_bishops;
2948 quint64 n1 = getFirstBitAndClear64<Square>(n);
2949 quint64 n2 = getFirstBitAndClear64<Square>(n);
2950 int sum = n1+n2;
2951 return (sum & 1);
2952 }
2953 }
2954 return false;
2955 }
2956
kingSquare(Color color) const2957 Square BitBoard::kingSquare(Color color) const
2958 {
2959 return m_ksq[color];
2960 }
2961
colorAt(Square s) const2962 Color BitBoard::colorAt(Square s) const
2963 {
2964 Q_ASSERT(s < 64);
2965 quint64 bit = SetBit(s);
2966 if(m_occupied & bit)
2967 {
2968 if(m_occupied_co[White] & bit)
2969 {
2970 return White;
2971 }
2972 else
2973 {
2974 return Black;
2975 }
2976 }
2977 return NoColor;
2978 }
2979
pieceAt(Square s) const2980 Piece BitBoard::pieceAt(Square s) const
2981 {
2982 Q_ASSERT(s < 64);
2983 quint64 bit = SetBit(s);
2984 if(m_occupied & bit)
2985 {
2986 if(m_occupied_co[White] & bit)
2987 {
2988 return Piece(m_piece[s]);
2989 }
2990 else
2991 {
2992 return Piece(m_piece[s] + 6);
2993 }
2994 }
2995 return Empty;
2996 }
2997
2998 /** Return ASCII character for given piece to be used in FEN */
pieceToChar(const Piece piece)2999 inline QChar pieceToChar(const Piece piece)
3000 {
3001 return piece > BlackPawn ? '?' : " KQRBNPkqrbnp"[piece];
3002 };
3003
3004 /** Return ASCII character for given piece to be used in human FEN */
pieceToHumanChar(const Piece piece)3005 inline QChar pieceToHumanChar(const Piece piece)
3006 {
3007 return piece > BlackPawn ? '?' : " KQRBNPKQRBNP"[piece];
3008 };
3009
toFen(bool forceExtendedFEN) const3010 QString BitBoard::toFen(bool forceExtendedFEN) const
3011 {
3012 QString fen = "";
3013 Piece piece;
3014 int empty = 0;
3015
3016 //piece placement
3017 for(int row = 7; row >= 0; row--)
3018 {
3019 for(unsigned char col = 0; col < 8; ++col)
3020 {
3021 piece = pieceAt(SquareFromRankAndFile(row,col));
3022 if(piece != Empty)
3023 {
3024 if(empty != 0)
3025 {
3026 fen += QString::number(empty);
3027 empty = 0;
3028 }
3029 fen += pieceToChar(piece);
3030 }
3031 else
3032 {
3033 empty++;
3034 }
3035 }
3036 if(empty != 0)
3037 {
3038 fen += QString::number(empty);
3039 empty = 0;
3040 }
3041 if(row != 0)
3042 {
3043 fen += '/';
3044 }
3045 }
3046
3047 //side to move
3048 fen += m_stm == White ? " w " : " b ";
3049
3050 //castling rights
3051 if(castlingRights() == NoRights)
3052 {
3053 fen += "- ";
3054 }
3055 else
3056 {
3057 char s00 = 0;
3058 char s000 = 0;
3059 if (canCastleShort(White))
3060 {
3061 s00 = 'a'+File(CastlingRook(1));
3062 }
3063 else if (canCastleShort(Black))
3064 {
3065 s00 = 'a'+File(CastlingRook(3));
3066 }
3067 if (canCastleLong(White))
3068 {
3069 s000 = 'a'+File(CastlingRook(0));
3070 }
3071 else if (canCastleLong(Black))
3072 {
3073 s000 = 'a'+File(CastlingRook(2));
3074 }
3075 if (forceExtendedFEN || hasAmbiguousCastlingRooks(s000, s00))
3076 {
3077 if(castlingRights() & WhiteQueenside)
3078 {
3079 fen += 'A'+File(CastlingRook(0));
3080 }
3081 if(castlingRights() & WhiteKingside)
3082 {
3083 fen += 'A'+File(CastlingRook(1));
3084 }
3085 if(castlingRights() & BlackQueenside)
3086 {
3087 fen += 'a'+File(CastlingRook(2));
3088 }
3089 if(castlingRights() & BlackKingside)
3090 {
3091 fen += 'a'+File(CastlingRook(3));
3092 }
3093 }
3094 else
3095 {
3096 if(castlingRights() & WhiteKingside)
3097 {
3098 fen += 'K';
3099 }
3100 if(castlingRights() & WhiteQueenside)
3101 {
3102 fen += 'Q';
3103 }
3104 if(castlingRights() & BlackKingside)
3105 {
3106 fen += 'k';
3107 }
3108 if(castlingRights() & BlackQueenside)
3109 {
3110 fen += 'q';
3111 }
3112 }
3113 fen += ' ';
3114 }
3115
3116 //en passant square
3117 if(m_epSquare == NoEPSquare)
3118 {
3119 fen += "- ";
3120 }
3121 else
3122 {
3123 fen += 'a' + (m_epSquare & 7);
3124 fen += '1' + ((m_epSquare & 56) >> 3);
3125 fen += ' ';
3126 }
3127
3128 // half move clock
3129 fen += QString::number(halfMoveClock());
3130 fen += " ";
3131 // move number
3132 fen += QString::number(m_moveNumber == 0 ? 1 : m_moveNumber);
3133
3134 return fen;
3135 }
3136
toHumanFen() const3137 QString BitBoard::toHumanFen() const
3138 {
3139 QString fenFormat = QCoreApplication::translate("BitBoard", "w%1\nb%2\n%3 to move");
3140 QMap<Piece, QStringList> charLists;
3141
3142 //piece placement
3143 for(int row = 7; row >= 0; row--)
3144 {
3145 for(unsigned char col = 0; col < 8; ++col)
3146 {
3147 Piece piece = pieceAt(SquareFromRankAndFile(row,col));
3148 if(piece != Empty)
3149 {
3150 charLists[piece].append(QString("%1%2").arg(QChar('a' + col)).arg(row + 1));
3151 }
3152 }
3153 }
3154
3155 //side to move
3156 QString toMove = (m_stm == White) ? QCoreApplication::translate("BitBoard", "White") : QCoreApplication::translate("BitBoard", "Black");
3157
3158 QString w, b;
3159 for(Piece p = WhiteKing; p <= WhitePawn; ++p)
3160 {
3161 if(charLists.contains(p))
3162 {
3163 if(!w.isEmpty())
3164 {
3165 w += ",";
3166 }
3167 w.append(pieceToHumanChar(p));
3168 w.append(charLists[p].join(","));
3169 }
3170 }
3171 for(Piece p = BlackKing; p != Empty; ++p)
3172 {
3173 if(charLists.contains(p))
3174 {
3175 if(!b.isEmpty())
3176 {
3177 b += ",";
3178 }
3179 b.append(pieceToHumanChar(p));
3180 b.append(charLists[p].join(","));
3181 }
3182 }
3183
3184 QString fen = fenFormat.arg(w, b, toMove);
3185 fen.append(QString(" (%1+%2).").arg(m_pieceCount[White]).arg(m_pieceCount[Black]));
3186 return fen;
3187 }
3188
3189 /** Calculate global bit board values before starting */
bitBoardInit()3190 void bitBoardInit()
3191 {
3192 bitBoardInitRun = true;
3193 int i, q;
3194 quint64 mask;
3195
3196 // Square masks
3197 mask = 1;
3198 for(i = 0; i < 64; ++i)
3199 {
3200 bb_Mask[i] = mask << i;
3201 }
3202 for(i = 0; i < 64; ++i)
3203 {
3204 bb_MaskL90[i] = SetBit(RotateL90[i]);
3205 bb_MaskL45[i] = SetBit(RotateL45[i]);
3206 bb_MaskR45[i] = SetBit(RotateR45[i]);
3207 }
3208
3209 // Pawn moves and attacks
3210 for(i = 0; i < 64; ++i)
3211 {
3212 mask = SetBit(i);
3213 bb_PawnAttacks[White][i] = ShiftUpLeft(mask);
3214 bb_PawnAttacks[White][i] |= ShiftUpRight(mask);
3215
3216 bb_PawnAttacks[Black][i] = ShiftDownLeft(mask);
3217 bb_PawnAttacks[Black][i] |= ShiftDownRight(mask);
3218
3219 bb_PawnF1[White][i] = ShiftUp(mask);
3220 bb_PawnF2[White][i] = Shift2Up(mask) & rank4;
3221
3222 bb_PawnF1[Black][i] = ShiftDown(mask);
3223 bb_PawnF2[Black][i] = Shift2Down(mask) & rank5;
3224
3225 bb_PawnALL[White][i] = bb_PawnAttacks[White][i] |
3226 bb_PawnF1[White][i] |
3227 bb_PawnF2[White][i];
3228
3229 bb_PawnALL[Black][i] = bb_PawnAttacks[Black][i] |
3230 bb_PawnF1[Black][i] |
3231 bb_PawnF2[Black][i];
3232 }
3233
3234 // Knight attacks
3235 for(i = 0; i < 64; ++i)
3236 {
3237 mask = SetBit(i);
3238 bb_KnightAttacks[i] = ShiftLeft(Shift2Up(mask));
3239 bb_KnightAttacks[i] |= ShiftRight(Shift2Up(mask));
3240 bb_KnightAttacks[i] |= ShiftLeft(Shift2Down(mask));
3241 bb_KnightAttacks[i] |= ShiftRight(Shift2Down(mask));
3242 bb_KnightAttacks[i] |= Shift2Left(ShiftUp(mask));
3243 bb_KnightAttacks[i] |= Shift2Right(ShiftUp(mask));
3244 bb_KnightAttacks[i] |= Shift2Left(ShiftDown(mask));
3245 bb_KnightAttacks[i] |= Shift2Right(ShiftDown(mask));
3246 }
3247
3248 // Diagonal attacks
3249 for(int s = 0; s < 64; ++s)
3250 {
3251 for(int b = 0; b < 64; ++b)
3252 {
3253 mask = 0;
3254 q = s;
3255 while(File(q) > 0 && Rank(q) < 7)
3256 {
3257 q += 7;
3258 mask |= SetBit(q);
3259 if(b & (SetBit(RotateL45[q]) >> bb_ShiftL45[s]))
3260 {
3261 break;
3262 }
3263 }
3264 q = s;
3265 while(File(q) < 7 && Rank(q) > 0)
3266 {
3267 q -= 7;
3268 mask |= SetBit(q);
3269 if(b & (SetBit(RotateL45[q]) >> bb_ShiftL45[s]))
3270 {
3271 break;
3272 }
3273 }
3274 bb_L45Attacks[s][b] = mask;
3275
3276 mask = 0;
3277 q = s;
3278 while(File(q) < 7 && Rank(q) < 7)
3279 {
3280 q += 9;
3281 mask |= SetBit(q);
3282 if(b & (SetBit(RotateR45[q]) >> bb_ShiftR45[s]))
3283 {
3284 break;
3285 }
3286 }
3287 q = s;
3288 while(File(q) > 0 && Rank(q) > 0)
3289 {
3290 q -= 9;
3291 mask |= SetBit(q);
3292 if(b & (SetBit(RotateR45[q]) >> bb_ShiftR45[s]))
3293 {
3294 break;
3295 }
3296 }
3297 bb_R45Attacks[s][b] = mask;
3298 }
3299 }
3300
3301 // Rank and File attacks
3302 memset(bb_RankAttacks, 0, sizeof(bb_RankAttacks));
3303 memset(bb_FileAttacks, 0, sizeof(bb_FileAttacks));
3304 int file, rank;
3305 for(int sq = 0; sq < 64; ++sq)
3306 {
3307 for(int bitrow = 0; bitrow < 64; ++bitrow)
3308 {
3309 file = File(sq);
3310 q = sq + 1;
3311 while(++file < 8)
3312 {
3313 bb_RankAttacks[sq][bitrow] |= SetBit(q);
3314 if((1 << file) & (bitrow << 1))
3315 {
3316 break;
3317 }
3318 ++q;
3319 }
3320 file = File(sq);
3321 q = sq - 1;
3322 while(--file >= 0)
3323 {
3324 bb_RankAttacks[sq][bitrow] |= SetBit(q);
3325 if((1 << file) & (bitrow << 1))
3326 {
3327 break;
3328 }
3329 --q;
3330 }
3331 rank = Rank(sq);
3332 q = sq + 8;
3333 while(++rank < 8)
3334 {
3335 bb_FileAttacks[sq][bitrow] |= SetBit(q);
3336 if((1 << (7 - rank)) & (bitrow << 1))
3337 {
3338 break;
3339 }
3340 q += 8;
3341 }
3342 rank = Rank(sq);
3343 q = sq - 8;
3344 while(--rank >= 0)
3345 {
3346 bb_FileAttacks[sq][bitrow] |= SetBit(q);
3347 if((1 << (7 - rank)) & (bitrow << 1))
3348 {
3349 break;
3350 }
3351 q -= 8;
3352 }
3353 }
3354 }
3355
3356 // King:
3357 for(i = 0; i < 64; ++i)
3358 {
3359 mask = SetBit(i);
3360 bb_KingAttacks[i] = ShiftLeft(mask);
3361 bb_KingAttacks[i] |= ShiftRight(mask);
3362 bb_KingAttacks[i] |= ShiftUp(mask);
3363 bb_KingAttacks[i] |= ShiftDown(mask);
3364 bb_KingAttacks[i] |= ShiftUpLeft(mask);
3365 bb_KingAttacks[i] |= ShiftUpRight(mask);
3366 bb_KingAttacks[i] |= ShiftDownLeft(mask);
3367 bb_KingAttacks[i] |= ShiftDownRight(mask);
3368 }
3369
3370 // File and rank masks
3371 quint64 rseed = 0xFF00000000000000ULL;
3372 quint64 fseed = 0x8080808080808080ULL;
3373 for(i = 7; i >= 0; --i)
3374 {
3375 bb_rankMask[i] = rseed;
3376 rseed >>= 8;
3377 bb_fileMask[i] = fseed;
3378 fseed >>= 1;
3379 }
3380
3381 // Pawn promotion ranks
3382 bb_PromotionRank[White] = bb_rankMask[7];
3383 bb_PromotionRank[Black] = bb_rankMask[0];
3384
3385 // Now that global data has been calculated, we can create a start position
3386 standardPosition.fromFen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
3387 }
3388
getStandardPosition()3389 BitBoard getStandardPosition()
3390 {
3391 BitBoard b;
3392 b.fromFen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");
3393 return b;
3394 }
3395
moveToFullSan(const Move & move,bool translate) const3396 QString BitBoard::moveToFullSan(const Move &move, bool translate) const
3397 {
3398 QString dots = whiteToMove() ? "." : "...";
3399 return QString("%1%2%3").arg(m_moveNumber).arg(dots, moveToSan(move,translate));
3400 }
3401
3402 //a charboard is a 64 length board that looks something like this:
3403 //-----B----p------p---k-pq---N---r-----P-------P--P----K---Q-----
3404 //dashes: empty space
from64Char(const QString & qcharboard)3405 bool BitBoard::from64Char(const QString& qcharboard)
3406 {
3407 QStringList l = qcharboard.split(' ');
3408 if (l.size() < 30) return false;
3409 int n = 7;
3410 for (int i=C64_ROW8; i<=C64_ROW1; ++i,--n)
3411 {
3412 QString s = l[i];
3413 for (int j=7;j>=0;--j)
3414 {
3415 QChar c = s[j];
3416 Square sq = Square(n*8+j);
3417 switch (c.toLatin1())
3418 {
3419 case 'p': setAt(sq, BlackPawn); break;
3420 case 'n': setAt(sq, BlackKnight); break;
3421 case 'b': setAt(sq, BlackBishop); break;
3422 case 'r': setAt(sq, BlackRook); break;
3423 case 'q': setAt(sq, BlackQueen); break;
3424 case 'k': setAt(sq, BlackKing); break;
3425
3426 case 'P': setAt(sq, WhitePawn); break;
3427 case 'N': setAt(sq, WhiteKnight); break;
3428 case 'B': setAt(sq, WhiteBishop); break;
3429 case 'R': setAt(sq, WhiteRook); break;
3430 case 'Q': setAt(sq, WhiteQueen); break;
3431 case 'K': setAt(sq, WhiteKing); break;
3432 default: removeAt(sq); break;
3433 }
3434 }
3435 }
3436
3437 if (l[C64_COLOR_TO_MOVE]=="W")
3438 {
3439 setToMove(White);
3440 }
3441 else if (l[C64_COLOR_TO_MOVE]=="B")
3442 {
3443 setToMove(Black);
3444 }
3445
3446 int ep = l[C64_COL_DOUBLE_PAWN_PUSH].toInt();
3447 setEnPassantFile(ep);
3448
3449 if (l[C64_CASTLE_W_00].toInt()) setCastleShort(White);
3450 if (l[C64_CASTLE_W_000].toInt()) setCastleLong(White);
3451 if (l[C64_CASTLE_B_00].toInt()) setCastleShort(Black);
3452 if (l[C64_CASTLE_B_000].toInt()) setCastleLong(Black);
3453
3454 setCastlingRooks();
3455
3456 setMoveNumber(l[C64_NEXT_MOVE_NUMBER].toInt());
3457
3458 return true;
3459 }
3460
numAttackedBy(const unsigned int color,Square square) const3461 int BitBoard::numAttackedBy(const unsigned int color, Square square) const
3462 {
3463 int num = 0;
3464 num += countSetBits(bb_PawnAttacks[color ^ 1][square] & m_pawns & m_occupied_co[color]);
3465 num += countSetBits(knightAttacksFrom(square) & m_knights & m_occupied_co[color]);
3466 num += countSetBits(bishopAttacksFrom(square) & (m_bishops | m_queens) & m_occupied_co[color]);
3467 num += countSetBits(rookAttacksFrom(square) & (m_rooks | m_queens) & m_occupied_co[color]);
3468 num += countSetBits(kingAttacksFrom(square) & m_kings & m_occupied_co[color]);
3469 return num;
3470 };
3471
setMoveNumber(unsigned int moveNumber)3472 void BitBoard::setMoveNumber(unsigned int moveNumber)
3473 {
3474 m_moveNumber = moveNumber;
3475 }
3476
setToMove(const Color & c)3477 void BitBoard::setToMove(const Color &c)
3478 {
3479 m_stm = c;
3480 }
3481
positionIsSame(const BitBoard & target) const3482 bool BitBoard::positionIsSame(const BitBoard &target) const
3483 {
3484 if(m_occupied_co[White] != target.m_occupied_co[White] ||
3485 m_occupied_co[Black] != target.m_occupied_co[Black] ||
3486 m_pawns != target.m_pawns ||
3487 m_knights != target.m_knights ||
3488 m_bishops != target.m_bishops ||
3489 m_rooks != target.m_rooks ||
3490 m_queens != target.m_queens ||
3491 m_kings != target.m_kings ||
3492 m_stm != target.m_stm)
3493 {
3494 return false;
3495 }
3496 return true;
3497 }
3498
swapToMove()3499 void BitBoard::swapToMove()
3500 {
3501 m_stm ^= 1;
3502 }
3503
setCastlingRights(CastlingRights cr)3504 void BitBoard::setCastlingRights(CastlingRights cr)
3505 {
3506 m_castle = cr;
3507 }
3508