Yes, Glaurung and Crafty use this with very good results.Aleks Peshkov wrote:When you need an ordered sequence it is not necessary to sort it explicitly.
Linear search form the rest is not bad alternative, at least it is proved to be faster then bubble sort on worst and on average case.
Using nested move ordering data for pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Using nested move ordering data for pruning
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Using nested move ordering data for pruning
The discussion was about a bubble sort, which is not a great idea for "the rest of the moves". You do work that is wasted in at least 95% of all positions (1/2 are ALL nodes where ordering is meaningless anyway) and in the CUT positions, we already get 90+% of the fail highs on the first move found. So we are beyond 95% of the cases already.mcostalba wrote:Yes I agree, perhaps I have expressed incorrectly my opinion. What I was trying to say is that WHEN you generate moves THEN you need to sort them.bob wrote:Actually you don't. For example, you can play the hash move without generating moves at all. Then you can try the captures that don't lose material according to SEE, without generating / sorting _all_ moves. Then you can try the killer moves, again before generating/sorting. You have already gotten 99% of the fail high moves you are going to get. Most programs, when they fail high, fail high on the first move searched over 90% of the time. Adding in those others takes it to 99%. Sorting to find that last 1% quicker, means you are wasting effort in the other 99% of the cases.mcostalba wrote:Here the key point is "after the first few moves".Zach Wegner wrote:I'd say the usual belief is that expending much effort after the first few moves at ALL nodes is a waste.
Point is that to find the fist moves (also if are few) you need to order the whole move's set. You need to order the whole move set even to find the first (i.e. highed score) move alone.
If you try TT you have nothing to sort, if you generate captures you sort captures, if and when you generates non captures you sort non captures, so sorting is very bound to move generation...
A "selection" sort makes more sense since you can determine how many selection passes to make before giving up and just taking moves in order, while a real sort takes N^2 passes (bubble) each and every time you use it.
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Using nested move ordering data for pruning
This morning I had a "great idea"bob wrote: A "selection" sort makes more sense since you can determine how many selection passes to make before giving up and just taking moves in order, while a real sort takes N^2 passes (bubble) each and every time you use it.
Instead of sorting non-captures I sort only for ply > 1 OR if there are killer moves (killers are tried among non-captures in Glaurung and so in Stockfish)
Of corse I not only not sort, but, as a natural consequence I even didn't score them when the above condition hold.
Profiling showed that this idea cut in half the time needed to score and sort non-captures.
I start the verification tests against the unmodified version.
This afternoon I trashed everything: a disaster !!!!!!!
Not ordering not captures even if only at ply one, even if there aren't killer moves to try gave TERRIBLE results after 150 games we were far down in ELO
This evening what was a grat idea this morning is now only bulls.... !
Chess engines are nasty beasts!!!
-
- Posts: 10316
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Using nested move ordering data for pruning
Not surprising result for me.mcostalba wrote:This morning I had a "great idea"bob wrote: A "selection" sort makes more sense since you can determine how many selection passes to make before giving up and just taking moves in order, while a real sort takes N^2 passes (bubble) each and every time you use it.
Instead of sorting non-captures I sort only for ply > 1 OR if there are killer moves (killers are tried among non-captures in Glaurung and so in Stockfish)
Of corse I not only not sort, but, as a natural consequence I even didn't score them when the above condition hold.
Profiling showed that this idea cut in half the time needed to score and sort non-captures.
I start the verification tests against the unmodified version.
This afternoon I trashed everything: a disaster !!!!!!!
Not ordering not captures even if only at ply one, even if there aren't killer moves to try gave TERRIBLE results after 150 games we were far down in ELO
This evening what was a grat idea this morning is now only bulls.... !
Chess engines are nasty beasts!!!
My guess is that
if you do not sort non captures at ply=1 then the killer moves that you get later are relatively inferior killer moves and you have worse order of moves later that means that there is a bigger probability that your killer move do not work at bigger depth.
Edit:It is possible that you may get better results if you use the same idea only in the last iteration.
Uri
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Using nested move ordering data for pruning
Sorry, I have written wrong. I was meaning depth 1, not ply 1 as I have bogusly written.Uri Blass wrote:Not surprising result for me.mcostalba wrote:This morning I had a "great idea"bob wrote: A "selection" sort makes more sense since you can determine how many selection passes to make before giving up and just taking moves in order, while a real sort takes N^2 passes (bubble) each and every time you use it.
Instead of sorting non-captures I sort only for ply > 1 OR if there are killer moves (killers are tried among non-captures in Glaurung and so in Stockfish)
Of corse I not only not sort, but, as a natural consequence I even didn't score them when the above condition hold.
Profiling showed that this idea cut in half the time needed to score and sort non-captures.
I start the verification tests against the unmodified version.
This afternoon I trashed everything: a disaster !!!!!!!
Not ordering not captures even if only at ply one, even if there aren't killer moves to try gave TERRIBLE results after 150 games we were far down in ELO
This evening what was a grat idea this morning is now only bulls.... !
Chess engines are nasty beasts!!!
My guess is that
if you do not sort non captures at ply=1 then the killer moves that you get later are relatively inferior killer moves and you have worse order of moves later that means that there is a bigger probability that your killer move do not work at bigger depth.
Edit:It is possible that you may get better results if you use the same idea only in the last iteration.
Uri
In other words I was skipping sorting at the leavs of the search not at the root (where there is little sense to do it).
-
- Posts: 10316
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Using nested move ordering data for pruning
I understood what you meant
My point is still the same.
if you do not sort at depth=1 from the beginning of the search then you may get a cutoff by a different move and this different move that you may use later as a killer move may be inferior move so there is a bigger probability that you may get fail low in one of the next iterations.
You can reduce the effect by not sorting at depth=1 only in the last iteration(you may get the same position by tranposition and you may not be sure what is the last iteration so it is not a perfect solution but if the number of tranpositions is small enough you may get some elo improvements)
Uri
My point is still the same.
if you do not sort at depth=1 from the beginning of the search then you may get a cutoff by a different move and this different move that you may use later as a killer move may be inferior move so there is a bigger probability that you may get fail low in one of the next iterations.
You can reduce the effect by not sorting at depth=1 only in the last iteration(you may get the same position by tranposition and you may not be sure what is the last iteration so it is not a perfect solution but if the number of tranpositions is small enough you may get some elo improvements)
Uri