From: Steinar H. Gunderson Date: Mon, 3 Aug 2020 10:27:33 +0000 (+0200) Subject: Merge remote-tracking branch 'upstream/master' into HEAD X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=a24f28be8567c2527b154ef981090368a2bd8f76;hp=9cb1f9f2655cd378eec9d88fd57a039a04396aae Merge remote-tracking branch 'upstream/master' into HEAD --- diff --git a/.travis.yml b/.travis.yml index e2b42e6d..e2ae61be 100644 --- a/.travis.yml +++ b/.travis.yml @@ -50,7 +50,7 @@ script: - echo "Reference bench:" $benchref # # Verify bench number against various builds - - export CXXFLAGS=-Werror + - export CXXFLAGS="-Werror -D_GLIBCXX_DEBUG" - make clean && make -j2 ARCH=x86-64 optimize=no debug=yes build && ../tests/signature.sh $benchref - make clean && make -j2 ARCH=x86-32 optimize=no debug=yes build && ../tests/signature.sh $benchref - make clean && make -j2 ARCH=x86-32 build && ../tests/signature.sh $benchref diff --git a/AUTHORS b/AUTHORS index a9f141f9..f08d71d3 100644 --- a/AUTHORS +++ b/AUTHORS @@ -1,4 +1,4 @@ -# List of authors for Stockfish, as of January 7, 2020 +# List of authors for Stockfish, as of March 30, 2020 Tord Romstad (romstad) Marco Costalba (mcostalba) @@ -42,12 +42,14 @@ Eelco de Groot (KingDefender) Elvin Liu (solarlight2) erbsenzaehler Ernesto Gatti +Linmiao Xu (linrock) Fabian Beuke (madnight) Fabian Fichter (ianfab) fanon Fauzi Akram Dabat (FauziAkram) Felix Wittmann gamander +Gary Heckman (gheckman) gguliash Gian-Carlo Pascutto (gcp) Gontran Lemaire (gonlem) @@ -113,6 +115,7 @@ Nick Pelling (nickpelling) Nicklas Persson (NicklasPersson) Niklas Fiekas (niklasf) Nikolay Kostov (NikolayIT) +Nguyen Pham Ondrej Mosnáček (WOnder93) Oskar Werkelin Ahlin Pablo Vazquez @@ -122,6 +125,8 @@ Pasquale Pigazzini (ppigazzini) Patrick Jansen (mibere) pellanda Peter Zsifkovits (CoffeeOne) +Praveen Kumar Tummala (praveentml) +Rahul Dsilva (silversolver1) Ralph Stößer (Ralph Stoesser) Raminder Singh renouve @@ -147,8 +152,10 @@ thaspel theo77186 Tom Truscott Tom Vijlbrief (tomtor) +Tomasz Sobczyk (Sopel97) Torsten Franz (torfranz, tfranzer) Tracey Emery (basepr1me) +Unai Corzo (unaiic) Uri Blass (uriblass) Vince Negri (cuddlestmonkey) @@ -157,7 +164,3 @@ Vince Negri (cuddlestmonkey) # an amazing and essential framework for the development of Stockfish! # # https://github.com/glinscott/fishtest/blob/master/AUTHORS - - - - diff --git a/Readme.md b/Readme.md index a759eff6..823518d1 100644 --- a/Readme.md +++ b/Readme.md @@ -42,7 +42,7 @@ Currently, Stockfish has the following UCI options: this equal to the number of CPU cores available. * #### Hash - The size of the hash table in MB. + The size of the hash table in MB. It is recommended to set Hash after setting Threads. * #### Clear Hash Clear the hash table. @@ -66,13 +66,15 @@ Currently, Stockfish has the following UCI options: If enabled by UCI_LimitStrength, aim for an engine strength of the given Elo. This Elo rating has been calibrated at a time control of 60s+0.6s and anchored to CCRL 40/4. + * #### UCI_ShowWDL + If enabled, show approximate WDL statistics as part of the engine output. + These WDL numbers model expected game outcomes for a given evaluation and + game ply for engine self-play at fishtest LTC conditions (60+0.6s per game). + * #### Move Overhead Assume a time delay of x ms due to network and GUI overheads. This is useful to avoid losses on time in those cases. - * #### Minimum Thinking Time - Search for at least x ms per move. - * #### Slow Mover Lower values will make Stockfish take less time in games, higher values will make it think longer. @@ -138,20 +140,50 @@ more compact than Nalimov tablebases, while still storing all information needed for optimal play and in addition being able to take into account the 50-move rule. +## Large Pages + +Stockfish supports large pages on Linux and Windows. Large pages make +the hash access more efficient, improving the engine speed, especially +on large hash sizes. Typical increases are 5..10% in terms of nps, but +speed increases up to 30% have been measured. The support is +automatic. Stockfish attempts to use large pages when available and +will fall back to regular memory allocation when this is not the case. + +### Support on Linux + +Large page support on Linux is obtained by the Linux kernel +transparent huge pages functionality. Typically, transparent huge pages +are already enabled and no configuration is needed. + +### Support on Windows + +The use of large pages requires "Lock Pages in Memory" privilege. See +[Enable the Lock Pages in Memory Option (Windows)](https://docs.microsoft.com/en-us/sql/database-engine/configure-windows/enable-the-lock-pages-in-memory-option-windows) +on how to enable this privilege. Logout/login may be needed +afterwards. Due to memory fragmentation, it may not always be +possible to allocate large pages even when enabled. A reboot +might alleviate this problem. To determine whether large pages +are in use, see the engine log. ## Compiling Stockfish yourself from the sources -On Unix-like systems, it should be possible to compile Stockfish -directly from the source code with the included Makefile. +Stockfish has support for 32 or 64-bit CPUs, certain hardware +instructions, big-endian machines such as Power PC, and other platforms. + +On Unix-like systems, it should be easy to compile Stockfish +directly from the source code with the included Makefile in the folder +`src`. In general it is recommended to run `make help` to see a list of make +targets with corresponding descriptions. -Stockfish has support for 32 or 64-bit CPUs, the hardware POPCNT -instruction, big-endian machines such as Power PC, and other platforms. +``` + cd src + make help + make build ARCH=x86-64-modern +``` -In general it is recommended to run `make help` to see a list of make -targets with corresponding descriptions. When not using the Makefile to -compile (for instance with Microsoft MSVC) you need to manually -set/unset some switches in the compiler command line; see file *types.h* -for a quick reference. +When not using the Makefile to compile (for instance with Microsoft MSVC) you +need to manually set/unset some switches in the compiler command line; see +file *types.h* for a quick reference. When reporting an issue or a bug, please tell us which version and compiler you used to create your executable. These informations can diff --git a/src/Makefile b/src/Makefile index 06c95faf..9b10a195 100644 --- a/src/Makefile +++ b/src/Makefile @@ -35,12 +35,17 @@ BINDIR = $(PREFIX)/bin ### Built-in benchmark for pgo-builds PGOBENCH = ./$(EXE) bench -### Object files -OBJS = benchmark.o bitbase.o bitboard.o endgame.o evaluate.o main.o \ - material.o misc.o movegen.o movepick.o pawns.o position.o psqt.o \ - search.o thread.o timeman.o tt.o uci.o ucioption.o syzygy/tbprobe.o \ - hashprobe.grpc.pb.o hashprobe.pb.o -CLIOBJS = client.o hashprobe.grpc.pb.o hashprobe.pb.o uci.o +### Source and object files +SRCS = benchmark.cpp bitbase.cpp bitboard.cpp endgame.cpp evaluate.cpp main.cpp \ + material.cpp misc.cpp movegen.cpp movepick.cpp pawns.cpp position.cpp psqt.cpp \ + search.cpp thread.cpp timeman.cpp tt.cpp uci.cpp ucioption.cpp tune.cpp syzygy/tbprobe.cpp \ + hashprobe.grpc.pb.cc hashprobe.pb.cc +CLISRCS = client.cpp hashprobe.grpc.pb.cc hashprobe.pb.cc uci.cpp + +OBJS = $(notdir $(SRCS:.cpp=.o)) +CLIOBJS = $(notdir $(CLISRCS:.cpp=.o)) + +VPATH = syzygy ### Establish the operating system name KERNEL = $(shell uname -s) @@ -52,7 +57,7 @@ endif ### Section 2. High-level Configuration ### ========================================================================== # -# flag --- Comp switch --- Description +# flag --- Comp switch --- Description # ---------------------------------------------------------------------------- # # debug = yes/no --- -DNDEBUG --- Enable/Disable debug mode @@ -75,43 +80,42 @@ endif optimize = yes debug = no sanitize = no -bits = 32 +bits = 64 prefetch = no popcnt = no sse = no pext = no ### 2.2 Architecture specific - ifeq ($(ARCH),general-32) arch = any + bits = 32 endif ifeq ($(ARCH),x86-32-old) arch = i386 + bits = 32 endif ifeq ($(ARCH),x86-32) arch = i386 + bits = 32 prefetch = yes sse = yes endif ifeq ($(ARCH),general-64) arch = any - bits = 64 endif ifeq ($(ARCH),x86-64) arch = x86_64 - bits = 64 prefetch = yes sse = yes endif ifeq ($(ARCH),x86-64-modern) arch = x86_64 - bits = 64 prefetch = yes popcnt = yes sse = yes @@ -119,7 +123,6 @@ endif ifeq ($(ARCH),x86-64-bmi2) arch = x86_64 - bits = 64 prefetch = yes popcnt = yes sse = yes @@ -129,26 +132,31 @@ endif ifeq ($(ARCH),armv7) arch = armv7 prefetch = yes + bits = 32 +endif + +ifeq ($(ARCH),armv8) + arch = armv8-a + prefetch = yes + popcnt = yes endif ifeq ($(ARCH),ppc-32) arch = ppc + bits = 32 endif ifeq ($(ARCH),ppc-64) arch = ppc64 - bits = 64 popcnt = yes prefetch = yes endif - ### ========================================================================== -### Section 3. Low-level configuration +### Section 3. Low-level Configuration ### ========================================================================== ### 3.1 Selecting compiler (default = gcc) - CXXFLAGS += -Wall -Wcast-qual -fno-exceptions -std=c++11 $(EXTRACXXFLAGS) DEPENDFLAGS += -std=c++11 LDFLAGS += $(EXTRALDFLAGS) @@ -162,7 +170,7 @@ ifeq ($(COMP),gcc) CXX=g++ CXXFLAGS += -pedantic -Wextra - ifeq ($(ARCH),armv7) + ifeq ($(ARCH),$(filter $(ARCH),armv7 armv8)) ifeq ($(OS),Android) CXXFLAGS += -m$(bits) LDFLAGS += -m$(bits) @@ -219,7 +227,7 @@ ifeq ($(COMP),clang) endif endif - ifeq ($(ARCH),armv7) + ifeq ($(ARCH),$(filter $(ARCH),armv7 armv8)) ifeq ($(OS),Android) CXXFLAGS += -m$(bits) LDFLAGS += -m$(bits) @@ -317,7 +325,7 @@ endif ### 3.6 popcnt ifeq ($(popcnt),yes) - ifeq ($(arch),ppc64) + ifeq ($(arch),$(filter $(arch),ppc64 armv8-a)) CXXFLAGS += -DUSE_POPCNT else ifeq ($(comp),icc) CXXFLAGS += -msse3 -DUSE_POPCNT @@ -334,7 +342,7 @@ ifeq ($(pext),yes) endif endif -### 3.8 Link Time Optimization, it works since gcc 4.5 but not on mingw under Windows. +### 3.8 Link Time Optimization ### This is a mix of compile and link time options because the lto link phase ### needs access to the optimization flags. ifeq ($(optimize),yes) @@ -344,6 +352,9 @@ ifeq ($(debug), no) LDFLAGS += $(CXXFLAGS) endif +# To use LTO and static linking on windows, the tool chain requires a recent gcc: +# gcc version 10.1 in msys2 or TDM-GCC version 9.2 are know to work, older might not. +# So, only enable it for a cross from Linux by default. ifeq ($(comp),mingw) ifeq ($(KERNEL),Linux) CXXFLAGS += -flto @@ -360,9 +371,8 @@ ifeq ($(OS), Android) LDFLAGS += -fPIE -pie endif - ### ========================================================================== -### Section 4. Public targets +### Section 4. Public Targets ### ========================================================================== help: @@ -389,6 +399,7 @@ help: @echo "ppc-64 > PPC 64-bit" @echo "ppc-32 > PPC 32-bit" @echo "armv7 > ARMv7 32-bit" + @echo "armv8 > ARMv8 64-bit" @echo "general-64 > unspecified 64-bit" @echo "general-32 > unspecified 32-bit" @echo "" @@ -411,7 +422,7 @@ help: @echo "" -.PHONY: help build profile-build strip install clean objclean profileclean help \ +.PHONY: help build profile-build strip install clean objclean profileclean \ config-sanity icc-profile-use icc-profile-make gcc-profile-use gcc-profile-make \ clang-profile-use clang-profile-make @@ -452,14 +463,14 @@ objclean: # clean auxiliary profiling files profileclean: @rm -rf profdir - @rm -f bench.txt *.gcda ./syzygy/*.gcda *.gcno ./syzygy/*.gcno + @rm -f bench.txt *.gcda *.gcno @rm -f stockfish.profdata *.profraw default: help ### ========================================================================== -### Section 5. Private targets +### Section 5. Private Targets ### ========================================================================== all: $(EXE) client .depend @@ -490,7 +501,8 @@ config-sanity: @test "$(sanitize)" = "undefined" || test "$(sanitize)" = "thread" || test "$(sanitize)" = "address" || test "$(sanitize)" = "no" @test "$(optimize)" = "yes" || test "$(optimize)" = "no" @test "$(arch)" = "any" || test "$(arch)" = "x86_64" || test "$(arch)" = "i386" || \ - test "$(arch)" = "ppc64" || test "$(arch)" = "ppc" || test "$(arch)" = "armv7" + test "$(arch)" = "ppc64" || test "$(arch)" = "ppc" || \ + test "$(arch)" = "armv7" || test "$(arch)" = "armv8-a" @test "$(bits)" = "32" || test "$(bits)" = "64" @test "$(prefetch)" = "yes" || test "$(prefetch)" = "no" @test "$(popcnt)" = "yes" || test "$(popcnt)" = "no" @@ -564,7 +576,6 @@ client: $(CLIOBJS) # Other stuff .depend: - -@$(CXX) $(DEPENDFLAGS) -MM $(OBJS:.o=.cpp) $(OBJS:.o=.cc) > $@ 2> /dev/null + -@$(CXX) $(DEPENDFLAGS) -MM $(SRCS) > $@ 2> /dev/null -include .depend - diff --git a/src/benchmark.cpp b/src/benchmark.cpp index f906e731..3299f373 100644 --- a/src/benchmark.cpp +++ b/src/benchmark.cpp @@ -65,6 +65,7 @@ const vector Defaults = { "4rrk1/1p1nq3/p7/2p1P1pp/3P2bp/3Q1Bn1/PPPB4/1K2R1NR w - - 40 21", "r3k2r/3nnpbp/q2pp1p1/p7/Pp1PPPP1/4BNN1/1P5P/R2Q1RK1 w kq - 0 16", "3Qb1k1/1r2ppb1/pN1n2q1/Pp1Pp1Pr/4P2p/4BP2/4B1R1/1R5K b - - 11 40", + "4k3/3q1r2/1N2r1b1/3ppN2/2nPP3/1B1R2n1/2R1Q3/3K4 w - - 5 1", // 5-man positions "8/8/8/8/5kp1/P7/8/1K1N4 w - - 0 1", // Kc2 - mate @@ -87,7 +88,7 @@ const vector Defaults = { // Chess 960 "setoption name UCI_Chess960 value true", - "bbqnnrkr/pppppppp/8/8/8/8/PPPPPPPP/BBQNNRKR w KQkq - 0 1 moves g2g3 d7d5 d2d4 c8h3 c1g5 e8d6 g5e7 f7f6", + "bbqnnrkr/pppppppp/8/8/8/8/PPPPPPPP/BBQNNRKR w HFhf - 0 1 moves g2g3 d7d5 d2d4 c8h3 c1g5 e8d6 g5e7 f7f6", "setoption name UCI_Chess960 value false" }; diff --git a/src/bitbase.cpp b/src/bitbase.cpp index 78614fa2..7e27eb96 100644 --- a/src/bitbase.cpp +++ b/src/bitbase.cpp @@ -19,8 +19,8 @@ */ #include -#include #include +#include #include "bitboard.h" #include "types.h" @@ -31,8 +31,7 @@ namespace { // Positions with the pawn on files E to H will be mirrored before probing. constexpr unsigned MAX_INDEX = 2*24*64*64; // stm * psq * wksq * bksq = 196608 - // Each uint32_t stores results of 32 positions, one per bit - uint32_t KPKBitbase[MAX_INDEX / 32]; + std::bitset KPKBitbase; // A KPK bitbase index is an integer in [0, IndexMax] range // @@ -43,8 +42,8 @@ namespace { // bit 12: side to move (WHITE or BLACK) // bit 13-14: white pawn file (from FILE_A to FILE_D) // bit 15-17: white pawn RANK_7 - rank (from RANK_7 - RANK_7 to RANK_7 - RANK_2) - unsigned index(Color us, Square bksq, Square wksq, Square psq) { - return int(wksq) | (bksq << 6) | (us << 12) | (file_of(psq) << 13) | ((RANK_7 - rank_of(psq)) << 15); + unsigned index(Color stm, Square bksq, Square wksq, Square psq) { + return int(wksq) | (bksq << 6) | (stm << 12) | (file_of(psq) << 13) | ((RANK_7 - rank_of(psq)) << 15); } enum Result { @@ -60,12 +59,9 @@ namespace { KPKPosition() = default; explicit KPKPosition(unsigned idx); operator Result() const { return result; } - Result classify(const std::vector& db) - { return us == WHITE ? classify(db) : classify(db); } + Result classify(const std::vector& db); - template Result classify(const std::vector& db); - - Color us; + Color stm; Square ksq[COLOR_NB], psq; Result result; }; @@ -73,12 +69,11 @@ namespace { } // namespace -bool Bitbases::probe(Square wksq, Square wpsq, Square bksq, Color us) { +bool Bitbases::probe(Square wksq, Square wpsq, Square bksq, Color stm) { assert(file_of(wpsq) <= FILE_D); - unsigned idx = index(us, bksq, wksq, wpsq); - return KPKBitbase[idx / 32] & (1 << (idx & 0x1F)); + return KPKBitbase[index(stm, bksq, wksq, wpsq)]; } @@ -97,10 +92,10 @@ void Bitbases::init() { for (repeat = idx = 0; idx < MAX_INDEX; ++idx) repeat |= (db[idx] == UNKNOWN && db[idx].classify(db) != UNKNOWN); - // Map 32 results into one KPKBitbase[] entry + // Fill the bitbase with the decisive results for (idx = 0; idx < MAX_INDEX; ++idx) if (db[idx] == WIN) - KPKBitbase[idx / 32] |= 1 << (idx & 0x1F); + KPKBitbase.set(idx); } @@ -110,28 +105,28 @@ namespace { ksq[WHITE] = Square((idx >> 0) & 0x3F); ksq[BLACK] = Square((idx >> 6) & 0x3F); - us = Color ((idx >> 12) & 0x01); + stm = Color ((idx >> 12) & 0x01); psq = make_square(File((idx >> 13) & 0x3), Rank(RANK_7 - ((idx >> 15) & 0x7))); - // Check if two pieces are on the same square or if a king can be captured + // Invalid if two pieces are on the same square or if a king can be captured if ( distance(ksq[WHITE], ksq[BLACK]) <= 1 || ksq[WHITE] == psq || ksq[BLACK] == psq - || (us == WHITE && (PawnAttacks[WHITE][psq] & ksq[BLACK]))) + || (stm == WHITE && (pawn_attacks_bb(WHITE, psq) & ksq[BLACK]))) result = INVALID; - // Immediate win if a pawn can be promoted without getting captured - else if ( us == WHITE + // Win if the pawn can be promoted without getting captured + else if ( stm == WHITE && rank_of(psq) == RANK_7 - && ksq[us] != psq + NORTH - && ( distance(ksq[~us], psq + NORTH) > 1 - || (PseudoAttacks[KING][ksq[us]] & (psq + NORTH)))) + && ksq[WHITE] != psq + NORTH + && ( distance(ksq[BLACK], psq + NORTH) > 1 + || (distance(ksq[WHITE], psq + NORTH) == 1))) result = WIN; - // Immediate draw if it is a stalemate or a king captures undefended pawn - else if ( us == BLACK - && ( !(PseudoAttacks[KING][ksq[us]] & ~(PseudoAttacks[KING][ksq[~us]] | PawnAttacks[~us][psq])) - || (PseudoAttacks[KING][ksq[us]] & psq & ~PseudoAttacks[KING][ksq[~us]]))) + // Draw if it is stalemate or the black king can capture the pawn + else if ( stm == BLACK + && ( !(attacks_bb(ksq[BLACK]) & ~(attacks_bb(ksq[WHITE]) | pawn_attacks_bb(WHITE, psq))) + || (attacks_bb(ksq[BLACK]) & ~attacks_bb(ksq[WHITE]) & psq))) result = DRAW; // Position will be classified later @@ -139,7 +134,6 @@ namespace { result = UNKNOWN; } - template Result KPKPosition::classify(const std::vector& db) { // White to move: If one move leads to a position classified as WIN, the result @@ -151,27 +145,25 @@ namespace { // of the current position is DRAW. If all moves lead to positions classified // as WIN, the position is classified as WIN, otherwise the current position is // classified as UNKNOWN. - - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); - constexpr Result Good = (Us == WHITE ? WIN : DRAW); - constexpr Result Bad = (Us == WHITE ? DRAW : WIN); + const Result Good = (stm == WHITE ? WIN : DRAW); + const Result Bad = (stm == WHITE ? DRAW : WIN); Result r = INVALID; - Bitboard b = PseudoAttacks[KING][ksq[Us]]; + Bitboard b = attacks_bb(ksq[stm]); while (b) - r |= Us == WHITE ? db[index(Them, ksq[Them] , pop_lsb(&b), psq)] - : db[index(Them, pop_lsb(&b), ksq[Them] , psq)]; + r |= stm == WHITE ? db[index(BLACK, ksq[BLACK] , pop_lsb(&b), psq)] + : db[index(WHITE, pop_lsb(&b), ksq[WHITE], psq)]; - if (Us == WHITE) + if (stm == WHITE) { if (rank_of(psq) < RANK_7) // Single push - r |= db[index(Them, ksq[Them], ksq[Us], psq + NORTH)]; + r |= db[index(BLACK, ksq[BLACK], ksq[WHITE], psq + NORTH)]; if ( rank_of(psq) == RANK_2 // Double push - && psq + NORTH != ksq[Us] - && psq + NORTH != ksq[Them]) - r |= db[index(Them, ksq[Them], ksq[Us], psq + NORTH + NORTH)]; + && psq + NORTH != ksq[WHITE] + && psq + NORTH != ksq[BLACK]) + r |= db[index(BLACK, ksq[BLACK], ksq[WHITE], psq + NORTH + NORTH)]; } return result = r & Good ? Good : r & UNKNOWN ? UNKNOWN : Bad; diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 70114f20..0bf7eef9 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -40,7 +40,7 @@ namespace { Bitboard RookTable[0x19000]; // To store rook attacks Bitboard BishopTable[0x1480]; // To store bishop attacks - void init_magics(Bitboard table[], Magic magics[], Direction directions[]); + void init_magics(PieceType pt, Bitboard table[], Magic magics[]); } @@ -56,8 +56,9 @@ const std::string Bitboards::pretty(Bitboard b) { for (File f = FILE_A; f <= FILE_H; ++f) s += b & make_square(f, r) ? "| X " : "| "; - s += "|\n+---+---+---+---+---+---+---+---+\n"; + s += "| " + std::to_string(1 + r) + "\n+---+---+---+---+---+---+---+---+\n"; } + s += " a b c d e f g h\n"; return s; } @@ -69,7 +70,7 @@ const std::string Bitboards::pretty(Bitboard b) { void Bitboards::init() { for (unsigned i = 0; i < (1 << 16); ++i) - PopCnt16[i] = std::bitset<16>(i).count(); + PopCnt16[i] = uint8_t(std::bitset<16>(i).count()); for (Square s = SQ_A1; s <= SQ_H8; ++s) SquareBB[s] = (1ULL << s); @@ -78,36 +79,20 @@ void Bitboards::init() { for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2) SquareDistance[s1][s2] = std::max(distance(s1, s2), distance(s1, s2)); - for (Square s = SQ_A1; s <= SQ_H8; ++s) - { - PawnAttacks[WHITE][s] = pawn_attacks_bb(square_bb(s)); - PawnAttacks[BLACK][s] = pawn_attacks_bb(square_bb(s)); - } + init_magics(ROOK, RookTable, RookMagics); + init_magics(BISHOP, BishopTable, BishopMagics); - // Helper returning the target bitboard of a step from a square - auto landing_square_bb = [&](Square s, int step) + for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1) { - Square to = Square(s + step); - return is_ok(to) && distance(s, to) <= 2 ? square_bb(to) : Bitboard(0); - }; + PawnAttacks[WHITE][s1] = pawn_attacks_bb(square_bb(s1)); + PawnAttacks[BLACK][s1] = pawn_attacks_bb(square_bb(s1)); - for (Square s = SQ_A1; s <= SQ_H8; ++s) - { for (int step : {-9, -8, -7, -1, 1, 7, 8, 9} ) - PseudoAttacks[KING][s] |= landing_square_bb(s, step); + PseudoAttacks[KING][s1] |= safe_destination(s1, step); for (int step : {-17, -15, -10, -6, 6, 10, 15, 17} ) - PseudoAttacks[KNIGHT][s] |= landing_square_bb(s, step); - } - - Direction RookDirections[] = { NORTH, EAST, SOUTH, WEST }; - Direction BishopDirections[] = { NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST }; + PseudoAttacks[KNIGHT][s1] |= safe_destination(s1, step); - init_magics(RookTable, RookMagics, RookDirections); - init_magics(BishopTable, BishopMagics, BishopDirections); - - for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1) - { PseudoAttacks[QUEEN][s1] = PseudoAttacks[BISHOP][s1] = attacks_bb(s1, 0); PseudoAttacks[QUEEN][s1] |= PseudoAttacks[ ROOK][s1] = attacks_bb< ROOK>(s1, 0); @@ -121,22 +106,20 @@ void Bitboards::init() { namespace { - Bitboard sliding_attack(Direction directions[], Square sq, Bitboard occupied) { - - Bitboard attack = 0; + Bitboard sliding_attack(PieceType pt, Square sq, Bitboard occupied) { - for (int i = 0; i < 4; ++i) - for (Square s = sq + directions[i]; - is_ok(s) && distance(s, s - directions[i]) == 1; - s += directions[i]) - { - attack |= s; + Bitboard attacks = 0; + Direction RookDirections[4] = {NORTH, SOUTH, EAST, WEST}; + Direction BishopDirections[4] = {NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST}; - if (occupied & s) - break; - } + for(Direction d : (pt == ROOK ? RookDirections : BishopDirections)) + { + Square s = sq; + while(safe_destination(s, d) && !(occupied & s)) + attacks |= (s += d); + } - return attack; + return attacks; } @@ -145,7 +128,7 @@ namespace { // www.chessprogramming.org/Magic_Bitboards. In particular, here we use the so // called "fancy" approach. - void init_magics(Bitboard table[], Magic magics[], Direction directions[]) { + void init_magics(PieceType pt, Bitboard table[], Magic magics[]) { // Optimal PRNG seeds to pick the correct magics in the shortest time int seeds[][RANK_NB] = { { 8977, 44560, 54343, 38998, 5731, 95205, 104912, 17020 }, @@ -165,7 +148,7 @@ namespace { // the number of 1s of the mask. Hence we deduce the size of the shift to // apply to the 64 or 32 bits word to get the index. Magic& m = magics[s]; - m.mask = sliding_attack(directions, s, 0) & ~edges; + m.mask = sliding_attack(pt, s, 0) & ~edges; m.shift = (Is64Bit ? 64 : 32) - popcount(m.mask); // Set the offset for the attacks table of the square. We have individual @@ -177,7 +160,7 @@ namespace { b = size = 0; do { occupancy[size] = b; - reference[size] = sliding_attack(directions, s, b); + reference[size] = sliding_attack(pt, s, b); if (HasPext) m.attacks[pext(b, m.mask)] = reference[size]; diff --git a/src/bitboard.h b/src/bitboard.h index 440de1ea..8c95de8c 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -106,10 +106,11 @@ extern Magic RookMagics[SQUARE_NB]; extern Magic BishopMagics[SQUARE_NB]; inline Bitboard square_bb(Square s) { - assert(s >= SQ_A1 && s <= SQ_H8); + assert(is_ok(s)); return SquareBB[s]; } + /// Overloads of bitwise operators between a Bitboard and a Square for testing /// whether a given bit is set in a bitboard, and for setting and clearing bits. @@ -123,38 +124,39 @@ inline Bitboard operator&(Square s, Bitboard b) { return b & s; } inline Bitboard operator|(Square s, Bitboard b) { return b | s; } inline Bitboard operator^(Square s, Bitboard b) { return b ^ s; } -inline Bitboard operator|(Square s, Square s2) { return square_bb(s) | square_bb(s2); } +inline Bitboard operator|(Square s1, Square s2) { return square_bb(s1) | s2; } constexpr bool more_than_one(Bitboard b) { return b & (b - 1); } -inline bool opposite_colors(Square s1, Square s2) { - return bool(DarkSquares & s1) != bool(DarkSquares & s2); + +constexpr bool opposite_colors(Square s1, Square s2) { + return (s1 + rank_of(s1) + s2 + rank_of(s2)) & 1; } /// rank_bb() and file_bb() return a bitboard representing all the squares on /// the given file or rank. -inline Bitboard rank_bb(Rank r) { +constexpr Bitboard rank_bb(Rank r) { return Rank1BB << (8 * r); } -inline Bitboard rank_bb(Square s) { +constexpr Bitboard rank_bb(Square s) { return rank_bb(rank_of(s)); } -inline Bitboard file_bb(File f) { +constexpr Bitboard file_bb(File f) { return FileABB << f; } -inline Bitboard file_bb(Square s) { +constexpr Bitboard file_bb(Square s) { return file_bb(file_of(s)); } -/// shift() moves a bitboard one step along direction D +/// shift() moves a bitboard one or two steps as specified by the direction D template constexpr Bitboard shift(Bitboard b) { @@ -176,6 +178,12 @@ constexpr Bitboard pawn_attacks_bb(Bitboard b) { : shift(b) | shift(b); } +inline Bitboard pawn_attacks_bb(Color c, Square s) { + + assert(is_ok(s)); + return PawnAttacks[c][s]; +} + /// pawn_double_attacks_bb() returns the squares doubly attacked by pawns of the /// given color from the squares in the given bitboard. @@ -188,19 +196,33 @@ constexpr Bitboard pawn_double_attacks_bb(Bitboard b) { /// adjacent_files_bb() returns a bitboard representing all the squares on the -/// adjacent files of the given one. +/// adjacent files of a given square. -inline Bitboard adjacent_files_bb(Square s) { +constexpr Bitboard adjacent_files_bb(Square s) { return shift(file_bb(s)) | shift(file_bb(s)); } -/// between_bb() returns squares that are linearly between the given squares -/// If the given squares are not on a same file/rank/diagonal, return 0. +/// line_bb() returns a bitboard representing an entire line (from board edge +/// to board edge) that intersects the two given squares. If the given squares +/// are not on a same file/rank/diagonal, the function returns 0. For instance, +/// line_bb(SQ_C4, SQ_F7) will return a bitboard with the A2-G8 diagonal. + +inline Bitboard line_bb(Square s1, Square s2) { + + assert(is_ok(s1) && is_ok(s2)); + return LineBB[s1][s2]; +} + + +/// between_bb() returns a bitboard representing squares that are linearly +/// between the two given squares (excluding the given squares). If the given +/// squares are not on a same file/rank/diagonal, we return 0. For instance, +/// between_bb(SQ_C4, SQ_F7) will return a bitboard with squares D5 and E6. inline Bitboard between_bb(Square s1, Square s2) { - return LineBB[s1][s2] & ( (AllSquares << (s1 + (s1 < s2))) - ^(AllSquares << (s2 + !(s1 < s2)))); + Bitboard b = line_bb(s1, s2) & ((AllSquares << s1) ^ (AllSquares << s2)); + return b & (b - 1); //exclude lsb } @@ -208,25 +230,25 @@ inline Bitboard between_bb(Square s1, Square s2) { /// in front of the given one, from the point of view of the given color. For instance, /// forward_ranks_bb(BLACK, SQ_D3) will return the 16 squares on ranks 1 and 2. -inline Bitboard forward_ranks_bb(Color c, Square s) { - return c == WHITE ? ~Rank1BB << 8 * (rank_of(s) - RANK_1) - : ~Rank8BB >> 8 * (RANK_8 - rank_of(s)); +constexpr Bitboard forward_ranks_bb(Color c, Square s) { + return c == WHITE ? ~Rank1BB << 8 * relative_rank(WHITE, s) + : ~Rank8BB >> 8 * relative_rank(BLACK, s); } /// forward_file_bb() returns a bitboard representing all the squares along the /// line in front of the given one, from the point of view of the given color. -inline Bitboard forward_file_bb(Color c, Square s) { +constexpr Bitboard forward_file_bb(Color c, Square s) { return forward_ranks_bb(c, s) & file_bb(s); } /// pawn_attack_span() returns a bitboard representing all the squares that can -/// be attacked by a pawn of the given color when it moves along its file, -/// starting from the given square. +/// be attacked by a pawn of the given color when it moves along its file, starting +/// from the given square. -inline Bitboard pawn_attack_span(Color c, Square s) { +constexpr Bitboard pawn_attack_span(Color c, Square s) { return forward_ranks_bb(c, s) & adjacent_files_bb(s); } @@ -234,8 +256,8 @@ inline Bitboard pawn_attack_span(Color c, Square s) { /// passed_pawn_span() returns a bitboard which can be used to test if a pawn of /// the given color and on the given square is a passed pawn. -inline Bitboard passed_pawn_span(Color c, Square s) { - return forward_ranks_bb(c, s) & (adjacent_files_bb(s) | file_bb(s)); +constexpr Bitboard passed_pawn_span(Color c, Square s) { + return pawn_attack_span(c, s) | forward_file_bb(c, s); } @@ -243,7 +265,7 @@ inline Bitboard passed_pawn_span(Color c, Square s) { /// straight or on a diagonal line. inline bool aligned(Square s1, Square s2, Square s3) { - return LineBB[s1][s2] & s3; + return line_bb(s1, s2) & s3; } @@ -255,23 +277,53 @@ template<> inline int distance(Square x, Square y) { return std::abs(file_ template<> inline int distance(Square x, Square y) { return std::abs(rank_of(x) - rank_of(y)); } template<> inline int distance(Square x, Square y) { return SquareDistance[x][y]; } -template constexpr const T& clamp(const T& v, const T& lo, const T& hi) { - return v < lo ? lo : v > hi ? hi : v; +inline int edge_distance(File f) { return std::min(f, File(FILE_H - f)); } +inline int edge_distance(Rank r) { return std::min(r, Rank(RANK_8 - r)); } + + +/// safe_destination() returns the bitboard of target square for the given step +/// from the given square. If the step is off the board, returns empty bitboard. + +inline Bitboard safe_destination(Square s, int step) +{ + Square to = Square(s + step); + return is_ok(to) && distance(s, to) <= 2 ? square_bb(to) : Bitboard(0); } -/// attacks_bb() returns a bitboard representing all the squares attacked by a -/// piece of type Pt (bishop or rook) placed on 's'. + +/// attacks_bb(Square) returns the pseudo attacks of the give piece type +/// assuming an empty board. + +template +inline Bitboard attacks_bb(Square s) { + + assert((Pt != PAWN) && (is_ok(s))); + + return PseudoAttacks[Pt][s]; +} + + +/// attacks_bb(Square, Bitboard) returns the attacks by the given piece +/// assuming the board is occupied according to the passed Bitboard. +/// Sliding piece attacks do not continue passed an occupied square. template inline Bitboard attacks_bb(Square s, Bitboard occupied) { - const Magic& m = Pt == ROOK ? RookMagics[s] : BishopMagics[s]; - return m.attacks[m.index(occupied)]; + assert((Pt != PAWN) && (is_ok(s))); + + switch (Pt) + { + case BISHOP: return BishopMagics[s].attacks[BishopMagics[s].index(occupied)]; + case ROOK : return RookMagics[s].attacks[ RookMagics[s].index(occupied)]; + case QUEEN : return attacks_bb(s, occupied) | attacks_bb(s, occupied); + default : return PseudoAttacks[Pt][s]; + } } inline Bitboard attacks_bb(PieceType pt, Square s, Bitboard occupied) { - assert(pt != PAWN); + assert((pt != PAWN) && (is_ok(s))); switch (pt) { @@ -376,14 +428,17 @@ inline Square msb(Bitboard b) { /// pop_lsb() finds and clears the least significant bit in a non-zero bitboard inline Square pop_lsb(Bitboard* b) { + assert(*b); const Square s = lsb(*b); *b &= *b - 1; return s; } -/// frontmost_sq() returns the most advanced square for the given color +/// frontmost_sq() returns the most advanced square for the given color, +/// requires a non-zero bitboard. inline Square frontmost_sq(Color c, Bitboard b) { + assert(b); return c == WHITE ? msb(b) : lsb(b); } diff --git a/src/endgame.cpp b/src/endgame.cpp index 2ed6ebc2..a8ceb648 100644 --- a/src/endgame.cpp +++ b/src/endgame.cpp @@ -24,42 +24,25 @@ #include "endgame.h" #include "movegen.h" -using std::string; - namespace { - // Table used to drive the king towards the edge of the board + // Used to drive the king towards the edge of the board // in KX vs K and KQ vs KR endgames. - constexpr int PushToEdges[SQUARE_NB] = { - 100, 90, 80, 70, 70, 80, 90, 100, - 90, 70, 60, 50, 50, 60, 70, 90, - 80, 60, 40, 30, 30, 40, 60, 80, - 70, 50, 30, 20, 20, 30, 50, 70, - 70, 50, 30, 20, 20, 30, 50, 70, - 80, 60, 40, 30, 30, 40, 60, 80, - 90, 70, 60, 50, 50, 60, 70, 90, - 100, 90, 80, 70, 70, 80, 90, 100 - }; - - // Table used to drive the king towards a corner square of the - // right color in KBN vs K endgames. - constexpr int PushToCorners[SQUARE_NB] = { - 6400, 6080, 5760, 5440, 5120, 4800, 4480, 4160, - 6080, 5760, 5440, 5120, 4800, 4480, 4160, 4480, - 5760, 5440, 4960, 4480, 4480, 4000, 4480, 4800, - 5440, 5120, 4480, 3840, 3520, 4480, 4800, 5120, - 5120, 4800, 4480, 3520, 3840, 4480, 5120, 5440, - 4800, 4480, 4000, 4480, 4480, 4960, 5440, 5760, - 4480, 4160, 4480, 4800, 5120, 5440, 5760, 6080, - 4160, 4480, 4800, 5120, 5440, 5760, 6080, 6400 - }; - - // Tables used to drive a piece towards or away from another piece - constexpr int PushClose[8] = { 0, 0, 100, 80, 60, 40, 20, 10 }; - constexpr int PushAway [8] = { 0, 5, 20, 40, 60, 80, 90, 100 }; - - // Pawn Rank based scaling factors used in KRPPKRP endgame - constexpr int KRPPKRPScaleFactors[RANK_NB] = { 0, 9, 10, 14, 21, 44, 0, 0 }; + // Values range from 27 (center squares) to 90 (in the corners) + inline int push_to_edge(Square s) { + int rd = edge_distance(rank_of(s)), fd = edge_distance(file_of(s)); + return 90 - (7 * fd * fd / 2 + 7 * rd * rd / 2); + } + + // Used to drive the king towards A1H8 corners in KBN vs K endgames. + // Values range from 0 on A8H1 diagonal to 7 in A1H8 corners + inline int push_to_corner(Square s) { + return abs(7 - rank_of(s) - file_of(s)); + } + + // Drive a piece close to or away from another piece + inline int push_close(Square s1, Square s2) { return 140 - 20 * distance(s1, s2); } + inline int push_away(Square s1, Square s2) { return 120 - push_close(s1, s2); } #ifndef NDEBUG bool verify_material(const Position& pos, Color c, Value npm, int pawnsCnt) { @@ -74,9 +57,9 @@ namespace { assert(pos.count(strongSide) == 1); if (file_of(pos.square(strongSide)) >= FILE_E) - sq = Square(int(sq) ^ 7); // Mirror SQ_H1 -> SQ_A1 + sq = flip_file(sq); - return strongSide == WHITE ? sq : ~sq; + return strongSide == WHITE ? sq : flip_rank(sq); } } // namespace @@ -98,8 +81,6 @@ namespace Endgames { add("KQKR"); add("KNNKP"); - add("KNPK"); - add("KNPKB"); add("KRPKR"); add("KRPKB"); add("KBPKB"); @@ -124,20 +105,20 @@ Value Endgame::operator()(const Position& pos) const { if (pos.side_to_move() == weakSide && !MoveList(pos).size()) return VALUE_DRAW; - Square winnerKSq = pos.square(strongSide); - Square loserKSq = pos.square(weakSide); + Square strongKing = pos.square(strongSide); + Square weakKing = pos.square(weakSide); Value result = pos.non_pawn_material(strongSide) + pos.count(strongSide) * PawnValueEg - + PushToEdges[loserKSq] - + PushClose[distance(winnerKSq, loserKSq)]; + + push_to_edge(weakKing) + + push_close(strongKing, weakKing); if ( pos.count(strongSide) || pos.count(strongSide) ||(pos.count(strongSide) && pos.count(strongSide)) || ( (pos.pieces(strongSide, BISHOP) & ~DarkSquares) && (pos.pieces(strongSide, BISHOP) & DarkSquares))) - result = std::min(result + VALUE_KNOWN_WIN, VALUE_MATE_IN_MAX_PLY - 1); + result = std::min(result + VALUE_KNOWN_WIN, VALUE_TB_WIN_IN_MAX_PLY - 1); return strongSide == pos.side_to_move() ? result : -result; } @@ -151,18 +132,18 @@ Value Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, KnightValueMg + BishopValueMg, 0)); assert(verify_material(pos, weakSide, VALUE_ZERO, 0)); - Square winnerKSq = pos.square(strongSide); - Square loserKSq = pos.square(weakSide); - Square bishopSq = pos.square(strongSide); + Square strongKing = pos.square(strongSide); + Square strongBishop = pos.square(strongSide); + Square weakKing = pos.square(weakSide); // If our bishop does not attack A1/H8, we flip the enemy king square // to drive to opposite corners (A8/H1). - Value result = VALUE_KNOWN_WIN - + PushClose[distance(winnerKSq, loserKSq)] - + PushToCorners[opposite_colors(bishopSq, SQ_A1) ? ~loserKSq : loserKSq]; + Value result = (VALUE_KNOWN_WIN + 3520) + + push_close(strongKing, weakKing) + + 420 * push_to_corner(opposite_colors(strongBishop, SQ_A1) ? flip_file(weakKing) : weakKing); - assert(abs(result) < VALUE_MATE_IN_MAX_PLY); + assert(abs(result) < VALUE_TB_WIN_IN_MAX_PLY); return strongSide == pos.side_to_move() ? result : -result; } @@ -175,16 +156,16 @@ Value Endgame::operator()(const Position& pos) const { assert(verify_material(pos, weakSide, VALUE_ZERO, 0)); // Assume strongSide is white and the pawn is on files A-D - Square wksq = normalize(pos, strongSide, pos.square(strongSide)); - Square bksq = normalize(pos, strongSide, pos.square(weakSide)); - Square psq = normalize(pos, strongSide, pos.square(strongSide)); + Square strongKing = normalize(pos, strongSide, pos.square(strongSide)); + Square strongPawn = normalize(pos, strongSide, pos.square(strongSide)); + Square weakKing = normalize(pos, strongSide, pos.square(weakSide)); Color us = strongSide == pos.side_to_move() ? WHITE : BLACK; - if (!Bitbases::probe(wksq, psq, bksq, us)) + if (!Bitbases::probe(strongKing, strongPawn, weakKing, us)) return VALUE_DRAW; - Value result = VALUE_KNOWN_WIN + PawnValueEg + Value(rank_of(psq)); + Value result = VALUE_KNOWN_WIN + PawnValueEg + Value(rank_of(strongPawn)); return strongSide == pos.side_to_move() ? result : -result; } @@ -200,36 +181,35 @@ Value Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, RookValueMg, 0)); assert(verify_material(pos, weakSide, VALUE_ZERO, 1)); - Square wksq = relative_square(strongSide, pos.square(strongSide)); - Square bksq = relative_square(strongSide, pos.square(weakSide)); - Square rsq = relative_square(strongSide, pos.square(strongSide)); - Square psq = relative_square(strongSide, pos.square(weakSide)); - - Square queeningSq = make_square(file_of(psq), RANK_1); + Square strongKing = pos.square(strongSide); + Square weakKing = pos.square(weakSide); + Square strongRook = pos.square(strongSide); + Square weakPawn = pos.square(weakSide); + Square queeningSquare = make_square(file_of(weakPawn), relative_rank(weakSide, RANK_8)); Value result; // If the stronger side's king is in front of the pawn, it's a win - if (forward_file_bb(WHITE, wksq) & psq) - result = RookValueEg - distance(wksq, psq); + if (forward_file_bb(strongSide, strongKing) & weakPawn) + result = RookValueEg - distance(strongKing, weakPawn); // If the weaker side's king is too far from the pawn and the rook, // it's a win. - else if ( distance(bksq, psq) >= 3 + (pos.side_to_move() == weakSide) - && distance(bksq, rsq) >= 3) - result = RookValueEg - distance(wksq, psq); + else if ( distance(weakKing, weakPawn) >= 3 + (pos.side_to_move() == weakSide) + && distance(weakKing, strongRook) >= 3) + result = RookValueEg - distance(strongKing, weakPawn); // If the pawn is far advanced and supported by the defending king, // the position is drawish - else if ( rank_of(bksq) <= RANK_3 - && distance(bksq, psq) == 1 - && rank_of(wksq) >= RANK_4 - && distance(wksq, psq) > 2 + (pos.side_to_move() == strongSide)) - result = Value(80) - 8 * distance(wksq, psq); + else if ( relative_rank(strongSide, weakKing) <= RANK_3 + && distance(weakKing, weakPawn) == 1 + && relative_rank(strongSide, strongKing) >= RANK_4 + && distance(strongKing, weakPawn) > 2 + (pos.side_to_move() == strongSide)) + result = Value(80) - 8 * distance(strongKing, weakPawn); else - result = Value(200) - 8 * ( distance(wksq, psq + SOUTH) - - distance(bksq, psq + SOUTH) - - distance(psq, queeningSq)); + result = Value(200) - 8 * ( distance(strongKing, weakPawn + pawn_push(weakSide)) + - distance(weakKing, weakPawn + pawn_push(weakSide)) + - distance(weakPawn, queeningSquare)); return strongSide == pos.side_to_move() ? result : -result; } @@ -243,7 +223,7 @@ Value Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, RookValueMg, 0)); assert(verify_material(pos, weakSide, BishopValueMg, 0)); - Value result = Value(PushToEdges[pos.square(weakSide)]); + Value result = Value(push_to_edge(pos.square(weakSide))); return strongSide == pos.side_to_move() ? result : -result; } @@ -256,9 +236,9 @@ Value Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, RookValueMg, 0)); assert(verify_material(pos, weakSide, KnightValueMg, 0)); - Square bksq = pos.square(weakSide); - Square bnsq = pos.square(weakSide); - Value result = Value(PushToEdges[bksq] + PushAway[distance(bksq, bnsq)]); + Square weakKing = pos.square(weakSide); + Square weakKnight = pos.square(weakSide); + Value result = Value(push_to_edge(weakKing) + push_away(weakKing, weakKnight)); return strongSide == pos.side_to_move() ? result : -result; } @@ -273,22 +253,22 @@ Value Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, QueenValueMg, 0)); assert(verify_material(pos, weakSide, VALUE_ZERO, 1)); - Square winnerKSq = pos.square(strongSide); - Square loserKSq = pos.square(weakSide); - Square pawnSq = pos.square(weakSide); + Square strongKing = pos.square(strongSide); + Square weakKing = pos.square(weakSide); + Square weakPawn = pos.square(weakSide); - Value result = Value(PushClose[distance(winnerKSq, loserKSq)]); + Value result = Value(push_close(strongKing, weakKing)); - if ( relative_rank(weakSide, pawnSq) != RANK_7 - || distance(loserKSq, pawnSq) != 1 - || !((FileABB | FileCBB | FileFBB | FileHBB) & pawnSq)) + if ( relative_rank(weakSide, weakPawn) != RANK_7 + || distance(weakKing, weakPawn) != 1 + || ((FileBBB | FileDBB | FileEBB | FileGBB) & weakPawn)) result += QueenValueEg - PawnValueEg; return strongSide == pos.side_to_move() ? result : -result; } -/// KQ vs KR. This is almost identical to KX vs K: We give the attacking +/// KQ vs KR. This is almost identical to KX vs K: we give the attacking /// king a bonus for having the kings close together, and for forcing the /// defending king towards the edge. If we also take care to avoid null move for /// the defending side in the search, this is usually sufficient to win KQ vs KR. @@ -298,28 +278,32 @@ Value Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, QueenValueMg, 0)); assert(verify_material(pos, weakSide, RookValueMg, 0)); - Square winnerKSq = pos.square(strongSide); - Square loserKSq = pos.square(weakSide); + Square strongKing = pos.square(strongSide); + Square weakKing = pos.square(weakSide); Value result = QueenValueEg - RookValueEg - + PushToEdges[loserKSq] - + PushClose[distance(winnerKSq, loserKSq)]; + + push_to_edge(weakKing) + + push_close(strongKing, weakKing); return strongSide == pos.side_to_move() ? result : -result; } -/// KNN vs KP. Simply push the opposing king to the corner +/// KNN vs KP. Very drawish, but there are some mate opportunities if we can +/// press the weakSide King to a corner before the pawn advances too much. template<> Value Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, 2 * KnightValueMg, 0)); assert(verify_material(pos, weakSide, VALUE_ZERO, 1)); - Value result = 2 * KnightValueEg - - PawnValueEg - + PushToEdges[pos.square(weakSide)]; + Square weakKing = pos.square(weakSide); + Square weakPawn = pos.square(weakSide); + + Value result = PawnValueEg + + 2 * push_to_edge(weakKing) + - 10 * relative_rank(weakSide, weakPawn); return strongSide == pos.side_to_move() ? result : -result; } @@ -342,51 +326,47 @@ ScaleFactor Endgame::operator()(const Position& pos) const { // No assertions about the material of weakSide, because we want draws to // be detected even when the weaker side has some pawns. - Bitboard pawns = pos.pieces(strongSide, PAWN); - File pawnsFile = file_of(lsb(pawns)); + Bitboard strongPawns = pos.pieces(strongSide, PAWN); + Bitboard allPawns = pos.pieces(PAWN); + + Square strongBishop = pos.square(strongSide); + Square weakKing = pos.square(weakSide); + Square strongKing = pos.square(strongSide); - // All pawns are on a single rook file? - if ( (pawnsFile == FILE_A || pawnsFile == FILE_H) - && !(pawns & ~file_bb(pawnsFile))) + // All strongSide pawns are on a single rook file? + if (!(strongPawns & ~FileABB) || !(strongPawns & ~FileHBB)) { - Square bishopSq = pos.square(strongSide); - Square queeningSq = relative_square(strongSide, make_square(pawnsFile, RANK_8)); - Square kingSq = pos.square(weakSide); + Square queeningSquare = relative_square(strongSide, make_square(file_of(lsb(strongPawns)), RANK_8)); - if ( opposite_colors(queeningSq, bishopSq) - && distance(queeningSq, kingSq) <= 1) + if ( opposite_colors(queeningSquare, strongBishop) + && distance(queeningSquare, weakKing) <= 1) return SCALE_FACTOR_DRAW; } // If all the pawns are on the same B or G file, then it's potentially a draw - if ( (pawnsFile == FILE_B || pawnsFile == FILE_G) - && !(pos.pieces(PAWN) & ~file_bb(pawnsFile)) + if ((!(allPawns & ~FileBBB) || !(allPawns & ~FileGBB)) && pos.non_pawn_material(weakSide) == 0 && pos.count(weakSide) >= 1) { - // Get weakSide pawn that is closest to the home rank - Square weakPawnSq = frontmost_sq(strongSide, pos.pieces(weakSide, PAWN)); - - Square strongKingSq = pos.square(strongSide); - Square weakKingSq = pos.square(weakSide); - Square bishopSq = pos.square(strongSide); + // Get the least advanced weakSide pawn + Square weakPawn = frontmost_sq(strongSide, pos.pieces(weakSide, PAWN)); // There's potential for a draw if our pawn is blocked on the 7th rank, - // the bishop cannot attack it or they only have one pawn left - if ( relative_rank(strongSide, weakPawnSq) == RANK_7 - && (pos.pieces(strongSide, PAWN) & (weakPawnSq + pawn_push(weakSide))) - && (opposite_colors(bishopSq, weakPawnSq) || pos.count(strongSide) == 1)) + // the bishop cannot attack it or they only have one pawn left. + if ( relative_rank(strongSide, weakPawn) == RANK_7 + && (strongPawns & (weakPawn + pawn_push(weakSide))) + && (opposite_colors(strongBishop, weakPawn) || !more_than_one(strongPawns))) { - int strongKingDist = distance(weakPawnSq, strongKingSq); - int weakKingDist = distance(weakPawnSq, weakKingSq); + int strongKingDist = distance(weakPawn, strongKing); + int weakKingDist = distance(weakPawn, weakKing); // It's a draw if the weak king is on its back two ranks, within 2 // squares of the blocking pawn and the strong king is not // closer. (I think this rule only fails in practically // unreachable positions such as 5k1K/6p1/6P1/8/8/3B4/8/8 w // and positions where qsearch will immediately correct the - // problem such as 8/4k1p1/6P1/1K6/3B4/8/8/8 w) - if ( relative_rank(strongSide, weakKingSq) >= RANK_7 + // problem such as 8/4k1p1/6P1/1K6/3B4/8/8/8 w). + if ( relative_rank(strongSide, weakKing) >= RANK_7 && weakKingDist <= 2 && weakKingDist <= strongKingDist) return SCALE_FACTOR_DRAW; @@ -406,15 +386,16 @@ ScaleFactor Endgame::operator()(const Position& pos) const { assert(pos.count(weakSide) == 1); assert(pos.count(weakSide) >= 1); - Square kingSq = pos.square(weakSide); - Square rsq = pos.square(weakSide); + Square strongKing = pos.square(strongSide); + Square weakKing = pos.square(weakSide); + Square weakRook = pos.square(weakSide); - if ( relative_rank(weakSide, kingSq) <= RANK_2 - && relative_rank(weakSide, pos.square(strongSide)) >= RANK_4 - && relative_rank(weakSide, rsq) == RANK_3 + if ( relative_rank(weakSide, weakKing) <= RANK_2 + && relative_rank(weakSide, strongKing) >= RANK_4 + && relative_rank(weakSide, weakRook) == RANK_3 && ( pos.pieces(weakSide, PAWN) - & pos.attacks_from(kingSq) - & pos.attacks_from(rsq, strongSide))) + & attacks_bb(weakKing) + & pawn_attacks_bb(strongSide, weakRook))) return SCALE_FACTOR_DRAW; return SCALE_FACTOR_NONE; @@ -434,89 +415,89 @@ ScaleFactor Endgame::operator()(const Position& pos) const { assert(verify_material(pos, weakSide, RookValueMg, 0)); // Assume strongSide is white and the pawn is on files A-D - Square wksq = normalize(pos, strongSide, pos.square(strongSide)); - Square bksq = normalize(pos, strongSide, pos.square(weakSide)); - Square wrsq = normalize(pos, strongSide, pos.square(strongSide)); - Square wpsq = normalize(pos, strongSide, pos.square(strongSide)); - Square brsq = normalize(pos, strongSide, pos.square(weakSide)); - - File f = file_of(wpsq); - Rank r = rank_of(wpsq); - Square queeningSq = make_square(f, RANK_8); + Square strongKing = normalize(pos, strongSide, pos.square(strongSide)); + Square strongRook = normalize(pos, strongSide, pos.square(strongSide)); + Square strongPawn = normalize(pos, strongSide, pos.square(strongSide)); + Square weakKing = normalize(pos, strongSide, pos.square(weakSide)); + Square weakRook = normalize(pos, strongSide, pos.square(weakSide)); + + File pawnFile = file_of(strongPawn); + Rank pawnRank = rank_of(strongPawn); + Square queeningSquare = make_square(pawnFile, RANK_8); int tempo = (pos.side_to_move() == strongSide); // If the pawn is not too far advanced and the defending king defends the // queening square, use the third-rank defence. - if ( r <= RANK_5 - && distance(bksq, queeningSq) <= 1 - && wksq <= SQ_H5 - && (rank_of(brsq) == RANK_6 || (r <= RANK_3 && rank_of(wrsq) != RANK_6))) + if ( pawnRank <= RANK_5 + && distance(weakKing, queeningSquare) <= 1 + && strongKing <= SQ_H5 + && (rank_of(weakRook) == RANK_6 || (pawnRank <= RANK_3 && rank_of(strongRook) != RANK_6))) return SCALE_FACTOR_DRAW; // The defending side saves a draw by checking from behind in case the pawn // has advanced to the 6th rank with the king behind. - if ( r == RANK_6 - && distance(bksq, queeningSq) <= 1 - && rank_of(wksq) + tempo <= RANK_6 - && (rank_of(brsq) == RANK_1 || (!tempo && distance(brsq, wpsq) >= 3))) + if ( pawnRank == RANK_6 + && distance(weakKing, queeningSquare) <= 1 + && rank_of(strongKing) + tempo <= RANK_6 + && (rank_of(weakRook) == RANK_1 || (!tempo && distance(weakRook, strongPawn) >= 3))) return SCALE_FACTOR_DRAW; - if ( r >= RANK_6 - && bksq == queeningSq - && rank_of(brsq) == RANK_1 - && (!tempo || distance(wksq, wpsq) >= 2)) + if ( pawnRank >= RANK_6 + && weakKing == queeningSquare + && rank_of(weakRook) == RANK_1 + && (!tempo || distance(strongKing, strongPawn) >= 2)) return SCALE_FACTOR_DRAW; // White pawn on a7 and rook on a8 is a draw if black's king is on g7 or h7 // and the black rook is behind the pawn. - if ( wpsq == SQ_A7 - && wrsq == SQ_A8 - && (bksq == SQ_H7 || bksq == SQ_G7) - && file_of(brsq) == FILE_A - && (rank_of(brsq) <= RANK_3 || file_of(wksq) >= FILE_D || rank_of(wksq) <= RANK_5)) + if ( strongPawn == SQ_A7 + && strongRook == SQ_A8 + && (weakKing == SQ_H7 || weakKing == SQ_G7) + && file_of(weakRook) == FILE_A + && (rank_of(weakRook) <= RANK_3 || file_of(strongKing) >= FILE_D || rank_of(strongKing) <= RANK_5)) return SCALE_FACTOR_DRAW; // If the defending king blocks the pawn and the attacking king is too far // away, it's a draw. - if ( r <= RANK_5 - && bksq == wpsq + NORTH - && distance(wksq, wpsq) - tempo >= 2 - && distance(wksq, brsq) - tempo >= 2) + if ( pawnRank <= RANK_5 + && weakKing == strongPawn + NORTH + && distance(strongKing, strongPawn) - tempo >= 2 + && distance(strongKing, weakRook) - tempo >= 2) return SCALE_FACTOR_DRAW; // Pawn on the 7th rank supported by the rook from behind usually wins if the // attacking king is closer to the queening square than the defending king, // and the defending king cannot gain tempi by threatening the attacking rook. - if ( r == RANK_7 - && f != FILE_A - && file_of(wrsq) == f - && wrsq != queeningSq - && (distance(wksq, queeningSq) < distance(bksq, queeningSq) - 2 + tempo) - && (distance(wksq, queeningSq) < distance(bksq, wrsq) + tempo)) - return ScaleFactor(SCALE_FACTOR_MAX - 2 * distance(wksq, queeningSq)); + if ( pawnRank == RANK_7 + && pawnFile != FILE_A + && file_of(strongRook) == pawnFile + && strongRook != queeningSquare + && (distance(strongKing, queeningSquare) < distance(weakKing, queeningSquare) - 2 + tempo) + && (distance(strongKing, queeningSquare) < distance(weakKing, strongRook) + tempo)) + return ScaleFactor(SCALE_FACTOR_MAX - 2 * distance(strongKing, queeningSquare)); // Similar to the above, but with the pawn further back - if ( f != FILE_A - && file_of(wrsq) == f - && wrsq < wpsq - && (distance(wksq, queeningSq) < distance(bksq, queeningSq) - 2 + tempo) - && (distance(wksq, wpsq + NORTH) < distance(bksq, wpsq + NORTH) - 2 + tempo) - && ( distance(bksq, wrsq) + tempo >= 3 - || ( distance(wksq, queeningSq) < distance(bksq, wrsq) + tempo - && (distance(wksq, wpsq + NORTH) < distance(bksq, wrsq) + tempo)))) + if ( pawnFile != FILE_A + && file_of(strongRook) == pawnFile + && strongRook < strongPawn + && (distance(strongKing, queeningSquare) < distance(weakKing, queeningSquare) - 2 + tempo) + && (distance(strongKing, strongPawn + NORTH) < distance(weakKing, strongPawn + NORTH) - 2 + tempo) + && ( distance(weakKing, strongRook) + tempo >= 3 + || ( distance(strongKing, queeningSquare) < distance(weakKing, strongRook) + tempo + && (distance(strongKing, strongPawn + NORTH) < distance(weakKing, strongPawn) + tempo)))) return ScaleFactor( SCALE_FACTOR_MAX - - 8 * distance(wpsq, queeningSq) - - 2 * distance(wksq, queeningSq)); + - 8 * distance(strongPawn, queeningSquare) + - 2 * distance(strongKing, queeningSquare)); // If the pawn is not far advanced and the defending king is somewhere in // the pawn's path, it's probably a draw. - if (r <= RANK_4 && bksq > wpsq) + if (pawnRank <= RANK_4 && weakKing > strongPawn) { - if (file_of(bksq) == file_of(wpsq)) + if (file_of(weakKing) == file_of(strongPawn)) return ScaleFactor(10); - if ( distance(bksq, wpsq) == 1 - && distance(wksq, bksq) > 2) - return ScaleFactor(24 - 2 * distance(wksq, bksq)); + if ( distance(weakKing, strongPawn) == 1 + && distance(strongKing, weakKing) > 2) + return ScaleFactor(24 - 2 * distance(strongKing, weakKing)); } return SCALE_FACTOR_NONE; } @@ -530,10 +511,11 @@ ScaleFactor Endgame::operator()(const Position& pos) const { // Test for a rook pawn if (pos.pieces(PAWN) & (FileABB | FileHBB)) { - Square ksq = pos.square(weakSide); - Square bsq = pos.square(weakSide); - Square psq = pos.square(strongSide); - Rank rk = relative_rank(strongSide, psq); + Square weakKing = pos.square(weakSide); + Square weakBishop = pos.square(weakSide); + Square strongKing = pos.square(strongSide); + Square strongPawn = pos.square(strongSide); + Rank pawnRank = relative_rank(strongSide, strongPawn); Direction push = pawn_push(strongSide); // If the pawn is on the 5th rank and the pawn (currently) is on @@ -541,11 +523,11 @@ ScaleFactor Endgame::operator()(const Position& pos) const { // a fortress. Depending on the king position give a moderate // reduction or a stronger one if the defending king is near the // corner but not trapped there. - if (rk == RANK_5 && !opposite_colors(bsq, psq)) + if (pawnRank == RANK_5 && !opposite_colors(weakBishop, strongPawn)) { - int d = distance(psq + 3 * push, ksq); + int d = distance(strongPawn + 3 * push, weakKing); - if (d <= 2 && !(d == 0 && ksq == pos.square(strongSide) + 2 * push)) + if (d <= 2 && !(d == 0 && weakKing == strongKing + 2 * push)) return ScaleFactor(24); else return ScaleFactor(48); @@ -555,10 +537,10 @@ ScaleFactor Endgame::operator()(const Position& pos) const { // it's drawn if the bishop attacks the square in front of the // pawn from a reasonable distance and the defending king is near // the corner - if ( rk == RANK_6 - && distance(psq + 2 * push, ksq) <= 1 - && (PseudoAttacks[BISHOP][bsq] & (psq + push)) - && distance(bsq, psq) >= 2) + if ( pawnRank == RANK_6 + && distance(strongPawn + 2 * push, weakKing) <= 1 + && (attacks_bb(weakBishop) & (strongPawn + push)) + && distance(weakBishop, strongPawn) >= 2) return ScaleFactor(8); } @@ -573,28 +555,28 @@ ScaleFactor Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, RookValueMg, 2)); assert(verify_material(pos, weakSide, RookValueMg, 1)); - Square wpsq1 = pos.squares(strongSide)[0]; - Square wpsq2 = pos.squares(strongSide)[1]; - Square bksq = pos.square(weakSide); + Square strongPawn1 = pos.squares(strongSide)[0]; + Square strongPawn2 = pos.squares(strongSide)[1]; + Square weakKing = pos.square(weakSide); // Does the stronger side have a passed pawn? - if (pos.pawn_passed(strongSide, wpsq1) || pos.pawn_passed(strongSide, wpsq2)) + if (pos.pawn_passed(strongSide, strongPawn1) || pos.pawn_passed(strongSide, strongPawn2)) return SCALE_FACTOR_NONE; - Rank r = std::max(relative_rank(strongSide, wpsq1), relative_rank(strongSide, wpsq2)); + Rank pawnRank = std::max(relative_rank(strongSide, strongPawn1), relative_rank(strongSide, strongPawn2)); - if ( distance(bksq, wpsq1) <= 1 - && distance(bksq, wpsq2) <= 1 - && relative_rank(strongSide, bksq) > r) + if ( distance(weakKing, strongPawn1) <= 1 + && distance(weakKing, strongPawn2) <= 1 + && relative_rank(strongSide, weakKing) > pawnRank) { - assert(r > RANK_1 && r < RANK_7); - return ScaleFactor(KRPPKRPScaleFactors[r]); + assert(pawnRank > RANK_1 && pawnRank < RANK_7); + return ScaleFactor(7 * pawnRank); } return SCALE_FACTOR_NONE; } -/// K and two or more pawns vs K. There is just a single rule here: If all pawns +/// K and two or more pawns vs K. There is just a single rule here: if all pawns /// are on the same rook file and are blocked by the defending king, it's a draw. template<> ScaleFactor Endgame::operator()(const Position& pos) const { @@ -603,14 +585,12 @@ ScaleFactor Endgame::operator()(const Position& pos) const { assert(pos.count(strongSide) >= 2); assert(verify_material(pos, weakSide, VALUE_ZERO, 0)); - Square ksq = pos.square(weakSide); - Bitboard pawns = pos.pieces(strongSide, PAWN); + Square weakKing = pos.square(weakSide); + Bitboard strongPawns = pos.pieces(strongSide, PAWN); - // If all pawns are ahead of the king, on a single rook file and - // the king is within one file of the pawns, it's a draw. - if ( !(pawns & ~forward_ranks_bb(weakSide, ksq)) - && !((pawns & ~FileABB) && (pawns & ~FileHBB)) - && distance(ksq, lsb(pawns)) <= 1) + // If all pawns are ahead of the king on a single rook file, it's a draw. + if ( !(strongPawns & ~(FileABB | FileHBB)) + && !(strongPawns & ~passed_pawn_span(weakSide, weakKing))) return SCALE_FACTOR_DRAW; return SCALE_FACTOR_NONE; @@ -627,20 +607,19 @@ ScaleFactor Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, BishopValueMg, 1)); assert(verify_material(pos, weakSide, BishopValueMg, 0)); - Square pawnSq = pos.square(strongSide); - Square strongBishopSq = pos.square(strongSide); - Square weakBishopSq = pos.square(weakSide); - Square weakKingSq = pos.square(weakSide); + Square strongPawn = pos.square(strongSide); + Square strongBishop = pos.square(strongSide); + Square weakBishop = pos.square(weakSide); + Square weakKing = pos.square(weakSide); // Case 1: Defending king blocks the pawn, and cannot be driven away - if ( file_of(weakKingSq) == file_of(pawnSq) - && relative_rank(strongSide, pawnSq) < relative_rank(strongSide, weakKingSq) - && ( opposite_colors(weakKingSq, strongBishopSq) - || relative_rank(strongSide, weakKingSq) <= RANK_6)) + if ( (forward_file_bb(strongSide, strongPawn) & weakKing) + && ( opposite_colors(weakKing, strongBishop) + || relative_rank(strongSide, weakKing) <= RANK_6)) return SCALE_FACTOR_DRAW; // Case 2: Opposite colored bishops - if (opposite_colors(strongBishopSq, weakBishopSq)) + if (opposite_colors(strongBishop, weakBishop)) return SCALE_FACTOR_DRAW; return SCALE_FACTOR_NONE; @@ -654,36 +633,36 @@ ScaleFactor Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, BishopValueMg, 2)); assert(verify_material(pos, weakSide, BishopValueMg, 0)); - Square wbsq = pos.square(strongSide); - Square bbsq = pos.square(weakSide); + Square strongBishop = pos.square(strongSide); + Square weakBishop = pos.square(weakSide); - if (!opposite_colors(wbsq, bbsq)) + if (!opposite_colors(strongBishop, weakBishop)) return SCALE_FACTOR_NONE; - Square ksq = pos.square(weakSide); - Square psq1 = pos.squares(strongSide)[0]; - Square psq2 = pos.squares(strongSide)[1]; + Square weakKing = pos.square(weakSide); + Square strongPawn1 = pos.squares(strongSide)[0]; + Square strongPawn2 = pos.squares(strongSide)[1]; Square blockSq1, blockSq2; - if (relative_rank(strongSide, psq1) > relative_rank(strongSide, psq2)) + if (relative_rank(strongSide, strongPawn1) > relative_rank(strongSide, strongPawn2)) { - blockSq1 = psq1 + pawn_push(strongSide); - blockSq2 = make_square(file_of(psq2), rank_of(psq1)); + blockSq1 = strongPawn1 + pawn_push(strongSide); + blockSq2 = make_square(file_of(strongPawn2), rank_of(strongPawn1)); } else { - blockSq1 = psq2 + pawn_push(strongSide); - blockSq2 = make_square(file_of(psq1), rank_of(psq2)); + blockSq1 = strongPawn2 + pawn_push(strongSide); + blockSq2 = make_square(file_of(strongPawn1), rank_of(strongPawn2)); } - switch (distance(psq1, psq2)) + switch (distance(strongPawn1, strongPawn2)) { case 0: // Both pawns are on the same file. It's an easy draw if the defender firmly // controls some square in the frontmost pawn's path. - if ( file_of(ksq) == file_of(blockSq1) - && relative_rank(strongSide, ksq) >= relative_rank(strongSide, blockSq1) - && opposite_colors(ksq, wbsq)) + if ( file_of(weakKing) == file_of(blockSq1) + && relative_rank(strongSide, weakKing) >= relative_rank(strongSide, blockSq1) + && opposite_colors(weakKing, strongBishop)) return SCALE_FACTOR_DRAW; else return SCALE_FACTOR_NONE; @@ -692,17 +671,17 @@ ScaleFactor Endgame::operator()(const Position& pos) const { // Pawns on adjacent files. It's a draw if the defender firmly controls the // square in front of the frontmost pawn's path, and the square diagonally // behind this square on the file of the other pawn. - if ( ksq == blockSq1 - && opposite_colors(ksq, wbsq) - && ( bbsq == blockSq2 - || (pos.attacks_from(blockSq2) & pos.pieces(weakSide, BISHOP)) - || distance(psq1, psq2) >= 2)) + if ( weakKing == blockSq1 + && opposite_colors(weakKing, strongBishop) + && ( weakBishop == blockSq2 + || (attacks_bb(blockSq2, pos.pieces()) & pos.pieces(weakSide, BISHOP)) + || distance(strongPawn1, strongPawn2) >= 2)) return SCALE_FACTOR_DRAW; - else if ( ksq == blockSq2 - && opposite_colors(ksq, wbsq) - && ( bbsq == blockSq1 - || (pos.attacks_from(blockSq1) & pos.pieces(weakSide, BISHOP)))) + else if ( weakKing == blockSq2 + && opposite_colors(weakKing, strongBishop) + && ( weakBishop == blockSq1 + || (attacks_bb(blockSq1, pos.pieces()) & pos.pieces(weakSide, BISHOP)))) return SCALE_FACTOR_DRAW; else return SCALE_FACTOR_NONE; @@ -714,7 +693,7 @@ ScaleFactor Endgame::operator()(const Position& pos) const { } -/// KBP vs KN. There is a single rule: If the defending king is somewhere along +/// KBP vs KN. There is a single rule: if the defending king is somewhere along /// the path of the pawn, and the square of the king is not of the same color as /// the stronger side's bishop, it's a draw. template<> @@ -723,62 +702,22 @@ ScaleFactor Endgame::operator()(const Position& pos) const { assert(verify_material(pos, strongSide, BishopValueMg, 1)); assert(verify_material(pos, weakSide, KnightValueMg, 0)); - Square pawnSq = pos.square(strongSide); - Square strongBishopSq = pos.square(strongSide); - Square weakKingSq = pos.square(weakSide); + Square strongPawn = pos.square(strongSide); + Square strongBishop = pos.square(strongSide); + Square weakKing = pos.square(weakSide); - if ( file_of(weakKingSq) == file_of(pawnSq) - && relative_rank(strongSide, pawnSq) < relative_rank(strongSide, weakKingSq) - && ( opposite_colors(weakKingSq, strongBishopSq) - || relative_rank(strongSide, weakKingSq) <= RANK_6)) + if ( file_of(weakKing) == file_of(strongPawn) + && relative_rank(strongSide, strongPawn) < relative_rank(strongSide, weakKing) + && ( opposite_colors(weakKing, strongBishop) + || relative_rank(strongSide, weakKing) <= RANK_6)) return SCALE_FACTOR_DRAW; return SCALE_FACTOR_NONE; } -/// KNP vs K. There is a single rule: if the pawn is a rook pawn on the 7th rank -/// and the defending king prevents the pawn from advancing, the position is drawn. -template<> -ScaleFactor Endgame::operator()(const Position& pos) const { - - assert(verify_material(pos, strongSide, KnightValueMg, 1)); - assert(verify_material(pos, weakSide, VALUE_ZERO, 0)); - - // Assume strongSide is white and the pawn is on files A-D - Square pawnSq = normalize(pos, strongSide, pos.square(strongSide)); - Square weakKingSq = normalize(pos, strongSide, pos.square(weakSide)); - - if (pawnSq == SQ_A7 && distance(SQ_A8, weakKingSq) <= 1) - return SCALE_FACTOR_DRAW; - - return SCALE_FACTOR_NONE; -} - - -/// KNP vs KB. If knight can block bishop from taking pawn, it's a win. -/// Otherwise the position is drawn. -template<> -ScaleFactor Endgame::operator()(const Position& pos) const { - - assert(verify_material(pos, strongSide, KnightValueMg, 1)); - assert(verify_material(pos, weakSide, BishopValueMg, 0)); - - Square pawnSq = pos.square(strongSide); - Square bishopSq = pos.square(weakSide); - Square weakKingSq = pos.square(weakSide); - - // King needs to get close to promoting pawn to prevent knight from blocking. - // Rules for this are very tricky, so just approximate. - if (forward_file_bb(strongSide, pawnSq) & pos.attacks_from(bishopSq)) - return ScaleFactor(distance(weakKingSq, pawnSq)); - - return SCALE_FACTOR_NONE; -} - - /// KP vs KP. This is done by removing the weakest side's pawn and probing the -/// KP vs K bitbase: If the weakest side has a draw without the pawn, it probably +/// KP vs K bitbase: if the weakest side has a draw without the pawn, it probably /// has at least a draw with the pawn as well. The exception is when the stronger /// side's pawn is far advanced and not on a rook file; in this case it is often /// possible to win (e.g. 8/4k3/3p4/3P4/6K1/8/8/8 w - - 0 1). @@ -789,18 +728,18 @@ ScaleFactor Endgame::operator()(const Position& pos) const { assert(verify_material(pos, weakSide, VALUE_ZERO, 1)); // Assume strongSide is white and the pawn is on files A-D - Square wksq = normalize(pos, strongSide, pos.square(strongSide)); - Square bksq = normalize(pos, strongSide, pos.square(weakSide)); - Square psq = normalize(pos, strongSide, pos.square(strongSide)); + Square strongKing = normalize(pos, strongSide, pos.square(strongSide)); + Square weakKing = normalize(pos, strongSide, pos.square(weakSide)); + Square strongPawn = normalize(pos, strongSide, pos.square(strongSide)); Color us = strongSide == pos.side_to_move() ? WHITE : BLACK; // If the pawn has advanced to the fifth rank or further, and is not a // rook pawn, it's too dangerous to assume that it's at least a draw. - if (rank_of(psq) >= RANK_5 && file_of(psq) != FILE_A) + if (rank_of(strongPawn) >= RANK_5 && file_of(strongPawn) != FILE_A) return SCALE_FACTOR_NONE; // Probe the KPK bitbase with the weakest side's pawn removed. If it's a draw, // it's probably at least a draw even with the pawn. - return Bitbases::probe(wksq, psq, bksq, us) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW; + return Bitbases::probe(strongKing, strongPawn, weakKing, us) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW; } diff --git a/src/endgame.h b/src/endgame.h index 4642e448..fd1aba2d 100644 --- a/src/endgame.h +++ b/src/endgame.h @@ -21,10 +21,10 @@ #ifndef ENDGAME_H_INCLUDED #define ENDGAME_H_INCLUDED -#include #include #include #include +#include #include #include "position.h" @@ -57,8 +57,6 @@ enum EndgameCode { KBPKB, // KBP vs KB KBPPKB, // KBPP vs KB KBPKN, // KBP vs KN - KNPK, // KNP vs K - KNPKB, // KNP vs KB KPKP // KP vs KP }; diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 7c7ce95c..b34d82f6 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -35,7 +35,7 @@ namespace Trace { enum Tracing { NO_TRACE, TRACE }; enum Term { // The first 8 entries are reserved for PieceType - MATERIAL = 8, IMBALANCE, MOBILITY, THREAT, PASSED, SPACE, INITIATIVE, TOTAL, TERM_NB + MATERIAL = 8, IMBALANCE, MOBILITY, THREAT, PASSED, SPACE, WINNABLE, TOTAL, TERM_NB }; Score scores[TERM_NB][COLOR_NB]; @@ -59,7 +59,7 @@ namespace Trace { std::ostream& operator<<(std::ostream& os, Term t) { - if (t == MATERIAL || t == IMBALANCE || t == INITIATIVE || t == TOTAL) + if (t == MATERIAL || t == IMBALANCE || t == WINNABLE || t == TOTAL) os << " ---- ----" << " | " << " ---- ----"; else os << scores[t][WHITE] << " | " << scores[t][BLACK]; @@ -74,79 +74,92 @@ using namespace Trace; namespace { // Threshold for lazy and space evaluation - constexpr Value LazyThreshold = Value(1400); + constexpr Value LazyThreshold1 = Value(1400); + constexpr Value LazyThreshold2 = Value(1300); constexpr Value SpaceThreshold = Value(12222); // KingAttackWeights[PieceType] contains king attack weights by piece type constexpr int KingAttackWeights[PIECE_TYPE_NB] = { 0, 0, 81, 52, 44, 10 }; - // Penalties for enemy's safe checks - constexpr int QueenSafeCheck = 780; - constexpr int RookSafeCheck = 1080; - constexpr int BishopSafeCheck = 635; - constexpr int KnightSafeCheck = 790; + // SafeCheck[PieceType][single/multiple] contains safe check bonus by piece type, + // higher if multiple safe checks are possible for that piece type. + constexpr int SafeCheck[][2] = { + {}, {}, {792, 1283}, {645, 967}, {1084, 1897}, {772, 1119} + }; #define S(mg, eg) make_score(mg, eg) // MobilityBonus[PieceType-2][attacked] contains bonuses for middle and end game, // indexed by piece type and number of attacked squares in the mobility area. constexpr Score MobilityBonus[][32] = { - { S(-62,-81), S(-53,-56), S(-12,-30), S( -4,-14), S( 3, 8), S( 13, 15), // Knights - S( 22, 23), S( 28, 27), S( 33, 33) }, - { S(-48,-59), S(-20,-23), S( 16, -3), S( 26, 13), S( 38, 24), S( 51, 42), // Bishops + { S(-62,-81), S(-53,-56), S(-12,-31), S( -4,-16), S( 3, 5), S( 13, 11), // Knight + S( 22, 17), S( 28, 20), S( 33, 25) }, + { S(-48,-59), S(-20,-23), S( 16, -3), S( 26, 13), S( 38, 24), S( 51, 42), // Bishop S( 55, 54), S( 63, 57), S( 63, 65), S( 68, 73), S( 81, 78), S( 81, 86), S( 91, 88), S( 98, 97) }, - { S(-58,-76), S(-27,-18), S(-15, 28), S(-10, 55), S( -5, 69), S( -2, 82), // Rooks - S( 9,112), S( 16,118), S( 30,132), S( 29,142), S( 32,155), S( 38,165), - S( 46,166), S( 48,169), S( 58,171) }, - { S(-39,-36), S(-21,-15), S( 3, 8), S( 3, 18), S( 14, 34), S( 22, 54), // Queens - S( 28, 61), S( 41, 73), S( 43, 79), S( 48, 92), S( 56, 94), S( 60,104), - S( 60,113), S( 66,120), S( 67,123), S( 70,126), S( 71,133), S( 73,136), - S( 79,140), S( 88,143), S( 88,148), S( 99,166), S(102,170), S(102,175), - S(106,184), S(109,191), S(113,206), S(116,212) } + { S(-60,-78), S(-20,-17), S( 2, 23), S( 3, 39), S( 3, 70), S( 11, 99), // Rook + S( 22,103), S( 31,121), S( 40,134), S( 40,139), S( 41,158), S( 48,164), + S( 57,168), S( 57,169), S( 62,172) }, + { S(-30,-48), S(-12,-30), S( -8, -7), S( -9, 19), S( 20, 40), S( 23, 55), // Queen + S( 23, 59), S( 35, 75), S( 38, 78), S( 53, 96), S( 64, 96), S( 65,100), + S( 65,121), S( 66,127), S( 67,131), S( 67,133), S( 72,136), S( 72,141), + S( 77,147), S( 79,150), S( 93,151), S(108,168), S(108,168), S(108,171), + S(110,182), S(114,182), S(114,192), S(116,219) } + }; + + // KingProtector[knight/bishop] contains penalty for each distance unit to own king + constexpr Score KingProtector[] = { S(8, 9), S(6, 9) }; + + // Outpost[knight/bishop] contains bonuses for each knight or bishop occupying a + // pawn protected square on rank 4 to 6 which is also safe from a pawn attack. + constexpr Score Outpost[] = { S(56, 36), S(30, 23) }; + + // PassedRank[Rank] contains a bonus according to the rank of a passed pawn + constexpr Score PassedRank[RANK_NB] = { + S(0, 0), S(10, 28), S(17, 33), S(15, 41), S(62, 72), S(168, 177), S(276, 260) }; // RookOnFile[semiopen/open] contains bonuses for each rook when there is // no (friendly) pawn on the rook file. - constexpr Score RookOnFile[] = { S(21, 4), S(47, 25) }; + constexpr Score RookOnFile[] = { S(19, 7), S(48, 29) }; // ThreatByMinor/ByRook[attacked PieceType] contains bonuses according to // which piece type attacks which one. Attacks on lesser pieces which are // pawn-defended are not considered. constexpr Score ThreatByMinor[PIECE_TYPE_NB] = { - S(0, 0), S(6, 32), S(59, 41), S(79, 56), S(90, 119), S(79, 161) + S(0, 0), S(5, 32), S(57, 41), S(77, 56), S(88, 119), S(79, 161) }; constexpr Score ThreatByRook[PIECE_TYPE_NB] = { - S(0, 0), S(3, 44), S(38, 71), S(38, 61), S(0, 38), S(51, 38) - }; - - // PassedRank[Rank] contains a bonus according to the rank of a passed pawn - constexpr Score PassedRank[RANK_NB] = { - S(0, 0), S(10, 28), S(17, 33), S(15, 41), S(62, 72), S(168, 177), S(276, 260) + S(0, 0), S(3, 46), S(37, 68), S(42, 60), S(0, 38), S(58, 41) }; // Assorted bonuses and penalties - constexpr Score BishopPawns = S( 3, 7); - constexpr Score CorneredBishop = S( 50, 50); - constexpr Score FlankAttacks = S( 8, 0); - constexpr Score Hanging = S( 69, 36); - constexpr Score KingProtector = S( 7, 8); - constexpr Score KnightOnQueen = S( 16, 12); - constexpr Score LongDiagonalBishop = S( 45, 0); - constexpr Score MinorBehindPawn = S( 18, 3); - constexpr Score Outpost = S( 30, 21); - constexpr Score PassedFile = S( 11, 8); - constexpr Score PawnlessFlank = S( 17, 95); - constexpr Score RestrictedPiece = S( 7, 7); - constexpr Score ReachableOutpost = S( 32, 10); - constexpr Score RookOnQueenFile = S( 7, 6); - constexpr Score SliderOnQueen = S( 59, 18); - constexpr Score ThreatByKing = S( 24, 89); - constexpr Score ThreatByPawnPush = S( 48, 39); - constexpr Score ThreatBySafePawn = S(173, 94); - constexpr Score TrappedRook = S( 52, 10); - constexpr Score WeakQueen = S( 49, 15); + constexpr Score BadOutpost = S( -7, 36); + constexpr Score BishopOnKingRing = S( 24, 0); + constexpr Score BishopPawns = S( 3, 7); + constexpr Score BishopXRayPawns = S( 4, 5); + constexpr Score CorneredBishop = S( 50, 50); + constexpr Score FlankAttacks = S( 8, 0); + constexpr Score Hanging = S( 69, 36); + constexpr Score KnightOnQueen = S( 16, 11); + constexpr Score LongDiagonalBishop = S( 45, 0); + constexpr Score MinorBehindPawn = S( 18, 3); + constexpr Score PassedFile = S( 11, 8); + constexpr Score PawnlessFlank = S( 17, 95); + constexpr Score QueenInfiltration = S( -2, 14); + constexpr Score ReachableOutpost = S( 31, 22); + constexpr Score RestrictedPiece = S( 7, 7); + constexpr Score RookOnKingRing = S( 16, 0); + constexpr Score RookOnQueenFile = S( 6, 11); + constexpr Score SliderOnQueen = S( 60, 18); + constexpr Score ThreatByKing = S( 24, 89); + constexpr Score ThreatByPawnPush = S( 48, 39); + constexpr Score ThreatBySafePawn = S(173, 94); + constexpr Score TrappedRook = S( 55, 13); + constexpr Score WeakQueenProtection = S( 14, 0); + constexpr Score WeakQueen = S( 56, 15); + #undef S @@ -167,8 +180,7 @@ namespace { template Score threats() const; template Score passed() const; template Score space() const; - ScaleFactor scale_factor(Value eg) const; - Score initiative(Score score) const; + Value winnable(Score score) const; const Position& pos; Material::Entry* me; @@ -210,10 +222,11 @@ namespace { // Evaluation::initialize() computes king and pawn attacks, and the king ring // bitboard for a given color. This is done at the beginning of the evaluation. + template template void Evaluation::initialize() { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; constexpr Direction Up = pawn_push(Us); constexpr Direction Down = -Up; constexpr Bitboard LowRanks = (Us == WHITE ? Rank2BB | Rank3BB : Rank7BB | Rank6BB); @@ -230,15 +243,15 @@ namespace { mobilityArea[Us] = ~(b | pos.pieces(Us, KING, QUEEN) | pos.blockers_for_king(Us) | pe->pawn_attacks(Them)); // Initialize attackedBy[] for king and pawns - attackedBy[Us][KING] = pos.attacks_from(ksq); + attackedBy[Us][KING] = attacks_bb(ksq); attackedBy[Us][PAWN] = pe->pawn_attacks(Us); attackedBy[Us][ALL_PIECES] = attackedBy[Us][KING] | attackedBy[Us][PAWN]; attackedBy2[Us] = dblAttackByPawn | (attackedBy[Us][KING] & attackedBy[Us][PAWN]); // Init our king safety tables - Square s = make_square(clamp(file_of(ksq), FILE_B, FILE_G), - clamp(rank_of(ksq), RANK_2, RANK_7)); - kingRing[Us] = PseudoAttacks[KING][s] | s; + Square s = make_square(Utility::clamp(file_of(ksq), FILE_B, FILE_G), + Utility::clamp(rank_of(ksq), RANK_2, RANK_7)); + kingRing[Us] = attacks_bb(s) | s; kingAttackersCount[Them] = popcount(kingRing[Us] & pe->pawn_attacks(Them)); kingAttacksCount[Them] = kingAttackersWeight[Them] = 0; @@ -249,10 +262,11 @@ namespace { // Evaluation::pieces() scores pieces of a given color and type + template template Score Evaluation::pieces() { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; constexpr Direction Down = -pawn_push(Us); constexpr Bitboard OutpostRanks = (Us == WHITE ? Rank4BB | Rank5BB | Rank6BB : Rank5BB | Rank4BB | Rank3BB); @@ -268,10 +282,10 @@ namespace { // Find attacked squares, including x-ray attacks for bishops and rooks b = Pt == BISHOP ? attacks_bb(s, pos.pieces() ^ pos.pieces(QUEEN)) : Pt == ROOK ? attacks_bb< ROOK>(s, pos.pieces() ^ pos.pieces(QUEEN) ^ pos.pieces(Us, ROOK)) - : pos.attacks_from(s); + : attacks_bb(s, pos.pieces()); if (pos.blockers_for_king(Us) & s) - b &= LineBB[pos.square(Us)][s]; + b &= line_bb(pos.square(Us), s); attackedBy2[Us] |= attackedBy[Us][ALL_PIECES] & b; attackedBy[Us][Pt] |= b; @@ -284,35 +298,52 @@ namespace { kingAttacksCount[Us] += popcount(b & attackedBy[Them][KING]); } + else if (Pt == ROOK && (file_bb(s) & kingRing[Them])) + score += RookOnKingRing; + + else if (Pt == BISHOP && (attacks_bb(s, pos.pieces(PAWN)) & kingRing[Them])) + score += BishopOnKingRing; + int mob = popcount(b & mobilityArea[Us]); mobility[Us] += MobilityBonus[Pt - 2][mob]; if (Pt == BISHOP || Pt == KNIGHT) { - // Bonus if piece is on an outpost square or can reach one + // Bonus if the piece is on an outpost square or can reach one + // Reduced bonus for knights (BadOutpost) if few relevant targets bb = OutpostRanks & attackedBy[Us][PAWN] & ~pe->pawn_attacks_span(Them); - if (bb & s) - score += Outpost * (Pt == KNIGHT ? 2 : 1); - + Bitboard targets = pos.pieces(Them) & ~pos.pieces(PAWN); + + if ( Pt == KNIGHT + && bb & s & ~CenterFiles // on a side outpost + && !(b & targets) // no relevant attacks + && (!more_than_one(targets & (s & QueenSide ? QueenSide : KingSide)))) + score += BadOutpost; + else if (bb & s) + score += Outpost[Pt == BISHOP]; else if (Pt == KNIGHT && bb & b & ~pos.pieces(Us)) score += ReachableOutpost; - // Knight and Bishop bonus for being right behind a pawn + // Bonus for a knight or bishop shielded by pawn if (shift(pos.pieces(PAWN)) & s) score += MinorBehindPawn; // Penalty if the piece is far from the king - score -= KingProtector * distance(s, pos.square(Us)); + score -= KingProtector[Pt == BISHOP] * distance(pos.square(Us), s); if (Pt == BISHOP) { - // Penalty according to number of pawns on the same color square as the - // bishop, bigger when the center files are blocked with pawns. + // Penalty according to the number of our pawns on the same color square as the + // bishop, bigger when the center files are blocked with pawns and smaller + // when the bishop is outside the pawn chain. Bitboard blocked = pos.pieces(Us, PAWN) & shift(pos.pieces()); score -= BishopPawns * pos.pawns_on_same_color_squares(Us, s) - * (1 + popcount(blocked & CenterFiles)); + * (!(attackedBy[Us][PAWN] & s) + popcount(blocked & CenterFiles)); + + // Penalty for all enemy pawns x-rayed + score -= BishopXRayPawns * popcount(attacks_bb(s) & pos.pieces(Them, PAWN)); // Bonus for bishop on a long diagonal which can "see" both center squares if (more_than_one(attacks_bb(s, pos.pieces(PAWN)) & Center)) @@ -358,6 +389,10 @@ namespace { Bitboard queenPinners; if (pos.slider_blockers(pos.pieces(Them, ROOK, BISHOP), s, queenPinners)) score -= WeakQueen; + + // Bonus for queen on weak square in enemy camp + if (relative_rank(Us, s) > RANK_4 && (~pe->pawn_attacks_span(Them) & s)) + score += QueenInfiltration; } } if (T) @@ -368,10 +403,11 @@ namespace { // Evaluation::king() assigns bonuses and penalties to a king of a given color + template template Score Evaluation::king() const { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; constexpr Bitboard Camp = (Us == WHITE ? AllSquares ^ Rank6BB ^ Rank7BB ^ Rank8BB : AllSquares ^ Rank1BB ^ Rank2BB ^ Rank3BB); @@ -396,41 +432,33 @@ namespace { b2 = attacks_bb(ksq, pos.pieces() ^ pos.pieces(Us, QUEEN)); // Enemy rooks checks - rookChecks = b1 & safe & attackedBy[Them][ROOK]; - + rookChecks = b1 & attackedBy[Them][ROOK] & safe; if (rookChecks) - kingDanger += RookSafeCheck; + kingDanger += SafeCheck[ROOK][more_than_one(rookChecks)]; else unsafeChecks |= b1 & attackedBy[Them][ROOK]; - // Enemy queen safe checks: we count them only if they are from squares from - // which we can't give a rook check, because rook checks are more valuable. - queenChecks = (b1 | b2) - & attackedBy[Them][QUEEN] - & safe - & ~attackedBy[Us][QUEEN] - & ~rookChecks; - + // Enemy queen safe checks: count them only if the checks are from squares from + // which opponent cannot give a rook check, because rook checks are more valuable. + queenChecks = (b1 | b2) & attackedBy[Them][QUEEN] & safe + & ~(attackedBy[Us][QUEEN] | rookChecks); if (queenChecks) - kingDanger += QueenSafeCheck; + kingDanger += SafeCheck[QUEEN][more_than_one(queenChecks)]; - // Enemy bishops checks: we count them only if they are from squares from - // which we can't give a queen check, because queen checks are more valuable. - bishopChecks = b2 - & attackedBy[Them][BISHOP] - & safe + // Enemy bishops checks: count them only if they are from squares from which + // opponent cannot give a queen check, because queen checks are more valuable. + bishopChecks = b2 & attackedBy[Them][BISHOP] & safe & ~queenChecks; - if (bishopChecks) - kingDanger += BishopSafeCheck; + kingDanger += SafeCheck[BISHOP][more_than_one(bishopChecks)]; + else unsafeChecks |= b2 & attackedBy[Them][BISHOP]; // Enemy knights checks - knightChecks = pos.attacks_from(ksq) & attackedBy[Them][KNIGHT]; - + knightChecks = attacks_bb(ksq) & attackedBy[Them][KNIGHT]; if (knightChecks & safe) - kingDanger += KnightSafeCheck; + kingDanger += SafeCheck[KNIGHT][more_than_one(knightChecks & safe)]; else unsafeChecks |= knightChecks; @@ -440,7 +468,7 @@ namespace { b2 = b1 & attackedBy2[Them]; b3 = attackedBy[Us][ALL_PIECES] & KingFlank[file_of(ksq)] & Camp; - int kingFlankAttack = popcount(b1) + popcount(b2); + int kingFlankAttack = popcount(b1) + popcount(b2); int kingFlankDefense = popcount(b3); kingDanger += kingAttackersCount[Them] * kingAttackersWeight[Them] @@ -476,10 +504,11 @@ namespace { // Evaluation::threats() assigns bonuses according to the types of the // attacking and the attacked pieces. + template template Score Evaluation::threats() const { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; constexpr Direction Up = pawn_push(Us); constexpr Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB); @@ -517,13 +546,15 @@ namespace { b = ~attackedBy[Them][ALL_PIECES] | (nonPawnEnemies & attackedBy2[Us]); score += Hanging * popcount(weak & b); + + // Additional bonus if weak piece is only protected by a queen + score += WeakQueenProtection * popcount(weak & attackedBy[Them][QUEEN]); } // Bonus for restricting their piece moves b = attackedBy[Them][ALL_PIECES] & ~stronglyProtected & attackedBy[Us][ALL_PIECES]; - score += RestrictedPiece * popcount(b); // Protected or unattacked squares @@ -548,17 +579,21 @@ namespace { // Bonus for threats on the next moves against enemy queen if (pos.count(Them) == 1) { + bool queenImbalance = pos.count() == 1; + Square s = pos.square(Them); - safe = mobilityArea[Us] & ~stronglyProtected; + safe = mobilityArea[Us] + & ~pos.pieces(Us, PAWN) + & ~stronglyProtected; - b = attackedBy[Us][KNIGHT] & pos.attacks_from(s); + b = attackedBy[Us][KNIGHT] & attacks_bb(s); - score += KnightOnQueen * popcount(b & safe); + score += KnightOnQueen * popcount(b & safe) * (1 + queenImbalance); - b = (attackedBy[Us][BISHOP] & pos.attacks_from(s)) - | (attackedBy[Us][ROOK ] & pos.attacks_from(s)); + b = (attackedBy[Us][BISHOP] & attacks_bb(s, pos.pieces())) + | (attackedBy[Us][ROOK ] & attacks_bb(s, pos.pieces())); - score += SliderOnQueen * popcount(b & safe & attackedBy2[Us]); + score += SliderOnQueen * popcount(b & safe & attackedBy2[Us]) * (1 + queenImbalance); } if (T) @@ -573,18 +608,32 @@ namespace { template template Score Evaluation::passed() const { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; constexpr Direction Up = pawn_push(Us); + constexpr Direction Down = -Up; auto king_proximity = [&](Color c, Square s) { return std::min(distance(pos.square(c), s), 5); }; - Bitboard b, bb, squaresToQueen, unsafeSquares; + Bitboard b, bb, squaresToQueen, unsafeSquares, blockedPassers, helpers; Score score = SCORE_ZERO; b = pe->passed_pawns(Us); + blockedPassers = b & shift(pos.pieces(Them, PAWN)); + if (blockedPassers) + { + helpers = shift(pos.pieces(Us, PAWN)) + & ~pos.pieces(Them) + & (~attackedBy2[Them] | attackedBy[Us][ALL_PIECES]); + + // Remove blocked candidate passers that don't have help to pass + b &= ~blockedPassers + | shift(helpers) + | shift(helpers); + } + while (b) { Square s = pop_lsb(&b); @@ -635,13 +684,7 @@ namespace { } } // r > RANK_3 - // Scale down bonus for candidate passers which need more than one - // pawn push to become passed, or have a pawn in front of them. - if ( !pos.pawn_passed(Us, s + Up) - || (pos.pieces(PAWN) & (s + Up))) - bonus = bonus / 2; - - score += bonus - PassedFile * map_to_queenside(file_of(s)); + score += bonus - PassedFile * edge_distance(file_of(s)); } if (T) @@ -651,20 +694,19 @@ namespace { } - // Evaluation::space() computes the space evaluation for a given side. The - // space evaluation is a simple bonus based on the number of safe squares - // available for minor pieces on the central four files on ranks 2--4. Safe - // squares one, two or three squares behind a friendly pawn are counted - // twice. Finally, the space bonus is multiplied by a weight. The aim is to - // improve play on game opening. + // Evaluation::space() computes a space evaluation for a given side, aiming to improve game + // play in the opening. It is based on the number of safe squares on the 4 central files + // on ranks 2 to 4. Completely safe squares behind a friendly pawn are counted twice. + // Finally, the space bonus is multiplied by a weight which decreases according to occupancy. template template Score Evaluation::space() const { + // Early exit if, for example, both queens or 6 minor pieces have been exchanged if (pos.non_pawn_material() < SpaceThreshold) return SCORE_ZERO; - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; constexpr Direction Down = -pawn_push(Us); constexpr Bitboard SpaceMask = Us == WHITE ? CenterFiles & (Rank2BB | Rank3BB | Rank4BB) @@ -681,7 +723,7 @@ namespace { behind |= shift(behind); int bonus = popcount(safe) + popcount(behind & safe & ~attackedBy[Them][ALL_PIECES]); - int weight = pos.count(Us) - 1; + int weight = pos.count(Us) - 3 + std::min(pe->blocked_count(), 9); Score score = make_score(bonus * weight * weight / 16, 0); if (T) @@ -691,73 +733,87 @@ namespace { } - // Evaluation::initiative() computes the initiative correction value - // for the position. It is a second order bonus/malus based on the - // known attacking/defending status of the players. + // Evaluation::winnable() adjusts the midgame and endgame score components, based on + // the known attacking/defending status of the players. The final value is derived + // by interpolation from the midgame and endgame values. template - Score Evaluation::initiative(Score score) const { - - Value mg = mg_value(score); - Value eg = eg_value(score); + Value Evaluation::winnable(Score score) const { int outflanking = distance(pos.square(WHITE), pos.square(BLACK)) - distance(pos.square(WHITE), pos.square(BLACK)); - bool infiltration = rank_of(pos.square(WHITE)) > RANK_4 - || rank_of(pos.square(BLACK)) < RANK_5; - bool pawnsOnBothFlanks = (pos.pieces(PAWN) & QueenSide) && (pos.pieces(PAWN) & KingSide); - bool almostUnwinnable = !pe->passed_count() - && outflanking < 0 + bool almostUnwinnable = outflanking < 0 && !pawnsOnBothFlanks; + bool infiltration = rank_of(pos.square(WHITE)) > RANK_4 + || rank_of(pos.square(BLACK)) < RANK_5; + // Compute the initiative bonus for the attacking side int complexity = 9 * pe->passed_count() - + 11 * pos.count() + + 12 * pos.count() + 9 * outflanking - + 12 * infiltration + 21 * pawnsOnBothFlanks + + 24 * infiltration + 51 * !pos.non_pawn_material() - 43 * almostUnwinnable - - 100 ; + -110 ; + + Value mg = mg_value(score); + Value eg = eg_value(score); // Now apply the bonus: note that we find the attacking side by extracting the // sign of the midgame or endgame values, and that we carefully cap the bonus // so that the midgame and endgame scores do not change sign after the bonus. - int u = ((mg > 0) - (mg < 0)) * std::max(std::min(complexity + 50, 0), -abs(mg)); + int u = ((mg > 0) - (mg < 0)) * Utility::clamp(complexity + 50, -abs(mg), 0); int v = ((eg > 0) - (eg < 0)) * std::max(complexity, -abs(eg)); - if (T) - Trace::add(INITIATIVE, make_score(u, v)); - - return make_score(u, v); - } - - - // Evaluation::scale_factor() computes the scale factor for the winning side - - template - ScaleFactor Evaluation::scale_factor(Value eg) const { + mg += u; + eg += v; + // Compute the scale factor for the winning side Color strongSide = eg > VALUE_DRAW ? WHITE : BLACK; int sf = me->scale_factor(pos, strongSide); - // If scale is not already specific, scale down the endgame via general heuristics + // If scale factor is not already specific, scale down via general heuristics if (sf == SCALE_FACTOR_NORMAL) { - if ( pos.opposite_bishops() - && pos.non_pawn_material() == 2 * BishopValueMg) - sf = 22 ; + if (pos.opposite_bishops()) + { + if ( pos.non_pawn_material(WHITE) == BishopValueMg + && pos.non_pawn_material(BLACK) == BishopValueMg) + sf = 18 + 4 * popcount(pe->passed_pawns(strongSide)); + else + sf = 22 + 3 * pos.count(strongSide); + } + else if ( pos.non_pawn_material(WHITE) == RookValueMg + && pos.non_pawn_material(BLACK) == RookValueMg + && pos.count(strongSide) - pos.count(~strongSide) <= 1 + && bool(KingSide & pos.pieces(strongSide, PAWN)) != bool(QueenSide & pos.pieces(strongSide, PAWN)) + && (attacks_bb(pos.square(~strongSide)) & pos.pieces(~strongSide, PAWN))) + sf = 36; + else if (pos.count() == 1) + sf = 37 + 3 * (pos.count(WHITE) == 1 ? pos.count(BLACK) + pos.count(BLACK) + : pos.count(WHITE) + pos.count(WHITE)); else - sf = std::min(sf, 36 + (pos.opposite_bishops() ? 2 : 7) * pos.count(strongSide)); + sf = std::min(sf, 36 + 7 * pos.count(strongSide)); + } - sf = std::max(0, sf - (pos.rule50_count() - 12) / 4); + // Interpolate between the middlegame and (scaled by 'sf') endgame score + v = mg * int(me->game_phase()) + + eg * int(PHASE_MIDGAME - me->game_phase()) * ScaleFactor(sf) / SCALE_FACTOR_NORMAL; + v /= PHASE_MIDGAME; + + if (T) + { + Trace::add(WINNABLE, make_score(u, eg * ScaleFactor(sf) / SCALE_FACTOR_NORMAL - eg_value(score))); + Trace::add(TOTAL, make_score(mg, eg * ScaleFactor(sf) / SCALE_FACTOR_NORMAL)); } - return ScaleFactor(sf); + return Value(v); } @@ -788,16 +844,19 @@ namespace { score += pe->pawn_score(WHITE) - pe->pawn_score(BLACK); // Early exit if score is high - Value v = (mg_value(score) + eg_value(score)) / 2; - if (abs(v) > LazyThreshold + pos.non_pawn_material() / 64) - return pos.side_to_move() == WHITE ? v : -v; + auto lazy_skip = [&](Value lazyThreshold) { + return abs(mg_value(score) + eg_value(score)) / 2 > lazyThreshold + pos.non_pawn_material() / 64; + }; - // Main evaluation begins here + if (lazy_skip(LazyThreshold1)) + goto make_v; + // Main evaluation begins here initialize(); initialize(); - // Pieces should be evaluated first (populate attack tables) + // Pieces evaluated first (also populates attackedBy, attackedBy2). + // Note that the order of evaluation of the terms is left unspecified. score += pieces() - pieces() + pieces() - pieces() + pieces() - pieces() @@ -805,19 +864,19 @@ namespace { score += mobility[WHITE] - mobility[BLACK]; + // More complex interactions that require fully populated attack bitboards score += king< WHITE>() - king< BLACK>() - + threats() - threats() - + passed< WHITE>() - passed< BLACK>() - + space< WHITE>() - space< BLACK>(); + + passed< WHITE>() - passed< BLACK>(); - score += initiative(score); + if (lazy_skip(LazyThreshold2)) + goto make_v; - // Interpolate between a middlegame and a (scaled by 'sf') endgame score - ScaleFactor sf = scale_factor(eg_value(score)); - v = mg_value(score) * int(me->game_phase()) - + eg_value(score) * int(PHASE_MIDGAME - me->game_phase()) * sf / SCALE_FACTOR_NORMAL; + score += threats() - threats() + + space< WHITE>() - space< BLACK>(); - v /= PHASE_MIDGAME; +make_v: + // Derive single value from mg and eg parts of score + Value v = winnable(score); // In case of tracing add all remaining individual evaluation terms if (T) @@ -826,11 +885,18 @@ namespace { Trace::add(IMBALANCE, me->imbalance()); Trace::add(PAWN, pe->pawn_score(WHITE), pe->pawn_score(BLACK)); Trace::add(MOBILITY, mobility[WHITE], mobility[BLACK]); - Trace::add(TOTAL, score); } - return (pos.side_to_move() == WHITE ? v : -v) // Side to move point of view - + Eval::Tempo; + // Evaluation grain + v = (v / 16) * 16; + + // Side to move point of view + v = (pos.side_to_move() == WHITE ? v : -v) + Tempo; + + // Damp down the evaluation linearly when shuffling + v = v * (100 - pos.rule50_count()) / 100; + + return v; } } // namespace @@ -878,11 +944,11 @@ std::string Eval::trace(const Position& pos) { << " Threats | " << Term(THREAT) << " Passed | " << Term(PASSED) << " Space | " << Term(SPACE) - << " Initiative | " << Term(INITIATIVE) + << " Winnable | " << Term(WINNABLE) << " ------------+-------------+-------------+------------\n" << " Total | " << Term(TOTAL); - ss << "\nTotal evaluation: " << to_cp(v) << " (white side)\n"; + ss << "\nFinal evaluation: " << to_cp(v) << " (white side)\n"; return ss.str(); } diff --git a/src/evaluate.h b/src/evaluate.h index 077de70c..7c8a2a6f 100644 --- a/src/evaluate.h +++ b/src/evaluate.h @@ -29,8 +29,6 @@ class Position; namespace Eval { -constexpr Value Tempo = Value(28); // Must be visible to search - std::string trace(const Position& pos); Value evaluate(const Position& pos); diff --git a/src/main.cpp b/src/main.cpp index dc8487e9..98cbfc97 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -24,12 +24,12 @@ #include #include "bitboard.h" +#include "endgame.h" #include "position.h" #include "search.h" #include "thread.h" #include "tt.h" #include "uci.h" -#include "endgame.h" #include "syzygy/tbprobe.h" #include @@ -232,12 +232,13 @@ int main(int argc, char* argv[]) { std::cout << engine_info() << std::endl; UCI::init(Options); + Tune::init(); PSQT::init(); Bitboards::init(); Position::init(); Bitbases::init(); Endgames::init(); - Threads.set(Options["Threads"]); + Threads.set(size_t(Options["Threads"])); Search::clear(); // After threads are up UCI::loop(argc, argv); diff --git a/src/material.cpp b/src/material.cpp index 0e130878..bb25d3ca 100644 --- a/src/material.cpp +++ b/src/material.cpp @@ -44,12 +44,12 @@ namespace { constexpr int QuadraticTheirs[][PIECE_TYPE_NB] = { // THEIR PIECES // pair pawn knight bishop rook queen - { 0 }, // Bishop pair - { 36, 0 }, // Pawn - { 9, 63, 0 }, // Knight OUR PIECES - { 59, 65, 42, 0 }, // Bishop - { 46, 39, 24, -24, 0 }, // Rook - { 97, 100, -42, 137, 268, 0 } // Queen + { }, // Bishop pair + { 36, }, // Pawn + { 9, 63, }, // Knight OUR PIECES + { 59, 65, 42, }, // Bishop + { 46, 39, 24, -24, }, // Rook + { 97, 100, -42, 137, 268, } // Queen }; // Endgame evaluation and scaling functions are accessed directly and not through @@ -79,12 +79,14 @@ namespace { && pos.count(~us) >= 1; } + /// imbalance() calculates the imbalance by comparing the piece count of each /// piece type for both colors. + template int imbalance(const int pieceCount[][PIECE_TYPE_NB]) { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; int bonus = 0; @@ -94,9 +96,9 @@ namespace { if (!pieceCount[Us][pt1]) continue; - int v = 0; + int v = QuadraticOurs[pt1][pt1] * pieceCount[Us][pt1]; - for (int pt2 = NO_PIECE_TYPE; pt2 <= pt1; ++pt2) + for (int pt2 = NO_PIECE_TYPE; pt2 < pt1; ++pt2) v += QuadraticOurs[pt1][pt2] * pieceCount[Us][pt2] + QuadraticTheirs[pt1][pt2] * pieceCount[Them][pt2]; @@ -110,6 +112,7 @@ namespace { namespace Material { + /// Material::probe() looks up the current position's material configuration in /// the material hash table. It returns a pointer to the Entry if the position /// is found. Otherwise a new Entry is computed and stored there, so we don't @@ -129,7 +132,7 @@ Entry* probe(const Position& pos) { Value npm_w = pos.non_pawn_material(WHITE); Value npm_b = pos.non_pawn_material(BLACK); - Value npm = clamp(npm_w + npm_b, EndgameLimit, MidgameLimit); + Value npm = Utility::clamp(npm_w + npm_b, EndgameLimit, MidgameLimit); // Map total non-pawn material into [PHASE_ENDGAME, PHASE_MIDGAME] e->gamePhase = Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit)); diff --git a/src/material.h b/src/material.h index 9ab1d81c..21647f23 100644 --- a/src/material.h +++ b/src/material.h @@ -44,7 +44,7 @@ struct Entry { bool specialized_eval_exists() const { return evaluationFunction != nullptr; } Value evaluate(const Position& pos) const { return (*evaluationFunction)(pos); } - // scale_factor takes a position and a color as input and returns a scale factor + // scale_factor() takes a position and a color as input and returns a scale factor // for the given color. We have to provide the position in addition to the color // because the scale factor may also be a function which should be applied to // the position. For instance, in KBP vs K endgames, the scaling function looks diff --git a/src/misc.cpp b/src/misc.cpp index 6ed0bdd0..d9c0679b 100644 --- a/src/misc.cpp +++ b/src/misc.cpp @@ -47,6 +47,11 @@ typedef bool(*fun3_t)(HANDLE, CONST GROUP_AFFINITY*, PGROUP_AFFINITY); #include #include +#if defined(__linux__) && !defined(__ANDROID__) +#include +#include +#endif + #include "misc.h" #include "thread.h" @@ -56,7 +61,7 @@ namespace { /// Version number. If Version is left empty, then compile date in the format /// DD-MM-YY and show in engine_info. -const string Version = "11"; +const string Version = ""; /// Our fancy logging facility. The trick here is to replace cin.rdbuf() and /// cout.rdbuf() with two Tie objects that tie cin and cout to a file stream. We @@ -156,9 +161,9 @@ const string engine_info(bool to_uci) { const std::string compiler_info() { - #define STRINGIFY2(x) #x - #define STRINGIFY(x) STRINGIFY2(x) - #define VER_STRING(major, minor, patch) STRINGIFY(major) "." STRINGIFY(minor) "." STRINGIFY(patch) + #define stringify2(x) #x + #define stringify(x) stringify2(x) + #define make_version_string(major, minor, patch) stringify(major) "." stringify(minor) "." stringify(patch) /// Predefined macros hell: /// @@ -172,26 +177,26 @@ const std::string compiler_info() { #ifdef __clang__ compiler += "clang++ "; - compiler += VER_STRING(__clang_major__, __clang_minor__, __clang_patchlevel__); + compiler += make_version_string(__clang_major__, __clang_minor__, __clang_patchlevel__); #elif __INTEL_COMPILER compiler += "Intel compiler "; compiler += "(version "; - compiler += STRINGIFY(__INTEL_COMPILER) " update " STRINGIFY(__INTEL_COMPILER_UPDATE); + compiler += stringify(__INTEL_COMPILER) " update " stringify(__INTEL_COMPILER_UPDATE); compiler += ")"; #elif _MSC_VER compiler += "MSVC "; compiler += "(version "; - compiler += STRINGIFY(_MSC_FULL_VER) "." STRINGIFY(_MSC_BUILD); + compiler += stringify(_MSC_FULL_VER) "." stringify(_MSC_BUILD); compiler += ")"; #elif __GNUC__ compiler += "g++ (GNUC) "; - compiler += VER_STRING(__GNUC__, __GNUC_MINOR__, __GNUC_PATCHLEVEL__); + compiler += make_version_string(__GNUC__, __GNUC_MINOR__, __GNUC_PATCHLEVEL__); #else compiler += "Unknown compiler "; compiler += "(unknown version)"; #endif - #if defined(__APPLE__) + #if defined(__APPLE__) compiler += " on Apple"; #elif defined(__CYGWIN__) compiler += " on Cygwin"; @@ -289,6 +294,133 @@ void prefetch(void* addr) { #endif + +/// aligned_ttmem_alloc() will return suitably aligned memory, and if possible use large pages. +/// The returned pointer is the aligned one, while the mem argument is the one that needs +/// to be passed to free. With c++17 some of this functionality could be simplified. + +#if defined(__linux__) && !defined(__ANDROID__) + +void* aligned_ttmem_alloc(size_t allocSize, void*& mem) { + + constexpr size_t alignment = 2 * 1024 * 1024; // assumed 2MB page sizes + size_t size = ((allocSize + alignment - 1) / alignment) * alignment; // multiple of alignment + if (posix_memalign(&mem, alignment, size)) + mem = nullptr; + madvise(mem, allocSize, MADV_HUGEPAGE); + return mem; +} + +#elif defined(_WIN64) + +static void* aligned_ttmem_alloc_large_pages(size_t allocSize) { + + HANDLE hProcessToken { }; + LUID luid { }; + void* mem = nullptr; + + const size_t largePageSize = GetLargePageMinimum(); + if (!largePageSize) + return nullptr; + + // We need SeLockMemoryPrivilege, so try to enable it for the process + if (!OpenProcessToken(GetCurrentProcess(), TOKEN_ADJUST_PRIVILEGES | TOKEN_QUERY, &hProcessToken)) + return nullptr; + + if (LookupPrivilegeValue(NULL, SE_LOCK_MEMORY_NAME, &luid)) + { + TOKEN_PRIVILEGES tp { }; + TOKEN_PRIVILEGES prevTp { }; + DWORD prevTpLen = 0; + + tp.PrivilegeCount = 1; + tp.Privileges[0].Luid = luid; + tp.Privileges[0].Attributes = SE_PRIVILEGE_ENABLED; + + // Try to enable SeLockMemoryPrivilege. Note that even if AdjustTokenPrivileges() succeeds, + // we still need to query GetLastError() to ensure that the privileges were actually obtained. + if (AdjustTokenPrivileges( + hProcessToken, FALSE, &tp, sizeof(TOKEN_PRIVILEGES), &prevTp, &prevTpLen) && + GetLastError() == ERROR_SUCCESS) + { + // Round up size to full pages and allocate + allocSize = (allocSize + largePageSize - 1) & ~size_t(largePageSize - 1); + mem = VirtualAlloc( + NULL, allocSize, MEM_RESERVE | MEM_COMMIT | MEM_LARGE_PAGES, PAGE_READWRITE); + + // Privilege no longer needed, restore previous state + AdjustTokenPrivileges(hProcessToken, FALSE, &prevTp, 0, NULL, NULL); + } + } + + CloseHandle(hProcessToken); + + return mem; +} + +void* aligned_ttmem_alloc(size_t allocSize, void*& mem) { + + static bool firstCall = true; + + // Try to allocate large pages + mem = aligned_ttmem_alloc_large_pages(allocSize); + + // Suppress info strings on the first call. The first call occurs before 'uci' + // is received and in that case this output confuses some GUIs. + if (!firstCall) + { + if (mem) + sync_cout << "info string Hash table allocation: Windows large pages used." << sync_endl; + else + sync_cout << "info string Hash table allocation: Windows large pages not used." << sync_endl; + } + firstCall = false; + + // Fall back to regular, page aligned, allocation if necessary + if (!mem) + mem = VirtualAlloc(NULL, allocSize, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE); + + return mem; +} + +#else + +void* aligned_ttmem_alloc(size_t allocSize, void*& mem) { + + constexpr size_t alignment = 64; // assumed cache line size + size_t size = allocSize + alignment - 1; // allocate some extra space + mem = malloc(size); + void* ret = reinterpret_cast((uintptr_t(mem) + alignment - 1) & ~uintptr_t(alignment - 1)); + return ret; +} + +#endif + + +/// aligned_ttmem_free() will free the previously allocated ttmem + +#if defined(_WIN64) + +void aligned_ttmem_free(void* mem) { + + if (mem && !VirtualFree(mem, 0, MEM_RELEASE)) + { + DWORD err = GetLastError(); + std::cerr << "Failed to free transposition table. Error code: 0x" << + std::hex << err << std::dec << std::endl; + exit(EXIT_FAILURE); + } +} + +#else + +void aligned_ttmem_free(void *mem) { + free(mem); +} + +#endif + + namespace WinProcGroup { #ifndef _WIN32 diff --git a/src/misc.h b/src/misc.h index b11c5aa8..373f1b77 100644 --- a/src/misc.h +++ b/src/misc.h @@ -33,6 +33,8 @@ const std::string engine_info(bool to_uci = false); const std::string compiler_info(); void prefetch(void* addr); void start_logger(const std::string& fname); +void* aligned_ttmem_alloc(size_t size, void*& mem); +void aligned_ttmem_free(void* mem); // nop if mem == nullptr void dbg_hit_on(bool b); void dbg_hit_on(bool c, bool b); @@ -63,6 +65,14 @@ std::ostream& operator<<(std::ostream&, SyncCout); #define sync_cout std::cout << IO_LOCK #define sync_endl std::endl << IO_UNLOCK +namespace Utility { + +/// Clamp a value between lo and hi. Available in c++17. +template constexpr const T& clamp(const T& v, const T& lo, const T& hi) { + return v < lo ? lo : v > hi ? hi : v; +} + +} /// xorshift64star Pseudo-Random Number Generator /// This class is based on original code written and dedicated @@ -100,6 +110,19 @@ public: { return T(rand64() & rand64() & rand64()); } }; +inline uint64_t mul_hi64(uint64_t a, uint64_t b) { +#if defined(__GNUC__) && defined(IS_64BIT) + __extension__ typedef unsigned __int128 uint128; + return ((uint128)a * (uint128)b) >> 64; +#else + uint64_t aL = (uint32_t)a, aH = a >> 32; + uint64_t bL = (uint32_t)b, bH = b >> 32; + uint64_t c1 = (aL * bL) >> 32; + uint64_t c2 = aH * bL + c1; + uint64_t c3 = aL * bH + (uint32_t)c2; + return aH * bH + (c2 >> 32) + (c3 >> 32); +#endif +} /// Under Windows it is not possible for a process to run on more than one /// logical processor group. This usually means to be limited to use max 64 diff --git a/src/movegen.cpp b/src/movegen.cpp index 8f6edffb..4ff12fc6 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -29,22 +29,20 @@ namespace { ExtMove* make_promotions(ExtMove* moveList, Square to, Square ksq) { if (Type == CAPTURES || Type == EVASIONS || Type == NON_EVASIONS) + { *moveList++ = make(to - D, to, QUEEN); + if (attacks_bb(to) & ksq) + *moveList++ = make(to - D, to, KNIGHT); + } if (Type == QUIETS || Type == EVASIONS || Type == NON_EVASIONS) { *moveList++ = make(to - D, to, ROOK); *moveList++ = make(to - D, to, BISHOP); - *moveList++ = make(to - D, to, KNIGHT); + if (!(attacks_bb(to) & ksq)) + *moveList++ = make(to - D, to, KNIGHT); } - // Knight promotion is the only promotion that can give a direct check - // that's not already included in the queen promotion. - if (Type == QUIET_CHECKS && (PseudoAttacks[KNIGHT][to] & ksq)) - *moveList++ = make(to - D, to, KNIGHT); - else - (void)ksq; // Silence a warning under MSVC - return moveList; } @@ -52,8 +50,7 @@ namespace { template ExtMove* generate_pawn_moves(const Position& pos, ExtMove* moveList, Bitboard target) { - // Compute some compile time parameters relative to the white side - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; constexpr Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB); constexpr Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB); constexpr Direction Up = pawn_push(Us); @@ -85,8 +82,8 @@ namespace { if (Type == QUIET_CHECKS) { - b1 &= pos.attacks_from(ksq, Them); - b2 &= pos.attacks_from(ksq, Them); + b1 &= pawn_attacks_bb(Them, ksq); + b2 &= pawn_attacks_bb(Them, ksq); // Add pawn pushes which give discovered check. This is possible only // if the pawn is not on the same file as the enemy king, because we @@ -167,7 +164,7 @@ namespace { if (Type == EVASIONS && !(target & (pos.ep_square() - Up))) return moveList; - b1 = pawnsNotOn7 & pos.attacks_from(pos.ep_square(), Them); + b1 = pawnsNotOn7 & pawn_attacks_bb(Them, pos.ep_square()); assert(b1); @@ -180,27 +177,26 @@ namespace { } - template - ExtMove* generate_moves(const Position& pos, ExtMove* moveList, Color us, - Bitboard target) { + template + ExtMove* generate_moves(const Position& pos, ExtMove* moveList, Bitboard target) { static_assert(Pt != KING && Pt != PAWN, "Unsupported piece type in generate_moves()"); - const Square* pl = pos.squares(us); + const Square* pl = pos.squares(Us); for (Square from = *pl; from != SQ_NONE; from = *++pl) { if (Checks) { if ( (Pt == BISHOP || Pt == ROOK || Pt == QUEEN) - && !(PseudoAttacks[Pt][from] & target & pos.check_squares(Pt))) + && !(attacks_bb(from) & target & pos.check_squares(Pt))) continue; - if (pos.blockers_for_king(~us) & from) + if (pos.blockers_for_king(~Us) & from) continue; } - Bitboard b = pos.attacks_from(from) & target; + Bitboard b = attacks_bb(from, pos.pieces()) & target; if (Checks) b &= pos.check_squares(Pt); @@ -214,33 +210,49 @@ namespace { template - ExtMove* generate_all(const Position& pos, ExtMove* moveList, Bitboard target) { - - constexpr CastlingRights OO = Us & KING_SIDE; - constexpr CastlingRights OOO = Us & QUEEN_SIDE; + ExtMove* generate_all(const Position& pos, ExtMove* moveList) { constexpr bool Checks = Type == QUIET_CHECKS; // Reduce template instantations + Bitboard target; + + switch (Type) + { + case CAPTURES: + target = pos.pieces(~Us); + break; + case QUIETS: + case QUIET_CHECKS: + target = ~pos.pieces(); + break; + case EVASIONS: + { + Square checksq = lsb(pos.checkers()); + target = between_bb(pos.square(Us), checksq) | checksq; + break; + } + case NON_EVASIONS: + target = ~pos.pieces(Us); + break; + default: + static_assert(true, "Unsupported type in generate_all()"); + } moveList = generate_pawn_moves(pos, moveList, target); - moveList = generate_moves(pos, moveList, Us, target); - moveList = generate_moves(pos, moveList, Us, target); - moveList = generate_moves< ROOK, Checks>(pos, moveList, Us, target); - moveList = generate_moves< QUEEN, Checks>(pos, moveList, Us, target); + moveList = generate_moves(pos, moveList, target); + moveList = generate_moves(pos, moveList, target); + moveList = generate_moves(pos, moveList, target); + moveList = generate_moves(pos, moveList, target); if (Type != QUIET_CHECKS && Type != EVASIONS) { Square ksq = pos.square(Us); - Bitboard b = pos.attacks_from(ksq) & target; + Bitboard b = attacks_bb(ksq) & target; while (b) *moveList++ = make_move(ksq, pop_lsb(&b)); - if (Type != CAPTURES && pos.can_castle(CastlingRights(OO | OOO))) - { - if (!pos.castling_impeded(OO) && pos.can_castle(OO)) - *moveList++ = make(ksq, pos.castling_rook_square(OO)); - - if (!pos.castling_impeded(OOO) && pos.can_castle(OOO)) - *moveList++ = make(ksq, pos.castling_rook_square(OOO)); - } + if ((Type != CAPTURES) && pos.can_castle(Us & ANY_CASTLING)) + for(CastlingRights cr : { Us & KING_SIDE, Us & QUEEN_SIDE } ) + if (!pos.castling_impeded(cr) && pos.can_castle(cr)) + *moveList++ = make(ksq, pos.castling_rook_square(cr)); } return moveList; @@ -249,8 +261,8 @@ namespace { } // namespace -/// Generates all pseudo-legal captures and queen promotions -/// Generates all pseudo-legal non-captures and underpromotions +/// Generates all pseudo-legal captures plus queen and checking knight promotions +/// Generates all pseudo-legal non-captures and underpromotions(except checking knight) /// Generates all pseudo-legal captures and non-captures /// /// Returns a pointer to the end of the move list. @@ -263,12 +275,8 @@ ExtMove* generate(const Position& pos, ExtMove* moveList) { Color us = pos.side_to_move(); - Bitboard target = Type == CAPTURES ? pos.pieces(~us) - : Type == QUIETS ? ~pos.pieces() - : Type == NON_EVASIONS ? ~pos.pieces(us) : 0; - - return us == WHITE ? generate_all(pos, moveList, target) - : generate_all(pos, moveList, target); + return us == WHITE ? generate_all(pos, moveList) + : generate_all(pos, moveList); } // Explicit template instantiations @@ -277,35 +285,32 @@ template ExtMove* generate(const Position&, ExtMove*); template ExtMove* generate(const Position&, ExtMove*); -/// generate generates all pseudo-legal non-captures and knight -/// underpromotions that give check. Returns a pointer to the end of the move list. +/// generate generates all pseudo-legal non-captures. +/// Returns a pointer to the end of the move list. template<> ExtMove* generate(const Position& pos, ExtMove* moveList) { assert(!pos.checkers()); Color us = pos.side_to_move(); - Bitboard dc = pos.blockers_for_king(~us) & pos.pieces(us); + Bitboard dc = pos.blockers_for_king(~us) & pos.pieces(us) & ~pos.pieces(PAWN); while (dc) { Square from = pop_lsb(&dc); PieceType pt = type_of(pos.piece_on(from)); - if (pt == PAWN) - continue; // Will be generated together with direct checks - - Bitboard b = pos.attacks_from(pt, from) & ~pos.pieces(); + Bitboard b = attacks_bb(pt, from, pos.pieces()) & ~pos.pieces(); if (pt == KING) - b &= ~PseudoAttacks[QUEEN][pos.square(~us)]; + b &= ~attacks_bb(pos.square(~us)); while (b) *moveList++ = make_move(from, pop_lsb(&b)); } - return us == WHITE ? generate_all(pos, moveList, ~pos.pieces()) - : generate_all(pos, moveList, ~pos.pieces()); + return us == WHITE ? generate_all(pos, moveList) + : generate_all(pos, moveList); } @@ -325,13 +330,10 @@ ExtMove* generate(const Position& pos, ExtMove* moveList) { // the king evasions in order to skip known illegal moves, which avoids any // useless legality checks later on. while (sliders) - { - Square checksq = pop_lsb(&sliders); - sliderAttacks |= LineBB[checksq][ksq] ^ checksq; - } + sliderAttacks |= line_bb(ksq, pop_lsb(&sliders)) & ~pos.checkers(); // Generate evasions for king, capture and non capture moves - Bitboard b = pos.attacks_from(ksq) & ~pos.pieces(us) & ~sliderAttacks; + Bitboard b = attacks_bb(ksq) & ~pos.pieces(us) & ~sliderAttacks; while (b) *moveList++ = make_move(ksq, pop_lsb(&b)); @@ -339,11 +341,8 @@ ExtMove* generate(const Position& pos, ExtMove* moveList) { return moveList; // Double check, only a king move can save the day // Generate blocking evasions or captures of the checking piece - Square checksq = lsb(pos.checkers()); - Bitboard target = between_bb(checksq, ksq) | checksq; - - return us == WHITE ? generate_all(pos, moveList, target) - : generate_all(pos, moveList, target); + return us == WHITE ? generate_all(pos, moveList) + : generate_all(pos, moveList); } diff --git a/src/movepick.cpp b/src/movepick.cpp index 025f5b82..5775f810 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -56,45 +56,39 @@ namespace { /// ordering is at the current node. /// MovePicker constructor for the main search -MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, - const CapturePieceToHistory* cph, const PieceToHistory** ch, Move cm, Move* killers) - : pos(p), mainHistory(mh), captureHistory(cph), continuationHistory(ch), - refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}}, depth(d) { +MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, const LowPlyHistory* lp, + const CapturePieceToHistory* cph, const PieceToHistory** ch, Move cm, const Move* killers, int pl) + : pos(p), mainHistory(mh), lowPlyHistory(lp), captureHistory(cph), continuationHistory(ch), + ttMove(ttm), refutations{{killers[0], 0}, {killers[1], 0}, {cm, 0}}, depth(d), ply(pl) { assert(d > 0); - stage = pos.checkers() ? EVASION_TT : MAIN_TT; - ttMove = ttm && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE; - stage += (ttMove == MOVE_NONE); + stage = (pos.checkers() ? EVASION_TT : MAIN_TT) + + !(ttm && pos.pseudo_legal(ttm)); } /// MovePicker constructor for quiescence search MovePicker::MovePicker(const Position& p, Move ttm, Depth d, const ButterflyHistory* mh, const CapturePieceToHistory* cph, const PieceToHistory** ch, Square rs) - : pos(p), mainHistory(mh), captureHistory(cph), continuationHistory(ch), recaptureSquare(rs), depth(d) { + : pos(p), mainHistory(mh), captureHistory(cph), continuationHistory(ch), ttMove(ttm), recaptureSquare(rs), depth(d) { assert(d <= 0); - stage = pos.checkers() ? EVASION_TT : QSEARCH_TT; - ttMove = ttm - && (depth > DEPTH_QS_RECAPTURES || to_sq(ttm) == recaptureSquare) - && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE; - stage += (ttMove == MOVE_NONE); + stage = (pos.checkers() ? EVASION_TT : QSEARCH_TT) + + !(ttm && (depth > DEPTH_QS_RECAPTURES || to_sq(ttm) == recaptureSquare) + && pos.pseudo_legal(ttm)); } /// MovePicker constructor for ProbCut: we generate captures with SEE greater /// than or equal to the given threshold. MovePicker::MovePicker(const Position& p, Move ttm, Value th, const CapturePieceToHistory* cph) - : pos(p), captureHistory(cph), threshold(th) { + : pos(p), captureHistory(cph), ttMove(ttm), threshold(th) { assert(!pos.checkers()); - stage = PROBCUT_TT; - ttMove = ttm - && pos.capture(ttm) - && pos.pseudo_legal(ttm) - && pos.see_ge(ttm, threshold) ? ttm : MOVE_NONE; - stage += (ttMove == MOVE_NONE); + stage = PROBCUT_TT + !(ttm && pos.capture(ttm) + && pos.pseudo_legal(ttm) + && pos.see_ge(ttm, threshold)); } /// MovePicker::score() assigns a numerical value to each move in a list, used @@ -115,7 +109,8 @@ void MovePicker::score() { + 2 * (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)] + 2 * (*continuationHistory[1])[pos.moved_piece(m)][to_sq(m)] + 2 * (*continuationHistory[3])[pos.moved_piece(m)][to_sq(m)] - + (*continuationHistory[5])[pos.moved_piece(m)][to_sq(m)]; + + (*continuationHistory[5])[pos.moved_piece(m)][to_sq(m)] + + (ply < MAX_LPH ? std::min(4, depth / 3) * (*lowPlyHistory)[ply][from_to(m)] : 0); else // Type == EVASIONS { @@ -174,7 +169,7 @@ top: case GOOD_CAPTURE: if (select([&](){ - return pos.see_ge(*cur, Value(-55 * cur->value / 1024)) ? + return pos.see_ge(*cur, Value(-69 * cur->value / 1024)) ? // Move losing capture to endBadCaptures to be tried later true : (*endBadCaptures++ = *cur, false); })) return *(cur - 1); diff --git a/src/movepick.h b/src/movepick.h index cdedc9b6..aaff388f 100644 --- a/src/movepick.h +++ b/src/movepick.h @@ -88,6 +88,12 @@ enum StatsType { NoCaptures, Captures }; /// the move's from and to squares, see www.chessprogramming.org/Butterfly_Boards typedef Stats ButterflyHistory; +/// At higher depths LowPlyHistory records successful quiet moves near the root and quiet +/// moves which are/were in the PV (ttPv) +/// It is cleared with each new search and filled during iterative deepening +constexpr int MAX_LPH = 4; +typedef Stats LowPlyHistory; + /// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous /// move, see www.chessprogramming.org/Countermove_Heuristic typedef Stats CounterMoveHistory; @@ -123,10 +129,12 @@ public: const PieceToHistory**, Square); MovePicker(const Position&, Move, Depth, const ButterflyHistory*, + const LowPlyHistory*, const CapturePieceToHistory*, const PieceToHistory**, Move, - Move*); + const Move*, + int); Move next_move(bool skipQuiets = false); private: @@ -137,6 +145,7 @@ private: const Position& pos; const ButterflyHistory* mainHistory; + const LowPlyHistory* lowPlyHistory; const CapturePieceToHistory* captureHistory; const PieceToHistory** continuationHistory; Move ttMove; @@ -145,6 +154,7 @@ private: Square recaptureSquare; Value threshold; Depth depth; + int ply; ExtMove moves[MAX_MOVES]; }; diff --git a/src/pawns.cpp b/src/pawns.cpp index c3f7872f..7f8d451a 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -33,12 +33,18 @@ namespace { // Pawn penalties constexpr Score Backward = S( 9, 24); - constexpr Score BlockedStorm = S(82, 82); constexpr Score Doubled = S(11, 56); constexpr Score Isolated = S( 5, 15); constexpr Score WeakLever = S( 0, 56); constexpr Score WeakUnopposed = S(13, 27); + // Bonus for blocked pawns at 5th or 6th rank + constexpr Score BlockedPawn[2] = { S(-11, -4), S(-3, 4) }; + + constexpr Score BlockedStorm[RANK_NB] = { + S(0, 0), S(0, 0), S(76, 78), S(-10, 15), S(-7, 10), S(-4, 6), S(-1, 2) + }; + // Connected pawn bonus constexpr int Connected[RANK_NB] = { 0, 7, 8, 12, 29, 48, 86 }; @@ -65,10 +71,16 @@ namespace { #undef S #undef V + + /// evaluate() calculates a score for the static pawn structure of the given position. + /// We cannot use the location of pieces or king in this function, as the evaluation + /// of the pawn structure will be stored in a small cache for speed reasons, and will + /// be re-used even when the pieces have moved. + template Score evaluate(const Position& pos, Pawns::Entry* e) { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; constexpr Direction Up = pawn_push(Us); Bitboard neighbours, stoppers, support, phalanx, opposed; @@ -86,6 +98,7 @@ namespace { e->passedPawns[Us] = 0; e->kingSquares[Us] = SQ_NONE; e->pawnAttacks[Us] = e->pawnAttacksSpan[Us] = pawn_attacks_bb(ourPawns); + e->blockedCount += popcount(shift(ourPawns) & (theirPawns | doubleAttackThem)); // Loop through all pawns of the current color and score each pawn while ((s = *pl++) != SQ_NONE) @@ -98,8 +111,8 @@ namespace { opposed = theirPawns & forward_file_bb(Us, s); blocked = theirPawns & (s + Up); stoppers = theirPawns & passed_pawn_span(Us, s); - lever = theirPawns & PawnAttacks[Us][s]; - leverPush = theirPawns & PawnAttacks[Us][s + Up]; + lever = theirPawns & pawn_attacks_bb(Us, s); + leverPush = theirPawns & pawn_attacks_bb(Us, s + Up); doubled = ourPawns & (s - Up); neighbours = ourPawns & adjacent_files_bb(s); phalanx = neighbours & rank_bb(s); @@ -118,12 +131,15 @@ namespace { // (a) there is no stoppers except some levers // (b) the only stoppers are the leverPush, but we outnumber them // (c) there is only one front stopper which can be levered. + // (Refined in Evaluation::passed) passed = !(stoppers ^ lever) || ( !(stoppers ^ leverPush) && popcount(phalanx) >= popcount(leverPush)) || ( stoppers == blocked && r >= RANK_5 && (shift(support) & ~(theirPawns | doubleAttackThem))); + passed &= !(forward_file_bb(Us, s) & ourPawns); + // Passed pawns will be properly scored later in evaluation when we have // full attack info. if (passed) @@ -139,16 +155,26 @@ namespace { } else if (!neighbours) - score -= Isolated - + WeakUnopposed * !opposed; + { + if ( opposed + && (ourPawns & forward_file_bb(Them, s)) + && !(theirPawns & adjacent_files_bb(s))) + score -= Doubled; + else + score -= Isolated + + WeakUnopposed * !opposed; + } else if (backward) - score -= Backward - + WeakUnopposed * !opposed; + score -= Backward + + WeakUnopposed * !opposed; if (!support) - score -= Doubled * doubled - + WeakLever * more_than_one(lever); + score -= Doubled * doubled + + WeakLever * more_than_one(lever); + + if (blocked && r > RANK_4) + score += BlockedPawn[r-4]; } return score; @@ -158,6 +184,7 @@ namespace { namespace Pawns { + /// Pawns::probe() looks up the current position's pawns configuration in /// the pawns hash table. It returns a pointer to the Entry if the position /// is found. Otherwise a new Entry is computed and stored there, so we don't @@ -172,6 +199,7 @@ Entry* probe(const Position& pos) { return e; e->key = key; + e->blockedCount = 0; e->scores[WHITE] = evaluate(pos, e); e->scores[BLACK] = evaluate(pos, e); @@ -183,17 +211,17 @@ Entry* probe(const Position& pos) { /// penalty for a king, looking at the king file and the two closest files. template -Score Entry::evaluate_shelter(const Position& pos, Square ksq) { +Score Entry::evaluate_shelter(const Position& pos, Square ksq) const { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); + constexpr Color Them = ~Us; Bitboard b = pos.pieces(PAWN) & ~forward_ranks_bb(Them, ksq); - Bitboard ourPawns = b & pos.pieces(Us); + Bitboard ourPawns = b & pos.pieces(Us) & ~pawnAttacks[Them]; Bitboard theirPawns = b & pos.pieces(Them); Score bonus = make_score(5, 5); - File center = clamp(file_of(ksq), FILE_B, FILE_G); + File center = Utility::clamp(file_of(ksq), FILE_B, FILE_G); for (File f = File(center - 1); f <= File(center + 1); ++f) { b = ourPawns & file_bb(f); @@ -202,11 +230,11 @@ Score Entry::evaluate_shelter(const Position& pos, Square ksq) { b = theirPawns & file_bb(f); int theirRank = b ? relative_rank(Us, frontmost_sq(Them, b)) : 0; - File d = map_to_queenside(f); + int d = edge_distance(f); bonus += make_score(ShelterStrength[d][ourRank], 0); if (ourRank && (ourRank == theirRank - 1)) - bonus -= BlockedStorm * int(theirRank == RANK_3); + bonus -= BlockedStorm[theirRank]; else bonus -= make_score(UnblockedStorm[d][theirRank], 0); } @@ -238,9 +266,9 @@ Score Entry::do_king_safety(const Position& pos) { // In endgame we like to bring our king near our closest pawn Bitboard pawns = pos.pieces(Us, PAWN); - int minPawnDist = pawns ? 8 : 0; + int minPawnDist = 6; - if (pawns & PseudoAttacks[KING][ksq]) + if (pawns & attacks_bb(ksq)) minPawnDist = 1; else while (pawns) minPawnDist = std::min(minPawnDist, distance(ksq, pop_lsb(&pawns))); diff --git a/src/pawns.h b/src/pawns.h index bd17618f..e6098069 100644 --- a/src/pawns.h +++ b/src/pawns.h @@ -38,6 +38,7 @@ struct Entry { Bitboard passed_pawns(Color c) const { return passedPawns[c]; } Bitboard pawn_attacks_span(Color c) const { return pawnAttacksSpan[c]; } int passed_count() const { return popcount(passedPawns[WHITE] | passedPawns[BLACK]); } + int blocked_count() const { return blockedCount; } template Score king_safety(const Position& pos) { @@ -49,7 +50,7 @@ struct Entry { Score do_king_safety(const Position& pos); template - Score evaluate_shelter(const Position& pos, Square ksq); + Score evaluate_shelter(const Position& pos, Square ksq) const; Key key; Score scores[COLOR_NB]; @@ -59,6 +60,7 @@ struct Entry { Square kingSquares[COLOR_NB]; Score kingSafety[COLOR_NB]; int castlingRights[COLOR_NB]; + int blockedCount; }; typedef HashTable Table; diff --git a/src/position.cpp b/src/position.cpp index 09a574a5..57f731d4 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -64,10 +64,11 @@ std::ostream& operator<<(std::ostream& os, const Position& pos) { for (File f = FILE_A; f <= FILE_H; ++f) os << " | " << PieceToChar[pos.piece_on(make_square(f, r))]; - os << " |\n +---+---+---+---+---+---+---+---+\n"; + os << " | " << (1 + r) << "\n +---+---+---+---+---+---+---+---+\n"; } - os << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase + os << " a b c d e f g h\n" + << "\nFen: " << pos.fen() << "\nKey: " << std::hex << std::uppercase << std::setfill('0') << std::setw(16) << pos.key() << std::setfill(' ') << std::dec << "\nCheckers: "; @@ -104,8 +105,7 @@ Key cuckoo[8192]; Move cuckooMove[8192]; -/// Position::init() initializes at startup the various arrays used to compute -/// hash keys. +/// Position::init() initializes at startup the various arrays used to compute hash keys void Position::init() { @@ -119,15 +119,7 @@ void Position::init() { Zobrist::enpassant[f] = rng.rand(); for (int cr = NO_CASTLING; cr <= ANY_CASTLING; ++cr) - { - Zobrist::castling[cr] = 0; - Bitboard b = cr; - while (b) - { - Key k = Zobrist::castling[1ULL << pop_lsb(&b)]; - Zobrist::castling[cr] ^= k ? k : rng.rand(); - } - } + Zobrist::castling[cr] = rng.rand(); Zobrist::side = rng.rand(); Zobrist::noPawns = rng.rand(); @@ -139,7 +131,7 @@ void Position::init() { for (Piece pc : Pieces) for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1) for (Square s2 = Square(s1 + 1); s2 <= SQ_H8; ++s2) - if (PseudoAttacks[type_of(pc)][s1] & s2) + if ((type_of(pc) != PAWN) && (attacks_bb(type_of(pc), s1, 0) & s2)) { Move move = make_move(s1, s2); Key key = Zobrist::psq[pc][s1] ^ Zobrist::psq[pc][s2] ^ Zobrist::side; @@ -186,9 +178,9 @@ Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Th 4) En passant target square (in algebraic notation). If there's no en passant target square, this is "-". If a pawn has just made a 2-square move, this - is the position "behind" the pawn. This is recorded only if there is a pawn - in position to make an en passant capture, and if there really is a pawn - that might have advanced two squares. + is the position "behind" the pawn. Following X-FEN standard, this is recorded only + if there is a pawn in position to make an en passant capture, and if there really + is a pawn that might have advanced two squares. 5) Halfmove clock. This is the number of halfmoves since the last pawn advance or capture. This is used to determine if a draw can be claimed under the @@ -259,17 +251,25 @@ Position& Position::set(const string& fenStr, bool isChess960, StateInfo* si, Th set_castling_right(c, rsq); } - // 4. En passant square. Ignore if no pawn capture is possible + // 4. En passant square. + // Ignore if square is invalid or not on side to move relative rank 6. + bool enpassant = false; + if ( ((ss >> col) && (col >= 'a' && col <= 'h')) - && ((ss >> row) && (row == '3' || row == '6'))) + && ((ss >> row) && (row == (sideToMove == WHITE ? '6' : '3')))) { st->epSquare = make_square(File(col - 'a'), Rank(row - '1')); - if ( !(attackers_to(st->epSquare) & pieces(sideToMove, PAWN)) - || !(pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove)))) - st->epSquare = SQ_NONE; + // En passant square will be considered only if + // a) side to move have a pawn threatening epSquare + // b) there is an enemy pawn in front of epSquare + // c) there is no piece on epSquare or behind epSquare + enpassant = pawn_attacks_bb(~sideToMove, st->epSquare) & pieces(sideToMove, PAWN) + && (pieces(~sideToMove, PAWN) & (st->epSquare + pawn_push(~sideToMove))) + && !(pieces() & (st->epSquare | (st->epSquare + pawn_push(sideToMove)))); } - else + + if (!enpassant) st->epSquare = SQ_NONE; // 5-6. Halfmove clock and fullmove number @@ -304,7 +304,7 @@ void Position::set_castling_right(Color c, Square rfrom) { Square rto = relative_square(c, cr & KING_SIDE ? SQ_F1 : SQ_D1); castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto) - & ~(square_bb(kfrom) | rfrom); + & ~(kfrom | rfrom); } @@ -317,10 +317,10 @@ void Position::set_check_info(StateInfo* si) const { Square ksq = square(~sideToMove); - si->checkSquares[PAWN] = attacks_from(ksq, ~sideToMove); - si->checkSquares[KNIGHT] = attacks_from(ksq); - si->checkSquares[BISHOP] = attacks_from(ksq); - si->checkSquares[ROOK] = attacks_from(ksq); + si->checkSquares[PAWN] = pawn_attacks_bb(~sideToMove, ksq); + si->checkSquares[KNIGHT] = attacks_bb(ksq); + si->checkSquares[BISHOP] = attacks_bb(ksq, pieces()); + si->checkSquares[ROOK] = attacks_bb(ksq, pieces()); si->checkSquares[QUEEN] = si->checkSquares[BISHOP] | si->checkSquares[ROOK]; si->checkSquares[KING] = 0; } @@ -373,11 +373,13 @@ void Position::set_state(StateInfo* si) const { Position& Position::set(const string& code, Color c, StateInfo* si) { - assert(code.length() > 0 && code.length() < 8); assert(code[0] == 'K'); string sides[] = { code.substr(code.find('K', 1)), // Weak - code.substr(0, code.find('K', 1)) }; // Strong + code.substr(0, std::min(code.find('v'), code.find('K', 1))) }; // Strong + + assert(sides[0].length() > 0 && sides[0].length() < 8); + assert(sides[1].length() > 0 && sides[1].length() < 8); std::transform(sides[c].begin(), sides[c].end(), sides[c].begin(), tolower); @@ -451,8 +453,8 @@ Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners pinners = 0; // Snipers are sliders that attack 's' when a piece and other snipers are removed - Bitboard snipers = ( (PseudoAttacks[ ROOK][s] & pieces(QUEEN, ROOK)) - | (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders; + Bitboard snipers = ( (attacks_bb< ROOK>(s) & pieces(QUEEN, ROOK)) + | (attacks_bb(s) & pieces(QUEEN, BISHOP))) & sliders; Bitboard occupancy = pieces() ^ snipers; while (snipers) @@ -476,12 +478,12 @@ Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners Bitboard Position::attackers_to(Square s, Bitboard occupied) const { - return (attacks_from(s, BLACK) & pieces(WHITE, PAWN)) - | (attacks_from(s, WHITE) & pieces(BLACK, PAWN)) - | (attacks_from(s) & pieces(KNIGHT)) + return (pawn_attacks_bb(BLACK, s) & pieces(WHITE, PAWN)) + | (pawn_attacks_bb(WHITE, s) & pieces(BLACK, PAWN)) + | (attacks_bb(s) & pieces(KNIGHT)) | (attacks_bb< ROOK>(s, occupied) & pieces( ROOK, QUEEN)) | (attacks_bb(s, occupied) & pieces(BISHOP, QUEEN)) - | (attacks_from(s) & pieces(KING)); + | (attacks_bb(s) & pieces(KING)); } @@ -584,15 +586,15 @@ bool Position::pseudo_legal(const Move m) const { if ((Rank8BB | Rank1BB) & to) return false; - if ( !(attacks_from(from, us) & pieces(~us) & to) // Not a capture + if ( !(pawn_attacks_bb(us, from) & pieces(~us) & to) // Not a capture && !((from + pawn_push(us) == to) && empty(to)) // Not a single push && !( (from + 2 * pawn_push(us) == to) // Not a double push - && (rank_of(from) == relative_rank(us, RANK_2)) + && (relative_rank(us, from) == RANK_2) && empty(to) && empty(to - pawn_push(us)))) return false; } - else if (!(attacks_from(type_of(pc), from) & to)) + else if (!(attacks_bb(type_of(pc), from, pieces()) & to)) return false; // Evasions generator already takes care to avoid some kind of illegal moves @@ -631,11 +633,11 @@ bool Position::gives_check(Move m) const { Square to = to_sq(m); // Is there a direct check? - if (st->checkSquares[type_of(piece_on(from))] & to) + if (check_squares(type_of(piece_on(from))) & to) return true; // Is there a discovered check? - if ( (st->blockersForKing[~sideToMove] & from) + if ( (blockers_for_king(~sideToMove) & from) && !aligned(from, to, square(~sideToMove))) return true; @@ -662,11 +664,11 @@ bool Position::gives_check(Move m) const { case CASTLING: { Square kfrom = from; - Square rfrom = to; // Castling is encoded as 'King captures the rook' + Square rfrom = to; // Castling is encoded as 'king captures the rook' Square kto = relative_square(sideToMove, rfrom > kfrom ? SQ_G1 : SQ_C1); Square rto = relative_square(sideToMove, rfrom > kfrom ? SQ_F1 : SQ_D1); - return (PseudoAttacks[ROOK][rto] & square(~sideToMove)) + return (attacks_bb(rto) & square(~sideToMove)) && (attacks_bb(rto, (pieces() ^ kfrom ^ rfrom) | rto | kto) & square(~sideToMove)); } default: @@ -741,8 +743,6 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) { assert(relative_rank(us, to) == RANK_6); assert(piece_on(to) == NO_PIECE); assert(piece_on(capsq) == make_piece(them, PAWN)); - - board[capsq] = NO_PIECE; // Not done by remove_piece() } st->pawnKey ^= Zobrist::psq[captured][capsq]; @@ -751,7 +751,10 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) { st->nonPawnMaterial[them] -= PieceValue[MG][captured]; // Update board and piece lists - remove_piece(captured, capsq); + remove_piece(capsq); + + if (type_of(m) == ENPASSANT) + board[capsq] = NO_PIECE; // Update material hash key and prefetch access to materialTable k ^= Zobrist::psq[captured][capsq]; @@ -775,21 +778,21 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) { // Update castling rights if needed if (st->castlingRights && (castlingRightsMask[from] | castlingRightsMask[to])) { - int cr = castlingRightsMask[from] | castlingRightsMask[to]; - k ^= Zobrist::castling[st->castlingRights & cr]; - st->castlingRights &= ~cr; + k ^= Zobrist::castling[st->castlingRights]; + st->castlingRights &= ~(castlingRightsMask[from] | castlingRightsMask[to]); + k ^= Zobrist::castling[st->castlingRights]; } // Move the piece. The tricky Chess960 castling is handled earlier if (type_of(m) != CASTLING) - move_piece(pc, from, to); + move_piece(from, to); // If the moving piece is a pawn do some special extra work if (type_of(pc) == PAWN) { // Set en-passant square if the moved pawn can be captured if ( (int(to) ^ int(from)) == 16 - && (attacks_from(to - pawn_push(us), us) & pieces(them, PAWN))) + && (pawn_attacks_bb(us, to - pawn_push(us)) & pieces(them, PAWN))) { st->epSquare = to - pawn_push(us); k ^= Zobrist::enpassant[file_of(st->epSquare)]; @@ -802,7 +805,7 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) { assert(relative_rank(us, to) == RANK_8); assert(type_of(promotion) >= KNIGHT && type_of(promotion) <= QUEEN); - remove_piece(pc, to); + remove_piece(to); put_piece(promotion, to); // Update hash keys @@ -882,7 +885,7 @@ void Position::undo_move(Move m) { assert(type_of(pc) == promotion_type(m)); assert(type_of(pc) >= KNIGHT && type_of(pc) <= QUEEN); - remove_piece(pc, to); + remove_piece(to); pc = make_piece(us, PAWN); put_piece(pc, to); } @@ -894,7 +897,7 @@ void Position::undo_move(Move m) { } else { - move_piece(pc, to, from); // Put the piece back at the source square + move_piece(to, from); // Put the piece back at the source square if (st->capturedPiece) { @@ -934,9 +937,9 @@ void Position::do_castling(Color us, Square from, Square& to, Square& rfrom, Squ to = relative_square(us, kingSide ? SQ_G1 : SQ_C1); // Remove both pieces first since squares could overlap in Chess960 - remove_piece(make_piece(us, KING), Do ? from : to); - remove_piece(make_piece(us, ROOK), Do ? rfrom : rto); - board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do it for us + remove_piece(Do ? from : to); + remove_piece(Do ? rfrom : rto); + board[Do ? from : to] = board[Do ? rfrom : rto] = NO_PIECE; // Since remove_piece doesn't do this for us put_piece(make_piece(us, KING), Do ? to : from); put_piece(make_piece(us, ROOK), Do ? rto : rfrom); } @@ -1106,6 +1109,7 @@ bool Position::see_ge(Move m, Value threshold) const { return bool(res); } + /// Position::is_draw() tests whether the position is drawn by 50-move rule /// or by repetition. It does not detect stalemates. @@ -1116,10 +1120,7 @@ bool Position::is_draw(int ply) const { // Return a draw score if a position repeats once earlier but strictly // after the root, or repeats twice before or at the root. - if (st->repetition && st->repetition < ply) - return true; - - return false; + return st->repetition && st->repetition < ply; } diff --git a/src/position.h b/src/position.h index 6791455f..8cfa3920 100644 --- a/src/position.h +++ b/src/position.h @@ -56,6 +56,7 @@ struct StateInfo { int repetition; }; + /// A list to keep track of the position states along the setup moves (from the /// start position to the position just before the search starts). Needed by /// 'draw by repetition' detection. Use a std::deque because pointers to @@ -83,7 +84,6 @@ public: const std::string fen() const; // Position representation - Bitboard pieces() const; Bitboard pieces(PieceType pt) const; Bitboard pieces(PieceType pt1, PieceType pt2) const; Bitboard pieces(Color c) const; @@ -99,7 +99,7 @@ public: bool is_on_semiopen_file(Color c, Square s) const; // Castling - int castling_rights(Color c) const; + CastlingRights castling_rights(Color c) const; bool can_castle(CastlingRights cr) const; bool castling_impeded(CastlingRights cr) const; Square castling_rook_square(CastlingRights cr) const; @@ -113,9 +113,6 @@ public: // Attacks to/from a given square Bitboard attackers_to(Square s) const; Bitboard attackers_to(Square s, Bitboard occupied) const; - Bitboard attacks_from(PieceType pt, Square s) const; - template Bitboard attacks_from(Square s) const; - template Bitboard attacks_from(Square s, Color c) const; Bitboard slider_blockers(Bitboard sliders, Square s, Bitboard& pinners) const; // Properties of moves @@ -174,8 +171,8 @@ private: // Other helpers void put_piece(Piece pc, Square s); - void remove_piece(Piece pc, Square s); - void move_piece(Piece pc, Square from, Square to); + void remove_piece(Square s); + void move_piece(Square from, Square to); template void do_castling(Color us, Square from, Square& to, Square& rfrom, Square& rto); @@ -207,28 +204,25 @@ inline Color Position::side_to_move() const { return sideToMove; } -inline bool Position::empty(Square s) const { - return board[s] == NO_PIECE; -} - inline Piece Position::piece_on(Square s) const { + assert(is_ok(s)); return board[s]; } -inline Piece Position::moved_piece(Move m) const { - return board[from_sq(m)]; +inline bool Position::empty(Square s) const { + return piece_on(s) == NO_PIECE; } -inline Bitboard Position::pieces() const { - return byTypeBB[ALL_PIECES]; +inline Piece Position::moved_piece(Move m) const { + return piece_on(from_sq(m)); } -inline Bitboard Position::pieces(PieceType pt) const { +inline Bitboard Position::pieces(PieceType pt = ALL_PIECES) const { return byTypeBB[pt]; } inline Bitboard Position::pieces(PieceType pt1, PieceType pt2) const { - return byTypeBB[pt1] | byTypeBB[pt2]; + return pieces(pt1) | pieces(pt2); } inline Bitboard Position::pieces(Color c) const { @@ -236,11 +230,11 @@ inline Bitboard Position::pieces(Color c) const { } inline Bitboard Position::pieces(Color c, PieceType pt) const { - return byColorBB[c] & byTypeBB[pt]; + return pieces(c) & pieces(pt); } inline Bitboard Position::pieces(Color c, PieceType pt1, PieceType pt2) const { - return byColorBB[c] & (byTypeBB[pt1] | byTypeBB[pt2]); + return pieces(c) & (pieces(pt1) | pieces(pt2)); } template inline int Position::count(Color c) const { @@ -248,7 +242,7 @@ template inline int Position::count(Color c) const { } template inline int Position::count() const { - return pieceCount[make_piece(WHITE, Pt)] + pieceCount[make_piece(BLACK, Pt)]; + return count(WHITE) + count(BLACK); } template inline const Square* Position::squares(Color c) const { @@ -257,7 +251,7 @@ template inline const Square* Position::squares(Color c) const { template inline Square Position::square(Color c) const { assert(pieceCount[make_piece(c, Pt)] == 1); - return pieceList[make_piece(c, Pt)][0]; + return squares(c)[0]; } inline Square Position::ep_square() const { @@ -272,14 +266,14 @@ inline bool Position::can_castle(CastlingRights cr) const { return st->castlingRights & cr; } -inline int Position::castling_rights(Color c) const { - return st->castlingRights & (c == WHITE ? WHITE_CASTLING : BLACK_CASTLING); +inline CastlingRights Position::castling_rights(Color c) const { + return c & CastlingRights(st->castlingRights); } inline bool Position::castling_impeded(CastlingRights cr) const { assert(cr == WHITE_OO || cr == WHITE_OOO || cr == BLACK_OO || cr == BLACK_OOO); - return byTypeBB[ALL_PIECES] & castlingPath[cr]; + return pieces() & castlingPath[cr]; } inline Square Position::castling_rook_square(CastlingRights cr) const { @@ -288,26 +282,8 @@ inline Square Position::castling_rook_square(CastlingRights cr) const { return castlingRookSquare[cr]; } -template -inline Bitboard Position::attacks_from(Square s) const { - static_assert(Pt != PAWN, "Pawn attacks need color"); - - return Pt == BISHOP || Pt == ROOK ? attacks_bb(s, byTypeBB[ALL_PIECES]) - : Pt == QUEEN ? attacks_from(s) | attacks_from(s) - : PseudoAttacks[Pt][s]; -} - -template<> -inline Bitboard Position::attacks_from(Square s, Color c) const { - return PawnAttacks[c][s]; -} - -inline Bitboard Position::attacks_from(PieceType pt, Square s) const { - return attacks_bb(pt, s, byTypeBB[ALL_PIECES]); -} - inline Bitboard Position::attackers_to(Square s) const { - return attackers_to(s, byTypeBB[ALL_PIECES]); + return attackers_to(s, pieces()); } inline Bitboard Position::checkers() const { @@ -360,7 +336,7 @@ inline Value Position::non_pawn_material(Color c) const { } inline Value Position::non_pawn_material() const { - return st->nonPawnMaterial[WHITE] + st->nonPawnMaterial[BLACK]; + return non_pawn_material(WHITE) + non_pawn_material(BLACK); } inline int Position::game_ply() const { @@ -372,8 +348,8 @@ inline int Position::rule50_count() const { } inline bool Position::opposite_bishops() const { - return pieceCount[W_BISHOP] == 1 - && pieceCount[B_BISHOP] == 1 + return count(WHITE) == 1 + && count(BLACK) == 1 && opposite_colors(square(WHITE), square(BLACK)); } @@ -403,8 +379,7 @@ inline Thread* Position::this_thread() const { inline void Position::put_piece(Piece pc, Square s) { board[s] = pc; - byTypeBB[ALL_PIECES] |= s; - byTypeBB[type_of(pc)] |= s; + byTypeBB[ALL_PIECES] |= byTypeBB[type_of(pc)] |= s; byColorBB[color_of(pc)] |= s; index[s] = pieceCount[pc]++; pieceList[pc][index[s]] = s; @@ -412,12 +387,13 @@ inline void Position::put_piece(Piece pc, Square s) { psq += PSQT::psq[pc][s]; } -inline void Position::remove_piece(Piece pc, Square s) { +inline void Position::remove_piece(Square s) { // WARNING: This is not a reversible operation. If we remove a piece in // do_move() and then replace it in undo_move() we will put it at the end of // the list and not in its original place, it means index[] and pieceList[] // are not invariant to a do_move() + undo_move() sequence. + Piece pc = board[s]; byTypeBB[ALL_PIECES] ^= s; byTypeBB[type_of(pc)] ^= s; byColorBB[color_of(pc)] ^= s; @@ -430,10 +406,11 @@ inline void Position::remove_piece(Piece pc, Square s) { psq -= PSQT::psq[pc][s]; } -inline void Position::move_piece(Piece pc, Square from, Square to) { +inline void Position::move_piece(Square from, Square to) { // index[from] is not updated and becomes stale. This works as long as index[] // is accessed just by known occupied squares. + Piece pc = board[from]; Bitboard fromTo = from | to; byTypeBB[ALL_PIECES] ^= fromTo; byTypeBB[type_of(pc)] ^= fromTo; diff --git a/src/psqt.cpp b/src/psqt.cpp index 647bd864..5e8dd2c7 100644 --- a/src/psqt.cpp +++ b/src/psqt.cpp @@ -21,11 +21,7 @@ #include #include "types.h" - -Value PieceValue[PHASE_NB][PIECE_NB] = { - { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg }, - { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg } -}; +#include "bitboard.h" namespace PSQT { @@ -95,9 +91,9 @@ constexpr Score PBonus[RANK_NB][FILE_NB] = { }, { S( 3,-10), S( 3, -6), S( 10, 10), S( 19, 0), S( 16, 14), S( 19, 7), S( 7, -5), S( -5,-19) }, { S( -9,-10), S(-15,-10), S( 11,-10), S( 15, 4), S( 32, 4), S( 22, 3), S( 5, -6), S(-22, -4) }, - { S( -8, 6), S(-23, -2), S( 6, -8), S( 20, -4), S( 40,-13), S( 17,-12), S( 4,-10), S(-12, -9) }, - { S( 13, 9), S( 0, 4), S(-13, 3), S( 1,-12), S( 11,-12), S( -2, -6), S(-13, 13), S( 5, 8) }, - { S( -5, 28), S(-12, 20), S( -7, 21), S( 22, 28), S( -8, 30), S( -5, 7), S(-15, 6), S(-18, 13) }, + { S( -4, 6), S(-23, -2), S( 6, -8), S( 20, -4), S( 40,-13), S( 17,-12), S( 4,-10), S( -8, -9) }, + { S( 13, 10), S( 0, 5), S(-13, 4), S( 1, -5), S( 11, -5), S( -2, -5), S(-13, 14), S( 5, 9) }, + { S( 5, 28), S(-12, 20), S( -7, 21), S( 22, 28), S( -8, 30), S( -5, 7), S(-15, 6), S( -8, 13) }, { S( -7, 0), S( 7,-11), S( -3, 12), S(-13, 21), S( 5, 25), S(-16, 19), S( 10, 4), S( -8, 7) } }; @@ -105,24 +101,22 @@ constexpr Score PBonus[RANK_NB][FILE_NB] = Score psq[PIECE_NB][SQUARE_NB]; -// init() initializes piece-square tables: the white halves of the tables are -// copied from Bonus[] adding the piece value, then the black halves of the -// tables are initialized by flipping and changing the sign of the white scores. + +// PSQT::init() initializes piece-square tables: the white halves of the tables are +// copied from Bonus[] and PBonus[], adding the piece value, then the black halves of +// the tables are initialized by flipping and changing the sign of the white scores. void init() { - for (Piece pc = W_PAWN; pc <= W_KING; ++pc) + for (Piece pc : {W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING}) { - PieceValue[MG][~pc] = PieceValue[MG][pc]; - PieceValue[EG][~pc] = PieceValue[EG][pc]; - Score score = make_score(PieceValue[MG][pc], PieceValue[EG][pc]); for (Square s = SQ_A1; s <= SQ_H8; ++s) { - File f = map_to_queenside(file_of(s)); - psq[ pc][ s] = score + (type_of(pc) == PAWN ? PBonus[rank_of(s)][file_of(s)] - : Bonus[pc][rank_of(s)][f]); - psq[~pc][~s] = -psq[pc][s]; + File f = File(edge_distance(file_of(s))); + psq[ pc][s] = score + (type_of(pc) == PAWN ? PBonus[rank_of(s)][file_of(s)] + : Bonus[pc][rank_of(s)][f]); + psq[~pc][flip_rank(s)] = -psq[pc][s]; } } } diff --git a/src/search.cpp b/src/search.cpp index 0eea4127..91ac60ad 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -61,13 +61,13 @@ namespace { // Different node types, used as a template parameter enum NodeType { NonPV, PV }; - constexpr uint64_t ttHitAverageWindow = 4096; - constexpr uint64_t ttHitAverageResolution = 1024; + constexpr uint64_t TtHitAverageWindow = 4096; + constexpr uint64_t TtHitAverageResolution = 1024; // Razor and futility margins - constexpr int RazorMargin = 531; + constexpr int RazorMargin = 527; Value futility_margin(Depth d, bool improving) { - return Value(217 * (d - improving)); + return Value(227 * (d - improving)); } // Reductions lookup table, initialized at startup @@ -75,16 +75,16 @@ namespace { Depth reduction(bool i, Depth d, int mn) { int r = Reductions[d] * Reductions[mn]; - return (r + 511) / 1024 + (!i && r > 1007); + return (r + 570) / 1024 + (!i && r > 1018); } constexpr int futility_move_count(bool improving, Depth depth) { - return (5 + depth * depth) * (1 + improving) / 2 - 1; + return (3 + depth * depth) / (2 - improving); } // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return d > 15 ? -8 : 19 * d * d + 155 * d - 132; + return d > 15 ? 27 : 17 * d * d + 133 * d - 134; } // Add a small random component to draw evaluations to avoid 3fold-blindness @@ -156,7 +156,7 @@ namespace { Value value_from_tt(Value v, int ply, int r50c); void update_pv(Move* pv, Move move, Move* childPv); void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus); - void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus); + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth); void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq, Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth); @@ -194,7 +194,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((24.8 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((24.8 + std::log(Threads.size())) * std::log(i)); } @@ -236,14 +236,8 @@ void MainThread::search() { } else { - for (Thread* th : Threads) - { - th->bestMoveChanges = 0; - if (th != this) - th->start_searching(); - } - - Thread::search(); // Let's start searching! + Threads.start_searching(); // start non-main threads + Thread::search(); // main thread start searching } // When we reach the maximum depth, we can arrive here without a raise of @@ -260,9 +254,7 @@ void MainThread::search() { Threads.stop = true; // Wait until all threads have finished - for (Thread* th : Threads) - if (th != this) - th->wait_for_search_finished(); + Threads.wait_for_search_finished(); // When playing in 'nodes as time' mode, subtract the searched nodes from // the available ones before exiting. @@ -271,38 +263,13 @@ void MainThread::search() { Thread* bestThread = this; - // Check if there are threads with a better score than main thread - if ( Options["MultiPV"] == 1 + if ( int(Options["MultiPV"]) == 1 && !Limits.depth - && !(Skill(Options["Skill Level"]).enabled() || Options["UCI_LimitStrength"]) - && rootMoves[0].pv[0] != MOVE_NONE) - { - std::map votes; - Value minScore = this->rootMoves[0].score; + && !(Skill(Options["Skill Level"]).enabled() || int(Options["UCI_LimitStrength"])) + && rootMoves[0].pv[0] != MOVE_NONE) + bestThread = Threads.get_best_thread(); - // Find out minimum score - for (Thread* th: Threads) - minScore = std::min(minScore, th->rootMoves[0].score); - - // Vote according to score and depth, and select the best thread - for (Thread* th : Threads) - { - votes[th->rootMoves[0].pv[0]] += - (th->rootMoves[0].score - minScore + 14) * int(th->completedDepth); - - if (bestThread->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY) - { - // Make sure we pick the shortest mate - if (th->rootMoves[0].score > bestThread->rootMoves[0].score) - bestThread = th; - } - else if ( th->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY - || votes[th->rootMoves[0].pv[0]] > votes[bestThread->rootMoves[0].pv[0]]) - bestThread = th; - } - } - - previousScore = bestThread->rootMoves[0].score; + bestPreviousScore = bestThread->rootMoves[0].score; // Send again PV info if we have a new best thread if (bestThread != this) @@ -348,15 +315,18 @@ void Thread::search() { if (mainThread) { - if (mainThread->previousScore == VALUE_INFINITE) - for (int i=0; i<4; ++i) + if (mainThread->bestPreviousScore == VALUE_INFINITE) + for (int i = 0; i < 4; ++i) mainThread->iterValue[i] = VALUE_ZERO; else - for (int i=0; i<4; ++i) - mainThread->iterValue[i] = mainThread->previousScore; + for (int i = 0; i < 4; ++i) + mainThread->iterValue[i] = mainThread->bestPreviousScore; } - size_t multiPV = Options["MultiPV"]; + std::copy(&lowPlyHistory[2][0], &lowPlyHistory.back().back() + 1, &lowPlyHistory[0][0]); + std::fill(&lowPlyHistory[MAX_LPH - 2][0], &lowPlyHistory.back().back() + 1, 0); + + size_t multiPV = size_t(Options["MultiPV"]); // Pick integer skill levels, but non-deterministically round up or down // such that the average integer skill corresponds to the input floating point one. @@ -365,7 +335,7 @@ void Thread::search() { // for match (TC 60+0.6) results spanning a wide range of k values. PRNG rng(now()); double floatLevel = Options["UCI_LimitStrength"] ? - clamp(std::pow((Options["UCI_Elo"] - 1346.6) / 143.4, 1 / 0.806), 0.0, 20.0) : + Utility::clamp(std::pow((Options["UCI_Elo"] - 1346.6) / 143.4, 1 / 0.806), 0.0, 20.0) : double(Options["Skill Level"]); int intLevel = int(floatLevel) + ((floatLevel - int(floatLevel)) * 1024 > rng.rand() % 1024 ? 1 : 0); @@ -377,7 +347,7 @@ void Thread::search() { multiPV = std::max(multiPV, (size_t)4); multiPV = std::min(multiPV, rootMoves.size()); - ttHitAverage = ttHitAverageWindow * ttHitAverageResolution / 2; + ttHitAverage = TtHitAverageWindow * TtHitAverageResolution / 2; int ct = int(Options["Contempt"]) * PawnValueEg / 100; // From centipawns @@ -432,13 +402,13 @@ void Thread::search() { // Reset aspiration window starting size if (rootDepth >= 4) { - Value previousScore = rootMoves[pvIdx].previousScore; - delta = Value(21 + abs(previousScore) / 256); - alpha = std::max(previousScore - delta,-VALUE_INFINITE); - beta = std::min(previousScore + delta, VALUE_INFINITE); + Value prev = rootMoves[pvIdx].previousScore; + delta = Value(19); + alpha = std::max(prev - delta,-VALUE_INFINITE); + beta = std::min(prev + delta, VALUE_INFINITE); // Adjust contempt based on root move's previousScore (dynamic contempt) - int dct = ct + (102 - ct / 2) * previousScore / (abs(previousScore) + 157); + int dct = ct + (110 - ct / 2) * prev / (abs(prev) + 140); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -536,13 +506,13 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (332 + 6 * (mainThread->previousScore - bestValue) - + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 704.0; - fallingEval = clamp(fallingEval, 0.5, 1.5); + double fallingEval = (296 + 6 * (mainThread->bestPreviousScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 725.0; + fallingEval = Utility::clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.94 : 0.91; - double reduction = (1.41 + mainThread->previousTimeReduction) / (2.27 * timeReduction); + timeReduction = lastBestMoveDepth + 10 < completedDepth ? 1.92 : 0.95; + double reduction = (1.47 + mainThread->previousTimeReduction) / (2.22 * timeReduction); // Use part of the gained time from a previous stable move for the current move for (Thread* th : Threads) @@ -552,9 +522,11 @@ void Thread::search() { } double bestMoveInstability = 1 + totBestMoveChanges / Threads.size(); - // Stop the search if we have only one legal move, or if available time elapsed - if ( rootMoves.size() == 1 - || Time.elapsed() > Time.optimum() * fallingEval * reduction * bestMoveInstability) + double totalTime = rootMoves.size() == 1 ? 0 : + Time.optimum() * fallingEval * reduction * bestMoveInstability; + + // Stop the search if we have exceeded the totalTime, at least 1ms search + if (Time.elapsed() > totalTime) { // If we are allowed to ponder do not stop the search now but // keep pondering until the GUI sends "ponderhit" or "stop". @@ -565,7 +537,7 @@ void Thread::search() { } else if ( Threads.increaseDepth && !mainThread->ponder - && Time.elapsed() > Time.optimum() * fallingEval * reduction * bestMoveInstability * 0.6) + && Time.elapsed() > totalTime * 0.56) Threads.increaseDepth = false; else Threads.increaseDepth = true; @@ -624,15 +596,16 @@ namespace { Key posKey; Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; - Value bestValue, value, ttValue, eval, maxValue; - bool ttHit, ttPv, inCheck, givesCheck, improving, didLMR, priorCapture; - bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture, singularLMR; + Value bestValue, value, ttValue, eval, maxValue, probcutBeta; + bool ttHit, ttPv, formerPv, givesCheck, improving, didLMR, priorCapture; + bool captureOrPromotion, doFullDepthSearch, moveCountPruning, + ttCapture, singularQuietLMR; Piece movedPiece; int moveCount, captureCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); - inCheck = pos.checkers(); + ss->inCheck = pos.checkers(); priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); moveCount = captureCount = quietCount = ss->moveCount = 0; @@ -653,8 +626,8 @@ namespace { if ( Threads.stop.load(std::memory_order_relaxed) || pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) - return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) - : value_draw(pos.this_thread()); + return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) + : value_draw(pos.this_thread()); // Step 3. Mate distance pruning. Even if we mate at the next move our score // would be at best mate_in(ss->ply+1), but if alpha is already bigger because @@ -689,15 +662,24 @@ namespace { // search to overwrite a previous full search TT value, so we use a different // position key in case of an excluded move. excludedMove = ss->excludedMove; - posKey = pos.key() ^ Key(excludedMove << 16); // Isn't a very good hash + posKey = excludedMove == MOVE_NONE ? pos.key() : pos.key() ^ make_key(excludedMove); tte = TT.probe(posKey, ttHit); ttValue = ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; ttPv = PvNode || (ttHit && tte->is_pv()); + formerPv = ttPv && !PvNode; + + if ( ttPv + && depth > 12 + && ss->ply - 1 < MAX_LPH + && !priorCapture + && is_ok((ss-1)->currentMove)) + thisThread->lowPlyHistory[ss->ply - 1][from_to((ss-1)->currentMove)] << stat_bonus(depth - 5); + // thisThread->ttHitAverage can be used to approximate the running average of ttHit - thisThread->ttHitAverage = (ttHitAverageWindow - 1) * thisThread->ttHitAverage / ttHitAverageWindow - + ttHitAverageResolution * ttHit; + thisThread->ttHitAverage = (TtHitAverageWindow - 1) * thisThread->ttHitAverage / TtHitAverageWindow + + TtHitAverageResolution * ttHit; // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -713,7 +695,7 @@ namespace { if (ttValue >= beta) { if (!pos.capture_or_promotion(ttMove)) - update_quiet_stats(pos, ss, ttMove, stat_bonus(depth)); + update_quiet_stats(pos, ss, ttMove, stat_bonus(depth), depth); // Extra penalty for early quiet moves of the previous ply if ((ss-1)->moveCount <= 2 && !priorCapture) @@ -755,9 +737,10 @@ namespace { int drawScore = TB::UseRule50 ? 1 : 0; - value = wdl < -drawScore ? -VALUE_MATE + MAX_PLY + ss->ply + 1 - : wdl > drawScore ? VALUE_MATE - MAX_PLY - ss->ply - 1 - : VALUE_DRAW + 2 * wdl * drawScore; + // use the range VALUE_MATE_IN_MAX_PLY to VALUE_TB_WIN_IN_MAX_PLY to score + value = wdl < -drawScore ? VALUE_MATED_IN_MAX_PLY + ss->ply + 1 + : wdl > drawScore ? VALUE_MATE_IN_MAX_PLY - ss->ply - 1 + : VALUE_DRAW + 2 * wdl * drawScore; Bound b = wdl < -drawScore ? BOUND_UPPER : wdl > drawScore ? BOUND_LOWER : BOUND_EXACT; @@ -783,12 +766,15 @@ namespace { } } + CapturePieceToHistory& captureHistory = thisThread->captureHistory; + // Step 6. Static evaluation of the position - if (inCheck) + if (ss->inCheck) { + // Skip early pruning when in check ss->staticEval = eval = VALUE_NONE; improving = false; - goto moves_loop; // Skip early pruning when in check + goto moves_loop; } else if (ttHit) { @@ -814,19 +800,19 @@ namespace { ss->staticEval = eval = evaluate(pos) + bonus; } else - ss->staticEval = eval = -(ss-1)->staticEval + 2 * Eval::Tempo; + ss->staticEval = eval = -(ss-1)->staticEval + 2 * Tempo; tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } // Step 7. Razoring (~1 Elo) if ( !rootNode // The required rootNode PV handling is not available in qsearch - && depth < 2 + && depth == 1 && eval <= alpha - RazorMargin) return qsearch(pos, ss, alpha, beta); - improving = (ss-2)->staticEval == VALUE_NONE ? (ss->staticEval >= (ss-4)->staticEval - || (ss-4)->staticEval == VALUE_NONE) : ss->staticEval >= (ss-2)->staticEval; + improving = (ss-2)->staticEval == VALUE_NONE ? (ss->staticEval > (ss-4)->staticEval + || (ss-4)->staticEval == VALUE_NONE) : ss->staticEval > (ss-2)->staticEval; // Step 8. Futility pruning: child node (~50 Elo) if ( !PvNode @@ -838,10 +824,10 @@ namespace { // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 23397 + && (ss-1)->statScore < 23824 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 32 * depth + 292 - improving * 30 + && ss->staticEval >= beta - 33 * depth - 33 * improving + 112 * ttPv + 311 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -849,7 +835,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = (854 + 68 * depth) / 258 + std::min(int(eval - beta) / 192, 3); + Depth R = (737 + 77 * depth) / 246 + std::min(int(eval - beta) / 192, 3); ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -862,8 +848,8 @@ namespace { if (nullValue >= beta) { - // Do not return unproven mate scores - if (nullValue >= VALUE_MATE_IN_MAX_PLY) + // Do not return unproven mate or TB scores + if (nullValue >= VALUE_TB_WIN_IN_MAX_PLY) nullValue = beta; if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 13)) @@ -885,18 +871,32 @@ namespace { } } + probcutBeta = beta + 176 - 49 * improving; + // Step 10. ProbCut (~10 Elo) // If we have a good enough capture and a reduced search returns a value // much above beta, we can (almost) safely prune the previous move. if ( !PvNode - && depth >= 5 - && abs(beta) < VALUE_MATE_IN_MAX_PLY) + && depth > 4 + && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY + && !( ttHit + && tte->depth() >= depth - 3 + && ttValue != VALUE_NONE + && ttValue < probcutBeta)) { - Value raisedBeta = std::min(beta + 189 - 45 * improving, VALUE_INFINITE); - MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &thisThread->captureHistory); + if ( ttHit + && tte->depth() >= depth - 3 + && ttValue != VALUE_NONE + && ttValue >= probcutBeta + && ttMove + && pos.capture_or_promotion(ttMove)) + return probcutBeta; + + assert(probcutBeta < VALUE_INFINITE); + MovePicker mp(pos, ttMove, probcutBeta - ss->staticEval, &captureHistory); int probCutCount = 0; - while ( (move = mp.next_move()) != MOVE_NONE + while ( (move = mp.next_move()) != MOVE_NONE && probCutCount < 2 + 2 * cutNode) if (move != excludedMove && pos.legal(move)) { @@ -907,7 +907,7 @@ namespace { probCutCount++; ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[inCheck] + ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] [captureOrPromotion] [pos.moved_piece(move)] [to_sq(move)]; @@ -915,16 +915,24 @@ namespace { pos.do_move(move, st); // Perform a preliminary qsearch to verify that the move holds - value = -qsearch(pos, ss+1, -raisedBeta, -raisedBeta+1); + value = -qsearch(pos, ss+1, -probcutBeta, -probcutBeta+1); // If the qsearch held, perform the regular search - if (value >= raisedBeta) - value = -search(pos, ss+1, -raisedBeta, -raisedBeta+1, depth - 4, !cutNode); + if (value >= probcutBeta) + value = -search(pos, ss+1, -probcutBeta, -probcutBeta+1, depth - 4, !cutNode); pos.undo_move(move); - if (value >= raisedBeta) + if (value >= probcutBeta) + { + if ( !(ttHit + && tte->depth() >= depth - 3 + && ttValue != VALUE_NONE)) + tte->save(posKey, value_to_tt(value, ss->ply), ttPv, + BOUND_LOWER, + depth - 3, move, ss->staticEval); return value; + } } } @@ -947,13 +955,15 @@ moves_loop: // When in check, search starts from here Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, - &thisThread->captureHistory, + &thisThread->lowPlyHistory, + &captureHistory, contHist, countermove, - ss->killers); + ss->killers, + ss->ply); value = bestValue; - singularLMR = moveCountPruning = false; + singularQuietLMR = moveCountPruning = false; ttCapture = ttMove && pos.capture_or_promotion(ttMove); // Mark this node as being searched @@ -996,17 +1006,17 @@ moves_loop: // When in check, search starts from here // Step 13. Pruning at shallow depth (~200 Elo) if ( !rootNode && pos.non_pawn_material(us) - && bestValue > VALUE_MATED_IN_MAX_PLY) + && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) { // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold moveCountPruning = moveCount >= futility_move_count(improving, depth); + // Reduced depth of the next LMR search + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); + if ( !captureOrPromotion && !givesCheck) { - // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); - // Countermoves based pruning (~20 Elo) if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold @@ -1015,20 +1025,40 @@ moves_loop: // When in check, search starts from here // Futility pruning: parent node (~5 Elo) if ( lmrDepth < 6 - && !inCheck - && ss->staticEval + 235 + 172 * lmrDepth <= alpha - && thisThread->mainHistory[us][from_to(move)] - + (*contHist[0])[movedPiece][to_sq(move)] + && !ss->inCheck + && ss->staticEval + 284 + 188 * lmrDepth <= alpha + && (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] - + (*contHist[3])[movedPiece][to_sq(move)] < 25000) + + (*contHist[3])[movedPiece][to_sq(move)] + + (*contHist[5])[movedPiece][to_sq(move)] / 2 < 28388) continue; // Prune moves with negative SEE (~20 Elo) - if (!pos.see_ge(move, Value(-(32 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) + if (!pos.see_ge(move, Value(-(29 - std::min(lmrDepth, 17)) * lmrDepth * lmrDepth))) continue; } - else if (!pos.see_ge(move, Value(-194) * depth)) // (~25 Elo) + else + { + // Capture history based pruning when the move doesn't give check + if ( !givesCheck + && lmrDepth < 1 + && captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] < 0) + continue; + + // Futility pruning for captures + if ( !givesCheck + && lmrDepth < 6 + && !(PvNode && abs(bestValue) < 2) + && PieceValue[MG][type_of(movedPiece)] >= PieceValue[MG][type_of(pos.piece_on(to_sq(move)))] + && !ss->inCheck + && ss->staticEval + 267 + 391 * lmrDepth + + PieceValue[MG][type_of(pos.piece_on(to_sq(move)))] <= alpha) + continue; + + // See based pruning + if (!pos.see_ge(move, Value(-202) * depth)) // (~25 Elo) continue; + } } // Step 14. Extensions (~75 Elo) @@ -1037,7 +1067,7 @@ moves_loop: // When in check, search starts from here // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), // then that move is singular and should be extended. To verify this we do // a reduced search on all the other moves but the ttMove and if the - // result is lower than ttValue minus a margin then we will extend the ttMove. + // result is lower than ttValue minus a margin, then we will extend the ttMove. if ( depth >= 6 && move == ttMove && !rootNode @@ -1048,16 +1078,16 @@ moves_loop: // When in check, search starts from here && tte->depth() >= depth - 3 && pos.legal(move)) { - Value singularBeta = ttValue - 2 * depth; - Depth halfDepth = depth / 2; + Value singularBeta = ttValue - ((formerPv + 4) * depth) / 2; + Depth singularDepth = (depth - 1 + 3 * formerPv) / 2; ss->excludedMove = move; - value = search(pos, ss, singularBeta - 1, singularBeta, halfDepth, cutNode); + value = search(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); ss->excludedMove = MOVE_NONE; if (value < singularBeta) { extension = 1; - singularLMR = true; + singularQuietLMR = !ttCapture; } // Multi-cut pruning @@ -1067,6 +1097,18 @@ moves_loop: // When in check, search starts from here // a soft bound. else if (singularBeta >= beta) return singularBeta; + + // If the eval of ttMove is greater than beta we try also if there is another + // move that pushes it over beta, if so also produce a cutoff. + else if (ttValue >= beta) + { + ss->excludedMove = move; + value = search(pos, ss, beta - 1, beta, (depth + 3) / 2, cutNode); + ss->excludedMove = MOVE_NONE; + + if (value >= beta) + return beta; + } } // Check extension (~2 Elo) @@ -1104,7 +1146,7 @@ moves_loop: // When in check, search starts from here // Update the current move (this must be done after singular extension search) ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[inCheck] + ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] [captureOrPromotion] [movedPiece] [to_sq(move)]; @@ -1115,21 +1157,28 @@ moves_loop: // When in check, search starts from here // Step 16. Reduced depth search (LMR, ~200 Elo). If the move fails high it will be // re-searched at full depth. if ( depth >= 3 - && moveCount > 1 + rootNode + (rootNode && bestValue < alpha) + && moveCount > 1 + 2 * rootNode && (!rootNode || thisThread->best_move_count(move) == 0) && ( !captureOrPromotion || moveCountPruning || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha || cutNode - || thisThread->ttHitAverage < 375 * ttHitAverageResolution * ttHitAverageWindow / 1024)) + || thisThread->ttHitAverage < 415 * TtHitAverageResolution * TtHitAverageWindow / 1024)) { Depth r = reduction(improving, depth, moveCount); + // Decrease reduction at non-check cut nodes for second move at low depths + if ( cutNode + && depth <= 10 + && moveCount <= 2 + && !ss->inCheck) + r--; + // Decrease reduction if the ttHit running average is large - if (thisThread->ttHitAverage > 500 * ttHitAverageResolution * ttHitAverageWindow / 1024) + if (thisThread->ttHitAverage > 473 * TtHitAverageResolution * TtHitAverageWindow / 1024) r--; - // Reduction if other threads are searching this position. + // Reduction if other threads are searching this position if (th.marked()) r++; @@ -1137,13 +1186,16 @@ moves_loop: // When in check, search starts from here if (ttPv) r -= 2; + if (moveCountPruning && !formerPv) + r++; + // Decrease reduction if opponent's move count is high (~5 Elo) - if ((ss-1)->moveCount > 14) + if ((ss-1)->moveCount > 13) r--; // Decrease reduction if ttMove has been singularly extended (~3 Elo) - if (singularLMR) - r -= 2; + if (singularQuietLMR) + r -= 1 + formerPv; if (!captureOrPromotion) { @@ -1160,44 +1212,50 @@ moves_loop: // When in check, search starts from here // hence break make_move(). (~2 Elo) else if ( type_of(move) == NORMAL && !pos.see_ge(reverse_move(move))) - r -= 2; + r -= 2 + ttPv - (type_of(movedPiece) == PAWN); ss->statScore = thisThread->mainHistory[us][from_to(move)] + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 4926; - - // Reset statScore to zero if negative and most stats shows >= 0 - if ( ss->statScore < 0 - && (*contHist[0])[movedPiece][to_sq(move)] >= 0 - && (*contHist[1])[movedPiece][to_sq(move)] >= 0 - && thisThread->mainHistory[us][from_to(move)] >= 0) - ss->statScore = 0; + - 4826; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) - if (ss->statScore >= -102 && (ss-1)->statScore < -114) + if (ss->statScore >= -100 && (ss-1)->statScore < -112) r--; - else if ((ss-1)->statScore >= -116 && ss->statScore < -154) + else if ((ss-1)->statScore >= -125 && ss->statScore < -138) r++; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 16384; + r -= ss->statScore / 14615; + } + else + { + // Increase reduction for captures/promotions if late move and at low depth + if (depth < 8 && moveCount > 2) + r++; + + // Unless giving check, this capture is likely bad + if ( !givesCheck + && ss->staticEval + PieceValue[EG][pos.captured_piece()] + 211 * depth <= alpha) + r++; } - // Increase reduction for captures/promotions if late move and at low depth - else if (depth < 8 && moveCount > 2) - r++; - - Depth d = clamp(newDepth - r, 1, newDepth); + Depth d = Utility::clamp(newDepth - r, 1, newDepth); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = (value > alpha && d != newDepth), didLMR = true; + doFullDepthSearch = value > alpha && d != newDepth; + + didLMR = true; } else - doFullDepthSearch = !PvNode || moveCount > 1, didLMR = false; + { + doFullDepthSearch = !PvNode || moveCount > 1; + + didLMR = false; + } // Step 17. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) @@ -1257,7 +1315,7 @@ moves_loop: // When in check, search starts from here rm.pv.push_back(*m); // We record how often the best move has been changed in each - // iteration. This information is used for time management: When + // iteration. This information is used for time management: when // the best move changes frequently, we allocate some more time. if (moveCount > 1) ++thisThread->bestMoveChanges; @@ -1314,11 +1372,11 @@ moves_loop: // When in check, search starts from here // must be a mate or a stalemate. If we are in a singular extension search then // return a fail low score. - assert(moveCount || !inCheck || excludedMove || !MoveList(pos).size()); + assert(moveCount || !ss->inCheck || excludedMove || !MoveList(pos).size()); if (!moveCount) bestValue = excludedMove ? alpha - : inCheck ? mated_in(ss->ply) : VALUE_DRAW; + : ss->inCheck ? mated_in(ss->ply) : VALUE_DRAW; else if (bestMove) update_all_stats(pos, ss, bestMove, bestValue, beta, prevSq, @@ -1332,7 +1390,7 @@ moves_loop: // When in check, search starts from here if (PvNode) bestValue = std::min(bestValue, maxValue); - if (!excludedMove) + if (!excludedMove && !(rootNode && thisThread->pvIdx)) tte->save(posKey, value_to_tt(bestValue, ss->ply), ttPv, bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, @@ -1362,7 +1420,7 @@ moves_loop: // When in check, search starts from here Move ttMove, move, bestMove; Depth ttDepth; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool ttHit, pvHit, inCheck, givesCheck, captureOrPromotion, evasionPrunable; + bool ttHit, pvHit, givesCheck, captureOrPromotion; int moveCount; if (PvNode) @@ -1375,20 +1433,20 @@ moves_loop: // When in check, search starts from here Thread* thisThread = pos.this_thread(); (ss+1)->ply = ss->ply + 1; bestMove = MOVE_NONE; - inCheck = pos.checkers(); + ss->inCheck = pos.checkers(); moveCount = 0; // Check for an immediate draw or maximum ply reached if ( pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) - return (ss->ply >= MAX_PLY && !inCheck) ? evaluate(pos) : VALUE_DRAW; + return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) : VALUE_DRAW; assert(0 <= ss->ply && ss->ply < MAX_PLY); // Decide whether or not to include checks: this fixes also the type of // TT entry depth that we are going to use. Note that in qsearch we use // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. - ttDepth = inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS + ttDepth = ss->inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; // Transposition table lookup posKey = pos.key(); @@ -1406,7 +1464,7 @@ moves_loop: // When in check, search starts from here return ttValue; // Evaluate the position statically - if (inCheck) + if (ss->inCheck) { ss->staticEval = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; @@ -1427,13 +1485,13 @@ moves_loop: // When in check, search starts from here else ss->staticEval = bestValue = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) - : -(ss-1)->staticEval + 2 * Eval::Tempo; + : -(ss-1)->staticEval + 2 * Tempo; // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) { if (!ttHit) - tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, BOUND_LOWER, + tte->save(posKey, value_to_tt(bestValue, ss->ply), false, BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->staticEval); return bestValue; @@ -1442,7 +1500,7 @@ moves_loop: // When in check, search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 154; + futilityBase = bestValue + 141; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1451,8 +1509,8 @@ moves_loop: // When in check, search starts from here // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, - // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will - // be generated. + // queen and checking knight promotions, and other checks(only if depth >= DEPTH_QS_CHECKS) + // will be generated. MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, contHist, @@ -1469,7 +1527,7 @@ moves_loop: // When in check, search starts from here moveCount++; // Futility pruning - if ( !inCheck + if ( !ss->inCheck && !givesCheck && futilityBase > -VALUE_KNOWN_WIN && !pos.advanced_pawn_push(move)) @@ -1491,14 +1549,8 @@ moves_loop: // When in check, search starts from here } } - // Detect non-capture evasions that are candidates to be pruned - evasionPrunable = inCheck - && (depth != 0 || moveCount > 2) - && bestValue > VALUE_MATED_IN_MAX_PLY - && !pos.capture(move); - - // Don't search moves with negative SEE values - if ( (!inCheck || evasionPrunable) && !pos.see_ge(move)) + // Do not search moves with negative SEE values + if ( !ss->inCheck && !pos.see_ge(move)) continue; // Speculative prefetch as early as possible @@ -1512,7 +1564,7 @@ moves_loop: // When in check, search starts from here } ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[inCheck] + ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] [captureOrPromotion] [pos.moved_piece(move)] [to_sq(move)]; @@ -1544,9 +1596,9 @@ moves_loop: // When in check, search starts from here } } - // All legal moves have been searched. A special case: If we're in check + // All legal moves have been searched. A special case: if we're in check // and no legal moves were found, it is checkmate. - if (inCheck && bestValue == -VALUE_INFINITE) + if (ss->inCheck && bestValue == -VALUE_INFINITE) return mated_in(ss->ply); // Plies to mate from the root tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, @@ -1560,28 +1612,47 @@ moves_loop: // When in check, search starts from here } - // value_to_tt() adjusts a mate score from "plies to mate from the root" to - // "plies to mate from the current position". Non-mate scores are unchanged. + // value_to_tt() adjusts a mate or TB score from "plies to mate from the root" to + // "plies to mate from the current position". Standard scores are unchanged. // The function is called before storing a value in the transposition table. Value value_to_tt(Value v, int ply) { assert(v != VALUE_NONE); - return v >= VALUE_MATE_IN_MAX_PLY ? v + ply - : v <= VALUE_MATED_IN_MAX_PLY ? v - ply : v; + return v >= VALUE_TB_WIN_IN_MAX_PLY ? v + ply + : v <= VALUE_TB_LOSS_IN_MAX_PLY ? v - ply : v; } - // value_from_tt() is the inverse of value_to_tt(): It adjusts a mate score - // from the transposition table (which refers to the plies to mate/be mated - // from current position) to "plies to mate/be mated from the root". + // value_from_tt() is the inverse of value_to_tt(): it adjusts a mate or TB score + // from the transposition table (which refers to the plies to mate/be mated from + // current position) to "plies to mate/be mated (TB win/loss) from the root". However, + // for mate scores, to avoid potentially false mate scores related to the 50 moves rule + // and the graph history interaction, we return an optimal TB score instead. Value value_from_tt(Value v, int ply, int r50c) { - return v == VALUE_NONE ? VALUE_NONE - : v >= VALUE_MATE_IN_MAX_PLY ? VALUE_MATE - v > 99 - r50c ? VALUE_MATE_IN_MAX_PLY : v - ply - : v <= VALUE_MATED_IN_MAX_PLY ? VALUE_MATE + v > 99 - r50c ? VALUE_MATED_IN_MAX_PLY : v + ply : v; + if (v == VALUE_NONE) + return VALUE_NONE; + + if (v >= VALUE_TB_WIN_IN_MAX_PLY) // TB win or better + { + if (v >= VALUE_MATE_IN_MAX_PLY && VALUE_MATE - v > 99 - r50c) + return VALUE_MATE_IN_MAX_PLY - 1; // do not return a potentially false mate score + + return v - ply; + } + + if (v <= VALUE_TB_LOSS_IN_MAX_PLY) // TB loss or worse + { + if (v <= VALUE_MATED_IN_MAX_PLY && VALUE_MATE + v > 99 - r50c) + return VALUE_MATED_IN_MAX_PLY + 1; // do not return a potentially false mate score + + return v + ply; + } + + return v; } @@ -1613,7 +1684,7 @@ moves_loop: // When in check, search starts from here if (!pos.capture_or_promotion(bestMove)) { - update_quiet_stats(pos, ss, bestMove, bonus2); + update_quiet_stats(pos, ss, bestMove, bonus2, depth); // Decrease all the non-best quiet moves for (int i = 0; i < quietCount; ++i) @@ -1641,19 +1712,23 @@ moves_loop: // When in check, search starts from here // update_continuation_histories() updates histories of the move pairs formed - // by moves at ply -1, -2, and -4 with current move. + // by moves at ply -1, -2, -4, and -6 with current move. void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) { for (int i : {1, 2, 4, 6}) + { + if (ss->inCheck && i > 2) + break; if (is_ok((ss-i)->currentMove)) (*(ss-i)->continuationHistory)[pc][to] << bonus; + } } // update_quiet_stats() updates move sorting heuristics - void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus) { + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth) { if (ss->killers[0] != move) { @@ -1674,6 +1749,9 @@ moves_loop: // When in check, search starts from here Square prevSq = to_sq((ss-1)->currentMove); thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move; } + + if (depth > 11 && ss->ply < MAX_LPH) + thisThread->lowPlyHistory[ss->ply][from_to(move)] << stat_bonus(depth - 6); } // When playing with strength handicap, choose best move among a set of RootMoves @@ -1711,6 +1789,7 @@ moves_loop: // When in check, search starts from here } // namespace + /// MainThread::check_time() is used to print debug info and, more importantly, /// to detect when we are out of available time and thus stop the search. @@ -1767,7 +1846,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { Depth d = updated ? depth : depth - 1; Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore; - bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; + bool tb = TB::RootInTB && abs(v) < VALUE_MATE_IN_MAX_PLY; v = tb ? rootMoves[i].tbScore : v; if (ss.rdbuf()->in_avail()) // Not at first line @@ -1779,6 +1858,9 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { << " multipv " << i + 1 << " score " << UCI::value(v); + if (Options["UCI_ShowWDL"]) + ss << UCI::wdl(v, pos.game_ply()); + if (!tb && i == pvIdx) ss << (v >= beta ? " lowerbound" : v <= alpha ? " upperbound" : ""); diff --git a/src/search.h b/src/search.h index a900d094..3e855c8b 100644 --- a/src/search.h +++ b/src/search.h @@ -49,6 +49,7 @@ struct Stack { Value staticEval; int statScore; int moveCount; + bool inCheck; }; @@ -90,7 +91,7 @@ struct LimitsType { } bool use_time_management() const { - return !(mate | movetime | depth | nodes | perft | infinite); + return time[WHITE] || time[BLACK]; } std::vector searchmoves; diff --git a/src/syzygy/tbprobe.cpp b/src/syzygy/tbprobe.cpp index b9a33595..764574f7 100644 --- a/src/syzygy/tbprobe.cpp +++ b/src/syzygy/tbprobe.cpp @@ -60,13 +60,12 @@ namespace { constexpr int TBPIECES = 7; // Max number of supported pieces enum { BigEndian, LittleEndian }; -enum TBType { KEY, WDL, DTZ }; // Used as template parameter +enum TBType { WDL, DTZ }; // Used as template parameter // Each table has a set of flags: all of them refer to DTZ tables, the last one to WDL tables enum TBFlag { STM = 1, Mapped = 2, WinPlies = 4, LossPlies = 8, Wide = 16, SingleValue = 128 }; inline WDLScore operator-(WDLScore d) { return WDLScore(-int(d)); } -inline Square operator^=(Square& s, int i) { return s = Square(int(s) ^ i); } inline Square operator^(Square s, int i) { return Square(int(s) ^ i); } const std::string PieceToChar = " PNBRQK pnbrqk"; @@ -404,7 +403,17 @@ TBTable::TBTable(const TBTable& wdl) : TBTable() { // at init time, accessed at probe time. class TBTables { - typedef std::tuple*, TBTable*> Entry; + struct Entry + { + Key key; + TBTable* wdl; + TBTable* dtz; + + template + TBTable* get() const { + return (TBTable*)(Type == WDL ? (void*)wdl : (void*)dtz); + } + }; static constexpr int Size = 1 << 12; // 4K table, indexed by key's 12 lsb static constexpr int Overflow = 1; // Number of elements allowed to map to the last bucket @@ -416,12 +425,12 @@ class TBTables { void insert(Key key, TBTable* wdl, TBTable* dtz) { uint32_t homeBucket = (uint32_t)key & (Size - 1); - Entry entry = std::make_tuple(key, wdl, dtz); + Entry entry{ key, wdl, dtz }; // Ensure last element is empty to avoid overflow when looking up for (uint32_t bucket = homeBucket; bucket < Size + Overflow - 1; ++bucket) { - Key otherKey = std::get(hashTable[bucket]); - if (otherKey == key || !std::get(hashTable[bucket])) { + Key otherKey = hashTable[bucket].key; + if (otherKey == key || !hashTable[bucket].get()) { hashTable[bucket] = entry; return; } @@ -430,7 +439,7 @@ class TBTables { // insert here and search for a new spot for the other element instead. uint32_t otherHomeBucket = (uint32_t)otherKey & (Size - 1); if (otherHomeBucket > homeBucket) { - swap(entry, hashTable[bucket]); + std::swap(entry, hashTable[bucket]); key = otherKey; homeBucket = otherHomeBucket; } @@ -443,8 +452,8 @@ public: template TBTable* get(Key key) { for (const Entry* entry = &hashTable[(uint32_t)key & (Size - 1)]; ; ++entry) { - if (std::get(*entry) == key || !std::get(*entry)) - return std::get(*entry); + if (entry->key == key || !entry->get()) + return entry->get(); } } @@ -521,7 +530,7 @@ int decompress_pairs(PairsData* d, uint64_t idx) { // I(k) = k * d->span + d->span / 2 (1) // First step is to get the 'k' of the I(k) nearest to our idx, using definition (1) - uint32_t k = idx / d->span; + uint32_t k = uint32_t(idx / d->span); // Then we read the corresponding SparseIndex[] entry uint32_t block = number(&d->sparseIndex[k].block); @@ -567,7 +576,7 @@ int decompress_pairs(PairsData* d, uint64_t idx) { // All the symbols of a given length are consecutive integers (numerical // sequence property), so we can compute the offset of our symbol of // length len, stored at the beginning of buf64. - sym = (buf64 - d->base64[len]) >> (64 - len - d->minSymLen); + sym = Sym((buf64 - d->base64[len]) >> (64 - len - d->minSymLen)); // Now add the value of the lowest symbol of length len to get our symbol sym += number(&d->lowestSym[len]); @@ -706,7 +715,7 @@ Ret do_probe_table(const Position& pos, T* entry, WDLScore wdl, ProbeState* resu std::swap(squares[0], *std::max_element(squares, squares + leadPawnsCnt, pawns_comp)); - tbFile = map_to_queenside(file_of(squares[0])); + tbFile = File(edge_distance(file_of(squares[0]))); } // DTZ tables are one-sided, i.e. they store positions only for white to @@ -743,7 +752,7 @@ Ret do_probe_table(const Position& pos, T* entry, WDLScore wdl, ProbeState* resu // the triangle A1-D1-D4. if (file_of(squares[0]) > FILE_D) for (int i = 0; i < size; ++i) - squares[i] ^= 7; // Horizontal flip: SQ_H1 -> SQ_A1 + squares[i] = flip_file(squares[i]); // Encode leading pawns starting with the one with minimum MapPawns[] and // proceeding in ascending order. @@ -762,7 +771,7 @@ Ret do_probe_table(const Position& pos, T* entry, WDLScore wdl, ProbeState* resu // piece is below RANK_5. if (rank_of(squares[0]) > RANK_4) for (int i = 0; i < size; ++i) - squares[i] ^= SQ_A8; // Vertical flip: SQ_A8 -> SQ_A1 + squares[i] = flip_rank(squares[i]); // Look for the first piece of the leading group not on the A1-D4 diagonal // and ensure it is mapped below the diagonal. @@ -770,7 +779,7 @@ Ret do_probe_table(const Position& pos, T* entry, WDLScore wdl, ProbeState* resu if (!off_A1H8(squares[i])) continue; - if (off_A1H8(squares[i]) > 0) // A1-H8 diagonal flip: SQ_A3 -> SQ_C3 + if (off_A1H8(squares[i]) > 0) // A1-H8 diagonal flip: SQ_A3 -> SQ_C1 for (int j = i; j < size; ++j) squares[j] = Square(((squares[j] >> 3) | (squares[j] << 3)) & 63); break; @@ -975,7 +984,7 @@ uint8_t* set_sizes(PairsData* d, uint8_t* data) { d->sizeofBlock = 1ULL << *data++; d->span = 1ULL << *data++; - d->sparseIndexSize = (tbSize + d->span - 1) / d->span; // Round up + d->sparseIndexSize = size_t((tbSize + d->span - 1) / d->span); // Round up auto padding = number(data++); d->blocksNum = number(data); data += sizeof(uint32_t); d->blockLengthSize = d->blocksNum + padding; // Padded to ensure SparseIndex[] @@ -1191,7 +1200,7 @@ WDLScore search(Position& pos, ProbeState* result) { auto moveList = MoveList(pos); size_t totalCount = moveList.size(), moveCount = 0; - for (const Move& move : moveList) + for (const Move move : moveList) { if ( !pos.capture(move) && (!CheckZeroingMoves || type_of(pos.moved_piece(move)) != PAWN)) @@ -1344,7 +1353,7 @@ void Tablebases::init(const std::string& paths) { if (leadPawnsCnt == 1) { MapPawns[sq] = availableSquares--; - MapPawns[sq ^ 7] = availableSquares--; // Horizontal flip + MapPawns[flip_file(sq)] = availableSquares--; } LeadPawnIdx[leadPawnsCnt][sq] = idx; idx += Binomial[leadPawnsCnt - 1][MapPawns[sq]]; @@ -1353,7 +1362,7 @@ void Tablebases::init(const std::string& paths) { LeadPawnsSize[leadPawnsCnt][f] = idx; } - // Add entries in TB tables if the corresponding ".rtbw" file exsists + // Add entries in TB tables if the corresponding ".rtbw" file exists for (PieceType p1 = PAWN; p1 < KING; ++p1) { TBTables.add({KING, p1, KING}); @@ -1460,7 +1469,7 @@ int Tablebases::probe_dtz(Position& pos, ProbeState* result) { StateInfo st; int minDTZ = 0xFFFF; - for (const Move& move : MoveList(pos)) + for (const Move move : MoveList(pos)) { bool zeroing = pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN; diff --git a/src/thread.cpp b/src/thread.cpp index 615d482c..a0ee2b25 100644 --- a/src/thread.cpp +++ b/src/thread.cpp @@ -52,9 +52,10 @@ Thread::~Thread() { stdThread.join(); } + /// Thread::bestMoveCount(Move move) return best move counter for the given root move -int Thread::best_move_count(Move move) { +int Thread::best_move_count(Move move) const { auto rm = std::find(rootMoves.begin() + pvIdx, rootMoves.begin() + pvLast, move); @@ -62,25 +63,27 @@ int Thread::best_move_count(Move move) { return rm != rootMoves.begin() + pvLast ? rm->bestMoveCount : 0; } + /// Thread::clear() reset histories, usually before a new game void Thread::clear() { counterMoves.fill(MOVE_NONE); mainHistory.fill(0); + lowPlyHistory.fill(0); captureHistory.fill(0); for (bool inCheck : { false, true }) - for (StatsType c : { NoCaptures, Captures }) - for (auto& to : continuationHistory[inCheck][c]) - for (auto& h : to) - h->fill(0); - - for (bool inCheck : { false, true }) - for (StatsType c : { NoCaptures, Captures }) - continuationHistory[inCheck][c][NO_PIECE][0]->fill(Search::CounterMovePruneThreshold - 1); + for (StatsType c : { NoCaptures, Captures }) + { + for (auto& to : continuationHistory[inCheck][c]) + for (auto& h : to) + h->fill(0); + continuationHistory[inCheck][c][NO_PIECE][0]->fill(Search::CounterMovePruneThreshold - 1); + } } + /// Thread::start_searching() wakes up the thread that will start the search void Thread::start_searching() { @@ -151,14 +154,15 @@ void ThreadPool::set(size_t requested) { clear(); // Reallocate the hash with the new threadpool size - TT.resize(Options["Hash"]); + TT.resize(size_t(Options["Hash"])); // Init thread number dependent search params. Search::init(); } } -/// ThreadPool::clear() sets threadPool data to initial values. + +/// ThreadPool::clear() sets threadPool data to initial values void ThreadPool::clear() { @@ -166,10 +170,11 @@ void ThreadPool::clear() { th->clear(); main()->callsCnt = 0; - main()->previousScore = VALUE_INFINITE; + main()->bestPreviousScore = VALUE_INFINITE; main()->previousTimeReduction = 1.0; } + /// ThreadPool::start_thinking() wakes up main thread waiting in idle_loop() and /// returns immediately. Main thread will wake up other threads and start the search. @@ -208,7 +213,7 @@ void ThreadPool::start_thinking(Position& pos, StateListPtr& states, for (Thread* th : *this) { - th->nodes = th->tbHits = th->nmpMinPly = 0; + th->nodes = th->tbHits = th->nmpMinPly = th->bestMoveChanges = 0; th->rootDepth = th->completedDepth = 0; th->rootMoves = rootMoves; th->rootPos.set(pos.fen(), pos.is_chess960(), &setupStates->back(), th); @@ -218,3 +223,54 @@ void ThreadPool::start_thinking(Position& pos, StateListPtr& states, main()->start_searching(); } + +Thread* ThreadPool::get_best_thread() const { + + Thread* bestThread = front(); + std::map votes; + Value minScore = VALUE_NONE; + + // Find minimum score of all threads + for (Thread* th: *this) + minScore = std::min(minScore, th->rootMoves[0].score); + + // Vote according to score and depth, and select the best thread + for (Thread* th : *this) + { + votes[th->rootMoves[0].pv[0]] += + (th->rootMoves[0].score - minScore + 14) * int(th->completedDepth); + + if (abs(bestThread->rootMoves[0].score) >= VALUE_TB_WIN_IN_MAX_PLY) + { + // Make sure we pick the shortest mate / TB conversion or stave off mate the longest + if (th->rootMoves[0].score > bestThread->rootMoves[0].score) + bestThread = th; + } + else if ( th->rootMoves[0].score >= VALUE_TB_WIN_IN_MAX_PLY + || ( th->rootMoves[0].score > VALUE_TB_LOSS_IN_MAX_PLY + && votes[th->rootMoves[0].pv[0]] > votes[bestThread->rootMoves[0].pv[0]])) + bestThread = th; + } + + return bestThread; +} + + +/// Start non-main threads + +void ThreadPool::start_searching() { + + for (Thread* th : *this) + if (th != front()) + th->start_searching(); +} + + +/// Wait for non-main threads + +void ThreadPool::wait_for_search_finished() const { + + for (Thread* th : *this) + if (th != front()) + th->wait_for_search_finished(); +} diff --git a/src/thread.h b/src/thread.h index aea86fd5..a69e1d10 100644 --- a/src/thread.h +++ b/src/thread.h @@ -56,7 +56,7 @@ public: void idle_loop(); void start_searching(); void wait_for_search_finished(); - int best_move_count(Move move); + int best_move_count(Move move) const; Pawns::Table pawnsTable; Material::Table materialTable; @@ -71,6 +71,7 @@ public: Depth rootDepth, completedDepth; CounterMoveHistory counterMoves; ButterflyHistory mainHistory; + LowPlyHistory lowPlyHistory; CapturePieceToHistory captureHistory; ContinuationHistory continuationHistory[2][2]; Score contempt; @@ -87,7 +88,7 @@ struct MainThread : public Thread { void check_time(); double previousTimeReduction; - Value previousScore; + Value bestPreviousScore; Value iterValue[4]; int callsCnt; bool stopOnPonderhit; @@ -108,6 +109,9 @@ struct ThreadPool : public std::vector { MainThread* main() const { return static_cast(front()); } uint64_t nodes_searched() const { return accumulate(&Thread::nodes); } uint64_t tb_hits() const { return accumulate(&Thread::tbHits); } + Thread* get_best_thread() const; + void start_searching(); + void wait_for_search_finished() const; std::atomic_bool stop, increaseDepth; diff --git a/src/timeman.cpp b/src/timeman.cpp index 0848be42..546eadd2 100644 --- a/src/timeman.cpp +++ b/src/timeman.cpp @@ -28,66 +28,21 @@ TimeManagement Time; // Our global time management object -namespace { - enum TimeType { OptimumTime, MaxTime }; - - constexpr int MoveHorizon = 50; // Plan time management at most this many moves ahead - constexpr double MaxRatio = 7.3; // When in trouble, we can step over reserved time with this ratio - constexpr double StealRatio = 0.34; // However we must not steal time from remaining moves over this ratio - - - // move_importance() is a skew-logistic function based on naive statistical - // analysis of "how many games are still undecided after n half-moves". Game - // is considered "undecided" as long as neither side has >275cp advantage. - // Data was extracted from the CCRL game database with some simple filtering criteria. - - double move_importance(int ply) { - - constexpr double XScale = 6.85; - constexpr double XShift = 64.5; - constexpr double Skew = 0.171; - - return pow((1 + exp((ply - XShift) / XScale)), -Skew) + DBL_MIN; // Ensure non-zero - } - - template - TimePoint remaining(TimePoint myTime, int movesToGo, int ply, TimePoint slowMover) { - - constexpr double TMaxRatio = (T == OptimumTime ? 1.0 : MaxRatio); - constexpr double TStealRatio = (T == OptimumTime ? 0.0 : StealRatio); - - double moveImportance = (move_importance(ply) * slowMover) / 100.0; - double otherMovesImportance = 0.0; - - for (int i = 1; i < movesToGo; ++i) - otherMovesImportance += move_importance(ply + 2 * i); - - double ratio1 = (TMaxRatio * moveImportance) / (TMaxRatio * moveImportance + otherMovesImportance); - double ratio2 = (moveImportance + TStealRatio * otherMovesImportance) / (moveImportance + otherMovesImportance); - - return TimePoint(myTime * std::min(ratio1, ratio2)); // Intel C++ asks for an explicit cast - } - -} // namespace - - -/// init() is called at the beginning of the search and calculates the allowed -/// thinking time out of the time control and current game ply. We support four -/// different kinds of time controls, passed in 'limits': -/// -/// inc == 0 && movestogo == 0 means: x basetime [sudden death!] -/// inc == 0 && movestogo != 0 means: x moves in y minutes -/// inc > 0 && movestogo == 0 means: x basetime + z increment -/// inc > 0 && movestogo != 0 means: x moves in y minutes + z increment +/// TimeManagement::init() is called at the beginning of the search and calculates +/// the bounds of time allowed for the current game ply. We currently support: +// 1) x basetime (+ z increment) +// 2) x moves in y seconds (+ z increment) void TimeManagement::init(Search::LimitsType& limits, Color us, int ply) { - TimePoint minThinkingTime = Options["Minimum Thinking Time"]; - TimePoint moveOverhead = Options["Move Overhead"]; - TimePoint slowMover = Options["Slow Mover"]; - TimePoint npmsec = Options["nodestime"]; - TimePoint hypMyTime; + TimePoint moveOverhead = TimePoint(Options["Move Overhead"]); + TimePoint slowMover = TimePoint(Options["Slow Mover"]); + TimePoint npmsec = TimePoint(Options["nodestime"]); + + // opt_scale is a percentage of available time to use for the current move. + // max_scale is a multiplier applied to optimumTime. + double opt_scale, max_scale; // If we have to play in 'nodes as time' mode, then convert from time // to nodes, and use resulting values in time management formulas. @@ -105,29 +60,40 @@ void TimeManagement::init(Search::LimitsType& limits, Color us, int ply) { } startTime = limits.startTime; - optimumTime = maximumTime = std::max(limits.time[us], minThinkingTime); - const int maxMTG = limits.movestogo ? std::min(limits.movestogo, MoveHorizon) : MoveHorizon; + // Maximum move horizon of 50 moves + int mtg = limits.movestogo ? std::min(limits.movestogo, 50) : 50; - // We calculate optimum time usage for different hypothetical "moves to go" values - // and choose the minimum of calculated search time values. Usually the greatest - // hypMTG gives the minimum values. - for (int hypMTG = 1; hypMTG <= maxMTG; ++hypMTG) - { - // Calculate thinking time for hypothetical "moves to go"-value - hypMyTime = limits.time[us] - + limits.inc[us] * (hypMTG - 1) - - moveOverhead * (2 + std::min(hypMTG, 40)); + // Make sure timeLeft is > 0 since we may use it as a divisor + TimePoint timeLeft = std::max(TimePoint(1), + limits.time[us] + limits.inc[us] * (mtg - 1) - moveOverhead * (2 + mtg)); - hypMyTime = std::max(hypMyTime, TimePoint(0)); + // A user may scale time usage by setting UCI option "Slow Mover" + // Default is 100 and changing this value will probably lose elo. + timeLeft = slowMover * timeLeft / 100; - TimePoint t1 = minThinkingTime + remaining(hypMyTime, hypMTG, ply, slowMover); - TimePoint t2 = minThinkingTime + remaining(hypMyTime, hypMTG, ply, slowMover); + // x basetime (+ z increment) + // If there is a healthy increment, timeLeft can exceed actual available + // game time for the current move, so also cap to 20% of available game time. + if (limits.movestogo == 0) + { + opt_scale = std::min(0.008 + std::pow(ply + 3.0, 0.5) / 250.0, + 0.2 * limits.time[us] / double(timeLeft)); + max_scale = std::min(7.0, 4.0 + ply / 12.0); + } - optimumTime = std::min(t1, optimumTime); - maximumTime = std::min(t2, maximumTime); + // x moves in y seconds (+ z increment) + else + { + opt_scale = std::min((0.8 + ply / 128.0) / mtg, + 0.8 * limits.time[us] / double(timeLeft)); + max_scale = std::min(6.3, 1.5 + 0.11 * mtg); } + // Never use more than 80% of the available time for this move + optimumTime = TimePoint(opt_scale * timeLeft); + maximumTime = TimePoint(std::min(0.8 * limits.time[us] - moveOverhead, max_scale * optimumTime)); + if (Options["Ponder"]) optimumTime += optimumTime / 4; } diff --git a/src/tt.cpp b/src/tt.cpp index 0b4a59de..34590903 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -30,23 +30,23 @@ TranspositionTable TT; // Our global transposition table -/// TTEntry::save populates the TTEntry with a new node's data, possibly +/// TTEntry::save() populates the TTEntry with a new node's data, possibly /// overwriting an old position. Update is not atomic and can be racy. void TTEntry::save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev) { // Preserve any existing move for the same position - if (m || (k >> 48) != key16) + if (m || (uint16_t)k != key16) move16 = (uint16_t)m; // Overwrite less valuable entries - if ( (k >> 48) != key16 + if ((uint16_t)k != key16 || d - DEPTH_OFFSET > depth8 - 4 || b == BOUND_EXACT) { assert(d >= DEPTH_OFFSET); - key16 = (uint16_t)(k >> 48); + key16 = (uint16_t)k; value16 = (int16_t)v; eval16 = (int16_t)ev; genBound8 = (uint8_t)(TT.generation8 | uint8_t(pv) << 2 | b); @@ -63,11 +63,10 @@ void TranspositionTable::resize(size_t mbSize) { Threads.main()->wait_for_search_finished(); - clusterCount = mbSize * 1024 * 1024 / sizeof(Cluster); - - free(mem); - mem = malloc(clusterCount * sizeof(Cluster) + CacheLineSize - 1); + aligned_ttmem_free(mem); + clusterCount = mbSize * 1024 * 1024 / sizeof(Cluster); + table = static_cast(aligned_ttmem_alloc(clusterCount * sizeof(Cluster), mem)); if (!mem) { std::cerr << "Failed to allocate " << mbSize @@ -75,7 +74,6 @@ void TranspositionTable::resize(size_t mbSize) { exit(EXIT_FAILURE); } - table = (Cluster*)((uintptr_t(mem) + CacheLineSize - 1) & ~(CacheLineSize - 1)); clear(); } @@ -96,8 +94,8 @@ void TranspositionTable::clear() { WinProcGroup::bindThisThread(idx); // Each thread will zero its part of the hash table - const size_t stride = clusterCount / Options["Threads"], - start = stride * idx, + const size_t stride = size_t(clusterCount / Options["Threads"]), + start = size_t(stride * idx), len = idx != Options["Threads"] - 1 ? stride : clusterCount - start; @@ -105,10 +103,11 @@ void TranspositionTable::clear() { }); } - for (std::thread& th: threads) + for (std::thread& th : threads) th.join(); } + /// TranspositionTable::probe() looks up the current position in the transposition /// table. It returns true and a pointer to the TTEntry if the position is found. /// Otherwise, it returns false and a pointer to an empty or least valuable TTEntry @@ -119,7 +118,7 @@ void TranspositionTable::clear() { TTEntry* TranspositionTable::probe(const Key key, bool& found) const { TTEntry* const tte = first_entry(key); - const uint16_t key16 = key >> 48; // Use the high 16 bits as key inside the cluster + const uint16_t key16 = (uint16_t)key; // Use the low 16 bits as key inside the cluster for (int i = 0; i < ClusterSize; ++i) if (!tte[i].key16 || tte[i].key16 == key16) @@ -150,9 +149,9 @@ TTEntry* TranspositionTable::probe(const Key key, bool& found) const { int TranspositionTable::hashfull() const { int cnt = 0; - for (int i = 0; i < 1000 / ClusterSize; ++i) + for (int i = 0; i < 1000; ++i) for (int j = 0; j < ClusterSize; ++j) cnt += (table[i].entry[j].genBound8 & 0xF8) == generation8; - return cnt * 1000 / (ClusterSize * (1000 / ClusterSize)); + return cnt / ClusterSize; } diff --git a/src/tt.h b/src/tt.h index 98b054d3..e18db8ce 100644 --- a/src/tt.h +++ b/src/tt.h @@ -41,7 +41,7 @@ struct TTEntry { Value value() const { return (Value)value16; } Value eval() const { return (Value)eval16; } Depth depth() const { return (Depth)depth8 + DEPTH_OFFSET; } - bool is_pv() const { return (bool)(genBound8 & 0x4); } + bool is_pv() const { return (bool)(genBound8 & 0x4); } Bound bound() const { return (Bound)(genBound8 & 0x3); } void save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev); @@ -57,36 +57,33 @@ private: }; -/// A TranspositionTable consists of a power of 2 number of clusters and each -/// cluster consists of ClusterSize number of TTEntry. Each non-empty entry -/// contains information of exactly one position. The size of a cluster should -/// divide the size of a cache line size, to ensure that clusters never cross -/// cache lines. This ensures best cache performance, as the cacheline is -/// prefetched, as soon as possible. +/// A TranspositionTable is an array of Cluster, of size clusterCount. Each +/// cluster consists of ClusterSize number of TTEntry. Each non-empty TTEntry +/// contains information on exactly one position. The size of a Cluster should +/// divide the size of a cache line for best performance, as the cacheline is +/// prefetched when possible. class TranspositionTable { - static constexpr int CacheLineSize = 64; static constexpr int ClusterSize = 3; struct Cluster { TTEntry entry[ClusterSize]; - char padding[2]; // Align to a divisor of the cache line size + char padding[2]; // Pad to 32 bytes }; - static_assert(CacheLineSize % sizeof(Cluster) == 0, "Cluster size incorrect"); + static_assert(sizeof(Cluster) == 32, "Unexpected Cluster size"); public: - ~TranspositionTable() { free(mem); } + ~TranspositionTable() { aligned_ttmem_free(mem); } void new_search() { generation8 += 8; } // Lower 3 bits are used by PV flag and Bound TTEntry* probe(const Key key, bool& found) const; int hashfull() const; void resize(size_t mbSize); void clear(); - // The 32 lowest order bits of the key are used to get the index of the cluster TTEntry* first_entry(const Key key) const { - return &table[(uint32_t(key) * uint64_t(clusterCount)) >> 32].entry[0]; + return &table[mul_hi64(key, clusterCount)].entry[0]; } private: diff --git a/src/tune.cpp b/src/tune.cpp new file mode 100644 index 00000000..c1b1c76b --- /dev/null +++ b/src/tune.cpp @@ -0,0 +1,146 @@ +/* + Stockfish, a UCI chess playing engine derived from Glaurung 2.1 + Copyright (C) 2004-2008 Tord Romstad (Glaurung author) + Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2015-2020 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad + + Stockfish is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + Stockfish is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#include +#include +#include + +#include "types.h" +#include "misc.h" +#include "uci.h" + +using std::string; + +bool Tune::update_on_last; +const UCI::Option* LastOption = nullptr; +BoolConditions Conditions; +static std::map TuneResults; + +string Tune::next(string& names, bool pop) { + + string name; + + do { + string token = names.substr(0, names.find(',')); + + if (pop) + names.erase(0, token.size() + 1); + + std::stringstream ws(token); + name += (ws >> token, token); // Remove trailing whitespace + + } while ( std::count(name.begin(), name.end(), '(') + - std::count(name.begin(), name.end(), ')')); + + return name; +} + +static void on_tune(const UCI::Option& o) { + + if (!Tune::update_on_last || LastOption == &o) + Tune::read_options(); +} + +static void make_option(const string& n, int v, const SetRange& r) { + + // Do not generate option when there is nothing to tune (ie. min = max) + if (r(v).first == r(v).second) + return; + + if (TuneResults.count(n)) + v = TuneResults[n]; + + Options[n] << UCI::Option(v, r(v).first, r(v).second, on_tune); + LastOption = &Options[n]; + + // Print formatted parameters, ready to be copy-pasted in Fishtest + std::cout << n << "," + << v << "," + << r(v).first << "," << r(v).second << "," + << (r(v).second - r(v).first) / 20.0 << "," + << "0.0020" + << std::endl; +} + +template<> void Tune::Entry::init_option() { make_option(name, value, range); } + +template<> void Tune::Entry::read_option() { + if (Options.count(name)) + value = int(Options[name]); +} + +template<> void Tune::Entry::init_option() { make_option(name, value, range); } + +template<> void Tune::Entry::read_option() { + if (Options.count(name)) + value = Value(int(Options[name])); +} + +template<> void Tune::Entry::init_option() { + make_option("m" + name, mg_value(value), range); + make_option("e" + name, eg_value(value), range); +} + +template<> void Tune::Entry::read_option() { + if (Options.count("m" + name)) + value = make_score(int(Options["m" + name]), eg_value(value)); + + if (Options.count("e" + name)) + value = make_score(mg_value(value), int(Options["e" + name])); +} + +// Instead of a variable here we have a PostUpdate function: just call it +template<> void Tune::Entry::init_option() {} +template<> void Tune::Entry::read_option() { value(); } + + +// Set binary conditions according to a probability that depends +// on the corresponding parameter value. + +void BoolConditions::set() { + + static PRNG rng(now()); + static bool startup = true; // To workaround fishtest bench + + for (size_t i = 0; i < binary.size(); i++) + binary[i] = !startup && (values[i] + int(rng.rand() % variance) > threshold); + + startup = false; + + for (size_t i = 0; i < binary.size(); i++) + sync_cout << binary[i] << sync_endl; +} + + +// Init options with tuning session results instead of default values. Useful to +// get correct bench signature after a tuning session or to test tuned values. +// Just copy fishtest tuning results in a result.txt file and extract the +// values with: +// +// cat results.txt | sed 's/^param: \([^,]*\), best: \([^,]*\).*/ TuneResults["\1"] = int(round(\2));/' +// +// Then paste the output below, as the function body + +#include + +void Tune::read_results() { + + /* ...insert your values here... */ +} diff --git a/src/tune.h b/src/tune.h new file mode 100644 index 00000000..27c3f961 --- /dev/null +++ b/src/tune.h @@ -0,0 +1,195 @@ +/* + Stockfish, a UCI chess playing engine derived from Glaurung 2.1 + Copyright (C) 2004-2008 Tord Romstad (Glaurung author) + Copyright (C) 2008-2017 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2015-2018 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad + + Stockfish is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + Stockfish is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#ifndef TUNE_H_INCLUDED +#define TUNE_H_INCLUDED + +#include +#include +#include +#include + +typedef std::pair Range; // Option's min-max values +typedef Range (RangeFun) (int); + +// Default Range function, to calculate Option's min-max values +inline Range default_range(int v) { + return v > 0 ? Range(0, 2 * v) : Range(2 * v, 0); +} + +struct SetRange { + explicit SetRange(RangeFun f) : fun(f) {} + SetRange(int min, int max) : fun(nullptr), range(min, max) {} + Range operator()(int v) const { return fun ? fun(v) : range; } + + RangeFun* fun; + Range range; +}; + +#define SetDefaultRange SetRange(default_range) + + +/// BoolConditions struct is used to tune boolean conditions in the +/// code by toggling them on/off according to a probability that +/// depends on the value of a tuned integer parameter: for high +/// values of the parameter condition is always disabled, for low +/// values is always enabled, otherwise it is enabled with a given +/// probability that depnends on the parameter under tuning. + +struct BoolConditions { + void init(size_t size) { values.resize(size, defaultValue), binary.resize(size, 0); } + void set(); + + std::vector binary, values; + int defaultValue = 465, variance = 40, threshold = 500; + SetRange range = SetRange(0, 1000); +}; + +extern BoolConditions Conditions; + +inline void set_conditions() { Conditions.set(); } + + +/// Tune class implements the 'magic' code that makes the setup of a fishtest +/// tuning session as easy as it can be. Mainly you have just to remove const +/// qualifiers from the variables you want to tune and flag them for tuning, so +/// if you have: +/// +/// const Score myScore = S(10, 15); +/// const Value myValue[][2] = { { V(100), V(20) }, { V(7), V(78) } }; +/// +/// If you have a my_post_update() function to run after values have been updated, +/// and a my_range() function to set custom Option's min-max values, then you just +/// remove the 'const' qualifiers and write somewhere below in the file: +/// +/// TUNE(SetRange(my_range), myScore, myValue, my_post_update); +/// +/// You can also set the range directly, and restore the default at the end +/// +/// TUNE(SetRange(-100, 100), myScore, SetDefaultRange); +/// +/// In case update function is slow and you have many parameters, you can add: +/// +/// UPDATE_ON_LAST(); +/// +/// And the values update, including post update function call, will be done only +/// once, after the engine receives the last UCI option, that is the one defined +/// and created as the last one, so the GUI should send the options in the same +/// order in which have been defined. + +class Tune { + + typedef void (PostUpdate) (); // Post-update function + + Tune() { read_results(); } + Tune(const Tune&) = delete; + void operator=(const Tune&) = delete; + void read_results(); + + static Tune& instance() { static Tune t; return t; } // Singleton + + // Use polymorphism to accomodate Entry of different types in the same vector + struct EntryBase { + virtual ~EntryBase() = default; + virtual void init_option() = 0; + virtual void read_option() = 0; + }; + + template + struct Entry : public EntryBase { + + static_assert(!std::is_const::value, "Parameter cannot be const!"); + + static_assert( std::is_same::value + || std::is_same::value + || std::is_same::value + || std::is_same::value, "Parameter type not supported!"); + + Entry(const std::string& n, T& v, const SetRange& r) : name(n), value(v), range(r) {} + void operator=(const Entry&) = delete; // Because 'value' is a reference + void init_option() override; + void read_option() override; + + std::string name; + T& value; + SetRange range; + }; + + // Our facilty to fill the container, each Entry corresponds to a parameter to tune. + // We use variadic templates to deal with an unspecified number of entries, each one + // of a possible different type. + static std::string next(std::string& names, bool pop = true); + + int add(const SetRange&, std::string&&) { return 0; } + + template + int add(const SetRange& range, std::string&& names, T& value, Args&&... args) { + list.push_back(std::unique_ptr(new Entry(next(names), value, range))); + return add(range, std::move(names), args...); + } + + // Template specialization for arrays: recursively handle multi-dimensional arrays + template + int add(const SetRange& range, std::string&& names, T (&value)[N], Args&&... args) { + for (size_t i = 0; i < N; i++) + add(range, next(names, i == N - 1) + "[" + std::to_string(i) + "]", value[i]); + return add(range, std::move(names), args...); + } + + // Template specialization for SetRange + template + int add(const SetRange&, std::string&& names, SetRange& value, Args&&... args) { + return add(value, (next(names), std::move(names)), args...); + } + + // Template specialization for BoolConditions + template + int add(const SetRange& range, std::string&& names, BoolConditions& cond, Args&&... args) { + for (size_t size = cond.values.size(), i = 0; i < size; i++) + add(cond.range, next(names, i == size - 1) + "_" + std::to_string(i), cond.values[i]); + return add(range, std::move(names), args...); + } + + std::vector> list; + +public: + template + static int add(const std::string& names, Args&&... args) { + return instance().add(SetDefaultRange, names.substr(1, names.size() - 2), args...); // Remove trailing parenthesis + } + static void init() { for (auto& e : instance().list) e->init_option(); read_options(); } // Deferred, due to UCI::Options access + static void read_options() { for (auto& e : instance().list) e->read_option(); } + static bool update_on_last; +}; + +// Some macro magic :-) we define a dummy int variable that compiler initializes calling Tune::add() +#define STRINGIFY(x) #x +#define UNIQUE2(x, y) x ## y +#define UNIQUE(x, y) UNIQUE2(x, y) // Two indirection levels to expand __LINE__ +#define TUNE(...) int UNIQUE(p, __LINE__) = Tune::add(STRINGIFY((__VA_ARGS__)), __VA_ARGS__) + +#define UPDATE_ON_LAST() bool UNIQUE(p, __LINE__) = Tune::update_on_last = true + +// Some macro to tune toggling of boolean conditions +#define CONDITION(x) (Conditions.binary[__COUNTER__] || (x)) +#define TUNE_CONDITIONS() int UNIQUE(c, __LINE__) = (Conditions.init(__COUNTER__), 0); \ + TUNE(Conditions, set_conditions) + +#endif // #ifndef TUNE_H_INCLUDED diff --git a/src/types.h b/src/types.h index 902c2cfc..c1598561 100644 --- a/src/types.h +++ b/src/types.h @@ -40,7 +40,6 @@ #include #include -#include #include #include #include @@ -176,14 +175,17 @@ enum Value : int { VALUE_INFINITE = 32001, VALUE_NONE = 32002, - VALUE_MATE_IN_MAX_PLY = VALUE_MATE - 2 * MAX_PLY, - VALUE_MATED_IN_MAX_PLY = -VALUE_MATE + 2 * MAX_PLY, + VALUE_TB_WIN_IN_MAX_PLY = VALUE_MATE - 2 * MAX_PLY, + VALUE_TB_LOSS_IN_MAX_PLY = -VALUE_TB_WIN_IN_MAX_PLY, + VALUE_MATE_IN_MAX_PLY = VALUE_MATE - MAX_PLY, + VALUE_MATED_IN_MAX_PLY = -VALUE_MATE_IN_MAX_PLY, - PawnValueMg = 128, PawnValueEg = 213, + PawnValueMg = 124, PawnValueEg = 206, KnightValueMg = 781, KnightValueEg = 854, BishopValueMg = 825, BishopValueEg = 915, RookValueMg = 1276, RookValueEg = 1380, QueenValueMg = 2538, QueenValueEg = 2682, + Tempo = 28, MidgameLimit = 15258, EndgameLimit = 3915 }; @@ -201,18 +203,22 @@ enum Piece { PIECE_NB = 16 }; -extern Value PieceValue[PHASE_NB][PIECE_NB]; +constexpr Value PieceValue[PHASE_NB][PIECE_NB] = { + { VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg, VALUE_ZERO, VALUE_ZERO, + VALUE_ZERO, PawnValueMg, KnightValueMg, BishopValueMg, RookValueMg, QueenValueMg, VALUE_ZERO, VALUE_ZERO }, + { VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg, VALUE_ZERO, VALUE_ZERO, + VALUE_ZERO, PawnValueEg, KnightValueEg, BishopValueEg, RookValueEg, QueenValueEg, VALUE_ZERO, VALUE_ZERO } +}; typedef int Depth; enum : int { - DEPTH_QS_CHECKS = 0, DEPTH_QS_NO_CHECKS = -1, DEPTH_QS_RECAPTURES = -5, DEPTH_NONE = -6, - DEPTH_OFFSET = DEPTH_NONE, + DEPTH_OFFSET = DEPTH_NONE }; enum Square : int { @@ -274,11 +280,11 @@ inline Value mg_value(Score s) { } #define ENABLE_BASE_OPERATORS_ON(T) \ -constexpr T operator+(T d1, T d2) { return T(int(d1) + int(d2)); } \ -constexpr T operator-(T d1, T d2) { return T(int(d1) - int(d2)); } \ +constexpr T operator+(T d1, int d2) { return T(int(d1) + d2); } \ +constexpr T operator-(T d1, int d2) { return T(int(d1) - d2); } \ constexpr T operator-(T d) { return T(-int(d)); } \ -inline T& operator+=(T& d1, T d2) { return d1 = d1 + d2; } \ -inline T& operator-=(T& d1, T d2) { return d1 = d1 - d2; } +inline T& operator+=(T& d1, int d2) { return d1 = d1 + d2; } \ +inline T& operator-=(T& d1, int d2) { return d1 = d1 - d2; } #define ENABLE_INCR_OPERATORS_ON(T) \ inline T& operator++(T& d) { return d = T(int(d) + 1); } \ @@ -297,7 +303,6 @@ ENABLE_FULL_OPERATORS_ON(Value) ENABLE_FULL_OPERATORS_ON(Direction) ENABLE_INCR_OPERATORS_ON(PieceType) -ENABLE_INCR_OPERATORS_ON(Piece) ENABLE_INCR_OPERATORS_ON(Square) ENABLE_INCR_OPERATORS_ON(File) ENABLE_INCR_OPERATORS_ON(Rank) @@ -308,12 +313,6 @@ ENABLE_BASE_OPERATORS_ON(Score) #undef ENABLE_INCR_OPERATORS_ON #undef ENABLE_BASE_OPERATORS_ON -/// Additional operators to add integers to a Value -constexpr Value operator+(Value v, int i) { return Value(int(v) + i); } -constexpr Value operator-(Value v, int i) { return Value(int(v) - i); } -inline Value& operator+=(Value& v, int i) { return v = v + i; } -inline Value& operator-=(Value& v, int i) { return v = v - i; } - /// Additional operators to add a Direction to a Square constexpr Square operator+(Square s, Direction d) { return Square(int(s) + int(d)); } constexpr Square operator-(Square s, Direction d) { return Square(int(s) - int(d)); } @@ -343,23 +342,23 @@ inline Score operator*(Score s, int i) { /// Multiplication of a Score by a boolean inline Score operator*(Score s, bool b) { - return Score(int(s) * int(b)); + return b ? s : SCORE_ZERO; } constexpr Color operator~(Color c) { return Color(c ^ BLACK); // Toggle color } -constexpr Square operator~(Square s) { - return Square(s ^ SQ_A8); // Vertical flip SQ_A1 -> SQ_A8 +constexpr Square flip_rank(Square s) { // Swap A1 <-> A8 + return Square(s ^ SQ_A8); } -constexpr Piece operator~(Piece pc) { - return Piece(pc ^ 8); // Swap color of piece B_KNIGHT -> W_KNIGHT +constexpr Square flip_file(Square s) { // Swap A1 <-> H1 + return Square(s ^ SQ_H1); } -inline File map_to_queenside(File f) { - return std::min(f, File(FILE_H - f)); // Map files ABCDEFGH to files ABCDDCBA +constexpr Piece operator~(Piece pc) { + return Piece(pc ^ 8); // Swap color of piece B_KNIGHT <-> W_KNIGHT } constexpr CastlingRights operator&(Color c, CastlingRights cr) { @@ -456,4 +455,11 @@ constexpr bool is_ok(Move m) { return from_sq(m) != to_sq(m); // Catch MOVE_NULL and MOVE_NONE } +/// Based on a congruential pseudo random number generator +constexpr Key make_key(uint64_t seed) { + return seed * 6364136223846793005ULL + 1442695040888963407ULL; +} + #endif // #ifndef TYPES_H_INCLUDED + +#include "tune.h" // Global visibility to tuning setup diff --git a/src/uci.cpp b/src/uci.cpp index 8b35e6fd..bb57c80b 100644 --- a/src/uci.cpp +++ b/src/uci.cpp @@ -19,6 +19,7 @@ */ #include +#include #include #include #include @@ -115,7 +116,7 @@ namespace { limits.startTime = now(); // As early as possible! while (is >> token) - if (token == "searchmoves") + if (token == "searchmoves") // Needs to be the last command on the line while (is >> token) limits.searchmoves.push_back(UCI::to_move(pos, token)); @@ -182,6 +183,28 @@ namespace { << "\nNodes/second : " << 1000 * nodes / elapsed << endl; } + // The win rate model returns the probability (per mille) of winning given an eval + // and a game-ply. The model fits rather accurately the LTC fishtest statistics. + int win_rate_model(Value v, int ply) { + + // The model captures only up to 240 plies, so limit input (and rescale) + double m = std::min(240, ply) / 64.0; + + // Coefficients of a 3rd order polynomial fit based on fishtest data + // for two parameters needed to transform eval to the argument of a + // logistic function. + double as[] = {-8.24404295, 64.23892342, -95.73056462, 153.86478679}; + double bs[] = {-3.37154371, 28.44489198, -56.67657741, 72.05858751}; + double a = (((as[0] * m + as[1]) * m + as[2]) * m) + as[3]; + double b = (((bs[0] * m + bs[1]) * m + bs[2]) * m) + bs[3]; + + // Transform eval to centipawns with limited range + double x = Utility::clamp(double(100 * v) / PawnValueEg, -1000.0, 1000.0); + + // Return win rate in per mille (rounded to nearest) + return int(0.5 + 1000 / (1 + std::exp((a - x) / b))); + } + } // namespace @@ -260,7 +283,7 @@ string UCI::value(Value v) { stringstream ss; - if (abs(v) < VALUE_MATE - MAX_PLY) + if (abs(v) < VALUE_MATE_IN_MAX_PLY) ss << "cp " << v * 100 / PawnValueEg; else ss << "mate " << (v > 0 ? VALUE_MATE - v + 1 : -VALUE_MATE - v) / 2; @@ -269,6 +292,22 @@ string UCI::value(Value v) { } +/// UCI::wdl() report WDL statistics given an evaluation and a game ply, based on +/// data gathered for fishtest LTC games. + +string UCI::wdl(Value v, int ply) { + + stringstream ss; + + int wdl_w = win_rate_model( v, ply); + int wdl_l = win_rate_model(-v, ply); + int wdl_d = 1000 - wdl_w - wdl_l; + ss << " wdl " << wdl_w << " " << wdl_d << " " << wdl_l; + + return ss.str(); +} + + /// UCI::square() converts a Square to a string in algebraic notation (g1, a7, etc.) std::string UCI::square(Square s) { diff --git a/src/uci.h b/src/uci.h index b845889b..ad954d9f 100644 --- a/src/uci.h +++ b/src/uci.h @@ -73,6 +73,7 @@ std::string value(Value v); std::string square(Square s); std::string move(Move m, bool chess960); std::string pv(const Position& pos, Depth depth, Value alpha, Value beta); +std::string wdl(Value v, int ply); Move to_move(const Position& pos, std::string& str); } // namespace UCI diff --git a/src/ucioption.cpp b/src/ucioption.cpp index 78e3d465..5982f26a 100644 --- a/src/ucioption.cpp +++ b/src/ucioption.cpp @@ -40,9 +40,9 @@ namespace UCI { /// 'On change' actions, triggered by an option's value change void on_clear_hash(const Option&) { Search::clear(); } -void on_hash_size(const Option& o) { TT.resize(o); } +void on_hash_size(const Option& o) { TT.resize(size_t(o)); } void on_logger(const Option& o) { start_logger(o); } -void on_threads(const Option& o) { Threads.set(o); } +void on_threads(const Option& o) { Threads.set(size_t(o)); } void on_tb_path(const Option& o) { Tablebases::init(o); } void on_rpc_server_address(const Option& o) { if (hash_probe_thread) { @@ -60,12 +60,11 @@ bool CaseInsensitiveLess::operator() (const string& s1, const string& s2) const } -/// init() initializes the UCI options to their hard-coded default values +/// UCI::init() initializes the UCI options to their hard-coded default values void init(OptionsMap& o) { - // at most 2^32 clusters. - constexpr int MaxHashMB = Is64Bit ? 131072 : 2048; + constexpr int MaxHashMB = Is64Bit ? 33554432 : 2048; o["Debug Log File"] << Option("", on_logger); o["Contempt"] << Option(24, -100, 100); @@ -76,14 +75,14 @@ void init(OptionsMap& o) { o["Ponder"] << Option(false); o["MultiPV"] << Option(1, 1, 500); o["Skill Level"] << Option(20, 0, 20); - o["Move Overhead"] << Option(30, 0, 5000); - o["Minimum Thinking Time"] << Option(20, 0, 5000); - o["Slow Mover"] << Option(84, 10, 1000); + o["Move Overhead"] << Option(10, 0, 5000); + o["Slow Mover"] << Option(100, 10, 1000); o["nodestime"] << Option(0, 0, 10000); o["UCI_Chess960"] << Option(false); o["UCI_AnalyseMode"] << Option(false); o["UCI_LimitStrength"] << Option(false); o["UCI_Elo"] << Option(1350, 1350, 2850); + o["UCI_ShowWDL"] << Option(false); o["SyzygyPath"] << Option("", on_tb_path); o["SyzygyProbeDepth"] << Option(1, 1, 100); o["Syzygy50MoveRule"] << Option(true);