Какие-либо распределенные параллельные предложения алгоритма поиска по дереву?
Я пишу распределенного бота Go/Gomoku.
В основном точка должна распределить поиск по дереву на многие компьютеры. С основными алгоритмами поиска по дереву как DFS это было бы очень просто, поскольку я мог просто разделить пространство поиска в поддеревья. Хотя у меня было бы что-то более эффективным, как минимакс с сокращением альфы - беты - но от моего понимания это довольно бессмысленно без любого вида общей памяти. Таким образом, я отчасти застреваю.
Какие-либо идеи, какой алгоритм я мог использовать, это эффективно и распределено легко? И что еще более важно, где я могу найти некоторый (псевдо) код для него или возможно реализацию?
Спасибо,
3 ответа
Что касается одноручных клавиатур, я попробовал использовать фрогпад и нашел его приемлемым для ввода текста, но непригодным для кодирования. Символы требуют нескольких последовательных нажатий клавиш, и я счел невозможным использовать ярлыки надежно. Было слишком легко нажать не на ту клавишу и застрять в неправильном режиме.
-121--2560165-DDS * и ABDADA - это 2 распределенных/параллельных минимаксовых алгоритма. Некоторая связь необходима, но это может быть сделано путем передачи определенных результатов обратно в контроллер.
Более простой подход, как вы упомянули, будет что-то вроде сокращения карты с различными корнями дерева поиска.
Как справедливо упоминает @ Pascal Cuoq , Поиск дерева Монте-Карло является самым современным в Go.
Здесь вы можете найти хорошее объяснение алгоритма поиска MoGo и того, как его параллелизованные:
http://www.lri.fr/~gelly/paper/nips_exploration_exploitation_mogo.pdf
узлы, которые играют с лучшими результатами, основанными на случайной игре, более глубоко изучены. На каждом шаге выбирается листовой узел для однослойного расширения. Это может быть распределено, если каждая машина выберет свой лист для расширения.
хороший обзор поиска в дереве monte carlo здесь:
http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf
-121--3677671-Вам нужно прочитать о Поиске Дерева Монте-Карло не потому, что его по своей сути легче распространять (это не легче и не сложнее, чем другой поиск дерева), а потому, что это современное состояние и что люди, работающие над проблемой, работают над распределенной версией этого алгоритма.
Если у вас возникнут проблемы с созданием распределенного алгоритма, нет причин начинать с меньшего. Если вы не создадите распределенный алгоритм по образовательным причинам, в этом случае, вперед, будет что-то глубоко образовательное в эксперименте по распространению базового алгоритма и видеть, что он работает хуже, чем не распределенный современный алгоритм:)
MoGo Смотрите раздел «Последние разработки» на странице Википедии
DDS* и ABDADA - это 2 распределенных/параллельных минимаксных алгоритма. Необходима некоторая коммуникация, но это может быть сделано путем передачи определенных результатов обратно контроллеру.
Более простой подход, как вы упомянули, был бы чем-то вроде map reduce с различными корнями дерева поиска.
Как справедливо отмечает @Pascal Cuoq, поиск по дереву Монте-Карло является передовым в 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