Solvable Sokoban Without a Solver via Diffusion

In de wereld van de computerwetenschappen bestaat een klasse problemen die zo complex zijn dat het controleren van een oplossing eenvoudig kan zijn, maar het vinden ervan een doolhof van mogelijkheden vereist dat zo uitgestrekt is dat het langer zou duren dan het huidige universum om het door middel van brute kracht op te lossen. Dit zijn niet louter moeilijke puzzels; het zijn problemen waarbij het pad naar het antwoord niet alleen lang is, maar exponentieel lang, wat betekent dat elke stap die je zet een heel universum aan nieuwe mogelijkheden kan openen terwijl het tegelijkertijd anderen afsluit. Een van de bekendste voorbeelden hiervan is een spel genaamd Sokoban, gespeeld op een raster waar een enkel personage dozen naar specifieke doelvlakken moet duwen. Het nadeel is dat het personage alleen kan duwen, nooit kan trekken, en zodra een doos in een hoek klem komt te zitten, is deze vaak voor altijd vast. Omdat de positie van één doos de bereikbaarheid van het hele bord volledig kan veranderen, kan het spel niet worden opgedeeld in kleine, onafhankelijke taken. Het oplossen ervan vereist een holistisch plan dat rekening houdt met elke interactie voordat er ook maar één zet wordt gedaan. Decennialang was het vermogen om nieuwe, geldige puzzels van deze soort te genereren een uitdaging, omdat het creëren van een oplosbaar doolhof net zo moeilijk is als het oplossen ervan, en het controleren of een doolhof werkt meestal een krachtige computer vereist om elke mogelijke zet te simuleren.

Een recente studie heeft een verrassende manier gevonden om deze complexe puzzels te genereren zonder de computer ooit te leren hoe hij ze moet oplossen. Onderzoekers trainden een type kunstmatige intelligentie-model om ontbrekende stukken van een Sokoban-raster in te vullen, vergelijkbaar met hoe een mens een kruiswoordraadsel invult door de ontbrekende woorden te raden op basis van de omliggende letters. Het model werd getoond aan duizenden echte puzzels en gevraagd om de patronen van muren, vloeren en dozen te leren, maar het werd nooit verteld welke puzzels oplosbaar waren, noch kreeg het enige beloning voor het creëren van een werkend spel. Het leerde simpelweg te voorspellen welk tegelstuk in een verborgen plek moest komen op basis van de tegels die al zichtbaar waren. Het resultaat was verbazingwekkend: wanneer het model nieuwe puzzels vanaf nul genereerde, waren 77,4 procent van deze oplosbaar. Dit is een opmerkelijke uitkomst omdat het model nooit expliciet getraind werd om oplosbaarheid te garanderen; het werd alleen getraind om de gaten in te vullen. De onderzoekers ontdekten dat het vermogen om een oplosbare puzzel te creëren geen aparte vaardigheid was die het model leerde, maar een natuurlijk bijproduct van het leren van de lokale patronen van het spel.

Het succes van deze aanpak berust op de manier waarop het model over het raster denkt. Traditionele computerprogramma's die sequenties genereren, zoals die tekst schrijven, werken in een vaste volgorde, waarbij ze eerst het eerste woord beslissen, dan het tweede, dan het derde. Deze lineaire aanpak worstelt met Sokoban omdat een beslissing die aan het begin van het raster wordt genomen, wat mogelijk is aan het einde van het raster kan beperken, wat een conflict creëert dat het programma later niet kan herstellen. Het model dat in deze studie werd gebruikt, volgt echter geen vaste volgorde. Het begint met een volledig leeg raster waarbij elke cel verborgen is en onthult ze één voor één in een willekeurige volgorde. Bij elke stap kijkt het naar het hele bord zoals het er op dat moment bij staat — muren hier, dozen daar, en lege ruimtes elders — en beslist wat er in de volgende verborgen plek thuishoort. Dit stelt het model in staat om een muur in één hoek te plaatsen en een doel in de tegenoverliggende hoek, en vervolgens de gang te bedenken die hen verbindt, waarbij het zijn begrip van het hele bord aanpast met elk nieuw stuk dat het onthult. Deze flexibiliteit weerspiegelt de manier waarop een menselijke speler over het spel moet denken, waarbij de moeilijkheid voortkomt uit de niet-lokale interacties tussen verre delen van het bord.

Om te testen hoe goed deze methode werkte, genereerden de onderzoekers 50.000 nieuwe puzzels en controleerden elke puzzel met een standaard solver. Ze ontdekten dat bijna drie kwart van de puzzels direct oplosbaar was. Nog veelzeggender was wat er gebeurde met de puzzels die faalden. In 94,5 procent van de onoplosbare gevallen kon de puzzel eenvoudig worden gerepareerd door één enkele binnenmuur te verwijderen. Dit suggerek dat het model niet zomaar willekeurig gokte; het creëerde structuren die bijna volledig correct waren, waarbij slechts kleine, oppervlakkige fouten een oplossing verhinderden. De onderzoekers controleerden ook of het model de puzzels die het tijdens de training had gezien niet simpelweg uit het hoofd leerde. Ze vergeleken de nieuwe puzzels met de oorspronkelijke dataset en ontdekten dat de gegenereerde puzzels net zo verschillend waren van de trainingsdata als echte, ongeziene puzzels. Het model had de onderliggende structuur van het spel geleerd, en niet slechts een lijst met specifieke voorbeelden.

De studie onderzocht ook hoe het gedrag van het model veranderde wanneer de onderzoekers de mate van zelfverzekerdheid aanpasten. Door het model besluitzamer te maken in zijn keuzes, konden ze de oplosbaarheid verhogen tot bijna 99 procent, hoewel dit ten koste ging van het creëren van puzzels met iets meer muren dan gebruikelijk. De standaardinstelling produceerde echter puzzels die de dichtheid van muren uit de oorspronkelijke trainingsset perfect maten. Deze balans tussen structuur en willekeur is essentieel. Het model leerde dat voor een geldige puzzel de muren en dozen op een zeer specifieke manier bij elkaar moeten passen, en door te leren de gaten correct in te vullen, leerde het onbedoeld de regels van oplosbaarheid. De onderzoekers merkten op dat de prestaties van het model op de globale eigenschap van oplosbaarheid bleven verbeteren, lang nadat het vermogen om individuele tegels te voorspellen was gestopt met verbeteren. Dit geeft aan dat de twee doelen verschillend zijn: een model kan goed zijn in het invullen van een enkele tegel zonder goed te zijn in het creëren van een hele puzzel, maar in dit geval was het beheersen van de lokale details genoeg om de globale oplossing te ontsluiten.

De implicaties van deze bevinding strekken zich uit voorbij het maken van betere puzzels. Het demonstreert dat complexe, globale eigenschappen kunnen voortkomen uit eenvoudige, lokale trainingsdoelen. Het model werd nooit verteld dat een puzzel oplosbaar moet zijn, maar toch leerde het ze te creëren. Dit suggereert dat de structuur van de data zelf de logica van de oplossing bevat, en dat een model dat in staat is om de relaties tussen alle delen van een systeem te begrijpen, het vermogen kan erven om het te oplossen. De onderzoekers bevestigden dat het model geen verborgen solver gebruikte om de generatie te sturen. Elke stap in het proces werd gedreven door de eigen voorspellingen van het model op basis van de zichtbare delen van het raster. Het feit dat het model in staat was om een oplosbaar doolhof te genereren zonder ooit het oplossingspad te hebben gezien, is een getuigenis van de kracht van het diepgaand leren van de patronen van een systeem om diens meest moeilijke eigenschappen te reproduceren.

Uiteindelijk laat het werk zien dat de barrière tussen het genereren van een probleem en het oplossen ervan niet zo hoog is als voorheen gedacht. Door een model te trainen om simpelweg een patroon te voltooien, ontsloten de onderzoekers het vermogen om geldige, complexe uitdagingen te creëren. Het model hoefde geen grootmeester van het spel te zijn om een spel waardevol te maken om te spelen; het hoefde alleen de regels van de tegels te begrijpen. Deze aanpak biedt een nieuwe manier om over kunstmatige intelligentie na te denken, en suggereert dat als we een systeem leren de lokale relaties binnen een complexe wereld te begrijpen, het vanzelf kan leren om de globale uitdagingen van die wereld te navigeren zonder dat het daar expliciet voor getraind is. De gegenereerde puzzels waren niet perfect, maar ze waren goed genoeg zodat een kleine aanpassing ze werkend kon maken, wat bewees dat het model de essentie van het spel had gegrepen.