From 486ec580f98ee1f3072bc40278083091408205ec Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Thu, 16 Oct 2008 14:25:56 +0200 Subject: [PATCH 01/16] Space inflate movepick.cpp Also added some FIXME to dubious points. Still no functional change. Signed-off-by: Marco Costalba --- src/movepick.cpp | 461 ++++++++++++++++++++++++----------------------- src/movepick.h | 9 + 2 files changed, 246 insertions(+), 224 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index 066af5f9..ca7e1a25 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -94,89 +94,84 @@ MovePicker::MovePicker(Position &p, bool pvnode, Move ttm, Move mk, /// are no more moves left of the types we are interested in. Move MovePicker::get_next_move() { + Move move; - while(true) { + while (true) + { // If we already have a list of generated moves, pick the best move from // the list, and return it: - move = this->pick_move_from_list(); - if(move != MOVE_NONE) { - assert(move_is_ok(move)); - return move; + move = pick_move_from_list(); + if (move != MOVE_NONE) + { + assert(move_is_ok(move)); + return move; } // Next phase: phaseIndex++; - switch(PhaseTable[phaseIndex]) { + switch (PhaseTable[phaseIndex]) { case PH_TT_MOVE: - if(ttMove != MOVE_NONE) { - assert(move_is_ok(ttMove)); - Move m = generate_move_if_legal(*pos, ttMove, pinned); - if(m != MOVE_NONE) { - assert(m == ttMove); - return m; + if (ttMove != MOVE_NONE) + { + assert(move_is_ok(ttMove)); + if (generate_move_if_legal(*pos, ttMove, pinned) != MOVE_NONE) + return ttMove; } - } - break; + break; case PH_MATE_KILLER: - if(mateKiller != MOVE_NONE) { - assert(move_is_ok(mateKiller)); - Move m = generate_move_if_legal(*pos, mateKiller, pinned); - if(m != MOVE_NONE) { - assert(m == mateKiller); - return m; + if (mateKiller != MOVE_NONE) + { + assert(move_is_ok(mateKiller)); + if (generate_move_if_legal(*pos, mateKiller, pinned) != MOVE_NONE) + return ttMove; } - } - break; + break; - case PH_GOOD_CAPTURES: - // pinned = pos->pinned_pieces(pos->side_to_move()); - numOfMoves = generate_captures(*pos, moves); - this->score_captures(); - movesPicked = 0; - break; + case PH_GOOD_CAPTURES: + numOfMoves = generate_captures(*pos, moves); + score_captures(); + movesPicked = 0; + break; case PH_BAD_CAPTURES: - badCapturesPicked = 0; - break; + badCapturesPicked = 0; + break; case PH_NONCAPTURES: - numOfMoves = generate_noncaptures(*pos, moves); - this->score_noncaptures(); - movesPicked = 0; - break; + numOfMoves = generate_noncaptures(*pos, moves); + score_noncaptures(); + movesPicked = 0; + break; case PH_EVASIONS: - assert(pos->is_check()); - // pinned = pos->pinned_pieces(pos->side_to_move()); - numOfMoves = generate_evasions(*pos, moves); - this->score_evasions(); - movesPicked = 0; - break; - - case PH_QCAPTURES: - // pinned = pos->pinned_pieces(pos->side_to_move()); - numOfMoves = generate_captures(*pos, moves); - this->score_qcaptures(); - movesPicked = 0; - break; + assert(pos->is_check()); + numOfMoves = generate_evasions(*pos, moves); + score_evasions(); + movesPicked = 0; + break; + + case PH_QCAPTURES: + numOfMoves = generate_captures(*pos, moves); + score_qcaptures(); + movesPicked = 0; + break; case PH_QCHECKS: - numOfMoves = generate_checks(*pos, moves, dc); - movesPicked = 0; - break; + numOfMoves = generate_checks(*pos, moves, dc); + movesPicked = 0; + break; case PH_STOP: - return MOVE_NONE; + return MOVE_NONE; default: - assert(false); - return MOVE_NONE; + assert(false); + return MOVE_NONE; } } - assert(false); return MOVE_NONE; @@ -187,32 +182,21 @@ Move MovePicker::get_next_move() { /// prevent multiple threads from picking the same move at a split point. Move MovePicker::get_next_move(Lock &lock) { - Move m; - - lock_grab(&lock); - if(finished) { - lock_release(&lock); - return MOVE_NONE; - } - m = this->get_next_move(); - if(m == MOVE_NONE) - finished = true; - lock_release(&lock); - - return m; -} - -/// MovePicker::number_of_moves() simply returns the numOfMoves member -/// variable. It is intended to be used in positions where the side to move -/// is in check, for detecting checkmates or situations where there is only -/// a single reply to check. + lock_grab(&lock); + if (finished) + { + lock_release(&lock); + return MOVE_NONE; + } + Move m = get_next_move(); + if (m == MOVE_NONE) + finished = true; -int MovePicker::number_of_moves() const { - return numOfMoves; + lock_release(&lock); + return m; } - /// MovePicker::score_captures(), MovePicker::score_noncaptures(), /// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a /// numerical move ordering score to each move in a move list. The moves @@ -229,19 +213,17 @@ void MovePicker::score_captures() { // where it is possible to recapture with the hanging piece). Exchanging // big pieces before capturing a hanging piece probably helps to reduce // the subtree size. - for(int i = 0; i < numOfMoves; i++) { - int seeValue = pos->see(moves[i].move); - if(seeValue >= 0) { - if(move_promotion(moves[i].move)) - moves[i].score = QueenValueMidgame; - else - moves[i].score = - int(pos->midgame_value_of_piece_on(move_to(moves[i].move))) - - int(pos->type_of_piece_on(move_from(moves[i].move))); - } - else - moves[i].score = seeValue; - + for (int i = 0; i < numOfMoves; i++) + { + Move m = moves[i].move; + moves[i].score = pos->see(m); + if (moves[i].score >= 0) + { + moves[i].score = move_promotion(m) ? QueenValueMidgame + : int(pos->midgame_value_of_piece_on(move_to(m))) + -int(pos->type_of_piece_on(move_from(m))); + // FIXME second term seems wrong ! + } } } @@ -266,29 +248,34 @@ void MovePicker::score_noncaptures() { } void MovePicker::score_evasions() { - for(int i = 0; i < numOfMoves; i++) { - Move m = moves[i].move; - if(m == ttMove) - moves[i].score = 2*HistoryMax; - else if(!pos->square_is_empty(move_to(m))) { - int seeScore = pos->see(m); - moves[i].score = (seeScore >= 0)? seeScore + HistoryMax : seeScore; - } - else - moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m); + + for (int i = 0; i < numOfMoves; i++) + { + Move m = moves[i].move; + if (m == ttMove) + moves[i].score = 2*HistoryMax; + else if (!pos->square_is_empty(move_to(m))) + { + moves[i].score = pos->see(m); + if (moves[i].score >= 0) + moves[i].score += HistoryMax; + } + else + moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m); } + // FIXME try psqt also here } void MovePicker::score_qcaptures() { + // Use MVV/LVA ordering. - for(int i = 0; i < numOfMoves; i++) { - Move m = moves[i].move; - if(move_promotion(m)) - moves[i].score = QueenValueMidgame; - else - moves[i].score = - int(pos->midgame_value_of_piece_on(move_to(m))) - - int(pos->midgame_value_of_piece_on(move_to(m))) / 64; + for (int i = 0; i < numOfMoves; i++) + { + Move m = moves[i].move; + moves[i].score = move_promotion(m) ? QueenValueMidgame + : int(pos->midgame_value_of_piece_on(move_to(m))) + -int(pos->midgame_value_of_piece_on(move_to(m))) / 64; + // FIXME Why second term like that ??? } } @@ -302,161 +289,187 @@ void MovePicker::score_qcaptures() { /// negative SEE values to the badCaptures[] array. Move MovePicker::pick_move_from_list() { + int bestScore = -10000000; int bestIndex; Move move; - switch(PhaseTable[phaseIndex]) { + switch (PhaseTable[phaseIndex]) { case PH_GOOD_CAPTURES: - assert(!pos->is_check()); - assert(movesPicked >= 0); - while(movesPicked < numOfMoves) { - bestScore = -10000000; - bestIndex = -1; - for(int i = movesPicked; i < numOfMoves; i++) { - if(moves[i].score < 0) { - // Losing capture, move it to the badCaptures[] array - assert(numOfBadCaptures < 63); - badCaptures[numOfBadCaptures++] = moves[i]; - moves[i--] = moves[--numOfMoves]; - } - else if(moves[i].score > bestScore) { - bestIndex = i; - bestScore = moves[i].score; - } - } - if(bestIndex != -1) { // Found a good capture - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - if(move != ttMove && move != mateKiller && - pos->move_is_legal(move, pinned)) - return move; + assert(!pos->is_check()); + assert(movesPicked >= 0); + while (movesPicked < numOfMoves) + { + bestScore = -10000000; + bestIndex = -1; + for (int i = movesPicked; i < numOfMoves; i++) + { + if (moves[i].score < 0) + { + // Losing capture, move it to the badCaptures[] array + assert(numOfBadCaptures < 63); + badCaptures[numOfBadCaptures++] = moves[i]; + moves[i--] = moves[--numOfMoves]; + } + else if (moves[i].score > bestScore) + { + bestIndex = i; + bestScore = moves[i].score; + } + } + if (bestIndex != -1) // Found a good capture + { + move = moves[bestIndex].move; + moves[bestIndex] = moves[movesPicked++]; + if ( move != ttMove + && move != mateKiller + && pos->move_is_legal(move, pinned)) + return move; + } } - } - break; + break; case PH_NONCAPTURES: - assert(!pos->is_check()); - assert(movesPicked >= 0); - while(movesPicked < numOfMoves) { - bestScore = -10000000; - - // If this is a PV node or we have only picked a few moves, scan - // the entire move list for the best move. If many moves have already - // been searched and it is not a PV node, we are probably failing low - // anyway, so we just pick the first move from the list. - if(pvNode || movesPicked < 12) { - bestIndex = -1; - for(int i = movesPicked; i < numOfMoves; i++) - if(moves[i].score > bestScore) { - bestIndex = i; - bestScore = moves[i].score; - } - } - else - bestIndex = movesPicked; - - if(bestIndex != -1) { - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - if(move != ttMove && move != mateKiller && - pos->move_is_legal(move, pinned)) - return move; - } + assert(!pos->is_check()); + assert(movesPicked >= 0); + while (movesPicked < numOfMoves) + { + // If this is a PV node or we have only picked a few moves, scan + // the entire move list for the best move. If many moves have already + // been searched and it is not a PV node, we are probably failing low + // anyway, so we just pick the first move from the list. + if (pvNode || movesPicked < 12) + { + bestScore = -10000000; + bestIndex = -1; + for (int i = movesPicked; i < numOfMoves; i++) + if(moves[i].score > bestScore) + { + bestIndex = i; + bestScore = moves[i].score; + } + } else + bestIndex = movesPicked; + + if (bestIndex != -1) + { + move = moves[bestIndex].move; + moves[bestIndex] = moves[movesPicked++]; + if ( move != ttMove + && move != mateKiller + && pos->move_is_legal(move, pinned)) + return move; + } } break; case PH_EVASIONS: - assert(pos->is_check()); - assert(movesPicked >= 0); - while(movesPicked < numOfMoves) { - bestScore = -10000000; - bestIndex = -1; - for(int i = movesPicked; i < numOfMoves; i++) - if(moves[i].score > bestScore) { - bestIndex = i; - bestScore = moves[i].score; - } - - if(bestIndex != -1) { - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - return move; + assert(pos->is_check()); + assert(movesPicked >= 0); + while (movesPicked < numOfMoves) + { + bestScore = -10000000; + bestIndex = -1; + for (int i = movesPicked; i < numOfMoves; i++) + if (moves[i].score > bestScore) + { + bestIndex = i; + bestScore = moves[i].score; + } + + if (bestIndex != -1) + { + move = moves[bestIndex].move; + moves[bestIndex] = moves[movesPicked++]; + return move; + } } - } - break; + break; case PH_BAD_CAPTURES: - assert(!pos->is_check()); - assert(badCapturesPicked >= 0); - // It's probably a good idea to use SEE move ordering here, instead - // of just picking the first move. FIXME - while(badCapturesPicked < numOfBadCaptures) { - move = badCaptures[badCapturesPicked++].move; - if(move != ttMove && move != mateKiller && - pos->move_is_legal(move, pinned)) - return move; - } - break; + assert(!pos->is_check()); + assert(badCapturesPicked >= 0); + // It's probably a good idea to use SEE move ordering here, instead + // of just picking the first move. FIXME + while (badCapturesPicked < numOfBadCaptures) + { + move = badCaptures[badCapturesPicked++].move; + if ( move != ttMove + && move != mateKiller + && pos->move_is_legal(move, pinned)) + return move; + } + break; case PH_QCAPTURES: - assert(!pos->is_check()); - assert(movesPicked >= 0); - while(movesPicked < numOfMoves) { - bestScore = -10000000; - if(movesPicked < 4) { - bestIndex = -1; - for(int i = movesPicked; i < numOfMoves; i++) - if(moves[i].score > bestScore) { - bestIndex = i; - bestScore = moves[i].score; + assert(!pos->is_check()); + assert(movesPicked >= 0); + while (movesPicked < numOfMoves) + { + bestScore = -10000000; + if (movesPicked < 4) // FIXME makes sens to score qcaps? + { + bestIndex = -1; + for (int i = movesPicked; i < numOfMoves; i++) + if(moves[i].score > bestScore) + { + bestIndex = i; + bestScore = moves[i].score; + } + } else + bestIndex = movesPicked; + + if (bestIndex != -1) + { + move = moves[bestIndex].move; + moves[bestIndex] = moves[movesPicked++]; + // Remember to change the line below if we decide to hash the qsearch! + // Maybe also postpone the legality check until after futility pruning? + // FIXME !!! + if (/* move != ttMove && */ pos->move_is_legal(move, pinned)) + return move; } } - else - bestIndex = movesPicked; - - if(bestIndex != -1) { - move = moves[bestIndex].move; - moves[bestIndex] = moves[movesPicked++]; - // Remember to change the line below if we decide to hash the qsearch! - // Maybe also postpone the legality check until after futility pruning? - if(/* move != ttMove && */ pos->move_is_legal(move, pinned)) - return move; - } - } - break; + break; case PH_QCHECKS: - assert(!pos->is_check()); - assert(movesPicked >= 0); - // Perhaps we should do something better than just picking the first - // move here? FIXME - while(movesPicked < numOfMoves) { - move = moves[movesPicked++].move; - // Remember to change the line below if we decide to hash the qsearch! - if(/* move != ttMove && */ pos->move_is_legal(move, pinned)) - return move; - } - break; + assert(!pos->is_check()); + assert(movesPicked >= 0); + // Perhaps we should do something better than just picking the first + // move here? FIXME + while (movesPicked < numOfMoves) + { + move = moves[movesPicked++].move; + // Remember to change the line below if we decide to hash the qsearch! + // FIXME !!! + if (/* move != ttMove && */ pos->move_is_legal(move, pinned)) + return move; + } + break; default: - break; + break; } - return MOVE_NONE; } + +/// MovePicker::current_move_type() returns the type of the just +/// picked next move. It can be used in search to further differentiate +/// according to the current move type: capture, non capture, escape, etc. MovePicker::MovegenPhase MovePicker::current_move_type() const { return PhaseTable[phaseIndex]; } + /// MovePicker::init_phase_table() initializes the PhaseTable[], /// MainSearchPhaseIndex, EvasionPhaseIndex, QsearchWithChecksPhaseIndex /// and QsearchWithoutChecksPhaseIndex variables. It is only called once /// during program startup, and never again while the program is running. void MovePicker::init_phase_table() { + int i = 0; // Main search diff --git a/src/movepick.h b/src/movepick.h index df2012fe..ab1c0ade 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -94,6 +94,15 @@ private: //// Inline functions //// +/// MovePicker::number_of_moves() simply returns the numOfMoves member +/// variable. It is intended to be used in positions where the side to move +/// is in check, for detecting checkmates or situations where there is only +/// a single reply to check. + +inline int MovePicker::number_of_moves() const { + return numOfMoves; +} + /// MovePicker::discovered_check_candidates() returns a bitboard containing /// all pieces which can possibly give discovered check. This bitboard is /// computed by the constructor function. -- 2.39.2 From 2943e1ca3171341cd301b18280f3fa3b6bdda162 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Thu, 16 Oct 2008 16:21:36 +0200 Subject: [PATCH 02/16] MovePicker: use const reference instead of pointers Signed-off-by: Marco Costalba --- src/movepick.cpp | 65 ++++++++++++++++++++++++------------------------ src/movepick.h | 5 ++-- 2 files changed, 34 insertions(+), 36 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index ca7e1a25..4b1fccc4 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -60,15 +60,14 @@ namespace { /// search captures, promotions and some checks) and about how important good /// move ordering is at the current node. -MovePicker::MovePicker(Position &p, bool pvnode, Move ttm, Move mk, - Move k1, Move k2, Depth dpth) { - pos = &p; +MovePicker::MovePicker(const Position& p, bool pvnode, Move ttm, Move mk, + Move k1, Move k2, Depth d) : pos(p) { pvNode = pvnode; ttMove = ttm; mateKiller = (mk == ttm)? MOVE_NONE : mk; killer1 = k1; killer2 = k2; - depth = dpth; + depth = d; movesPicked = 0; numOfMoves = 0; numOfBadCaptures = 0; @@ -116,7 +115,7 @@ Move MovePicker::get_next_move() { if (ttMove != MOVE_NONE) { assert(move_is_ok(ttMove)); - if (generate_move_if_legal(*pos, ttMove, pinned) != MOVE_NONE) + if (generate_move_if_legal(pos, ttMove, pinned) != MOVE_NONE) return ttMove; } break; @@ -125,13 +124,13 @@ Move MovePicker::get_next_move() { if (mateKiller != MOVE_NONE) { assert(move_is_ok(mateKiller)); - if (generate_move_if_legal(*pos, mateKiller, pinned) != MOVE_NONE) + if (generate_move_if_legal(pos, mateKiller, pinned) != MOVE_NONE) return ttMove; } break; case PH_GOOD_CAPTURES: - numOfMoves = generate_captures(*pos, moves); + numOfMoves = generate_captures(pos, moves); score_captures(); movesPicked = 0; break; @@ -141,26 +140,26 @@ Move MovePicker::get_next_move() { break; case PH_NONCAPTURES: - numOfMoves = generate_noncaptures(*pos, moves); + numOfMoves = generate_noncaptures(pos, moves); score_noncaptures(); movesPicked = 0; break; case PH_EVASIONS: - assert(pos->is_check()); - numOfMoves = generate_evasions(*pos, moves); + assert(pos.is_check()); + numOfMoves = generate_evasions(pos, moves); score_evasions(); movesPicked = 0; break; case PH_QCAPTURES: - numOfMoves = generate_captures(*pos, moves); + numOfMoves = generate_captures(pos, moves); score_qcaptures(); movesPicked = 0; break; case PH_QCHECKS: - numOfMoves = generate_checks(*pos, moves, dc); + numOfMoves = generate_checks(pos, moves, dc); movesPicked = 0; break; @@ -216,12 +215,12 @@ void MovePicker::score_captures() { for (int i = 0; i < numOfMoves; i++) { Move m = moves[i].move; - moves[i].score = pos->see(m); + moves[i].score = pos.see(m); if (moves[i].score >= 0) { moves[i].score = move_promotion(m) ? QueenValueMidgame - : int(pos->midgame_value_of_piece_on(move_to(m))) - -int(pos->type_of_piece_on(move_from(m))); + : int(pos.midgame_value_of_piece_on(move_to(m))) + -int(pos.type_of_piece_on(move_from(m))); // FIXME second term seems wrong ! } } @@ -237,13 +236,13 @@ void MovePicker::score_noncaptures() { else if (m == killer2) moves[i].score = HistoryMax + 1; else - moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m); + moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), m); // Ensure moves in history are always sorted as first if (moves[i].score > 0) moves[i].score += 1000; - moves[i].score += pos->mg_pst_delta(moves[i].move); + moves[i].score += pos.mg_pst_delta(moves[i].move); } } @@ -254,14 +253,14 @@ void MovePicker::score_evasions() { Move m = moves[i].move; if (m == ttMove) moves[i].score = 2*HistoryMax; - else if (!pos->square_is_empty(move_to(m))) + else if (!pos.square_is_empty(move_to(m))) { - moves[i].score = pos->see(m); + moves[i].score = pos.see(m); if (moves[i].score >= 0) moves[i].score += HistoryMax; } else - moves[i].score = H.move_ordering_score(pos->piece_on(move_from(m)), m); + moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), m); } // FIXME try psqt also here } @@ -273,8 +272,8 @@ void MovePicker::score_qcaptures() { { Move m = moves[i].move; moves[i].score = move_promotion(m) ? QueenValueMidgame - : int(pos->midgame_value_of_piece_on(move_to(m))) - -int(pos->midgame_value_of_piece_on(move_to(m))) / 64; + : int(pos.midgame_value_of_piece_on(move_to(m))) + -int(pos.midgame_value_of_piece_on(move_to(m))) / 64; // FIXME Why second term like that ??? } } @@ -297,7 +296,7 @@ Move MovePicker::pick_move_from_list() { switch (PhaseTable[phaseIndex]) { case PH_GOOD_CAPTURES: - assert(!pos->is_check()); + assert(!pos.is_check()); assert(movesPicked >= 0); while (movesPicked < numOfMoves) { @@ -324,14 +323,14 @@ Move MovePicker::pick_move_from_list() { moves[bestIndex] = moves[movesPicked++]; if ( move != ttMove && move != mateKiller - && pos->move_is_legal(move, pinned)) + && pos.move_is_legal(move, pinned)) return move; } } break; case PH_NONCAPTURES: - assert(!pos->is_check()); + assert(!pos.is_check()); assert(movesPicked >= 0); while (movesPicked < numOfMoves) { @@ -358,14 +357,14 @@ Move MovePicker::pick_move_from_list() { moves[bestIndex] = moves[movesPicked++]; if ( move != ttMove && move != mateKiller - && pos->move_is_legal(move, pinned)) + && pos.move_is_legal(move, pinned)) return move; } } break; case PH_EVASIONS: - assert(pos->is_check()); + assert(pos.is_check()); assert(movesPicked >= 0); while (movesPicked < numOfMoves) { @@ -388,7 +387,7 @@ Move MovePicker::pick_move_from_list() { break; case PH_BAD_CAPTURES: - assert(!pos->is_check()); + assert(!pos.is_check()); assert(badCapturesPicked >= 0); // It's probably a good idea to use SEE move ordering here, instead // of just picking the first move. FIXME @@ -397,13 +396,13 @@ Move MovePicker::pick_move_from_list() { move = badCaptures[badCapturesPicked++].move; if ( move != ttMove && move != mateKiller - && pos->move_is_legal(move, pinned)) + && pos.move_is_legal(move, pinned)) return move; } break; case PH_QCAPTURES: - assert(!pos->is_check()); + assert(!pos.is_check()); assert(movesPicked >= 0); while (movesPicked < numOfMoves) { @@ -427,14 +426,14 @@ Move MovePicker::pick_move_from_list() { // Remember to change the line below if we decide to hash the qsearch! // Maybe also postpone the legality check until after futility pruning? // FIXME !!! - if (/* move != ttMove && */ pos->move_is_legal(move, pinned)) + if (/* move != ttMove && */ pos.move_is_legal(move, pinned)) return move; } } break; case PH_QCHECKS: - assert(!pos->is_check()); + assert(!pos.is_check()); assert(movesPicked >= 0); // Perhaps we should do something better than just picking the first // move here? FIXME @@ -443,7 +442,7 @@ Move MovePicker::pick_move_from_list() { move = moves[movesPicked++].move; // Remember to change the line below if we decide to hash the qsearch! // FIXME !!! - if (/* move != ttMove && */ pos->move_is_legal(move, pinned)) + if (/* move != ttMove && */ pos.move_is_legal(move, pinned)) return move; } break; diff --git a/src/movepick.h b/src/movepick.h index ab1c0ade..839d1bd2 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -59,8 +59,7 @@ public: PH_STOP }; - MovePicker(Position &p, bool pvnode, Move ttm, Move mk, Move k1, Move k2, - Depth dpth); + MovePicker(const Position& p, bool pvnode, Move ttm, Move mk, Move k1, Move k2, Depth d); Move get_next_move(); Move get_next_move(Lock &lock); int number_of_moves() const; @@ -77,7 +76,7 @@ private: void score_qcaptures(); Move pick_move_from_list(); - Position *pos; + const Position& pos; Move ttMove, mateKiller, killer1, killer2; Bitboard pinned, dc; MoveStack moves[256], badCaptures[64]; -- 2.39.2 From 173ecc0acf672ca83b5accda121ec5379e0023fd Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 17 Oct 2008 06:14:21 +0200 Subject: [PATCH 03/16] Use MVV to score captures when see >=0 This fix a couple of dubious bugs in MVV/LVA ordering. Tests seems to confirm now is slightly better. Signed-off-by: Marco Costalba --- src/movepick.cpp | 26 +++++++++----------------- 1 file changed, 9 insertions(+), 17 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index 4b1fccc4..0017353c 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -125,7 +125,7 @@ Move MovePicker::get_next_move() { { assert(move_is_ok(mateKiller)); if (generate_move_if_legal(pos, mateKiller, pinned) != MOVE_NONE) - return ttMove; + return mateKiller; } break; @@ -218,10 +218,9 @@ void MovePicker::score_captures() { moves[i].score = pos.see(m); if (moves[i].score >= 0) { - moves[i].score = move_promotion(m) ? QueenValueMidgame - : int(pos.midgame_value_of_piece_on(move_to(m))) - -int(pos.type_of_piece_on(move_from(m))); - // FIXME second term seems wrong ! + moves[i].score = HistoryMax; + moves[i].score += move_promotion(m) ? QueenValueMidgame + : pos.midgame_value_of_piece_on(move_to(m)); } } } @@ -267,14 +266,12 @@ void MovePicker::score_evasions() { void MovePicker::score_qcaptures() { - // Use MVV/LVA ordering. + // Use MVV/LVA ordering for (int i = 0; i < numOfMoves; i++) { Move m = moves[i].move; moves[i].score = move_promotion(m) ? QueenValueMidgame - : int(pos.midgame_value_of_piece_on(move_to(m))) - -int(pos.midgame_value_of_piece_on(move_to(m))) / 64; - // FIXME Why second term like that ??? + : pos.midgame_value_of_piece_on(move_to(m)); } } @@ -423,10 +420,7 @@ Move MovePicker::pick_move_from_list() { { move = moves[bestIndex].move; moves[bestIndex] = moves[movesPicked++]; - // Remember to change the line below if we decide to hash the qsearch! - // Maybe also postpone the legality check until after futility pruning? - // FIXME !!! - if (/* move != ttMove && */ pos.move_is_legal(move, pinned)) + if (move != ttMove && pos.move_is_legal(move, pinned)) return move; } } @@ -439,10 +433,8 @@ Move MovePicker::pick_move_from_list() { // move here? FIXME while (movesPicked < numOfMoves) { - move = moves[movesPicked++].move; - // Remember to change the line below if we decide to hash the qsearch! - // FIXME !!! - if (/* move != ttMove && */ pos.move_is_legal(move, pinned)) + move = moves[movesPicked++].move; + if (move != ttMove && pos.move_is_legal(move, pinned)) return move; } break; -- 2.39.2 From 06d6468ce9f660d4e901096780b3282eb5652984 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 17 Oct 2008 07:58:36 +0200 Subject: [PATCH 04/16] Test with see Signed-off-by: Marco Costalba --- src/movepick.cpp | 13 +++++-------- 1 file changed, 5 insertions(+), 8 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index 0017353c..e7ae8c36 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -203,7 +203,7 @@ Move MovePicker::get_next_move(Lock &lock) { /// MovePicker::pick_move_from_list(). void MovePicker::score_captures() { - // Winning and equal captures in the main search are ordered by MVV/LVA. + // Winning and equal captures in the main search are ordered by MVV. // Suprisingly, this appears to perform slightly better than SEE based // move ordering. The reason is probably that in a position with a winning // capture, capturing a more valuable (but sufficiently defended) piece @@ -216,12 +216,9 @@ void MovePicker::score_captures() { { Move m = moves[i].move; moves[i].score = pos.see(m); - if (moves[i].score >= 0) - { - moves[i].score = HistoryMax; - moves[i].score += move_promotion(m) ? QueenValueMidgame - : pos.midgame_value_of_piece_on(move_to(m)); - } + //if (moves[i].score >= 0) + // moves[i].score = move_promotion(m) ? QueenValueMidgame + // : pos.midgame_value_of_piece_on(move_to(m)); } } @@ -266,7 +263,7 @@ void MovePicker::score_evasions() { void MovePicker::score_qcaptures() { - // Use MVV/LVA ordering + // Use MVV ordering for (int i = 0; i < numOfMoves; i++) { Move m = moves[i].move; -- 2.39.2 From cf8ee79b767771bfb9c0ad06de1362400ea0ee5d Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 17 Oct 2008 08:25:39 +0200 Subject: [PATCH 05/16] Movepick: add and use find_best_index() helper This removes a bunch of redundant code. No functional change. Signed-off-by: Marco Costalba --- src/movepick.cpp | 64 ++++++++++++++++++++---------------------------- src/movepick.h | 1 + 2 files changed, 27 insertions(+), 38 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index e7ae8c36..9a389c6b 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -73,11 +73,11 @@ MovePicker::MovePicker(const Position& p, bool pvnode, Move ttm, Move mk, numOfBadCaptures = 0; dc = p.discovered_check_candidates(p.side_to_move()); - if(p.is_check()) + if (p.is_check()) phaseIndex = EvasionsPhaseIndex; - else if(depth > Depth(0)) + else if (depth > Depth(0)) phaseIndex = MainSearchPhaseIndex; - else if(depth == Depth(0)) + else if (depth == Depth(0)) phaseIndex = QsearchWithChecksPhaseIndex; else phaseIndex = QsearchWithoutChecksPhaseIndex; @@ -273,6 +273,23 @@ void MovePicker::score_qcaptures() { } +/// find_best_index() loops across the moves and returns index of +/// the highest scored one. + +int MovePicker::find_best_index() { + + int bestScore = -10000000, bestIndex = -1; + + for (int i = movesPicked; i < numOfMoves; i++) + if (moves[i].score > bestScore) + { + bestIndex = i; + bestScore = moves[i].score; + } + return bestIndex; +} + + /// MovePicker::pick_move_from_list() picks the move with the biggest score /// from a list of generated moves (moves[] or badCaptures[], depending on /// the current move generation phase). It takes care not to return the @@ -283,7 +300,6 @@ void MovePicker::score_qcaptures() { Move MovePicker::pick_move_from_list() { - int bestScore = -10000000; int bestIndex; Move move; @@ -294,7 +310,7 @@ Move MovePicker::pick_move_from_list() { assert(movesPicked >= 0); while (movesPicked < numOfMoves) { - bestScore = -10000000; + int bestScore = -10000000; bestIndex = -1; for (int i = movesPicked; i < numOfMoves; i++) { @@ -305,7 +321,7 @@ Move MovePicker::pick_move_from_list() { badCaptures[numOfBadCaptures++] = moves[i]; moves[i--] = moves[--numOfMoves]; } - else if (moves[i].score > bestScore) + else if (moves[i].score > bestScore) // FIXME >= 0 ?? { bestIndex = i; bestScore = moves[i].score; @@ -332,18 +348,7 @@ Move MovePicker::pick_move_from_list() { // the entire move list for the best move. If many moves have already // been searched and it is not a PV node, we are probably failing low // anyway, so we just pick the first move from the list. - if (pvNode || movesPicked < 12) - { - bestScore = -10000000; - bestIndex = -1; - for (int i = movesPicked; i < numOfMoves; i++) - if(moves[i].score > bestScore) - { - bestIndex = i; - bestScore = moves[i].score; - } - } else - bestIndex = movesPicked; + bestIndex = (pvNode || movesPicked < 12 ? find_best_index() : movesPicked); if (bestIndex != -1) { @@ -362,14 +367,7 @@ Move MovePicker::pick_move_from_list() { assert(movesPicked >= 0); while (movesPicked < numOfMoves) { - bestScore = -10000000; - bestIndex = -1; - for (int i = movesPicked; i < numOfMoves; i++) - if (moves[i].score > bestScore) - { - bestIndex = i; - bestScore = moves[i].score; - } + bestIndex = find_best_index(); if (bestIndex != -1) { @@ -400,18 +398,8 @@ Move MovePicker::pick_move_from_list() { assert(movesPicked >= 0); while (movesPicked < numOfMoves) { - bestScore = -10000000; - if (movesPicked < 4) // FIXME makes sens to score qcaps? - { - bestIndex = -1; - for (int i = movesPicked; i < numOfMoves; i++) - if(moves[i].score > bestScore) - { - bestIndex = i; - bestScore = moves[i].score; - } - } else - bestIndex = movesPicked; + // FIXME makes sens to score qcaps? + bestIndex = (movesPicked < 4 ? find_best_index() : movesPicked); if (bestIndex != -1) { diff --git a/src/movepick.h b/src/movepick.h index 839d1bd2..af34711d 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -75,6 +75,7 @@ private: void score_evasions(); void score_qcaptures(); Move pick_move_from_list(); + int find_best_index(); const Position& pos; Move ttMove, mateKiller, killer1, killer2; -- 2.39.2 From 158911425bd35e9a95ff7a4c1e65f2ec834e7b5c Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 17 Oct 2008 15:11:19 +0200 Subject: [PATCH 06/16] Space inflate movegen.cpp Signed-off-by: Marco Costalba --- src/movegen.cpp | 478 ++++++++++++++++++++++------------------------- src/movepick.cpp | 12 +- 2 files changed, 234 insertions(+), 256 deletions(-) diff --git a/src/movegen.cpp b/src/movegen.cpp index abcafc00..fee25e28 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -32,21 +32,16 @@ namespace { - int generate_white_pawn_captures(const Position &pos, MoveStack *mlist); - int generate_black_pawn_captures(const Position &pos, MoveStack *mlist); - int generate_white_pawn_noncaptures(const Position &pos, MoveStack *mlist); - int generate_black_pawn_noncaptures(const Position &pos, MoveStack *mlist); - int generate_knight_moves(const Position &pos, MoveStack *mlist, - Color side, Bitboard target); - int generate_bishop_moves(const Position &pos, MoveStack *mlist, - Color side, Bitboard target); - int generate_rook_moves(const Position &pos, MoveStack *mlist, - Color side, Bitboard target); - int generate_queen_moves(const Position &pos, MoveStack *mlist, - Color side, Bitboard target); - int generate_king_moves(const Position &pos, MoveStack *mlist, - Square from, Bitboard target); - int generate_castle_moves(const Position &pos, MoveStack *mlist, Color us); + int generate_white_pawn_captures(const Position&, MoveStack*); + int generate_black_pawn_captures(const Position&, MoveStack*); + int generate_white_pawn_noncaptures(const Position&, MoveStack*); + int generate_black_pawn_noncaptures(const Position&, MoveStack*); + int generate_knight_moves(const Position&, MoveStack*, Color side, Bitboard t); + int generate_bishop_moves(const Position&, MoveStack*, Color side, Bitboard t); + int generate_rook_moves(const Position&, MoveStack*, Color side, Bitboard t); + int generate_queen_moves(const Position&, MoveStack*, Color side, Bitboard t); + int generate_king_moves(const Position&, MoveStack*, Square from, Bitboard t); + int generate_castle_moves(const Position&, MoveStack*, Color us); } @@ -59,24 +54,25 @@ namespace { /// generate_captures generates() all pseudo-legal captures and queen /// promotions. The return value is the number of moves generated. -int generate_captures(const Position &pos, MoveStack *mlist) { - Color us = pos.side_to_move(); - Bitboard target = pos.pieces_of_color(opposite_color(us)); - int n = 0; +int generate_captures(const Position& pos, MoveStack* mlist) { assert(pos.is_ok()); assert(!pos.is_check()); - if(us == WHITE) - n += generate_white_pawn_captures(pos, mlist); + Color us = pos.side_to_move(); + Bitboard target = pos.pieces_of_color(opposite_color(us)); + int n; + + if (us == WHITE) + n = generate_white_pawn_captures(pos, mlist); else - n += generate_black_pawn_captures(pos, mlist); + n = generate_black_pawn_captures(pos, mlist); + n += generate_knight_moves(pos, mlist+n, us, target); n += generate_bishop_moves(pos, mlist+n, us, target); n += generate_rook_moves(pos, mlist+n, us, target); n += generate_queen_moves(pos, mlist+n, us, target); n += generate_king_moves(pos, mlist+n, pos.king_square(us), target); - return n; } @@ -84,25 +80,26 @@ int generate_captures(const Position &pos, MoveStack *mlist) { /// 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) { - Color us = pos.side_to_move(); - Bitboard target = pos.empty_squares(); - int n = 0; +int generate_noncaptures(const Position& pos, MoveStack *mlist) { assert(pos.is_ok()); assert(!pos.is_check()); - if(us == WHITE) - n += generate_white_pawn_noncaptures(pos, mlist); + Color us = pos.side_to_move(); + Bitboard target = pos.empty_squares(); + int n; + + if (us == WHITE) + n = generate_white_pawn_noncaptures(pos, mlist); else - n += generate_black_pawn_noncaptures(pos, mlist); + n = generate_black_pawn_noncaptures(pos, mlist); + n += generate_knight_moves(pos, mlist+n, us, target); n += generate_bishop_moves(pos, mlist+n, us, target); n += generate_rook_moves(pos, mlist+n, us, target); n += generate_queen_moves(pos, mlist+n, us, target); n += generate_king_moves(pos, mlist+n, pos.king_square(us), target); n += generate_castle_moves(pos, mlist+n, us); - return n; } @@ -111,15 +108,16 @@ int generate_noncaptures(const Position &pos, MoveStack *mlist) { /// checks, except castling moves (will add this later). It returns the /// number of generated moves. -int generate_checks(const Position &pos, MoveStack *mlist, Bitboard dc) { +int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { + + assert(pos.is_ok()); + assert(!pos.is_check()); + Color us, them; Square ksq, from, to; Bitboard empty, checkSqs, b1, b2, b3; int n = 0; - assert(pos.is_ok()); - assert(!pos.is_check()); - us = pos.side_to_move(); them = opposite_color(us); @@ -132,7 +130,8 @@ int generate_checks(const Position &pos, MoveStack *mlist, Bitboard dc) { // Pawn moves. This is somewhat messy, and we use separate code for white // and black, because we can't shift by negative numbers in C/C++. :-( - if(us == WHITE) { + if (us == WHITE) + { // Pawn moves which give 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. @@ -338,15 +337,16 @@ int generate_checks(const Position &pos, MoveStack *mlist, Bitboard dc) { /// function is very ugly, and needs cleaning up some time later. FIXME int generate_evasions(const Position &pos, MoveStack *mlist) { + + assert(pos.is_ok()); + assert(pos.is_check()); + Color us, them; Bitboard checkers = pos.checkers(); Bitboard pinned, b1, b2; Square ksq, from, to; int n = 0; - assert(pos.is_ok()); - assert(pos.is_check()); - us = pos.side_to_move(); them = opposite_color(us); @@ -575,27 +575,25 @@ int generate_evasions(const Position &pos, MoveStack *mlist) { /// 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) { +int generate_legal_moves(const Position& pos, MoveStack* mlist) { + assert(pos.is_ok()); - if(pos.is_check()) - return generate_evasions(pos, mlist); - else { - int i, n; - Bitboard pinned = pos.pinned_pieces(pos.side_to_move()); + if (pos.is_check()) + return generate_evasions(pos, mlist); - // Generate pseudo-legal moves: - n = generate_captures(pos, mlist); - n += generate_noncaptures(pos, mlist + n); + // Generate pseudo-legal moves: + int n = generate_captures(pos, mlist); + n += generate_noncaptures(pos, mlist + n); - // Remove illegal moves from the list: - for(i = 0; i < n; i++) { - if(!pos.move_is_legal(mlist[i].move, pinned)) - mlist[i--].move = mlist[--n].move; - } + Bitboard pinned = pos.pinned_pieces(pos.side_to_move()); - return n; - } + // Remove illegal moves from the list: + for (int i = 0; i < n; i++) + if (!pos.move_is_legal(mlist[i].move, pinned)) + mlist[i--].move = mlist[--n].move; + + return n; } @@ -606,255 +604,235 @@ int generate_legal_moves(const Position &pos, MoveStack *mlist) { /// only be used when the side to move is not in check. Move generate_move_if_legal(const Position &pos, Move m, Bitboard pinned) { - Color us, them; - Square from, to; - Piece pc; assert(pos.is_ok()); assert(!pos.is_check()); assert(move_is_ok(m)); - us = pos.side_to_move(); - them = opposite_color(us); - from = move_from(m); - pc = pos.piece_on(from); + Color us = pos.side_to_move(); + Color them = opposite_color(us); + Square from = move_from(m); + Piece pc = pos.piece_on(from); // If the from square is not occupied by a piece belonging to the side to // move, the move is obviously not legal. - if(color_of_piece(pc) != us ) - return MOVE_NONE; + if (color_of_piece(pc) != us) + return MOVE_NONE; - to = move_to(m); + Square to = move_to(m); - // En passant moves: - if(move_is_ep(m)) { + // En passant moves + if (move_is_ep(m)) + { + // The piece must be a pawn and destination square must be the + // en passant square. + if ( type_of_piece(pc) != PAWN + || to != pos.ep_square()) + return MOVE_NONE; - // The piece must be a pawn: - if(type_of_piece(pc) != PAWN) - return MOVE_NONE; + assert(pos.square_is_empty(to)); + assert(pos.piece_on(to - pawn_push(us)) == pawn_of_color(them)); - // The destination square must be the en passant square: - if(to != pos.ep_square()) - return MOVE_NONE; + // The move is pseudo-legal. If it is legal, return it. + return (pos.move_is_legal(m) ? m : MOVE_NONE); + } - assert(pos.square_is_empty(to)); - assert(pos.piece_on(to - pawn_push(us)) == pawn_of_color(them)); + // Castling moves + if (move_is_short_castle(m)) + { + // The piece must be a king and side to move must still have + // the right to castle kingside. + if ( type_of_piece(pc) != KING + ||!pos.can_castle_kingside(us)) + return MOVE_NONE; - // The move is pseudo-legal. If it is legal, return it. - if(pos.move_is_legal(m)) - return m; - else - return MOVE_NONE; + assert(from == pos.king_square(us)); + assert(to == pos.initial_kr_square(us)); + assert(pos.piece_on(to) == rook_of_color(us)); + + Square g1 = relative_square(us, SQ_G1); + Square f1 = relative_square(us, SQ_F1); + Square s; + bool illegal = false; + + // Check if any of the squares between king and rook + // is occupied or under attack. + for (s = Min(from, g1); s <= Max(from, g1); s++) + if ( (s != from && s != to && !pos.square_is_empty(s)) + || pos.square_is_attacked(s, them)) + illegal = true; + + // Check if any of the squares between king and rook + // is occupied. + for (s = Min(to, f1); s <= Max(to, f1); s++) + if (s != from && s != to && !pos.square_is_empty(s)) + illegal = true; + + return (!illegal ? m : MOVE_NONE); } - // Castling moves: - else if(move_is_short_castle(m)) { + if (move_is_long_castle(m)) + { + // The piece must be a king and side to move must still have + // the right to castle kingside. + if ( type_of_piece(pc) != KING + ||!pos.can_castle_queenside(us)) + return MOVE_NONE; - // The piece must be a king: - if(type_of_piece(pc) != KING) - return MOVE_NONE; + assert(from == pos.king_square(us)); + assert(to == pos.initial_qr_square(us)); + assert(pos.piece_on(to) == rook_of_color(us)); - // The side to move must still have the right to castle kingside: - if(!pos.can_castle_kingside(us)) - return MOVE_NONE; + Square c1 = relative_square(us, SQ_C1); + Square d1 = relative_square(us, SQ_D1); + Square s; + bool illegal = false; - assert(from == pos.king_square(us)); - assert(to == pos.initial_kr_square(us)); - assert(pos.piece_on(to) == rook_of_color(us)); - - Square g1 = relative_square(us, SQ_G1); - Square f1 = relative_square(us, SQ_F1); - Square s; - bool illegal = false; - - for(s = Min(from, g1); s <= Max(from, g1); s++) - if((s != from && s != to && !pos.square_is_empty(s)) || - pos.square_is_attacked(s, them)) - illegal = true; - for(s = Min(to, f1); s <= Max(to, f1); s++) - if(s != from && s != to && !pos.square_is_empty(s)) - illegal = true; - - if(!illegal) - return m; - else - return MOVE_NONE; - } - else if(move_is_long_castle(m)) { + for (s = Min(from, c1); s <= Max(from, c1); s++) + if( (s != from && s != to && !pos.square_is_empty(s)) + || pos.square_is_attacked(s, them)) + illegal = true; - // The piece must be a king: - if(type_of_piece(pc) != KING) - return MOVE_NONE; + for (s = Min(to, d1); s <= Max(to, d1); s++) + if(s != from && s != to && !pos.square_is_empty(s)) + illegal = true; - // The side to move must still have the right to castle kingside: - if(!pos.can_castle_queenside(us)) - return MOVE_NONE; + if ( square_file(to) == FILE_B + && ( pos.piece_on(to + DELTA_W) == rook_of_color(them) + || pos.piece_on(to + DELTA_W) == queen_of_color(them))) + illegal = true; - assert(from == pos.king_square(us)); - assert(to == pos.initial_qr_square(us)); - assert(pos.piece_on(to) == rook_of_color(us)); - - Square c1 = relative_square(us, SQ_C1); - Square d1 = relative_square(us, SQ_D1); - Square s; - bool illegal = false; - - for(s = Min(from, c1); s <= Max(from, c1); s++) - if((s != from && s != to && !pos.square_is_empty(s)) || - pos.square_is_attacked(s, them)) - illegal = true; - for(s = Min(to, d1); s <= Max(to, d1); s++) - if(s != from && s != to && !pos.square_is_empty(s)) - illegal = true; - if(square_file(to) == FILE_B && - (pos.piece_on(to + DELTA_W) == rook_of_color(them) || - pos.piece_on(to + DELTA_W) == queen_of_color(them))) - illegal = true; - - if(!illegal) - return m; - else - return MOVE_NONE; + return (!illegal ? m : MOVE_NONE); } // Normal moves - else { - // The destination square cannot be occupied by a friendly piece: - if(pos.color_of_piece_on(to) == us) + // The destination square cannot be occupied by a friendly piece + if (pos.color_of_piece_on(to) == us) return MOVE_NONE; - // Proceed according to the type of the moving piece. - switch(type_of_piece(pc)) { + // Proceed according to the type of the moving piece. + switch(type_of_piece(pc)) { - case PAWN: + case PAWN: // Pawn moves, as usual, are somewhat messy. - if(us == WHITE) { - // If the destination square is on the 8th rank, the move must be a - // promotion. - if(square_rank(to) == RANK_8 && !move_promotion(m)) - return MOVE_NONE; + if (us == WHITE) + { + // If the destination square is on the 8th rank, the move must + // be a promotion. + if (square_rank(to) == RANK_8 && !move_promotion(m)) + return MOVE_NONE; - // Proceed according to the square delta between the source and - // destionation squares. - switch(to - from) { - - case DELTA_NW: case DELTA_NE: - // Capture. The destination square must be occupied by an enemy piece - // (en passant captures was handled earlier). - if(pos.color_of_piece_on(to) != them) - return MOVE_NONE; - break; - - case DELTA_N: - // Pawn push. The destination square must be empty. - if(!pos.square_is_empty(to)) - return MOVE_NONE; - break; - - case DELTA_NN: + // Proceed according to the square delta between the source and + // destionation squares. + switch (to - from) + { + case DELTA_NW: + case DELTA_NE: + // Capture. The destination square must be occupied by an enemy + // piece (en passant captures was handled earlier). + if (pos.color_of_piece_on(to) != them) + return MOVE_NONE; + break; + + case DELTA_N: + // Pawn push. The destination square must be empty. + if (!pos.square_is_empty(to)) + return MOVE_NONE; + break; + + case DELTA_NN: // Double pawn push. The destination square must be on the fourth // rank, and both the destination square and the square between the // source and destination squares must be empty. - if(square_rank(to) != RANK_4 || !pos.square_is_empty(to) || - !pos.square_is_empty(from + DELTA_N)) - return MOVE_NONE; - break; + if ( square_rank(to) != RANK_4 + || !pos.square_is_empty(to) + || !pos.square_is_empty(from + DELTA_N)) + return MOVE_NONE; + break; - default: - return MOVE_NONE; + default: + return MOVE_NONE; } } - else { // (us == BLACK) - // If the destination square is on the 1st rank, the move must be a - // promotion. - if(square_rank(to) == RANK_1 && !move_promotion(m)) - return MOVE_NONE; + else // (us == BLACK) + { + // If the destination square is on the 1th rank, the move must + // be a promotion. + if (square_rank(to) == RANK_1 && !move_promotion(m)) + return MOVE_NONE; - // Proceed according to the square delta between the source and - // destionation squares. - switch(to - from) { + // Proceed according to the square delta between the source and + // destionation squares. + switch (to - from) + { + case DELTA_SW: + case DELTA_SE: + // Capture. The destination square must be occupied by an enemy + // piece (en passant captures was handled earlier). + if (pos.color_of_piece_on(to) != them) + return MOVE_NONE; + break; - case DELTA_SW: case DELTA_SE: - // Capture. The destination square must be occupied by an enemy piece - // (en passant captures was handled earlier). - if(pos.color_of_piece_on(to) != them) - return MOVE_NONE; - break; + case DELTA_S: + // Pawn push. The destination square must be empty. + if (!pos.square_is_empty(to)) + return MOVE_NONE; + break; - case DELTA_S: - // Pawn push. The destination square must be empty. - if(!pos.square_is_empty(to)) - return MOVE_NONE; - break; - - case DELTA_SS: + case DELTA_SS: // Double pawn push. The destination square must be on the fifth // rank, and both the destination square and the square between the // source and destination squares must be empty. - if(square_rank(to) != RANK_5 || !pos.square_is_empty(to) || - !pos.square_is_empty(from + DELTA_S)) - return MOVE_NONE; - break; + if ( square_rank(to) != RANK_5 + || !pos.square_is_empty(to) + || !pos.square_is_empty(from + DELTA_S)) + return MOVE_NONE; + break; - default: - return MOVE_NONE; - } + default: + return MOVE_NONE; + } } // The move is pseudo-legal. Return it if it is legal. - if(pos.move_is_legal(m)) - return m; - else - return MOVE_NONE; + return (pos.move_is_legal(m) ? m : MOVE_NONE); break; - case KNIGHT: - if(pos.knight_attacks_square(from, to) && pos.move_is_legal(m) && - !move_promotion(m)) - return m; - else - return MOVE_NONE; - break; + case KNIGHT: + return ( pos.knight_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; - case BISHOP: - if(pos.bishop_attacks_square(from, to) && pos.move_is_legal(m) && - !move_promotion(m)) - return m; - else - return MOVE_NONE; - break; + case BISHOP: + return ( pos.bishop_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; - case ROOK: - if(pos.rook_attacks_square(from, to) && pos.move_is_legal(m) && - !move_promotion(m)) - return m; - else - return MOVE_NONE; - break; + case ROOK: + return ( pos.rook_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; - case QUEEN: - if(pos.queen_attacks_square(from, to) && pos.move_is_legal(m) && - !move_promotion(m)) - return m; - else - return MOVE_NONE; - break; + case QUEEN: + return ( pos.queen_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; - case KING: - if(pos.king_attacks_square(from, to) && pos.move_is_legal(m) && - !move_promotion(m)) - return m; - else - return MOVE_NONE; - break; + case KING: + return ( pos.king_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; - default: - assert(false); + default: + assert(false); } - } - - assert(false); - return MOVE_NONE; + assert(false); + return MOVE_NONE; } diff --git a/src/movepick.cpp b/src/movepick.cpp index 9a389c6b..c0ec8677 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -99,7 +99,7 @@ Move MovePicker::get_next_move() { while (true) { // If we already have a list of generated moves, pick the best move from - // the list, and return it: + // the list, and return it. move = pick_move_from_list(); if (move != MOVE_NONE) { @@ -107,7 +107,7 @@ Move MovePicker::get_next_move() { return move; } - // Next phase: + // Next phase phaseIndex++; switch (PhaseTable[phaseIndex]) { @@ -199,8 +199,7 @@ Move MovePicker::get_next_move(Lock &lock) { /// MovePicker::score_captures(), MovePicker::score_noncaptures(), /// MovePicker::score_evasions() and MovePicker::score_qcaptures() assign a /// numerical move ordering score to each move in a move list. The moves -/// with highest scores will be picked first by -/// MovePicker::pick_move_from_list(). +/// with highest scores will be picked first by pick_move_from_list(). void MovePicker::score_captures() { // Winning and equal captures in the main search are ordered by MVV. @@ -321,7 +320,7 @@ Move MovePicker::pick_move_from_list() { badCaptures[numOfBadCaptures++] = moves[i]; moves[i--] = moves[--numOfMoves]; } - else if (moves[i].score > bestScore) // FIXME >= 0 ?? + else if (moves[i].score > bestScore) { bestIndex = i; bestScore = moves[i].score; @@ -348,7 +347,7 @@ Move MovePicker::pick_move_from_list() { // the entire move list for the best move. If many moves have already // been searched and it is not a PV node, we are probably failing low // anyway, so we just pick the first move from the list. - bestIndex = (pvNode || movesPicked < 12 ? find_best_index() : movesPicked); + bestIndex = (movesPicked < 12 || pvNode ? find_best_index() : movesPicked); if (bestIndex != -1) { @@ -435,6 +434,7 @@ Move MovePicker::pick_move_from_list() { /// picked next move. It can be used in search to further differentiate /// according to the current move type: capture, non capture, escape, etc. MovePicker::MovegenPhase MovePicker::current_move_type() const { + return PhaseTable[phaseIndex]; } -- 2.39.2 From 8be2c483a1d71865cda6f737d72fa11b64f73dd5 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 17 Oct 2008 15:38:00 +0200 Subject: [PATCH 07/16] Unify black and white code in generate_move_if_legal() Signed-off-by: Marco Costalba --- src/movegen.cpp | 188 +++++++++++++++++++++--------------------------- 1 file changed, 80 insertions(+), 108 deletions(-) diff --git a/src/movegen.cpp b/src/movegen.cpp index fee25e28..a2e9c9c9 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -712,127 +712,99 @@ Move generate_move_if_legal(const Position &pos, Move m, Bitboard pinned) { return MOVE_NONE; // Proceed according to the type of the moving piece. - switch(type_of_piece(pc)) { - + switch (type_of_piece(pc)) + { case PAWN: - // Pawn moves, as usual, are somewhat messy. - if (us == WHITE) + // If the destination square is on the 8/1th rank, the move must + // be a promotion. + if ( ( (square_rank(to) == RANK_8 && us == WHITE) + ||(square_rank(to) == RANK_1 && us != WHITE)) + && !move_promotion(m)) + return MOVE_NONE; + + // Proceed according to the square delta between the source and + // destionation squares. + switch (to - from) { - // If the destination square is on the 8th rank, the move must - // be a promotion. - if (square_rank(to) == RANK_8 && !move_promotion(m)) - return MOVE_NONE; - - // Proceed according to the square delta between the source and - // destionation squares. - switch (to - from) - { - case DELTA_NW: - case DELTA_NE: - // Capture. The destination square must be occupied by an enemy - // piece (en passant captures was handled earlier). - if (pos.color_of_piece_on(to) != them) - return MOVE_NONE; - break; - - case DELTA_N: - // Pawn push. The destination square must be empty. - if (!pos.square_is_empty(to)) - return MOVE_NONE; - break; - - case DELTA_NN: - // Double pawn push. The destination square must be on the fourth - // rank, and both the destination square and the square between the - // source and destination squares must be empty. - if ( square_rank(to) != RANK_4 - || !pos.square_is_empty(to) - || !pos.square_is_empty(from + DELTA_N)) - return MOVE_NONE; - break; - - default: + case DELTA_NW: + case DELTA_NE: + case DELTA_SW: + case DELTA_SE: + // Capture. The destination square must be occupied by an enemy + // piece (en passant captures was handled earlier). + if (pos.color_of_piece_on(to) != them) return MOVE_NONE; - } - } - else // (us == BLACK) - { - // If the destination square is on the 1th rank, the move must - // be a promotion. - if (square_rank(to) == RANK_1 && !move_promotion(m)) + break; + + case DELTA_N: + case DELTA_S: + // Pawn push. The destination square must be empty. + if (!pos.square_is_empty(to)) return MOVE_NONE; - - // Proceed according to the square delta between the source and - // destionation squares. - switch (to - from) - { - case DELTA_SW: - case DELTA_SE: - // Capture. The destination square must be occupied by an enemy - // piece (en passant captures was handled earlier). - if (pos.color_of_piece_on(to) != them) - return MOVE_NONE; - break; - - case DELTA_S: - // Pawn push. The destination square must be empty. - if (!pos.square_is_empty(to)) - return MOVE_NONE; - break; - - case DELTA_SS: - // Double pawn push. The destination square must be on the fifth - // rank, and both the destination square and the square between the - // source and destination squares must be empty. - if ( square_rank(to) != RANK_5 - || !pos.square_is_empty(to) - || !pos.square_is_empty(from + DELTA_S)) - return MOVE_NONE; - break; - - default: + break; + + case DELTA_NN: + // Double white pawn push. The destination square must be on the fourth + // rank, and both the destination square and the square between the + // source and destination squares must be empty. + if ( square_rank(to) != RANK_4 + || !pos.square_is_empty(to) + || !pos.square_is_empty(from + DELTA_N)) + return MOVE_NONE; + break; + + case DELTA_SS: + // Double black pawn push. The destination square must be on the fifth + // rank, and both the destination square and the square between the + // source and destination squares must be empty. + if ( square_rank(to) != RANK_5 + || !pos.square_is_empty(to) + || !pos.square_is_empty(from + DELTA_S)) return MOVE_NONE; - } + break; + + default: + return MOVE_NONE; } // The move is pseudo-legal. Return it if it is legal. return (pos.move_is_legal(m) ? m : MOVE_NONE); break; - case KNIGHT: - return ( pos.knight_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; - - case BISHOP: - return ( pos.bishop_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; - - case ROOK: - return ( pos.rook_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; - - case QUEEN: - return ( pos.queen_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; + case KNIGHT: + return ( pos.knight_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; + + case BISHOP: + return ( pos.bishop_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; + + case ROOK: + return ( pos.rook_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; - case KING: - return ( pos.king_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; + case QUEEN: + return ( pos.queen_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; - default: - assert(false); + case KING: + return ( pos.king_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); + break; + + default: + assert(false); } - assert(false); - return MOVE_NONE; + assert(false); + return MOVE_NONE; } -- 2.39.2 From c852a940094d4f685d7efa4d14ab7e95ddf7ebd2 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 17 Oct 2008 22:52:36 +0200 Subject: [PATCH 08/16] Movegen: further simplify generate_move_if_legal Signed-off-by: Marco Costalba --- src/movegen.cpp | 48 ++++++++---------------------------------------- 1 file changed, 8 insertions(+), 40 deletions(-) diff --git a/src/movegen.cpp b/src/movegen.cpp index a2e9c9c9..9474bb76 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -712,9 +712,8 @@ Move generate_move_if_legal(const Position &pos, Move m, Bitboard pinned) { return MOVE_NONE; // Proceed according to the type of the moving piece. - switch (type_of_piece(pc)) - { - case PAWN: + if (type_of_piece(pc) == PAWN) + { // If the destination square is on the 8/1th rank, the move must // be a promotion. if ( ( (square_rank(to) == RANK_8 && us == WHITE) @@ -768,43 +767,12 @@ Move generate_move_if_legal(const Position &pos, Move m, Bitboard pinned) { } // The move is pseudo-legal. Return it if it is legal. return (pos.move_is_legal(m) ? m : MOVE_NONE); - break; + } - case KNIGHT: - return ( pos.knight_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; - - case BISHOP: - return ( pos.bishop_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; - - case ROOK: - return ( pos.rook_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; - - case QUEEN: - return ( pos.queen_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; - - case KING: - return ( pos.king_attacks_square(from, to) - && pos.move_is_legal(m) - && !move_promotion(m) ? m : MOVE_NONE); - break; - - default: - assert(false); - } - assert(false); - return MOVE_NONE; + // Luckly we can handle all the other pieces in one go + return ( pos.piece_attacks_square(from, to) + && pos.move_is_legal(m) + && !move_promotion(m) ? m : MOVE_NONE); } @@ -1039,7 +1007,7 @@ namespace { return n; } - + int generate_knight_moves(const Position &pos, MoveStack *mlist, Color side, Bitboard target) { Square from, to; -- 2.39.2 From 94f1b31484c2415b19a43f385e92cd1cb4bd7ecc Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 17 Oct 2008 22:54:23 +0200 Subject: [PATCH 09/16] movegen: revert see ordering in score_captures() It works better with MVV ordering. Signed-off-by: Marco Costalba --- src/movepick.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/src/movepick.cpp b/src/movepick.cpp index c0ec8677..1024cbff 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -215,9 +215,9 @@ void MovePicker::score_captures() { { Move m = moves[i].move; moves[i].score = pos.see(m); - //if (moves[i].score >= 0) - // moves[i].score = move_promotion(m) ? QueenValueMidgame - // : pos.midgame_value_of_piece_on(move_to(m)); + if (moves[i].score >= 0) + moves[i].score = move_promotion(m) ? QueenValueMidgame + : pos.midgame_value_of_piece_on(move_to(m)); } } -- 2.39.2 From aa7121297de97ee0f449d7a265d91796ac3d8843 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 17 Oct 2008 23:30:34 +0200 Subject: [PATCH 10/16] Use pointer-to-members to remove a bunch of duplicated code Remove all generate_XXX_moves() functions, use an array of pointer to members instead. Signed-off-by: Marco Costalba --- src/main.cpp | 1 + src/movegen.cpp | 95 ++++++++++-------------------------------------- src/position.cpp | 10 +++++ src/position.h | 5 +++ 4 files changed, 35 insertions(+), 76 deletions(-) diff --git a/src/main.cpp b/src/main.cpp index e89fee0e..9979e851 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -52,6 +52,7 @@ int main(int argc, char *argv[]) { // Initialization + init_piece_attacks_fn(); init_mersenne(); init_direction_table(); init_bitboards(); diff --git a/src/movegen.cpp b/src/movegen.cpp index 9474bb76..b6bf6b24 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -36,10 +36,7 @@ namespace { int generate_black_pawn_captures(const Position&, MoveStack*); int generate_white_pawn_noncaptures(const Position&, MoveStack*); int generate_black_pawn_noncaptures(const Position&, MoveStack*); - int generate_knight_moves(const Position&, MoveStack*, Color side, Bitboard t); - int generate_bishop_moves(const Position&, MoveStack*, Color side, Bitboard t); - int generate_rook_moves(const Position&, MoveStack*, Color side, Bitboard t); - int generate_queen_moves(const Position&, MoveStack*, Color side, Bitboard t); + int generate_piece_moves(PieceType, const Position&, MoveStack*, Color side, Bitboard t); int generate_king_moves(const Position&, MoveStack*, Square from, Bitboard t); int generate_castle_moves(const Position&, MoveStack*, Color us); @@ -68,10 +65,9 @@ int generate_captures(const Position& pos, MoveStack* mlist) { else n = generate_black_pawn_captures(pos, mlist); - n += generate_knight_moves(pos, mlist+n, us, target); - n += generate_bishop_moves(pos, mlist+n, us, target); - n += generate_rook_moves(pos, mlist+n, us, target); - n += generate_queen_moves(pos, mlist+n, us, target); + for (PieceType pce = KNIGHT; pce < KING; pce++) + n += generate_piece_moves(pce, pos, mlist+n, us, target); + n += generate_king_moves(pos, mlist+n, pos.king_square(us), target); return n; } @@ -94,10 +90,9 @@ int generate_noncaptures(const Position& pos, MoveStack *mlist) { else n = generate_black_pawn_noncaptures(pos, mlist); - n += generate_knight_moves(pos, mlist+n, us, target); - n += generate_bishop_moves(pos, mlist+n, us, target); - n += generate_rook_moves(pos, mlist+n, us, target); - n += generate_queen_moves(pos, mlist+n, us, target); + for (PieceType pce = KNIGHT; pce < KING; pce++) + n += generate_piece_moves(pce, pos, mlist+n, us, target); + n += generate_king_moves(pos, mlist+n, pos.king_square(us), target); n += generate_castle_moves(pos, mlist+n, us); return n; @@ -1007,74 +1002,22 @@ namespace { return n; } - - int generate_knight_moves(const Position &pos, MoveStack *mlist, - Color side, Bitboard target) { - Square from, to; - Bitboard b; - int i, n = 0; - - for(i = 0; i < pos.knight_count(side); i++) { - from = pos.knight_list(side, i); - b = pos.knight_attacks(from) & target; - while(b) { - to = pop_1st_bit(&b); - mlist[n++].move = make_move(from, to); - } - } - return n; - } - - - int generate_bishop_moves(const Position &pos, MoveStack *mlist, - Color side, Bitboard target) { - Square from, to; - Bitboard b; - int i, n = 0; - - for(i = 0; i < pos.bishop_count(side); i++) { - from = pos.bishop_list(side, i); - b = pos.bishop_attacks(from) & target; - while(b) { - to = pop_1st_bit(&b); - mlist[n++].move = make_move(from, to); - } - } - return n; - } - - - int generate_rook_moves(const Position &pos, MoveStack *mlist, - Color side, Bitboard target) { - Square from, to; - Bitboard b; - int i, n = 0; - - for(i = 0; i < pos.rook_count(side); i++) { - from = pos.rook_list(side, i); - b = pos.rook_attacks(from) & target; - while(b) { - to = pop_1st_bit(&b); - mlist[n++].move = make_move(from, to); - } - } - return n; - } - - - int generate_queen_moves(const Position &pos, MoveStack *mlist, + int generate_piece_moves(PieceType piece, const Position &pos, MoveStack *mlist, Color side, Bitboard target) { Square from, to; Bitboard b; - int i, n = 0; + Piece_attacks_fn mem_fn = piece_attacks_fn[piece]; + int n = 0; - for(i = 0; i < pos.queen_count(side); i++) { - from = pos.queen_list(side, i); - b = pos.queen_attacks(from) & target; - while(b) { - to = pop_1st_bit(&b); - mlist[n++].move = make_move(from, to); - } + for (int i = 0; i < pos.piece_count(side, piece); i++) + { + from = pos.piece_list(side, piece, i); + b = (pos.*mem_fn)(from) & target; + while (b) + { + to = pop_1st_bit(&b); + mlist[n++].move = make_move(from, to); + } } return n; } diff --git a/src/position.cpp b/src/position.cpp index 7b39be15..f16d498f 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -48,11 +48,21 @@ Key Position::zobSideToMove; Value Position::MgPieceSquareTable[16][64]; Value Position::EgPieceSquareTable[16][64]; +Piece_attacks_fn piece_attacks_fn[7]; //// //// Functions //// +void init_piece_attacks_fn() { + + piece_attacks_fn[KNIGHT] = &Position::knight_attacks; + piece_attacks_fn[BISHOP] = &Position::bishop_attacks; + piece_attacks_fn[ROOK] = &Position::rook_attacks; + piece_attacks_fn[QUEEN] = &Position::queen_attacks; + piece_attacks_fn[KING] = &Position::king_attacks; +} + /// Constructors Position::Position(const Position &pos) { diff --git a/src/position.h b/src/position.h index 25596bf6..1c422088 100644 --- a/src/position.h +++ b/src/position.h @@ -370,6 +370,11 @@ private: }; +/// An array of member functions to dispatch attacks_square +typedef Bitboard (Position::* Piece_attacks_fn)(Square s) const; +extern Piece_attacks_fn piece_attacks_fn[7]; +extern void init_piece_attacks_fn(); + //// //// Inline functions //// -- 2.39.2 From 3b857d1625c87ae3b87ea9e960b2c8d2d3284b9a Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 18 Oct 2008 08:54:18 +0200 Subject: [PATCH 11/16] Use a const pointer-to-member array for attacks Allow the compiler to optimize member function access. Signed-off-by: Marco Costalba --- src/main.cpp | 1 - src/movegen.cpp | 4 ++-- src/position.cpp | 17 +++++++---------- src/position.h | 3 +-- 4 files changed, 10 insertions(+), 15 deletions(-) diff --git a/src/main.cpp b/src/main.cpp index 9979e851..e89fee0e 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -52,7 +52,6 @@ int main(int argc, char *argv[]) { // Initialization - init_piece_attacks_fn(); init_mersenne(); init_direction_table(); init_bitboards(); diff --git a/src/movegen.cpp b/src/movegen.cpp index b6bf6b24..2972eeee 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -1004,9 +1004,10 @@ namespace { int generate_piece_moves(PieceType piece, const Position &pos, MoveStack *mlist, Color side, Bitboard target) { + + const Piece_attacks_fn mem_fn = piece_attacks_fn[piece]; Square from, to; Bitboard b; - Piece_attacks_fn mem_fn = piece_attacks_fn[piece]; int n = 0; for (int i = 0; i < pos.piece_count(side, piece); i++) @@ -1095,5 +1096,4 @@ namespace { return n; } - } diff --git a/src/position.cpp b/src/position.cpp index f16d498f..6de3f08c 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -48,21 +48,18 @@ Key Position::zobSideToMove; Value Position::MgPieceSquareTable[16][64]; Value Position::EgPieceSquareTable[16][64]; -Piece_attacks_fn piece_attacks_fn[7]; +const Piece_attacks_fn piece_attacks_fn[] = + { 0, 0, + &Position::knight_attacks, + &Position::bishop_attacks, + &Position::rook_attacks, + &Position::queen_attacks, + &Position::king_attacks }; //// //// Functions //// -void init_piece_attacks_fn() { - - piece_attacks_fn[KNIGHT] = &Position::knight_attacks; - piece_attacks_fn[BISHOP] = &Position::bishop_attacks; - piece_attacks_fn[ROOK] = &Position::rook_attacks; - piece_attacks_fn[QUEEN] = &Position::queen_attacks; - piece_attacks_fn[KING] = &Position::king_attacks; -} - /// Constructors Position::Position(const Position &pos) { diff --git a/src/position.h b/src/position.h index 1c422088..5285c8f9 100644 --- a/src/position.h +++ b/src/position.h @@ -372,8 +372,7 @@ private: /// An array of member functions to dispatch attacks_square typedef Bitboard (Position::* Piece_attacks_fn)(Square s) const; -extern Piece_attacks_fn piece_attacks_fn[7]; -extern void init_piece_attacks_fn(); +extern const Piece_attacks_fn piece_attacks_fn[]; //// //// Inline functions -- 2.39.2 From ea16985ea5b6fc239f33aa333c0c0a6e8f2c7dcc Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 18 Oct 2008 09:49:51 +0200 Subject: [PATCH 12/16] Do not special case generate_king_moves() Teoretically a little slowdown. If after testing we verify the slowdown has impact on ELO we revert the change. Signed-off-by: Marco Costalba --- src/movegen.cpp | 23 +++-------------------- 1 file changed, 3 insertions(+), 20 deletions(-) diff --git a/src/movegen.cpp b/src/movegen.cpp index 2972eeee..71204af4 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -37,7 +37,6 @@ namespace { int generate_white_pawn_noncaptures(const Position&, MoveStack*); int generate_black_pawn_noncaptures(const Position&, MoveStack*); int generate_piece_moves(PieceType, const Position&, MoveStack*, Color side, Bitboard t); - int generate_king_moves(const Position&, MoveStack*, Square from, Bitboard t); int generate_castle_moves(const Position&, MoveStack*, Color us); } @@ -65,10 +64,9 @@ int generate_captures(const Position& pos, MoveStack* mlist) { else n = generate_black_pawn_captures(pos, mlist); - for (PieceType pce = KNIGHT; pce < KING; pce++) + for (PieceType pce = KNIGHT; pce <= KING; pce++) n += generate_piece_moves(pce, pos, mlist+n, us, target); - n += generate_king_moves(pos, mlist+n, pos.king_square(us), target); return n; } @@ -90,10 +88,9 @@ int generate_noncaptures(const Position& pos, MoveStack *mlist) { else n = generate_black_pawn_noncaptures(pos, mlist); - for (PieceType pce = KNIGHT; pce < KING; pce++) + for (PieceType pce = KNIGHT; pce <= KING; pce++) n += generate_piece_moves(pce, pos, mlist+n, us, target); - n += generate_king_moves(pos, mlist+n, pos.king_square(us), target); n += generate_castle_moves(pos, mlist+n, us); return n; } @@ -1002,6 +999,7 @@ namespace { return n; } + int generate_piece_moves(PieceType piece, const Position &pos, MoveStack *mlist, Color side, Bitboard target) { @@ -1024,21 +1022,6 @@ namespace { } - int generate_king_moves(const Position &pos, MoveStack *mlist, - Square from, Bitboard target) { - Square to; - Bitboard b; - int n = 0; - - b = pos.king_attacks(from) & target; - while(b) { - to = pop_1st_bit(&b); - mlist[n++].move = make_move(from, to); - } - return n; - } - - int generate_castle_moves(const Position &pos, MoveStack *mlist, Color us) { int n = 0; -- 2.39.2 From 146bb2dfa730841d8c00c162076423437af1377d Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 18 Oct 2008 10:57:27 +0200 Subject: [PATCH 13/16] Unify pieces check generation with generate_piece_checks() Could be slower: test needed! Signed-off-by: Marco Costalba --- src/movegen.cpp | 382 +++++++++++++++++++++++------------------------- 1 file changed, 182 insertions(+), 200 deletions(-) diff --git a/src/movegen.cpp b/src/movegen.cpp index 71204af4..f4ea0c6e 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -39,6 +39,8 @@ namespace { int generate_piece_moves(PieceType, const Position&, MoveStack*, Color side, Bitboard t); int generate_castle_moves(const Position&, MoveStack*, Color us); + int generate_piece_checks(PieceType pce, const Position& pos, Bitboard target, + Bitboard dc, Square ksq, MoveStack* mlist); } @@ -107,7 +109,7 @@ int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { Color us, them; Square ksq, from, to; - Bitboard empty, checkSqs, b1, b2, b3; + Bitboard empty, b1, b2, b3; int n = 0; us = pos.side_to_move(); @@ -124,45 +126,49 @@ int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { if (us == WHITE) { - // Pawn moves which give discovered check. This is possible only if the + // Pawn moves which give 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. - // Find all friendly pawns not on the enemy king's file: + // Find all friendly pawns not on the enemy king's file b1 = pos.pawns(us) & ~file_bb(ksq); - // Discovered checks, single pawn pushes: + // Discovered checks, single pawn pushes b2 = b3 = ((b1 & dc) << 8) & ~Rank8BB & empty; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_N, to); + while (b3) + { + to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - DELTA_N, to); } - // Discovered checks, double pawn pushes: + // Discovered checks, double pawn pushes b3 = ((b2 & Rank3BB) << 8) & empty; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to); + while (b3) + { + to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to); } - // Direct checks. These are possible only for pawns on neighboring files - // of the enemy king: + // Direct checks. These are possible only for pawns on neighboring files + // of the enemy king b1 &= (~dc & neighboring_files_bb(ksq)); - // Direct checks, single pawn pushes: + // Direct checks, single pawn pushes b2 = (b1 << 8) & empty; b3 = b2 & pos.black_pawn_attacks(ksq); - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_N, to); + while(b3) + { + to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - DELTA_N, to); } - // Direct checks, double pawn pushes: + // Direct checks, double pawn pushes b3 = ((b2 & Rank3BB) << 8) & empty & pos.black_pawn_attacks(ksq); - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to); + while (b3) + { + to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to); } } else { // (us == BLACK) @@ -174,147 +180,75 @@ int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { // Find all friendly pawns not on the enemy king's file: b1 = pos.pawns(us) & ~file_bb(ksq); - // Discovered checks, single pawn pushes: + // Discovered checks, single pawn pushes b2 = b3 = ((b1 & dc) >> 8) & ~Rank1BB & empty; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_S, to); + while (b3) + { + to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - DELTA_S, to); } - // Discovered checks, double pawn pushes: + // Discovered checks, double pawn pushes b3 = ((b2 & Rank6BB) >> 8) & empty; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to); + while (b3) + { + to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to); } // Direct checks. These are possible only for pawns on neighboring files - // of the enemy king: + // of the enemy king b1 &= (~dc & neighboring_files_bb(ksq)); // Direct checks, single pawn pushes: b2 = (b1 >> 8) & empty; b3 = b2 & pos.white_pawn_attacks(ksq); - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_S, to); + while (b3) + { + to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - DELTA_S, to); } - // Direct checks, double pawn pushes: + // Direct checks, double pawn pushes b3 = ((b2 & Rank6BB) >> 8) & empty & pos.black_pawn_attacks(ksq); - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to); + while (b3) + { + to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to); } } // Knight moves b1 = pos.knights(us); - if(b1) { - // Discovered knight checks: - b2 = b1 & dc; - while(b2) { - from = pop_1st_bit(&b2); - b3 = pos.knight_attacks(from) & empty; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(from, to); - } - } - - // Direct knight checks: - b2 = b1 & ~dc; - checkSqs = pos.knight_attacks(ksq) & empty; - while(b2) { - from = pop_1st_bit(&b2); - b3 = pos.knight_attacks(from) & checkSqs; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(from, to); - } - } - } + if (b1) + n += generate_piece_checks(KNIGHT, pos, b1, dc, ksq, mlist); // Bishop moves b1 = pos.bishops(us); - if(b1) { - // Discovered bishop checks: - b2 = b1 & dc; - while(b2) { - from = pop_1st_bit(&b2); - b3 = pos.bishop_attacks(from) & empty; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(from, to); - } - } - - // Direct bishop checks: - b2 = b1 & ~dc; - checkSqs = pos.bishop_attacks(ksq) & empty; - while(b2) { - from = pop_1st_bit(&b2); - b3 = pos.bishop_attacks(from) & checkSqs; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(from, to); - } - } - } + if (b1) + n += generate_piece_checks(BISHOP, pos, b1, dc, ksq, mlist); // Rook moves b1 = pos.rooks(us); - if(b1) { - // Discovered rook checks: - b2 = b1 & dc; - while(b2) { - from = pop_1st_bit(&b2); - b3 = pos.rook_attacks(from) & empty; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(from, to); - } - } - - // Direct rook checks: - b2 = b1 & ~dc; - checkSqs = pos.rook_attacks(ksq) & empty; - while(b2) { - from = pop_1st_bit(&b2); - b3 = pos.rook_attacks(from) & checkSqs; - while(b3) { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(from, to); - } - } - } + if (b1) + n += generate_piece_checks(ROOK, pos, b1, dc, ksq, mlist); // Queen moves b1 = pos.queens(us); - if(b1) { - // Discovered queen checks are impossible! - - // Direct queen checks: - checkSqs = pos.queen_attacks(ksq) & empty; - while(b1) { - from = pop_1st_bit(&b1); - b2 = pos.queen_attacks(from) & checkSqs; - while(b2) { - to = pop_1st_bit(&b2); - mlist[n++].move = make_move(from, to); - } - } - } + if (b1) + n += generate_piece_checks(QUEEN, pos, b1, dc, ksq, mlist); // King moves from = pos.king_square(us); - if(bit_is_set(dc, from)) { - b1 = pos.king_attacks(from) & empty & ~QueenPseudoAttacks[ksq]; - while(b1) { - to = pop_1st_bit(&b1); - mlist[n++].move = make_move(from, to); - } + if (bit_is_set(dc, from)) + { + b1 = pos.king_attacks(from) & empty & ~QueenPseudoAttacks[ksq]; + while (b1) + { + to = pop_1st_bit(&b1); + mlist[n++].move = make_move(from, to); + } } // TODO: Castling moves! @@ -771,132 +705,145 @@ Move generate_move_if_legal(const Position &pos, Move m, Bitboard pinned) { namespace { int generate_white_pawn_captures(const Position &pos, MoveStack *mlist) { + Bitboard pawns = pos.pawns(WHITE); Bitboard enemyPieces = pos.pieces_of_color(BLACK); - Bitboard b1, b2; Square sq; int n = 0; - // Captures in the a1-h8 direction: - b1 = (pawns << 9) & ~FileABB & enemyPieces; + // Captures in the a1-h8 direction + Bitboard b1 = (pawns << 9) & ~FileABB & enemyPieces; - // Promotions: - b2 = b1 & Rank8BB; - while(b2) { - sq = pop_1st_bit(&b2); - mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, QUEEN); + // Capturing promotions + Bitboard b2 = b1 & Rank8BB; + while (b2) + { + sq = pop_1st_bit(&b2); + mlist[n++].move = make_promotion_move(sq - DELTA_NE, sq, QUEEN); } - // Non-promotions: + // Capturing non-promotions b2 = b1 & ~Rank8BB; - while(b2) { - sq = pop_1st_bit(&b2); - mlist[n++].move = make_move(sq - DELTA_NE, sq); + while (b2) + { + sq = pop_1st_bit(&b2); + mlist[n++].move = make_move(sq - DELTA_NE, sq); } - // Captures in the h1-a8 direction: + // Captures in the h1-a8 direction b1 = (pawns << 7) & ~FileHBB & enemyPieces; - // Promotions: + // Capturing promotions b2 = b1 & Rank8BB; - while(b2) { - sq = pop_1st_bit(&b2); - mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, QUEEN); + while (b2) + { + sq = pop_1st_bit(&b2); + mlist[n++].move = make_promotion_move(sq - DELTA_NW, sq, QUEEN); } - // Non-promotions: + // Capturing non-promotions b2 = b1 & ~Rank8BB; - while(b2) { - sq = pop_1st_bit(&b2); - mlist[n++].move = make_move(sq - DELTA_NW, sq); + while (b2) + { + sq = pop_1st_bit(&b2); + mlist[n++].move = make_move(sq - DELTA_NW, sq); } - // Non-capturing promotions: + // Non-capturing promotions b1 = (pawns << 8) & pos.empty_squares() & Rank8BB; - while(b1) { - sq = pop_1st_bit(&b1); - mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, QUEEN); - } - - // En passant captures: - if(pos.ep_square() != SQ_NONE) { - assert(square_rank(pos.ep_square()) == RANK_6); - b1 = pawns & pos.black_pawn_attacks(pos.ep_square()); - assert(b1 != EmptyBoardBB); - while(b1) { + while (b1) + { sq = pop_1st_bit(&b1); - mlist[n++].move = make_ep_move(sq, pos.ep_square()); - } + mlist[n++].move = make_promotion_move(sq - DELTA_N, sq, QUEEN); } + // En passant captures + if (pos.ep_square() != SQ_NONE) + { + assert(square_rank(pos.ep_square()) == RANK_6); + b1 = pawns & pos.black_pawn_attacks(pos.ep_square()); + assert(b1 != EmptyBoardBB); + while (b1) + { + sq = pop_1st_bit(&b1); + mlist[n++].move = make_ep_move(sq, pos.ep_square()); + } + } return n; } int generate_black_pawn_captures(const Position &pos, MoveStack *mlist) { + Bitboard pawns = pos.pawns(BLACK); Bitboard enemyPieces = pos.pieces_of_color(WHITE); - Bitboard b1, b2; Square sq; int n = 0; - // Captures in the a8-h1 direction: - b1 = (pawns >> 7) & ~FileABB & enemyPieces; + // Captures in the a8-h1 direction + Bitboard b1 = (pawns >> 7) & ~FileABB & enemyPieces; - // Promotions: - b2 = b1 & Rank1BB; - while(b2) { - sq = pop_1st_bit(&b2); - mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, QUEEN); + // Capturing promotions + Bitboard b2 = b1 & Rank1BB; + while (b2) + { + sq = pop_1st_bit(&b2); + mlist[n++].move = make_promotion_move(sq - DELTA_SE, sq, QUEEN); } - // Non-promotions: + // Capturing non-promotions b2 = b1 & ~Rank1BB; - while(b2) { - sq = pop_1st_bit(&b2); - mlist[n++].move = make_move(sq - DELTA_SE, sq); + while (b2) + { + sq = pop_1st_bit(&b2); + mlist[n++].move = make_move(sq - DELTA_SE, sq); } - // Captures in the h8-a1 direction: + // Captures in the h8-a1 direction b1 = (pawns >> 9) & ~FileHBB & enemyPieces; - // Promotions: + // Capturing promotions b2 = b1 & Rank1BB; - while(b2) { - sq = pop_1st_bit(&b2); - mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, QUEEN); + while (b2) + { + sq = pop_1st_bit(&b2); + mlist[n++].move = make_promotion_move(sq - DELTA_SW, sq, QUEEN); } - // Non-promotions: + // Capturing Non-promotions b2 = b1 & ~Rank1BB; - while(b2) { - sq = pop_1st_bit(&b2); - mlist[n++].move = make_move(sq - DELTA_SW, sq); + while (b2) + { + sq = pop_1st_bit(&b2); + mlist[n++].move = make_move(sq - DELTA_SW, sq); } - // Non-capturing promotions: + // Non-capturing promotions b1 = (pawns >> 8) & pos.empty_squares() & Rank1BB; - while(b1) { - sq = pop_1st_bit(&b1); - mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, QUEEN); - } - - // En passant captures: - if(pos.ep_square() != SQ_NONE) { - assert(square_rank(pos.ep_square()) == RANK_3); - b1 = pawns & pos.white_pawn_attacks(pos.ep_square()); - assert(b1 != EmptyBoardBB); - while(b1) { + while (b1) + { sq = pop_1st_bit(&b1); - mlist[n++].move = make_ep_move(sq, pos.ep_square()); - } + mlist[n++].move = make_promotion_move(sq - DELTA_S, sq, QUEEN); } + // En passant captures + if (pos.ep_square() != SQ_NONE) + { + assert(square_rank(pos.ep_square()) == RANK_3); + b1 = pawns & pos.white_pawn_attacks(pos.ep_square()); + assert(b1 != EmptyBoardBB); + while (b1) + { + sq = pop_1st_bit(&b1); + mlist[n++].move = make_ep_move(sq, pos.ep_square()); + } + } return n; } - + int generate_white_pawn_noncaptures(const Position &pos, MoveStack *mlist) { + Bitboard pawns = pos.pawns(WHITE); Bitboard enemyPieces = pos.pieces_of_color(BLACK); Bitboard emptySquares = pos.empty_squares(); @@ -1079,4 +1026,39 @@ namespace { return n; } + + int generate_piece_checks(PieceType pce, const Position& pos, Bitboard target, + Bitboard dc, Square ksq, MoveStack* mlist) { + + const Piece_attacks_fn mem_fn = piece_attacks_fn[pce]; + int n = 0; + + // Discovered checks + Bitboard b = target & dc; + while (b) + { + Square from = pop_1st_bit(&b); + Bitboard bb = (pos.*mem_fn)(from) & pos.empty_squares(); + while (bb) + { + Square to = pop_1st_bit(&bb); + mlist[n++].move = make_move(from, to); + } + } + + // Direct checks + b = target & ~dc; + Bitboard checkSqs = (pos.*mem_fn)(ksq) & pos.empty_squares(); + while (b) + { + Square from = pop_1st_bit(&b); + Bitboard bb = (pos.*mem_fn)(from) & checkSqs; + while (bb) + { + Square to = pop_1st_bit(&bb); + mlist[n++].move = make_move(from, to); + } + } + return n; + } } -- 2.39.2 From 35fd5ce5bc3b2a99369e277a83b4426ab3bc5bc2 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 18 Oct 2008 11:07:27 +0200 Subject: [PATCH 14/16] Space inflate generate_castle_moves() No functional change. Signed-off-by: Marco Costalba --- src/movegen.cpp | 91 ++++++++++++++++++++++++++----------------------- 1 file changed, 49 insertions(+), 42 deletions(-) diff --git a/src/movegen.cpp b/src/movegen.cpp index f4ea0c6e..99b6076c 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -970,60 +970,67 @@ namespace { int generate_castle_moves(const Position &pos, MoveStack *mlist, Color us) { + int n = 0; - if(pos.can_castle(us)) { - Color them = opposite_color(us); - Square ksq = pos.king_square(us); - assert(pos.piece_on(ksq) == king_of_color(us)); - - if(pos.can_castle_kingside(us)) { - Square rsq = pos.initial_kr_square(us); - Square g1 = relative_square(us, SQ_G1); - Square f1 = relative_square(us, SQ_F1); - Square s; - bool illegal = false; + if (pos.can_castle(us)) + { + Color them = opposite_color(us); + Square ksq = pos.king_square(us); - assert(pos.piece_on(rsq) == rook_of_color(us)); + assert(pos.piece_on(ksq) == king_of_color(us)); - for(s = Min(ksq, g1); s <= Max(ksq, g1); s++) - if((s != ksq && s != rsq && pos.square_is_occupied(s)) - || pos.square_is_attacked(s, them)) - illegal = true; - for(s = Min(rsq, f1); s <= Max(rsq, f1); s++) - if(s != ksq && s != rsq && pos.square_is_occupied(s)) - illegal = true; + if (pos.can_castle_kingside(us)) + { + Square rsq = pos.initial_kr_square(us); + Square g1 = relative_square(us, SQ_G1); + Square f1 = relative_square(us, SQ_F1); + Square s; + bool illegal = false; - if(!illegal) - mlist[n++].move = make_castle_move(ksq, rsq); - } + assert(pos.piece_on(rsq) == rook_of_color(us)); - if(pos.can_castle_queenside(us)) { - Square rsq = pos.initial_qr_square(us); - Square c1 = relative_square(us, SQ_C1); - Square d1 = relative_square(us, SQ_D1); - Square s; - bool illegal = false; + for (s = Min(ksq, g1); s <= Max(ksq, g1); s++) + if ( (s != ksq && s != rsq && pos.square_is_occupied(s)) + || pos.square_is_attacked(s, them)) + illegal = true; - assert(pos.piece_on(rsq) == rook_of_color(us)); + for (s = Min(rsq, f1); s <= Max(rsq, f1); s++) + if (s != ksq && s != rsq && pos.square_is_occupied(s)) + illegal = true; - for(s = Min(ksq, c1); s <= Max(ksq, c1); s++) - if((s != ksq && s != rsq && pos.square_is_occupied(s)) - || pos.square_is_attacked(s, them)) - illegal = true; - for(s = Min(rsq, d1); s <= Max(rsq, d1); s++) - if(s != ksq && s != rsq && pos.square_is_occupied(s)) + if (!illegal) + mlist[n++].move = make_castle_move(ksq, rsq); + } + + if (pos.can_castle_queenside(us)) + { + Square rsq = pos.initial_qr_square(us); + Square c1 = relative_square(us, SQ_C1); + Square d1 = relative_square(us, SQ_D1); + Square s; + bool illegal = false; + + assert(pos.piece_on(rsq) == rook_of_color(us)); + + for (s = Min(ksq, c1); s <= Max(ksq, c1); s++) + if ( (s != ksq && s != rsq && pos.square_is_occupied(s)) + || pos.square_is_attacked(s, them)) + illegal = true; + + for (s = Min(rsq, d1); s <= Max(rsq, d1); s++) + if (s != ksq && s != rsq && pos.square_is_occupied(s)) + illegal = true; + + if ( square_file(rsq) == FILE_B + && ( pos.piece_on(relative_square(us, SQ_A1)) == rook_of_color(them) + || pos.piece_on(relative_square(us, SQ_A1)) == queen_of_color(them))) illegal = true; - if(square_file(rsq) == FILE_B && - (pos.piece_on(relative_square(us, SQ_A1)) == rook_of_color(them) || - pos.piece_on(relative_square(us, SQ_A1)) == queen_of_color(them))) - illegal = true; - if(!illegal) - mlist[n++].move = make_castle_move(ksq, rsq); + if (!illegal) + mlist[n++].move = make_castle_move(ksq, rsq); } } - return n; } -- 2.39.2 From 5abe8a0816ee924952a44c738d747eb86c805ced Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 18 Oct 2008 13:58:07 +0200 Subject: [PATCH 15/16] generate_checks: fix a bug in black double pawn push It was written pos.black_pawn_attacks(ksq) instead of pos.white_pawn_attacks(ksq) Updated to the undrlying pos.pawn_attacks(WHITE, ksq) Signed-off-by: Marco Costalba --- src/movegen.cpp | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/src/movegen.cpp b/src/movegen.cpp index 99b6076c..cfcaf3de 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -152,19 +152,19 @@ int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { // Direct checks. These are possible only for pawns on neighboring files // of the enemy king - b1 &= (~dc & neighboring_files_bb(ksq)); + b1 &= (~dc & neighboring_files_bb(ksq)); // FIXME why ~dc ?? // Direct checks, single pawn pushes b2 = (b1 << 8) & empty; - b3 = b2 & pos.black_pawn_attacks(ksq); - while(b3) + b3 = b2 & pos.pawn_attacks(BLACK, ksq); + while (b3) { to = pop_1st_bit(&b3); mlist[n++].move = make_move(to - DELTA_N, to); } // Direct checks, double pawn pushes - b3 = ((b2 & Rank3BB) << 8) & empty & pos.black_pawn_attacks(ksq); + b3 = ((b2 & Rank3BB) << 8) & empty & pos.pawn_attacks(BLACK, ksq); while (b3) { to = pop_1st_bit(&b3); @@ -203,7 +203,7 @@ int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { // Direct checks, single pawn pushes: b2 = (b1 >> 8) & empty; - b3 = b2 & pos.white_pawn_attacks(ksq); + b3 = b2 & pos.pawn_attacks(WHITE, ksq); while (b3) { to = pop_1st_bit(&b3); @@ -211,7 +211,7 @@ int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { } // Direct checks, double pawn pushes - b3 = ((b2 & Rank6BB) >> 8) & empty & pos.black_pawn_attacks(ksq); + b3 = ((b2 & Rank6BB) >> 8) & empty & pos.pawn_attacks(WHITE, ksq); while (b3) { to = pop_1st_bit(&b3); -- 2.39.2 From 34a515f20b0d8fa467af776c78b572cdafe819b1 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Sat, 18 Oct 2008 15:36:58 +0200 Subject: [PATCH 16/16] movegen: Introduce generate_pawn_checks() This greatly simplify redundant code. Perhaps slihtly slower. Test needed. Signed-off-by: Marco Costalba --- src/movegen.cpp | 219 ++++++++++++++++++++---------------------------- 1 file changed, 93 insertions(+), 126 deletions(-) diff --git a/src/movegen.cpp b/src/movegen.cpp index cfcaf3de..f363fa5a 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -41,6 +41,23 @@ namespace { int generate_piece_checks(PieceType pce, const Position& pos, Bitboard target, Bitboard dc, Square ksq, MoveStack* mlist); + + inline Bitboard next_row_white(Bitboard b) { return b << 8; } + inline Bitboard next_row_black(Bitboard b) { return b >> 8; } + + struct PawnOffsets { + + Bitboard Rank3BB; + Bitboard Rank8BB; + SquareDelta DELTA_N; + Color them; + Bitboard (*next_row_fn)(Bitboard b); + }; + const PawnOffsets WhitePawnOffsets = { Rank3BB, Rank8BB, DELTA_N, BLACK, &next_row_white }; + const PawnOffsets BlackPawnOffsets = { Rank6BB, Rank1BB, DELTA_S, WHITE, &next_row_black }; + + int generate_pawn_checks(const PawnOffsets& ofs, const Position& pos, Bitboard dc, + Square ksq, MoveStack* mlist); } @@ -107,146 +124,45 @@ int generate_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { assert(pos.is_ok()); assert(!pos.is_check()); - Color us, them; - Square ksq, from, to; - Bitboard empty, b1, b2, b3; + Color us = pos.side_to_move(); + Square ksq = pos.king_square(opposite_color(us)); int n = 0; - us = pos.side_to_move(); - them = opposite_color(us); - - ksq = pos.king_square(them); - assert(pos.piece_on(ksq) == king_of_color(them)); + assert(pos.piece_on(ksq) == king_of_color(opposite_color(us))); dc = pos.discovered_check_candidates(us); - empty = pos.empty_squares(); - - // Pawn moves. This is somewhat messy, and we use separate code for white - // and black, because we can't shift by negative numbers in C/C++. :-( - - if (us == WHITE) - { - // Pawn moves which give 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. - - // Find all friendly pawns not on the enemy king's file - b1 = pos.pawns(us) & ~file_bb(ksq); - - // Discovered checks, single pawn pushes - b2 = b3 = ((b1 & dc) << 8) & ~Rank8BB & empty; - while (b3) - { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_N, to); - } - - // Discovered checks, double pawn pushes - b3 = ((b2 & Rank3BB) << 8) & empty; - while (b3) - { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to); - } - - // Direct checks. These are possible only for pawns on neighboring files - // of the enemy king - - b1 &= (~dc & neighboring_files_bb(ksq)); // FIXME why ~dc ?? - - // Direct checks, single pawn pushes - b2 = (b1 << 8) & empty; - b3 = b2 & pos.pawn_attacks(BLACK, ksq); - while (b3) - { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_N, to); - } - - // Direct checks, double pawn pushes - b3 = ((b2 & Rank3BB) << 8) & empty & pos.pawn_attacks(BLACK, ksq); - while (b3) - { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_N - DELTA_N, to); - } - } - else { // (us == BLACK) - - // Pawn moves which give 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. - - // Find all friendly pawns not on the enemy king's file: - b1 = pos.pawns(us) & ~file_bb(ksq); - - // Discovered checks, single pawn pushes - b2 = b3 = ((b1 & dc) >> 8) & ~Rank1BB & empty; - while (b3) - { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_S, to); - } - // Discovered checks, double pawn pushes - b3 = ((b2 & Rank6BB) >> 8) & empty; - while (b3) - { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to); - } - - // Direct checks. These are possible only for pawns on neighboring files - // of the enemy king - - b1 &= (~dc & neighboring_files_bb(ksq)); - - // Direct checks, single pawn pushes: - b2 = (b1 >> 8) & empty; - b3 = b2 & pos.pawn_attacks(WHITE, ksq); - while (b3) - { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_S, to); - } - - // Direct checks, double pawn pushes - b3 = ((b2 & Rank6BB) >> 8) & empty & pos.pawn_attacks(WHITE, ksq); - while (b3) - { - to = pop_1st_bit(&b3); - mlist[n++].move = make_move(to - DELTA_S - DELTA_S, to); - } - } + // Pawn moves + if (us == WHITE) + n += generate_pawn_checks(WhitePawnOffsets, pos, dc, ksq, mlist); + else + n += generate_pawn_checks(BlackPawnOffsets, pos, dc, ksq, mlist); - // Knight moves - b1 = pos.knights(us); - if (b1) - n += generate_piece_checks(KNIGHT, pos, b1, dc, ksq, mlist); + // Pieces moves + Bitboard b = pos.knights(us); + if (b) + n += generate_piece_checks(KNIGHT, pos, b, dc, ksq, mlist); - // Bishop moves - b1 = pos.bishops(us); - if (b1) - n += generate_piece_checks(BISHOP, pos, b1, dc, ksq, mlist); + b = pos.bishops(us); + if (b) + n += generate_piece_checks(BISHOP, pos, b, dc, ksq, mlist); - // Rook moves - b1 = pos.rooks(us); - if (b1) - n += generate_piece_checks(ROOK, pos, b1, dc, ksq, mlist); + b = pos.rooks(us); + if (b) + n += generate_piece_checks(ROOK, pos, b, dc, ksq, mlist); - // Queen moves - b1 = pos.queens(us); - if (b1) - n += generate_piece_checks(QUEEN, pos, b1, dc, ksq, mlist); + b = pos.queens(us); + if (b) + n += generate_piece_checks(QUEEN, pos, b, dc, ksq, mlist); // King moves - from = pos.king_square(us); + Square from = pos.king_square(us); if (bit_is_set(dc, from)) { - b1 = pos.king_attacks(from) & empty & ~QueenPseudoAttacks[ksq]; - while (b1) + b = pos.king_attacks(from) & pos.empty_squares() & ~QueenPseudoAttacks[ksq]; + while (b) { - to = pop_1st_bit(&b1); + Square to = pop_1st_bit(&b); mlist[n++].move = make_move(from, to); } } @@ -1068,4 +984,55 @@ namespace { } return n; } + + int generate_pawn_checks(const PawnOffsets& ofs, const Position& pos, Bitboard dc, Square ksq, MoveStack* mlist) + { + // Pawn moves which give 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. + int n = 0; + Bitboard empty = pos.empty_squares(); + + // Find all friendly pawns not on the enemy king's file + Bitboard b1 = pos.pawns(pos.side_to_move()) & ~file_bb(ksq), b2, b3; + + // Discovered checks, single pawn pushes + b2 = b3 = (ofs.next_row_fn)(b1 & dc) & ~ofs.Rank8BB & empty; + while (b3) + { + Square to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - ofs.DELTA_N, to); + } + + // Discovered checks, double pawn pushes + b3 = (ofs.next_row_fn)(b2 & ofs.Rank3BB) & empty; + while (b3) + { + Square to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - ofs.DELTA_N - ofs.DELTA_N, to); + } + + // Direct checks. These are possible only for pawns on neighboring files + // of the enemy king + + b1 &= (~dc & neighboring_files_bb(ksq)); // FIXME why ~dc ?? + + // Direct checks, single pawn pushes + b2 = (ofs.next_row_fn)(b1) & empty; + b3 = b2 & pos.pawn_attacks(ofs.them, ksq); + while (b3) + { + Square to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - ofs.DELTA_N, to); + } + + // Direct checks, double pawn pushes + b3 = (ofs.next_row_fn)(b2 & ofs.Rank3BB) & empty & pos.pawn_attacks(ofs.them, ksq); + while (b3) + { + Square to = pop_1st_bit(&b3); + mlist[n++].move = make_move(to - ofs.DELTA_N - ofs.DELTA_N, to); + } + return n; + } } -- 2.39.2