Move ordering for cheapest refutation
Moderators: bob, hgm, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
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 FastestCutFirst 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
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.
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.
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.

 Posts: 793
 Joined: Sun Aug 03, 2014 2:48 am
 Location: London, UK
 Contact:
Re: Move ordering for cheapest refutation
Thanks! Very interesting paper.Bloodbane wrote:I don't know if this is what you want, but "Timothy Furtak, Michael Buro (2009). Minimum Proof Graphs and FastestCutFirst Search Heuristics" seems to have something to do with your problem.
That is essentially what I am doing for CUT nodes, except I assume Pi to be 1 if the estimated score is higher than or equal to beta.Consider a naive version of AlphaBeta search that does not adjust α based on returned values and searches a game tree starting at cutnode v with successors v1, . . . , vn. Let Si be the expected size of the subtree rooted at vi, and Pi the probability of move i leading to a βcut. Then, visiting vi in ascending order of Si/Pi minimizes the expected number of visited nodes starting at v.
Still need to figure out what to do for PV nodes, though.
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.
Re: Move ordering for cheapest refutation
But how can you estimate the tree size of a move?
Sorting the captures first is exactly following this principle, cause with less pieces on the table the tree is probably smaller. Even more if the most valuable pieces are removed first (which have higher mobility)  i.e. MVVLVA.
But except this, I don't see any other method (except of course SEE sorting, and/or history) which would give further improvement. Or, if yes, it must be some variant of history.
Sorting the captures first is exactly following this principle, cause with less pieces on the table the tree is probably smaller. Even more if the most valuable pieces are removed first (which have higher mobility)  i.e. MVVLVA.
But except this, I don't see any other method (except of course SEE sorting, and/or history) which would give further improvement. Or, if yes, it must be some variant of history.

 Posts: 793
 Joined: Sun Aug 03, 2014 2:48 am
 Location: London, UK
 Contact:
Re: Move ordering for cheapest refutation
In my case, I am doing probabilitybased node budgeting, so I determine how large each tree is before searching.nionita wrote:But how can you estimate the tree size of a move?
Sorting the captures first is exactly following this principle, cause with less pieces on the table the tree is probably smaller. Even more if the most valuable pieces are removed first (which have higher mobility)  i.e. MVVLVA.
But except this, I don't see any other method (except of course SEE sorting, and/or history) which would give further improvement. Or, if yes, it must be some variant of history.
You can do it with LMR as well. By actually searching a late node with high reduction first, if you estimate that it's probably still good enough to cause a cutoff.
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.
Re: Move ordering for cheapest refutation
I agree, thanks!matthewlai wrote:Thanks! Very interesting paper.Bloodbane wrote:I don't know if this is what you want, but "Timothy Furtak, Michael Buro (2009). Minimum Proof Graphs and FastestCutFirst Search Heuristics" seems to have something to do with your problem.
Effectively this is also what problem solver Chest is trying to do by sorting defender moves by increasing estimated tree size. But since Chest estimates all Pi to be 1, no complicated reasoning is necessary to derive this rather obvious heuristic.That is essentially what I am doing for CUT nodes, except I assume Pi to be 1 if the estimated score is higher than or equal to beta.Consider a naive version of AlphaBeta search that does not adjust α based on returned values and searches a game tree starting at cutnode v with successors v1, . . . , vn. Let Si be the expected size of the subtree rooted at vi, and Pi the probability of move i leading to a βcut. Then, visiting vi in ascending order of Si/Pi minimizes the expected number of visited nodes starting at v.
Cheers, Heiner