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=-c Merge remote-tracking branch 'upstream/master' --- d4062bbfa6c71e23fc6fb3f04e043409e8e41df7 diff --combined src/Makefile index 1314092e,285d314e..42e4118b --- a/src/Makefile +++ b/src/Makefile @@@ -38,9 -38,7 +38,9 @@@ PGOBENCH = ./$(EXE) benc ### 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 + 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 ### Establish the operating system name KERNEL = $(shell uname -s) @@@ -138,6 -136,8 +138,8 @@@ endi ifeq ($(ARCH),ppc-64) arch = ppc64 bits = 64 + popcnt = yes + prefetch = yes endif @@@ -158,7 -158,7 +160,7 @@@ endi ifeq ($(COMP),gcc) comp=gcc CXX=g++ - CXXFLAGS += -pedantic -Wextra -Wshadow + CXXFLAGS += -pedantic -Wextra ifeq ($(ARCH),armv7) ifeq ($(OS),Android) @@@ -283,7 -283,7 +285,7 @@@ endi ### 3.3 Optimization ifeq ($(optimize),yes) - CXXFLAGS += -O3 + CXXFLAGS += -O3 -g ifeq ($(comp),gcc) ifeq ($(OS), Android) @@@ -315,7 -315,9 +317,9 @@@ endi ### 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 @@@ -458,7 -460,7 +462,7 @@@ default ### Section 5. Private targets ### ========================================================================== -all: $(EXE) .depend +all: $(EXE) client .depend config-sanity: @echo "" @@@ -483,7 -485,7 +487,7 @@@ @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" @@@ -533,34 -535,8 +537,34 @@@ icc-profile-use EXTRACXXFLAGS='-prof_use -prof_dir ./profdir' \ all +### GRPC + +PROTOS_PATH = . +PROTOC = protoc +GRPC_CPP_PLUGIN = grpc_cpp_plugin +GRPC_CPP_PLUGIN_PATH ?= `which $(GRPC_CPP_PLUGIN)` + +%.grpc.pb.h %.grpc.pb.cc: %.proto + $(PROTOC) -I $(PROTOS_PATH) --grpc_out=. --plugin=protoc-gen-grpc=$(GRPC_CPP_PLUGIN_PATH) $< + +# oh my +%.cpp: %.cc + cp $< $@ + +%.pb.h %.pb.cc: %.proto + $(PROTOC) -I $(PROTOS_PATH) --cpp_out=. $< + +#LDFLAGS += -Wl,-Bstatic -Wl,-\( -lprotobuf -lgrpc++_unsecure -lgrpc_unsecure -lgrpc -lz -Wl,-\) -Wl,-Bdynamic -ldl +LDFLAGS += /usr/lib/x86_64-linux-gnu/libprotobuf.a /usr/lib/x86_64-linux-gnu/libgrpc++_unsecure.a /usr/lib/x86_64-linux-gnu/libgrpc_unsecure.a /usr/lib/x86_64-linux-gnu/libgrpc.a /usr/lib/x86_64-linux-gnu/libcares.a -ldl -lz +#LDFLAGS += /usr/lib/x86_64-linux-gnu/libprotobuf.a /usr/lib/libgrpc++_unsecure.a /usr/lib/libgrpc_unsecure.a /usr/lib/libgrpc.a /usr/lib/x86_64-linux-gnu/libcares.a -ldl -lz + +client: $(CLIOBJS) + $(CXX) -o $@ $(CLIOBJS) $(LDFLAGS) + +# Other stuff + .depend: - -@$(CXX) $(DEPENDFLAGS) -MM $(OBJS:.o=.cpp) > $@ 2> /dev/null + -@$(CXX) $(DEPENDFLAGS) -MM $(OBJS:.o=.cpp) $(OBJS:.o=.cc) > $@ 2> /dev/null -include .depend diff --combined src/main.cpp index b9d2dfb4,f94a322c..88d46117 --- a/src/main.cpp +++ b/src/main.cpp @@@ -18,10 -18,7 +18,10 @@@ along with this program. If not, see . */ +#include #include +#include +#include #include "bitboard.h" #include "position.h" @@@ -29,199 -26,9 +29,200 @@@ #include "thread.h" #include "tt.h" #include "uci.h" + #include "endgame.h" #include "syzygy/tbprobe.h" +#include +#include +#include +#include "hashprobe.h" +#include "hashprobe.grpc.pb.h" +#include "tt.h" + +using grpc::Server; +using grpc::ServerBuilder; +using grpc::ServerContext; +using grpc::Status; +using grpc::StatusCode; +using namespace hashprobe; + +Status HashProbeImpl::Probe(ServerContext* context, + const HashProbeRequest* request, + HashProbeResponse *response) { + Position pos; + StateInfo st; + pos.set(request->fen(), /*isChess960=*/false, &st, Threads.main()); + if (!pos.pos_is_ok()) { + return Status(StatusCode::INVALID_ARGUMENT, "Invalid FEN"); + } + + bool invert = (pos.side_to_move() == BLACK); + StateListPtr setup_states = StateListPtr(new std::deque(1)); + + ProbeMove(&pos, setup_states.get(), invert, response->mutable_root()); + + MoveList moves(pos); + for (const ExtMove* em = moves.begin(); em != moves.end(); ++em) { + HashProbeLine *line = response->add_line(); + FillMove(&pos, em->move, line->mutable_move()); + setup_states->push_back(StateInfo()); + pos.do_move(em->move, setup_states->back()); + ProbeMove(&pos, setup_states.get(), !invert, line); + pos.undo_move(em->move); + } + + return Status::OK; +} + +void HashProbeImpl::FillMove(Position *pos, Move move, HashProbeMove* decoded) { + if (!is_ok(move)) return; + + Square from = from_sq(move); + Square to = to_sq(move); + + if (type_of(move) == CASTLING) { + to = make_square(to > from ? FILE_G : FILE_C, rank_of(from)); + } + + Piece moved_piece = pos->moved_piece(move); + std::string pretty; + if (type_of(move) == CASTLING) { + if (to > from) { + pretty = "O-O"; + } else { + pretty = "O-O-O"; + } + } else if (type_of(moved_piece) == PAWN) { + if (type_of(move) == ENPASSANT || pos->piece_on(to) != NO_PIECE) { + // Capture. + pretty = char('a' + file_of(from)); + pretty += "x"; + } + pretty += UCI::square(to); + if (type_of(move) == PROMOTION) { + pretty += "="; + pretty += " PNBRQK"[promotion_type(move)]; + } + } else { + pretty = " PNBRQK"[type_of(moved_piece)]; + Bitboard attackers = pos->attackers_to(to) & pos->pieces(color_of(moved_piece), type_of(moved_piece)); + if (more_than_one(attackers)) { + // Remove all illegal moves to disambiguate. + Bitboard att_copy = attackers; + while (att_copy) { + Square s = pop_lsb(&att_copy); + Move m = make_move(s, to); + if (!pos->pseudo_legal(m) || !pos->legal(m)) { + attackers &= ~SquareBB[s]; + } + } + } + if (more_than_one(attackers)) { + // Disambiguate by file if possible. + Bitboard attackers_this_file = attackers & file_bb(file_of(from)); + if (attackers != attackers_this_file) { + pretty += char('a' + file_of(from)); + attackers = attackers_this_file; + } + if (more_than_one(attackers)) { + // Still ambiguous, so need to disambiguate by rank. + pretty += char('1' + rank_of(from)); + } + } + + if (type_of(move) == ENPASSANT || pos->piece_on(to) != NO_PIECE) { + pretty += "x"; + } + + pretty += UCI::square(to); + } + + if (pos->gives_check(move)) { + // Check if mate. + StateInfo si; + pos->do_move(move, si, true); + if (MoveList(*pos).size() > 0) { + pretty += "+"; + } else { + pretty += "#"; + } + pos->undo_move(move); + } + + decoded->set_pretty(pretty); +} + +void HashProbeImpl::ProbeMove(Position* pos, std::deque* setup_states, bool invert, HashProbeLine* response) { + bool found; + TTEntry *entry = TT.probe(pos->key(), found); + response->set_found(found); + if (found) { + Value value = entry->value(); + Value eval = entry->eval(); + Bound bound = entry->bound(); + + if (invert) { + value = -value; + eval = -eval; + if (bound == BOUND_UPPER) { + bound = BOUND_LOWER; + } else if (bound == BOUND_LOWER) { + bound = BOUND_UPPER; + } + } + + response->set_depth(entry->depth()); + FillValue(eval, response->mutable_eval()); + if (entry->depth() > DEPTH_NONE) { + FillValue(value, response->mutable_value()); + } + response->set_bound(HashProbeLine::ValueBound(bound)); + + // Follow the PV until we hit an illegal move. + std::stack pv; + std::set seen; + while (found && is_ok(entry->move()) && + pos->pseudo_legal(entry->move()) && + pos->legal(entry->move())) { + FillMove(pos, entry->move(), response->add_pv()); + if (seen.count(pos->key())) break; + pv.push(entry->move()); + seen.insert(pos->key()); + setup_states->push_back(StateInfo()); + pos->do_move(entry->move(), setup_states->back()); + entry = TT.probe(pos->key(), found); + } + + // Unroll the PV back again, so the Position object remains unchanged. + while (!pv.empty()) { + pos->undo_move(pv.top()); + pv.pop(); + } + } +} + +void HashProbeImpl::FillValue(Value value, HashProbeScore* score) { + if (abs(value) < VALUE_MATE - MAX_PLY) { + score->set_score_type(HashProbeScore::SCORE_CP); + score->set_score_cp(value * 100 / PawnValueEg); + } else { + score->set_score_type(HashProbeScore::SCORE_MATE); + score->set_score_mate((value > 0 ? VALUE_MATE - value + 1 : -VALUE_MATE - value) / 2); + } +} + +HashProbeThread::HashProbeThread(const std::string &server_address) { + builder.AddListeningPort(server_address, grpc::InsecureServerCredentials()); + builder.RegisterService(&service); + server = std::move(builder.BuildAndStart()); + std::cout << "Server listening on " << server_address << std::endl; + std::thread([this]{ server->Wait(); }).detach(); +} + +void HashProbeThread::Shutdown() { + server->Shutdown(); +} + namespace PSQT { void init(); } @@@ -235,6 -42,7 +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 --combined src/misc.cpp index bca48876,b1539ce2..43a73b28 --- a/src/misc.cpp +++ b/src/misc.cpp @@@ -133,7 -133,6 +133,7 @@@ const string engine_info(bool to_uci) { date >> month >> day >> year; ss << setw(2) << day << setw(2) << (1 + months.find(month) / 4) << year.substr(2); + ss << "-asn"; } ss << (Is64Bit ? " 64" : "") @@@ -146,7 -145,7 +146,7 @@@ /// 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 -210,6 +211,6 @@@ void prefetch(void* addr) #endif - void prefetch2(void* addr) { - - prefetch(addr); - prefetch((uint8_t*)addr + 64); - } - namespace WinProcGroup { #ifndef _WIN32 diff --combined src/position.cpp index ed5cc43f,fbde810b..3310460f --- a/src/position.cpp +++ b/src/position.cpp @@@ -18,6 -18,7 +18,7 @@@ along with this program. If not, see . */ + #include #include #include // For offsetof() #include // For std::memset, std::memcmp @@@ -54,13 -55,13 +55,13 @@@ constexpr Piece Pieces[] = { W_PAWN, W_ // 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 +77,7 @@@ // 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<> @@@ -317,6 -318,8 +318,6 @@@ Position& Position::set(const string& f thisThread = th; set_state(st); - assert(pos_is_ok()); - return *this; } @@@ -338,8 -341,8 +339,8 @@@ void Position::set_castling_right(Colo 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 -383,12 +381,12 @@@ void Position::set_state(StateInfo* si 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 -399,9 +397,9 @@@ 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 -491,7 +489,7 @@@ Bitboard Position::slider_blockers(Bitb // 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 -855,6 +853,6 @@@ void Position::do_move(Move m, StateInf // 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 -874,25 +872,25 @@@ // 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 -1008,8 +1006,8 @@@ void Position::do_null_move(StateInfo& set_check_info(st); + st->repetition = 0; + assert(pos_is_ok()); } @@@ -1115,24 -1133,10 +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 -1148,15 +1146,15 @@@ 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 -1189,19 +1187,19 @@@ bool Position::has_game_cycle(int ply) 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 -1299,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 --combined src/search.cpp index 95b14021,98419b20..53f61a97 --- a/src/search.cpp +++ b/src/search.cpp @@@ -18,6 -18,7 +18,7 @@@ along with this program. If not, see . */ + #include #include #include #include // For std::memset @@@ -61,17 -62,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 +82,7 @@@ // 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 +102,48 @@@ 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 +190,8 @@@ 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 +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 +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 +409,15 @@@ 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 +461,14 @@@ 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 +512,12 @@@ && !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 +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 +637,7 @@@ 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 +646,10 @@@ // 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,17 -660,8 +660,17 @@@ 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 + && ss->ply > 36 + && depth < 3 * ONE_PLY + && ttHit + && tte->depth() > depth + && pos.count() > 0) + return VALUE_DRAW; + // At non-PV nodes we check for an early TT cutoff if ( !PvNode && ttHit @@@ -707,7 -753,7 +762,7 @@@ } 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 -796,9 +805,9 @@@ // 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 -806,7 +815,7 @@@ 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 -823,7 +832,7 @@@ 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 -849,7 +858,7 @@@ && 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 -881,7 +890,7 @@@ } // 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 -908,9 +917,9 @@@ moves_loop: // When in check, search st 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 -949,11 +958,11 @@@ // 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,30 -966,40 +975,44 @@@ 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 + else if(pos.rule50_count() > 14 && ss->ply > 14 && depth < 3 * ONE_PLY && PvNode) + extension = ONE_PLY; + // Castling extension 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 -1019,34 +1032,34 @@@ 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 -1070,28 +1083,28 @@@ // 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 -1113,52 +1126,52 @@@ + (*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 -1297,8 +1310,8 @@@ } - // 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 -1369,7 +1382,7 @@@ { 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 -1396,7 +1409,7 @@@ if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 128; + futilityBase = bestValue + 153; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@@ -1363,6 -1452,7 +1465,7 @@@ // 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 -1563,7 +1576,7 @@@ 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 -1804,7 +1817,7 @@@ void Tablebases::rank_root_moves(Positi } 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 --combined src/syzygy/tbprobe.cpp index 3dbe18fb,90c86388..a5b10f81 --- a/src/syzygy/tbprobe.cpp +++ b/src/syzygy/tbprobe.cpp @@@ -74,7 -74,7 +74,7 @@@ int MapB1H1H7[SQUARE_NB] int MapA1D1D4[SQUARE_NB]; int MapKK[10][SQUARE_NB]; // [MapA1D1D4][SQUARE_NB] -int Binomial[6][SQUARE_NB]; // [k][n] k elements from a set of n elements +int Binomial[7][SQUARE_NB]; // [k][n] k elements from a set of n elements int LeadPawnIdx[6][SQUARE_NB]; // [leadPawnsCnt][SQUARE_NB] int LeadPawnsSize[6][4]; // [leadPawnsCnt][FILE_A..FILE_D] @@@ -367,7 -367,7 +367,7 @@@ TBTable::TBTable(const std::string 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; @@@ -1311,7 -1311,7 +1311,7 @@@ void Tablebases::init(const std::string Binomial[0][0] = 1; for (int n = 1; n < 64; n++) // Squares - for (int k = 0; k < 6 && k <= n; ++k) // Pieces + for (int k = 0; k < 7 && k <= n; ++k) // Pieces Binomial[k][n] = (k > 0 ? Binomial[k - 1][n - 1] : 0) + (k < n ? Binomial[k ][n - 1] : 0); diff --combined src/ucioption.cpp index 8b75eea9,23c0c480..ea370106 --- a/src/ucioption.cpp +++ b/src/ucioption.cpp @@@ -18,6 -18,7 +18,7 @@@ along with this program. If not, see . */ + #include #include #include #include @@@ -27,13 -28,11 +28,13 @@@ #include "thread.h" #include "tt.h" #include "uci.h" +#include "hashprobe.h" #include "syzygy/tbprobe.h" using std::string; UCI::OptionsMap Options; // Global object +std::unique_ptr hash_probe_thread; namespace UCI { @@@ -43,13 -42,7 +44,13 @@@ void on_hash_size(const Option& o) { TT void on_logger(const Option& o) { start_logger(o); } void on_threads(const Option& o) { Threads.set(o); } void on_tb_path(const Option& o) { Tablebases::init(o); } - +void on_rpc_server_address(const Option& o) { + if (hash_probe_thread) { + hash_probe_thread->Shutdown(); + } + std::string addr = o; + hash_probe_thread.reset(new HashProbeThread(addr)); +} /// Our case insensitive less() function as required by UCI protocol bool CaseInsensitiveLess::operator() (const string& s1, const string& s2) const { @@@ -81,11 -74,12 +82,13 @@@ 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); o["SyzygyProbeLimit"] << Option(7, 0, 7); + o["RPCServerAddress"] << Option("", on_rpc_server_address); }