search efficiency
Moderators: hgm, Rebel, chrisw
-
- Posts: 46
- Joined: Sat Sep 12, 2015 5:23 am
- Location: United States
Re: search efficiency
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.
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: search efficiency
Excellent. But implementing a perft and testing it on "tricky" positions is the only way to be sure.crybotmark wrote:I've already done that sistematically. I like to think that my move generator is bug free.JVMerlino wrote: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 wrote:What do you mean, exactly?jdart wrote: You should be verifying node counts from perft for example.
--Jon
https://chessprogramming.wikispaces.com/Perft
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: search efficiency
crybotmark wrote: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?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.
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.
-
- Posts: 37
- Joined: Thu May 09, 2013 9:06 pm
Re: search efficiency
My move generator passed the test with all the positions of chessprogramming.JVMerlino wrote:
Excellent. But implementing a perft and testing it on "tricky" positions is the only way to be sure.
https://chessprogramming.wikispaces.com/Perft
Except for very deep depths that would require days of computations...
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: search efficiency
Perfect. Well done!crybotmark wrote:My move generator passed the test with all the positions of chessprogramming.JVMerlino wrote:
Excellent. But implementing a perft and testing it on "tricky" positions is the only way to be sure.
https://chessprogramming.wikispaces.com/Perft
Except for very deep depths that would require days of computations...
-
- Posts: 2204
- Joined: Sat Jan 18, 2014 10:24 am
- Location: Andorra
Re: search efficiency
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.mkchan wrote: I have always been skeptical about the implication good evaluation => much better search. What's the impact a good evaluation could have on search?
Some more information:
http://talkchess.com/forum/viewtopic.ph ... t&start=10
Daniel José - http://www.andscacs.com
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: search efficiency
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.AlvaroBegue wrote:crybotmark wrote: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?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.
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.
-
- Posts: 88
- Joined: Thu Oct 06, 2016 9:17 pm
- Location: India
Re: search efficiency
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.crybotmark wrote: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?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.
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)
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: search efficiency
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
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]
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 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]
-
- Posts: 27816
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: search efficiency
It doesn't seem good to separate winning captures from equal captures; esearching QxQ before PxB (.e. victim-value order) usually gives better results.crybotmark wrote: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
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?