Een veelgehoorde klacht in videogames is dat de kunstmatige intelligentie van tegenstanders slechte beslissingen neemt. Daarom spelen ze in sommige gevallen gewoon vals spelen, maar soms gebeurt het tegenovergestelde en laten ze zeer effectieve strategieën zien in spellen die we als 'simpel' kunnen beschouwen. Een van de redenen is de toepassing van de Minimax-stelling, een algoritme dat als doel heeft om het maximaal verwachte verlies te minimaliseren in tweepersoonsspellen met volledige informatie voor beide partijen.
Veel spellen verbergen informatie voor de deelnemers als onderdeel van hun mechanica. Denk bijvoorbeeld aan de 'fog of war' in klassieke spellen (StarCraft en Civilization komen in gedachten). Dat hulpmiddel stelt de kunstmatige intelligentie in staat om zomaar 20 of 30 eenheden tevoorschijn te toveren zonder dat je het doorhebt (onder andere), en het wegnemen ervan is een essentiële stap, of je nu eenheden op verkenning stuurt of technologieën ontwikkelt die het effect opheffen (zoals Satellieten in Civ).
Maar wat gebeurt er wanneer de informatie perfect is? Hoe gedraagt een kunstmatige intelligentie zich wanneer er niets te verbergen valt en alle elementen van het spel vanaf het begin bekend zijn? Een van de vele mogelijkheden voor de ontwikkelaar is de implementatie van de Minimax-stelling. De officiële beschrijving spreekt over een 'beslissingsmethode om het maximaal verwachte verlies te minimaliseren', en dat lijkt op het eerste gezicht eenvoudig, maar verdient een diepere verkenning:
Minimax-stelling: optimale oplossingen voor nulsomspellen
Het kanaal BitBoss doet uitstekend werk door het Minimax-algoritme samen te vatten, en het beste is dat het minder dan vier minuten duurt. Kort gezegd werkt Minimax in nulsomspellen, dat wil zeggen dat onze winst of voordeel verlies wordt voor de tegenstander. Schaken is een klassiek voorbeeld van een nulsomspel met perfecte informatie, maar de video neemt ons mee op een eenvoudiger pad, met boter-kaas-en-eieren als referentie.
Elke fase van het spel kan worden gedefinieerd met een getal, positief voor de ene speler en negatief voor de andere. De strategie van het Minimax-algoritme probeert de beste beschikbare zet te kiezen, ervan uitgaande dat de tegenstander ook de beste zet tegen je zal kiezen. Als een Minimax-KI de overwinning behaalt met een positief getal, zullen haar beslissingen proberen de route te volgen die dat getal begunstigt.
De grafiek toont de laatste zes mogelijke zetten van een kunstmatige intelligentie in een spelletje boter-kaas-en-eieren. Vier daarvan geven een overwinning voor de AI (geel) met een waarde van 1, en de andere twee voor de menselijke speler (blauw) met -1. De zetten worden van onder naar boven, of van achter naar voren geanalyseerd: omdat de kunstmatige intelligentie nog maar één zet te gaan heeft, gaan de waarden voor elke zet naar de vorige stap. Volgens dezelfde logica heeft de menselijke speler twee zetten die hem een -1 garanderen, en een derde die hem dwingt om 1 te kiezen. Daarom verzekert de AI zich van de overwinning door druk uit te oefenen op die route, die begint met een kruis in het midden.
Uiteraard is dit een te eenvoudig voorbeeld, en alleen mogelijk dankzij de natuurlijke beperkingen van boter-kaas-en-eieren. Als we de Minimax-methode verplaatsen naar zeer complexe spellen zoals schaken of go, het aantal te controleren toestanden groeit exponentieel, en wordt toepassing van Minimax onhaalbaar. Een mogelijke oplossing is het beperken van de zoekdiepte, en over het algemeen is dat meer dan genoeg om de n00bs een pak slaag te geven.
