Il gioco perfetto di «Snake»: algoritmi per dominare il classico

Pochi youtuber spiegano gli algoritmi e l'intelligenza artificiale come Code Bullet. I suoi video hanno tutto: successi, fallimenti, insulti, crisi emotive e sfide semplici che diventano gigantesche. Il suo video più recente è la continuazione del progetto pubblicato mesi fa, in cui ha lottato per far imparare a un'intelligenza artificiale a giocare a Snake tramite Q-learning. Questa volta torna all'attacco cercando rivincita, e anche se la "perfezione" nei video di Code Bullet va presa con le pinze, il risultato finale è molto superiore al precedente.

Non è la prima volta che parliamo di intelligenze artificiali addestrate per dominare giochi. Il Deep-Q di Google si è addestrato con titoli Atari 2600, e in particolare con incubi al livello del Montezuma's Revenge. Facebook ha già partecipato con i suoi bot in tornei di StarCraft, e OpenAI ha ottenuto vittorie di alto profilo in DotA 2.

Il legame tra videogiochi e intelligenze artificiali diventerà sempre più forte, ma indipendentemente dalla qualità delle partite, non è una cattiva idea imparare qualcosa sul processo in sottofondo. Prendiamo il caso di Snake. Un gioco più che semplice per un umano, ma cosa servirebbe a un'intelligenza artificiale per conquistarlo completamente?

La nuova sfida di Code Bullet

Code Bullet su YouTube ha deciso di rispondere a questa domanda... e credo che sia un po' pentito. Dopo aver sofferto con il Q-learning nel suo primo video a metà luglio, è tornato alla carica buttando tutto il lavoro precedente nella spazzatura e ricominciando da zero. Snake ha quattro comandi di base: su, giù, sinistra e destra. C'è un muro sul perimetro della mappa, ma il corpo stesso del serpente agisce come muro interno, con la difficoltà aggiuntiva che si muove. Calcolando il numero di percorsi, il numero approssimativo è di 295 trilioni di possibilità... quindi serve qualcosa di diverso.

La prima idea è stata dare priorità ai percorsi che permettono al serpente di avvicinarsi al cibo invece di allontanarsi con l'aiuto dell'algoritmo A*, uno dei più popolari nel pathfinding... ma non ha funzionato. Quando rimaneva intrappolato, il serpente semplicemente smetteva di muoversi. La soluzione è stata mettere A* a testa in giù: invece di cercare il percorso più corto, il serpente prende il più lungo, che in un certo senso è ciò che tutti i giocatori di Snake dovrebbero fare quando il serpente diventa molto grande. A questo ha aggiunto un'altra condizione: il serpente deve sempre essere in grado di accedere all'80% dei blocchi vuoti...

... e quasi ci è riuscito. Un altro riavvio, e così è arrivato al cosiddetto «ciclo di Hamilton», che interpreta la mappa di Snake come un circuito pieno di nodi da visitare una sola volta e tornare all'inizio. Tutto ciò che il nuovo algoritmo dovrebbe fare è generare cicli di Hamilton e seguire ciascuno alla lettera... ma questo è noioso per Code Bullet, quindi ha fatto una piccola modifica affinché il serpente prenda scorciatoie occasionali. Risultati? Il primo è stato un successo, con una partita perfetta di Snake. Il secondo è finito in fallimento per appena due blocchi... anche se la mappa era enorme.