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.