CayleyPy и кубик Рубика: как нейросеть превосходит классический поиск
Habr ·
Задача сборки механических головоломок за минимальное количество ходов формализуется как поиск кратчайшего пути в графе Кэли. Вершинами такого графа являются допустимые состояния головоломки, а ребрами – допустимые ходы, переводящие одно состояние в другое. Для классического кубика Рубика 3×3×3 диаметр графа был определен в 2010 году Томасом Рокицки с коллегами – число Бога составило 20 ходов в метрике HTM (Half-Turn Metric). Однако для головоломок больших размеров – кубиков 4×4×4, 5×5×5, биг-кубов, мегаминкса – точное значение диаметра графа Кэли остается неизвестным. Проект CayleyPy развивает серию соревнований на платформе Kaggle, посвященных поиску оптимальных и субоптимальных путей в графах Кэли с огромным числом состояний. В этой статье я разберу архитектуру нейросетевого пайплайна CayleyPy, проанализирую результаты завершившихся конкурсов и расскажу о текущих контестах для больших кубов, где участвую как член команды. Крутить далее
Задача сборки механических головоломок за минимальное количество ходов формализуется как поиск кратчайшего пути в графе Кэли. Вершинами такого графа являются допустимые состояния головоломки, а ребрами – допустимые ходы, переводящие одно состояние в другое. Для классического кубика Рубика 3×3×3 диаметр графа был определен в 2010 году Томасом Рокицки с коллегами – число Бога составило 20 ходов в метрике HTM (Half-Turn Metric). Однако для головоломок больших размеров – кубиков 4×4×4, 5×5×5, биг-кубов, мегаминкса – точное значение диаметра графа Кэли остается неизвестным. Проект CayleyPy развивает серию соревнований на платформе Kaggle, посвященных поиску оптимальных и субоптимальных путей в графах Кэли с огромным числом состояний. В этой статье я разберу архитектуру нейросетевого пайплайна CayleyPy, проанализирую результаты завершившихся конкурсов и расскажу о текущих контестах для больших кубов, где участвую как член команды. Крутить далее