Любые предложения по алгоритму поиска в параллельном дереве?
Я пишу распределенный бот Go/Gomoku.
По сути, дело в том, чтобы распространять поиск по дереву на многие компьютеры. С базовыми алгоритмами поиска по дереву, такими как DFS, это было бы очень просто, так как я мог бы просто разделить пространство поиска на поддеревья. Хотя я бы предпочел что-то более эффективное, например, мини-макс с альфа-бета-обрезкой, но, насколько я понимаю, это совершенно бессмысленно без какой-либо общей памяти. Так что я застрял.
Любые идеи, какой алгоритм я мог бы использовать, который эффективен и легко распространяется? И что еще более важно, где я могу найти некоторый (псевдо) код для него или, может быть, реализацию?
Спасибо,
3 ответа
Вы должны прочитать о поиске по дереву Монте-Карло не потому, что его по сути проще распространять (это не проще и не сложнее, чем поиск по другому дереву), а потому, что это состояние дел, и люди, работающие над проблемой, работают над распределением версия этого алгоритма.
Если вы собираетесь создать распределенный алгоритм, нет причин начинать с меньшего. Если вы не создадите распределенный алгоритм по образовательным причинам, в таком случае, вперед, в эксперименте по распространению базового алгоритма будет происходить что-то очень познавательное, и вы увидите, что он работает хуже, чем нераспределенный современный алгоритм:)
Смотрите раздел "последние разработки" на странице Википедии на компьютере go.
Попробуйте Map Reduce подход. Например, см.
DDS* и ABDADA - это 2 распределенных / параллельных минимаксных алгоритма. Некоторая связь необходима, но это можно сделать, передав определенные результаты обратно контроллеру.
Упрощенный подход, как вы упомянули, будет что-то вроде сокращения карты с различными корнями дерева поиска.
Как справедливо отмечает @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