search efficiency

[crybotmark]

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]

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]

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.

[cdani]

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.

[JVMerlino]

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]

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]

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]

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?

You should be verifying node counts from perft for example.
--Jon

What do you mean, exactly?

[JVMerlino]

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]

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.