Solvable Sokoban Without a Solver via Diffusion

Nel mondo dell'informatica, esiste una classe di problemi così complessi che controllare una soluzione può essere facile, ma trovarne una richiede di navigare in un labirinto di possibilità così vasto che richiederebbe più del tempo dell'età dell'universo per essere risolto tramite la forza bruta. Questi non sono meri enigmi difficili; sono problemi in cui il percorso verso la risposta non è solo lungo, ma esponenzialmente lungo, il che significa che ogni passo che si compie può aprire un universo di nuove possibilità e, contemporaneamente, chiuderne altre. Uno degli esempi più famosi di questo è un gioco chiamato Sokoban, giocato su una griglia dove un singolo personaggio deve spingere delle scatole su appositi quadrati bersaglio. Il problema è che il personaggio può solo spingere, mai tirare, e una volta che una scatola rimane incastrata in un angolo, spesso rimane bloccata per sempre. Poiché la posizione di una singola scatola può alterare completamente la raggiungibilità dell'intero tabellone, il gioco non può essere scomposto in piccoli compiti indipendenti. Risolverlo richiede un piano olistico che tenga conto di ogni interazione prima ancora di compiere una singola mossa. Per decenni, la capacità di generare nuovi puzzle validi di questo tipo è stata una sfida, perché creare un labirinto risolvibile è difficile quanto risolverlo, e controllare se un labirinto funzioni di solito richiede un computer potente per simulare ogni possibile mossa.

Uno studio recente ha scoperto un modo sorprendente per generare questi complessi puzzle senza mai insegnare al computer come risolverli. I ricercatori hanno addestrato un tipo di modello di intelligenza artificiale a riempire le parti mancanti di una griglia di Sokoban, molto come un essere umano che completa un cruciverba indovinando le parole mancanti basandosi sulle lettere circostanti. Il modello gli sono stati mostrati migliaia di veri puzzle e gli è stato chiesto di imparare i pattern di muri, pavimenti e scatole, ma non gli è mai stato detto quali puzzle fossero risolvibili, né gli è stato dato alcun premio per creare un gioco funzionante. Ha semplicemente imparato a prevedere quale tassello dovesse andare in un punto nascosto basandosi sui tasselli già visibili. Il risultato è stato sorprendente: quando il modello ha generato nuovi puzzle da zero, il 77,4 percento di essi era risolvibile. Questo è un risultato notevole perché il modello non era stato esplicitamente addestrato per garantire la risolvibilità; era stato solo addestrato a riempire i vuoti. I ricercatori hanno scoperto che la capacità di creare un puzzle risolvibile non era una competenza separata che il modello aveva appreso, ma un sottoprodotto naturale dell'apprendimento dei pattern locali del gioco.

Il successo di questo approccio dipende da come il modello pensa alla griglia. I programmi informatici tradizionali che generano sequenze, come quelli che scrivono testi, lavorano in un ordine fisso, decidendo la prima parola, poi la seconda, poi la terza. Questo approccio lineare fatica con Sokoban perché una decisione presa all'inizio della griglia può vincolare ciò che è possibile alla fine, creando un conflitto che il programma non può correggere in seguito. Il modello utilizzato in questo studio, tuttavia, non segue un ordine fisso. Inizia con una griglia completamente vuota dove ogni cella è nascosta e le rivela una per una in una sequenza casuale. Ad ogni passaggio, osserva l'intero tabellone così come si presenta in quel momento — muri qui, scatole lì e spazi vuoti altrove — e decide cosa appartiene al prossimo punto nascosto. Ciò gli permette di posizionare un muro in un angolo e un obiettivo nell'angolo opposto, e poi individuare il corridoio che li connette, adattando la sua comprensione dell'intero tabellone con ogni nuovo pezzo che rivela. Questa flessibilità rispecchia il modo in cui un giocatore umano deve pensare al gioco, dove la difficoltà deriva dalle interazioni non locali tra parti distanti del tabellone.

Per testare l'efficacia di questo metodo, i ricercatori hanno generato 50.000 nuovi puzzle e controllato ciascuno di essi con un risolutore standard. Hanno scoperto che quasi tre quarti dei puzzle erano immediatamente risolvibili. Ancora più significativo è stato ciò che è accaduto ai puzzle che non lo erano. Nel 94,5 percento dei casi irrisolvibili, il puzzle poteva essere sistemato semplicemente rimuovendo un singolo muro interno. Ciò suggerisce che il modello non stava solo indovinando casualmente; stava creando strutture che erano quasi interamente corrette, con solo lievi errori superficiali che impedivano la soluzione. I ricercatori hanno anche verificato che il modello non stesse semplicemente memorizzando i puzzle visti durante l'addestramento. Hanno confrontato i nuovi puzzle con il dataset originale e hanno scoperto che i puzzle generati erano altrettanto diversi dai dati di addestramento quanto lo erano i veri puzzle mai visti. Il modello aveva appreso la struttura sottostante del gioco, non solo un elenco di esempi specifici.

Lo studio ha anche esplorato come il comportamento del modello cambiasse quando i ricercatori regolavano la sua confidenza. Rendendo il modello più deciso nelle sue scelte, potevano aumentare il tasso di risolvibilità fino a quasi il 99 percento, sebbene ciò comportasse la creazione di puzzle con un numero di muri leggermente superiore al solito. L'impostazione predefinita, tuttavia, produceva puzzle che corrispondevano perfettamente alla densità di muri presente nel dataset di addestramento originale. Questo equilibrio tra struttura e casualità è fondamentale. Il modello ha imparato che, affinché un puzzle sia valido, i muri e le scatole devono incastrarsi in un modo molto specifico, e imparando a riempire correttamente i vuoti, ha involontariamente imparato le regole della risolvibilità. I ricercatori hanno notato che le prestazioni del modello sulla proprietà globale della risolvibilità continuavano a migliorare molto dopo che la sua capacità di prevedere i singoli tasselli aveva smesso di migliorare. Ciò indica che i due obiettivi sono distinti: un modello può essere bravo a riempire un singolo tassello senza essere bravo a creare un intero puzzle, ma in questo caso, padroneggiare i dettagli locali è stato sufficiente per sbloccare la soluzione globale.

Le implicazioni di questa scoperta vanno oltre la semplice creazione di migliori puzzle. Dimostra che proprietà globali complesse possono emergere da obiettivi di addestramento locali semplici. Il modello non è mai stato istruito affinché un puzzle debba essere risolvibile, eppure ha imparato a crearli comunque. Ciò suggerisce che la struttura stessa dei dati contiene la logica della soluzione, e che un modello capace di comprendere le relazioni tra tutte le parti di un sistema può ereditare la capacità di risolverlo. I ricercatori hanno confermato che il modello non stava usando un risolutore nascosto per guidare la sua generazione. Ogni fase del processo era guidata dalle predizioni del modello basate sulle parti visibili della griglia. Il fatto che il modello potesse generare un labirinto risolvibile senza mai vedere il percorso della soluzione è una testimonianza del potere di apprendere profondamente i pattern di un sistema per riprodurne le proprietà più difficili.

In definitiva, il lavoro dimostra che la barriera tra la generazione di un problema e la sua risoluzione non è così alta come si pensava. Addestrando un modello a completare semplicemente un pattern, i ricercatori hanno sbloccato la capacità di creare sfide valide e complesse. Il modello non aveva bisogno di essere un grande maestro del gioco per creare un gioco degno di essere giocato; doveva solo comprendere le regole dei tasselli. Questo approccio offre un nuovo modo di pensare all'intelligenza artificiale, suggerendo che se insegniamo a un sistema a comprendere le relazioni locali all'interno di un mondo complesso, esso potrebbe naturalmente imparare a navigare le sfide globali di quel mondo senza mai essere esplicitamente istruito per farlo. I puzzle generati non erano perfetti, ma erano abbastanza vicini da poter funzionare con un piccolo aggiustamento, provando che il modello aveva colto l'essenza del gioco.