From: Marco Costalba Date: Fri, 15 May 2009 14:42:30 +0000 (+0200) Subject: Better document how history works X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=436fa5c8fa5302f69a83ad28491702c5dc3d4af7;ds=sidebyside Better document how history works Both with added comment and changing the API to reflect that only destination square and moved piece is important for history. No functional change. Signed-off-by: Marco Costalba --- diff --git a/src/history.cpp b/src/history.cpp index 899d40aa..6fe222fe 100644 --- a/src/history.cpp +++ b/src/history.cpp @@ -32,14 +32,13 @@ //// Functions //// + /// Constructor -History::History() { - this->clear(); -} +History::History() { clear(); } -/// History::clear() clears the history tables. +/// History::clear() clears the history tables void History::clear() { memset(history, 0, 2 * 8 * 64 * sizeof(int)); @@ -48,55 +47,59 @@ void History::clear() { } -/// History::success() registers a move as being successful. This is done +/// History::success() registers a move as being successful. This is done /// whenever a non-capturing move causes a beta cutoff in the main search. -/// The three parameters are the moving piece, the move itself, and the -/// search depth. +/// The three parameters are the moving piece, the destination square, and +/// the search depth. + +void History::success(Piece p, Square to, Depth d) { -void History::success(Piece p, Move m, Depth d) { assert(piece_is_ok(p)); - assert(move_is_ok(m)); + assert(square_is_ok(to)); - history[p][move_to(m)] += int(d) * int(d); - successCount[p][move_to(m)]++; + history[p][to] += int(d) * int(d); + successCount[p][to]++; - // Prevent history overflow: - if(history[p][move_to(m)] >= HistoryMax) - for(int i = 0; i < 16; i++) - for(int j = 0; j < 64; j++) - history[i][j] /= 2; + // Prevent history overflow + if (history[p][to] >= HistoryMax) + for (int i = 0; i < 16; i++) + for (int j = 0; j < 64; j++) + history[i][j] /= 2; } -/// History::failure() registers a move as being unsuccessful. The function is +/// History::failure() registers a move as being unsuccessful. The function is /// called for each non-capturing move which failed to produce a beta cutoff /// at a node where a beta cutoff was finally found. -void History::failure(Piece p, Move m) { +void History::failure(Piece p, Square to) { + assert(piece_is_ok(p)); - assert(move_is_ok(m)); + assert(square_is_ok(to)); - failureCount[p][move_to(m)]++; + failureCount[p][to]++; } /// History::move_ordering_score() returns an integer value used to order the /// non-capturing moves in the MovePicker class. -int History::move_ordering_score(Piece p, Move m) const { +int History::move_ordering_score(Piece p, Square to) const { + assert(piece_is_ok(p)); - assert(move_is_ok(m)); + assert(square_is_ok(to)); - return history[p][move_to(m)]; + return history[p][to]; } /// History::ok_to_prune() decides whether a move has been sufficiently /// unsuccessful that it makes sense to prune it entirely. -bool History::ok_to_prune(Piece p, Move m, Depth d) const { +bool History::ok_to_prune(Piece p, Square to, Depth d) const { + assert(piece_is_ok(p)); - assert(move_is_ok(m)); + assert(square_is_ok(to)); - return (int(d) * successCount[p][move_to(m)] < failureCount[p][move_to(m)]); + return (int(d) * successCount[p][to] < failureCount[p][to]); } diff --git a/src/history.h b/src/history.h index b08c8d33..df56307b 100644 --- a/src/history.h +++ b/src/history.h @@ -34,19 +34,22 @@ //// Types //// -/// The History class stores statistics about how often different moves have -/// been successful or unsuccessful during the current search. These -/// statistics are used for reduction and move ordering decisions. +/// The History class stores statistics about how often different moves +/// have been successful or unsuccessful during the current search. These +/// statistics are used for reduction and move ordering decisions. History +/// entries are stored according only to moving piece and destination square, +/// in particular two moves with different origin but same destination and +/// same piece will be considered identical. class History { public: History(); void clear(); - void success(Piece p, Move m, Depth d); - void failure(Piece p, Move m); - int move_ordering_score(Piece p, Move m) const; - bool ok_to_prune(Piece p, Move m, Depth d) const; + void success(Piece p, Square to, Depth d); + void failure(Piece p, Square to); + int move_ordering_score(Piece p, Square to) const; + bool ok_to_prune(Piece p, Square to, Depth d) const; private: int history[16][64]; // [piece][square] @@ -61,14 +64,14 @@ private: /// HistoryMax controls how often the history counters will be scaled down: /// When the history score for a move gets bigger than HistoryMax, all -/// entries in the table are divided by 2. It is difficult to guess what -/// the ideal value of this constant is. Scaling down the scores often has +/// entries in the table are divided by 2. It is difficult to guess what +/// the ideal value of this constant is. Scaling down the scores often has /// the effect that parts of the search tree which have been searched /// recently have a bigger importance for move ordering than the moves which /// have been searched a long time ago. /// /// Note that HistoryMax should probably be changed whenever the constant -/// OnePly in depth.h is changed. This is somewhat annoying. Perhaps it +/// OnePly in depth.h is changed. This is somewhat annoying. Perhaps it /// would be better to scale down the history table at regular intervals? const int HistoryMax = 50000; diff --git a/src/movepick.cpp b/src/movepick.cpp index d6031bda..3897f4c1 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -264,7 +264,7 @@ void MovePicker::score_noncaptures() { else if (m == killer2) hs = HistoryMax + 1; else - hs = H.move_ordering_score(pos.piece_on(move_from(m)), m); + hs = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m)); // Ensure history is always preferred to pst if (hs > 0) @@ -287,7 +287,7 @@ void MovePicker::score_evasions() { 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); + moves[i].score = H.move_ordering_score(pos.piece_on(move_from(m)), move_to(m)); } } diff --git a/src/search.cpp b/src/search.cpp index 30abecd0..4e04d074 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -2332,7 +2332,7 @@ namespace { return false; // Case 4: Don't prune moves with good history. - if (!H.ok_to_prune(pos.piece_on(move_from(m)), m, d)) + if (!H.ok_to_prune(pos.piece_on(mfrom), mto, d)) return false; // Case 5: If the moving piece in the threatened move is a slider, don't @@ -2379,13 +2379,13 @@ namespace { void update_history(const Position& pos, Move m, Depth depth, Move movesSearched[], int moveCount) { - H.success(pos.piece_on(move_from(m)), m, depth); + H.success(pos.piece_on(move_from(m)), move_to(m), depth); for (int i = 0; i < moveCount - 1; i++) { assert(m != movesSearched[i]); if (ok_to_history(pos, movesSearched[i])) - H.failure(pos.piece_on(move_from(movesSearched[i])), movesSearched[i]); + H.failure(pos.piece_on(move_from(movesSearched[i])), move_to(movesSearched[i])); } }