Как распараллелить алгоритм Negamax?
Есть ли способ распараллелить следующий алгоритм Negamax?
01 function negamax(node, depth, color)
02 if depth = 0 or node is a terminal node
03 return color * the heuristic value of node
04 bestValue := −∞
05 foreach child of node
06 v := −negamax(child, depth − 1, −color)
07 bestValue := max( bestValue, v )
08 return bestValue
2 ответа
Когда сформулировано так, как единственная рекурсивная функция, не легко.
Самый простой способ - разделить его на две функции: одну специально для самого первого вызова в корне дерева, а затем другую функцию, которая вызывается и также рекурсивно продолжает вызывать себя. В корневой версии вы могли бы распараллелить цикл через дочерние элементы и сохранить различные значения в списке. Тогда вам просто понадобится непараллельный цикл, чтобы найти максимум из списка, но это будет сделано мгновенно.
Обратите внимание, что если вы перейдете к улучшениям, таким как альфа-бета-обрезка, это станет намного сложнее; наивное распараллеливание первого цикла, как я предложил здесь, значительно сократит количество узлов, которые могут быть отсечены альфа-бета-отсечкой
Топология + чистая [SERIAL] Цепочка зависимостей решает игру:
Принимая во внимание древовидную топологию, использование рекурсивной формулировки является не причиной, а скорее следствием, поскольку рекурсивная формулировка настолько проста для наброска и кодирования. (Для тех, кто действительно интересуется информатикой, просто сравните потребление ресурсов рекурсивно сформулированных вычислительных стратегий и выполните тестирование (как в [SPACE] - а также [TIME] -домены) как скоро это начинает создавать проблемы, как только масштабирование вашего эталонного теста немного выходит за рамки масштабов проблем в учебниках и / или выходит за рамки выбора дизайнеров в этой самой ограничивающей ресурсы дилемме о том, насколько глубокие уровни рекурсии справедливы для ожидания и выделить ресурсы и что будет дальше, если рекурсии попытаются погрузиться на шаг глубже, чем этот "предварительно смонтированный" стеклянный потолок случился).
Как превратить это в истинно [PARALLEL] вычислительный график?
Вопрос о шансах найти правдивую [PARALLEL] Стратегия обработки принимается прямо при поиске непараллельного [SERIAL] цепочки зависимостей, которые начинаются от каждого из терминальных узлов и продвигаются назад, к корневому узлу дерева.
Древовидная топология требует своего рода "передачи" взаимозависимостей, которые появляются во время обратного обхода дерева, поэтому все главные преимущества [PARALLEL] график обработки может позволить эффективно теряются при такой необходимости для передачи продуктов [SERIAL] цепочки зависимостей значений до "следующего", нелокального выполнения потока выполнения кода. Это делает оригинальную идею анти-паттерном.
Осознав это принципиально чисто [SERIAL] зависимости, любые попытки принудительного распараллеливания остаются возможными, но результаты их работы становятся скорее антишаблоном, чем любым разумно поддерживаемым выбором, поскольку на самом деле они будут стоить дороже (в [TIME] -домен), чем последовательная цепочка обработки (формулируется рекурсивно или нет), учитывая [SPACE] -домен разрешает такой способ работы.