Move ordering for cheapest refutation

[matthewlai]

Suppose for each position I have a score estimate for each of the offsprings, as well as an estimate of how large that subtree is (for example, nodes/depths we intend to search that subtree to), how do I order the moves to get minimal tree size?

Ordering by score estimate is not the best way, because on CUT nodes, we want the cheapest refutation, not the highest refutation.

I have come up with this ordering that is supposed to work with all 3 types of nodes. Does it make sense?

First, divide the offsprings into 3 groups - group A consists of nodes equal or higher than beta, group B consists of nodes less than beta and higher than alpha, and group C consists of nodes equal or lower than alpha.

Group A is ordered before B, which is ordered before C.

Within group A, nodes are ordered in ascending order of node allocation (or depth after reductions).

Within group B, nodes are ordered in descending order of score estimates.

Within group C, nodes are ordered in descending order of score estimates (just in case we get an unexpected cutoff), although it doesn't really matter too much.

I am not too sure about groups B and C (PV and ALL nodes respectively). On one hand, searching moves with higher score estimates first can potentially raise alpha more, making subsequent searches faster.

On the other hand, searching moves with lower time allocation first can quickly raise alpha to make searching the big offsprings quicker.

In conventional alpha-beta (no reductions), it's clear that the best strategy is to search expected best moves first. However, when we are spending different amounts of time on subtrees, it becomes more complicated.

What do you think?

[Henk]

Just assume alpha = beta - 1. Makes it simpler.

[matthewlai]

Just assume alpha = beta - 1. Makes it simpler.

Yeah but then I'd have to think about PV nodes separately, and will have the same problem .

[kbhearn]

I'm not sure there's a consistent way to predict when the first refutation will not be the quickest refutation.

Certainly gobbling up free material will usually be the first thing tried and usually the smallest tree as null move reductions will be able to kick in easier but those are already tried first apart from the best move in the hash table which if it's not one of those it means they didn't successfully refute it at the previous depth.

So we'll assume your idea mostly pertains to something subtler. Say a move that just doesn't accomplish anything or creates an unnecessary weakness but isn't tactically losing. How do you determine which subtree between two potential 'refutations' is smaller without first searching both?

[Henk]

Just assume alpha = beta - 1. Makes it simpler.

Yeah but then I'd have to think about PV nodes separately, and will have the same problem .

PV nodes are exceptions. So main line first.

[matthewlai]

I'm not sure there's a consistent way to predict when the first refutation will not be the quickest refutation.

Certainly gobbling up free material will usually be the first thing tried and usually the smallest tree as null move reductions will be able to kick in easier but those are already tried first apart from the best move in the hash table which if it's not one of those it means they didn't successfully refute it at the previous depth.

So we'll assume your idea mostly pertains to something subtler. Say a move that just doesn't accomplish anything or creates an unnecessary weakness but isn't tactically losing. How do you determine which subtree between two potential 'refutations' is smaller without first searching both?

Neural networks .

But a simpler way to get score estimates is static eval + SEE (SEE works for non-captures as well, to identify suicidal moves). That way it's possible to get pretty good estimates for all moves quickly. At high depths, it may even make sense to do a QSearch on all moves.

Then, in case of LMR for example, if you see that the last move (with very high reduction) will probably cause a cutoff, it may make sense to search that move first, before even hash move, good captures, and killers.

[Bloodbane]

I don't know if this is what you want, but "Timothy Furtak, Michael Buro (2009). Minimum Proof Graphs and Fastest-Cut-First Search Heuristics" seems to have something to do with your problem.

[Henk]

Maybe also use single neural cell instead of network. For networks will be too slow. Also tuning a single cell takes less time.

[xmas79]

Maybe also use single neural cell instead of network. For networks will be too slow. Also tuning a single cell takes less time.

Yeah, and why don't you use a single scalar value then?

[Henk]

Maybe also use single neural cell instead of network. For networks will be too slow. Also tuning a single cell takes less time.

Yeah, and why don't you use a single scalar value then?

No first step is to remove it for it usually doesn't work.