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

Question

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

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

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

Спасибо

Answer 1

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

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

Некоторые слайды

Домашняя страница MoGo

См. Раздел «последние разработки» на странице Википедии на компьютере. .

Answer 2

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

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

Answer 3

DDS * и ABDADA - это 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