Альфа-бета «взлом» закон Амдаля?
У меня есть классическое минимаксное решение проблем с дополнительной реализацией сокращения альфа-бета.
Я распараллелил алгоритм следующим образом:
- Делайте итеративное углубление, пока у нас не будет больше узлов, чем доступных потоков
- Запускайте один минимакс на поток в пакетах из N потоков. Таким образом, если мы получаем 9 возможных ходов на глубине 2 из последовательного поиска, мы сначала запускаем 4 потока, затем еще 4, а затем 1 в конце, каждый из которых начинается на глубине 2 со своими собственными параметрами.
Получается, что ускорение S = T (последовательный) / T (параллельный) для 4 потоков составляет 4,77, поэтому я в основном нарушаю закон Амдала здесь.
Если мы говорим, что реализация каким-то образом не нарушена, я подозреваю, что альфа-бета-обрезка делает магию здесь? Благодаря параллельному запуску нескольких поисков происходит рано? Это моя теория, но я бы с удовольствием, если бы кто-то мог подтвердить это более подробно.
Просто для ясности:
Минимакс без альфа-бета-реализации в основном выполняет поиск в глубину целое дерево до некоторой максимальной глубины.
С альфа-бета он делает то же самое, за исключением того, что обрезает некоторые ветви, что в любом случае приведет к худшему результату.
Изменить: После дальнейшего изучения кода у меня была ошибка в одной строке кода, которая заставила программу «обманывать» и не выполнять некоторые шаги. Фактический коэффициент ускорения сейчас составляет 3,6. Извините за трату времени всех .. сегодня нет прорыва в вычислительной технике. : /
Решение
Это может быть связано с эффектом кэша или подобным. Это называется суперлинейное ускорение. Это может случиться.
Другие решения
Используя больше потоков, вы эффективно запускаете частичный поиск в ширину. Просто так получается, что ваша проблема поддается поиску в ширину.
Даже на одноядерном компьютере вы увидите ускорение.
Вам не нужны потоки для достижения этого ускорения. Вы можете просто запрограммировать (частичный) поиск в ширину, который будет вести себя как несколько потоков.
Представьте, что вы хотите найти два списка:
-
1 миллион раз
0, затем1 -
1, то 1 миллион раз0
И вы остановитесь, как только найдете 1, Если вы будете искать их последовательно, вам нужно посмотреть на 1 000 002 элементов. Если вы используете две темы на одном ядре, поиск сразу найдет 1 и вы сделали. «Суперлинейное» ускорение в 1 000 000 раз или около того!