Using nested move ordering data for pruning

[sje]

The usual belief is that expending much effort with move ordering at ALL flavor nodes is wasteful. However, it may be possible to recover some extra value for move ordering work at each kind of node regardless of ALL/CUT/PV flavor.

Consider move ordering as a means of ranking the moves at a node in order of decreasing likelihood of actually being played. Now, let a program keep track of the rank index of each move for each ply along the current branch. Each rank index can be mapped to a (rough) probability estimate of being relevant, and the product of these estimates can give an estimate of the current variation being relevant.

The idea here is that nodes that are determined to be highly unlikely due to poor rankings of the current variation can be more aggressively reduced or pruned. And so move ordering efforts at ALL flavor nodes is not totally wasted.

[mcostalba]

The usual belief is that expending much effort with move ordering at ALL flavor nodes is wasteful.

I don't understund how such belief can stand when you throw in stuff like LMR.

If your program uses LMR, I would think move ordering DOES count, being it done either in an ALL or in a CUT node.

[Zach Wegner]

Two words: search instability.

[Zach Wegner]

The usual belief is that expending much effort with move ordering at ALL flavor nodes is wasteful.

I don't understund how such belief can stand when you throw in stuff like LMR.

If your program uses LMR, I would think move ordering DOES count, being it done either in an ALL or in a CUT node.

I'd say the usual belief is that expending much effort after the first few moves at ALL nodes is a waste. Generally when you think a node is an ALL node it's with pretty low confidence until you search more moves, at which point you are LMRing anyways.

[bob]

The usual belief is that expending much effort with move ordering at ALL flavor nodes is wasteful.

I don't understund how such belief can stand when you throw in stuff like LMR.

If your program uses LMR, I would think move ordering DOES count, being it done either in an ALL or in a CUT node.

I use LMR, and do not order the moves other than the usual hash, good captures and then killers. For the rest of the moves, I don't depend on the order to limit LMR at all.

[mcostalba]

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.

[mcostalba]

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

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

[mcostalba]

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

[Aleks Peshkov]

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.