From: Steinar H. Gunderson Date: Mon, 12 Aug 2019 17:27:15 +0000 (+0200) Subject: Merge remote-tracking branch 'upstream/master' X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=d4062bbfa6c71e23fc6fb3f04e043409e8e41df7;hp=ca6ce6398b1bd21ff2ac29b2dc27d7c25abbb509 Merge remote-tracking branch 'upstream/master' --- diff --git a/Readme.md b/Readme.md index bc058dbc..10ffdeae 100644 --- a/Readme.md +++ b/Readme.md @@ -1,7 +1,7 @@ ## Overview [![Build Status](https://travis-ci.org/official-stockfish/Stockfish.svg?branch=master)](https://travis-ci.org/official-stockfish/Stockfish) -[![Build Status](https://ci.appveyor.com/api/projects/status/github/official-stockfish/Stockfish?svg=true)](https://ci.appveyor.com/project/mcostalba/stockfish) +[![Build Status](https://ci.appveyor.com/api/projects/status/github/official-stockfish/Stockfish?branch=master&svg=true)](https://ci.appveyor.com/project/mcostalba/stockfish/branch/master) [Stockfish](https://stockfishchess.org) is a free, powerful UCI chess engine derived from Glaurung 2.1. It is not a complete chess program and requires a @@ -34,11 +34,11 @@ Currently, Stockfish has the following UCI options: A positive value for contempt favors middle game positions and avoids draws. * #### Analysis Contempt - By default, contempt is set to prefer the side to move. Set this option to "White" + By default, contempt is set to prefer the side to move. Set this option to "White" or "Black" to analyse with contempt for that side, or "Off" to disable contempt. * #### Threads - The number of CPU threads used for searching a position. For best performance, set + The number of CPU threads used for searching a position. For best performance, set this equal to the number of CPU cores available. * #### Hash @@ -55,21 +55,30 @@ Currently, Stockfish has the following UCI options: Leave at 1 for best performance. * #### Skill Level - Lower the Skill Level in order to make Stockfish play weaker. + Lower the Skill Level in order to make Stockfish play weaker (see also UCI_LimitStrength). + Internally, MultiPV is enabled, and with a certain probability depending on the Skill Level a + weaker move will be played. + + * #### UCI_LimitStrength + Enable weaker play aiming for an Elo rating as set by UCI_Elo. This option overrides Skill Level. + + * #### UCI_Elo + 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. * #### Move Overhead - Assume a time delay of x ms due to network and GUI overheads. This is useful to + 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. + Search for at least x ms per move. * #### Slow Mover - Lower values will make Stockfish take less time in games, higher values will + Lower values will make Stockfish take less time in games, higher values will make it think longer. * #### nodestime - Tells the engine to use nodes searched instead of wall time to account for + Tells the engine to use nodes searched instead of wall time to account for elapsed time. Useful for engine testing. * #### UCI_Chess960 @@ -79,13 +88,13 @@ Currently, Stockfish has the following UCI options: An option handled by your GUI. * #### SyzygyPath - Path to the folders/directories storing the Syzygy tablebase files. Multiple - directories are to be separated by ";" on Windows and by ":" on Unix-based + Path to the folders/directories storing the Syzygy tablebase files. Multiple + directories are to be separated by ";" on Windows and by ":" on Unix-based operating systems. Do not use spaces around the ";" or ":". - + Example: `C:\tablebases\wdl345;C:\tablebases\wdl6;D:\tablebases\dtz345;D:\tablebases\dtz6` - - It is recommended to store .rtbw files on an SSD. There is no loss in storing + + It is recommended to store .rtbw files on an SSD. There is no loss in storing the .rtbz files on a regular HD. It is recommended to verify all md5 checksums of the downloaded tablebase files (`md5sum -c checksum.md5`) as corruption will lead to engine crashes. @@ -153,7 +162,7 @@ community effort. There are a few ways to help contribute to its growth. ### Donating hardware Improving Stockfish requires a massive amount of testing. You can donate -your hardware resources by installing the [Fishtest Worker](https://github.com/glinscott/fishtest/wiki/Running-the-worker) +your hardware resources by installing the [Fishtest Worker](https://github.com/glinscott/fishtest/wiki/Running-the-worker) and view the current tests on [Fishtest](http://tests.stockfishchess.org/tests). ### Improving the code @@ -169,7 +178,7 @@ generic rather than being focused on Stockfish's precise implementation. Nevertheless, a helpful resource. * The latest source can always be found on [GitHub](https://github.com/official-stockfish/Stockfish). -Discussions about Stockfish take place in the [FishCooking](https://groups.google.com/forum/#!forum/fishcooking) +Discussions about Stockfish take place in the [FishCooking](https://groups.google.com/forum/#!forum/fishcooking) group and engine testing is done on [Fishtest](http://tests.stockfishchess.org/tests). If you want to help improve Stockfish, please read this [guideline](https://github.com/glinscott/fishtest/wiki/Creating-my-first-test) first, where the basics of Stockfish development are explained. diff --git a/src/Makefile b/src/Makefile index 1314092e..42e4118b 100644 --- a/src/Makefile +++ b/src/Makefile @@ -138,6 +138,8 @@ endif ifeq ($(ARCH),ppc-64) arch = ppc64 bits = 64 + popcnt = yes + prefetch = yes endif @@ -315,7 +317,9 @@ endif ### 3.6 popcnt ifeq ($(popcnt),yes) - ifeq ($(comp),icc) + ifeq ($(arch),ppc64) + CXXFLAGS += -DUSE_POPCNT + else ifeq ($(comp),icc) CXXFLAGS += -msse3 -DUSE_POPCNT else CXXFLAGS += -msse3 -mpopcnt -DUSE_POPCNT @@ -483,7 +487,7 @@ config-sanity: @echo "Testing config sanity. If this fails, try 'make help' ..." @echo "" @test "$(debug)" = "yes" || test "$(debug)" = "no" - @test "$(sanitize)" = "undefined" || test "$(sanitize)" = "thread" || test "$(sanitize)" = "no" + @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" diff --git a/src/benchmark.cpp b/src/benchmark.cpp index 51bd7949..b23c5d17 100644 --- a/src/benchmark.cpp +++ b/src/benchmark.cpp @@ -139,9 +139,9 @@ vector setup_bench(const Position& current, istream& is) { file.close(); } - list.emplace_back("ucinewgame"); list.emplace_back("setoption name Threads value " + threads); list.emplace_back("setoption name Hash value " + ttSize); + list.emplace_back("ucinewgame"); for (const string& fen : fens) if (fen.find("setoption") != string::npos) diff --git a/src/bitbase.cpp b/src/bitbase.cpp index 8c8c4702..2b1a5517 100644 --- a/src/bitbase.cpp +++ b/src/bitbase.cpp @@ -27,7 +27,8 @@ namespace { - // There are 24 possible pawn squares: the first 4 files and ranks from 2 to 7 + // There are 24 possible pawn squares: files A to D and ranks from 2 to 7. + // 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 diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 94dfa70f..2afd3766 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -18,8 +18,8 @@ along with this program. If not, see . */ -#include #include +#include #include "bitboard.h" #include "misc.h" @@ -27,17 +27,10 @@ uint8_t PopCnt16[1 << 16]; uint8_t SquareDistance[SQUARE_NB][SQUARE_NB]; +Bitboard SquareBB[SQUARE_NB]; Bitboard LineBB[SQUARE_NB][SQUARE_NB]; -Bitboard DistanceRingBB[SQUARE_NB][8]; Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; Bitboard PawnAttacks[COLOR_NB][SQUARE_NB]; -Bitboard SquareBB[SQUARE_NB]; - -Bitboard KingFlank[FILE_NB] = { - QueenSide ^ FileDBB, QueenSide, QueenSide, - CenterFiles, CenterFiles, - KingSide, KingSide, KingSide ^ FileEBB -}; Magic RookMagics[SQUARE_NB]; Magic BishopMagics[SQUARE_NB]; @@ -83,14 +76,11 @@ void Bitboards::init() { for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1) for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2) - { SquareDistance[s1][s2] = std::max(distance(s1, s2), distance(s1, s2)); - DistanceRingBB[s1][SquareDistance[s1][s2]] |= s2; - } int steps[][5] = { {}, { 7, 9 }, { 6, 10, 15, 17 }, {}, {}, {}, { 1, 7, 8, 9 } }; - for (Color c = WHITE; c <= BLACK; ++c) + for (Color c : { WHITE, BLACK }) for (PieceType pt : { PAWN, KNIGHT, KING }) for (Square s = SQ_A1; s <= SQ_H8; ++s) for (int i = 0; steps[pt][i]; ++i) diff --git a/src/bitboard.h b/src/bitboard.h index 6f99ef19..7a16597d 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -65,15 +65,19 @@ constexpr Bitboard CenterFiles = FileCBB | FileDBB | FileEBB | FileFBB; constexpr Bitboard KingSide = FileEBB | FileFBB | FileGBB | FileHBB; constexpr Bitboard Center = (FileDBB | FileEBB) & (Rank4BB | Rank5BB); +constexpr Bitboard KingFlank[FILE_NB] = { + QueenSide ^ FileDBB, QueenSide, QueenSide, + CenterFiles, CenterFiles, + KingSide, KingSide, KingSide ^ FileEBB +}; + extern uint8_t PopCnt16[1 << 16]; extern uint8_t SquareDistance[SQUARE_NB][SQUARE_NB]; +extern Bitboard SquareBB[SQUARE_NB]; extern Bitboard LineBB[SQUARE_NB][SQUARE_NB]; -extern Bitboard DistanceRingBB[SQUARE_NB][8]; extern Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; extern Bitboard PawnAttacks[COLOR_NB][SQUARE_NB]; -extern Bitboard KingFlank[FILE_NB]; -extern Bitboard SquareBB[SQUARE_NB]; /// Magic holds all magic bitboards relevant data for a single square @@ -149,6 +153,7 @@ inline Bitboard file_bb(Square s) { template constexpr Bitboard shift(Bitboard b) { return D == NORTH ? b << 8 : D == SOUTH ? b >> 8 + : D == NORTH+NORTH? b <<16 : D == SOUTH+SOUTH? b >>16 : D == EAST ? (b & ~FileHBB) << 1 : D == WEST ? (b & ~FileABB) >> 1 : D == NORTH_EAST ? (b & ~FileHBB) << 9 : D == NORTH_WEST ? (b & ~FileABB) << 7 : D == SOUTH_EAST ? (b & ~FileHBB) >> 7 : D == SOUTH_WEST ? (b & ~FileABB) >> 9 @@ -179,8 +184,8 @@ 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. -inline Bitboard adjacent_files_bb(File f) { - return shift(file_bb(f)) | shift(file_bb(f)); +inline Bitboard adjacent_files_bb(Square s) { + return shift(file_bb(s)) | shift(file_bb(s)); } @@ -216,7 +221,7 @@ inline Bitboard forward_file_bb(Color c, Square s) { /// starting from the given square. inline Bitboard pawn_attack_span(Color c, Square s) { - return forward_ranks_bb(c, s) & adjacent_files_bb(file_of(s)); + return forward_ranks_bb(c, s) & adjacent_files_bb(s); } @@ -224,7 +229,7 @@ inline Bitboard pawn_attack_span(Color c, Square s) { /// 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(file_of(s)) | file_bb(s)); + return forward_ranks_bb(c, s) & (adjacent_files_bb(s) | file_bb(s)); } @@ -371,10 +376,7 @@ inline Square pop_lsb(Bitboard* b) { } -/// frontmost_sq() and backmost_sq() return the square corresponding to the -/// most/least advanced bit relative to the given color. - +/// frontmost_sq() returns the most advanced square for the given color inline Square frontmost_sq(Color c, Bitboard b) { return c == WHITE ? msb(b) : lsb(b); } -inline Square backmost_sq(Color c, Bitboard b) { return c == WHITE ? lsb(b) : msb(b); } #endif // #ifndef BITBOARD_H_INCLUDED diff --git a/src/endgame.cpp b/src/endgame.cpp index 5958e633..e10f8d5d 100644 --- a/src/endgame.cpp +++ b/src/endgame.cpp @@ -82,6 +82,34 @@ namespace { } // namespace +namespace Endgames { + + std::pair, Map> maps; + + void init() { + + add("KPK"); + add("KNNK"); + add("KBNK"); + add("KRKP"); + add("KRKB"); + add("KRKN"); + add("KQKP"); + add("KQKR"); + add("KNNKP"); + + add("KNPK"); + add("KNPKB"); + add("KRPKR"); + add("KRPKB"); + add("KBPKB"); + add("KBPKN"); + add("KBPPKB"); + add("KRPPKRP"); + } +} + + /// Mate with KX vs K. This function is used to evaluate positions with /// king and plenty of material vs a lone king. It simply gives the /// attacking side a bonus for driving the defending king towards the edge @@ -337,7 +365,7 @@ ScaleFactor Endgame::operator()(const Position& pos) const { && pos.count(weakSide) >= 1) { // Get weakSide pawn that is closest to the home rank - Square weakPawnSq = backmost_sq(weakSide, pos.pieces(weakSide, PAWN)); + Square weakPawnSq = frontmost_sq(strongSide, pos.pieces(weakSide, PAWN)); Square strongKingSq = pos.square(strongSide); Square weakKingSq = pos.square(weakSide); diff --git a/src/endgame.h b/src/endgame.h index 2a48488f..d0a5a97e 100644 --- a/src/endgame.h +++ b/src/endgame.h @@ -91,15 +91,19 @@ struct Endgame : public EndgameBase { }; -/// The Endgames class stores the pointers to endgame evaluation and scaling +/// The Endgames namespace handles the pointers to endgame evaluation and scaling /// base objects in two std::map. We use polymorphism to invoke the actual /// endgame function by calling its virtual operator(). -class Endgames { +namespace Endgames { template using Ptr = std::unique_ptr>; template using Map = std::map>; + extern std::pair, Map> maps; + + void init(); + template Map& map() { return std::get::value>(maps); @@ -113,35 +117,10 @@ class Endgames { map()[Position().set(code, BLACK, &st).material_key()] = Ptr(new Endgame(BLACK)); } - std::pair, Map> maps; - -public: - Endgames() { - - add("KPK"); - add("KNNK"); - add("KBNK"); - add("KRKP"); - add("KRKB"); - add("KRKN"); - add("KQKP"); - add("KQKR"); - add("KNNKP"); - - add("KNPK"); - add("KNPKB"); - add("KRPKR"); - add("KRPKB"); - add("KBPKB"); - add("KBPKN"); - add("KBPPKB"); - add("KRPPKRP"); - } - template const EndgameBase* probe(Key key) { return map().count(key) ? map()[key].get() : nullptr; } -}; +} #endif // #ifndef ENDGAME_H_INCLUDED diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 566eba6d..7359eb92 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -18,6 +18,7 @@ along with this program. If not, see . */ +#include #include #include // For std::memset #include @@ -73,7 +74,7 @@ using namespace Trace; namespace { // Threshold for lazy and space evaluation - constexpr Value LazyThreshold = Value(1500); + constexpr Value LazyThreshold = Value(1400); constexpr Value SpaceThreshold = Value(12222); // KingAttackWeights[PieceType] contains king attack weights by piece type @@ -122,13 +123,7 @@ namespace { // PassedRank[Rank] contains a bonus according to the rank of a passed pawn constexpr Score PassedRank[RANK_NB] = { - S(0, 0), S(5, 18), S(12, 23), S(10, 31), S(57, 62), S(163, 167), S(271, 250) - }; - - // PassedFile[File] contains a bonus according to the file of a passed pawn - constexpr Score PassedFile[FILE_NB] = { - S( -1, 7), S( 0, 9), S(-9, -8), S(-30,-14), - S(-30,-14), S(-9, -8), S( 0, 9), S( -1, 7) + S(0, 0), S(10, 28), S(17, 33), S(15, 41), S(62, 72), S(168, 177), S(276, 260) }; // Assorted bonuses and penalties @@ -140,7 +135,8 @@ namespace { constexpr Score KnightOnQueen = S( 16, 12); constexpr Score LongDiagonalBishop = S( 45, 0); constexpr Score MinorBehindPawn = S( 18, 3); - constexpr Score Outpost = S( 9, 3); + constexpr Score Outpost = S( 18, 6); + constexpr Score PassedFile = S( 11, 8); constexpr Score PawnlessFlank = S( 17, 95); constexpr Score RestrictedPiece = S( 7, 7); constexpr Score RookOnPawn = S( 10, 32); @@ -151,7 +147,6 @@ namespace { constexpr Score ThreatBySafePawn = S(173, 94); constexpr Score TrappedRook = S( 47, 4); constexpr Score WeakQueen = S( 49, 15); - constexpr Score WeakUnopposedPawn = S( 12, 23); #undef S @@ -186,15 +181,12 @@ namespace { // is also calculated is ALL_PIECES. Bitboard attackedBy[COLOR_NB][PIECE_TYPE_NB]; - // attackedBy2[color] are the squares attacked by 2 pieces of a given color, - // possibly via x-ray or by one pawn and one piece. Diagonal x-ray through - // pawn or squares attacked by 2 pawns are not explicitly added. + // attackedBy2[color] are the squares attacked by at least 2 units of a given + // color, including x-rays. But diagonal x-rays through pawns are not computed. Bitboard attackedBy2[COLOR_NB]; - // kingRing[color] are the squares adjacent to the king, plus (only for a - // king on its first rank) the squares two ranks in front. For instance, - // if black's king is on g8, kingRing[BLACK] is f8, h8, f7, g7, h7, f6, g6 - // and h6. + // kingRing[color] are the squares adjacent to the king plus some other + // very near squares, depending on king position. Bitboard kingRing[COLOR_NB]; // kingAttackersCount[color] is the number of pieces of the given color @@ -224,7 +216,7 @@ namespace { constexpr Color Them = (Us == WHITE ? BLACK : WHITE); constexpr Direction Up = (Us == WHITE ? NORTH : SOUTH); constexpr Direction Down = (Us == WHITE ? SOUTH : NORTH); - constexpr Bitboard LowRanks = (Us == WHITE ? Rank2BB | Rank3BB: Rank7BB | Rank6BB); + constexpr Bitboard LowRanks = (Us == WHITE ? Rank2BB | Rank3BB : Rank7BB | Rank6BB); const Square ksq = pos.square(Us); @@ -241,8 +233,7 @@ namespace { attackedBy[Us][KING] = pos.attacks_from(ksq); attackedBy[Us][PAWN] = pe->pawn_attacks(Us); attackedBy[Us][ALL_PIECES] = attackedBy[Us][KING] | attackedBy[Us][PAWN]; - attackedBy2[Us] = (attackedBy[Us][KING] & attackedBy[Us][PAWN]) - | dblAttackByPawn; + attackedBy2[Us] = dblAttackByPawn | (attackedBy[Us][KING] & attackedBy[Us][PAWN]); // Init our king safety tables kingRing[Us] = attackedBy[Us][KING]; @@ -306,14 +297,12 @@ namespace { if (Pt == BISHOP || Pt == KNIGHT) { // Bonus if piece is on an outpost square or can reach one - bb = OutpostRanks & ~pe->pawn_attacks_span(Them); + bb = OutpostRanks & attackedBy[Us][PAWN] & ~pe->pawn_attacks_span(Them); if (bb & s) - score += Outpost * (Pt == KNIGHT ? 4 : 2) - * (1 + bool(attackedBy[Us][PAWN] & s)); + score += Outpost * (Pt == KNIGHT ? 4 : 2); - else if (bb &= b & ~pos.pieces(Us)) - score += Outpost * (Pt == KNIGHT ? 2 : 1) - * (1 + bool(attackedBy[Us][PAWN] & bb)); + else if (bb & b & ~pos.pieces(Us)) + score += Outpost * (Pt == KNIGHT ? 2 : 1); // Knight and Bishop bonus for being right behind a pawn if (shift(pos.pieces(PAWN)) & s) @@ -358,8 +347,8 @@ namespace { score += RookOnPawn * popcount(pos.pieces(Them, PAWN) & PseudoAttacks[ROOK][s]); // Bonus for rook on an open or semi-open file - if (pos.semiopen_file(Us, file_of(s))) - score += RookOnFile[bool(pos.semiopen_file(Them, file_of(s)))]; + if (pos.is_on_semiopen_file(Us, s)) + score += RookOnFile[bool(pos.is_on_semiopen_file(Them, s))]; // Penalty when trapped by the king, even more if the king cannot castle else if (mob <= 3) @@ -467,12 +456,13 @@ namespace { + 69 * kingAttacksCount[Them] + 185 * popcount(kingRing[Us] & weak) - 100 * bool(attackedBy[Us][KNIGHT] & attackedBy[Us][KING]) + - 35 * bool(attackedBy[Us][BISHOP] & attackedBy[Us][KING]) + 150 * popcount(pos.blockers_for_king(Us) | unsafeChecks) - 873 * !pos.count(Them) - 6 * mg_value(score) / 8 + mg_value(mobility[Them] - mobility[Us]) + 5 * kingFlankAttacks * kingFlankAttacks / 16 - - 15; + - 7; // Transform the kingDanger units into a Score, and subtract it from the evaluation if (kingDanger > 100) @@ -557,10 +547,6 @@ namespace { score += RestrictedPiece * popcount(b); - // Bonus for enemy unopposed weak pawns - if (pos.pieces(Us, ROOK, QUEEN)) - score += WeakUnopposedPawn * pe->weak_unopposed(Them); - // Find squares where our pawns can push on the next move b = shift(pos.pieces(Us, PAWN)) & ~pos.pieces(); b |= shift(b & TRank3BB) & ~pos.pieces(); @@ -569,7 +555,7 @@ namespace { b &= ~attackedBy[Them][PAWN] & safe; // Bonus for safe pawn threats on the next move - b = pawn_attacks_bb(b) & pos.pieces(Them); + b = pawn_attacks_bb(b) & nonPawnEnemies; score += ThreatByPawnPush * popcount(b); // Our safe or protected pawns @@ -613,7 +599,7 @@ namespace { return std::min(distance(pos.square(c), s), 5); }; - Bitboard b, bb, squaresToQueen, defendedSquares, unsafeSquares; + Bitboard b, bb, squaresToQueen, unsafeSquares; Score score = SCORE_ZERO; b = pe->passed_pawns(Us); @@ -625,12 +611,13 @@ namespace { assert(!(pos.pieces(Them, PAWN) & forward_file_bb(Us, s + Up))); int r = relative_rank(Us, s); + File f = file_of(s); Score bonus = PassedRank[r]; if (r > RANK_3) { - int w = (r-2) * (r-2) + 2; + int w = 5 * r - 13; Square blockSq = s + Up; // Adjust bonus based on the king's proximity @@ -644,42 +631,37 @@ namespace { // If the pawn is free to advance, then increase the bonus if (pos.empty(blockSq)) { - // If there is a rook or queen attacking/defending the pawn from behind, - // consider all the squaresToQueen. Otherwise consider only the squares - // in the pawn's path attacked or occupied by the enemy. - defendedSquares = unsafeSquares = squaresToQueen = forward_file_bb(Us, s); + squaresToQueen = forward_file_bb(Us, s); + unsafeSquares = passed_pawn_span(Us, s); - bb = forward_file_bb(Them, s) & pos.pieces(ROOK, QUEEN) & pos.attacks_from(s); - - if (!(pos.pieces(Us) & bb)) - defendedSquares &= attackedBy[Us][ALL_PIECES]; + bb = forward_file_bb(Them, s) & pos.pieces(ROOK, QUEEN); if (!(pos.pieces(Them) & bb)) - unsafeSquares &= attackedBy[Them][ALL_PIECES] | pos.pieces(Them); - - // If there aren't any enemy attacks, assign a big bonus. Otherwise - // assign a smaller bonus if the block square isn't attacked. - int k = !unsafeSquares ? 20 : !(unsafeSquares & blockSq) ? 9 : 0; + unsafeSquares &= attackedBy[Them][ALL_PIECES]; - // If the path to the queen is fully defended, assign a big bonus. - // Otherwise assign a smaller bonus if the block square is defended. - if (defendedSquares == squaresToQueen) - k += 6; + // If there are no enemy attacks on passed pawn span, assign a big bonus. + // Otherwise assign a smaller bonus if the path to queen is not attacked + // and even smaller bonus if it is attacked but block square is not. + int k = !unsafeSquares ? 35 : + !(unsafeSquares & squaresToQueen) ? 20 : + !(unsafeSquares & blockSq) ? 9 : + 0 ; - else if (defendedSquares & blockSq) - k += 4; + // Assign a larger bonus if the block square is defended + if ((pos.pieces(Us) & bb) || (attackedBy[Us][ALL_PIECES] & blockSq)) + k += 5; bonus += make_score(k * w, k * w); } - } // rank > RANK_3 + } // 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) & forward_file_bb(Us, s))) + || (pos.pieces(PAWN) & (s + Up))) bonus = bonus / 2; - score += bonus + PassedFile[file_of(s)]; + score += bonus - PassedFile * std::min(f, ~f); } if (T) @@ -716,12 +698,10 @@ namespace { // Find all squares which are at most three squares behind some friendly pawn Bitboard behind = pos.pieces(Us, PAWN); behind |= shift(behind); - behind |= shift(shift(behind)); - - int bonus = popcount(safe) + popcount(behind & safe); - int weight = pos.count(Us) - - (16 - pos.count()) / 4; + behind |= shift(behind); + int bonus = popcount(safe) + popcount(behind & safe & ~attackedBy[Them][ALL_PIECES]); + int weight = pos.count(Us) - 1; Score score = make_score(bonus * weight * weight / 16, 0); if (T) @@ -776,8 +756,7 @@ namespace { if (sf == SCALE_FACTOR_NORMAL) { if ( pos.opposite_bishops() - && pos.non_pawn_material(WHITE) == BishopValueMg - && pos.non_pawn_material(BLACK) == BishopValueMg) + && pos.non_pawn_material() == 2 * BishopValueMg) sf = 16 + 4 * pe->passed_count(); else sf = std::min(40 + (pos.opposite_bishops() ? 2 : 7) * pos.count(strongSide), sf); @@ -816,7 +795,7 @@ namespace { // Early exit if score is high Value v = (mg_value(score) + eg_value(score)) / 2; - if (abs(v) > LazyThreshold) + if (abs(v) > LazyThreshold + pos.non_pawn_material() / 64) return pos.side_to_move() == WHITE ? v : -v; // Main evaluation begins here diff --git a/src/main.cpp b/src/main.cpp index b9d2dfb4..88d46117 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -29,6 +29,7 @@ #include "thread.h" #include "tt.h" #include "uci.h" +#include "endgame.h" #include "syzygy/tbprobe.h" #include @@ -235,6 +236,7 @@ int main(int argc, char* argv[]) { Bitboards::init(); Position::init(); Bitbases::init(); + Endgames::init(); Search::init(); Threads.set(Options["Threads"]); Search::clear(); // After threads are up diff --git a/src/material.cpp b/src/material.cpp index ee5d4bce..11d4c687 100644 --- a/src/material.cpp +++ b/src/material.cpp @@ -137,10 +137,10 @@ Entry* probe(const Position& pos) { // Let's look if we have a specialized evaluation function for this particular // material configuration. Firstly we look for a fixed configuration one, then // for a generic one if the previous search failed. - if ((e->evaluationFunction = pos.this_thread()->endgames.probe(key)) != nullptr) + if ((e->evaluationFunction = Endgames::probe(key)) != nullptr) return e; - for (Color c = WHITE; c <= BLACK; ++c) + for (Color c : { WHITE, BLACK }) if (is_KXK(pos, c)) { e->evaluationFunction = &EvaluateKXK[c]; @@ -149,7 +149,7 @@ Entry* probe(const Position& pos) { // OK, we didn't find any special evaluation function for the current material // configuration. Is there a suitable specialized scaling function? - const auto* sf = pos.this_thread()->endgames.probe(key); + const auto* sf = Endgames::probe(key); if (sf) { @@ -160,7 +160,7 @@ Entry* probe(const Position& pos) { // We didn't find any specialized scaling function, so fall back on generic // ones that refer to more than one material distribution. Note that in this // case we don't return after setting the function. - for (Color c = WHITE; c <= BLACK; ++c) + for (Color c : { WHITE, BLACK }) { if (is_KBPsK(pos, c)) e->scalingFunction[c] = &ScaleKBPsK[c]; diff --git a/src/misc.cpp b/src/misc.cpp index bca48876..43a73b28 100644 --- a/src/misc.cpp +++ b/src/misc.cpp @@ -146,7 +146,7 @@ const string engine_info(bool to_uci) { /// Debug functions used mainly to collect run-time statistics -static int64_t hits[2], means[2]; +static std::atomic hits[2], means[2]; void dbg_hit_on(bool b) { ++hits[0]; if (b) ++hits[1]; } void dbg_hit_on(bool c, bool b) { if (c) dbg_hit_on(b); } @@ -211,12 +211,6 @@ void prefetch(void* addr) { #endif -void prefetch2(void* addr) { - - prefetch(addr); - prefetch((uint8_t*)addr + 64); -} - namespace WinProcGroup { #ifndef _WIN32 diff --git a/src/misc.h b/src/misc.h index 4b238df5..ddd05e4e 100644 --- a/src/misc.h +++ b/src/misc.h @@ -31,7 +31,6 @@ const std::string engine_info(bool to_uci = false); void prefetch(void* addr); -void prefetch2(void* addr); void start_logger(const std::string& fname); void dbg_hit_on(bool b); diff --git a/src/movepick.cpp b/src/movepick.cpp index a70785e7..64380da9 100644 --- a/src/movepick.cpp +++ b/src/movepick.cpp @@ -107,8 +107,8 @@ void MovePicker::score() { for (auto& m : *this) if (Type == CAPTURES) - m.value = PieceValue[MG][pos.piece_on(to_sq(m))] - + (*captureHistory)[pos.moved_piece(m)][to_sq(m)][type_of(pos.piece_on(to_sq(m)))] / 8; + m.value = int(PieceValue[MG][pos.piece_on(to_sq(m))]) * 6 + + (*captureHistory)[pos.moved_piece(m)][to_sq(m)][type_of(pos.piece_on(to_sq(m)))]; else if (Type == QUIETS) m.value = (*mainHistory)[pos.side_to_move()][from_to(m)] @@ -200,11 +200,15 @@ top: /* fallthrough */ case QUIET_INIT: - cur = endBadCaptures; - endMoves = generate(pos, cur); + if (!skipQuiets) + { + cur = endBadCaptures; + endMoves = generate(pos, cur); + + score(); + partial_insertion_sort(cur, endMoves, -4000 * depth / ONE_PLY); + } - score(); - partial_insertion_sort(cur, endMoves, -4000 * depth / ONE_PLY); ++stage; /* fallthrough */ diff --git a/src/pawns.cpp b/src/pawns.cpp index e2b26344..86c4b8ef 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -18,6 +18,7 @@ along with this program. If not, see . */ +#include #include #include "bitboard.h" @@ -31,12 +32,14 @@ namespace { #define S(mg, eg) make_score(mg, eg) // Pawn penalties - constexpr Score Backward = S( 9, 24); - constexpr Score Doubled = S(11, 56); - constexpr Score Isolated = S( 5, 15); + constexpr Score Backward = S( 9, 24); + constexpr Score Doubled = S(11, 56); + constexpr Score Isolated = S( 5, 15); + constexpr Score WeakLever = S( 0, 56); + constexpr Score WeakUnopposed = S(13, 27); // Connected pawn bonus - constexpr int Connected[RANK_NB] = { 0, 13, 17, 24, 59, 96, 171 }; + constexpr int Connected[RANK_NB] = { 0, 7, 8, 12, 29, 48, 86 }; // Strength of pawn shelter for our king by [distance from edge][rank]. // RANK_1 = 0 is used for files where we have no pawn, or pawn is behind our king. @@ -50,11 +53,12 @@ namespace { // Danger of enemy pawns moving toward our king by [distance from edge][rank]. // RANK_1 = 0 is used for files where the enemy has no pawn, or their pawn // is behind our king. + // [0][1-2] accommodate opponent pawn on edge (likely blocked by our king) constexpr Value UnblockedStorm[int(FILE_NB) / 2][RANK_NB] = { - { V( 89), V(107), V(123), V(93), V(57), V( 45), V( 51) }, - { V( 44), V(-18), V(123), V(46), V(39), V( -7), V( 23) }, - { V( 4), V( 52), V(162), V(37), V( 7), V(-14), V( -2) }, - { V(-10), V(-14), V( 90), V(15), V( 2), V( -7), V(-16) } + { V( 89), V(-285), V(-185), V(93), V(57), V( 45), V( 51) }, + { V( 44), V( -18), V( 123), V(46), V(39), V( -7), V( 23) }, + { V( 4), V( 52), V( 162), V(37), V( 7), V(-14), V( -2) }, + { V(-10), V( -14), V( 90), V(15), V( 2), V( -7), V(-16) } }; #undef S @@ -66,26 +70,27 @@ namespace { constexpr Color Them = (Us == WHITE ? BLACK : WHITE); constexpr Direction Up = (Us == WHITE ? NORTH : SOUTH); - Bitboard b, neighbours, stoppers, doubled, support, phalanx; + Bitboard neighbours, stoppers, doubled, support, phalanx; Bitboard lever, leverPush; Square s; - bool opposed, backward; + bool opposed, backward, passed; Score score = SCORE_ZERO; const Square* pl = pos.squares(Us); Bitboard ourPawns = pos.pieces( Us, PAWN); Bitboard theirPawns = pos.pieces(Them, PAWN); - e->passedPawns[Us] = e->pawnAttacksSpan[Us] = e->weakUnopposed[Us] = 0; - e->kingSquares[Us] = SQ_NONE; - e->pawnAttacks[Us] = pawn_attacks_bb(ourPawns); + Bitboard doubleAttackThem = pawn_double_attacks_bb(theirPawns); + + e->passedPawns[Us] = e->pawnAttacksSpan[Us] = 0; + e->kingSquares[Us] = SQ_NONE; + e->pawnAttacks[Us] = pawn_attacks_bb(ourPawns); // Loop through all pawns of the current color and score each pawn while ((s = *pl++) != SQ_NONE) { assert(pos.piece_on(s) == make_piece(Us, PAWN)); - File f = file_of(s); Rank r = relative_rank(Us, s); e->pawnAttacksSpan[Us] |= pawn_attack_span(Us, s); @@ -96,49 +101,55 @@ namespace { lever = theirPawns & PawnAttacks[Us][s]; leverPush = theirPawns & PawnAttacks[Us][s + Up]; doubled = ourPawns & (s - Up); - neighbours = ourPawns & adjacent_files_bb(f); + neighbours = ourPawns & adjacent_files_bb(s); phalanx = neighbours & rank_bb(s); support = neighbours & rank_bb(s - Up); - // A pawn is backward when it is behind all pawns of the same color - // on the adjacent files and cannot be safely advanced. - backward = !(ourPawns & pawn_attack_span(Them, s + Up)) + // A pawn is backward when it is behind all pawns of the same color on + // the adjacent files and cannot safely advance. Phalanx and isolated + // pawns will be excluded when the pawn is scored. + backward = !(neighbours & forward_ranks_bb(Them, s)) && (stoppers & (leverPush | (s + Up))); - // Passed pawns will be properly scored in evaluation because we need - // full attack info to evaluate them. Include also not passed pawns - // which could become passed after one or two pawn pushes when are - // not attacked more times than defended. - if ( !(stoppers ^ lever ^ leverPush) - && (support || !more_than_one(lever)) - && popcount(phalanx) >= popcount(leverPush)) + // A pawn is passed if one of the three following conditions is true: + // (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. + passed = !(stoppers ^ lever) + || ( !(stoppers ^ leverPush) + && popcount(phalanx) >= popcount(leverPush)) + || ( stoppers == square_bb(s + Up) && r >= RANK_5 + && (shift(support) & ~(theirPawns | doubleAttackThem))); + + // Passed pawns will be properly scored later in evaluation when we have + // full attack info. + if (passed) e->passedPawns[Us] |= s; - else if (stoppers == square_bb(s + Up) && r >= RANK_5) - { - b = shift(support) & ~theirPawns; - while (b) - if (!more_than_one(theirPawns & PawnAttacks[Us][pop_lsb(&b)])) - e->passedPawns[Us] |= s; - } - // Score this pawn if (support | phalanx) { - int v = (phalanx ? 3 : 2) * Connected[r]; - v = 17 * popcount(support) + (v >> (opposed + 1)); + int v = Connected[r] * (phalanx ? 3 : 2) / (opposed ? 2 : 1) + + 17 * popcount(support); + score += make_score(v, v * (r - 2) / 4); } + else if (!neighbours) - score -= Isolated, e->weakUnopposed[Us] += !opposed; + score -= Isolated + WeakUnopposed * int(!opposed); else if (backward) - score -= Backward, e->weakUnopposed[Us] += !opposed; + score -= Backward + WeakUnopposed * int(!opposed); if (doubled && !support) score -= Doubled; } + // Penalize our unsupported pawns attacked twice by enemy pawns + score -= WeakLever * popcount( ourPawns + & doubleAttackThem + & ~e->pawnAttacks[Us]); + return score; } @@ -171,35 +182,36 @@ Entry* probe(const Position& pos) { /// penalty for a king, looking at the king file and the two closest files. template -Value Entry::evaluate_shelter(const Position& pos, Square ksq) { +void Entry::evaluate_shelter(const Position& pos, Square ksq, Score& shelter) { - constexpr Color Them = (Us == WHITE ? BLACK : WHITE); - constexpr Direction Down = (Us == WHITE ? SOUTH : NORTH); - constexpr Bitboard BlockRanks = (Us == WHITE ? Rank1BB | Rank2BB : Rank8BB | Rank7BB); + constexpr Color Them = (Us == WHITE ? BLACK : WHITE); Bitboard b = pos.pieces(PAWN) & ~forward_ranks_bb(Them, ksq); Bitboard ourPawns = b & pos.pieces(Us); Bitboard theirPawns = b & pos.pieces(Them); - Value safety = (shift(theirPawns) & (FileABB | FileHBB) & BlockRanks & ksq) ? - Value(374) : Value(5); + Score bonus = make_score(5, 5); File center = clamp(file_of(ksq), FILE_B, FILE_G); for (File f = File(center - 1); f <= File(center + 1); ++f) { b = ourPawns & file_bb(f); - Rank ourRank = b ? relative_rank(Us, backmost_sq(Us, b)) : RANK_1; + Rank ourRank = b ? relative_rank(Us, frontmost_sq(Them, b)) : RANK_1; b = theirPawns & file_bb(f); Rank theirRank = b ? relative_rank(Us, frontmost_sq(Them, b)) : RANK_1; int d = std::min(f, ~f); - safety += ShelterStrength[d][ourRank]; - safety -= (ourRank && (ourRank == theirRank - 1)) ? 66 * (theirRank == RANK_3) - : UnblockedStorm[d][theirRank]; + bonus += make_score(ShelterStrength[d][ourRank], 0); + + if (ourRank && (ourRank == theirRank - 1)) + bonus -= make_score(82 * (theirRank == RANK_3), 82 * (theirRank == RANK_3)); + else + bonus -= make_score(UnblockedStorm[d][theirRank], 0); } - return safety; + if (mg_value(bonus) > mg_value(shelter)) + shelter = bonus; } @@ -212,22 +224,27 @@ Score Entry::do_king_safety(const Position& pos) { Square ksq = pos.square(Us); kingSquares[Us] = ksq; castlingRights[Us] = pos.castling_rights(Us); - int minKingPawnDistance = 0; Bitboard pawns = pos.pieces(Us, PAWN); - if (pawns) - while (!(DistanceRingBB[ksq][++minKingPawnDistance] & pawns)) {} + int minPawnDist = pawns ? 8 : 0; + + if (pawns & PseudoAttacks[KING][ksq]) + minPawnDist = 1; + + else while (pawns) + minPawnDist = std::min(minPawnDist, distance(ksq, pop_lsb(&pawns))); - Value bonus = evaluate_shelter(pos, ksq); + Score shelter = make_score(-VALUE_INFINITE, VALUE_ZERO); + evaluate_shelter(pos, ksq, shelter); // If we can castle use the bonus after the castling if it is bigger if (pos.can_castle(Us | KING_SIDE)) - bonus = std::max(bonus, evaluate_shelter(pos, relative_square(Us, SQ_G1))); + evaluate_shelter(pos, relative_square(Us, SQ_G1), shelter); if (pos.can_castle(Us | QUEEN_SIDE)) - bonus = std::max(bonus, evaluate_shelter(pos, relative_square(Us, SQ_C1))); + evaluate_shelter(pos, relative_square(Us, SQ_C1), shelter); - return make_score(bonus, -16 * minKingPawnDistance); + return shelter - make_score(VALUE_ZERO, 16 * minPawnDist); } // Explicit template instantiation diff --git a/src/pawns.h b/src/pawns.h index 88b55545..1f930988 100644 --- a/src/pawns.h +++ b/src/pawns.h @@ -37,8 +37,7 @@ struct Entry { Bitboard pawn_attacks(Color c) const { return pawnAttacks[c]; } Bitboard passed_pawns(Color c) const { return passedPawns[c]; } Bitboard pawn_attacks_span(Color c) const { return pawnAttacksSpan[c]; } - int weak_unopposed(Color c) const { return weakUnopposed[c]; } - int passed_count() const { return popcount(passedPawns[WHITE] | passedPawns[BLACK]); }; + int passed_count() const { return popcount(passedPawns[WHITE] | passedPawns[BLACK]); } template Score king_safety(const Position& pos) { @@ -50,7 +49,7 @@ struct Entry { Score do_king_safety(const Position& pos); template - Value evaluate_shelter(const Position& pos, Square ksq); + void evaluate_shelter(const Position& pos, Square ksq, Score& shelter); Key key; Score scores[COLOR_NB]; @@ -59,12 +58,10 @@ struct Entry { Bitboard pawnAttacksSpan[COLOR_NB]; Square kingSquares[COLOR_NB]; Score kingSafety[COLOR_NB]; - int weakUnopposed[COLOR_NB]; int castlingRights[COLOR_NB]; - int pawnsOnSquares[COLOR_NB][COLOR_NB]; // [color][light/dark squares] }; -typedef HashTable Table; +typedef HashTable Table; Entry* probe(const Position& pos); diff --git a/src/position.cpp b/src/position.cpp index ed5cc43f..3310460f 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -18,6 +18,7 @@ along with this program. If not, see . */ +#include #include #include // For offsetof() #include // For std::memset, std::memcmp @@ -54,13 +55,13 @@ constexpr Piece Pieces[] = { W_PAWN, W_KNIGHT, W_BISHOP, W_ROOK, W_QUEEN, W_KING // valuable attacker for the side to move, remove the attacker we just found // from the bitboards and scan for new X-ray attacks behind it. -template +template PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttackers, Bitboard& occupied, Bitboard& attackers) { Bitboard b = stmAttackers & byTypeBB[Pt]; if (!b) - return min_attacker(byTypeBB, to, stmAttackers, occupied, attackers); + return min_attacker(byTypeBB, to, stmAttackers, occupied, attackers); occupied ^= lsb(b); // Remove the attacker from occupied @@ -76,7 +77,7 @@ PieceType min_attacker(const Bitboard* byTypeBB, Square to, Bitboard stmAttacker // X-ray may add already processed pieces because byTypeBB[] is constant: in // the rook example, now attackers contains _again_ rook in a7, so remove it. attackers &= occupied; - return (PieceType)Pt; + return Pt; } template<> @@ -338,8 +339,8 @@ void Position::set_castling_right(Color c, Square rfrom) { Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1); Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1); - castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto) - & ~(square_bb(kfrom) | rfrom); + castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto) + & ~(square_bb(kfrom) | rfrom); } @@ -380,6 +381,12 @@ void Position::set_state(StateInfo* si) const { Square s = pop_lsb(&b); Piece pc = piece_on(s); si->key ^= Zobrist::psq[pc][s]; + + if (type_of(pc) == PAWN) + si->pawnKey ^= Zobrist::psq[pc][s]; + + else if (type_of(pc) != KING) + si->nonPawnMaterial[color_of(pc)] += PieceValue[MG][pc]; } if (si->epSquare != SQ_NONE) @@ -390,20 +397,9 @@ void Position::set_state(StateInfo* si) const { si->key ^= Zobrist::castling[si->castlingRights]; - for (Bitboard b = pieces(PAWN); b; ) - { - Square s = pop_lsb(&b); - si->pawnKey ^= Zobrist::psq[piece_on(s)][s]; - } - for (Piece pc : Pieces) - { - if (type_of(pc) != PAWN && type_of(pc) != KING) - si->nonPawnMaterial[color_of(pc)] += pieceCount[pc] * PieceValue[MG][pc]; - for (int cnt = 0; cnt < pieceCount[pc]; ++cnt) si->materialKey ^= Zobrist::psq[pc][cnt]; - } } @@ -493,7 +489,7 @@ Bitboard Position::slider_blockers(Bitboard sliders, Square s, Bitboard& pinners // 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 occupancy = pieces() & ~snipers; + Bitboard occupancy = pieces() ^ snipers; while (snipers) { @@ -857,7 +853,6 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) { // Update pawn hash key and prefetch access to pawnsTable st->pawnKey ^= Zobrist::psq[pc][from] ^ Zobrist::psq[pc][to]; - prefetch2(thisThread->pawnsTable[st->pawnKey]); // Reset rule 50 draw counter st->rule50 = 0; @@ -877,6 +872,25 @@ void Position::do_move(Move m, StateInfo& newSt, bool givesCheck) { // Update king attacks used for fast check detection set_check_info(st); + // Calculate the repetition info. It is the ply distance from the previous + // occurrence of the same position, negative in the 3-fold case, or zero + // if the position was not repeated. + st->repetition = 0; + int end = std::min(st->rule50, st->pliesFromNull); + if (end >= 4) + { + StateInfo* stp = st->previous->previous; + for (int i=4; i <= end; i += 2) + { + stp = stp->previous->previous; + if (stp->key == st->key) + { + st->repetition = stp->repetition ? -i : i; + break; + } + } + } + assert(pos_is_ok()); } @@ -992,6 +1006,8 @@ void Position::do_null_move(StateInfo& newSt) { set_check_info(st); + st->repetition = 0; + assert(pos_is_ok()); } @@ -1115,24 +1131,10 @@ bool Position::is_draw(int ply) const { if (st->rule50 > 99 && (!checkers() || MoveList(*this).size())) return true; - int end = std::min(st->rule50, st->pliesFromNull); - - if (end < 4) - return false; - - StateInfo* stp = st->previous->previous; - int cnt = 0; - - for (int i = 4; i <= end; i += 2) - { - stp = stp->previous->previous; - - // Return a draw score if a position repeats once earlier but strictly - // after the root, or repeats twice before or at the root. - if ( stp->key == st->key - && ++cnt + (ply > i) == 2) - return true; - } + // 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; } @@ -1144,26 +1146,15 @@ bool Position::is_draw(int ply) const { bool Position::has_repeated() const { StateInfo* stc = st; - while (true) + int end = std::min(st->rule50, st->pliesFromNull); + while (end-- >= 4) { - int i = 4, end = std::min(stc->rule50, stc->pliesFromNull); - - if (end < i) - return false; - - StateInfo* stp = stc->previous->previous; - - do { - stp = stp->previous->previous; - - if (stp->key == stc->key) - return true; - - i += 2; - } while (i <= end); + if (stc->repetition) + return true; stc = stc->previous; } + return false; } @@ -1196,22 +1187,19 @@ bool Position::has_game_cycle(int ply) const { if (!(between_bb(s1, s2) & pieces())) { - // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in the same - // location. We select the legal one by reversing the move variable if necessary. - if (empty(s1)) - move = make_move(s2, s1); - if (ply > i) return true; + // For nodes before or at the root, check that the move is a + // repetition rather than a move to the current position. + // In the cuckoo table, both moves Rc1c5 and Rc5c1 are stored in + // the same location, so we have to select which square to check. + if (color_of(piece_on(empty(s1) ? s2 : s1)) != side_to_move()) + continue; + // For repetitions before or at the root, require one more - StateInfo* next_stp = stp; - for (int k = i + 2; k <= end; k += 2) - { - next_stp = next_stp->previous->previous; - if (next_stp->key == stp->key) - return true; - } + if (stp->repetition) + return true; } } } @@ -1309,8 +1297,8 @@ bool Position::pos_is_ok() const { assert(0 && "pos_is_ok: Index"); } - for (Color c = WHITE; c <= BLACK; ++c) - for (CastlingSide s = KING_SIDE; s <= QUEEN_SIDE; s = CastlingSide(s + 1)) + for (Color c : { WHITE, BLACK }) + for (CastlingSide s : {KING_SIDE, QUEEN_SIDE}) { if (!can_castle(c | s)) continue; diff --git a/src/position.h b/src/position.h index 1078e03e..2106414b 100644 --- a/src/position.h +++ b/src/position.h @@ -46,6 +46,7 @@ struct StateInfo { Square epSquare; // Not copied when making a move (will be recomputed anyhow) + int repetition; Key key; Bitboard checkersBB; Piece capturedPiece; @@ -95,7 +96,7 @@ public: template int count() const; template const Square* squares(Color c) const; template Square square(Color c) const; - int semiopen_file(Color c, File f) const; + bool is_on_semiopen_file(Color c, Square s) const; // Castling int castling_rights(Color c) const; @@ -107,6 +108,7 @@ public: Bitboard checkers() const; Bitboard blockers_for_king(Color c) const; Bitboard check_squares(PieceType pt) const; + bool is_discovery_check_on_king(Color c, Move m) const; // Attacks to/from a given square Bitboard attackers_to(Square s) const; @@ -262,8 +264,8 @@ inline Square Position::ep_square() const { return st->epSquare; } -inline int Position::semiopen_file(Color c, File f) const { - return !(pieces(c, PAWN) & file_bb(f)); +inline bool Position::is_on_semiopen_file(Color c, Square s) const { + return !(pieces(c, PAWN) & file_bb(s)); } inline bool Position::can_castle(CastlingRight cr) const { @@ -315,13 +317,17 @@ inline Bitboard Position::check_squares(PieceType pt) const { return st->checkSquares[pt]; } +inline bool Position::is_discovery_check_on_king(Color c, Move m) const { + return st->blockersForKing[c] & from_sq(m); +} + inline bool Position::pawn_passed(Color c, Square s) const { return !(pieces(~c, PAWN) & passed_pawn_span(c, s)); } inline bool Position::advanced_pawn_push(Move m) const { return type_of(moved_piece(m)) == PAWN - && relative_rank(sideToMove, from_sq(m)) > RANK_4; + && relative_rank(sideToMove, to_sq(m)) > RANK_5; } inline int Position::pawns_on_same_color_squares(Color c, Square s) const { diff --git a/src/psqt.cpp b/src/psqt.cpp index cba6bb06..36d99feb 100644 --- a/src/psqt.cpp +++ b/src/psqt.cpp @@ -93,12 +93,12 @@ constexpr Score Bonus[][RANK_NB][int(FILE_NB) / 2] = { constexpr Score PBonus[RANK_NB][FILE_NB] = { // Pawn (asymmetric distribution) { }, - { S( 0,-10), S( -5,-3), S( 10, 7), S( 13,-1), S( 21, 7), S( 17, 6), S( 6, 1), S( -3,-20) }, - { S(-11, -6), S(-10,-6), S( 15,-1), S( 22,-1), S( 26, -1), S( 28, 2), S( 4,-2), S(-24, -5) }, - { S( -9, 4), S(-18,-5), S( 8,-4), S( 22,-5), S( 33, -6), S( 25,-13), S( -4,-3), S(-16, -7) }, - { S( 6, 18), S( -3, 2), S(-10, 2), S( 1,-9), S( 12,-13), S( 6, -8), S(-12,11), S( 1, 9) }, - { S( -6, 25), S( -8,17), S( 5,19), S( 11,29), S(-14, 29), S( 0, 8), S(-12, 4), S(-14, 12) }, - { S(-10, -1), S( 6,-6), S( -5,18), S(-11,22), S( -2, 22), S(-14, 17), S( 12, 2), S( -1, 9) } + { 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( -7, 0), S( 7,-11), S( -3, 12), S(-13, 21), S( 5, 25), S(-16, 19), S( 10, 4), S( -8, 7) } }; #undef S diff --git a/src/search.cpp b/src/search.cpp index 95b14021..53f61a97 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -18,6 +18,7 @@ along with this program. If not, see . */ +#include #include #include #include // For std::memset @@ -61,17 +62,17 @@ namespace { enum NodeType { NonPV, PV }; // Razor and futility margins - constexpr int RazorMargin = 600; + constexpr int RazorMargin = 661; Value futility_margin(Depth d, bool improving) { - return Value((175 - 50 * improving) * d / ONE_PLY); + return Value((168 - 51 * improving) * d / ONE_PLY); } // Reductions lookup table, initialized at startup - int Reductions[64]; // [depth or moveNumber] + int Reductions[MAX_MOVES]; // [depth or moveNumber] - template Depth reduction(bool i, Depth d, int mn) { - int r = Reductions[std::min(d / ONE_PLY, 63)] * Reductions[std::min(mn, 63)] / 1024; - return ((r + 512) / 1024 + (!i && r > 1024) - PvNode) * ONE_PLY; + Depth reduction(bool i, Depth d, int mn) { + int r = Reductions[d / ONE_PLY] * Reductions[mn]; + return ((r + 520) / 1024 + (!i && r > 999)) * ONE_PLY; } constexpr int futility_move_count(bool improving, int depth) { @@ -81,7 +82,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth depth) { int d = depth / ONE_PLY; - return d > 17 ? 0 : 29 * d * d + 138 * d - 134; + return d > 17 ? -8 : 22 * d * d + 151 * d - 140; } // Add a small random component to draw evaluations to avoid 3fold-blindness @@ -101,6 +102,48 @@ namespace { Move best = MOVE_NONE; }; + // Breadcrumbs are used to mark nodes as being searched by a given thread. + struct Breadcrumb { + std::atomic thread; + std::atomic key; + }; + std::array breadcrumbs; + + // ThreadHolding keeps track of which thread left breadcrumbs at the given node for potential reductions. + // A free node will be marked upon entering the moves loop, and unmarked upon leaving that loop, by the ctor/dtor of this struct. + struct ThreadHolding { + explicit ThreadHolding(Thread* thisThread, Key posKey, int ply) { + location = ply < 8 ? &breadcrumbs[posKey & (breadcrumbs.size() - 1)] : nullptr; + otherThread = false; + owning = false; + if (location) + { + // see if another already marked this location, if not, mark it ourselves. + Thread* tmp = (*location).thread.load(std::memory_order_relaxed); + if (tmp == nullptr) + { + (*location).thread.store(thisThread, std::memory_order_relaxed); + (*location).key.store(posKey, std::memory_order_relaxed); + owning = true; + } + else if ( tmp != thisThread + && (*location).key.load(std::memory_order_relaxed) == posKey) + otherThread = true; + } + } + + ~ThreadHolding() { + if (owning) // free the marked location. + (*location).thread.store(nullptr, std::memory_order_relaxed); + } + + bool marked() { return otherThread; } + + private: + Breadcrumb* location; + bool otherThread, owning; + }; + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); @@ -147,8 +190,8 @@ namespace { void Search::init() { - for (int i = 1; i < 64; ++i) - Reductions[i] = int(1024 * std::log(i) / std::sqrt(1.95)); + for (int i = 1; i < MAX_MOVES; ++i) + Reductions[i] = int(23.4 * std::log(i)); } @@ -228,31 +271,32 @@ void MainThread::search() { // Check if there are threads with a better score than main thread if ( Options["MultiPV"] == 1 && !Limits.depth - && !Skill(Options["Skill Level"]).enabled() + && !(Skill(Options["Skill Level"]).enabled() || Options["UCI_LimitStrength"]) && rootMoves[0].pv[0] != MOVE_NONE) { std::map votes; Value minScore = this->rootMoves[0].score; - // Find out minimum score and reset votes for moves which can be voted + // Find out minimum score for (Thread* th: Threads) minScore = std::min(minScore, th->rootMoves[0].score); - // Vote according to score and depth + // Vote according to score and depth, and select the best thread for (Thread* th : Threads) { - int64_t s = th->rootMoves[0].score - minScore + 1; - votes[th->rootMoves[0].pv[0]] += 200 + s * s * int(th->completedDepth); - } + votes[th->rootMoves[0].pv[0]] += + (th->rootMoves[0].score - minScore + 14) * int(th->completedDepth); - // Select best thread - auto bestVote = votes[this->rootMoves[0].pv[0]]; - for (Thread* th : Threads) - if (votes[th->rootMoves[0].pv[0]] > bestVote) + if (bestThread->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY) { - bestVote = votes[th->rootMoves[0].pv[0]]; - bestThread = th; + // 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; @@ -298,7 +342,19 @@ void Thread::search() { beta = VALUE_INFINITE; size_t multiPV = Options["MultiPV"]; - Skill skill(Options["Skill Level"]); + + // Pick integer skill levels, but non-deterministically round up or down + // such that the average integer skill corresponds to the input floating point one. + // UCI_Elo is converted to a suitable fractional skill level, using anchoring + // to CCRL Elo (goldfish 1.13 = 2000) and a fit through Ordo derived Elo + // 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) : + double(Options["Skill Level"]); + int intLevel = int(floatLevel) + + ((floatLevel - int(floatLevel)) * 1024 > rng.rand() % 1024 ? 1 : 0); + Skill skill(intLevel); // When playing with strength handicap enable MultiPV search that we will // use behind the scenes to retrieve a set of possible moves. @@ -353,15 +409,15 @@ void Thread::search() { selDepth = 0; // Reset aspiration window starting size - if (rootDepth >= 5 * ONE_PLY) + if (rootDepth >= 4 * ONE_PLY) { Value previousScore = rootMoves[pvIdx].previousScore; - delta = Value(20); + delta = Value(23); alpha = std::max(previousScore - delta,-VALUE_INFINITE); beta = std::min(previousScore + delta, VALUE_INFINITE); // Adjust contempt based on root move's previousScore (dynamic contempt) - int dct = ct + 88 * previousScore / (abs(previousScore) + 200); + int dct = ct + 86 * previousScore / (abs(previousScore) + 176); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -405,17 +461,14 @@ void Thread::search() { beta = (alpha + beta) / 2; alpha = std::max(bestValue - delta, -VALUE_INFINITE); + failedHighCnt = 0; if (mainThread) - { - failedHighCnt = 0; mainThread->stopOnPonderhit = false; - } } else if (bestValue >= beta) { beta = std::min(bestValue + delta, VALUE_INFINITE); - if (mainThread) - ++failedHighCnt; + ++failedHighCnt; } else break; @@ -459,12 +512,12 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (314 + 9 * (mainThread->previousScore - bestValue)) / 581.0; + double fallingEval = (354 + 10 * (mainThread->previousScore - bestValue)) / 692.0; fallingEval = clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 10 * ONE_PLY < completedDepth ? 1.95 : 1.0; - double reduction = std::pow(mainThread->previousTimeReduction, 0.528) / timeReduction; + timeReduction = lastBestMoveDepth + 9 * ONE_PLY < completedDepth ? 1.97 : 0.98; + double reduction = (1.36 + mainThread->previousTimeReduction) / (2.29 * timeReduction); // Use part of the gained time from a previous stable move for the current move for (Thread* th : Threads) @@ -539,16 +592,16 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue; - bool ttHit, ttPv, inCheck, givesCheck, improving; + bool ttHit, ttPv, inCheck, givesCheck, improving, doLMR; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; - int moveCount, captureCount, quietCount; + int moveCount, captureCount, quietCount, singularLMR; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); inCheck = pos.checkers(); Color us = pos.side_to_move(); - moveCount = captureCount = quietCount = ss->moveCount = 0; + moveCount = captureCount = quietCount = singularLMR = ss->moveCount = 0; bestValue = -VALUE_INFINITE; maxValue = VALUE_INFINITE; @@ -584,8 +637,7 @@ namespace { assert(0 <= ss->ply && ss->ply < MAX_PLY); (ss+1)->ply = ss->ply + 1; - ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; - ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; + (ss+1)->excludedMove = bestMove = MOVE_NONE; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; Square prevSq = to_sq((ss-1)->currentMove); @@ -594,7 +646,10 @@ namespace { // starts with statScore = 0. Later grandchildren start with the last calculated // statScore of the previous grandchild. This influences the reduction rules in // LMR which are based on the statScore of parent position. - (ss+2)->statScore = 0; + if (rootNode) + (ss + 4)->statScore = 0; + else + (ss + 2)->statScore = 0; // Step 4. Transposition table lookup. We don't want the score of a partial // search to overwrite a previous full search TT value, so we use a different @@ -605,7 +660,7 @@ namespace { ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ttHit ? tte->move() : MOVE_NONE; - ttPv = (ttHit && tte->is_pv()) || (PvNode && depth > 4 * ONE_PLY); + ttPv = PvNode || (ttHit && tte->is_pv()); // if position has been searched at higher depths and we are shuffling, return value_draw if (pos.rule50_count() > 36 @@ -707,7 +762,7 @@ namespace { } else if (ttHit) { - // Never assume anything on values stored in TT + // Never assume anything about values stored in TT ss->staticEval = eval = tte->eval(); if (eval == VALUE_NONE) ss->staticEval = eval = evaluate(pos); @@ -750,9 +805,9 @@ namespace { // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 23200 + && (ss-1)->statScore < 22661 && eval >= beta - && ss->staticEval >= beta - 36 * depth / ONE_PLY + 225 + && ss->staticEval >= beta - 33 * depth / ONE_PLY + 299 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -760,7 +815,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 200, 3)) * ONE_PLY; + Depth R = ((835 + 70 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 185, 3)) * ONE_PLY; ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; @@ -777,7 +832,7 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 12 * ONE_PLY)) + if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 13 * ONE_PLY)) return nullValue; assert(!thisThread->nmpMinPly); // Recursive verification is not allowed @@ -803,7 +858,7 @@ namespace { && depth >= 5 * ONE_PLY && abs(beta) < VALUE_MATE_IN_MAX_PLY) { - Value raisedBeta = std::min(beta + 216 - 48 * improving, VALUE_INFINITE); + Value raisedBeta = std::min(beta + 191 - 46 * improving, VALUE_INFINITE); MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &thisThread->captureHistory); int probCutCount = 0; @@ -835,7 +890,7 @@ namespace { } // Step 11. Internal iterative deepening (~2 Elo) - if (depth >= 8 * ONE_PLY && !ttMove) + if (depth >= 7 * ONE_PLY && !ttMove) { search(pos, ss, alpha, beta, depth - 7 * ONE_PLY, cutNode); @@ -862,6 +917,9 @@ moves_loop: // When in check, search starts from here moveCountPruning = false; ttCapture = ttMove && pos.capture_or_promotion(ttMove); + // Mark this node as being searched. + ThreadHolding th(thisThread, posKey, ss->ply); + // Step 12. Loop through all pseudo-legal moves until no moves remain // or a beta cutoff occurs. while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE) @@ -900,11 +958,11 @@ moves_loop: // When in check, search starts from here // 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. - if ( depth >= 8 * ONE_PLY + if ( depth >= 6 * ONE_PLY && move == ttMove && !rootNode && !excludedMove // Avoid recursive singular search - /* && ttValue != VALUE_NONE Already implicit in the next condition */ + /* && ttValue != VALUE_NONE Already implicit in the next condition */ && abs(ttValue) < VALUE_KNOWN_WIN && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY @@ -917,20 +975,27 @@ moves_loop: // When in check, search starts from here ss->excludedMove = MOVE_NONE; if (value < singularBeta) + { extension = ONE_PLY; + singularLMR++; + + if (value < singularBeta - std::min(4 * depth / ONE_PLY, 36)) + singularLMR++; + } // Multi-cut pruning // Our ttMove is assumed to fail high, and now we failed high also on a reduced // search without the ttMove. So we assume this expected Cut-node is not singular, - // that is multiple moves fail high, and we can prune the whole subtree by returning - // the hard beta bound. - else if (cutNode && singularBeta > beta) - return beta; + // that multiple moves fail high, and we can prune the whole subtree by returning + // a soft bound. + else if ( eval >= beta + && singularBeta >= beta) + return singularBeta; } // Check extension (~2 Elo) else if ( givesCheck - && (pos.blockers_for_king(~us) & from_sq(move) || pos.see_ge(move))) + && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move))) extension = ONE_PLY; // Shuffle extension @@ -941,6 +1006,13 @@ moves_loop: // When in check, search starts from here else if (type_of(move) == CASTLING) extension = ONE_PLY; + // Shuffle extension + else if ( PvNode + && pos.rule50_count() > 18 + && depth < 3 * ONE_PLY + && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4) // To avoid too many extensions + extension = ONE_PLY; + // Passed pawn extension else if ( move == ss->killers[0] && pos.advanced_pawn_push(move) @@ -960,33 +1032,34 @@ moves_loop: // When in check, search starts from here if ( !captureOrPromotion && !givesCheck - && !pos.advanced_pawn_push(move)) + && (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg)) { - // Move count based pruning (~30 Elo) + // Move count based pruning if (moveCountPruning) continue; // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO); + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO); lmrDepth /= ONE_PLY; // Countermoves based pruning (~20 Elo) - if ( lmrDepth < 3 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) + if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) continue; // Futility pruning: parent node (~2 Elo) - if ( lmrDepth < 7 + if ( lmrDepth < 6 && !inCheck - && ss->staticEval + 256 + 200 * lmrDepth <= alpha) + && ss->staticEval + 250 + 211 * lmrDepth <= alpha) continue; // Prune moves with negative SEE (~10 Elo) - if (!pos.see_ge(move, Value(-29 * lmrDepth * lmrDepth))) + if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) continue; } - else if (!pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo) + else if ( (!givesCheck || !extension) + && !pos.see_ge(move, Value(-199) * (depth / ONE_PLY))) // (~20 Elo) continue; } @@ -1010,19 +1083,28 @@ moves_loop: // When in check, search starts from here // Step 16. Reduced depth search (LMR). If the move fails high it will be // re-searched at full depth. if ( depth >= 3 * ONE_PLY - && moveCount > 1 - && (!captureOrPromotion || moveCountPruning)) + && moveCount > 1 + 3 * rootNode + && ( !captureOrPromotion + || moveCountPruning + || ss->staticEval + PieceValue[EG][pos.captured_piece()] <= alpha)) { - Depth r = reduction(improving, depth, moveCount); + Depth r = reduction(improving, depth, moveCount); + + // Reduction if other threads are searching this position. + if (th.marked()) + r += ONE_PLY; // Decrease reduction if position is or has been on the PV if (ttPv) - r -= ONE_PLY; + r -= 2 * ONE_PLY; // Decrease reduction if opponent's move count is high (~10 Elo) if ((ss-1)->moveCount > 15) r -= ONE_PLY; + // Decrease reduction if move has been singularly extended + r -= singularLMR * ONE_PLY; + if (!captureOrPromotion) { // Increase reduction if ttMove is a capture (~0 Elo) @@ -1044,32 +1126,52 @@ moves_loop: // When in check, search starts from here + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 4000; + - 4729; + + // 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; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) - if (ss->statScore >= 0 && (ss-1)->statScore < 0) + if (ss->statScore >= -99 && (ss-1)->statScore < -116) r -= ONE_PLY; - else if ((ss-1)->statScore >= 0 && ss->statScore < 0) + else if ((ss-1)->statScore >= -117 && ss->statScore < -144) r += ONE_PLY; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 20000 * ONE_PLY; + r -= ss->statScore / 16384 * ONE_PLY; } - Depth d = std::max(newDepth - std::max(r, DEPTH_ZERO), ONE_PLY); + Depth d = clamp(newDepth - r, ONE_PLY, newDepth); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = (value > alpha && d != newDepth); + doFullDepthSearch = (value > alpha && d != newDepth), doLMR = true; } else - doFullDepthSearch = !PvNode || moveCount > 1; + doFullDepthSearch = !PvNode || moveCount > 1, doLMR = false; // Step 17. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) + { value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + if (doLMR && !captureOrPromotion) + { + int bonus = value > alpha ? stat_bonus(newDepth) + : -stat_bonus(newDepth); + + if (move == ss->killers[0]) + bonus += bonus / 4; + + update_continuation_histories(ss, movedPiece, to_sq(move), bonus); + } + } + // For PV nodes only, do a full PV search on the first move or after a fail // high (in the latter case search only if value < beta), otherwise let the // parent node fail low with value <= alpha and try another move. @@ -1208,8 +1310,8 @@ moves_loop: // When in check, search starts from here } - // qsearch() is the quiescence search function, which is called by the main - // search function with depth zero, or recursively with depth less than ONE_PLY. + // qsearch() is the quiescence search function, which is called by the main search + // function with zero depth, or recursively with further decreasing depth per call. template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { @@ -1280,7 +1382,7 @@ moves_loop: // When in check, search starts from here { if (ttHit) { - // Never assume anything on values stored in TT + // Never assume anything about values stored in TT if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); @@ -1307,7 +1409,7 @@ moves_loop: // When in check, search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 128; + futilityBase = bestValue + 153; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1363,6 +1465,7 @@ moves_loop: // When in check, search starts from here // Don't search moves with negative SEE values if ( (!inCheck || evasionPrunable) + && (!givesCheck || !(pos.blockers_for_king(~pos.side_to_move()) & from_sq(move))) && !pos.see_ge(move)) continue; @@ -1473,7 +1576,7 @@ moves_loop: // When in check, search starts from here void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCount, int bonus) { - CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory; + CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory; Piece moved_piece = pos.moved_piece(move); PieceType captured = type_of(pos.piece_on(to_sq(move))); @@ -1714,7 +1817,7 @@ void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) { } else { - // Assign the same rank to all moves + // Clean up if root_probe() and root_probe_wdl() have failed for (auto& m : rootMoves) m.tbRank = 0; } diff --git a/src/search.h b/src/search.h index 92e124fc..24c58d30 100644 --- a/src/search.h +++ b/src/search.h @@ -69,7 +69,7 @@ struct RootMove { Value score = -VALUE_INFINITE; Value previousScore = -VALUE_INFINITE; int selDepth = 0; - int tbRank; + int tbRank = 0; Value tbScore; std::vector pv; }; diff --git a/src/syzygy/tbprobe.cpp b/src/syzygy/tbprobe.cpp index 3dbe18fb..a5b10f81 100644 --- a/src/syzygy/tbprobe.cpp +++ b/src/syzygy/tbprobe.cpp @@ -367,7 +367,7 @@ TBTable::TBTable(const std::string& code) : TBTable() { hasPawns = pos.pieces(PAWN); hasUniquePieces = false; - for (Color c = WHITE; c <= BLACK; ++c) + for (Color c : {WHITE, BLACK}) for (PieceType pt = PAWN; pt < KING; ++pt) if (popcount(pos.pieces(c, pt)) == 1) hasUniquePieces = true; diff --git a/src/thread.cpp b/src/thread.cpp index f216c321..e5043b6e 100644 --- a/src/thread.cpp +++ b/src/thread.cpp @@ -20,6 +20,7 @@ #include +#include // For std::count #include "movegen.h" #include "search.h" #include "thread.h" @@ -190,7 +191,7 @@ void ThreadPool::start_thinking(Position& pos, StateListPtr& states, for (Thread* th : *this) { - th->nodes = th->tbHits = th->nmpMinPly = 0; + th->shuffleExts = th->nodes = th->tbHits = th->nmpMinPly = 0; th->rootDepth = th->completedDepth = DEPTH_ZERO; th->rootMoves = rootMoves; th->rootPos.set(pos.fen(), pos.is_chess960(), &setupStates->back(), th); diff --git a/src/thread.h b/src/thread.h index 7a27aab1..c11d1787 100644 --- a/src/thread.h +++ b/src/thread.h @@ -59,8 +59,7 @@ public: Pawns::Table pawnsTable; Material::Table materialTable; - Endgames endgames; - size_t pvIdx, pvLast; + size_t pvIdx, pvLast, shuffleExts; int selDepth, nmpMinPly; Color nmpColor; std::atomic nodes, tbHits, bestMoveChanges; diff --git a/src/timeman.cpp b/src/timeman.cpp index fafde2aa..484aaa65 100644 --- a/src/timeman.cpp +++ b/src/timeman.cpp @@ -18,6 +18,7 @@ along with this program. If not, see . */ +#include #include #include diff --git a/src/tt.cpp b/src/tt.cpp index 33768ca4..6121b3ad 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -43,14 +43,16 @@ void TTEntry::save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev) // Overwrite less valuable entries if ( (k >> 48) != key16 - || d / ONE_PLY > depth8 - 4 + ||(d - DEPTH_OFFSET) / ONE_PLY > depth8 - 4 || b == BOUND_EXACT) { + assert((d - DEPTH_OFFSET) / ONE_PLY >= 0); + key16 = (uint16_t)(k >> 48); value16 = (int16_t)v; eval16 = (int16_t)ev; genBound8 = (uint8_t)(TT.generation8 | uint8_t(pv) << 2 | b); - depth8 = (int8_t)(d / ONE_PLY); + depth8 = (uint8_t)((d - DEPTH_OFFSET) / ONE_PLY); } } diff --git a/src/tt.h b/src/tt.h index fefc8e2c..3a5ba5da 100644 --- a/src/tt.h +++ b/src/tt.h @@ -40,7 +40,7 @@ struct TTEntry { Move move() const { return (Move )move16; } Value value() const { return (Value)value16; } Value eval() const { return (Value)eval16; } - Depth depth() const { return (Depth)(depth8 * int(ONE_PLY)); } + Depth depth() const { return (Depth)(depth8 * int(ONE_PLY)) + DEPTH_OFFSET; } 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); @@ -53,7 +53,7 @@ private: int16_t value16; int16_t eval16; uint8_t genBound8; - int8_t depth8; + uint8_t depth8; }; diff --git a/src/types.h b/src/types.h index 2e36279d..b0c333b8 100644 --- a/src/types.h +++ b/src/types.h @@ -101,7 +101,7 @@ typedef uint64_t Key; typedef uint64_t Bitboard; constexpr int MAX_MOVES = 256; -constexpr int MAX_PLY = 128; +constexpr int MAX_PLY = 246; /// A move needs 16 bits to be stored /// @@ -213,8 +213,9 @@ enum Depth : int { DEPTH_QS_NO_CHECKS = -1 * ONE_PLY, DEPTH_QS_RECAPTURES = -5 * ONE_PLY, - DEPTH_NONE = -6 * ONE_PLY, - DEPTH_MAX = MAX_PLY * ONE_PLY + DEPTH_NONE = -6 * ONE_PLY, + DEPTH_OFFSET = DEPTH_NONE, + DEPTH_MAX = MAX_PLY * ONE_PLY }; static_assert(!(ONE_PLY & (ONE_PLY - 1)), "ONE_PLY is not a power of 2"); @@ -290,7 +291,6 @@ inline T& operator--(T& d) { return d = T(int(d) - 1); } #define ENABLE_FULL_OPERATORS_ON(T) \ ENABLE_BASE_OPERATORS_ON(T) \ -ENABLE_INCR_OPERATORS_ON(T) \ constexpr T operator*(int i, T d) { return T(i * int(d)); } \ constexpr T operator*(T d, int i) { return T(int(d) * i); } \ constexpr T operator/(T d, int i) { return T(int(d) / i); } \ @@ -304,7 +304,6 @@ ENABLE_FULL_OPERATORS_ON(Direction) ENABLE_INCR_OPERATORS_ON(PieceType) ENABLE_INCR_OPERATORS_ON(Piece) -ENABLE_INCR_OPERATORS_ON(Color) ENABLE_INCR_OPERATORS_ON(Square) ENABLE_INCR_OPERATORS_ON(File) ENABLE_INCR_OPERATORS_ON(Rank) diff --git a/src/uci.cpp b/src/uci.cpp index 739cf343..a4235f2b 100644 --- a/src/uci.cpp +++ b/src/uci.cpp @@ -164,7 +164,7 @@ namespace { } else if (token == "setoption") setoption(is); else if (token == "position") position(pos, is, states); - else if (token == "ucinewgame") Search::clear(); + else if (token == "ucinewgame") { Search::clear(); elapsed = now(); } // Search::clear() may take some while } elapsed = now() - elapsed + 1; // Ensure positivity to avoid a 'divide by zero' diff --git a/src/ucioption.cpp b/src/ucioption.cpp index 8b75eea9..ea370106 100644 --- a/src/ucioption.cpp +++ b/src/ucioption.cpp @@ -18,6 +18,7 @@ along with this program. If not, see . */ +#include #include #include #include @@ -81,6 +82,8 @@ void init(OptionsMap& o) { 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["SyzygyPath"] << Option("", on_tb_path); o["SyzygyProbeDepth"] << Option(1, 1, 100); o["Syzygy50MoveRule"] << Option(true);