Вместо мин-макс проблемы с недействительностью дерева

Question

Я пытаюсь построить параллельную реализацию поиска min-max . Мой текущий подход состоит в том, чтобы материализовать дерево на небольшую глубину, а затем выполнить обычные действия с каждого из этих узлов.

Простой способ сделать это - вычислить эвристическое значение для каждого листа, а затем развернуть и вычислить мин / макс. Проблема в том, что при этом на верхних уровнях исключается альфа / бета-отсечение , что делает основной удар по производительности.

Моим первым «решением» было повышение мин / макс после вычисления каждого листа. Это дает значение обновления, так что я могу отсканировать дерево и проверить, нужно ли удалить лист.

Проблема в том, что он полностью сломан. (2 дня отладки, чтобы заметить это, черт возьми, я чувствую себя глупо)

Теперь на вопрос:

Есть ли способ построить минимальное-максимальное дерево, которое позволяет оценивать листья в случайном порядке, а также позволяет выполнять альфа / бета-обрезку?

Answer 1

Оформить поиск по дереву параллельных игр , например эта бумага .

Answer 2

Я думаю, что нашел решение, но мне не нравится его в нескольких отношениях:

1. Аннотируйте дерево с количеством незаконченных детей.
2. После оценки листа обновите его родителя, уменьшите счет родителя
3. Если это число только что достигло нуля, обновите его родитель, уменьшите это число
4. вспенить, встать, повторить

Альфа / бета-обрезка работает как положено.

Проблемы с этим заключаются в том, что при оценке случайного порядка намного больше узлов будут оцениваться до того, как материал начнет сокращаться. С другой стороны, это могло бы быть смягчено лучшим упорядочением листьев.