Альфа-бета "нарушает" закон Амдала?

Question

У меня есть классическое минимаксное решение проблем с дополнительной реализацией сокращения альфа-бета.

Я распараллелил алгоритм следующим образом:

1. Делайте итеративное углубление, пока у нас не будет больше узлов, чем доступных потоков
2. Запускайте один минимакс на поток в пакетах из N потоков. Таким образом, если мы получаем 9 возможных ходов на глубине 2 из последовательного поиска, мы сначала запускаем 4 потока, затем еще 4, а затем 1 в конце, каждый из которых начинается на глубине 2 со своими собственными параметрами.

Оказывается, что ускорение S=T(последовательный)/T(параллельный) для 4 потоков составляет 4,77, поэтому я в основном нарушаю закон Амдала здесь.

Если мы говорим, что реализация каким-то образом не нарушена, я подозреваю, что альфа-бета-обрезка делает магию здесь? Из-за запуска нескольких поисков параллельно, есть еще обрезка ираньше? Это моя теория, но я бы с удовольствием, если бы кто-то мог подтвердить это более подробно.

Просто для ясности:

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

Редактировать: После дальнейшего изучения кода у меня была ошибка в одной строке кода, которая заставляла программу "обманывать" и не выполнять некоторые действия. Фактический коэффициент ускорения сейчас составляет 3,6. Извините за трату времени каждого.. сегодня нет прорыва в вычислительной технике.:/

Answer 1

Это может быть связано с эффектом кэша или подобным. Это называется суперлинейным ускорением. Это может случиться.

Answer 2

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

Даже на одноядерном компьютере вы увидите ускорение.

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

Представьте, что вы хотите найти два списка:

• 1 миллион раз 0, затем 1

• 1, то 1 миллион раз 0

И вы остановитесь, как только найдете 1, Если вы будете искать их последовательно, вам нужно посмотреть на 1 000 002 элементов. Если вы используете две темы на одном ядре, поиск сразу найдет 1 и вы сделали. "Суперлинейное" ускорение в 1 000 000 раз или около того!