Как написать многопоточный алгоритм альфа-бета-поиска?

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

Однако есть еще несколько способов сделать это, большинство из них довольно сложны и крайне плохо масштабируются при большем количестве потоков. Алгоритм перехода раньше был концепцией ожидания Young Brothers, это довольно сложный алгоритм, и он использовался, например, Stockfish до нескольких лет назад. Однако с увеличением количества ядер, доступных на современных компьютерах, масштабирование было очень плохим, а код очень сложным. Сегодня большинство современных движков используют то, что называется Lazy SMP. Этот алгоритм настолько прост, насколько это возможно, и масштабируется лучше, чем другие.

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

Я рекомендую вам заглянуть на вики по шахматному программированию, где вы даже можете найти псевдокод того, как это реализовать. https://www.chessprogramming.org/Lazy_SMP

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