Есть какие-нибудь предложения по алгоритму поиска распределенного параллельного дерева?

Question

Я пишу распределенного бота Go / Gomoku.

По сути, суть в том, чтобы распространить древовидный поиск на множество компьютеров.С базовыми алгоритмами поиска по дереву, такими как DFS, это было бы очень просто, так как я мог бы просто разбить пространство поиска на поддеревья.Хотя я бы предпочел что-то более эффективное, например mini-max с альфа-бета обрезкой, но, насколько я понимаю, это совершенно бессмысленно без какой-либо общей памяти.Так что я вроде как застрял.

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

Спасибо,

Answer 1

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

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

Несколько слайдов

Тот Самый Домашняя страница MoGo

Смотрите раздел "Последние события" в Страница Википедии на компьютере go.

Answer 2

Попробуйте подход Map Reduc.Например, см.

Поиск в ширину (BFS) и MapReduce

Answer 3

ДДС* и АБДАДА — это 2 распределенных/параллельных минимаксных алгоритма.Необходима некоторая связь, но это можно сделать путем передачи определенных результатов обратно контроллеру.

Как вы упомянули, более простой подход - это что-то вроде сокращения карты с разными корнями дерева поиска.

Как @Паскаль Куок справедливо упоминает, Поиск по дереву Монте-Карло — это новейшая разработка в Go.

Здесь вы можете найти хорошее объяснение алгоритма поиска MoGo и его распараллеливания:

http://www.lri.fr/~gelly/paper/nips_exploration_exploitation_mogo.pdf

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

хороший обзор поиска по дереву Монте-Карло находится здесь:

http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf