Order of implementing things

[cyberfish]

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

[Dann Corbit]

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

IID gives a big boost if you have poor move ordering. I guess that if you implement in that order, you will see a few percent improvement for IID at most, if everything else is done right. If you want to get a charge out of IID, introduce it right after the hash table and before everything else.

[cyberfish]

What will happen, then, if I get a good move ordering later? Will IID actually hinder?

[Zach Wegner]

Here's my completely-unscientific-not-based-on-testing-quite-possibly-wrong-but-should-be-a-good-guess order:

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

[Zach Wegner]

What will happen, then, if I get a good move ordering later? Will IID actually hinder?

No. Depending on how you do it, IID should always help. Move ordering is very important, especially in PV nodes.

[cyberfish]

Thanks! My guess was an out-of-nowhere guess, too, but I will follow yours .

[hgm]

It depends on if you want to do things that give you the most Elo first, or things that impact the logic of your engine most. I would recommend the latter.

So I would start with IID. I would implemet this through self-deepening, of course.
Then PVS (to get the re-search logic right).
Then null move and killer.
Extension / reduction control for LMR and Check Extension is then almost trivial to add.
SEE and pruning bad captures are also easy to add later.

[cyberfish]

So I would start with IID. I would implemet this through self-deepening, of course.

Can you please elaborate a bit on that? I always thought IID is just doing a shallower search and ignore the result (except store the hash move in transposition table), if there is no hash move for the current position. What do you mean by self-deepening?

[hgm]

With self-deepening, cut-moves will be automatically searched to full depth, so that you cannot get a cutoff in an early iteration of IID. I gave a pseudo-code description of self-deepening in the other thread.

The way you descibe it has two disadvantages:
1) when the search finds a cut-move, every IID iteration would only search that cut-move. This is needlessly inefficient, because you re-enter the same daughter (which is an all-node) time after time, and each time it will have to do move generation. With self-deepening you stay in the daughter node, so you have to do move generation only once.
2) If a cut-move would work a long way, but not quite to full depth, normal IID would start to look for an alternative at the large depth where the cut-move failed, completely uninformed about these moves. If there would be an alternative cut move, it might waste a lot of search effort before it finds it. With self-deepening you would always search all moves at lower depth before you search them at full depth.

[Harald Johnsen]

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

The biggest improvment comes from a bug free code

1) simple, bug free :
SEE : pruning bad captures from qs reduce the tree a lot
Killers : simple and good for move ordering.
Null move : a big win, note that this will reduce the tactic ability of your engine and add zugzwang problems.
IID : simple, good for move ordering.

2) will break the search
hash table : this won't break the search if you do not use it for cutoffs but only use it for move ordering ; features like iid, pvs, lmr, etc rely on hash tables because of all them will do search and re-search
PVS : big reduction of tree size if you don't use windows
LMR : a moderate to big win, big win at first but you must understand that your engine will be blind to lot of things (add it last).
search window : if you have too much time only...

HJ.