2 Glaurung, a UCI chess playing engine.
3 Copyright (C) 2004-2008 Tord Romstad
5 Glaurung is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
10 Glaurung is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
33 #include "ucioption.h"
40 int Position::castleRightsMask[64];
42 Key Position::zobrist[2][8][64];
43 Key Position::zobEp[64];
44 Key Position::zobCastle[16];
45 Key Position::zobMaterial[2][8][16];
46 Key Position::zobSideToMove;
48 Value Position::MgPieceSquareTable[16][64];
49 Value Position::EgPieceSquareTable[16][64];
58 Position::Position() { } // Do we really need this one?
60 Position::Position(const Position &pos) {
64 Position::Position(const std::string &fen) {
69 /// Position::from_fen() initializes the position object with the given FEN
70 /// string. This function is not very robust - make sure that input FENs are
71 /// correct (this is assumed to be the responsibility of the GUI).
73 void Position::from_fen(const std::string &fen) {
83 for(i = 0; fen[i] != ' '; i++) {
85 // Skip the given number of files
86 file += (fen[i] - '1' + 1);
88 Square square = make_square(file, rank);
90 case 'K': this->put_piece(WK, square); file++; break;
91 case 'Q': this->put_piece(WQ, square); file++; break;
92 case 'R': this->put_piece(WR, square); file++; break;
93 case 'B': this->put_piece(WB, square); file++; break;
94 case 'N': this->put_piece(WN, square); file++; break;
95 case 'P': this->put_piece(WP, square); file++; break;
96 case 'k': this->put_piece(BK, square); file++; break;
97 case 'q': this->put_piece(BQ, square); file++; break;
98 case 'r': this->put_piece(BR, square); file++; break;
99 case 'b': this->put_piece(BB, square); file++; break;
100 case 'n': this->put_piece(BN, square); file++; break;
101 case 'p': this->put_piece(BP, square); file++; break;
102 case '/': file = FILE_A; rank--; break;
105 std::cout << "Error in FEN at character " << i << std::endl;
115 else if(fen[i] == 'b')
118 std::cout << "Error in FEN at character " << i << std::endl;
125 std::cout << "Error in FEN at character " << i << std::endl;
130 while(strchr("KQkqabcdefghABCDEFGH-", fen[i])) {
134 else if(fen[i] == 'K') this->allow_oo(WHITE);
135 else if(fen[i] == 'Q') this->allow_ooo(WHITE);
136 else if(fen[i] == 'k') this->allow_oo(BLACK);
137 else if(fen[i] == 'q') this->allow_ooo(BLACK);
138 else if(fen[i] >= 'A' && fen[i] <= 'H') {
139 File rookFile, kingFile = FILE_NONE;
140 for(Square square = SQ_B1; square <= SQ_G1; square++)
141 if(this->piece_on(square) == WK)
142 kingFile = square_file(square);
143 if(kingFile == FILE_NONE) {
144 std::cout << "Error in FEN at character " << i << std::endl;
147 initialKFile = kingFile;
148 rookFile = File(fen[i] - 'A') + FILE_A;
149 if(rookFile < initialKFile) {
150 this->allow_ooo(WHITE);
151 initialQRFile = rookFile;
154 this->allow_oo(WHITE);
155 initialKRFile = rookFile;
158 else if(fen[i] >= 'a' && fen[i] <= 'h') {
159 File rookFile, kingFile = FILE_NONE;
160 for(Square square = SQ_B8; square <= SQ_G8; square++)
161 if(this->piece_on(square) == BK)
162 kingFile = square_file(square);
163 if(kingFile == FILE_NONE) {
164 std::cout << "Error in FEN at character " << i << std::endl;
167 initialKFile = kingFile;
168 rookFile = File(fen[i] - 'a') + FILE_A;
169 if(rookFile < initialKFile) {
170 this->allow_ooo(BLACK);
171 initialQRFile = rookFile;
174 this->allow_oo(BLACK);
175 initialKRFile = rookFile;
179 std::cout << "Error in FEN at character " << i << std::endl;
189 if(i < int(fen.length()) - 2)
190 if(fen[i] >= 'a' && fen[i] <= 'h' && (fen[i+1] == '3' || fen[i+1] == '6'))
191 epSquare = square_from_string(fen.substr(i, 2));
193 // Various initialisation
195 for(Square sq = SQ_A1; sq <= SQ_H8; sq++)
196 castleRightsMask[sq] = ALL_CASTLES;
197 castleRightsMask[make_square(initialKFile, RANK_1)] ^=
198 (WHITE_OO|WHITE_OOO);
199 castleRightsMask[make_square(initialKFile, RANK_8)] ^=
200 (BLACK_OO|BLACK_OOO);
201 castleRightsMask[make_square(initialKRFile, RANK_1)] ^= WHITE_OO;
202 castleRightsMask[make_square(initialKRFile, RANK_8)] ^= BLACK_OO;
203 castleRightsMask[make_square(initialQRFile, RANK_1)] ^= WHITE_OOO;
204 castleRightsMask[make_square(initialQRFile, RANK_8)] ^= BLACK_OOO;
206 this->find_checkers();
208 key = this->compute_key();
209 pawnKey = this->compute_pawn_key();
210 materialKey = this->compute_material_key();
211 mgValue = this->compute_mg_value();
212 egValue = this->compute_eg_value();
213 npMaterial[WHITE] = this->compute_non_pawn_material(WHITE);
214 npMaterial[BLACK] = this->compute_non_pawn_material(BLACK);
218 /// Position::to_fen() converts the position object to a FEN string. This is
219 /// probably only useful for debugging.
221 const std::string Position::to_fen() const {
222 char pieceLetters[] = " PNBRQK pnbrqk";
226 for(Rank rank = RANK_8; rank >= RANK_1; rank--) {
228 for(File file = FILE_A; file <= FILE_H; file++) {
229 Square square = make_square(file, rank);
230 if(this->square_is_occupied(square)) {
231 if(skip > 0) result += (char)skip + '0';
232 result += pieceLetters[this->piece_on(square)];
237 if(skip > 0) result += (char)skip + '0';
238 result += (rank > RANK_1)? '/' : ' ';
241 result += (sideToMove == WHITE)? 'w' : 'b';
243 if(castleRights == NO_CASTLES) result += '-';
245 if(this->can_castle_kingside(WHITE)) result += 'K';
246 if(this->can_castle_queenside(WHITE)) result += 'Q';
247 if(this->can_castle_kingside(BLACK)) result += 'k';
248 if(this->can_castle_queenside(BLACK)) result += 'q';
252 if(this->ep_square() == SQ_NONE) result += '-';
253 else result += square_to_string(this->ep_square());
259 /// Position::print() prints an ASCII representation of the position to
260 /// the standard output.
262 void Position::print() const {
263 char pieceStrings[][8] =
264 {"| ? ", "| P ", "| N ", "| B ", "| R ", "| Q ", "| K ", "| ? ",
265 "| ? ", "|=P=", "|=N=", "|=B=", "|=R=", "|=Q=", "|=K="
268 for(Rank rank = RANK_8; rank >= RANK_1; rank--) {
269 std::cout << "+---+---+---+---+---+---+---+---+\n";
270 for(File file = FILE_A; file <= FILE_H; file++) {
271 Square sq = make_square(file, rank);
272 Piece piece = this->piece_on(sq);
274 std::cout << ((square_color(sq) == WHITE)? "| " : "| . ");
276 std::cout << pieceStrings[piece];
280 std::cout << "+---+---+---+---+---+---+---+---+\n";
281 std::cout << this->to_fen() << std::endl;
282 std::cout << key << std::endl;
286 /// Position::copy() creates a copy of the input position.
288 void Position::copy(const Position &pos) {
289 memcpy(this, &pos, sizeof(Position));
293 /// Position:pinned_pieces() returns a bitboard of all pinned (against the
294 /// king) pieces for the given color.
296 Bitboard Position::pinned_pieces(Color c) const {
297 Bitboard b1, b2, pinned, pinners, sliders;
298 Square ksq = this->king_square(c), s;
299 Color them = opposite_color(c);
301 pinned = EmptyBoardBB;
302 b1 = this->occupied_squares();
304 sliders = this->rooks_and_queens(them) & ~this->checkers();
305 if(sliders & RookPseudoAttacks[ksq]) {
306 b2 = this->rook_attacks(ksq) & this->pieces_of_color(c);
307 pinners = rook_attacks_bb(ksq, b1 ^ b2) & sliders;
309 s = pop_1st_bit(&pinners);
310 pinned |= (squares_between(s, ksq) & b2);
314 sliders = this->bishops_and_queens(them) & ~this->checkers();
315 if(sliders & BishopPseudoAttacks[ksq]) {
316 b2 = this->bishop_attacks(ksq) & this->pieces_of_color(c);
317 pinners = bishop_attacks_bb(ksq, b1 ^ b2) & sliders;
319 s = pop_1st_bit(&pinners);
320 pinned |= (squares_between(s, ksq) & b2);
327 /// Position:discovered_check_candidates() returns a bitboard containing all
328 /// pieces for the given side which are candidates for giving a discovered
329 /// check. The code is almost the same as the function for finding pinned
332 Bitboard Position::discovered_check_candidates(Color c) const {
333 Bitboard b1, b2, dc, checkers, sliders;
334 Square ksq = this->king_square(opposite_color(c)), s;
337 b1 = this->occupied_squares();
339 sliders = this->rooks_and_queens(c);
340 if(sliders & RookPseudoAttacks[ksq]) {
341 b2 = this->rook_attacks(ksq) & this->pieces_of_color(c);
342 checkers = rook_attacks_bb(ksq, b1 ^ b2) & sliders;
344 s = pop_1st_bit(&checkers);
345 dc |= (squares_between(s, ksq) & b2);
349 sliders = this->bishops_and_queens(c);
350 if(sliders & BishopPseudoAttacks[ksq]) {
351 b2 = this->bishop_attacks(ksq) & this->pieces_of_color(c);
352 checkers = bishop_attacks_bb(ksq, b1 ^ b2) & sliders;
354 s = pop_1st_bit(&checkers);
355 dc |= (squares_between(s, ksq) & b2);
363 /// Position::square_is_attacked() checks whether the given side attacks the
366 bool Position::square_is_attacked(Square s, Color c) const {
368 (this->pawn_attacks(opposite_color(c), s) & this->pawns(c)) ||
369 (this->knight_attacks(s) & this->knights(c)) ||
370 (this->king_attacks(s) & this->kings(c)) ||
371 (this->rook_attacks(s) & this->rooks_and_queens(c)) ||
372 (this->bishop_attacks(s) & this->bishops_and_queens(c));
376 /// Position::attacks_to() computes a bitboard containing all pieces which
377 /// attacks a given square. There are two versions of this function: One
378 /// which finds attackers of both colors, and one which only finds the
379 /// attackers for one side.
381 Bitboard Position::attacks_to(Square s) const {
383 (this->black_pawn_attacks(s) & this->pawns(WHITE)) |
384 (this->white_pawn_attacks(s) & this->pawns(BLACK)) |
385 (this->knight_attacks(s) & this->pieces_of_type(KNIGHT)) |
386 (this->rook_attacks(s) & this->rooks_and_queens()) |
387 (this->bishop_attacks(s) & this->bishops_and_queens()) |
388 (this->king_attacks(s) & this->pieces_of_type(KING));
391 Bitboard Position::attacks_to(Square s, Color c) const {
392 return this->attacks_to(s) & this->pieces_of_color(c);
396 /// Position::piece_attacks_square() tests whether the piece on square f
397 /// attacks square t.
399 bool Position::piece_attacks_square(Square f, Square t) const {
400 assert(square_is_ok(f));
401 assert(square_is_ok(t));
403 switch(this->piece_on(f)) {
404 case WP: return this->white_pawn_attacks_square(f, t);
405 case BP: return this->black_pawn_attacks_square(f, t);
406 case WN: case BN: return this->knight_attacks_square(f, t);
407 case WB: case BB: return this->bishop_attacks_square(f, t);
408 case WR: case BR: return this->rook_attacks_square(f, t);
409 case WQ: case BQ: return this->queen_attacks_square(f, t);
410 case WK: case BK: return this->king_attacks_square(f, t);
411 default: return false;
418 /// Position::find_checkers() computes the checkersBB bitboard, which
419 /// contains a nonzero bit for each checking piece (0, 1 or 2). It
420 /// currently works by calling Position::attacks_to, which is probably
421 /// inefficient. Consider rewriting this function to use the last move
422 /// played, like in non-bitboard versions of Glaurung.
424 void Position::find_checkers() {
425 checkersBB = attacks_to(this->king_square(this->side_to_move()),
426 opposite_color(this->side_to_move()));
430 /// Position::move_is_legal() tests whether a pseudo-legal move is legal.
431 /// There are two versions of this function: One which takes only a
432 /// move as input, and one which takes a move and a bitboard of pinned
433 /// pieces. The latter function is faster, and should always be preferred
434 /// when a pinned piece bitboard has already been computed.
436 bool Position::move_is_legal(Move m) const {
437 return this->move_is_legal(m, this->pinned_pieces(this->side_to_move()));
441 bool Position::move_is_legal(Move m, Bitboard pinned) const {
445 assert(this->is_ok());
446 assert(move_is_ok(m));
447 assert(pinned == this->pinned_pieces(this->side_to_move()));
449 // If we're in check, all pseudo-legal moves are legal, because our
450 // check evasion generator only generates true legal moves.
451 if(this->is_check()) return true;
453 // Castling moves are checked for legality during move generation.
454 if(move_is_castle(m)) return true;
456 us = this->side_to_move();
457 them = opposite_color(us);
460 ksq = this->king_square(us);
462 assert(this->color_of_piece_on(from) == us);
463 assert(this->piece_on(ksq) == king_of_color(us));
465 // En passant captures are a tricky special case. Because they are
466 // rather uncommon, we do it simply by testing whether the king is attacked
467 // after the move is made:
469 Square to = move_to(m);
470 Square capsq = make_square(square_file(to), square_rank(from));
471 Bitboard b = this->occupied_squares();
473 assert(to == this->ep_square());
474 assert(this->piece_on(from) == pawn_of_color(us));
475 assert(this->piece_on(capsq) == pawn_of_color(them));
476 assert(this->piece_on(to) == EMPTY);
478 clear_bit(&b, from); clear_bit(&b, capsq); set_bit(&b, to);
480 (!(rook_attacks_bb(ksq, b) & this->rooks_and_queens(them)) &&
481 !(bishop_attacks_bb(ksq, b) & this->bishops_and_queens(them)));
484 // If the moving piece is a king, check whether the destination
485 // square is attacked by the opponent.
486 if(from == ksq) return !(this->square_is_attacked(move_to(m), them));
488 // A non-king move is legal if and only if it is not pinned or it
489 // is moving along the ray towards or away from the king.
490 if(!bit_is_set(pinned, from)) return true;
491 if(direction_between_squares(from, ksq) ==
492 direction_between_squares(move_to(m), ksq))
499 /// Position::move_is_check() tests whether a pseudo-legal move is a check.
500 /// There are two versions of this function: One which takes only a move as
501 /// input, and one which takes a move and a bitboard of discovered check
502 /// candidates. The latter function is faster, and should always be preferred
503 /// when a discovered check candidates bitboard has already been computed.
505 bool Position::move_is_check(Move m) const {
506 Bitboard dc = this->discovered_check_candidates(this->side_to_move());
507 return this->move_is_check(m, dc);
511 bool Position::move_is_check(Move m, Bitboard dcCandidates) const {
513 Square ksq, from, to;
515 assert(this->is_ok());
516 assert(move_is_ok(m));
517 assert(dcCandidates ==
518 this->discovered_check_candidates(this->side_to_move()));
520 us = this->side_to_move();
521 them = opposite_color(us);
525 ksq = this->king_square(them);
526 assert(this->color_of_piece_on(from) == us);
527 assert(this->piece_on(ksq) == king_of_color(them));
529 // Proceed according to the type of the moving piece:
530 switch(this->type_of_piece_on(from)) {
533 if(bit_is_set(this->pawn_attacks(them, ksq), to))
536 else if(bit_is_set(dcCandidates, from) &&
537 direction_between_squares(from, ksq) !=
538 direction_between_squares(to, ksq))
540 // Promotion with check?
541 else if(move_promotion(m)) {
542 Bitboard b = this->occupied_squares();
545 switch(move_promotion(m)) {
547 return this->knight_attacks_square(to, ksq);
549 return bit_is_set(bishop_attacks_bb(to, b), ksq);
551 return bit_is_set(rook_attacks_bb(to, b), ksq);
553 return bit_is_set(queen_attacks_bb(to, b), ksq);
558 // En passant capture with check? We have already handled the case
559 // of direct checks and ordinary discovered check, the only case we
560 // need to handle is the unusual case of a discovered check through the
562 else if(move_is_ep(m)) {
563 Square capsq = make_square(square_file(to), square_rank(from));
564 Bitboard b = this->occupied_squares();
566 clear_bit(&b, from); clear_bit(&b, capsq); set_bit(&b, to);
568 ((rook_attacks_bb(ksq, b) & this->rooks_and_queens(us)) ||
569 (bishop_attacks_bb(ksq, b) & this->bishops_and_queens(us)));
575 if(bit_is_set(dcCandidates, from))
579 return bit_is_set(this->knight_attacks(ksq), to);
583 if(bit_is_set(dcCandidates, from))
587 return bit_is_set(this->bishop_attacks(ksq), to);
591 if(bit_is_set(dcCandidates, from))
595 return bit_is_set(this->rook_attacks(ksq), to);
598 // Discovered checks are impossible!
599 assert(!bit_is_set(dcCandidates, from));
601 return bit_is_set(this->queen_attacks(ksq), to);
605 if(bit_is_set(dcCandidates, from) &&
606 direction_between_squares(from, ksq) !=
607 direction_between_squares(to, ksq))
609 // Castling with check?
610 if(move_is_castle(m)) {
611 Square kfrom, kto, rfrom, rto;
612 Bitboard b = this->occupied_squares();
617 kto = relative_square(us, SQ_G1);
618 rto = relative_square(us, SQ_F1);
621 kto = relative_square(us, SQ_C1);
622 rto = relative_square(us, SQ_D1);
625 clear_bit(&b, kfrom); clear_bit(&b, rfrom);
626 set_bit(&b, rto); set_bit(&b, kto);
628 return bit_is_set(rook_attacks_bb(rto, b), ksq);
643 /// Position::move_is_capture() tests whether a move from the current
644 /// position is a capture.
646 bool Position::move_is_capture(Move m) const {
648 this->color_of_piece_on(move_to(m)) == opposite_color(this->side_to_move())
653 /// Position::move_attacks_square() tests whether a move from the current
654 /// position attacks a given square. Only attacks by the moving piece are
655 /// considered; the function does not handle X-ray attacks.
657 bool Position::move_attacks_square(Move m, Square s) const {
658 assert(move_is_ok(m));
659 assert(square_is_ok(s));
661 Square f = move_from(m), t = move_to(m);
663 assert(this->square_is_occupied(f));
665 switch(this->piece_on(f)) {
666 case WP: return this->white_pawn_attacks_square(t, s);
667 case BP: return this->black_pawn_attacks_square(t, s);
668 case WN: case BN: return this->knight_attacks_square(t, s);
669 case WB: case BB: return this->bishop_attacks_square(t, s);
670 case WR: case BR: return this->rook_attacks_square(t, s);
671 case WQ: case BQ: return this->queen_attacks_square(t, s);
672 case WK: case BK: return this->king_attacks_square(t, s);
673 default: assert(false);
681 /// Position::backup() is called when making a move. All information
682 /// necessary to restore the position when the move is later unmade
683 /// is saved to an UndoInfo object. The function Position::restore
684 /// does the reverse operation: When one does a backup followed by
685 /// a restore with the same UndoInfo object, the position is restored
686 /// to the state before backup was called.
688 void Position::backup(UndoInfo &u) const {
689 u.castleRights = castleRights;
690 u.epSquare = epSquare;
691 u.checkersBB = checkersBB;
694 u.materialKey = materialKey;
696 u.lastMove = lastMove;
697 u.capture = NO_PIECE_TYPE;
703 /// Position::restore() is called when unmaking a move. It copies back
704 /// the information backed up during a previous call to Position::backup.
706 void Position::restore(const UndoInfo &u) {
707 castleRights = u.castleRights;
708 epSquare = u.epSquare;
709 checkersBB = u.checkersBB;
712 materialKey = u.materialKey;
714 lastMove = u.lastMove;
720 /// Position::do_move() makes a move, and backs up all information necessary
721 /// to undo the move to an UndoInfo object. The move is assumed to be legal.
722 /// Pseudo-legal moves should be filtered out before this function is called.
723 /// There are two versions of this function, one which takes only the move and
724 /// the UndoInfo as input, and one which takes a third parameter, a bitboard of
725 /// discovered check candidates. The second version is faster, because knowing
726 /// the discovered check candidates makes it easier to update the checkersBB
727 /// member variable in the position object.
729 void Position::do_move(Move m, UndoInfo &u) {
730 this->do_move(m, u, this->discovered_check_candidates(this->side_to_move()));
733 void Position::do_move(Move m, UndoInfo &u, Bitboard dcCandidates) {
734 assert(this->is_ok());
735 assert(move_is_ok(m));
737 // Back up the necessary information to our UndoInfo object (except the
738 // captured piece, which is taken care of later:
741 // Save the current key to the history[] array, in order to be able to
742 // detect repetition draws:
743 history[gamePly] = key;
745 // Increment the 50 moves rule draw counter. Resetting it to zero in the
746 // case of non-reversible moves is taken care of later.
749 if(move_is_castle(m))
750 this->do_castle_move(m);
751 else if(move_promotion(m))
752 this->do_promotion_move(m, u);
753 else if(move_is_ep(m))
758 PieceType piece, capture;
760 us = this->side_to_move();
761 them = opposite_color(us);
766 assert(this->color_of_piece_on(from) == us);
767 assert(this->color_of_piece_on(to) == them || this->piece_on(to) == EMPTY);
769 piece = this->type_of_piece_on(from);
770 capture = this->type_of_piece_on(to);
773 assert(capture != KING);
775 // Remove captured piece:
776 clear_bit(&(byColorBB[them]), to);
777 clear_bit(&(byTypeBB[capture]), to);
780 key ^= zobrist[them][capture][to];
782 // If the captured piece was a pawn, update pawn hash key:
784 pawnKey ^= zobrist[them][PAWN][to];
786 // Update incremental scores:
787 mgValue -= this->mg_pst(them, capture, to);
788 egValue -= this->eg_pst(them, capture, to);
792 npMaterial[them] -= piece_value_midgame(capture);
794 // Update material hash key:
795 materialKey ^= zobMaterial[them][capture][pieceCount[them][capture]];
797 // Update piece count:
798 pieceCount[them][capture]--;
800 // Update piece list:
801 pieceList[them][capture][index[to]] =
802 pieceList[them][capture][pieceCount[them][capture]];
803 index[pieceList[them][capture][index[to]]] = index[to];
805 // Remember the captured piece, in order to be able to undo the move
809 // Reset rule 50 counter:
814 clear_bit(&(byColorBB[us]), from);
815 clear_bit(&(byTypeBB[piece]), from);
816 clear_bit(&(byTypeBB[0]), from); // HACK: byTypeBB[0] == occupied squares
817 set_bit(&(byColorBB[us]), to);
818 set_bit(&(byTypeBB[piece]), to);
819 set_bit(&(byTypeBB[0]), to); // HACK: byTypeBB[0] == occupied squares
820 board[to] = board[from];
824 key ^= zobrist[us][piece][from] ^ zobrist[us][piece][to];
826 // Update incremental scores:
827 mgValue -= this->mg_pst(us, piece, from);
828 mgValue += this->mg_pst(us, piece, to);
829 egValue -= this->eg_pst(us, piece, from);
830 egValue += this->eg_pst(us, piece, to);
832 // If the moving piece was a king, update the king square:
836 // If the move was a double pawn push, set the en passant square.
837 // This code is a bit ugly right now, and should be cleaned up later.
839 if(epSquare != SQ_NONE) {
840 key ^= zobEp[epSquare];
844 if(abs(int(to) - int(from)) == 16) {
845 if((us == WHITE && (this->white_pawn_attacks(from + DELTA_N) &
846 this->pawns(BLACK))) ||
847 (us == BLACK && (this->black_pawn_attacks(from + DELTA_S) &
848 this->pawns(WHITE)))) {
849 epSquare = Square((int(from) + int(to)) / 2);
850 key ^= zobEp[epSquare];
853 // Reset rule 50 draw counter.
855 // Update pawn hash key:
856 pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to];
859 // Update piece lists:
860 pieceList[us][piece][index[from]] = to;
861 index[to] = index[from];
863 // Update castle rights:
864 key ^= zobCastle[castleRights];
865 castleRights &= castleRightsMask[from];
866 castleRights &= castleRightsMask[to];
867 key ^= zobCastle[castleRights];
869 // Update checkers bitboard:
870 checkersBB = EmptyBoardBB;
871 Square ksq = this->king_square(them);
876 if(bit_is_set(this->pawn_attacks(them, ksq), to))
877 set_bit(&checkersBB, to);
878 if(bit_is_set(dcCandidates, from))
880 ((this->rook_attacks(ksq) & this->rooks_and_queens(us)) |
881 (this->bishop_attacks(ksq) & this->bishops_and_queens(us)));
885 if(bit_is_set(this->knight_attacks(ksq), to))
886 set_bit(&checkersBB, to);
887 if(bit_is_set(dcCandidates, from))
889 ((this->rook_attacks(ksq) & this->rooks_and_queens(us)) |
890 (this->bishop_attacks(ksq) & this->bishops_and_queens(us)));
894 if(bit_is_set(this->bishop_attacks(ksq), to))
895 set_bit(&checkersBB, to);
896 if(bit_is_set(dcCandidates, from))
898 (this->rook_attacks(ksq) & this->rooks_and_queens(us));
902 if(bit_is_set(this->rook_attacks(ksq), to))
903 set_bit(&checkersBB, to);
904 if(bit_is_set(dcCandidates, from))
906 (this->bishop_attacks(ksq) & this->bishops_and_queens(us));
910 if(bit_is_set(this->queen_attacks(ksq), to))
911 set_bit(&checkersBB, to);
915 if(bit_is_set(dcCandidates, from))
917 ((this->rook_attacks(ksq) & this->rooks_and_queens(us)) |
918 (this->bishop_attacks(ksq) & this->bishops_and_queens(us)));
928 key ^= zobSideToMove;
929 sideToMove = opposite_color(sideToMove);
932 mgValue += (sideToMove == WHITE)? TempoValueMidgame : -TempoValueMidgame;
933 egValue += (sideToMove == WHITE)? TempoValueEndgame : -TempoValueEndgame;
935 assert(this->is_ok());
939 /// Position::do_castle_move() is a private method used to make a castling
940 /// move. It is called from the main Position::do_move function. Note that
941 /// castling moves are encoded as "king captures friendly rook" moves, for
942 /// instance white short castling in a non-Chess960 game is encoded as e1h1.
944 void Position::do_castle_move(Move m) {
946 Square kfrom, kto, rfrom, rto;
948 assert(this->is_ok());
949 assert(move_is_ok(m));
950 assert(move_is_castle(m));
952 us = this->side_to_move();
953 them = opposite_color(us);
955 // Find source squares for king and rook:
956 kfrom = move_from(m);
957 rfrom = move_to(m); // HACK: See comment at beginning of function.
959 assert(this->piece_on(kfrom) == king_of_color(us));
960 assert(this->piece_on(rfrom) == rook_of_color(us));
962 // Find destination squares for king and rook:
963 if(rfrom > kfrom) { // O-O
964 kto = relative_square(us, SQ_G1);
965 rto = relative_square(us, SQ_F1);
968 kto = relative_square(us, SQ_C1);
969 rto = relative_square(us, SQ_D1);
972 // Remove pieces from source squares:
973 clear_bit(&(byColorBB[us]), kfrom);
974 clear_bit(&(byTypeBB[KING]), kfrom);
975 clear_bit(&(byTypeBB[0]), kfrom); // HACK: byTypeBB[0] == occupied squares
976 clear_bit(&(byColorBB[us]), rfrom);
977 clear_bit(&(byTypeBB[ROOK]), rfrom);
978 clear_bit(&(byTypeBB[0]), rfrom); // HACK: byTypeBB[0] == occupied squares
980 // Put pieces on destination squares:
981 set_bit(&(byColorBB[us]), kto);
982 set_bit(&(byTypeBB[KING]), kto);
983 set_bit(&(byTypeBB[0]), kto); // HACK: byTypeBB[0] == occupied squares
984 set_bit(&(byColorBB[us]), rto);
985 set_bit(&(byTypeBB[ROOK]), rto);
986 set_bit(&(byTypeBB[0]), rto); // HACK: byTypeBB[0] == occupied squares
988 // Update board array:
989 board[kfrom] = board[rfrom] = EMPTY;
990 board[kto] = king_of_color(us);
991 board[rto] = rook_of_color(us);
993 // Update king square:
994 kingSquare[us] = kto;
996 // Update piece lists:
997 pieceList[us][KING][index[kfrom]] = kto;
998 pieceList[us][ROOK][index[rfrom]] = rto;
999 int tmp = index[rfrom];
1000 index[kto] = index[kfrom];
1003 // Update incremental scores:
1004 mgValue -= this->mg_pst(us, KING, kfrom);
1005 mgValue += this->mg_pst(us, KING, kto);
1006 egValue -= this->eg_pst(us, KING, kfrom);
1007 egValue += this->eg_pst(us, KING, kto);
1008 mgValue -= this->mg_pst(us, ROOK, rfrom);
1009 mgValue += this->mg_pst(us, ROOK, rto);
1010 egValue -= this->eg_pst(us, ROOK, rfrom);
1011 egValue += this->eg_pst(us, ROOK, rto);
1014 key ^= zobrist[us][KING][kfrom] ^ zobrist[us][KING][kto];
1015 key ^= zobrist[us][ROOK][rfrom] ^ zobrist[us][ROOK][rto];
1017 // Clear en passant square:
1018 if(epSquare != SQ_NONE) {
1019 key ^= zobEp[epSquare];
1023 // Update castling rights:
1024 key ^= zobCastle[castleRights];
1025 castleRights &= castleRightsMask[kfrom];
1026 key ^= zobCastle[castleRights];
1028 // Reset rule 50 counter:
1031 // Update checkers BB:
1032 checkersBB = attacks_to(this->king_square(them), us);
1036 /// Position::do_promotion_move() is a private method used to make a promotion
1037 /// move. It is called from the main Position::do_move function. The
1038 /// UndoInfo object, which has been initialized in Position::do_move, is
1039 /// used to store the captured piece (if any).
1041 void Position::do_promotion_move(Move m, UndoInfo &u) {
1044 PieceType capture, promotion;
1046 assert(this->is_ok());
1047 assert(move_is_ok(m));
1048 assert(move_promotion(m));
1050 us = this->side_to_move();
1051 them = opposite_color(us);
1053 from = move_from(m);
1056 assert(pawn_rank(us, to) == RANK_8);
1057 assert(this->piece_on(from) == pawn_of_color(us));
1058 assert(this->color_of_piece_on(to) == them || this->square_is_empty(to));
1060 capture = this->type_of_piece_on(to);
1063 assert(capture != KING);
1065 // Remove captured piece:
1066 clear_bit(&(byColorBB[them]), to);
1067 clear_bit(&(byTypeBB[capture]), to);
1070 key ^= zobrist[them][capture][to];
1072 // Update incremental scores:
1073 mgValue -= this->mg_pst(them, capture, to);
1074 egValue -= this->eg_pst(them, capture, to);
1076 // Update material. Because our move is a promotion, we know that the
1077 // captured piece is not a pawn.
1078 assert(capture != PAWN);
1079 npMaterial[them] -= piece_value_midgame(capture);
1081 // Update material hash key:
1082 materialKey ^= zobMaterial[them][capture][pieceCount[them][capture]];
1084 // Update piece count:
1085 pieceCount[them][capture]--;
1087 // Update piece list:
1088 pieceList[them][capture][index[to]] =
1089 pieceList[them][capture][pieceCount[them][capture]];
1090 index[pieceList[them][capture][index[to]]] = index[to];
1092 // Remember the captured piece, in order to be able to undo the move
1094 u.capture = capture;
1098 clear_bit(&(byColorBB[us]), from);
1099 clear_bit(&(byTypeBB[PAWN]), from);
1100 clear_bit(&(byTypeBB[0]), from); // HACK: byTypeBB[0] == occupied squares
1101 board[from] = EMPTY;
1103 // Insert promoted piece:
1104 promotion = move_promotion(m);
1105 assert(promotion >= KNIGHT && promotion <= QUEEN);
1106 set_bit(&(byColorBB[us]), to);
1107 set_bit(&(byTypeBB[promotion]), to);
1108 set_bit(&(byTypeBB[0]), to); // HACK: byTypeBB[0] == occupied squares
1109 board[to] = piece_of_color_and_type(us, promotion);
1112 key ^= zobrist[us][PAWN][from] ^ zobrist[us][promotion][to];
1114 // Update pawn hash key:
1115 pawnKey ^= zobrist[us][PAWN][from];
1117 // Update material key:
1118 materialKey ^= zobMaterial[us][PAWN][pieceCount[us][PAWN]];
1119 materialKey ^= zobMaterial[us][promotion][pieceCount[us][promotion]+1];
1121 // Update piece counts:
1122 pieceCount[us][PAWN]--;
1123 pieceCount[us][promotion]++;
1125 // Update piece lists:
1126 pieceList[us][PAWN][index[from]] =
1127 pieceList[us][PAWN][pieceCount[us][PAWN]];
1128 index[pieceList[us][PAWN][index[from]]] = index[from];
1129 pieceList[us][promotion][pieceCount[us][promotion] - 1] = to;
1130 index[to] = pieceCount[us][promotion] - 1;
1132 // Update incremental scores:
1133 mgValue -= this->mg_pst(us, PAWN, from);
1134 mgValue += this->mg_pst(us, promotion, to);
1135 egValue -= this->eg_pst(us, PAWN, from);
1136 egValue += this->eg_pst(us, promotion, to);
1139 npMaterial[us] += piece_value_midgame(promotion);
1141 // Clear the en passant square:
1142 if(epSquare != SQ_NONE) {
1143 key ^= zobEp[epSquare];
1147 // Update castle rights:
1148 key ^= zobCastle[castleRights];
1149 castleRights &= castleRightsMask[to];
1150 key ^= zobCastle[castleRights];
1152 // Reset rule 50 counter:
1155 // Update checkers BB:
1156 checkersBB = attacks_to(this->king_square(them), us);
1160 /// Position::do_ep_move() is a private method used to make an en passant
1161 /// capture. It is called from the main Position::do_move function. Because
1162 /// the captured piece is always a pawn, we don't need to pass an UndoInfo
1163 /// object in which to store the captured piece.
1165 void Position::do_ep_move(Move m) {
1167 Square from, to, capsq;
1169 assert(this->is_ok());
1170 assert(move_is_ok(m));
1171 assert(move_is_ep(m));
1173 us = this->side_to_move();
1174 them = opposite_color(us);
1176 // Find from, to and capture squares:
1177 from = move_from(m);
1179 capsq = (us == WHITE)? (to - DELTA_N) : (to - DELTA_S);
1181 assert(to == epSquare);
1182 assert(pawn_rank(us, to) == RANK_6);
1183 assert(this->piece_on(to) == EMPTY);
1184 assert(this->piece_on(from) == pawn_of_color(us));
1185 assert(this->piece_on(capsq) == pawn_of_color(them));
1187 // Remove captured piece:
1188 clear_bit(&(byColorBB[them]), capsq);
1189 clear_bit(&(byTypeBB[PAWN]), capsq);
1190 clear_bit(&(byTypeBB[0]), capsq); // HACK: byTypeBB[0] == occupied squares
1191 board[capsq] = EMPTY;
1193 // Remove moving piece from source square:
1194 clear_bit(&(byColorBB[us]), from);
1195 clear_bit(&(byTypeBB[PAWN]), from);
1196 clear_bit(&(byTypeBB[0]), from); // HACK: byTypeBB[0] == occupied squares
1198 // Put moving piece on destination square:
1199 set_bit(&(byColorBB[us]), to);
1200 set_bit(&(byTypeBB[PAWN]), to);
1201 set_bit(&(byTypeBB[0]), to); // HACK: byTypeBB[0] == occupied squares
1202 board[to] = board[from];
1203 board[from] = EMPTY;
1205 // Update material hash key:
1206 materialKey ^= zobMaterial[them][PAWN][pieceCount[them][PAWN]];
1208 // Update piece count:
1209 pieceCount[them][PAWN]--;
1211 // Update piece list:
1212 pieceList[us][PAWN][index[from]] = to;
1213 index[to] = index[from];
1214 pieceList[them][PAWN][index[capsq]] =
1215 pieceList[them][PAWN][pieceCount[them][PAWN]];
1216 index[pieceList[them][PAWN][index[capsq]]] = index[capsq];
1219 key ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to];
1220 key ^= zobrist[them][PAWN][capsq];
1221 key ^= zobEp[epSquare];
1223 // Update pawn hash key:
1224 pawnKey ^= zobrist[us][PAWN][from] ^ zobrist[us][PAWN][to];
1225 pawnKey ^= zobrist[them][PAWN][capsq];
1227 // Update incremental scores:
1228 mgValue -= this->mg_pst(them, PAWN, capsq);
1229 mgValue -= this->mg_pst(us, PAWN, from);
1230 mgValue += this->mg_pst(us, PAWN, to);
1231 egValue -= this->eg_pst(them, PAWN, capsq);
1232 egValue -= this->eg_pst(us, PAWN, from);
1233 egValue += this->eg_pst(us, PAWN, to);
1235 // Reset en passant square:
1238 // Reset rule 50 counter:
1241 // Update checkers BB:
1242 checkersBB = attacks_to(this->king_square(them), us);
1246 /// Position::undo_move() unmakes a move. When it returns, the position should
1247 /// be restored to exactly the same state as before the move was made. It is
1248 /// important that Position::undo_move is called with the same move and UndoInfo
1249 /// object as the earlier call to Position::do_move.
1251 void Position::undo_move(Move m, const UndoInfo &u) {
1252 assert(this->is_ok());
1253 assert(move_is_ok(m));
1256 sideToMove = opposite_color(sideToMove);
1258 // Restore information from our UndoInfo object (except the captured piece,
1259 // which is taken care of later):
1262 if(move_is_castle(m))
1263 this->undo_castle_move(m);
1264 else if(move_promotion(m))
1265 this->undo_promotion_move(m, u);
1266 else if(move_is_ep(m))
1267 this->undo_ep_move(m);
1271 PieceType piece, capture;
1273 us = this->side_to_move();
1274 them = opposite_color(us);
1276 from = move_from(m);
1279 assert(this->piece_on(from) == EMPTY);
1280 assert(color_of_piece_on(to) == us);
1282 // Put the piece back at the source square:
1283 piece = this->type_of_piece_on(to);
1284 set_bit(&(byColorBB[us]), from);
1285 set_bit(&(byTypeBB[piece]), from);
1286 set_bit(&(byTypeBB[0]), from); // HACK: byTypeBB[0] == occupied squares
1287 board[from] = piece_of_color_and_type(us, piece);
1289 // Clear the destination square
1290 clear_bit(&(byColorBB[us]), to);
1291 clear_bit(&(byTypeBB[piece]), to);
1292 clear_bit(&(byTypeBB[0]), to); // HACK: byTypeBB[0] == occupied squares
1294 // If the moving piece was a king, update the king square:
1296 kingSquare[us] = from;
1298 // Update piece list:
1299 pieceList[us][piece][index[to]] = from;
1300 index[from] = index[to];
1302 capture = u.capture;
1305 assert(capture != KING);
1306 // Replace the captured piece:
1307 set_bit(&(byColorBB[them]), to);
1308 set_bit(&(byTypeBB[capture]), to);
1309 set_bit(&(byTypeBB[0]), to);
1310 board[to] = piece_of_color_and_type(them, capture);
1314 npMaterial[them] += piece_value_midgame(capture);
1316 // Update piece list:
1317 pieceList[them][capture][pieceCount[them][capture]] = to;
1318 index[to] = pieceCount[them][capture];
1320 // Update piece count:
1321 pieceCount[them][capture]++;
1327 assert(this->is_ok());
1331 /// Position::undo_castle_move() is a private method used to unmake a castling
1332 /// move. It is called from the main Position::undo_move function. Note that
1333 /// castling moves are encoded as "king captures friendly rook" moves, for
1334 /// instance white short castling in a non-Chess960 game is encoded as e1h1.
1336 void Position::undo_castle_move(Move m) {
1338 Square kfrom, kto, rfrom, rto;
1340 assert(move_is_ok(m));
1341 assert(move_is_castle(m));
1343 // When we have arrived here, some work has already been done by
1344 // Position::undo_move. In particular, the side to move has been switched,
1345 // so the code below is correct.
1346 us = this->side_to_move();
1347 them = opposite_color(us);
1349 // Find source squares for king and rook:
1350 kfrom = move_from(m);
1351 rfrom = move_to(m); // HACK: See comment at beginning of function.
1353 // Find destination squares for king and rook:
1354 if(rfrom > kfrom) { // O-O
1355 kto = relative_square(us, SQ_G1);
1356 rto = relative_square(us, SQ_F1);
1359 kto = relative_square(us, SQ_C1);
1360 rto = relative_square(us, SQ_D1);
1363 assert(this->piece_on(kto) == king_of_color(us));
1364 assert(this->piece_on(rto) == rook_of_color(us));
1366 // Remove pieces from destination squares:
1367 clear_bit(&(byColorBB[us]), kto);
1368 clear_bit(&(byTypeBB[KING]), kto);
1369 clear_bit(&(byTypeBB[0]), kto); // HACK: byTypeBB[0] == occupied squares
1370 clear_bit(&(byColorBB[us]), rto);
1371 clear_bit(&(byTypeBB[ROOK]), rto);
1372 clear_bit(&(byTypeBB[0]), rto); // HACK: byTypeBB[0] == occupied squares
1374 // Put pieces on source squares:
1375 set_bit(&(byColorBB[us]), kfrom);
1376 set_bit(&(byTypeBB[KING]), kfrom);
1377 set_bit(&(byTypeBB[0]), kfrom); // HACK: byTypeBB[0] == occupied squares
1378 set_bit(&(byColorBB[us]), rfrom);
1379 set_bit(&(byTypeBB[ROOK]), rfrom);
1380 set_bit(&(byTypeBB[0]), rfrom); // HACK: byTypeBB[0] == occupied squares
1383 board[rto] = board[kto] = EMPTY;
1384 board[rfrom] = rook_of_color(us);
1385 board[kfrom] = king_of_color(us);
1387 // Update king square:
1388 kingSquare[us] = kfrom;
1390 // Update piece lists:
1391 pieceList[us][KING][index[kto]] = kfrom;
1392 pieceList[us][ROOK][index[rto]] = rfrom;
1393 int tmp = index[rto]; // Necessary because we may have rto == kfrom in FRC.
1394 index[kfrom] = index[kto];
1399 /// Position::undo_promotion_move() is a private method used to unmake a
1400 /// promotion move. It is called from the main Position::do_move
1401 /// function. The UndoInfo object, which has been initialized in
1402 /// Position::do_move, is used to put back the captured piece (if any).
1404 void Position::undo_promotion_move(Move m, const UndoInfo &u) {
1407 PieceType capture, promotion;
1409 assert(move_is_ok(m));
1410 assert(move_promotion(m));
1412 // When we have arrived here, some work has already been done by
1413 // Position::undo_move. In particular, the side to move has been switched,
1414 // so the code below is correct.
1415 us = this->side_to_move();
1416 them = opposite_color(us);
1418 from = move_from(m);
1421 assert(pawn_rank(us, to) == RANK_8);
1422 assert(this->piece_on(from) == EMPTY);
1424 // Remove promoted piece:
1425 promotion = move_promotion(m);
1426 assert(this->piece_on(to)==piece_of_color_and_type(us, promotion));
1427 assert(promotion >= KNIGHT && promotion <= QUEEN);
1428 clear_bit(&(byColorBB[us]), to);
1429 clear_bit(&(byTypeBB[promotion]), to);
1430 clear_bit(&(byTypeBB[0]), to); // HACK: byTypeBB[0] == occupied squares
1432 // Insert pawn at source square:
1433 set_bit(&(byColorBB[us]), from);
1434 set_bit(&(byTypeBB[PAWN]), from);
1435 set_bit(&(byTypeBB[0]), from); // HACK: byTypeBB[0] == occupied squares
1436 board[from] = pawn_of_color(us);
1439 npMaterial[us] -= piece_value_midgame(promotion);
1441 // Update piece list:
1442 pieceList[us][PAWN][pieceCount[us][PAWN]] = from;
1443 index[from] = pieceCount[us][PAWN];
1444 pieceList[us][promotion][index[to]] =
1445 pieceList[us][promotion][pieceCount[us][promotion] - 1];
1446 index[pieceList[us][promotion][index[to]]] = index[to];
1448 // Update piece counts:
1449 pieceCount[us][promotion]--;
1450 pieceCount[us][PAWN]++;
1452 capture = u.capture;
1454 assert(capture != KING);
1456 // Insert captured piece:
1457 set_bit(&(byColorBB[them]), to);
1458 set_bit(&(byTypeBB[capture]), to);
1459 set_bit(&(byTypeBB[0]), to); // HACK: byTypeBB[0] == occupied squares
1460 board[to] = piece_of_color_and_type(them, capture);
1462 // Update material. Because the move is a promotion move, we know
1463 // that the captured piece cannot be a pawn.
1464 assert(capture != PAWN);
1465 npMaterial[them] += piece_value_midgame(capture);
1467 // Update piece list:
1468 pieceList[them][capture][pieceCount[them][capture]] = to;
1469 index[to] = pieceCount[them][capture];
1471 // Update piece count:
1472 pieceCount[them][capture]++;
1479 /// Position::undo_ep_move() is a private method used to unmake an en passant
1480 /// capture. It is called from the main Position::undo_move function. Because
1481 /// the captured piece is always a pawn, we don't need to pass an UndoInfo
1482 /// object from which to retrieve the captured piece.
1484 void Position::undo_ep_move(Move m) {
1486 Square from, to, capsq;
1488 assert(move_is_ok(m));
1489 assert(move_is_ep(m));
1491 // When we have arrived here, some work has already been done by
1492 // Position::undo_move. In particular, the side to move has been switched,
1493 // so the code below is correct.
1494 us = this->side_to_move();
1495 them = opposite_color(us);
1497 // Find from, to and captures squares:
1498 from = move_from(m);
1500 capsq = (us == WHITE)? (to - DELTA_N) : (to - DELTA_S);
1502 assert(to == this->ep_square());
1503 assert(pawn_rank(us, to) == RANK_6);
1504 assert(this->piece_on(to) == pawn_of_color(us));
1505 assert(this->piece_on(from) == EMPTY);
1506 assert(this->piece_on(capsq) == EMPTY);
1508 // Replace captured piece:
1509 set_bit(&(byColorBB[them]), capsq);
1510 set_bit(&(byTypeBB[PAWN]), capsq);
1511 set_bit(&(byTypeBB[0]), capsq);
1512 board[capsq] = pawn_of_color(them);
1514 // Remove moving piece from destination square:
1515 clear_bit(&(byColorBB[us]), to);
1516 clear_bit(&(byTypeBB[PAWN]), to);
1517 clear_bit(&(byTypeBB[0]), to);
1520 // Replace moving piece at source square:
1521 set_bit(&(byColorBB[us]), from);
1522 set_bit(&(byTypeBB[PAWN]), from);
1523 set_bit(&(byTypeBB[0]), from);
1524 board[from] = pawn_of_color(us);
1526 // Update piece list:
1527 pieceList[us][PAWN][index[to]] = from;
1528 index[from] = index[to];
1529 pieceList[them][PAWN][pieceCount[them][PAWN]] = capsq;
1530 index[capsq] = pieceCount[them][PAWN];
1532 // Update piece count:
1533 pieceCount[them][PAWN]++;
1537 /// Position::do_null_move makes() a "null move": It switches the side to move
1538 /// and updates the hash key without executing any move on the board.
1540 void Position::do_null_move(UndoInfo &u) {
1541 assert(this->is_ok());
1542 assert(!this->is_check());
1544 // Back up the information necessary to undo the null move to the supplied
1545 // UndoInfo object. In the case of a null move, the only thing we need to
1546 // remember is the last move made and the en passant square.
1547 u.lastMove = lastMove;
1548 u.epSquare = epSquare;
1550 // Save the current key to the history[] array, in order to be able to
1551 // detect repetition draws:
1552 history[gamePly] = key;
1554 // Update the necessary information.
1555 sideToMove = opposite_color(sideToMove);
1556 if(epSquare != SQ_NONE)
1557 key ^= zobEp[epSquare];
1561 key ^= zobSideToMove;
1563 mgValue += (sideToMove == WHITE)? TempoValueMidgame : -TempoValueMidgame;
1564 egValue += (sideToMove == WHITE)? TempoValueEndgame : -TempoValueEndgame;
1566 assert(this->is_ok());
1570 /// Position::undo_null_move() unmakes a "null move".
1572 void Position::undo_null_move(const UndoInfo &u) {
1573 assert(this->is_ok());
1574 assert(!this->is_check());
1576 // Restore information from the supplied UndoInfo object:
1577 lastMove = u.lastMove;
1578 epSquare = u.epSquare;
1579 if(epSquare != SQ_NONE)
1580 key ^= zobEp[epSquare];
1582 // Update the necessary information.
1583 sideToMove = opposite_color(sideToMove);
1586 key ^= zobSideToMove;
1588 mgValue += (sideToMove == WHITE)? TempoValueMidgame : -TempoValueMidgame;
1589 egValue += (sideToMove == WHITE)? TempoValueEndgame : -TempoValueEndgame;
1591 assert(this->is_ok());
1595 /// Position::see() is a static exchange evaluator: It tries to estimate the
1596 /// material gain or loss resulting from a move. There are two versions of
1597 /// this function: One which takes a move as input, and one which takes a
1598 /// 'from' and a 'to' square. The function does not yet understand promotions
1599 /// or en passant captures.
1601 int Position::see(Square from, Square to) const {
1602 // Approximate material values, with pawn = 1:
1603 static const int seeValues[18] = {
1604 0, 1, 3, 3, 5, 10, 100, 0, 0, 1, 3, 3, 5, 10, 100, 0, 0, 0
1607 Piece piece, capture;
1608 Bitboard attackers, occ, b;
1610 assert(square_is_ok(from));
1611 assert(square_is_ok(to));
1613 // Initialize colors:
1614 us = this->color_of_piece_on(from);
1615 them = opposite_color(us);
1617 // Initialize pieces:
1618 piece = this->piece_on(from);
1619 capture = this->piece_on(to);
1621 // Find all attackers to the destination square, with the moving piece
1622 // removed, but possibly an X-ray attacker added behind it:
1623 occ = this->occupied_squares();
1624 clear_bit(&occ, from);
1626 (rook_attacks_bb(to, occ) & this->rooks_and_queens()) |
1627 (bishop_attacks_bb(to, occ) & this->bishops_and_queens()) |
1628 (this->knight_attacks(to) & this->knights()) |
1629 (this->king_attacks(to) & this->kings()) |
1630 (this->white_pawn_attacks(to) & this->pawns(BLACK)) |
1631 (this->black_pawn_attacks(to) & this->pawns(WHITE));
1634 // If the opponent has no attackers, we are finished:
1635 if((attackers & this->pieces_of_color(them)) == EmptyBoardBB)
1636 return seeValues[capture];
1638 // The destination square is defended, which makes things rather more
1639 // difficult to compute. We proceed by building up a "swap list" containing
1640 // the material gain or loss at each stop in a sequence of captures to the
1641 // destianation square, where the sides alternately capture, and always
1642 // capture with the least valuable piece. After each capture, we look for
1643 // new X-ray attacks from behind the capturing piece.
1644 int lastCapturingPieceValue = seeValues[piece];
1645 int swapList[32], n = 1;
1649 swapList[0] = seeValues[capture];
1652 // Locate the least valuable attacker for the side to move. The loop
1653 // below looks like it is potentially infinite, but it isn't. We know
1654 // that the side to move still has at least one attacker left.
1655 for(pt = PAWN; !(attackers&this->pieces_of_color_and_type(c, pt)); pt++)
1658 // Remove the attacker we just found from the 'attackers' bitboard,
1659 // and scan for new X-ray attacks behind the attacker:
1660 b = attackers & this->pieces_of_color_and_type(c, pt);
1663 (rook_attacks_bb(to, occ) & this->rooks_and_queens()) |
1664 (bishop_attacks_bb(to, occ) & this->bishops_and_queens());
1667 // Add the new entry to the swap list:
1669 swapList[n] = -swapList[n - 1] + lastCapturingPieceValue;
1672 // Remember the value of the capturing piece, and change the side to move
1673 // before beginning the next iteration:
1674 lastCapturingPieceValue = seeValues[pt];
1675 c = opposite_color(c);
1677 // Stop after a king capture:
1678 if(pt == KING && (attackers & this->pieces_of_color(c))) {
1680 swapList[n++] = 100;
1683 } while(attackers & this->pieces_of_color(c));
1685 // Having built the swap list, we negamax through it to find the best
1686 // achievable score from the point of view of the side to move:
1687 while(--n) swapList[n-1] = Min(-swapList[n], swapList[n-1]);
1693 int Position::see(Move m) const {
1694 assert(move_is_ok(m));
1695 return this->see(move_from(m), move_to(m));
1699 /// Position::clear() erases the position object to a pristine state, with an
1700 /// empty board, white to move, and no castling rights.
1702 void Position::clear() {
1705 for(i = 0; i < 64; i++) {
1710 for(i = 0; i < 2; i++)
1711 byColorBB[i] = EmptyBoardBB;
1713 for(i = 0; i < 7; i++) {
1714 byTypeBB[i] = EmptyBoardBB;
1715 pieceCount[0][i] = pieceCount[1][i] = 0;
1716 for(j = 0; j < 8; j++)
1717 pieceList[0][i][j] = pieceList[1][i][j] = SQ_NONE;
1720 checkersBB = EmptyBoardBB;
1722 lastMove = MOVE_NONE;
1725 castleRights = NO_CASTLES;
1726 initialKFile = FILE_E;
1727 initialKRFile = FILE_H;
1728 initialQRFile = FILE_A;
1735 /// Position::reset_game_ply() simply sets gamePly to 0. It is used from the
1736 /// UCI interface code, whenever a non-reversible move is made in a
1737 /// 'position fen <fen> moves m1 m2 ...' command. This makes it possible
1738 /// for the program to handle games of arbitrary length, as long as the GUI
1739 /// handles draws by the 50 move rule correctly.
1741 void Position::reset_game_ply() {
1746 /// Position::put_piece() puts a piece on the given square of the board,
1747 /// updating the board array, bitboards, and piece counts.
1749 void Position::put_piece(Piece p, Square s) {
1750 Color c = color_of_piece(p);
1751 PieceType pt = type_of_piece(p);
1754 index[s] = pieceCount[c][pt];
1755 pieceList[c][pt][index[s]] = s;
1757 set_bit(&(byTypeBB[pt]), s);
1758 set_bit(&(byColorBB[c]), s);
1759 set_bit(&byTypeBB[0], s); // HACK: byTypeBB[0] contains all occupied squares.
1761 pieceCount[c][pt]++;
1768 /// Position::allow_oo() gives the given side the right to castle kingside.
1769 /// Used when setting castling rights during parsing of FEN strings.
1771 void Position::allow_oo(Color c) {
1772 castleRights |= (1 + int(c));
1776 /// Position::allow_ooo() gives the given side the right to castle queenside.
1777 /// Used when setting castling rights during parsing of FEN strings.
1779 void Position::allow_ooo(Color c) {
1780 castleRights |= (4 + 4*int(c));
1784 /// Position::compute_key() computes the hash key of the position. The hash
1785 /// key is usually updated incrementally as moves are made and unmade, the
1786 /// compute_key() function is only used when a new position is set up, and
1787 /// to verify the correctness of the hash key when running in debug mode.
1789 Key Position::compute_key() const {
1790 Key result = Key(0ULL);
1792 for(Square s = SQ_A1; s <= SQ_H8; s++)
1793 if(this->square_is_occupied(s))
1795 zobrist[this->color_of_piece_on(s)][this->type_of_piece_on(s)][s];
1797 if(this->ep_square() != SQ_NONE)
1798 result ^= zobEp[this->ep_square()];
1799 result ^= zobCastle[castleRights];
1800 if(this->side_to_move() == BLACK) result ^= zobSideToMove;
1806 /// Position::compute_pawn_key() computes the hash key of the position. The
1807 /// hash key is usually updated incrementally as moves are made and unmade,
1808 /// the compute_pawn_key() function is only used when a new position is set
1809 /// up, and to verify the correctness of the pawn hash key when running in
1812 Key Position::compute_pawn_key() const {
1813 Key result = Key(0ULL);
1817 for(Color c = WHITE; c <= BLACK; c++) {
1820 s = pop_1st_bit(&b);
1821 result ^= zobrist[c][PAWN][s];
1828 /// Position::compute_material_key() computes the hash key of the position.
1829 /// The hash key is usually updated incrementally as moves are made and unmade,
1830 /// the compute_material_key() function is only used when a new position is set
1831 /// up, and to verify the correctness of the material hash key when running in
1834 Key Position::compute_material_key() const {
1835 Key result = Key(0ULL);
1836 for(Color c = WHITE; c <= BLACK; c++)
1837 for(PieceType pt = PAWN; pt <= QUEEN; pt++) {
1838 int count = this->piece_count(c, pt);
1839 for(int i = 0; i <= count; i++)
1840 result ^= zobMaterial[c][pt][i];
1846 /// Position::compute_mg_value() and Position::compute_eg_value() compute the
1847 /// incremental scores for the middle game and the endgame. These functions
1848 /// are used to initialize the incremental scores when a new position is set
1849 /// up, and to verify that the scores are correctly updated by do_move
1850 /// and undo_move when the program is running in debug mode.
1852 Value Position::compute_mg_value() const {
1853 Value result = Value(0);
1857 for(Color c = WHITE; c <= BLACK; c++)
1858 for(PieceType pt = PAWN; pt <= KING; pt++) {
1859 b = this->pieces_of_color_and_type(c, pt);
1861 s = pop_1st_bit(&b);
1862 assert(this->piece_on(s) == piece_of_color_and_type(c, pt));
1863 result += this->mg_pst(c, pt, s);
1866 result += (this->side_to_move() == WHITE)?
1867 (TempoValueMidgame / 2) : -(TempoValueMidgame / 2);
1871 Value Position::compute_eg_value() const {
1872 Value result = Value(0);
1876 for(Color c = WHITE; c <= BLACK; c++)
1877 for(PieceType pt = PAWN; pt <= KING; pt++) {
1878 b = this->pieces_of_color_and_type(c, pt);
1880 s = pop_1st_bit(&b);
1881 assert(this->piece_on(s) == piece_of_color_and_type(c, pt));
1882 result += this->eg_pst(c, pt, s);
1885 result += (this->side_to_move() == WHITE)?
1886 (TempoValueEndgame / 2) : -(TempoValueEndgame / 2);
1891 /// Position::compute_non_pawn_material() computes the total non-pawn middle
1892 /// game material score for the given side. Material scores are updated
1893 /// incrementally during the search, this function is only used while
1894 /// initializing a new Position object.
1896 Value Position::compute_non_pawn_material(Color c) const {
1897 Value result = Value(0);
1900 for(PieceType pt = KNIGHT; pt <= QUEEN; pt++) {
1901 Bitboard b = this->pieces_of_color_and_type(c, pt);
1903 s = pop_1st_bit(&b);
1904 assert(this->piece_on(s) == piece_of_color_and_type(c, pt));
1905 result += piece_value_midgame(pt);
1912 /// Position::is_mate() returns true or false depending on whether the
1913 /// side to move is checkmated. Note that this function is currently very
1914 /// slow, and shouldn't be used frequently inside the search.
1916 bool Position::is_mate() {
1917 if(this->is_check()) {
1918 MovePicker mp = MovePicker(*this, false, MOVE_NONE, MOVE_NONE, MOVE_NONE,
1919 MOVE_NONE, Depth(0));
1920 return mp.get_next_move() == MOVE_NONE;
1927 /// Position::is_draw() tests whether the position is drawn by material,
1928 /// repetition, or the 50 moves rule. It does not detect stalemates, this
1929 /// must be done by the search.
1931 bool Position::is_draw() const {
1932 // Draw by material?
1933 if(!this->pawns() &&
1934 this->non_pawn_material(WHITE) + this->non_pawn_material(BLACK)
1935 <= BishopValueMidgame)
1938 // Draw by the 50 moves rule?
1939 if(rule50 > 100 || (rule50 == 100 && !this->is_check()))
1942 // Draw by repetition?
1943 for(int i = 2; i < Min(gamePly, rule50); i += 2)
1944 if(history[gamePly - i] == key)
1951 /// Position::has_mate_threat() tests whether a given color has a mate in one
1952 /// from the current position. This function is quite slow, but it doesn't
1953 /// matter, because it is currently only called from PV nodes, which are rare.
1955 bool Position::has_mate_threat(Color c) {
1957 Color stm = this->side_to_move();
1959 // The following lines are useless and silly, but prevents gcc from
1960 // emitting a stupid warning stating that u1.lastMove and u1.epSquare might
1961 // be used uninitialized.
1962 u1.lastMove = lastMove;
1963 u1.epSquare = epSquare;
1965 if(this->is_check())
1968 // If the input color is not equal to the side to move, do a null move
1969 if(c != stm) this->do_null_move(u1);
1971 MoveStack mlist[120];
1973 bool result = false;
1975 // Generate legal moves
1976 count = generate_legal_moves(*this, mlist);
1978 // Loop through the moves, and see if one of them is mate.
1979 for(int i = 0; i < count; i++) {
1980 this->do_move(mlist[i].move, u2);
1981 if(this->is_mate()) result = true;
1982 this->undo_move(mlist[i].move, u2);
1985 // Undo null move, if necessary
1986 if(c != stm) this->undo_null_move(u1);
1992 /// Position::init_zobrist() is a static member function which initializes the
1993 /// various arrays used to compute hash keys.
1995 void Position::init_zobrist() {
1997 for(int i = 0; i < 2; i++)
1998 for(int j = 0; j < 8; j++)
1999 for(int k = 0; k < 64; k++)
2000 zobrist[i][j][k] = Key(genrand_int64());
2002 for(int i = 0; i < 64; i++)
2003 zobEp[i] = Key(genrand_int64());
2005 for(int i = 0; i < 16; i++)
2006 zobCastle[i] = genrand_int64();
2008 zobSideToMove = genrand_int64();
2010 for(int i = 0; i < 2; i++)
2011 for(int j = 0; j < 8; j++)
2012 for(int k = 0; k < 16; k++)
2013 zobMaterial[i][j][k] = (k > 0)? Key(genrand_int64()) : Key(0LL);
2015 for(int i = 0; i < 16; i++)
2016 zobMaterial[0][KING][i] = zobMaterial[1][KING][i] = Key(0ULL);
2020 /// Position::init_piece_square_tables() initializes the piece square tables.
2021 /// This is a two-step operation: First, the white halves of the tables are
2022 /// copied from the MgPST[][] and EgPST[][] arrays, with a small random number
2023 /// added to each entry if the "Randomness" UCI parameter is non-zero.
2024 /// Second, the black halves of the tables are initialized by mirroring
2025 /// and changing the sign of the corresponding white scores.
2027 void Position::init_piece_square_tables() {
2028 int r = get_option_value_int("Randomness"), i;
2029 for(Square s = SQ_A1; s <= SQ_H8; s++) {
2030 for(Piece p = WP; p <= WK; p++) {
2031 i = (r == 0)? 0 : (genrand_int32() % (r*2) - r);
2032 MgPieceSquareTable[p][s] = Value(MgPST[p][s] + i);
2033 EgPieceSquareTable[p][s] = Value(EgPST[p][s] + i);
2036 for(Square s = SQ_A1; s <= SQ_H8; s++)
2037 for(Piece p = BP; p <= BK; p++) {
2038 MgPieceSquareTable[p][s] = -MgPieceSquareTable[p-8][flip_square(s)];
2039 EgPieceSquareTable[p][s] = -EgPieceSquareTable[p-8][flip_square(s)];
2044 /// Position::flipped_copy() makes a copy of the input position, but with
2045 /// the white and black sides reversed. This is only useful for debugging,
2046 /// especially for finding evaluation symmetry bugs.
2048 void Position::flipped_copy(const Position &pos) {
2049 assert(pos.is_ok());
2054 for(Square s = SQ_A1; s <= SQ_H8; s++)
2055 if(!pos.square_is_empty(s))
2056 this->put_piece(Piece(int(pos.piece_on(s)) ^ 8), flip_square(s));
2059 sideToMove = opposite_color(pos.side_to_move());
2062 if(pos.can_castle_kingside(WHITE)) this->allow_oo(BLACK);
2063 if(pos.can_castle_queenside(WHITE)) this->allow_ooo(BLACK);
2064 if(pos.can_castle_kingside(BLACK)) this->allow_oo(WHITE);
2065 if(pos.can_castle_queenside(BLACK)) this->allow_ooo(WHITE);
2067 initialKFile = pos.initialKFile;
2068 initialKRFile = pos.initialKRFile;
2069 initialQRFile = pos.initialQRFile;
2071 for(Square sq = SQ_A1; sq <= SQ_H8; sq++)
2072 castleRightsMask[sq] = ALL_CASTLES;
2073 castleRightsMask[make_square(initialKFile, RANK_1)] ^= (WHITE_OO|WHITE_OOO);
2074 castleRightsMask[make_square(initialKFile, RANK_8)] ^= (BLACK_OO|BLACK_OOO);
2075 castleRightsMask[make_square(initialKRFile, RANK_1)] ^= WHITE_OO;
2076 castleRightsMask[make_square(initialKRFile, RANK_8)] ^= BLACK_OO;
2077 castleRightsMask[make_square(initialQRFile, RANK_1)] ^= WHITE_OOO;
2078 castleRightsMask[make_square(initialQRFile, RANK_8)] ^= BLACK_OOO;
2080 // En passant square
2081 if(pos.epSquare != SQ_NONE)
2082 epSquare = flip_square(pos.epSquare);
2085 this->find_checkers();
2088 key = this->compute_key();
2089 pawnKey = this->compute_pawn_key();
2090 materialKey = this->compute_material_key();
2092 // Incremental scores
2093 mgValue = this->compute_mg_value();
2094 egValue = this->compute_eg_value();
2097 npMaterial[WHITE] = this->compute_non_pawn_material(WHITE);
2098 npMaterial[BLACK] = this->compute_non_pawn_material(BLACK);
2100 assert(this->is_ok());
2104 /// Position::is_ok() performs some consitency checks for the position object.
2105 /// This is meant to be helpful when debugging.
2107 bool Position::is_ok() const {
2109 // What features of the position should be verified?
2110 static const bool debugBitboards = false;
2111 static const bool debugKingCount = false;
2112 static const bool debugKingCapture = false;
2113 static const bool debugCheckerCount = false;
2114 static const bool debugKey = false;
2115 static const bool debugMaterialKey = false;
2116 static const bool debugPawnKey = false;
2117 static const bool debugIncrementalEval = false;
2118 static const bool debugNonPawnMaterial = false;
2119 static const bool debugPieceCounts = false;
2120 static const bool debugPieceList = false;
2123 if(!color_is_ok(this->side_to_move()))
2126 // Are the king squares in the position correct?
2127 if(this->piece_on(this->king_square(WHITE)) != WK)
2129 if(this->piece_on(this->king_square(BLACK)) != BK)
2133 if(!file_is_ok(initialKRFile))
2135 if(!file_is_ok(initialQRFile))
2138 // Do both sides have exactly one king?
2139 if(debugKingCount) {
2140 int kingCount[2] = {0, 0};
2141 for(Square s = SQ_A1; s <= SQ_H8; s++)
2142 if(this->type_of_piece_on(s) == KING)
2143 kingCount[this->color_of_piece_on(s)]++;
2144 if(kingCount[0] != 1 || kingCount[1] != 1)
2148 // Can the side to move capture the opponent's king?
2149 if(debugKingCapture) {
2150 Color us = this->side_to_move();
2151 Color them = opposite_color(us);
2152 Square ksq = this->king_square(them);
2153 if(this->square_is_attacked(ksq, us))
2157 // Is there more than 2 checkers?
2158 if(debugCheckerCount && count_1s(checkersBB) > 2)
2162 if(debugBitboards) {
2163 // The intersection of the white and black pieces must be empty:
2164 if((this->pieces_of_color(WHITE) & this->pieces_of_color(BLACK))
2168 // The union of the white and black pieces must be equal to all
2169 // occupied squares:
2170 if((this->pieces_of_color(WHITE) | this->pieces_of_color(BLACK))
2171 != this->occupied_squares())
2174 // Separate piece type bitboards must have empty intersections:
2175 for(PieceType p1 = PAWN; p1 <= KING; p1++)
2176 for(PieceType p2 = PAWN; p2 <= KING; p2++)
2177 if(p1 != p2 && (this->pieces_of_type(p1) & this->pieces_of_type(p2)))
2181 // En passant square OK?
2182 if(this->ep_square() != SQ_NONE) {
2183 // The en passant square must be on rank 6, from the point of view of the
2185 if(pawn_rank(this->side_to_move(), this->ep_square()) != RANK_6)
2190 if(debugKey && key != this->compute_key())
2193 // Pawn hash key OK?
2194 if(debugPawnKey && pawnKey != this->compute_pawn_key())
2197 // Material hash key OK?
2198 if(debugMaterialKey && materialKey != this->compute_material_key())
2201 // Incremental eval OK?
2202 if(debugIncrementalEval) {
2203 if(mgValue != this->compute_mg_value())
2205 if(egValue != this->compute_eg_value())
2209 // Non-pawn material OK?
2210 if(debugNonPawnMaterial) {
2211 if(npMaterial[WHITE] != compute_non_pawn_material(WHITE))
2213 if(npMaterial[BLACK] != compute_non_pawn_material(BLACK))
2218 if(debugPieceCounts)
2219 for(Color c = WHITE; c <= BLACK; c++)
2220 for(PieceType pt = PAWN; pt <= KING; pt++)
2221 if(pieceCount[c][pt] != count_1s(this->pieces_of_color_and_type(c, pt)))
2224 if(debugPieceList) {
2225 for(Color c = WHITE; c <= BLACK; c++)
2226 for(PieceType pt = PAWN; pt <= KING; pt++)
2227 for(int i = 0; i < pieceCount[c][pt]; i++) {
2228 if(this->piece_on(this->piece_list(c, pt, i)) !=
2229 piece_of_color_and_type(c, pt))
2231 if(index[this->piece_list(c, pt, i)] != i)