Move ordering for cheapest refutation

[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.

[matthewlai]

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.

[nionita]

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]

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.

[hMx]

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