Update on null move and LMR

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Update on null move and LMR

Post by Michael Sherwin »

For null move reduction I revisited Dann Corbit "smooth scaling". I reread an old post of mine in which I used a variation on Dann's formula that tested well in the past.

Code: Select all

  if(!inCheck && depth > 1 && h->eval >= beta && wMat + bMat > 5200) {
    double delta = max(h->eval - beta, 1.0); 
    double ddepth = (double)depth; 
    int r = (int)(0.25 * ddepth + 2.5 + log(delta)/5.0);
    MakeMove(&noMove);
    inNull++;
    score = -Search(-beta, -beta + 1, depth - r, 0);
    inNull--;
    TakeBack();
    if(score >= beta) {
      PosStore(beta, depth, LOWER, &noMove);
      return beta;
    } 
    if&#40;score < -32000&#41; &#123;
      extendBy += 200;
    &#125;
  &#125;
What I failed to appreciate all those years ago was how effective basing the reduction on the internal evaluation was. So for LMR I never liked basing the reduction on depth and count which are quantity based and not quality based. So I tried the following for LMR.

Code: Select all

    &#125; else &#123;
        reduce = 1;
          if&#40;depth > 3 && g->phase == NEXTMOVE&#41; &#123;
          count++;
          if&#40;g->node->score < alpha&#41; &#123;
            if&#40;count > (&#40;inNull > 0&#41; << 2&#41;) &#123;
              s32 m = histTblg&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
              s32 n = histTbln&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
	        if&#40;n > 49 && m/n < 16&#41; &#123;
                reduce += (&#40;1 + log&#40;alpha - g->node->score&#41;) / 
                 &#40;log&#40;m/n+1&#41;+1&#41;);
              &#125;
	    &#125;
          &#125;
      &#125;
      if&#40;reduce == 1&#41; &#123;
        g->node->score = -Search&#40;-beta, -alpha, depth - 1, extendBy&#41;;
      &#125; else &#123;
        g->node->score = -Search&#40;-alpha - 1, -alpha, depth - reduce, extendBy&#41;;
        if&#40;g->node->score > alpha&#41;
          g->node->score = -Search&#40;-beta, -alpha, depth - 1, extendBy&#41;;
      &#125;
    &#125;
If you are wondering where I'm getting g->node->score before the search it is from the move ordering search.

Code: Select all

    case ADDMOVES&#58;
      h->phase = NEXTMOVE;
      AddMoves&#40;h->node, depth&#41;;
      if&#40;h->node == &#40;h+1&#41;->t&#41; return FALSE;
      if&#40;depth > 3&#41; &#123;
        for&#40;node = h->node; node < &#40;h+1&#41;->t; node++) &#123;
          Sort&#40;node, &#40;h+1&#41;->t&#41;;
          MakeMove&#40;&#40;moves *)&node->m&#41;;
          if&#40;GetReps&#40;))
            node->score = 0;
          else &#123;
            inShort++;
            node->score = -Search&#40;-beta - 180, -alpha + 20, depth > 7 ? 3 &#58; 1, extendBy&#41;;
            inShort--;
          &#125;
          ClrReps&#40;);
          TakeBack&#40;);
        &#125;
      &#125;        
    case NEXTMOVE&#58;
      if&#40;h->node + 1 == &#40;h+1&#41;->t&#41; &#123;
        h->phase = NOMOVES;
        return TRUE;
      &#125;
      Sort&#40;h->node, &#40;h+1&#41;->t&#41;;
The result of these first changes is Romi went from 46/100 vs Yace to this.

RomiChess - Yace : 52.5/100 39-34-27 (=11=11=0=11=01=010==00=1011011=10111=1=01101=11=100001011=0=0=110=1=11001=0=10=0010=0=10=1=11000=000) 53% +21

The first time Romi ever took a 100 game match from Yace!

:D
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Top
Dann Corbit
Posts: 12540
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Update on null move and LMR

Post by Dann Corbit »

Michael Sherwin wrote:For null move reduction I revisited Dann Corbit "smooth scaling". I reread an old post of mine in which I used a variation on Dann's formula that tested well in the past.

Code: Select all

  if&#40;!inCheck && depth > 1 && h->eval >= beta && wMat + bMat > 5200&#41; &#123;
    double delta = max&#40;h->eval - beta, 1.0&#41;; 
    double ddepth = &#40;double&#41;depth; 
    int r = &#40;int&#41;&#40;0.25 * ddepth + 2.5 + log&#40;delta&#41;/5.0&#41;;
    MakeMove&#40;&noMove&#41;;
    inNull++;
    score = -Search&#40;-beta, -beta + 1, depth - r, 0&#41;;
    inNull--;
    TakeBack&#40;);
    if&#40;score >= beta&#41; &#123;
      PosStore&#40;beta, depth, LOWER, &noMove&#41;;
      return beta;
    &#125; 
    if&#40;score < -32000&#41; &#123;
      extendBy += 200;
    &#125;
  &#125;
What I failed to appreciate all those years ago was how effective basing the reduction on the internal evaluation was. So for LMR I never liked basing the reduction on depth and count which are quantity based and not quality based. So I tried the following for LMR.

Code: Select all

    &#125; else &#123;
        reduce = 1;
          if&#40;depth > 3 && g->phase == NEXTMOVE&#41; &#123;
          count++;
          if&#40;g->node->score < alpha&#41; &#123;
            if&#40;count > (&#40;inNull > 0&#41; << 2&#41;) &#123;
              s32 m = histTblg&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
              s32 n = histTbln&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
	        if&#40;n > 49 && m/n < 16&#41; &#123;
                reduce += (&#40;1 + log&#40;alpha - g->node->score&#41;) / 
                 &#40;log&#40;m/n+1&#41;+1&#41;);
              &#125;
	    &#125;
          &#125;
      &#125;
      if&#40;reduce == 1&#41; &#123;
        g->node->score = -Search&#40;-beta, -alpha, depth - 1, extendBy&#41;;
      &#125; else &#123;
        g->node->score = -Search&#40;-alpha - 1, -alpha, depth - reduce, extendBy&#41;;
        if&#40;g->node->score > alpha&#41;
          g->node->score = -Search&#40;-beta, -alpha, depth - 1, extendBy&#41;;
      &#125;
    &#125;
If you are wondering where I'm getting g->node->score before the search it is from the move ordering search.

Code: Select all

    case ADDMOVES&#58;
      h->phase = NEXTMOVE;
      AddMoves&#40;h->node, depth&#41;;
      if&#40;h->node == &#40;h+1&#41;->t&#41; return FALSE;
      if&#40;depth > 3&#41; &#123;
        for&#40;node = h->node; node < &#40;h+1&#41;->t; node++) &#123;
          Sort&#40;node, &#40;h+1&#41;->t&#41;;
          MakeMove&#40;&#40;moves *)&node->m&#41;;
          if&#40;GetReps&#40;))
            node->score = 0;
          else &#123;
            inShort++;
            node->score = -Search&#40;-beta - 180, -alpha + 20, depth > 7 ? 3 &#58; 1, extendBy&#41;;
            inShort--;
          &#125;
          ClrReps&#40;);
          TakeBack&#40;);
        &#125;
      &#125;        
    case NEXTMOVE&#58;
      if&#40;h->node + 1 == &#40;h+1&#41;->t&#41; &#123;
        h->phase = NOMOVES;
        return TRUE;
      &#125;
      Sort&#40;h->node, &#40;h+1&#41;->t&#41;;
The result of these first changes is Romi went from 46/100 vs Yace to this.

RomiChess - Yace : 52.5/100 39-34-27 (=11=11=0=11=01=010==00=1011011=10111=1=01101=11=100001011=0=0=110=1=11001=0=10=0010=0=10=1=11000=000) 53% +21

The first time Romi ever took a 100 game match from Yace!

:D
That's a great result, but you need to be careful with 100 games.

I remember when I first implemented smooth scaling into SF, I reported a +100 Elo result after 100 games. It eventually went down to +40 after a much larger number of games. I tend to run tests at much slower time control that anyone else, so it takes me a long time to get a sensible result.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Top
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Update on null move and LMR

Post by Michael Sherwin »

I think it is very dependant on the opening books. RomiChess is probably over tuned to my 50 position test suite. It registers a 100 elo gain in the suite and then loses 50 elo at CCRL because they use different openings.

At CCRL P3L was no better than P3k. Then at CEGT P3L is 2283 and P3k is 2217. And all these years later I still have no idea if P3L is better than P3k or not.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Top
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Update on null move and LMR

Post by Michael Sherwin »

Standard baseline testing complete, 700 games. This version of Romi is best against all test engines. Over all 55.2 % vs 48.5 % of previous best result.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Top
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Update on null move and LMR

Post by Michael Sherwin »

Michael Sherwin wrote:For null move reduction I revisited Dann Corbit "smooth scaling". I reread an old post of mine in which I used a variation on Dann's formula that tested well in the past.

Code: Select all

  if&#40;!inCheck && depth > 1 && h->eval >= beta && wMat + bMat > 5200&#41; &#123;
    double delta = max&#40;h->eval - beta, 1.0&#41;; 
    double ddepth = &#40;double&#41;depth; 
    int r = &#40;int&#41;&#40;0.25 * ddepth + 2.5 + log&#40;delta&#41;/5.0&#41;;
    MakeMove&#40;&noMove&#41;;
    inNull++;
    score = -Search&#40;-beta, -beta + 1, depth - r, 0&#41;;
    inNull--;
    TakeBack&#40;);
    if&#40;score >= beta&#41; &#123;
      PosStore&#40;beta, depth, LOWER, &noMove&#41;;
      return beta;
    &#125; 
    if&#40;score < -32000&#41; &#123;
      extendBy += 200;
    &#125;
  &#125;
What I failed to appreciate all those years ago was how effective basing the reduction on the internal evaluation was. So for LMR I never liked basing the reduction on depth and count which are quantity based and not quality based. So I tried the following for LMR.

Code: Select all

    &#125; else &#123;
        reduce = 1;
          if&#40;depth > 3 && g->phase == NEXTMOVE&#41; &#123;
          count++;
          if&#40;g->node->score < alpha&#41; &#123;
            if&#40;count > (&#40;inNull > 0&#41; << 2&#41;) &#123;
              s32 m = histTblg&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
              s32 n = histTbln&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
	        if&#40;n > 49 && m/n < 16&#41; &#123;
                reduce += (&#40;1 + log&#40;alpha - g->node->score&#41;) / 
                 &#40;log&#40;m/n+1&#41;+1&#41;);
              &#125;
	    &#125;
          &#125;
      &#125;
      if&#40;reduce == 1&#41; &#123;
        g->node->score = -Search&#40;-beta, -alpha, depth - 1, extendBy&#41;;
      &#125; else &#123;
        g->node->score = -Search&#40;-alpha - 1, -alpha, depth - reduce, extendBy&#41;;
        if&#40;g->node->score > alpha&#41;
          g->node->score = -Search&#40;-beta, -alpha, depth - 1, extendBy&#41;;
      &#125;
    &#125;
If you are wondering where I'm getting g->node->score before the search it is from the move ordering search.

Code: Select all

    case ADDMOVES&#58;
      h->phase = NEXTMOVE;
      AddMoves&#40;h->node, depth&#41;;
      if&#40;h->node == &#40;h+1&#41;->t&#41; return FALSE;
      if&#40;depth > 3&#41; &#123;
        for&#40;node = h->node; node < &#40;h+1&#41;->t; node++) &#123;
          Sort&#40;node, &#40;h+1&#41;->t&#41;;
          MakeMove&#40;&#40;moves *)&node->m&#41;;
          if&#40;GetReps&#40;))
            node->score = 0;
          else &#123;
            inShort++;
            node->score = -Search&#40;-beta - 180, -alpha + 20, depth > 7 ? 3 &#58; 1, extendBy&#41;;
            inShort--;
          &#125;
          ClrReps&#40;);
          TakeBack&#40;);
        &#125;
      &#125;        
    case NEXTMOVE&#58;
      if&#40;h->node + 1 == &#40;h+1&#41;->t&#41; &#123;
        h->phase = NOMOVES;
        return TRUE;
      &#125;
      Sort&#40;h->node, &#40;h+1&#41;->t&#41;;
The result of these first changes is Romi went from 46/100 vs Yace to this.

RomiChess - Yace : 52.5/100 39-34-27 (=11=11=0=11=01=010==00=1011011=10111=1=01101=11=100001011=0=0=110=1=11001=0=10=0010=0=10=1=11000=000) 53% +21

The first time Romi ever took a 100 game match from Yace!

:D
RomiChessP3n was released with these changes. These changes were the main changes from version P3L. RomiChess version P3n has gained the best version status in the CCRL rating list.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Top
Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 3:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Update on null move and LMR

Post by Michael Sherwin »

And another apparent improvement to both null move reduction and LMR.

Code: Select all

if&#40;!inCheck && depth > 1 && h->eval >= beta && wMat + bMat > 5200&#41; &#123;
    double delta = max&#40;h->eval - beta + &#40;h-1&#41;->tries/4, 1.0&#41;; 
    double ddepth = &#40;double&#41;depth; 
    int r = &#40;int&#41;&#40;0.25 * ddepth + 2.5 + log&#40;delta&#41;/5.0&#41;;
    MakeMove&#40;&noMove&#41;;
    inNull++;
    score = -Search&#40;-beta, -beta + 1, depth - r, 0&#41;;
    inNull--;
    TakeBack&#40;);
This was added, "+ (h-1)->tries/4", which is the number of moves played by the other side at the previous ply. And the same was added to LMR below along with the current plys made moves.

Code: Select all

reduce = 1;
          if&#40;depth > 3 && g->phase == NEXTMOVE&#41; &#123;
          count++;
          if&#40;g->node->score < alpha&#41; &#123;
            if&#40;count > (&#40;inNull > 0&#41; << 2&#41;) &#123;
              s32 m = histTblg&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
              s32 n = histTbln&#91;fig&#93;&#91;fs&#93;&#91;ts&#93;;
	      if&#40;n > 49 && m/n < 16&#41; &#123;
                reduce += (&#40;log&#40;g->tries/4+&#40;g-1&#41;->tries+depth&#41;/4+log&#40;alpha-g->node->score&#41;)/&#40;log&#40;m/n+1&#41;+1&#41;);
              &#125;
	    &#125;
          &#125;
      &#125;
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Top

Return to “Computer Chess Club: Programming and Technical Discussions”