Zoekboom: hoe computers de toekomst doorrekenen voordat ze een zet doen
Stel je voor dat je schaakt en voor elke zet die je overweegt, in gedachten alle mogelijke reacties van je tegenstander doorloopt, en daarna weer jouw beste antwoord daarop, en zo verder, tien zetten diep. Dat is precies wat een zoekboom is: een vertakkende structuur waarin een computer alle (of de meest kansrijke) mogelijke vervolgstappen vanuit een bepaalde situatie in kaart brengt, om te bepalen welke actie nu het beste is.
De naam komt van de vorm: helemaal bovenaan staat de huidige situatie, de 'wortel' van de boom. Daaronder vertakt elke mogelijke zet naar een nieuwe situatie, die op zijn beurt weer vertakt naar de zetten daarna. Zo ontstaat een structuur die qua vorm op een boom lijkt, maar dan omgekeerd getekend: de wortel bovenaan, de takken naar beneden. Zoekbomen zitten in vrijwel elk systeem dat vooruit moet plannen, van schaakcomputers tot navigatie-apps die de snelste route berekenen.
Wat is het precies?
Een zoekboom ontstaat door een probleem op te splitsen in toestanden en acties. Een toestand is een momentopname van de situatie, bijvoorbeeld een schaakbord op een gegeven moment, of de positie van een robot in een magazijn. Een actie is een mogelijke stap vanuit die toestand, zoals een schaakzet of een beweging naar links.
De computer begint bij de starttoestand en genereert alle acties die daaruit mogelijk zijn. Elke actie leidt tot een nieuwe toestand, die weer als apart 'knooppunt' in de boom wordt neergezet. Vanuit elk van die knooppunten worden opnieuw alle mogelijke acties bekeken, enzovoort. Bij een spel als schaken loopt dit binnen enkele zetten al op tot miljarden knooppunten, omdat het aantal mogelijkheden exponentieel groeit met elke stap dieper in de boom.
Om die explosie beheersbaar te maken, gebruiken onderzoekers verschillende strategieën. Breedte-eerst zoeken (breadth-first search) onderzoekt eerst alle knooppunten op één niveau voordat het dieper gaat, wat garandeert dat de kortste route wordt gevonden maar veel geheugen kost. Diepte-eerst zoeken (depth-first search) duikt juist meteen diep één pad in en gaat pas terug als dat pad doodloopt. Het populaire A*-algoritme, bedacht in 1968, combineert de afgelegde afstand met een schatting van de resterende afstand, waardoor het gericht naar het doel toe zoekt in plaats van blind alle richtingen te verkennen — dit is bijvoorbeeld de basis van veel route-planningssoftware.
Bij spellen met een tegenstander, zoals schaken of dammen, wordt vaak het minimax-algoritme gebruikt: de computer neemt aan dat de tegenstander altijd de voor hem beste zet kiest, en zoekt zelf naar de zet die dat 'slechtste geval' zo gunstig mogelijk maakt. Met alfa-bèta-snoeiing (alpha-beta pruning) kan de computer hele takken van de boom overslaan zodra duidelijk is dat ze toch nooit tot een betere uitkomst leiden, wat enorm veel rekentijd bespaart zonder dat de uitkomst verandert.
Voor spellen met te veel mogelijkheden om volledig door te rekenen, zoals Go, is er Monte Carlo Tree Search (MCTS), rond 2006 gepopulariseerd door onder anderen onderzoeker Rémi Coulom. In plaats van elke tak helemaal uit te rekenen, speelt de computer duizenden willekeurige of geschatte partijen vanaf een bepaald punt door tot het einde, en telt hij hoe vaak dat tot winst leidt. Takken die vaker winnen krijgen meer aandacht in vervolgrondes van de zoektocht, waardoor de boom zich als het ware richt op de meest veelbelovende paden zonder alles te hoeven doorrekenen.
Wat wil men ermee bereiken?
Het achterliggende doel van onderzoek naar zoekbomen is simpel te omschrijven maar lastig te realiseren: systemen bouwen die vooruit kunnen denken en de gevolgen van hun keuzes kunnen afwegen, net zoals mensen dat (deels) doen. Dat is nuttig in situaties waarin een verkeerde beslissing nu grote gevolgen heeft later, zoals bij het plannen van een robotarm-beweging, het routeren van pakketten in een logistiek netwerk, of het spelen van een strategisch spel.
Een belangrijke drijfveer is ook efficiëntie: een zoekboom die alles letterlijk uitprobeert is voor complexe problemen praktisch onbruikbaar, omdat het aantal mogelijkheden razendsnel oploopt. Onderzoekers proberen daarom slimmere manieren te vinden om te bepalen welke takken van de boom de moeite waard zijn om te onderzoeken, en welke veilig genegeerd kunnen worden. Dat is ook de reden dat zoekbomen tegenwoordig vaak gecombineerd worden met neurale netwerken: die netwerken schatten snel in welke zetten of acties kansrijk lijken, zodat de zoekboom zich kan concentreren op een kleine, veelbelovende selectie in plaats van alles te doorlopen.
Uiteindelijk is het doel breder dan spelletjes: dezelfde onderliggende technieken voor gestructureerd vooruitplannen worden gebruikt bij het plannen van bevoorradingsketens, het besturen van autonome voertuigen, en het ontwerpen van medicijnmoleculen, waarbij telkens een enorme ruimte aan mogelijke keuzes moet worden doorzocht op zoek naar een goede of optimale uitkomst.
Voorbeelden uit de praktijk
Deep Blue (1997) versloeg wereldkampioen schaken Garry Kasparov met een klassieke zoekboom op basis van minimax en alfa-bèta-snoeiing, aangevuld met speciale schaakhardware die de computer in staat stelde miljoenen posities per seconde te evalueren.
AlphaGo (2016), ontwikkeld door het Britse onderzoeksbedrijf DeepMind, versloeg Go-grootmeester Lee Sedol. Go heeft zo veel meer mogelijke zetten dan schaken dat een klassieke volledige zoekboom onhaalbaar is; AlphaGo combineerde daarom Monte Carlo Tree Search met neurale netwerken die posities beoordeelden en veelbelovende zetten voorstelden.
AlphaZero (2017), eveneens van DeepMind, ging een stap verder door dezelfde aanpak te generaliseren naar schaken, shogi (Japans schaken) en Go, zonder enige menselijke partij als voorbeeld te gebruiken. Het systeem leerde puur door tegen zichzelf te spelen en zijn eigen zoekboom en netwerk steeds te verbeteren.
MuZero (2019-2020), weer een DeepMind-project, ging nog verder: het systeem kreeg de spelregels niet eens te horen, maar leerde zelf een intern model van hoe het spel werkt, en gebruikte dat model om zijn eigen zoekboom te bouwen. Dit werkte niet alleen bij bordspellen, maar ook bij het spelen van Atari-videogames.
Buiten de spelwereld worden zoekbomen dagelijks gebruikt in routenavigatie (varianten van het A*-algoritme berekenen de snelste of kortste route in navigatiesoftware) en in robotplanning, waarbij bijvoorbeeld magazijnrobots een zoekboom gebruiken om een pad te vinden dat botsingen met andere robots vermijdt.
Hoe ver is de techniek?
Voor goed gedefinieerde spellen met vaste regels, zoals schaken, dammen en Go, is de techniek inmiddels volwassen: computers presteren daar structureel beter dan de beste menselijke spelers, en dat verschil wordt eerder groter dan kleiner. De combinatie van zoekbomen met neurale netwerken, zoals bij AlphaZero en MuZero, wordt gezien als een van de duidelijkste successen binnen de kunstmatige intelligentie van de afgelopen tien jaar.
Buiten strak afgebakende spellen wordt het lastiger. Zodra een probleem minder duidelijke regels heeft, de omgeving onvoorspelbaar is, of er te veel mogelijke acties tegelijk zijn (denk aan het besturen van een auto in het echte verkeer), wordt het bouwen van een bruikbare zoekboom aanzienlijk moeilijker. Onderzoekers werken aan manieren om zoekbomen te combineren met leren uit ervaring, zodat systemen niet alles vooraf hoeven te weten, maar dat blijft een actief en nog onopgelost onderzoeksgebied.
Een ander obstakel is rekenkracht: het trainen van systemen als AlphaZero vergde destijds gespecialiseerde hardware en aanzienlijke energiekosten, wat de toegankelijkheid van dit soort onderzoek beperkt tot grote techbedrijven en goed gefinancierde universiteiten. Ook blijft uitlegbaarheid een punt van aandacht: een zoekboom met miljoenen knooppunten, gecombineerd met een neuraal netwerk, is voor mensen niet meer op een intuïtieve manier te doorgronden, ook al is de uiteindelijke beslissing vaak wel goed.
Wie werken eraan?
DeepMind (onderdeel van Google/Alphabet, gevestigd in Londen) geldt als een van de meest toonaangevende partijen op dit gebied, met AlphaGo, AlphaZero en MuZero als bekendste resultaten. Ook OpenAI in de Verenigde Staten onderzoekt vormen van planning en zoeken in combinatie met leren, onder meer in de context van robotica en taalmodellen.
Op universitair niveau zijn onder meer de University of Alberta in Canada (bekend van baanbrekend werk aan pokerspelende AI en reinforcement learning) en Carnegie Mellon University in de Verenigde Staten belangrijke onderzoekscentra. In Europa dragen onder andere onderzoeksgroepen aan Franse en Duitse technische universiteiten bij aan verdere ontwikkeling van zoek- en planningsalgoritmen, vaak in samenwerking met de klassieke AI-leerstoelen die het vakgebied al decennialang vormgeven.
Daarnaast is er een lange traditie van academisch werk dat teruggaat tot de vroege dagen van de kunstmatige intelligentie, met grondleggers als Allen Newell en Herbert Simon, die al in de jaren vijftig en zestig experimenteerden met zoekbomen voor probleemoplossing, en met het latere standaardwerk van Stuart Russell en Peter Norvig dat generaties informatici heeft opgeleid in deze technieken.