Using nested move ordering data for pruning

[mcostalba]

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.

Yes, Glaurung and Crafty use this with very good results.

[bob]

I'd say the usual belief is that expending much effort after the first few moves at ALL nodes is a waste.

Here the key point is "after the first few moves".

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.

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.

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.

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

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.

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.

[mcostalba]

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.

This morning I had a "great idea"

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!!!

[Uri Blass]

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.

This morning I had a "great idea"

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!!!

Not surprising result for me.
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

[mcostalba]

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.

This morning I had a "great idea"

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!!!

Not surprising result for me.
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

Sorry, I have written wrong. I was meaning depth 1, not ply 1 as I have bogusly written.

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

[Uri Blass]

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