From 436fa5c8fa5302f69a83ad28491702c5dc3d4af7 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 15 May 2009 16:42:30 +0200 Subject: [PATCH] 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 --- src/history.cpp | 55 +++++++++++++++++++++++++----------------------- src/history.h | 23 +++++++++++--------- src/movepick.cpp | 4 ++-- src/search.cpp | 6 +++--- 4 files changed, 47 insertions(+), 41 deletions(-) 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])); } } -- 2.39.2