Order of implementing things

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
cyberfish

Order of implementing things

Post by cyberfish » Fri Oct 10, 2008 2:22 am

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
Posts: 10101
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Order of implementing things

Post by Dann Corbit » Fri Oct 10, 2008 2:31 am

cyberfish wrote: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

Re: Order of implementing things

Post by cyberfish » Fri Oct 10, 2008 2:36 am

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

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Order of implementing things

Post by Zach Wegner » Fri Oct 10, 2008 2:48 am

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

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Order of implementing things

Post by Zach Wegner » Fri Oct 10, 2008 2:49 am

cyberfish wrote: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

Re: Order of implementing things

Post by cyberfish » Fri Oct 10, 2008 2:58 am

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

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Order of implementing things

Post by hgm » Fri Oct 10, 2008 7:08 am

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

Re: Order of implementing things

Post by cyberfish » Fri Oct 10, 2008 7:11 am

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?

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Order of implementing things

Post by hgm » Fri Oct 10, 2008 8:15 am

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

Re: Order of implementing things

Post by Harald Johnsen » Fri Oct 10, 2008 9:19 am

cyberfish wrote: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.

Post Reply