I can, but I am not sure if I want to. It would look like a release, and I am not expert on GPL or related things. I can study wikipedia and think about it deeply, but maybe it would be easier if you applied the patch by yourself.
In the meantime, I made a crude attempt to make a patch with ucioptions, halfply precision reductions AND two stages of null move search. Fist stage is scout&reduce, the second is null&verify. This time I was not able to guess anything nontrivial and working. Anyway, here is the patch (search.cpp and ucioption.cpp are affected) for anyone to read and maybe even tune.
Code: Select all
diff -dur src-Ch/search.cpp src-Avs2Ch/search.cpp
--- src-Ch/search.cpp 2010-07-11 14:58:47.000000000 +0200
+++ src-Avs2Ch/search.cpp 2010-07-11 20:29:17.000000000 +0200
@@ -175,6 +175,11 @@
// Step 8. Null move search with verification search
+ int NullScoutMultiplier, NullScoutShift, NullScoutDivisor;
+ int ResearchMultiplier, ResearchShift, ResearchDivisor;
+ int NullSearchMultiplier, NullSearchShift, NullSearchDivisor;
+ int VerificationMultiplier, VerificationShift, VerificationDivisor;
+
// Null move margin. A null move search will not be done if the static
// evaluation of the position is more than NullMoveMargin below beta.
const Value NullMoveMargin = Value(0x200);
@@ -458,6 +463,19 @@
if (button_was_pressed("Clear Hash") || button_was_pressed("New Game"))
TT.clear();
+ NullScoutMultiplier = get_option_value_int("Null Scout Reduction Multiplier");
+ NullScoutShift = get_option_value_int("Null Scout Reduction Shift (halfplies)");
+ NullScoutDivisor = get_option_value_int("Null Scout Reduction Divisor");
+ ResearchMultiplier = get_option_value_int("Research Reduction Multiplier");
+ ResearchShift = get_option_value_int("Research Reduction Shift (halfplies)");
+ ResearchDivisor = get_option_value_int("Research Reduction Divisor");
+ NullSearchMultiplier = get_option_value_int("Null Search Reduction Multiplier");
+ NullSearchShift = get_option_value_int("Null Search Reduction Shift (halfplies)");
+ NullSearchDivisor = get_option_value_int("Null Search Reduction Divisor");
+ VerificationMultiplier = get_option_value_int("Verification Reduction Multiplier");
+ VerificationShift = get_option_value_int("Verification Reduction Shift (halfplies)");
+ VerificationDivisor = get_option_value_int("Verification Reduction Divisor");
+
CheckExtension[1] = Depth(get_option_value_int("Check Extension (PV nodes)"));
CheckExtension[0] = Depth(get_option_value_int("Check Extension (non-PV nodes)"));
SingleEvasionExtension[1] = Depth(get_option_value_int("Single Evasion Extension (PV nodes)"));
@@ -1174,64 +1192,146 @@
// When we jump directly to qsearch() we do a null move only if static value is
// at least beta. Otherwise we do a null move if static value is not more than
// NullMoveMargin under beta.
+
if ( !PvNode
&& !ss->skipNullMove
&& depth > OnePly
- && refinedValue >= beta - (depth >= 4 * OnePly ? NullMoveMargin : 0)
+ && refinedValue >= beta - NullMoveMargin
&& !isCheck
&& !value_is_mate(beta)
&& pos.non_pawn_material(pos.side_to_move()))
{
+ // Null scout dynamic reduction based on value
+ int R2v = 0; // in halfplies (regardless of OnePly)
+ if (refinedValue - beta > PawnValueMidgame / 3)
+ R2v++;
+ if (refinedValue - beta > PawnValueMidgame)
+ R2v++;
+ if (refinedValue - beta > PawnValueMidgame * 3)
+ R2v++;
+ if (refinedValue - beta > PawnValueMidgame * 9)
+ R2v++;
+
ss->currentMove = MOVE_NULL;
+ // First, nullscout&research thinking.
// Null move dynamic reduction based on depth
- int R = 3 + (depth >= 5 * OnePly ? depth / 8 : 0);
-
- // Null move dynamic reduction based on value
- if (refinedValue - beta > PawnValueMidgame)
- R++;
+ int R2 = int(depth)*2/int(OnePly); // R2 is reduction in halfplies
+ R2 *= NullScoutMultiplier;
+ R2 += NullScoutShift*int(OnePly)/2;
+ R2 /= NullScoutDivisor;
+ R2 += R2v;
pos.do_null_move(st);
(ss+1)->skipNullMove = true;
- nullValue = depth-R*OnePly < OnePly ? -qsearch<NonPV>(pos, ss+1, -beta, -alpha, Depth(0), ply+1)
- : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R*OnePly, ply+1);
+ nullValue = depth-R2*OnePly/2 < OnePly ? -qsearch<NonPV>(pos, ss+1, -beta, -alpha, Depth(0), ply+1)
+ : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R2*OnePly/2, ply+1);
(ss+1)->skipNullMove = false;
pos.undo_null_move();
if (nullValue >= beta)
{
+ // Scout says we can afford to do a nullmove.
+ // That is good enough to try moderately reduced search.
+
// Do not return unproven mate scores
if (nullValue >= value_mate_in(PLY_MAX))
nullValue = beta;
+ // Now we compute R2 for reduction of reduced search
+ R2 = int(depth)*2/int(OnePly);
+ R2 *= VerificationMultiplier;
+ R2 += VerificationShift*int(OnePly)/2;
+ R2 /= VerificationDivisor;
+ R2 += R2v;
+
// Do zugzwang verification search at high depths
- if (depth < 6 * OnePly)
+ if (depth-R2*OnePly/2 < OnePly)
return nullValue;
ss->skipNullMove = true;
- Value v = search<NonPV>(pos, ss, alpha, beta, depth-5*OnePly, ply);
+ Value v = search<NonPV>(pos, ss, alpha, beta, depth-R2*OnePly/2, ply);
ss->skipNullMove = false;
if (v >= beta)
return nullValue;
+ // I believe v is better bound here, but let us be conservative.
+
+ // If we are here, reduced search failed low so we must enter move loop.
}
else
{
- // The null move failed low, which means that we may be faced with
- // some kind of threat. If the previous move was reduced, check if
- // the move that refuted the null move was somehow connected to the
- // move which was reduced. If a connection is found, return a fail
- // low score (which will cause the reduced move to fail high in the
- // parent node, which will trigger a re-search with full depth).
- if (nullValue == value_mated_in(ply + 2))
- mateThreat = true;
+ // Nullscout did not succeed.
+ // Either we really can not afford doing a null move here,
+ // or perhaps our inevitable avantage needs higher depths to show up.
+ // So we swith to nullsearch&verification thinking.
+ // Now we compute R2 for reduction of null search
+ R2 = int(depth)*2/int(OnePly);
+ R2 *= NullSearchMultiplier;
+ R2 += NullSearchShift*int(OnePly)/2;
+ R2 /= NullSearchDivisor;
+ R2 += R2v;
- ss->threatMove = (ss+1)->currentMove;
- if ( depth < ThreatDepth
- && (ss-1)->reduction
- && connected_moves(pos, (ss-1)->currentMove, ss->threatMove))
- return beta - 1;
+ pos.do_null_move(st);
+ (ss+1)->skipNullMove = true;
+
+ nullValue = depth-R2*OnePly/2 < OnePly ? -qsearch<NonPV>(pos, ss+1, -beta, -alpha, Depth(0), ply+1)
+ : - search<NonPV>(pos, ss+1, -beta, -alpha, depth-R2*OnePly/2, ply+1);
+ (ss+1)->skipNullMove = false;
+ pos.undo_null_move();
+
+ if (nullValue >= beta)
+ {
+ // So it looks we actually can afford a null move after all.
+ // We still have to verify to not fall to shallow zugzwangs,
+ // and this verification cannot be too shallow,
+ // because there was something that disturbed null scout.
+
+ // Do not return unproven mate scores
+ if (nullValue >= value_mate_in(PLY_MAX))
+ nullValue = beta;
+
+ // Now we compute R2 for reduction of verification search
+ R2 = int(depth)*2/int(OnePly);
+ R2 *= VerificationMultiplier;
+ R2 += VerificationShift*int(OnePly)/2;
+ R2 /= VerificationDivisor;
+ R2 += R2v;
+
+ // Do zugzwang verification search at high depths
+ if (depth-R2*OnePly/2 < OnePly)
+ return nullValue;
+
+ ss->skipNullMove = true;
+ Value v = search<NonPV>(pos, ss, alpha, beta, depth-R2*OnePly/2, ply);
+ ss->skipNullMove = false;
+
+ if (v >= beta)
+ return nullValue;
+ // v would be a worse bound here.
+
+ // We have found a zugzwang here.
+ // Or we may need higher depths to realize our advantage.
+ // Anyway, we proceed to move loop.
+ }
+ else
+ {
+ // The null move failed low again, which means that we may be faced with
+ // some kind of threat. If the previous move was reduced, check if
+ // the move that refuted the null move was somehow connected to the
+ // move which was reduced. If a connection is found, return a fail
+ // low score (which will cause the reduced move to fail high in the
+ // parent node, which will trigger a re-search with full depth).
+ if (nullValue == value_mated_in(ply + 2))
+ mateThreat = true;
+
+ ss->threatMove = (ss+1)->currentMove;
+ if ( depth < ThreatDepth
+ && (ss-1)->reduction
+ && connected_moves(pos, (ss-1)->currentMove, ss->threatMove))
+ return beta - 1;
+ }
}
}
diff -dur src-Ch/ucioption.cpp src-Avs2Ch/ucioption.cpp
--- src-Ch/ucioption.cpp 2010-07-11 14:58:47.000000000 +0200
+++ src-Avs2Ch/ucioption.cpp 2010-07-11 21:02:37.000000000 +0200
@@ -101,6 +101,18 @@
o["Passed Pawn Extension (non-PV nodes)"] = Option(0, 0, 2);
o["Pawn Endgame Extension (PV nodes)"] = Option(2, 0, 2);
o["Pawn Endgame Extension (non-PV nodes)"] = Option(2, 0, 2);
+ o["Null Scout Reduction Multiplier"] = Option(1, 0, 20);
+ o["Null Scout Reduction Shift (halfplies)"] = Option(14, 0, 200);
+ o["Null Scout Reduction Divisor"] = Option(3, 1, 100);
+ o["Research Reduction Multiplier"] = Option(1, 0, 20);
+ o["Research Reduction Shift (halfplies)"] = Option(14, 0, 200);
+ o["Research Reduction Divisor"] = Option(6, 1, 100);
+ o["Null Search Reduction Multiplier"] = Option(0, 0, 20);
+ o["Null Search Reduction Shift (halfplies)"] = Option(6, 0, 200);
+ o["Null Search Reduction Divisor"] = Option(1, 1, 100);
+ o["Verification Reduction Multiplier"] = Option(0, 0, 20);
+ o["Verification Reduction Shift (halfplies)"] = Option(10, 0, 200);
+ o["Verification Reduction Divisor"] = Option(1, 1, 100);
o["Randomness"] = Option(0, 0, 10);
o["Minimum Split Depth"] = Option(4, 4, 7);
o["Maximum Number of Threads per Split Point"] = Option(5, 4, 8);
It is already difficult to tune a single parameter in search and you are trying to tune the whole null search + verification in one go.