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?
Move ordering for cheapest refutation
Moderators: hgm, Rebel, chrisw
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Move ordering for cheapest refutation
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.
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Move ordering for cheapest refutation
Just assume alpha = beta - 1. Makes it simpler.
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Re: Move ordering for cheapest refutation
Yeah but then I'd have to think about PV nodes separately, and will have the same problem .Henk wrote:Just assume alpha = beta - 1. Makes it simpler.
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.
-
- Posts: 411
- Joined: Thu Dec 30, 2010 4:48 am
Re: Move ordering for cheapest refutation
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?
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?
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Move ordering for cheapest refutation
PV nodes are exceptions. So main line first.matthewlai wrote:Yeah but then I'd have to think about PV nodes separately, and will have the same problem .Henk wrote:Just assume alpha = beta - 1. Makes it simpler.
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Re: Move ordering for cheapest refutation
Neural networks .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?
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.
-
- Posts: 154
- Joined: Thu Oct 03, 2013 4:17 pm
Re: Move ordering for cheapest refutation
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
https://github.com/mAarnos
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Move ordering for cheapest refutation
Maybe also use single neural cell instead of network. For networks will be too slow. Also tuning a single cell takes less time.
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Move ordering for cheapest refutation
Yeah, and why don't you use a single scalar value then?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.
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Move ordering for cheapest refutation
No first step is to remove it for it usually doesn't work.xmas79 wrote:Yeah, and why don't you use a single scalar value then?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.