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

**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:

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, -])`

**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:

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.