Skip to content

Commit 062ca91

Browse files
mstemberazamar
mstembera
authored and
zamar
committed
New easy move implementation
Spend much less time in positions where one move is much better than all other alternatives. We carry forward pv stability information from the previous search to identify such positions. It's based on my old InstaMove idea but with two significant improvements. 1) Much better instability detection inside the search itself. 2) When it's time to make a FastMove we no longer make it instantly but still spend at least 10% of normal time verifying it. Credit to Gull for the inspiration. BIG thanks to Gary because this would not work without accurate PV! 20K ELO: 8.22 +-3.0 (95%) LOS: 100.0% Total: 20000 W: 4203 L: 3730 D: 12067 STC LLR: 2.96 (-2.94,2.94) [-1.50,4.50] Total: 23266 W: 4662 L: 4492 D: 14112 LTC LLR: 2.95 (-2.94,2.94) [0.00,6.00] Total: 12470 W: 2091 L: 1931 D: 8448 Resolves official-stockfish#283
1 parent 13c11f4 commit 062ca91

2 files changed

Lines changed: 79 additions & 16 deletions

File tree

‎src/search.cpp‎

Lines changed: 78 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -90,6 +90,45 @@ namespace {
9090
Move best = MOVE_NONE;
9191
};
9292

93+
struct FastMove {
94+
FastMove() { clear(); }
95+
96+
inline void clear() {
97+
expectedPosKey = 0;
98+
pv3[0] = pv3[1] = pv3[2] = MOVE_NONE;
99+
stableCnt = 0;
100+
}
101+
102+
void update(Position& pos) {
103+
// Keep track how many times in a row the PV stays stable 3 ply deep.
104+
const std::vector<Move>& RMpv = RootMoves[0].pv;
105+
if (RMpv.size() >= 3)
106+
{
107+
if (pv3[2] == RMpv[2])
108+
stableCnt++;
109+
else
110+
stableCnt = 0, pv3[2] = RMpv[2];
111+
112+
if (!expectedPosKey || pv3[0] != RMpv[0] || pv3[1] != RMpv[1])
113+
{
114+
pv3[0] = RMpv[0], pv3[1] = RMpv[1];
115+
StateInfo st[2];
116+
pos.do_move(RMpv[0], st[0], pos.gives_check(RMpv[0], CheckInfo(pos)));
117+
pos.do_move(RMpv[1], st[1], pos.gives_check(RMpv[1], CheckInfo(pos)));
118+
expectedPosKey = pos.key();
119+
pos.undo_move(RMpv[1]);
120+
pos.undo_move(RMpv[0]);
121+
}
122+
}
123+
else
124+
clear();
125+
}
126+
127+
Key expectedPosKey;
128+
Move pv3[3];
129+
int stableCnt;
130+
} FM;
131+
93132
size_t PVIdx;
94133
TimeManager TimeMgr;
95134
double BestMoveChanges;
@@ -281,6 +320,10 @@ namespace {
281320
Depth depth;
282321
Value bestValue, alpha, beta, delta;
283322

323+
// Init fastMove if the previous search generated a candidate and we now got the predicted position.
324+
const Move fastMove = (FM.expectedPosKey == pos.key()) ? FM.pv3[2] : MOVE_NONE;
325+
FM.clear();
326+
284327
std::memset(ss-2, 0, 5 * sizeof(Stack));
285328

286329
depth = DEPTH_ZERO;
@@ -405,27 +448,43 @@ namespace {
405448
Signals.stop = true;
406449

407450
// Do we have time for the next iteration? Can we stop searching now?
408-
if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit)
451+
if (Limits.use_time_management())
409452
{
410-
// Take some extra time if the best move has changed
411-
if (depth > 4 * ONE_PLY && multiPV == 1)
412-
TimeMgr.pv_instability(BestMoveChanges);
413-
414-
// Stop the search if only one legal move is available or all
415-
// of the available time has been used.
416-
if ( RootMoves.size() == 1
417-
|| now() - SearchTime > TimeMgr.available_time())
453+
if (!Signals.stop && !Signals.stopOnPonderhit)
418454
{
419-
// If we are allowed to ponder do not stop the search now but
420-
// keep pondering until the GUI sends "ponderhit" or "stop".
421-
if (Limits.ponder)
422-
Signals.stopOnPonderhit = true;
423-
else
424-
Signals.stop = true;
455+
// Take some extra time if the best move has changed
456+
if (depth > 4 * ONE_PLY && multiPV == 1)
457+
TimeMgr.pv_instability(BestMoveChanges);
458+
459+
// Stop the search if only one legal move is available or all
460+
// of the available time has been used or we matched a fastMove
461+
// from the previous search and just did a fast verification.
462+
if ( RootMoves.size() == 1
463+
|| now() - SearchTime > TimeMgr.available_time()
464+
|| ( fastMove == RootMoves[0].pv[0]
465+
&& BestMoveChanges < 0.03
466+
&& 10 * (now() - SearchTime) > TimeMgr.available_time()))
467+
{
468+
// If we are allowed to ponder do not stop the search now but
469+
// keep pondering until the GUI sends "ponderhit" or "stop".
470+
if (Limits.ponder)
471+
Signals.stopOnPonderhit = true;
472+
else
473+
Signals.stop = true;
474+
}
425475
}
476+
477+
// Update fast move stats.
478+
FM.update(pos);
426479
}
427480
}
428481

482+
// Clear any candidate fast move that wasn't completely stable for at least
483+
// the 6 final search iterations. (Independent of actual depth and thus TC.)
484+
// Time condition prevents consecutive fast moves.
485+
if (FM.stableCnt < 6 || now() - SearchTime < TimeMgr.available_time())
486+
FM.clear();
487+
429488
// If skill level is enabled, swap best PV line with the sub-optimal one
430489
if (skill.enabled())
431490
std::swap(RootMoves[0], *std::find(RootMoves.begin(),
@@ -1012,6 +1071,10 @@ namespace {
10121071

10131072
if (value > alpha)
10141073
{
1074+
// Clear fast move if unstable.
1075+
if (PvNode && pos.key() == FM.expectedPosKey && (move != FM.pv3[2] || moveCount > 1))
1076+
FM.clear();
1077+
10151078
bestMove = SpNode ? splitPoint->bestMove = move : move;
10161079

10171080
if (PvNode && !RootNode) // Update pv even in fail-high case

‎src/timeman.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,7 @@ class TimeManager {
2727
public:
2828
void init(const Search::LimitsType& limits, Color us, int ply);
2929
void pv_instability(double bestMoveChanges) { unstablePvFactor = 1 + bestMoveChanges; }
30-
int available_time() const { return int(optimumSearchTime * unstablePvFactor * 0.71); }
30+
int available_time() const { return int(optimumSearchTime * unstablePvFactor * 0.76); }
3131
int maximum_time() const { return maximumSearchTime; }
3232

3333
private:

0 commit comments

Comments
 (0)