In place min-max tree invalidation problems

Question

I’m trying to build a parallel implementation of a min-max search. My current approach is to materialize the tree to a small depth and then do the normal thing from each of these nodes.

The simple way to do this is to compute the heuristic value for each leaf and then sweep up and compute the min/max. The problem is that it this omits alpha/beta pruning at the upper levels and makes for a major performance hit.

My first “solution” to that was to push the min/max up after each leaf is computed. This gives updating value so I can scan up the tree and check if a leaf should be pruned.

The problem is that it's totally broken. (2 days of debugging to notice that, darn I feel stupid)

Now for the question:

Is there a way to build a min-max tree that allows the leafs to be evaluated in random order and also allows alpha/beta pruning?

Answer 1

I think I have found a solution but I don't like it in a few regards:

1. Annotate the tree with the number of unfinished children.
2. After a leaf is evaluated, update it's parent, decrement the parent's count
3. If that count just reached zero, update it's parent, decrement that count
4. Lather, rise, repeat

Alpha/beta pruning works as expected.

The problems with this is that with random order evaluation, a lot more nodes will get evaluated before stuff starts getting pruned. On the other hand, that might be mitigated by better ordering of the leafs.

Answer 2

Check out parallel game tree search, e.g. this paper.