Search-algorithm

[bob]

As mentioned, NegaScout aka PVS as alpha-beta enhancement is probably most common. Further important enhancements are related to various forward pruning techniques like Null Move Pruning, eventually Multi-Cut and Hyatt's Razoring. Quite common nowadays seems Late Move Reduction to reduce effective branching factor even more.

Razoring isn't my idea. Came from Heinz, and someone else before him (Kent?)

[Gerd Isenberg]

As mentioned, NegaScout aka PVS as alpha-beta enhancement is probably most common. Further important enhancements are related to various forward pruning techniques like Null Move Pruning, eventually Multi-Cut and Hyatt's Razoring. Quite common nowadays seems Late Move Reduction to reduce effective branching factor even more.

Razoring isn't my idea. Came from Heinz, and someone else before him (Kent?)

What you proposed in October 2008, was a complete different animal than classical razoring from Birmingham and Kent, as well the Limited Razoring (L) in AEL-Pruning from Heinz:

I had heard Tord mention that he was using razoring. I had tried this a few years back (along with lots of other things) and I try to save old code. I decided yesterday to see how it would look on a cluster run since I had never been able to test that thoroughly in the past.

Code: Select all

/*
************************************************************
*                                                          *
* now we try a quick Razoring test. If we are within 3     *
* plies of a tip, and the current eval is 3 pawns (or      *
* more) below beta, then we just drop into a q-search      *
* to try to get a quick cutoff without searching more in   *
* a position where we are way down in material.            *
*                                                          *
************************************************************
*/
if &#40;razoring_allowed && depth <= razor_depth&#41; &#123;
   if &#40;alpha == beta - 1&#41; &#123; // null window ?
      if &#40;Evaluate&#40;tree, ply, wtm, alpha, beta&#41; + razor_margin < beta&#41; &#123; // likely a fail-low node ?
         value = QuiesceChecks&#40;tree, alpha, beta, wtm, ply&#41;;
         if &#40;value < beta&#41;
            return value; 
      &#125;
   &#125;
&#125;

How should we call it if not "Hyatt's Razoring"?

[Teemu Pudas]

How should we call it if not "Hyatt's Razoring"?

"Rajlich-Osipov Razoring"?

Code: Select all

    /* In the non-pv not-in-check search function of Strelka 2.0 */
    value = pos_info_entry->value + 300;
    if &#40;value < beta && depth <= 3&#41; &#123; 
      new_value = qu_search&#40;beta-1, beta, depth*8-8, new_pv&#41;;
      if &#40;new_value < beta&#41; &#123;
        if &#40;new_value >= value&#41; return new_value; else return value;
      &#125;
    &#125;

qu_search with positive depth doesn't prune bad captures (doesn't reorder them either; Vas has hinted that this was a Rybka bug). Checks are searched at depth -5 and higher.

[Gerd Isenberg]

How should we call it if not "Hyatt's Razoring"?

"Rajlich-Osipov Razoring"?

Code: Select all

    /* In the non-pv not-in-check search function of Strelka 2.0 */
    value = pos_info_entry->value + 300;
    if &#40;value < beta && depth <= 3&#41; &#123; 
      new_value = qu_search&#40;beta-1, beta, depth*8-8, new_pv&#41;;
      if &#40;new_value < beta&#41; &#123;
        if &#40;new_value >= value&#41; return new_value; else return value;
      &#125;
    &#125;

qu_search with positive depth doesn't prune bad captures (doesn't reorder them either; Vas has hinted that this was a Rybka bug). Checks are searched at depth -5 and higher.

Yes, but Bob also said "I had tried this a few years back (along with lots of other things) and I try to save old code", so the idea was probably known and used by Bob (and others?) before Rybka/Strelka appeared.

[bob]

As mentioned, NegaScout aka PVS as alpha-beta enhancement is probably most common. Further important enhancements are related to various forward pruning techniques like Null Move Pruning, eventually Multi-Cut and Hyatt's Razoring. Quite common nowadays seems Late Move Reduction to reduce effective branching factor even more.

Razoring isn't my idea. Came from Heinz, and someone else before him (Kent?)

What you proposed in October 2008, was a complete different animal than classical razoring from Birmingham and Kent, as well the Limited Razoring (L) in AEL-Pruning from Heinz:

I had heard Tord mention that he was using razoring. I had tried this a few years back (along with lots of other things) and I try to save old code. I decided yesterday to see how it would look on a cluster run since I had never been able to test that thoroughly in the past.

Code: Select all

/*
************************************************************
*                                                          *
* now we try a quick Razoring test. If we are within 3     *
* plies of a tip, and the current eval is 3 pawns (or      *
* more) below beta, then we just drop into a q-search      *
* to try to get a quick cutoff without searching more in   *
* a position where we are way down in material.            *
*                                                          *
************************************************************
*/
if &#40;razoring_allowed && depth <= razor_depth&#41; &#123;
   if &#40;alpha == beta - 1&#41; &#123; // null window ?
      if &#40;Evaluate&#40;tree, ply, wtm, alpha, beta&#41; + razor_margin < beta&#41; &#123; // likely a fail-low node ?
         value = QuiesceChecks&#40;tree, alpha, beta, wtm, ply&#41;;
         if &#40;value < beta&#41;
            return value; 
      &#125;
   &#125;
&#125;

How should we call it if not "Hyatt's Razoring"?

That is more of a reduction, and I do not do things that way any longer, switching to actual forward pruning, which is what razoring actually does. So if you want to call that "Hyatt's razoring" I suppose that is OK. It is less risky, obviously, but also less effective although the difference is not huge.

[bob]

How should we call it if not "Hyatt's Razoring"?

"Rajlich-Osipov Razoring"?

Code: Select all

    /* In the non-pv not-in-check search function of Strelka 2.0 */
    value = pos_info_entry->value + 300;
    if &#40;value < beta && depth <= 3&#41; &#123; 
      new_value = qu_search&#40;beta-1, beta, depth*8-8, new_pv&#41;;
      if &#40;new_value < beta&#41; &#123;
        if &#40;new_value >= value&#41; return new_value; else return value;
      &#125;
    &#125;

qu_search with positive depth doesn't prune bad captures (doesn't reorder them either; Vas has hinted that this was a Rybka bug). Checks are searched at depth -5 and higher.

That idea didn't come from Strelka. It's been "as is" in Crafty for several years, added (I believe) by Jeremiah P. I think the notes in main.c give credit for this to him. I'd suspect someone borrowed it from Crafty, no big surprise there...