From 52129955637610488936648066f80a4515f6ce57 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Tue, 1 Jun 2010 21:28:45 +0100 Subject: [PATCH] Retire bitScanReverse32() Use log() instead because we are not in speed critical paths. Also a bit of renaming and code shuffle while there. No functional change. Signed-off-by: Marco Costalba --- src/bitboard.cpp | 33 ------------------ src/bitboard.h | 1 - src/search.cpp | 90 ++++++++++++++++++++++++------------------------ 3 files changed, 45 insertions(+), 79 deletions(-) diff --git a/src/bitboard.cpp b/src/bitboard.cpp index f014fe19..063204c5 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -373,39 +373,6 @@ Square pop_1st_bit(Bitboard* bb) { #endif -// Optimized bitScanReverse32() implementation by Pascal Georges. Note -// that first bit is 1, this allow to differentiate between 0 and 1. -static CACHE_LINE_ALIGNMENT -const char MsbTable[256] = { - 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, - 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, - 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, - 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, - 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 -}; - -int bitScanReverse32(uint32_t b) -{ - int result = 0; - - if (b > 0xFFFF) - { - b >>= 16; - result += 16; - } - if (b > 0xFF) - { - b >>= 8; - result += 8; - } - return result + MsbTable[b]; -} namespace { diff --git a/src/bitboard.h b/src/bitboard.h index 1ad5fdcb..9d061186 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -342,7 +342,6 @@ extern Square pop_1st_bit(Bitboard* b); extern void print_bitboard(Bitboard b); extern void init_bitboards(); -extern int bitScanReverse32(uint32_t b); #endif // !defined(BITBOARD_H_INCLUDED) diff --git a/src/search.cpp b/src/search.cpp index f11388c5..30179e8f 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -337,6 +337,51 @@ void exit_threads() { TM.exit_threads(); } int64_t nodes_searched() { return TM.nodes_searched(); } +/// init_search() is called during startup. It initializes various lookup tables + +void init_search() { + + int d; // depth (OnePly == 2) + int hd; // half depth (OnePly == 1) + int mc; // moveCount + + // Init reductions array + for (hd = 1; hd < 64; hd++) for (mc = 1; mc < 64; mc++) + { + double pvRed = log(double(hd)) * log(double(mc)) / 3.0; + double nonPVRed = log(double(hd)) * log(double(mc)) / 1.5; + ReductionMatrix[PV][hd][mc] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); + ReductionMatrix[NonPV][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); + } + + // Init futility margins array + for (d = 0; d < 16; d++) for (mc = 0; mc < 64; mc++) + FutilityMarginsMatrix[d][mc] = 112 * int(log(double(d * d) / 2) / log(2.0) + 1) - 8 * mc + 45; + + // Init futility move count array + for (d = 0; d < 32; d++) + FutilityMoveCountArray[d] = 3 + (1 << (3 * d / 8)); +} + + +// SearchStack::init() initializes a search stack. Used at the beginning of a +// new search from the root. +void SearchStack::init(int ply) { + + pv[ply] = pv[ply + 1] = MOVE_NONE; + currentMove = threatMove = MOVE_NONE; + reduction = Depth(0); + eval = VALUE_NONE; +} + +void SearchStack::initKillers() { + + mateKiller = MOVE_NONE; + for (int i = 0; i < KILLER_MAX; i++) + killers[i] = MOVE_NONE; +} + + /// perft() is our utility to verify move generation is bug free. All the legal /// moves up to given depth are generated and counted and the sum returned. @@ -549,51 +594,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, } -/// init_search() is called during startup. It initializes various lookup tables - -void init_search() { - - // Init our reduction lookup tables - for (int i = 1; i < 64; i++) // i == depth (OnePly = 1) - for (int j = 1; j < 64; j++) // j == moveNumber - { - double pvRed = log(double(i)) * log(double(j)) / 3.0; - double nonPVRed = log(double(i)) * log(double(j)) / 1.5; - ReductionMatrix[PV][i][j] = (int8_t) ( pvRed >= 1.0 ? floor( pvRed * int(OnePly)) : 0); - ReductionMatrix[NonPV][i][j] = (int8_t) (nonPVRed >= 1.0 ? floor(nonPVRed * int(OnePly)) : 0); - } - - // Init futility margins array - for (int i = 0; i < 16; i++) // i == depth (OnePly = 2) - for (int j = 0; j < 64; j++) // j == moveNumber - { - // FIXME: test using log instead of BSR - FutilityMarginsMatrix[i][j] = (i < 2 ? 0 : 112 * bitScanReverse32(i * i / 2)) - 8 * j + 45; - } - - // Init futility move count array - for (int i = 0; i < 32; i++) // i == depth (OnePly = 2) - FutilityMoveCountArray[i] = 3 + (1 << (3 * i / 8)); -} - - -// SearchStack::init() initializes a search stack. Used at the beginning of a -// new search from the root. -void SearchStack::init(int ply) { - - pv[ply] = pv[ply + 1] = MOVE_NONE; - currentMove = threatMove = MOVE_NONE; - reduction = Depth(0); - eval = VALUE_NONE; -} - -void SearchStack::initKillers() { - - mateKiller = MOVE_NONE; - for (int i = 0; i < KILLER_MAX; i++) - killers[i] = MOVE_NONE; -} - namespace { // id_loop() is the main iterative deepening loop. It calls root_search -- 2.39.2