From 9e4befe3f1ea324bece88aee2e97b38659411c52 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 28 Aug 2009 08:57:52 +0200 Subject: [PATCH 1/1] Use pointers instead of array indices in MovePicker This avoids calculating the array entry position at each access and gives another boost of almost 1%. No functional change. Signed-off-by: Marco Costalba --- src/book.cpp | 10 ++-- src/movegen.cpp | 49 +++++++++---------- src/movegen.h | 10 ++-- src/movepick.cpp | 121 ++++++++++++++++++++++++----------------------- src/movepick.h | 5 +- src/position.cpp | 12 ++--- src/search.cpp | 8 ++-- 7 files changed, 106 insertions(+), 109 deletions(-) diff --git a/src/book.cpp b/src/book.cpp index 9839124c..0c72d8e8 100644 --- a/src/book.cpp +++ b/src/book.cpp @@ -429,11 +429,11 @@ Move Book::get_move(const Position& pos) { if (!bookMove) return MOVE_NONE; - MoveStack moves[256]; - int n = generate_legal_moves(pos, moves); - for (int j = 0; j < n; j++) - if ((int(moves[j].move) & 07777) == bookMove) - return moves[j].move; + MoveStack mlist[256]; + MoveStack* last = generate_legal_moves(pos, mlist); + for (MoveStack* cur = mlist; cur != last; cur++) + if ((int(cur->move) & 07777) == bookMove) + return cur->move; return MOVE_NONE; } diff --git a/src/movegen.cpp b/src/movegen.cpp index eb65e7b9..bfeb7247 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -137,36 +137,33 @@ 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) { +MoveStack* generate_captures(const Position& pos, MoveStack* mlist) { assert(pos.is_ok()); assert(!pos.is_check()); Color us = pos.side_to_move(); Bitboard target = pos.pieces_of_color(opposite_color(us)); - MoveStack* mlist_start = mlist; mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us); - mlist = generate_piece_moves(pos, mlist, us, target); - return int(mlist - mlist_start); + return generate_piece_moves(pos, mlist, us, target); } /// generate_noncaptures() generates all pseudo-legal non-captures and /// underpromotions. The return value is the number of moves generated. -int generate_noncaptures(const Position& pos, MoveStack* mlist) { +MoveStack* generate_noncaptures(const Position& pos, MoveStack* mlist) { assert(pos.is_ok()); assert(!pos.is_check()); Color us = pos.side_to_move(); Bitboard target = pos.empty_squares(); - MoveStack* mlist_start = mlist; mlist = generate_piece_moves(pos, mlist, us); mlist = generate_piece_moves(pos, mlist, us, target); @@ -175,22 +172,20 @@ int generate_noncaptures(const Position& pos, MoveStack* mlist) { mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_piece_moves(pos, mlist, us, target); mlist = generate_castle_moves(pos, mlist); - mlist = generate_castle_moves(pos, mlist); - return int(mlist - mlist_start); + return generate_castle_moves(pos, mlist); } /// generate_non_capture_checks() generates all pseudo-legal non-capturing, /// non-promoting checks. It returns the number of generated moves. -int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { +MoveStack* generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc) { assert(pos.is_ok()); assert(!pos.is_check()); Color us = pos.side_to_move(); Square ksq = pos.king_square(opposite_color(us)); - MoveStack* mlist_start = mlist; assert(pos.piece_on(ksq) == piece_of_color_and_type(opposite_color(us), KING)); @@ -213,7 +208,7 @@ int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard && castling_is_check(pos, KING_SIDE)) mlist = generate_castle_moves(pos, mlist); - return int(mlist - mlist_start); + return mlist; } @@ -221,7 +216,7 @@ int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard /// in check. Unlike the other move generation functions, this one generates /// only legal moves. It returns the number of generated moves. -int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { +MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { assert(pos.is_ok()); assert(pos.is_check()); @@ -230,7 +225,6 @@ int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { Color us = pos.side_to_move(); Color them = opposite_color(us); Square ksq = pos.king_square(us); - MoveStack* mlist_start = mlist; assert(pos.piece_on(ksq) == piece_of_color_and_type(us, KING)); @@ -350,7 +344,7 @@ int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { } } } - return int(mlist - mlist_start); + return mlist; } @@ -360,7 +354,7 @@ int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned) { /// very hard to write an efficient legal move generator, but for the moment /// we don't need it. -int generate_legal_moves(const Position& pos, MoveStack* mlist) { +MoveStack* generate_legal_moves(const Position& pos, MoveStack* mlist) { assert(pos.is_ok()); @@ -370,15 +364,17 @@ int generate_legal_moves(const Position& pos, MoveStack* mlist) { return generate_evasions(pos, mlist, pinned); // Generate pseudo-legal moves - int n = generate_captures(pos, mlist); - n += generate_noncaptures(pos, mlist + n); + MoveStack* last = generate_captures(pos, mlist); + last = generate_noncaptures(pos, last); // Remove illegal moves from the list - for (int i = 0; i < n; i++) - if (!pos.pl_move_is_legal(mlist[i].move, pinned)) - mlist[i--].move = mlist[--n].move; - - return n; + for (MoveStack* cur = mlist; cur != last; cur++) + if (!pos.pl_move_is_legal(cur->move, pinned)) + { + cur->move = (--last)->move; + cur--; + } + return last; } @@ -580,11 +576,12 @@ bool move_is_legal(const Position& pos, const Move m) { else { Position p(pos); - MoveStack moves[64]; - int n = generate_evasions(p, moves, pinned); - for (int i = 0; i < n; i++) - if (moves[i].move == m) + MoveStack mlist[64]; + MoveStack* last = generate_evasions(p, mlist, pinned); + for (MoveStack* cur = mlist; cur != last; cur++) + if (cur->move == m) return true; + return false; } } diff --git a/src/movegen.h b/src/movegen.h index 991b0de3..7b7c4e91 100644 --- a/src/movegen.h +++ b/src/movegen.h @@ -32,11 +32,11 @@ //// Prototypes //// -extern int generate_captures(const Position& pos, MoveStack* mlist); -extern int generate_noncaptures(const Position& pos, MoveStack* mlist); -extern int generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc); -extern int generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned); -extern int generate_legal_moves(const Position& pos, MoveStack* mlist); +extern MoveStack* generate_captures(const Position& pos, MoveStack* mlist); +extern MoveStack* generate_noncaptures(const Position& pos, MoveStack* mlist); +extern MoveStack* generate_non_capture_checks(const Position& pos, MoveStack* mlist, Bitboard dc); +extern MoveStack* generate_evasions(const Position& pos, MoveStack* mlist, Bitboard pinned); +extern MoveStack* generate_legal_moves(const Position& pos, MoveStack* mlist); extern bool move_is_legal(const Position& pos, const Move m, Bitboard pinned); extern bool move_is_legal(const Position& pos, const Move m); diff --git a/src/movepick.cpp b/src/movepick.cpp index 57b5e1e9..45d989c9 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -100,55 +100,59 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d, /// MovePicker::go_next_phase() generates, scores and sorts the next bunch -/// of moves when there are no more moves to try for the currrent phase. +/// of moves when there are no more moves to try for the current phase. void MovePicker::go_next_phase() { - movesPicked = 0; + curMove = moves; phase = *(++phasePtr); switch (phase) { case PH_NULL_MOVE: case PH_TT_MOVES: + movesPicked = 0; return; case PH_GOOD_CAPTURES: - numOfMoves = generate_captures(pos, moves); + lastMove = generate_captures(pos, moves); score_captures(); - std::sort(moves, moves + numOfMoves); + std::sort(moves, lastMove); return; case PH_KILLERS: + movesPicked = 0; return; case PH_NONCAPTURES: - numOfMoves = generate_noncaptures(pos, moves); + lastMove = generate_noncaptures(pos, moves); score_noncaptures(); - std::sort(moves, moves + numOfMoves); + std::sort(moves, lastMove); return; case PH_BAD_CAPTURES: // Bad captures SEE value is already calculated so just sort them // to get SEE move ordering. - std::sort(badCaptures, badCaptures + numOfBadCaptures); + curMove = badCaptures; + lastMove = badCaptures + numOfBadCaptures; + std::sort(badCaptures, lastMove); return; case PH_EVASIONS: assert(pos.is_check()); - numOfMoves = generate_evasions(pos, moves, pinned); + lastMove = generate_evasions(pos, moves, pinned); score_evasions(); - std::sort(moves, moves + numOfMoves); + std::sort(moves, lastMove); return; case PH_QCAPTURES: - numOfMoves = generate_captures(pos, moves); + lastMove = generate_captures(pos, moves); score_captures(); - std::sort(moves, moves + numOfMoves); + std::sort(moves, lastMove); return; case PH_QCHECKS: // Perhaps we should order moves move here? FIXME - numOfMoves = generate_non_capture_checks(pos, moves, dc); + lastMove = generate_non_capture_checks(pos, moves, dc); return; case PH_STOP: @@ -161,10 +165,10 @@ void MovePicker::go_next_phase() { } -/// 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 pick_move_from_list(). +/// MovePicker::score_captures(), MovePicker::score_noncaptures() and +/// MovePicker::score_evasions() assign a numerical move ordering score +/// to each move in a move list. The moves with highest scores will be +/// picked first by get_next_move(). void MovePicker::score_captures() { // Winning and equal captures in the main search are ordered by MVV/LVA. @@ -183,14 +187,14 @@ void MovePicker::score_captures() { Move m; // Use MVV/LVA ordering - for (int i = 0; i < numOfMoves; i++) + for (MoveStack* cur = moves; cur != lastMove; cur++) { - m = moves[i].move; + m = cur->move; if (move_is_promotion(m)) - moves[i].score = QueenValueMidgame; + cur->score = QueenValueMidgame; else - moves[i].score = int(pos.midgame_value_of_piece_on(move_to(m))) - -int(pos.type_of_piece_on(move_from(m))); + cur->score = int(pos.midgame_value_of_piece_on(move_to(m))) + -int(pos.type_of_piece_on(move_from(m))); } } @@ -202,10 +206,10 @@ void MovePicker::score_noncaptures() { Square from, to; int hs; - for (int i = 0; i < numOfMoves; i++) + for (MoveStack* cur = moves; cur != lastMove; cur++) { - from = move_from(moves[i].move); - to = move_to(moves[i].move); + from = move_from(cur->move); + to = move_to(cur->move); piece = pos.piece_on(from); hs = H.move_ordering_score(piece, to); @@ -214,23 +218,23 @@ void MovePicker::score_noncaptures() { hs += 1000; // pst based scoring - moves[i].score = hs + pos.pst_delta(piece, from, to); + cur->score = hs + pos.pst_delta(piece, from, to); } } void MovePicker::score_evasions() { - for (int i = 0; i < numOfMoves; i++) + for (MoveStack* cur = moves; cur != lastMove; cur++) { - Move m = moves[i].move; + Move m = cur->move; if (m == ttMoves[0]) - moves[i].score = 2*HistoryMax; + cur->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; + cur->score = (seeScore >= 0)? seeScore + HistoryMax : seeScore; } else - moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m)); + cur->score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m)); } } @@ -242,7 +246,6 @@ void MovePicker::score_evasions() { Move MovePicker::get_next_move() { - assert(movesPicked >= 0); assert(!pos.is_check() || *phasePtr == PH_EVASIONS || *phasePtr == PH_STOP); assert( pos.is_check() || *phasePtr != PH_EVASIONS); @@ -255,18 +258,19 @@ Move MovePicker::get_next_move() { return MOVE_NULL; case PH_TT_MOVES: - while (movesPicked < 2) { - Move move = ttMoves[movesPicked++]; - if ( move != MOVE_NONE - && move_is_legal(pos, move, pinned)) - return move; - } - break; + while (movesPicked < 2) + { + Move move = ttMoves[movesPicked++]; + if ( move != MOVE_NONE + && move_is_legal(pos, move, pinned)) + return move; + } + break; case PH_GOOD_CAPTURES: - while (movesPicked < numOfMoves) + while (curMove != lastMove) { - Move move = moves[movesPicked++].move; + Move move = (curMove++)->move; if ( move != ttMoves[0] && move != ttMoves[1] && pos.pl_move_is_legal(move, pinned)) @@ -286,21 +290,22 @@ Move MovePicker::get_next_move() { break; case PH_KILLERS: - while (movesPicked < 2) { - Move move = killers[movesPicked++]; - if ( move != MOVE_NONE - && move != ttMoves[0] - && move != ttMoves[1] - && move_is_legal(pos, move, pinned) - && !pos.move_is_capture(move)) - return move; - } - break; + while (movesPicked < 2) + { + Move move = killers[movesPicked++]; + if ( move != MOVE_NONE + && move != ttMoves[0] + && move != ttMoves[1] + && move_is_legal(pos, move, pinned) + && !pos.move_is_capture(move)) + return move; + } + break; case PH_NONCAPTURES: - while (movesPicked < numOfMoves) + while (curMove != lastMove) { - Move move = moves[movesPicked++].move; + Move move = (curMove++)->move; if ( move != ttMoves[0] && move != ttMoves[1] && move != killers[0] @@ -311,20 +316,16 @@ Move MovePicker::get_next_move() { break; case PH_EVASIONS: - if (movesPicked < numOfMoves) - return moves[movesPicked++].move; - break; - case PH_BAD_CAPTURES: - if (movesPicked < numOfBadCaptures) - return badCaptures[movesPicked++].move; + if (curMove != lastMove) + return (curMove++)->move; break; case PH_QCAPTURES: case PH_QCHECKS: - while (movesPicked < numOfMoves) + while (curMove != lastMove) { - Move move = moves[movesPicked++].move; + Move move = (curMove++)->move; // Maybe postpone the legality check until after futility pruning? if ( move != ttMoves[0] && pos.pl_move_is_legal(move, pinned)) diff --git a/src/movepick.h b/src/movepick.h index c9c37f93..ced0a051 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -81,9 +81,10 @@ private: const History& H; Move ttMoves[2], killers[2]; const MovegenPhaseT* phasePtr; - int phase, movesPicked, numOfMoves, numOfBadCaptures; + int phase, movesPicked, numOfBadCaptures; bool finished; Bitboard dc, pinned; + MoveStack *curMove, *lastMove; MoveStack moves[256], badCaptures[64]; }; @@ -98,7 +99,7 @@ private: /// a single reply to check. inline int MovePicker::number_of_moves() const { - return numOfMoves; + return int(lastMove - moves); } /// MovePicker::discovered_check_candidates() returns a bitboard containing diff --git a/src/position.cpp b/src/position.cpp index c5d05798..2b50ff2a 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -1696,7 +1696,7 @@ bool Position::is_mate() const { MoveStack moves[256]; - return is_check() && !generate_evasions(*this, moves, pinned_pieces(sideToMove)); + return is_check() && (generate_evasions(*this, moves, pinned_pieces(sideToMove)) == moves); } @@ -1716,20 +1716,18 @@ bool Position::has_mate_threat(Color c) { do_null_move(st1); MoveStack mlist[120]; - int count; bool result = false; Bitboard dc = discovered_check_candidates(sideToMove); Bitboard pinned = pinned_pieces(sideToMove); // Generate pseudo-legal non-capture and capture check moves - count = generate_non_capture_checks(*this, mlist, dc); - count += generate_captures(*this, mlist + count); + MoveStack* last = generate_non_capture_checks(*this, mlist, dc); + last = generate_captures(*this, last); // Loop through the moves, and see if one of them is mate - for (int i = 0; i < count; i++) + for (MoveStack* cur = mlist; cur != last; cur++) { - Move move = mlist[i].move; - + Move move = cur->move; if (!pl_move_is_legal(move, pinned)) continue; diff --git a/src/search.cpp b/src/search.cpp index 804108b4..d93493c2 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1968,15 +1968,15 @@ namespace { bool includeAllMoves = (searchMoves[0] == MOVE_NONE); // Generate all legal moves - int lm_count = generate_legal_moves(pos, mlist); + MoveStack* last = generate_legal_moves(pos, mlist); // Add each move to the moves[] array - for (int i = 0; i < lm_count; i++) + for (MoveStack* cur = mlist; cur != last; cur++) { bool includeMove = includeAllMoves; for (int k = 0; !includeMove && searchMoves[k] != MOVE_NONE; k++) - includeMove = (searchMoves[k] == mlist[i].move); + includeMove = (searchMoves[k] == cur->move); if (!includeMove) continue; @@ -1985,7 +1985,7 @@ namespace { StateInfo st; SearchStack ss[PLY_MAX_PLUS_2]; - moves[count].move = mlist[i].move; + moves[count].move = cur->move; pos.do_move(moves[count].move, st); moves[count].score = -qsearch(pos, ss, -VALUE_INFINITE, VALUE_INFINITE, Depth(0), 1, 0); pos.undo_move(moves[count].move); -- 2.39.2