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