В общем, кратко, как это работает — а оно работает (см. тут):

1) Генерируем простым алгоритмом некоторое количество случайных прогулок по графу от собранного состояния до любых, куда заведёт генератор случайных чисел.

2) Компактифицируем дискретный граф 10^𝑛, переводя его в эмбеддинги в пространстве 𝑅^𝑑,где 𝑑≪𝑛. То есть пропускаем все сгенерированные состояния через нейросеть и говорим: вот это состояниe — оно на столько-то шагов от исходного. Учись, нейросеточка, на этом.

3) Пропускаем эти векторы через пару-тройку слоёв нейросети с нелинейностями — она ловит паттерны и учится одной простой вещи: предсказывать, насколько «близко к решению» текущее состояние, хотя никогда его напрямую не видела. Состояний-то слишком много. Поэтому ловим паттерны.

4) Beam Search делает своё дело: на каждом шаге проверяет варианты, смотрит на предсказанную «близость» и оставляет только топ‑k самых перспективных.

И вуаля — даже не видя все 10^n состояний, модель находит решение потому, что видит скрытые закономерности.

👆👆👆
Вообще, интересно наблюдать, как для решения задач в определённых алгебраических структурах могут применяться искусственные нейронные сети. Я пока занимался этим не так много, но вот что бросается в глаза: если у тебя есть какая-то, даже совсем не плохо исследованная математическая структура — например, симметрические группы как в случае с вверху обсуждаемыми вращательными пазлами — хочется понимать, какая нейросеть её «решает». Архитектура, размер пространства скрытых состояний, все гиперпараметры — хотелось бы видеть это как мост от известных математических инструментов к ИИ-системам, которые находят решения в этих структурах.

Да, можно решать пазлы методом тыка, подбирая размер сети и другие параметры «на глаз», но куда интереснее иметь какую-то теоретическую основу, которая объясняет, как из матаппарата структуры вырастает нейросеть, способная её эффективно обрабатывать 🤷‍♂️

начало тут 👆

🧩 Всем привет!

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

🎯 Суть
Нужно искать кратчайшие пути в графах Кэли — будь то оптимальные решения для куба Рубика 4×4×4 (Rubik’s Revenge), задачи на транспозоны или другие перестановочные головоломки.

В общем случае такие задачи NP-трудные.

Для малых размеров иногда можно найти оптимум, для больших — выигрывает тот, кто строит более короткие пути.

🔬 Научный контекст
Это классическая постановка: разложить элемент группы в произведение генераторов, или — найти путь в графе Кэли.

-Примеры: bubble sort, pancake sorting 🥞 (в котором, к слову, участвовал Билл Гейтс).

-Открытая гипотеза OEIS A065603 предсказывает, что диаметр (т.н. число Бога) равен ⌈(n+1)/2⌉ — она остаётся нерешённой уже 25 лет.

Важность темы подчёркивают работы М. Громова, Т. Тао и других. Дональд Кнут предлагал алгоритмические улучшения.

Применения: биоинформатика (оценка эволюционных расстояний), теория коммуникаций, оптимизация сетей и многое другое.

🤖 RL и компьютерные науки
Состояния = вершины графа Кэли.
Действия = рёбра (разрешённые перестановки).
Награды = всегда "1", пока не найдено решение (там 0).
Итого: классический RL с экстремально разреженной наградой.

Функция ценности = длина пути до решения, а уравнение Беллмана в этом случае напрямую отражает тривиальные соотношения на длинах путей.

Это отличная площадка для тестирования новых методов RL и pathfinding на пространствах колоссального размера (10³³ и больше).

🚀 Практика - соревнования
В соревнованиях можно попробовать себя не только с кубом Рубика, но и с другими задачами:

Pancake sorting
Transposons
Reversals
Glushkov problem
RapapportM2
Rubik's cube 444
Professor Tetraminx
Megaminx
Christophers jewel
SuperCube from IHES

Все они собраны в рамках проекта CayleyPy — это open-source crowd-sourcing инициатива для разработки AI-библиотеки по математике. Можно подключаться и вне Kaggle.

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

Продолжение тут и тут👇

#Puzzles #CayleyGraphs #SymmetricGroup #KaggleCompetitions

Вот несколько деталей и мотивация, почему это интересно 👆:

1️⃣ Соревнования только стартовали, а продлятся целый год — времени хватит на эксперименты, улучшения и изучение новых подходов.

2️⃣ Каждому пазлу прилагается ноутбук с примером решения.

Сегодня я выложу пример в Каггл пример ноутбука с решением для пазла Christopher’s Jewel. Но не обязательно решать так же.
Можно использовать любые методы — главное, кто найдёт самые короткие решения для заданного класса пазлов.

Если понадобится, могу помочь разобраться с ноутбуками.

3️⃣ Теоретический интерес:

Все эти соревнования основаны на нерешённых математических задачах о диаметре графа Кэли соответствующей группы.

Существует гипотеза о том, как диаметр растёт с увеличением числа элементов группы. Даже Теренс Тао пытался доказать её, но не смог.

Кто знает, может с помощью машинных методов именно вы добьётесь успеха? 💡

Например, чистые математики, которые тоже читают эту группу и не особо любят программировать и не занимаются МL могут скооперироваться с теми, кто любит программировать и МL - пишите в комменты!

4️⃣ Практическая сторона:

Некоторые задачи проще описать на примере кубика Рубика.
Для 3×3×3 известно так называемое число Бога — 20 вращений.
Для 4×4×4 и многих других головоломок диаметр не известен, и найти его — реально интересная и открытая проблема. Вот то что Теренс Тао не смог доказать, там ещё побиться надо, а это более реальный и вроде-бы быстрый, но таки новый математический результат! Есть возможность прославиться! 😀

5️⃣ И много других любопытных вопросов ждёт внутри соревнований: оптимальные пути, перестановочные головоломки, алгоритмические эксперименты, RL с разреженной наградой и т.д.

🚀 В общем, есть где развернуться и проверить себя на пересечении математики, программирования и AI.

Хотите лайв-стрим с введением в эти темы и парой советов как лучше в эту тему вьехать?

🚀 Соревнования по ИИ в графах Кэли / подгруппах симметрической группы: дата и время лайв-стрима?

Для пазла Christopher's Jewel уже сам Томас Рокицки засабмитил решение — тот самый исследователь, который доказал, что число Бога для кубика Рубика 3×3×3 равно 20. Надо попробовать побить решения Томаса на остальных пазлах :-)

Сейчас готовлю ноутбук с решением Christopher's Jewel — он будет в открытом доступе самое позднее в понедельник. Можно использовать его как основу, но совершенно не обязательно: подойдут любые подходы к поиску кратчайших решений. Хотите — используйте RL, хотите — другие методы. Главное — искать именно минимальные сборки.

👉 Число Бога для Christopher's Jewel пока не известно. Экспериментально у меня получается максимум 18 вращений, но это не доказано.


Остальные пазлы для соревнования:

Pancake sorting
Transposons
Reversals
Glushkov problem
RapapportM2
Rubik's cube 444
Professor Tetraminx
Megaminx
Christophers jewel
SuperCube from IHES


📺 На следующей неделе хочу провести лайв-стрим с введением в эти темы и формат соревнований чтобы понизить порог входа в эту тему. Когда вам удобно? Напишите в комментариях