распределенная альфа-бета-обрезка

19

Я ищу эффективный алгоритм, который позволил бы мне обрабатывать минимаксное дерево поиска шахмат с альфа-бета-отсечкой в распределенной архитектуре. Алгоритмы, которые я нашел (PVS, YBWC, DTS см. Ниже), все довольно старые (1990 год - самый последний). Я предполагаю, что с тех пор было много существенных улучшений. Каков текущий стандарт в этой области?

Также, пожалуйста, укажите мне объяснение DTS идиота, поскольку я не могу понять его из исследовательских работ, которые я прочитал.

Алгоритмы, упомянутые выше:

  • PVS: принцип вариации расщепления
  • YBWC: концепция молодых братьев подождет
  • DTS: динамическое расщепление деревьев

все обсуждаются здесь .

algorithms distributed-systems board-games wirate
источник
Может быть, это интересное чтение: chessbase.com/newsdetail.asp?newsid=8047
Алекс тен Бринк
2
Ну, это проблема (распараллеливание минимаксного поиска или любого его варианта), особенно сложная. В статье, опубликованной в этом году Ричардом Корфом и озаглавленной «Задачи исследования в комбинаторном поиске», можно прочитать следующее: «[...] поиск минимакса с отсечкой альфа-бета, как известно, трудно распараллелить», я искренне сомневаюсь есть алгоритм, который делает это всегда эффективно ...
Карлос Линарес Лопес
Итак, учитывая, что я всего лишь очень скромный студент 4-го семестра по информатике, должен ли я перейти на сериализованный алгоритм или попытаться ожидать некоторого приемлемого сублинейного ускорения?
wirate
Извините за задержку в моем ответе, это прошло совершенно незаметно в моем почтовом ящике. На самом деле, я ожидал бы, что окончательная экономия будет полностью зависеть от распределения оценок, назначенных вашей функцией оценки, на листья дерева поиска. В общем, нет никаких гарантий, что алгоритм распределенного поиска будет работать значительно лучше, чем алгоритм сериализованного поиска альфа-бета. Таким образом, я бы определенно пошел на сериализованную версию, пробуя как можно больше улучшений (упорядочивание ходов, таблицы транспонирования и т. Д.)
Карлос Линарес Лопес
У меня был некоторый успех с параллельной альфа-бета (в основном, как описано на странице вики, на которую вы ссылались).
Джереми Список

Ответы:

3

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

Основная идея DTS заключается в том, что деревья поиска распределяются между вычислительными узлами на основе сложности перемещения / размещения. неиспользуемые процессоры, которые «досрочно заканчивают», могут выполнять дополнительную работу помимо первоначального распределения, которое может быть распределено как можно более равномерно вначале, но окажется неравномерным. следовательно, это в основном своего рода очередь «балансировки нагрузки» и «производитель / потребитель» , или также похожая на планирование заданий.

Этот неработающий процессор передает (используя совместно используемую память), что он не используется, и доступен, чтобы «помочь» любому другому процессору завершить поиск в его дереве. Занятые процессоры собирают данные о «состоянии дерева» и сохраняют их в общей памяти для проверки незанятым процессором. Этот неработающий процессор анализирует эти данные и решает, какой из (если таковые имеется) занятых процессоров, по-видимому, имеет достаточно сложное дерево, чтобы эффективно помочь с поиском. Если такая позиция найдена, незанятый процессор информирует об этом процессор, которому принадлежит этот узел, и они «объединяют» силы.

ВЗН
источник