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

Question

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

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

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

Спасибо,

Answer 1

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

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

Some slides

MoGo homepage

Смотрите раздел "последние изменения" в Wikipedia page on computer go.

Answer 2

DDS* и ABDADA 2 распределенные/алгоритмы параллельных минимаксными. Требуется некоторая связь, но это может быть сделано путем передачи определенных результатов обратно контроллеру.

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

As @Pascal Cuoq rightly mentions, Monte Carlo Tree Search - это современное состояние в 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

Answer 3

Попытка сопоставить подход к сокращению. Например, см

Breadth-First Search (BFS) & MapReduce