Follow Don Dailey definition of cut/all node:
"If the previous node was a cut node, we consider this an ALL node.
The only exception is for PV nodes which are a special case of ALL nodes.
In the PVS framework, the first zero width window searched from a PV
node is by our definition a CUT node and if you have to do a re-search
then it is suddenly promoted to a PV nodes (as per PVS search) and only
then can the cut and all nodes swap positions. In other words, these
internal search failures can force the status of every node in the subtree
to swap if it propagates back to the last PV nodes."
http://talkchess.com/forum/viewtopic.php?topic_view=threads&p=519741&t=47577
With this definition we have an hit rate higher than 90% on:
if (!PvNode && depth > 4 * ONE_PLY)
dbg_hit_on_c(cutNode, (bestValue >= beta));
And an hit rate of just 28% on:
if (!PvNode && depth > 4 * ONE_PLY)
dbg_hit_on_c(!cutNode, (bestValue >= beta));
No functional change.
CountermovesStats Countermoves;
template <NodeType NT>
CountermovesStats Countermoves;
template <NodeType NT>
- Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
+ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode);
template <NodeType NT, bool InCheck>
Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
template <NodeType NT, bool InCheck>
Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
// research with bigger window until not failing high/low anymore.
while (true)
{
// research with bigger window until not failing high/low anymore.
while (true)
{
- bestValue = search<Root>(pos, ss, alpha, beta, depth * ONE_PLY);
+ bestValue = search<Root>(pos, ss, alpha, beta, depth * ONE_PLY, false);
// Bring to front the best move. It is critical that sorting is
// done with a stable algorithm because all the values but the first
// Bring to front the best move. It is critical that sorting is
// done with a stable algorithm because all the values but the first
Value rBeta = bestValue - 2 * PawnValueMg;
ss->excludedMove = RootMoves[0].pv[0];
ss->skipNullMove = true;
Value rBeta = bestValue - 2 * PawnValueMg;
ss->excludedMove = RootMoves[0].pv[0];
ss->skipNullMove = true;
- Value v = search<NonPV>(pos, ss, rBeta - 1, rBeta, (depth - 3) * ONE_PLY);
+ Value v = search<NonPV>(pos, ss, rBeta - 1, rBeta, (depth - 3) * ONE_PLY, true);
ss->skipNullMove = false;
ss->excludedMove = MOVE_NONE;
ss->skipNullMove = false;
ss->excludedMove = MOVE_NONE;
// here: This is taken care of after we return from the split point.
template <NodeType NT>
// here: This is taken care of after we return from the split point.
template <NodeType NT>
- Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) {
+ Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) {
const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot);
const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot);
const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot);
const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot);
pos.do_null_move(st);
(ss+1)->skipNullMove = true;
nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
pos.do_null_move(st);
(ss+1)->skipNullMove = true;
nullValue = depth-R < ONE_PLY ? -qsearch<NonPV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
- : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R);
+ : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R, !cutNode);
(ss+1)->skipNullMove = false;
pos.undo_null_move();
(ss+1)->skipNullMove = false;
pos.undo_null_move();
// Do verification search at high depths
ss->skipNullMove = true;
// Do verification search at high depths
ss->skipNullMove = true;
- Value v = search<NonPV>(pos, ss, alpha, beta, depth-R);
+ Value v = search<NonPV>(pos, ss, alpha, beta, depth-R, false);
ss->skipNullMove = false;
if (v >= beta)
ss->skipNullMove = false;
if (v >= beta)
{
ss->currentMove = move;
pos.do_move(move, st, ci, pos.move_gives_check(move, ci));
{
ss->currentMove = move;
pos.do_move(move, st, ci, pos.move_gives_check(move, ci));
- value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth);
+ value = -search<NonPV>(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode);
pos.undo_move(move);
if (value >= rbeta)
return value;
pos.undo_move(move);
if (value >= rbeta)
return value;
Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4);
ss->skipNullMove = true;
Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4);
ss->skipNullMove = true;
- search<PvNode ? PV : NonPV>(pos, ss, alpha, beta, d);
+ search<PvNode ? PV : NonPV>(pos, ss, alpha, beta, d, true);
ss->skipNullMove = false;
tte = TT.probe(posKey);
ss->skipNullMove = false;
tte = TT.probe(posKey);
Value rBeta = ttValue - int(depth);
ss->excludedMove = move;
ss->skipNullMove = true;
Value rBeta = ttValue - int(depth);
ss->excludedMove = move;
ss->skipNullMove = true;
- value = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2);
+ value = search<NonPV>(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode);
ss->skipNullMove = false;
ss->excludedMove = MOVE_NONE;
ss->skipNullMove = false;
ss->excludedMove = MOVE_NONE;
if (SpNode)
alpha = splitPoint->alpha;
if (SpNode)
alpha = splitPoint->alpha;
- value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d);
+ value = -search<NonPV>(pos, ss+1, -(alpha+1), -alpha, d, true);
doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO);
ss->reduction = DEPTH_ZERO;
doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO);
ss->reduction = DEPTH_ZERO;
value = newDepth < ONE_PLY ?
givesCheck ? -qsearch<NonPV, true>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
: -qsearch<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
value = newDepth < ONE_PLY ?
givesCheck ? -qsearch<NonPV, true>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
: -qsearch<NonPV, false>(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO)
- : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth);
+ : - search<NonPV>(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode);
}
// Only for PV nodes do a full PV search on the first move or after a fail
}
// Only for PV nodes do a full PV search on the first move or after a fail
value = newDepth < ONE_PLY ?
givesCheck ? -qsearch<PV, true>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
: -qsearch<PV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
value = newDepth < ONE_PLY ?
givesCheck ? -qsearch<PV, true>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
: -qsearch<PV, false>(pos, ss+1, -beta, -alpha, DEPTH_ZERO)
- : - search<PV>(pos, ss+1, -beta, -alpha, newDepth);
+ : - search<PV>(pos, ss+1, -beta, -alpha, newDepth, false);
// Step 17. Undo move
pos.undo_move(move);
// Step 17. Undo move
pos.undo_move(move);
assert(bestValue < beta);
thisThread->split<FakeSplit>(pos, ss, alpha, beta, &bestValue, &bestMove,
assert(bestValue < beta);
thisThread->split<FakeSplit>(pos, ss, alpha, beta, &bestValue, &bestMove,
- depth, threatMove, moveCount, &mp, NT);
+ depth, threatMove, moveCount, &mp, NT, cutNode);
if (bestValue >= beta)
break;
}
if (bestValue >= beta)
break;
}
switch (sp->nodeType) {
case Root:
switch (sp->nodeType) {
case Root:
- search<SplitPointRoot>(pos, ss, sp->alpha, sp->beta, sp->depth);
+ search<SplitPointRoot>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);
- search<SplitPointPV>(pos, ss, sp->alpha, sp->beta, sp->depth);
+ search<SplitPointPV>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);
- search<SplitPointNonPV>(pos, ss, sp->alpha, sp->beta, sp->depth);
+ search<SplitPointNonPV>(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode);
break;
default:
assert(false);
break;
default:
assert(false);
template <bool Fake>
void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bestValue,
Move* bestMove, Depth depth, Move threatMove, int moveCount,
template <bool Fake>
void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bestValue,
Move* bestMove, Depth depth, Move threatMove, int moveCount,
- MovePicker* movePicker, int nodeType) {
+ MovePicker* movePicker, int nodeType, bool cutNode) {
assert(pos.pos_is_ok());
assert(*bestValue <= alpha && alpha < beta && beta <= VALUE_INFINITE);
assert(pos.pos_is_ok());
assert(*bestValue <= alpha && alpha < beta && beta <= VALUE_INFINITE);
sp.alpha = alpha;
sp.beta = beta;
sp.nodeType = nodeType;
sp.alpha = alpha;
sp.beta = beta;
sp.nodeType = nodeType;
sp.movePicker = movePicker;
sp.moveCount = moveCount;
sp.pos = &pos;
sp.movePicker = movePicker;
sp.moveCount = moveCount;
sp.pos = &pos;
}
// Explicit template instantiations
}
// Explicit template instantiations
-template void Thread::split<false>(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int);
-template void Thread::split< true>(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int);
+template void Thread::split<false>(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int, bool);
+template void Thread::split< true>(Position&, Stack*, Value, Value, Value*, Move*, Depth, Move, int, MovePicker*, int, bool);
// wait_for_think_finished() waits for main thread to go to sleep then returns
// wait_for_think_finished() waits for main thread to go to sleep then returns
Value beta;
int nodeType;
Move threatMove;
Value beta;
int nodeType;
Move threatMove;
// Const pointers to shared data
MovePicker* movePicker;
// Const pointers to shared data
MovePicker* movePicker;
template <bool Fake>
void split(Position& pos, Search::Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove,
template <bool Fake>
void split(Position& pos, Search::Stack* ss, Value alpha, Value beta, Value* bestValue, Move* bestMove,
- Depth depth, Move threatMove, int moveCount, MovePicker* movePicker, int nodeType);
+ Depth depth, Move threatMove, int moveCount, MovePicker* movePicker, int nodeType, bool cutNode);
SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD];
Material::Table materialTable;
SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD];
Material::Table materialTable;