X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovegen.cpp;h=23f6c1bc90f9abd9ec6512890946f0ac1651dfda;hp=aa9f26f1311b05a1aa6205f2d253dfa027a0cbbb;hb=53c2bf069752d9d15d1678d79b0490b33ef240b4;hpb=20cac227bbc2080b3bd3a470f402c260ee827051 diff --git a/src/movegen.cpp b/src/movegen.cpp index aa9f26f1..23f6c1bc 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -52,45 +52,15 @@ namespace { EVASION }; - // Functions - bool castling_is_check(const Position&, CastlingSide); - // Helper templates template MoveStack* generate_castle_moves(const Position&, MoveStack*); - template - MoveStack* generate_pawn_captures_diagonal(MoveStack*, Bitboard, Bitboard, bool); - template MoveStack* generate_pawn_moves(const Position&, MoveStack*, Bitboard = EmptyBoardBB, Square = SQ_NONE, Bitboard = EmptyBoardBB); - template - inline Bitboard move_pawns(Bitboard p) { - - if (Direction == DELTA_N) - return Us == WHITE ? p << 8 : p >> 8; - else if (Direction == DELTA_NE) - return Us == WHITE ? p << 9 : p >> 7; - else if (Direction == DELTA_NW) - return Us == WHITE ? p << 7 : p >> 9; - else - return p; - } - - // Template generate_piece_checks() with specializations - template - MoveStack* generate_piece_checks(const Position&, MoveStack*, Color, Bitboard, Square); - - template<> - inline MoveStack* generate_piece_checks(const Position& p, MoveStack* m, Color us, Bitboard dc, Square ksq) { - - return (us == WHITE ? generate_pawn_moves(p, m, dc, ksq) - : generate_pawn_moves(p, m, dc, ksq)); - } - - // Template generate_piece_moves() with specializations and overloads + // Template generate_piece_moves (captures and non-captures) with specializations and overloads template MoveStack* generate_piece_moves(const Position&, MoveStack*, Color, Bitboard); @@ -107,12 +77,28 @@ namespace { : generate_pawn_moves(p, m)); } + // Templates for non-capture checks generation + + template + MoveStack* generate_discovered_checks(const Position& pos, Square from, MoveStack* mlist); + + template + MoveStack* generate_direct_checks(const Position&, MoveStack*, Color, Bitboard, Square); + + template<> + inline MoveStack* generate_direct_checks(const Position& p, MoveStack* m, Color us, Bitboard dc, Square ksq) { + + return (us == WHITE ? generate_pawn_moves(p, m, dc, ksq) + : generate_pawn_moves(p, m, dc, ksq)); + } + + // Template generate_piece_evasions with specializations template - MoveStack* generate_piece_moves(const Position&, MoveStack*, Color, Bitboard, Bitboard); + MoveStack* generate_piece_evasions(const Position&, MoveStack*, Color, Bitboard, Bitboard); template<> - inline MoveStack* generate_piece_moves(const Position& p, MoveStack* m, - Color us, Bitboard t, Bitboard pnd) { + inline MoveStack* generate_piece_evasions(const Position& p, MoveStack* m, + Color us, Bitboard t, Bitboard pnd) { return (us == WHITE ? generate_pawn_moves(p, m, pnd, SQ_NONE, t) : generate_pawn_moves(p, m, pnd, SQ_NONE, t)); @@ -180,26 +166,28 @@ MoveStack* generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bi assert(pos.piece_on(ksq) == piece_of_color_and_type(opposite_color(us), KING)); - // Pieces moves - mlist = generate_piece_checks(pos, mlist, us, dc, ksq); - mlist = generate_piece_checks(pos, mlist, us, dc, ksq); - mlist = generate_piece_checks(pos, mlist, us, dc, ksq); - mlist = generate_piece_checks(pos, mlist, us, dc, ksq); - mlist = generate_piece_checks(pos, mlist, us, dc, ksq); - mlist = generate_piece_checks(pos, mlist, us, dc, ksq); - - // Castling moves that give check. Very rare but nice to have! - if ( pos.can_castle_queenside(us) - && (square_rank(ksq) == square_rank(pos.king_square(us)) || square_file(ksq) == FILE_D) - && castling_is_check(pos, QUEEN_SIDE)) - mlist = generate_castle_moves(pos, mlist); - - if ( pos.can_castle_kingside(us) - && (square_rank(ksq) == square_rank(pos.king_square(us)) || square_file(ksq) == FILE_F) - && castling_is_check(pos, KING_SIDE)) - mlist = generate_castle_moves(pos, mlist); + // Discovered non-capture checks + Bitboard b = dc; + while (b) + { + Square from = pop_1st_bit(&b); + switch (pos.type_of_piece_on(from)) + { + case PAWN: /* Will be generated togheter with pawns direct checks */ break; + case KNIGHT: mlist = generate_discovered_checks(pos, from, mlist); break; + case BISHOP: mlist = generate_discovered_checks(pos, from, mlist); break; + case ROOK: mlist = generate_discovered_checks(pos, from, mlist); break; + case KING: mlist = generate_discovered_checks(pos, from, mlist); break; + default: assert(false); break; + } + } - return mlist; + // Direct non-capture checks + mlist = generate_direct_checks(pos, mlist, us, dc, ksq); + mlist = generate_direct_checks(pos, mlist, us, dc, ksq); + mlist = generate_direct_checks(pos, mlist, us, dc, ksq); + mlist = generate_direct_checks(pos, mlist, us, dc, ksq); + return generate_direct_checks(pos, mlist, us, dc, ksq); } @@ -258,81 +246,65 @@ MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pin // Generate evasions for other pieces only if not double check. We use a // simple bit twiddling hack here rather than calling count_1s in order to // save some time (we know that pos.checkers() has at most two nonzero bits). - if (!(checkers & (checkers - 1))) // Only one bit set? - { - Square checksq = first_1(checkers); + if (checkers & (checkers - 1)) // Two bits set? + return mlist; - assert(pos.color_of_piece_on(checksq) == them); + Square checksq = first_1(checkers); + Bitboard target = squares_between(checksq, ksq); - // Generate captures of the checking piece + assert(pos.color_of_piece_on(checksq) == them); - // Pawn captures - b1 = pos.attacks_from(checksq, them) & pos.pieces(PAWN, us) & ~pinned; - while (b1) + // Pawn captures + b1 = pos.attacks_from(checksq, them) & pos.pieces(PAWN, us) & ~pinned; + while (b1) + { + from = pop_1st_bit(&b1); + if (relative_rank(us, checksq) == RANK_8) { - from = pop_1st_bit(&b1); - if (relative_rank(us, checksq) == RANK_8) - { - (*mlist++).move = make_promotion_move(from, checksq, QUEEN); - (*mlist++).move = make_promotion_move(from, checksq, ROOK); - (*mlist++).move = make_promotion_move(from, checksq, BISHOP); - (*mlist++).move = make_promotion_move(from, checksq, KNIGHT); - } else - (*mlist++).move = make_move(from, checksq); - } + (*mlist++).move = make_promotion_move(from, checksq, QUEEN); + (*mlist++).move = make_promotion_move(from, checksq, ROOK); + (*mlist++).move = make_promotion_move(from, checksq, BISHOP); + (*mlist++).move = make_promotion_move(from, checksq, KNIGHT); + } else + (*mlist++).move = make_move(from, checksq); + } - // Pieces captures - b1 = ( (pos.attacks_from(checksq) & pos.pieces(KNIGHT, us)) - | (pos.attacks_from(checksq) & pos.pieces(BISHOP, QUEEN, us)) - | (pos.attacks_from(checksq) & pos.pieces(ROOK, QUEEN, us)) ) & ~pinned; + // Pawn blocking evasions (possible only if the checking piece is a slider) + if (sliderAttacks) + mlist = generate_piece_evasions(pos, mlist, us, target, pinned); + + // Add the checking piece to the target squares + target |= checkers; + + // Captures and blocking evasions for the other pieces + mlist = generate_piece_evasions(pos, mlist, us, target, pinned); + mlist = generate_piece_evasions(pos, mlist, us, target, pinned); + mlist = generate_piece_evasions(pos, mlist, us, target, pinned); + mlist = generate_piece_evasions(pos, mlist, us, target, pinned); + + // Finally, the special case of en passant captures. An en passant + // capture can only be a check evasion if the check is not a discovered + // check. If pos.ep_square() is set, the last move made must have been + // a double pawn push. If, furthermore, the checking piece is a pawn, + // an en passant check evasion may be possible. + if (pos.ep_square() != SQ_NONE && (checkers & pos.pieces(PAWN, them))) + { + to = pos.ep_square(); + b1 = pos.attacks_from(to, them) & pos.pieces(PAWN, us); + // The checking pawn cannot be a discovered (bishop) check candidate + // otherwise we were in check also before last double push move. + assert(!bit_is_set(pos.discovered_check_candidates(them), checksq)); + assert(count_1s(b1) == 1 || count_1s(b1) == 2); + + b1 &= ~pinned; while (b1) { from = pop_1st_bit(&b1); - (*mlist++).move = make_move(from, checksq); - } - - // Blocking check evasions are possible only if the checking piece is a slider - if (sliderAttacks) - { - Bitboard blockSquares = squares_between(checksq, ksq); - - assert((pos.occupied_squares() & blockSquares) == EmptyBoardBB); - - if (blockSquares) - { - mlist = generate_piece_moves(pos, mlist, us, blockSquares, pinned); - mlist = generate_piece_moves(pos, mlist, us, blockSquares, pinned); - mlist = generate_piece_moves(pos, mlist, us, blockSquares, pinned); - mlist = generate_piece_moves(pos, mlist, us, blockSquares, pinned); - mlist = generate_piece_moves(pos, mlist, us, blockSquares, pinned); - } - } - - // Finally, the special case of en passant captures. An en passant - // capture can only be a check evasion if the check is not a discovered - // check. If pos.ep_square() is set, the last move made must have been - // a double pawn push. If, furthermore, the checking piece is a pawn, - // an en passant check evasion may be possible. - if (pos.ep_square() != SQ_NONE && (checkers & pos.pieces(PAWN, them))) - { - to = pos.ep_square(); - b1 = pos.attacks_from(to, them) & pos.pieces(PAWN, us); - - // The checking pawn cannot be a discovered (bishop) check candidate - // otherwise we were in check also before last double push move. - assert(!bit_is_set(pos.discovered_check_candidates(them), checksq)); - assert(count_1s(b1) == 1 || count_1s(b1) == 2); - - b1 &= ~pinned; - while (b1) - { - from = pop_1st_bit(&b1); - // Move is always legal because checking pawn is not a discovered - // check candidate and our capturing pawn has been already tested - // against pinned pieces. - (*mlist++).move = make_ep_move(from, to); - } + // Move is always legal because checking pawn is not a discovered + // check candidate and our capturing pawn has been already tested + // against pinned pieces. + (*mlist++).move = make_ep_move(from, to); } } return mlist; @@ -491,10 +463,10 @@ namespace { Square from; Bitboard b; + const Square* ptr = pos.piece_list_begin(us, Piece); - for (int i = 0, e = pos.piece_count(us, Piece); i < e; i++) + while ((from = *ptr++) != SQ_NONE) { - from = pos.piece_list(us, Piece, i); b = pos.attacks_from(from) & target; SERIALIZE_MOVES(b); } @@ -513,14 +485,14 @@ namespace { } template - MoveStack* generate_piece_moves(const Position& pos, MoveStack* mlist, - Color us, Bitboard target, Bitboard pinned) { + MoveStack* generate_piece_evasions(const Position& pos, MoveStack* mlist, + Color us, Bitboard target, Bitboard pinned) { Square from; Bitboard b; + const Square* ptr = pos.piece_list_begin(us, Piece); - for (int i = 0, e = pos.piece_count(us, Piece); i < e; i++) + while ((from = *ptr++) != SQ_NONE) { - from = pos.piece_list(us, Piece, i); if (pinned && bit_is_set(pinned, from)) continue; @@ -530,8 +502,21 @@ namespace { return mlist; } + template + inline Bitboard move_pawns(Bitboard p) { + + if (Direction == DELTA_N) + return Us == WHITE ? p << 8 : p >> 8; + else if (Direction == DELTA_NE) + return Us == WHITE ? p << 9 : p >> 7; + else if (Direction == DELTA_NW) + return Us == WHITE ? p << 7 : p >> 9; + else + return p; + } + template - MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces, bool promotion) { + MoveStack* generate_pawn_diagonal_captures(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces, bool promotion) { // Calculate our parametrized parameters at compile time const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB); @@ -577,16 +562,15 @@ namespace { Bitboard b1, b2, dcPawns1, dcPawns2; Square to; - Bitboard pawns = (Type != EVASION ? pos.pieces(PAWN, Us) : pos.pieces(PAWN, Us) & ~dcp); - Bitboard emptySquares = pos.empty_squares(); - bool possiblePromotion = (pawns & TRank7BB); + Bitboard pawns = (Type == EVASION ? pos.pieces(PAWN, Us) & ~dcp : pos.pieces(PAWN, Us)); + bool possiblePromotion = pawns & TRank7BB; if (Type == CAPTURE) { // Standard captures and capturing promotions in both directions Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us)); - mlist = generate_pawn_captures_diagonal(mlist, pawns, enemyPieces, possiblePromotion); - mlist = generate_pawn_captures_diagonal(mlist, pawns, enemyPieces, possiblePromotion); + mlist = generate_pawn_diagonal_captures(mlist, pawns, enemyPieces, possiblePromotion); + mlist = generate_pawn_diagonal_captures(mlist, pawns, enemyPieces, possiblePromotion); } if (possiblePromotion) @@ -621,9 +605,9 @@ namespace { } } - // Underpromotion pawn pushes. Also promotion for evasions and captures. + // Underpromotion pawn pushes. Also queen promotions for evasions and captures. b1 = move_pawns(pp) & TRank8BB; - b1 &= (Type == EVASION ? blockSquares : emptySquares); + b1 &= (Type == EVASION ? blockSquares : pos.empty_squares()); while (b1) { @@ -640,88 +624,92 @@ namespace { } } - if (Type == CAPTURE) + if (Type != CAPTURE) { - // En passant captures - if (pos.ep_square() != SQ_NONE) + Bitboard emptySquares = pos.empty_squares(); + dcPawns1 = dcPawns2 = EmptyBoardBB; + if (Type == CHECK && (pawns & dcp)) { - assert(Us != WHITE || square_rank(pos.ep_square()) == RANK_6); - assert(Us != BLACK || square_rank(pos.ep_square()) == RANK_3); + // Pawn moves which gives discovered check. This is possible only if the + // pawn is not on the same file as the enemy king, because we don't + // generate captures. + dcPawns1 = move_pawns(pawns & dcp & ~file_bb(ksq)) & emptySquares & ~TRank8BB; + dcPawns2 = move_pawns(dcPawns1 & TRank3BB) & emptySquares; + } - Bitboard b1 = pawns & pos.attacks_from(pos.ep_square(), Them); - assert(b1 != EmptyBoardBB); + // Single pawn pushes + b1 = move_pawns(pawns) & emptySquares & ~TRank8BB; + b2 = (Type == CHECK ? (b1 & pos.attacks_from(ksq, Them)) | dcPawns1 : + (Type == EVASION ? b1 & blockSquares : b1)); + SERIALIZE_MOVES_D(b2, -TDELTA_N); + + // Double pawn pushes + b1 = move_pawns(b1 & TRank3BB) & emptySquares; + b2 = (Type == CHECK ? (b1 & pos.attacks_from(ksq, Them)) | dcPawns2 : + (Type == EVASION ? b1 & blockSquares : b1)); + SERIALIZE_MOVES_D(b2, -TDELTA_N -TDELTA_N); + } + else if (pos.ep_square() != SQ_NONE) // En passant captures + { + assert(Us != WHITE || square_rank(pos.ep_square()) == RANK_6); + assert(Us != BLACK || square_rank(pos.ep_square()) == RANK_3); - while (b1) - { - to = pop_1st_bit(&b1); - (*mlist++).move = make_ep_move(to, pos.ep_square()); - } + b1 = pawns & pos.attacks_from(pos.ep_square(), Them); + assert(b1 != EmptyBoardBB); + + while (b1) + { + to = pop_1st_bit(&b1); + (*mlist++).move = make_ep_move(to, pos.ep_square()); } - return mlist; } + return mlist; + } - dcPawns1 = dcPawns2 = EmptyBoardBB; - if (Type == CHECK && (pawns & dcp)) + template + MoveStack* generate_discovered_checks(const Position& pos, Square from, MoveStack* mlist) { + + assert(Piece != QUEEN); + + Bitboard b = pos.attacks_from(from) & pos.empty_squares(); + if (Piece == KING) { - // Pawn moves which gives discovered check. This is possible only if the - // pawn is not on the same file as the enemy king, because we don't - // generate captures. - dcPawns1 = move_pawns(pawns & dcp & ~file_bb(ksq)) & emptySquares & ~TRank8BB; - dcPawns2 = move_pawns(dcPawns1 & TRank3BB) & emptySquares; + Square ksq = pos.king_square(opposite_color(pos.side_to_move())); + b &= ~QueenPseudoAttacks[ksq]; } - - // Single pawn pushes - b1 = move_pawns(pawns) & emptySquares & ~TRank8BB; - b2 = (Type == CHECK ? (b1 & pos.attacks_from(ksq, Them)) | dcPawns1 : - (Type == EVASION ? b1 & blockSquares : b1)); - SERIALIZE_MOVES_D(b2, -TDELTA_N); - - // Double pawn pushes - b1 = move_pawns(b1 & TRank3BB) & emptySquares; - b2 = (Type == CHECK ? (b1 & pos.attacks_from(ksq, Them)) | dcPawns2 : - (Type == EVASION ? b1 & blockSquares : b1)); - SERIALIZE_MOVES_D(b2, -TDELTA_N -TDELTA_N); + SERIALIZE_MOVES(b); return mlist; } template - MoveStack* generate_piece_checks(const Position& pos, MoveStack* mlist, Color us, + MoveStack* generate_direct_checks(const Position& pos, MoveStack* mlist, Color us, Bitboard dc, Square ksq) { + assert(Piece != KING); - Bitboard target = pos.pieces(Piece, us); - - // Discovered non-capture checks - Bitboard b = target & dc; - - assert(Piece != QUEEN || !b); - - while (b) - { - Square from = pop_1st_bit(&b); - Bitboard bb = pos.attacks_from(from) & pos.empty_squares(); - if (Piece == KING) - bb &= ~QueenPseudoAttacks[ksq]; - - SERIALIZE_MOVES(bb); - } + Square from; + Bitboard checkSqs; + const Square* ptr = pos.piece_list_begin(us, Piece); - // Direct non-capture checks - b = target & ~dc; - Bitboard checkSqs = pos.attacks_from(ksq) & pos.empty_squares(); - if (Piece == KING || !checkSqs) + if ((from = *ptr++) == SQ_NONE) return mlist; - while (b) + checkSqs = pos.attacks_from(ksq) & pos.empty_squares(); + + do { - Square from = pop_1st_bit(&b); if ( (Piece == QUEEN && !(QueenPseudoAttacks[from] & checkSqs)) || (Piece == ROOK && !(RookPseudoAttacks[from] & checkSqs)) || (Piece == BISHOP && !(BishopPseudoAttacks[from] & checkSqs))) continue; + if (dc && bit_is_set(dc, from)) + continue; + Bitboard bb = pos.attacks_from(from) & checkSqs; SERIALIZE_MOVES(bb); - } + + } while ((from = *ptr++) != SQ_NONE); + return mlist; } @@ -767,17 +755,4 @@ namespace { } return mlist; } - - bool castling_is_check(const Position& pos, CastlingSide side) { - - // After castling opponent king is attacked by the castled rook? - File rookFile = (side == QUEEN_SIDE ? FILE_D : FILE_F); - Color us = pos.side_to_move(); - Square ksq = pos.king_square(us); - Bitboard occ = pos.occupied_squares(); - - clear_bit(&occ, ksq); // Remove our king from the board - Square rsq = make_square(rookFile, square_rank(ksq)); - return bit_is_set(rook_attacks_bb(rsq, occ), pos.king_square(opposite_color(us))); - } }