search efficiency

[jeffreyan11]

I wondered exactly the same thing when Laser was 2200-2600 Elo. After trying unsuccessfully to improve search for a while, I focused attention onto eval. Now, the search depths have improved significantly. Part of it was that after improving eval, more aggressive pruning and reductions that didn't work before now gain Elo.

[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.

I've already done that sistematically. I like to think that my move generator is bug free.

Excellent. But implementing a perft and testing it on "tricky" positions is the only way to be sure.

https://chessprogramming.wikispaces.com/Perft

[AlvaroBegue]

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?

Here's the result of a quick experiment. I took a middle game position
[D]r4rk1/1p3ppp/p1nqbn2/3p4/8/1N1B4/PPPN1PPP/R2QR1K1 w - -

RuyDos finishes depth 17 in 15.6 seconds for that position.

Now I take the evaluation function and I simplify it to be material + piece-square score, rounded to a multiple of 10 centipawns.

RuyDos with that brain-dead evaluation function finishes depth 17 in 209.6 seconds. This is even though the speed in nodes per second went up from 4161679 to 6499102 (+56%).

One possible explanation for this effect is that having a good evaluation function makes the search more consistent from depth d to depth d+1, so the hash move is much more useful.

[crybotmark]

Excellent. But implementing a perft and testing it on "tricky" positions is the only way to be sure.
https://chessprogramming.wikispaces.com/Perft

My move generator passed the test with all the positions of chessprogramming.
Except for very deep depths that would require days of computations...

[JVMerlino]

Excellent. But implementing a perft and testing it on "tricky" positions is the only way to be sure.
https://chessprogramming.wikispaces.com/Perft

My move generator passed the test with all the positions of chessprogramming.
Except for very deep depths that would require days of computations...

Perfect. Well done!

[cdani]

I have always been skeptical about the implication good evaluation => much better search. What's the impact a good evaluation could have on search?

As Andscacs went stronger and with better search and eval, I could prune and reduce more and more, but with little changes most times. Was a long work. Search and eval are sure tied to some extent.

Some more information:
http://talkchess.com/forum/viewtopic.ph ... t&start=10

[AlvaroBegue]

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?

Here's the result of a quick experiment. I took a middle game position
[D]r4rk1/1p3ppp/p1nqbn2/3p4/8/1N1B4/PPPN1PPP/R2QR1K1 w - -

RuyDos finishes depth 17 in 15.6 seconds for that position.

Now I take the evaluation function and I simplify it to be material + piece-square score, rounded to a multiple of 10 centipawns.

RuyDos with that brain-dead evaluation function finishes depth 17 in 209.6 seconds. This is even though the speed in nodes per second went up from 4161679 to 6499102 (+56%).

One possible explanation for this effect is that having a good evaluation function makes the search more consistent from depth d to depth d+1, so the hash move is much more useful.

Oh, scratch that. The lobotomy I performed on the evaluation function was worse than I described, and I got the sign wrong, depending on the side to move. As I described the experiment, the search doesn't seem to be any slower.

[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.

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?

Well like I said, my argument is that there are fewer good moves than bad moves. Therefore being able to prune out the bad moves more effectively(alpha-beta and it's extensions are more effective based on how accurate the heuristic evaluation at the leaf is) should reduce the number of nodes that require to be searched and therefore reduce time to depth on average.

You can always prune/reduce more aggressively but it doesn't mean anything if you aren't searching the 'good' nodes(i.e the nodes that you will likely visit when you and your opponent actually play the moves)

[elcabesa]

hi Marco,

when I wrote and tested Vajolet movegen I compared the perft up to 6 of Vajolet against a reference program(Stockfish)
I still have the 6000 position used for the test
you can find them at:

https://github.com/elcabesa/vajolet/tre ... st/movegen
the script is named parft-random

you can execute it on stockfish and save the results in a txt file with this command

Code: Select all

stockfish <perft-random.txt >out.txt 2>&1 

you'ìll get the result in a very verbose out.txt file.

you can then compare it with the result of your engine.

If i remeber correctly, running all those perft required my pc 1 day of work[/code]

[hgm]

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

It doesn't seem good to separate winning captures from equal captures; esearching QxQ before PxB (.e. victim-value order) usually gives better results.

Search efficiency also depends on how much you reduce for LMR and null move.

It is also important what you do when you don't have a TT move in a node with large depth. Do you use any form of iterative deepening in such a node?