search efficiency

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.
crybotmark
Posts: 37
Joined: Thu May 09, 2013 7:06 pm

search efficiency

Post by crybotmark » Fri Jun 23, 2017 6:01 pm

Hi there,

I'm writing this thread just out of curiosity, as it seems like that my attempts to improve my search routine in Napoleon are little and not so exciting...
My main concern is how top engines are able to reach such great depths. What am I missing? My code is probably hiding hundreds of bugs related to search (not that I have recently seen any side effects), but as far as selectivity concerns, I've already implemented most of the heuristics that top engines use: futility pruning, LMR, razoring, null move pruning...
What's THE thing I should put my attention on in order to improve search efficiency? What's the most rewarding heuristic that I should consider implementing (or rather adjust)?
It may be possible that, despite of all the pruning and reduction that my engine does, untuned parameters could slow down my search so much?
Napoleon is currently 2250-2300 elo with a basic evaluation function (material, pst, king tropism, passed/double/isolated pawns, mobility), and I heard that with search alone and a plain evaluation function any engine should be able to reach 2500 elo.
Again this is just for curiosity, since I'm currently testing many things with Napoleon and maybe I will find an answer by myself, but it's interesting to hear other opinions and suggestions.

mkchan
Posts: 83
Joined: Thu Oct 06, 2016 7:17 pm
Location: India
Contact:

Re: search efficiency

Post by mkchan » Fri Jun 23, 2017 6:19 pm

A good evaluation and move ordering is pretty necessary to reach high depths i think. I'd say that because the better the eval, the more accurately you identify good and bad nodes. I like to think there are fewer good moves than bad moves which then works out for good evaluation functions, more obviously so in open and tactical positions. Closed positions aren't helped as much by the move ordering(few captures) so eval guides the search there too.

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: search efficiency

Post by AlvaroBegue » Fri Jun 23, 2017 6:21 pm

How do you sort your moves, both in QS and in the regular search? How good are your transposition tables? Those things can make a big difference, and you didn't mention them.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: search efficiency

Post by cdani » Fri Jun 23, 2017 6:24 pm

crybotmark wrote:What's the most rewarding heuristic that I should consider implementing (or rather adjust)?
All should work well. Of course lmr, null move,... help a lot more when are optimized.

May be you can try to measure the gain of the main features, by disabling them one by one and playing against the full version, so we can have an idea of how well are working.

A 2500 engine already have a lot of things that work well, so a lot of hours of work.

User avatar
JVMerlino
Posts: 1003
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: search efficiency

Post by JVMerlino » Fri Jun 23, 2017 6:38 pm

A good way to measure efficiency, but certainly not the only way, is to see how often the first move searched is considered the "best". My engine is not great here, but is acceptable given my level of care. :-)

Gathering data from some fairly deep searches of a couple of dozen positions (mostly middlegame), the first move turns out best 88% of the time, and 93% of the time it's one of the first three moves searched.

crybotmark
Posts: 37
Joined: Thu May 09, 2013 7:06 pm

Re: search efficiency

Post by crybotmark » Fri Jun 23, 2017 6:54 pm

AlvaroBegue wrote:How do you sort your moves, both in QS and in the regular search? How good are your transposition tables? Those things can make a big difference, and you didn't mention them.
I sort moves in the same way both in search and quiescence, except that in QS
i don't use SEE for move ordering:
1) promotions
2) winning captures
3) equal captures
4) killer moves
5) other moves in history heuristic order
6) losing captures

The first move is the TT move, if available.

My transposition table is a standard 4 bucket hash table with depth preferred replacement scheme. What information should I give you to tell you how good my tt is?

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: search efficiency

Post by jdart » Fri Jun 23, 2017 6:56 pm

Debugging is very important. There are lots of possible bugs that will not show up as crashes but will instead hurt playing performance, in all kinds of ways.

I would make sure the search is correct first and then work on performance.

You should be verifying node counts from perft for example.

It may also be helpful to run a memory access/bounds overflow detector (such as gcc with sanitizer options).

Search depth is somewhat important but it is possible to get high depths by over-pruning, which can hurt overall playing strength.



--Jon

crybotmark
Posts: 37
Joined: Thu May 09, 2013 7:06 pm

Re: search efficiency

Post by crybotmark » Fri Jun 23, 2017 6:59 pm

mkchan wrote:A good evaluation and move ordering is pretty necessary to reach high depths i think. I'd say that because the better the eval, the more accurately you identify good and bad nodes. I like to think there are fewer good moves than bad moves which then works out for good evaluation functions, more obviously so in open and tactical positions. Closed positions aren't helped as much by the move ordering(few captures) so eval guides the search there too.
I have always been skeptical about the implication good evaluation => much better search. What's the impact a good evaluation could have on search? I mean, from an equal middlegame position, Napoleon is able to reach depth 13-14 in about a minute, i guess. What might be the result with a good evaluation function?
jdart wrote: You should be verifying node counts from perft for example.
--Jon
What do you mean, exactly?

User avatar
JVMerlino
Posts: 1003
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: search efficiency

Post by JVMerlino » Fri Jun 23, 2017 7:05 pm

crybotmark wrote:
jdart wrote: You should be verifying node counts from perft for example.
--Jon
What do you mean, exactly?
That's about move generation. Making sure that your engine correctly generates all legal moves for a position, as well as the correctness of the make/unmake process.

crybotmark
Posts: 37
Joined: Thu May 09, 2013 7:06 pm

Re: search efficiency

Post by crybotmark » Fri Jun 23, 2017 7:09 pm

JVMerlino wrote:
crybotmark wrote:
jdart wrote: You should be verifying node counts from perft for example.
--Jon
What do you mean, exactly?
That's about move generation. Making sure that your engine correctly generates all legal moves for a position, as well as the correctness of the make/unmake process.
I've already done that sistematically. I like to think that my move generator is bug free.

Post Reply