Het perfecte spel van Snake: algoritmes om de klassieker te domineren

Bijna geen YouTuber legt algoritmes en kunstmatige intelligentie uit zoals Code Bullet. Zijn video's hebben alles: successen, mislukkingen, beledigingen, emotionele crises en eenvoudige uitdagingen die gigantisch worden. Zijn nieuwste video is een vervolg op het project dat hij maanden geleden publiceerde, waarin hij vocht om een kunstmatige intelligentie Snake te leren spelen via Q-learning. Deze keer komt hij terug voor revanche, en hoewel 'perfectie' in de video's van Code Bullet met een korreltje zout moet worden genomen, is het eindresultaat veel beter dan het vorige.

Het is niet de eerste keer dat we praten over kunstmatige intelligenties die zijn getraind om spellen te beheersen. Googles Deep-Q is getraind met titels van Atari 2600, en in het bijzonder met nachtmerries op het niveau van Montezuma's Revenge. Facebook deed al mee met zijn bots in toernooien van StarCraft, en OpenAI behaalde spraakmakende overwinningen in DotA 2.

De band tussen videogames en kunstmatige intelligenties zal alleen maar sterker worden, maar ongeacht de kwaliteit van de wedstrijden is het geen slecht idee om iets te leren over het proces op de achtergrond. Neem het geval van Snake. Een spel dat eenvoudiger is als een mens het speelt, maar wat zou een kunstmatige intelligentie nodig hebben om het volledig te veroveren?

De zoektocht naar de perfecte Snake

Code Bullet op YouTube besloot die vraag te beantwoorden... en ik denk dat hij er een beetje spijt van heeft. Na te hebben geleden met Q-learning in zijn eerste video half juli, kwam hij terug en gooide al zijn eerdere werk weg om opnieuw te beginnen. Snake heeft vier basiscommando's: omhoog, omlaag, links en rechts. Er is een muur rondom het speelveld, maar het eigen lichaam van de slang fungeert als interne muur, met de extra moeilijkheid dat het beweegt. Bij het berekenen van het aantal paden is het geschatte aantal 295 biljoen mogelijkheden... dus hij heeft iets anders nodig.

… en bijna was het gelukt. Nog een herstart, en zo kwam hij bij de zogenaamde 'Hamilton-cyclus', die het Snake-speelveld interpreteert als een circuit vol knooppunten die hij slechts één keer moet bezoeken en vervolgens terugkeren naar het begin. Alles wat het nieuwe algoritme zou moeten doen is Hamilton-cycli genereren en elke cyclus letterlijk volgen... maar dat is saai voor Code Bullet, dus maakte hij een kleine aanpassing zodat de slang af en toe een shortcut neemt. Resultaten? De eerste was een succes, met een perfect spel Snake. De tweede eindigde in een mislukking met slechts twee blokken... hoewel het veld enorm was.