Order of implementing things

[Jan Brouwer]

I am doing a partial rewrite of my engine, and have boiled it down to basic alpha-beta + Q, MVV/LVA, and transposition table (hash move also used). I am now thinking about adding things to it. I want to implement things that make a big difference in playing strength first. Here is the order I came up with -

SEE (try to not consider bad captures in qsearch)
killers
PVS (relies on good move ordering, hence after the first two)
Null move
LMR
IID
check extension

I have done all these before the rewrite, so I know how they work. I am just doing the rewrite because I was so fascinated by all those algorithms that I implemented all of them blindly without much testing, and with poor implementations, too. This time I am going to test carefully and do things slowly .
How does the order look?
Comments? Suggestions?
Thanks

Hi Matthew,

I totally agree with this approach, and in fact I am considering to also start again from scratch, with emphasis on carefully checking each addition.
So far it has been my experience that the increase in playing strength is not necessarily related to the size of the new code.
A complicated new piece of evaluation code may show no measurable increase in playing strength, while a seemingly "trivial" cleanup of a few lines suddenly gives a nice jump in strength.
It makes you wonder how many of these subtle imperfections may still lurk in the program.
That's why I now think that simplicity of design and a systematic approach is important to make progress.
One idea is not always try to add new code to increase playing strength, but sometimes try to remove code without reducing playing strength.

Jan

[cyberfish]

Regarding self-deepening IID, I don't think I get what you mean, yet, even looking at the pseudo-code . I will definitely take a look at it later, though. It looks fairly difficult to implement, too (and with my programming skill, that equals buggy ).

[sje]

What you should consider is the implementation of run time switches for activating and passivating each of the listed features.

[hgm]

I don't think it is really more difficult to implement than normal IID. The main difference is that Search has an extra depth argument, that tells it how deep it could optionally go if the move you are currenlty searching is a cut-move. I agree that it is more difficult to grasp exactly what the code does.

Perhaps it helps to cast it in a form that is closer to normal IID:

Code: Select all

Search(depth) 
{ 
    MoveGen(); 
    Probehash(); 
    bestScore = hash.score; 
    for(iidDepth=hash.depth+1; iidDepth <= maxDepth; iidDept++) 
    { 
        for(ALL_MOVES) 
        { 
            Make(); 
            d=iidDepth;
            {  // deepen cut-moves immediately to maximum depth
                score = -Search(d-1); 
            } while(score >= beta && ++d <= depth)
            UnMake(); 
            if(score>bestScore) bestScore = score; 
            if(bestScore >= beta) goto cutoff;
        } 
    } 
  cutoff:
    StoreHash(); 
    return bestScore; 
} 

The only difference with the previously pseudo-code is that the latter moves the loop around the recursive call to Search to the next level of recursion, making it an outer loop there, (merging it with the existing outer loop, by just giving that a few extra optonal iterations) while it is the inner loop here. This saves repeated calling of Search (and unnecessary move generation each call).