X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovegen.cpp;h=bfeb7247c56b9c97085fc5ad2b26e57cb4eff8a7;hp=3845cd978cab815b5d9e83eb27de9ba536d58437;hb=9e4befe3f1ea324bece88aee2e97b38659411c52;hpb=bdb1bfecfb5665329a7d66f4c366a9736bab6c0b diff --git a/src/movegen.cpp b/src/movegen.cpp index 3845cd97..bfeb7247 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -24,12 +24,16 @@ #include +#include "bitcount.h" #include "movegen.h" // Simple macro to wrap a very common while loop, no facny, no flexibility, // hardcoded list name 'mlist' and from square 'from'. #define SERIALIZE_MOVES(b) while (b) (*mlist++).move = make_move(from, pop_1st_bit(&b)) +// Version used for pawns, where the 'from' square is given as a delta from the 'to' square +#define SERIALIZE_MOVES_D(b, d) while (b) { to = pop_1st_bit(&b); (*mlist++).move = make_move(to + (d), to); } + //// //// Local definitions //// @@ -60,7 +64,7 @@ namespace { MoveStack* generate_pawn_captures(const Position& pos, MoveStack* mlist); template - MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces); + MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces, bool promotion); template MoveStack* generate_pawn_noncaptures(const Position& pos, MoveStack* mlist); @@ -131,38 +135,35 @@ namespace { /// generate_captures generates() all pseudo-legal captures and queen -/// promotions. The return value is the number of moves generated. +/// promotions. The return value is the number of moves generated. -int generate_captures(const Position& pos, MoveStack* mlist) { +MoveStack* generate_captures(const Position& pos, MoveStack* mlist) { assert(pos.is_ok()); assert(!pos.is_check()); Color us = pos.side_to_move(); Bitboard target = pos.pieces_of_color(opposite_color(us)); - MoveStack* mlist_start = mlist; mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us); - mlist = generate_piece_moves(pos, mlist, us, target); - return int(mlist - mlist_start); + return generate_piece_moves(pos, mlist, us, target); } /// generate_noncaptures() generates all pseudo-legal non-captures and /// underpromotions. The return value is the number of moves generated. -int generate_noncaptures(const Position& pos, MoveStack* mlist) { +MoveStack* generate_noncaptures(const Position& pos, MoveStack* mlist) { assert(pos.is_ok()); assert(!pos.is_check()); Color us = pos.side_to_move(); Bitboard target = pos.empty_squares(); - MoveStack* mlist_start = mlist; mlist = generate_piece_moves(pos, mlist, us); mlist = generate_piece_moves(pos, mlist, us, target); @@ -171,22 +172,20 @@ int generate_noncaptures(const Position& pos, MoveStack* mlist) { mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_castle_moves(pos, mlist); - mlist = generate_castle_moves(pos, mlist); - return int(mlist - mlist_start); + return generate_castle_moves(pos, mlist); } /// generate_non_capture_checks() generates all pseudo-legal non-capturing, /// non-promoting checks. It returns the number of generated moves. -int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { +MoveStack* generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { assert(pos.is_ok()); assert(!pos.is_check()); Color us = pos.side_to_move(); Square ksq = pos.king_square(opposite_color(us)); - MoveStack* mlist_start = mlist; assert(pos.piece_on(ksq) == piece_of_color_and_type(opposite_color(us), KING)); @@ -209,7 +208,7 @@ int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard && castling_is_check(pos, KING_SIDE)) mlist = generate_castle_moves(pos, mlist); - return int(mlist - mlist_start); + return mlist; } @@ -217,7 +216,7 @@ int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard /// in check. Unlike the other move generation functions, this one generates /// only legal moves. It returns the number of generated moves. -int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { +MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { assert(pos.is_ok()); assert(pos.is_check()); @@ -226,7 +225,6 @@ int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { Color us = pos.side_to_move(); Color them = opposite_color(us); Square ksq = pos.king_square(us); - MoveStack* mlist_start = mlist; assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING)); @@ -346,7 +344,7 @@ int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { } } } - return int(mlist - mlist_start); + return mlist; } @@ -356,7 +354,7 @@ int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { /// very hard to write an efficient legal move generator, but for the moment /// we don't need it. -int generate_legal_moves(const Position& pos, MoveStack* mlist) { +MoveStack* generate_legal_moves(const Position& pos, MoveStack* mlist) { assert(pos.is_ok()); @@ -366,15 +364,17 @@ int generate_legal_moves(const Position& pos, MoveStack* mlist) { return generate_evasions(pos, mlist, pinned); // Generate pseudo-legal moves - int n = generate_captures(pos, mlist); - n += generate_noncaptures(pos, mlist + n); + MoveStack* last = generate_captures(pos, mlist); + last = generate_noncaptures(pos, last); // Remove illegal moves from the list - for (int i = 0; i < n; i++) - if (!pos.pl_move_is_legal(mlist[i].move, pinned)) - mlist[i--].move = mlist[--n].move; - - return n; + for (MoveStack* cur = mlist; cur != last; cur++) + if (!pos.pl_move_is_legal(cur->move, pinned)) + { + cur->move = (--last)->move; + cur--; + } + return last; } @@ -505,7 +505,7 @@ bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) { // be a promotion. if ( ( (square_rank(to) == RANK_8 && us == WHITE) ||(square_rank(to) == RANK_1 && us != WHITE)) - && !move_promotion(m)) + && !move_is_promotion(m)) return false; // Proceed according to the square delta between the source and @@ -559,7 +559,31 @@ bool move_is_legal(const Position& pos, const Move m, Bitboard pinned) { // Luckly we can handle all the other pieces in one go return ( pos.piece_attacks_square(pos.piece_on(from), from, to) && pos.pl_move_is_legal(m, pinned) - && !move_promotion(m)); + && !move_is_promotion(m)); +} + + +/// Another version of move_is_legal(), which takes only a position and a move +/// as input. This function does not require that the side to move is not in +/// check. It is not optimized for speed, and is only used for verifying move +/// legality when building a PV from the transposition table. + +bool move_is_legal(const Position& pos, const Move m) { + + Bitboard pinned = pos.pinned_pieces(pos.side_to_move()); + if (!pos.is_check()) + return move_is_legal(pos, m, pinned); + else + { + Position p(pos); + MoveStack mlist[64]; + MoveStack* last = generate_evasions(p, mlist, pinned); + for (MoveStack* cur = mlist; cur != last; cur++) + if (cur->move == m) + return true; + + return false; + } } @@ -610,7 +634,7 @@ namespace { } template - MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces) { + MoveStack* generate_pawn_captures_diagonal(MoveStack* mlist, Bitboard pawns, Bitboard enemyPieces, bool promotion) { // Calculate our parametrized parameters at compile time const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB); @@ -625,20 +649,19 @@ namespace { Bitboard b1 = move_pawns(pawns) & ~TFileABB & enemyPieces; // Capturing promotions - Bitboard b2 = b1 & TRank8BB; - while (b2) + if (promotion) { - to = pop_1st_bit(&b2); - (*mlist++).move = make_promotion_move(to - TTDELTA_NE, to, QUEEN); + Bitboard b2 = b1 & TRank8BB; + b1 &= ~TRank8BB; + while (b2) + { + to = pop_1st_bit(&b2); + (*mlist++).move = make_promotion_move(to - TTDELTA_NE, to, QUEEN); + } } // Capturing non-promotions - b2 = b1 & ~TRank8BB; - while (b2) - { - to = pop_1st_bit(&b2); - (*mlist++).move = make_move(to - TTDELTA_NE, to); - } + SERIALIZE_MOVES_D(b1, -TTDELTA_NE); return mlist; } @@ -648,22 +671,27 @@ namespace { // Calculate our parametrized parameters at compile time const Color Them = (Us == WHITE ? BLACK : WHITE); const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB); + const Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB); const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S); Square to; Bitboard pawns = pos.pawns(Us); Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us)); + bool possiblePromotion = (pawns & TRank7BB); // Standard captures and capturing promotions in both directions - mlist = generate_pawn_captures_diagonal(mlist, pawns, enemyPieces); - mlist = generate_pawn_captures_diagonal(mlist, pawns, enemyPieces); + mlist = generate_pawn_captures_diagonal(mlist, pawns, enemyPieces, possiblePromotion); + mlist = generate_pawn_captures_diagonal(mlist, pawns, enemyPieces, possiblePromotion); // Non-capturing promotions - Bitboard b1 = move_pawns(pawns) & pos.empty_squares() & TRank8BB; - while (b1) + if (possiblePromotion) { - to = pop_1st_bit(&b1); - (*mlist++).move = make_promotion_move(to - TDELTA_N, to, QUEEN); + Bitboard b1 = move_pawns(pawns) & pos.empty_squares() & TRank8BB; + while (b1) + { + to = pop_1st_bit(&b1); + (*mlist++).move = make_promotion_move(to - TDELTA_N, to, QUEEN); + } } // En passant captures @@ -672,7 +700,7 @@ namespace { assert(Us != WHITE || square_rank(pos.ep_square()) == RANK_6); assert(Us != BLACK || square_rank(pos.ep_square()) == RANK_3); - b1 = pawns & pos.pawn_attacks(Them, pos.ep_square()); + Bitboard b1 = pawns & pos.pawn_attacks(Them, pos.ep_square()); assert(b1 != EmptyBoardBB); while (b1) @@ -689,6 +717,7 @@ namespace { // Calculate our parametrized parameters at compile time const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB); + const Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB); const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB); const SquareDelta TDELTA_NE = (Us == WHITE ? DELTA_NE : DELTA_SE); const SquareDelta TDELTA_NW = (Us == WHITE ? DELTA_NW : DELTA_SW); @@ -697,53 +726,50 @@ namespace { Bitboard b1, b2; Square to; Bitboard pawns = pos.pawns(Us); - Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us)); Bitboard emptySquares = pos.empty_squares(); - // Underpromotion captures in the a1-h8 (a8-h1 for black) direction - b1 = move_pawns(pawns) & ~FileABB & enemyPieces & TRank8BB; - while (b1) + if (pawns & TRank7BB) // There is some promotion candidate ? { - to = pop_1st_bit(&b1); - (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, ROOK); - (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, BISHOP); - (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, KNIGHT); - } + Bitboard enemyPieces = pos.pieces_of_color(opposite_color(Us)); - // Underpromotion captures in the h1-a8 (h8-a1 for black) direction - b1 = move_pawns(pawns) & ~FileHBB & enemyPieces & TRank8BB; - while (b1) - { - to = pop_1st_bit(&b1); - (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, ROOK); - (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, BISHOP); - (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, KNIGHT); + // Underpromotion captures in the a1-h8 (a8-h1 for black) direction + b1 = move_pawns(pawns) & ~FileABB & enemyPieces & TRank8BB; + while (b1) + { + to = pop_1st_bit(&b1); + (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, ROOK); + (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, BISHOP); + (*mlist++).move = make_promotion_move(to - TDELTA_NE, to, KNIGHT); + } + + // Underpromotion captures in the h1-a8 (h8-a1 for black) direction + b1 = move_pawns(pawns) & ~FileHBB & enemyPieces & TRank8BB; + while (b1) + { + to = pop_1st_bit(&b1); + (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, ROOK); + (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, BISHOP); + (*mlist++).move = make_promotion_move(to - TDELTA_NW, to, KNIGHT); + } + + // Underpromotion pawn pushes + b1 = move_pawns(pawns) & emptySquares & TRank8BB; + while (b1) + { + to = pop_1st_bit(&b1); + (*mlist++).move = make_promotion_move(to - TDELTA_N, to, ROOK); + (*mlist++).move = make_promotion_move(to - TDELTA_N, to, BISHOP); + (*mlist++).move = make_promotion_move(to - TDELTA_N, to, KNIGHT); + } } // Single pawn pushes - b1 = move_pawns(pawns) & emptySquares; - b2 = b1 & TRank8BB; - while (b2) - { - to = pop_1st_bit(&b2); - (*mlist++).move = make_promotion_move(to - TDELTA_N, to, ROOK); - (*mlist++).move = make_promotion_move(to - TDELTA_N, to, BISHOP); - (*mlist++).move = make_promotion_move(to - TDELTA_N, to, KNIGHT); - } - b2 = b1 & ~TRank8BB; - while (b2) - { - to = pop_1st_bit(&b2); - (*mlist++).move = make_move(to - TDELTA_N, to); - } + b2 = b1 = move_pawns(pawns) & emptySquares & ~TRank8BB; + SERIALIZE_MOVES_D(b2, -TDELTA_N); // Double pawn pushes b2 = move_pawns(b1 & TRank3BB) & emptySquares; - while (b2) - { - to = pop_1st_bit(&b2); - (*mlist++).move = make_move(to - TDELTA_N - TDELTA_N, to); - } + SERIALIZE_MOVES_D(b2, -TDELTA_N -TDELTA_N); return mlist; } @@ -758,6 +784,7 @@ namespace { const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S); const SquareDelta TDELTA_S = (Us == WHITE ? DELTA_S : DELTA_N); + Square to; Bitboard b1, b2, b3; Bitboard pawns = pos.pawns(Us); @@ -772,46 +799,32 @@ namespace { // Discovered checks, single pawn pushes, no promotions b2 = b3 = move_pawns(b1 & dc) & empty & ~TRank8BB; - while (b3) - { - Square to = pop_1st_bit(&b3); - (*mlist++).move = make_move(to - TDELTA_N, to); - } + SERIALIZE_MOVES_D(b3, -TDELTA_N); // Discovered checks, double pawn pushes b3 = move_pawns(b2 & TRank3BB) & empty; - while (b3) - { - Square to = pop_1st_bit(&b3); - (*mlist++).move = make_move(to - TDELTA_N - TDELTA_N, to); - } + SERIALIZE_MOVES_D(b3, -TDELTA_N -TDELTA_N); } // Direct checks. These are possible only for pawns on neighboring files // and in the two ranks that, after the push, are in front of the enemy king. b1 = pawns & neighboring_files_bb(ksq) & ~dc; - b2 = rank_bb(ksq + 2 * TDELTA_S) | rank_bb(ksq + 3 * TDELTA_S); - b1 &= b2; - if (!b1) + + // We can get false positives if (ksq + x) is not in [0,63] range but + // is not a problem, they will be filtered out later. + b2 = b1 & (rank_bb(ksq + 2 * TDELTA_S) | rank_bb(ksq + 3 * TDELTA_S)); + if (!b2) return mlist; // Direct checks, single pawn pushes Bitboard empty = pos.empty_squares(); b2 = move_pawns(b1) & empty; b3 = b2 & pos.pawn_attacks(Them, ksq); - while (b3) - { - Square to = pop_1st_bit(&b3); - (*mlist++).move = make_move(to - TDELTA_N, to); - } + SERIALIZE_MOVES_D(b3, -TDELTA_N); // Direct checks, double pawn pushes b3 = move_pawns(b2 & TRank3BB) & empty & pos.pawn_attacks(Them, ksq); - while (b3) - { - Square to = pop_1st_bit(&b3); - (*mlist++).move = make_move(to - TDELTA_N - TDELTA_N, to); - } + SERIALIZE_MOVES_D(b3, -TDELTA_N -TDELTA_N); return mlist; } @@ -861,7 +874,7 @@ namespace { Bitboard blockSquares, MoveStack* mlist) { // Calculate our parametrized parameters at compile time - const Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB); + const Rank TRANK_8 = (Us == WHITE ? RANK_8 : RANK_1); const Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB); const SquareDelta TDELTA_N = (Us == WHITE ? DELTA_N : DELTA_S); @@ -879,7 +892,7 @@ namespace { assert(pos.piece_on(to) == EMPTY); - if (square_rank(to) == TRank8BB) + if (square_rank(to) == TRANK_8) { (*mlist++).move = make_promotion_move(to - TDELTA_N, to, QUEEN); (*mlist++).move = make_promotion_move(to - TDELTA_N, to, ROOK);