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

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 9:20 am

Bloodbane wrote: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.
Thanks! Very interesting paper.
Consider a naive version of Alpha-Beta search that does not adjust α based on returned values and searches a game tree starting at cut-node 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.
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.

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.

nionita
Posts: 161
Joined: Fri Oct 22, 2010 7:47 pm
Location: Austria

Re: Move ordering for cheapest refutation

Post by nionita » Wed Aug 12, 2015 5:58 pm

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.

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

Re: Move ordering for cheapest refutation

Post by matthewlai » Wed Aug 12, 2015 6:00 pm

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.
In my case, I am doing probability-based node budgeting, so I determine how large each tree is before searching.

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.

hMx
Posts: 61
Joined: Wed Mar 08, 2006 8:40 pm
Location: Germany, Berlin
Contact:

Re: Move ordering for cheapest refutation

Post by hMx » Thu Aug 13, 2015 3:34 pm

matthewlai wrote:
Bloodbane wrote: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.
Thanks! Very interesting paper.
I agree, thanks!
Consider a naive version of Alpha-Beta search that does not adjust α based on returned values and searches a game tree starting at cut-node 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.
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.
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.

Cheers, Heiner

Post Reply