Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Posted: Tue Jul 02, 2019 5:06 pm
I've given some thought to how to evaluate an "incomplete future".
The P3121* branch, and its parents, seems to satisfy all the situations I'm interested in. Here's my hand-done trace of execution:
Okay, so F1, F2, F311, and F313 are off executing in parallel while the code discovers the value F3121.
Lets actually evaluate things, because numbers are easier to think than futures. My "evaluation" function for the purposes of these posts is hash(Position) = ((Position * 31415) / 1000) % 100. (The 5th and 4th digits after being multiplied by the arbitrary Pi-like number 31415). And remember, 50-99 are negative numbers, while 0-49 are positive numbers. We're working modulo 100 arithmetic.
"Physically", the numbers are represented from 0 to 99. Logically, the numbers are -50 to 49. (And -50 negated == -50, same quirk as in binary.)
So we can evaluate F3121 without knowing what F1, F2, or anything else in the tree is. Secondly, YBWC and ABDADA would NOT have found this node, because F312 is a "younger brother". F312 will not execute until F311* branch has been fully evaluated. So my methodology will safely and work-efficiently find parallel work that YBWC / ABDADA will not (before resorting to speculative execution).
Moving up the tree, we still have:
Under my "work-efficiency" requirement, we cannot execute this BetaBlocked tree consisting of F3122 and F3123 until F1, F2, and F311 are done executing. But look at how bad F3121 is: it is -44 (and the absolute minimum score under my eval() methodology is -50). There's a very high chance that speculative execution would work out here.
Now it appears that F311 = -AlphaBeta(P311, ...) == -20. Lets modify the Beta-Block question now.
I don't know where I'm going with this . But I think a simple heuristic may exist here for speculative execution. F1 and F2 are "top level" nodes, so they'll probably have a value closer to 0 because there are more choices available to both players. Furthermore, -44 is almost the lowest number by my scheme (the minimum is -50), so it is very unlikely for F1 or F2 to come out as 45+ and actually refute the F312B tree.
So it is probably safe to speculatively execute F312B, even if we don't know the F1 and F2 values yet.
Because all the futures are stored in the BetaBlock task, it is theoretically possible for the scheduler to perform logic on the expression-tree and figure out which Beta-blocked tasks have the lowest chance of refutation. Maybe sorting all BetaBlocked tasks by the score, and executing the smallest score values is best.
If F312B executes speculatively, (with F1 and F2 remaining unknown), the F3122 would look as follows:
Where F312BB represents the 2nd beta-block in the F312* subtree.
------
Relaxing the work-efficiency requirement will be a last resort, if I cannot figure out a way to be work-efficient here. If I do have to resort to speculative execution here, it seems like simple heuristics (such as sorting the Beta-Blocked list by current minimum score) could go a long way to minimizing wasted work.
The P3121* branch, and its parents, seems to satisfy all the situations I'm interested in. Here's my hand-done trace of execution:
Code: Select all
F = AlphaBeta(P, -Inf, +Inf)
// F1 and F2 execute in parallel, but are ignored for this example
F3 = -AlphaBeta(P3, -Inf, [F1, F2, Max, -])
F31 = -AlphaBeta(P31, [F1, F2, Max], +Inf])
F3B = BetaBlock(F31 >= [F1, F2, Max, -])
// F311 and F313 execute in parallel, but are ignored for this example
F312 = -AlphaBeta(P31, -Inf, [F1, F2, Max, F311, Max, -])
F3121 = -AlphaBeta(P31, [F1, F2, Max, F311, Max], +Inf)
F312B = BetaBlocked(F3121 >= [F1, F2, Max, F311, Max, -])
// Penultimate node, shortcut here for simplicity
F3121 = -Max(-eval(P31211), -eval(F31212), -eval(F31213))
Lets actually evaluate things, because numbers are easier to think than futures. My "evaluation" function for the purposes of these posts is hash(Position) = ((Position * 31415) / 1000) % 100. (The 5th and 4th digits after being multiplied by the arbitrary Pi-like number 31415). And remember, 50-99 are negative numbers, while 0-49 are positive numbers. We're working modulo 100 arithmetic.
"Physically", the numbers are represented from 0 to 99. Logically, the numbers are -50 to 49. (And -50 negated == -50, same quirk as in binary.)
Code: Select all
eval(P31211) = (31211 * 31415) // 1000 % 100 = 93
-eval(P31211) = -93 = 7
eval(P31212) = 24
-eval(P31212) = -24 = 76
eval(P31213) = 56
-eval(P31213) = -56 = 44
F3121 = -Max(-eval(P31211), -eval(F31212), -eval(F31213))
F3121 = -Max(7, -24, 44)
F3121 = -44
Moving up the tree, we still have:
Code: Select all
F312B = BetaBlocked(F3121 >= [F1, F2, Max, F311, Max, -])
F312B = BetaBlocked(-44 >= [F1, F2, Max, F311, Max, -])
Now it appears that F311 = -AlphaBeta(P311, ...) == -20. Lets modify the Beta-Block question now.
Code: Select all
F312B = BetaBlocked(-44 >= [F1, F2, Max, -20, Max, -])
So it is probably safe to speculatively execute F312B, even if we don't know the F1 and F2 values yet.
Because all the futures are stored in the BetaBlock task, it is theoretically possible for the scheduler to perform logic on the expression-tree and figure out which Beta-blocked tasks have the lowest chance of refutation. Maybe sorting all BetaBlocked tasks by the score, and executing the smallest score values is best.
If F312B executes speculatively, (with F1 and F2 remaining unknown), the F3122 would look as follows:
Code: Select all
F3122 = -AlphaBeta(P3122, [F1, F2, Max, F311, Max], 44)
F312BB = BetaBlocked(F3122 >= [F1, F2, Max, F311, Max, -])
------
Relaxing the work-efficiency requirement will be a last resort, if I cannot figure out a way to be work-efficient here. If I do have to resort to speculative execution here, it seems like simple heuristics (such as sorting the Beta-Blocked list by current minimum score) could go a long way to minimizing wasted work.