combining pvs with null move

[flok]

Hi,

Am trying to combine PVS with null-move. Sofar this gives 150 elo LESS than without this combination. I probably made a bug:

Code: Select all

int bestVal = -infinite;
bool first = true;

for&#40;idx=0; idx<nMoves; idx++) &#123;
    Move m = moveList.at&#40;idx&#41;;

    newSearchDepth = currentDepth - 1;

    if &#40;kingUnderAttack&#40;) == false && currentDepth >= 3 && m.attack != false && m.promote == false&#41; &#123;
        if &#40;idx > 5&#41;
            newSearchDepth = currentDepth - 3;
        else if &#40;idx > 3&#41;
            newSearchDepth = currentDepth - 2;  
    &#125;

    doMove&#40;m&#41;;

    int score;
    bool use = false;

    if &#40;moveRepeats&#40;)) &#123;
        if &#40;0 > bestVal&#41; &#123;
          bestVal = 0;
          use = true;
        &#125;
        first = false;
    &#125;
    else if &#40;first&#41; &#123;
        score = -search&#40;newSearchDepth, -beta, -alpha&#41;;
        if &#40;score > bestVal&#41; &#123;
          bestVal = score;
          use = true;
        &#125;
        first = false;
    &#125;
    else &#123;
        score = -search&#40;newSearchDepth, -alpha - 1, -alpha&#41;;

        if &#40;score > alpha && score < beta&#41;
             score = -search&#40;currentDepth - 1, -beta, -score&#41;;

        if &#40;score > bestVal&#41; &#123;
          bestVal = score;
          use = true;
        &#125;
     &#125;

     undoMove&#40;);

     if &#40;bestVal > alpha&#41;
        alpha = bestVal;

     if &#40;bestVal >= beta&#41; &#123;
         betaCutOff = true;
         break;
     &#125;
&#125;

Does anyone can spot the problem?

[hgm]

I see no null move there. Just (quite aggressive) LMR.

[flok]

ah yes, that's what I meant

it was a long day

but anything wrong with this?

[hgm]

How are your moves ordered? Only the first 4 moves are not reduced, so there is not even a guarantee that captures and killers are not reduced. Normally one searches hashmove, captures, killers without reduction, and then perhaps a few non-captures with good history, before starting toreduce anything. The reduction seems to be quite large, it jumps to 2 immediately, and two moves later to 3. Fairy-Max never reduces more than 1 ply for LMR. And checks are normally not reduced, no matter how far down they are in the move list.

[flok]

How are your moves ordered? Only the first 4 moves are not reduced, so there is not even a guarantee that captures and killers are not reduced. Normally one searches hashmove, captures, killers without reduction, and then perhaps a few non-captures with good history, before starting toreduce anything.

The branch that I uploaded yesterday and that played far better indeed starts to reduce only after all special-ordening moves.
Just before this posting I merged that version into the (problematic-) trunk and that did not help (time to depth is an order of magnitude slower). So I think it may have to do with the PVS/lmr code.

The reduction seems to be quite large, it jumps to 2 immediately, and two moves later to 3. Fairy-Max never reduces more than 1 ply for LMR. And checks are normally not reduced, no matter how far down they are in the move list.

Here "putinfront" is the array of special moves.

Code: Select all

#define LATE_MOVE_RED_AFTER_N_MOVES_1 1
#define LATE_MOVE_RED_AFTER_N_MOVES_2 4

          int newDepth = depthLeft - 1;
          const int newDepthLMR1 = depthLeft - 2;
          const int newDepthLMR2 = (newDepth * 2) /3;
          const bool allowLMR = !sd -> s -> isKingUnderAttack(c) && depthLeft >= 3;

          int reduction = 0;

          for&#40;int idx=0; idx<nMoves; idx++) &#123;
                  Move m = moves -> at&#40;idx&#41;;
                  int currentDepth = newDepth;
  
                  if &#40;idx >= putInFront.size&#40;) && allowLMR && m.isCatchMove == false && m.promoteTo == NONE&#41;
                  &#123;
                          if &#40;reduction == LATE_MOVE_RED_AFTER_N_MOVES_1&#41;
                                  currentDepth = newDepthLMR1;
                          else if &#40;reduction == LATE_MOVE_RED_AFTER_N_MOVES_2&#41;
                                  currentDepth = newDepthLMR2;
  
                          reduction++;
                  &#125;

[flok]

New version of PVS + LMR.

Result is... 3 elo increase

Code: Select all

Rank Name          Elo    +    - games score oppo. draws
   1 fairymax      284    2    3 121175   68%   140   13%
   2 Emblapvs      143    3    4 40258   32%   284   14%
   3 trunk         141    4    4 40403   32%   284   13%
   4 Emblapvs-ns   140    4    4 40243   32%   284   13%

(Emblapvs-ns is with negascout)

Code: Select all

if (sd -> s -> isKingUnderAttack(co))
        goto skip_lmr;

if (first) {
        first = false;
        score = -search(sd, &m, depthLeft - 1, co, -beta, -alpha, newHash, stopFlag, curBestSiblings, false, &tempPv);
}
else if (isLMR) {
        score = -search(sd, &m, newDepth, co, -beta, -alpha, newHash, stopFlag, curBestSiblings, false, &tempPv);

        if (score > alpha) {
                if (!tempPv.empty()) {
                        curBestSiblings[0] = curBestSiblings[1];
                        curBestSiblings[1] = tempPv.back().m;
                }

                goto skip_lmr;
        }
}
else {
skip_lmr:
        score = -search(sd, &m, depthLeft - 1, co, -(alpha + 1), -alpha, newHash, stopFlag, curBestSiblings, false, &tempPv);

        if &#40;score > alpha && score < beta&#41; &#123;
                if (!tempPv.empty&#40;)) &#123;
                        curBestSiblings&#91;0&#93; = curBestSiblings&#91;1&#93;;
                        curBestSiblings&#91;1&#93; = tempPv.back&#40;).m;
                &#125;

                score = -search&#40;sd, &m, depthLeft - 1, co, -beta, -alpha, newHash, stopFlag, curBestSiblings, false, &tempPv&#41;;
        &#125;
&#125;

if (!tempPv.empty&#40;)) &#123;
        curBestSiblings&#91;0&#93; = curBestSiblings&#91;1&#93;;
        curBestSiblings&#91;1&#93; = tempPv.back&#40;).m;
&#125;

[Sven]

New version of PVS + LMR.

Result is... 3 elo increase

Code: Select all

Rank Name          Elo    +    - games score oppo. draws
   1 fairymax      284    2    3 121175   68%   140   13%
   2 Emblapvs      143    3    4 40258   32%   284   14%
   3 trunk         141    4    4 40403   32%   284   13%
   4 Emblapvs-ns   140    4    4 40243   32%   284   13%

Including the error bars it is between -5 and +10 ...

[flok]

Hmmm it is indeed. I'll let it play a bit longer for a while. Am curious what will happen.
For the last 10k games the 3 elo has been steady by the way.

[Henk]

Probably one can only develop engines if one is totally bored and has nothing else to do. This does not hold for tuning an engine because that is only starting and stopping a tuning task.

[Evert]

Hmmm it is indeed. I'll let it play a bit longer for a while. Am curious what will happen.
For the last 10k games the 3 elo has been steady by the way.

Personally I wouldn't bother with a 3 Elo patch at this level. There must be bigger gains that only take a fraction of the time to test.