Проблемы с недействительностью дерева min-max

Question

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

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

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

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

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

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

Answer 1

Отъезд параллельная игра дерево поиск, например. this paper.

Answer 2

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

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

Альфа/бета-обрезка работает, как ожидалось.

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