🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

Dit artikel presenteert het CayleyPy-project, dat versterkt leren combineert met diffusie-afstandsmethoden om padvinding op massale Cayley-graaf efficiënt op te lossen, klassieke hulpmiddelen zoals GAP succesvol overtreft, sterke aanwijzingen biedt voor de OEIS-A186783-conjectuur betreffende de diameter van de symmetrische groep, nieuwe theoretische grenzen vastlegt en uitnodigt tot gemeenschapsdeelname via Kaggle-uitdagingen.

Oorspronkelijke auteurs: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

Gepubliceerd 2026-05-19

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: De Kortste Weg Thuis Vinden in een Labyrint van Spiegels

Stel je voor dat je in een gigantisch, oneindig labyrint zit. Maar dit is geen normaal labyrint met muren; het is een labyrint gemaakt van regels. Elke keer als je een stap zet, volg je een specifieke regel die je positie verandert. In de wiskunde heet dit een Cayley-graf.

Het doel van dit paper is om een specifiek type labyrint op te lossen: het LRX-labyrint. Dit labyrint is gebouwd met de regels van het schudden van een kaartspel (of een permutatie van getallen).

Regel L: Schuif alles één plek naar links.
Regel R: Schuif alles één plek naar rechts.
Regel X: Wissel de eerste twee items om.

De uitdaging is: als je begint met een kaartspel in een rommelige volgorde, wat is dan de kortste reeks van Links, Rechts en Omwissel-bewegingen om ze terug te krijgen in de perfecte volgorde?

Het Probleem: Het Labyrint is Te Groot voor Mensen (en Oude Computers)

Voor een klein kaartspel kan een mens of een standaard computerprogramma (zoals de beroemde wiskundesoftware GAP) de oplossing vinden. Maar naarmate het aantal kaarten ( $n$ ) groeit, explodeert het aantal mogelijke rangschikkingen.

Voor $n=20$ is het labyrint enorm.
Voor $n=100$ is het labyrint zo groot dat het meer paden heeft dan er atomen in het universum zijn.

Oude computerprogramma's raken in de war. Ze proberen elk enkel pad in kaart te brengen, raken hun geheugen op en geven het op. De auteurs wilden zien of Kunstmatige Intelligentie (AI) kon fungeren als een slimme ontdekkingsreiziger om de weg te vinden door deze enorme labyrinten zonder elke centimeter in kaart te brengen.

De Oplossing: Een AI Leren om de Weg te "Raden"

De auteurs bouwden een systeem genaamd CayleyPy RL. Denk hierbij aan het trainen van een robot om door het labyrint te navigeren. Ze gebruikten een methode genaamd Versterkend Leren (Reinforcement Learning - RL).

Hier is hoe ze de robot trainden, met een eenvoudige analogie:

1. De "Opwarmfase" (Diffusie-afstand)
Stel je voor dat je een druppel inkt in een glas water laat vallen. De inkt verspreidt zich willekeurig. Als je wilt weten hoe ver een specifieke plek is van het centrum, kun je kijken hoe lang het duurt voordat de inkt daar aankomt.

De AI leerde eerst door miljoenen "willekeurige wandelingen" (zoals de inkt die zich verspreidt) te bekijken. Het wist niet het kortste pad, maar het leerde een "gevoel" van afstand. Het wist: "Als ik hier ben, duurt het meestal ongeveer 50 willekeurige stappen om thuis te komen."
Dit gaf de AI een ruwe kaart, maar het was niet perfect.

2. De "Slimme Training" (Versterkend Leren)
Vervolgens leerden ze de AI slimmer te zijn. In plaats van alleen te gokken op basis van willekeurige wandelingen, gebruikten ze een techniek genaamd Deep Q-Learning.

Stel je voor dat de AI een spel speelt waarbij het een "straf" krijgt voor elke stap die het zet. Het wil de finish bereiken met de minste straffen.
De AI probeerde verschillende zetten, zag welke het dichter bij de finish brachten, en paste zijn hersenen (neuraal netwerk) aan om betere voorspellingen te doen.
De Innovatie: Ze combineerden het "inkt-verspreiding" intuïtie met de "spel spelen" logica. Dit hielp de AI om vast te lopen in doodlopende straten (lokale minima) die meestal eenvoudigere algoritmen opsluiten.

3. De "Beam Search" (Het Team van Ontdekkingsreizigers)
Dit is het meest cruciale deel. Stel je voor dat je één ontdekkingsreiziger het labyrint in stuurt. Als ze een verkeerde afslag nemen, ben je ze kwijt.

In plaats daarvan stuurden de auteurs een team van ontdekkingsreizigers uit (een "beam").
Bij elke kruising splitst het team zich. Ze houden de top 10.000 meest veelbelovende paden en gooien de slechte eruit.
Door een enorm team te houden (in sommige gevallen miljoenen paden), zorgt de AI ervoor dat zelfs als de meeste ontdekkingsreizigers verdwalen, er ten minste één de perfecte kortste weg vindt.

De "Magische Truc" (De X-Truc)

De auteurs ontdekten een grappig klein trucje. In hun code voegden ze een enkele regel logica toe:

Als de eerste twee kaarten al in de juiste volgorde zitten, wissel ze dan niet om.

Het klinkt voor een mens vanzelfsprekend, maar voor een computer was het een gamechanger. Deze kleine regel, die ze de "X-truc" noemden, stelde hun AI in staat om labyrinten met 100 kaarten ( $n=100$ ) op te lossen.

Zonder de truc: De AI kon ongeveer 40 kaarten aan.
Met de truc: Het kon 100+ kaarten aan, en versloeg de oude computersoftware (GAP) die crashte rond de 20 kaarten.

Wat Bewezen Ze? (Het Wiskundige Deel)

Naast het bouwen van een snelle solver, gebruikten ze hun AI om ontdekkingen te doen over de wiskunde van deze labyrinten:

De "God's Number" Vermoeden: Er is een beroemd vermoeden in de wiskunde dat de moeilijkste mogelijke shuffle van $n$ kaarten precies $n(n-1)/2$ bewegingen vereist. De AI testte dit voor enorme getallen en vond nooit een shuffle die moeilijker was dan dit. Het ondersteunt sterk het idee dat deze formule het absolute limiet is.
De "Langste" Shuffle: Ze identificeerden de enige meest chaotische shuffle die mogelijk is (het "langste element") en bewezen precies hoe deze op te breken is in bewegingen.
Nieuwe Grenzen: Ze bewezen wiskundig dat het labyrint niet kleiner kan zijn dan een bepaalde grootte en niet groter kan zijn dan een andere grootte, waardoor het antwoord aanzienlijk wordt ingeperkt.
De Vorm van het Labyrint: Ze ontdekten dat als je telt hoeveel shuffles er bestaan op elke afstand van het startpunt, de getallen geen perfecte klokkromme volgen (zoals een normale verdeling). In plaats daarvan volgen ze een vreemde, scheve vorm die een Gumbel-verdeling wordt genoemd.

De Resultaten: AI versus De Oude Garde

Het paper vergelijkt hun nieuwe AI-methode met het standaard computeralgebrasysteem GAP:

GAP: Kan tot ongeveer 20 kaarten oplossen. Het duurt uren of dagen. De paden die het vindt zijn vaak lang en inefficiënt.
CayleyPy RL (AI): Kan tot ongeveer 100 kaarten oplossen. Het is veel sneller. Het vindt paden die zeer dicht bij het theoretisch kortst mogelijke pad liggen.

Samenvatting

De auteurs creëerden een slim AI-systeem dat complexe wiskundeproblemen behandelt als een gigantisch labyrint. Door willekeurig gissen te combineren met slim leren en een enorm "team" virtuele ontdekkingsreizigers uit te sturen, kunnen ze labyrinten navigeren die te groot zijn voor traditionele computers. Ze vonden zelfs een kleine "cheat code" (de X-truc) die hen in staat stelt problemen op te lossen die 5 keer zo groot zijn als voorheen, terwijl ze tegelijkertijd nieuwe wiskundige feiten bewijzen over hoe deze labyrinten zijn gestructureerd.

Ze hebben ook hun code en uitdagingen op een platform genaamd Kaggle gezet, waarbij ze andere mensen uitnodigen om te proberen hun records te breken en te helpen nog moeilijkere versies van deze puzzels op te lossen.

Technische Samenvatting: CayleyPy RL: Padvinding en Versterkend Leren op Cayley-graaf

Probleemstelling
Het artikel behandelt het probleem van padvinding op uiterst grote eindige Cayley-graaf, met name gericht op de symmetrische groep $S_n$ gegenereerd door linkse cyclische verschuivingen ( $L$ ), rechtse cyclische verschuivingen ( $R$ ), en een transpositie van de eerste twee elementen ( $X$ ). Deze configuratie, bekend als de LRX-Cayley-graaf, correspondeert met de OEIS-reeks A186783. De kern van de wiskundige uitdaging ligt in het ontbinden van een groepselement in het kortst mogelijke product van generatoren (het vinden van het kortste pad in de graaf). Dit probleem is NP-hard voor generieke eindige Cayley-graaf. Klassieke computeralgebrasystemen, zoals GAP, vertrouwen op het Schreier-Sims-algoritme, dat vaak exponentieel lange paden produceert en faalt bij groepen met groottes boven $10^{30}$ (ongeveer $n \approx 20$ voor $S_n$ ). De auteurs streven ernaar efficiënte, op kunstmatige intelligentie gebaseerde benaderingen te ontwikkelen die in staat zijn om graaf met groottes tot $10^{70}$ (bijv. $n \approx 40$ tot $100$) te verwerken, terwijl ze bijna-optimale of optimale paden produceren.

Methodologie
De auteurs stellen een hybride methodologie voor die Versterkend Leren (RL), specifiek Deep Q-Learning (DQN), combineert met een voortrainingsstrategie gebaseerd op diffusie-afstanden.

RL-kader: Het padvindingsprobleem wordt geformuleerd als het vinden van het kortste pad van een toestand $s$ naar het identiteitselement $e$ . Dit wordt gemodelleerd met de Bellman-vergelijking, waarbij de afstandsfunctie $d(s)$ voldoet aan $d(s) = 1 + \min_{t \in N(s)} d(t)$ . Standaard DQN wordt aangepast om deze waardenfunctie te benaderen met neurale netwerken.
Diffusie-afstand voortraining: Om het probleem van "spare beloningen" en de ruis inherent aan standaard DQN-initialisatie aan te pakken, introduceren de auteurs een "warm-up"-fase. Ze genereren trainingsdata via willekeurige wandelingen (diffusie) die beginnen bij het doel. Een neuraal netwerk wordt eerst getraind om het aantal stappen in deze willekeurige wandelingen (diffusie-afstand) te voorspellen.
Aangepast DQN: Het voorgetrainde netwerk wordt vervolgens fijngesleurd met een aangepast DQN-algoritme. Cruciaal is dat de Bellman-update-doelen worden afgeknipt op basis van de tijdstap $k$ waarop een toestand voor het eerst werd bezocht tijdens de generatie van willekeurige wandelingen. Dit voorkomt dat het netwerk afstanden overschat en stabiliseert de training.
Geleide Beam Search: Zodra het neurale netwerk is getraind om afstanden te schatten, fungeert het als een heuristische functie voor een beam search-algoritme. De beam search houdt een vast aantal ( $W$ ) van de meest veelbelovende toestanden bij elke stap bij, breidt hun buren uit en selecteert de top $W$ op basis van de voorspellingen van het netwerk. Dit voorkomt dat men vastloopt in lokale minima, een veelvoorkomende faalmodus voor greedy search.
De "X-truc": Een specifieke heuristische modificatie voor de LRX-generatoren wordt geïntroduceerd. Als de eerste twee elementen van een permutatie al gesorteerd zijn, wordt de generator $X$ (die ze verwisselt) uitgesloten van de buurset. Deze wijziging in één regel verkleint de zoekruimte drastisch en verbetert de mengtijden.
Niet-terugkeren: De auteurs integreren niet-terugkerende beperkingen in zowel de generatie van willekeurige wandelingen als de beam search om de variantie in de afstandsschattingen te verminderen en stagnatie in lokale minima te voorkomen.

Belangrijkste Bijdragen

Algoritmische Vooruitgang: Het artikel presenteert een nieuwe combinatie van diffusie-afstand voortraining en aangepast DQN. Deze aanpak overwint de beperkingen van standaard DQN (spare beloningen, ruisende doelen) en presteert beter dan klassieke methoden.
Prestatiebenchmarks: De voorgestelde methoden vinden succesvol paden voor LRX-Cayley-graaf tot $n \approx 44$ zonder voorafgaande kennis en tot $n \approx 100$ bij gebruik van de "X-truc". Dit overtreft aanzienlijk de mogelijkheden van GAP, dat beperkt is tot $n \approx 20$ . De AI-methoden produceren kortere paden en draaien sneller dan GAP voor vergelijkbare $n$ .
Wiskundige Resultaten en Vermoedens:
- Diametervermoeden: De auteurs ondersteunen sterk het OEIS-A186783-vermoeden dat de diameter van de LRX-Cayley-graaf $n(n-1)/2$ is. Ze verifieerden dit via brute-force BFS voor $n \le 15$ en via AI-ontbinding voor $n$ tot 200 (via Kaggle-uitdagingen), waarbij geen ontbinding korter dan de vermoede lengte werd gevonden.
- Langste Element: Ze identificeren een uniek "langste element" $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ en geven een expliciete ontbinding van lengte $n(n-1)/2$ .
- Grenzen: Het artikel bewijst een ondergrens voor de diameter van $n(n-1)/2 - n/2 - 1$ en een bovengrens van $n(n-1)/2 + 3n$ via een constructief algoritme. Een empirisch algoritme suggereert een strakkere bovengrens van $n(n-1)/2 + n/2$ .
- Groei-distributie: Numerieke experimenten suggereren dat de groeifunctie van de LRX-graaf voor grote $n$ een links-scheve Gumbel-distributie volgt, in tegenstelling tot de Gaussische distributie die wordt waargenomen bij graaf met buurtransposities.
- Mengtijd: Waar standaard willekeurige wandelingen mengtijden hebben tussen $O(n^3)$ en $O(n^3 \log n)$ , vermoeden de auteurs dat willekeurige wandelingen gemodificeerd met de "X-truc" sneller mengen, met een tijdscomplexiteit van $O(n^2)$ .
- Spectrum: Het spectrum van de LRX-graaf lijkt een uniforme distributie te volgen.
Open Source en Crowdsourcing: De auteurs hebben het project "CayleyPy" vrijgegeven en Kaggle-uitdagingen gecreëerd om oplossingen voor de ontbinding van het langste element en het vinden van optimale algoritmen in te zamelen via crowdsourcing, waardoor samenwerking tussen AI- en wiskundige gemeenschappen wordt gestimuleerd.

Resultaten

Efficiëntie: Voor $n=20$ heeft GAP meer dan 41 minuten nodig om een pad van lengte 217.944 te vinden, terwijl de diffusie-afstandsmethode het optimale pad van lengte 190 vindt in minder dan 4 minuten.
Schaalbaarheid: Met de "X-truc" lost het systeem instanties op voor $n=100$ (graafgrootte $\approx 10^{157}$ ) in ongeveer 8,5 uur op een enkele GPU, waarbij een pad van lengte 16.632 wordt gevonden (vergeleken met de vermoede diameter van 4.950).
Modelprestaties: Eenvoudige modellen zoals Multi-Layer Perceptrons (MLP) en Gradient Boosting (CatBoost/XGBoost) presteerden vaak beter dan complexe architecturen zoals Transformers en CNN's voor deze specifieke taak.
Beam Search: Het slagingspercentage om een pad te vinden is sterk afhankelijk van de beam-breedte, waarbij een superlineaire verbetering wordt getoond naarmate de beam-grootte toeneemt, analoog aan de "uitwisseling van ideeën" in een onderzoeksgemeenschap.

Betekenis
Het artikel beweert dat computationele experimenten, met name die gebruikmaken van AI, de wiskundige research op Cayley-graaf aanzienlijk kunnen bevorderen. Het toont aan dat AI-methoden klassieke computeralgebrasystemen kunnen "overtreffen" in zowel schaalbaarheid (het verwerken van veel grotere $n$ ) als oplossingskwaliteit (het vinden van kortere, bijna-optimale paden). Het werk overbrugt de kloof tussen theoretische groepentheorie en praktische AI, en biedt rigoureuze grenzen, nieuwe vermoedens over groei en mengtijden, en een kader voor het oplossen van padvindingsproblemen in uiterst grote toestandsruimtes die eerder onoplosbaar waren. De auteurs positioneren dit als een stap richting het toepassen van AI op andere complexe planningsproblemen in de theoretische wetenschap.