Move ordering for cheapest refutation

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
matthewlai
Posts: 793
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Move ordering for cheapest refutation

Post by matthewlai » Sun Aug 09, 2015 11:42 pm

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?
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

Henk
Posts: 5827
Joined: Mon May 27, 2013 8:31 am

Re: Move ordering for cheapest refutation

Post by Henk » Mon Aug 10, 2015 7:00 am

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

matthewlai
Posts: 793
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Move ordering for cheapest refutation

Post by matthewlai » Mon Aug 10, 2015 7:49 am

Henk wrote: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 :).
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Move ordering for cheapest refutation

Post by kbhearn » Mon Aug 10, 2015 8:00 am

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
Posts: 5827
Joined: Mon May 27, 2013 8:31 am

Re: Move ordering for cheapest refutation

Post by Henk » Mon Aug 10, 2015 8:05 am

matthewlai wrote:
Henk wrote: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
Posts: 793
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Move ordering for cheapest refutation

Post by matthewlai » Mon Aug 10, 2015 8:05 am

kbhearn wrote: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.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.

User avatar
Bloodbane
Posts: 154
Joined: Thu Oct 03, 2013 2:17 pm

Re: Move ordering for cheapest refutation

Post by Bloodbane » Mon Aug 10, 2015 8:15 am

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.
Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
https://github.com/mAarnos

Henk
Posts: 5827
Joined: Mon May 27, 2013 8:31 am

Re: Move ordering for cheapest refutation

Post by Henk » Mon Aug 10, 2015 8:45 am

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

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Move ordering for cheapest refutation

Post by xmas79 » Mon Aug 10, 2015 9:06 am

Henk wrote: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
Posts: 5827
Joined: Mon May 27, 2013 8:31 am

Re: Move ordering for cheapest refutation

Post by Henk » Mon Aug 10, 2015 9:15 am

xmas79 wrote:
Henk wrote: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.

Post Reply