Minimax voor beginners: hoe onze AI denkt

Wil je begrijpen waarom onze “Onverslaanbaar”-AI nooit verliest? Het zit verstopt in zeventig regels code, gebaseerd op een algoritme uit 1928. Hier is minimax — uitgelegd zonder wiskunde, met boter kaas en eieren als voorbeeld. Voor wie ooit een AI wil bouwen, of gewoon nieuwsgierig is.

Het probleem dat minimax oplost

Stel je een computer is. Je krijgt een 3×3-bord met al een paar X’en en O’en. Het is jouw beurt (jij bent X). Welke zet doe je?

De naïeve aanpak: probeer alle mogelijke zetten en kies degene die direct wint. Werkt soms — als er een directe winst voor het grijpen ligt. Maar in de meeste situaties is er geen directe winst, en moet je vooruitkijken. Twee zetten vooruit. Drie zetten. Vijf. Op een gegeven moment loopt het potje af, en pas dan weet je wat de uitkomst was.

Minimax is een systematische manier om die “tot het einde doorkijken” te doen.

Het idee in één zin

Stel dat ik maximaal speel (probeer te winnen) en mijn tegenstander minimaal speelt voor mij (probeert mij te laten verliezen). Dan kies ik bij elke zet de optie die — als beide partijen verder optimaal spelen — leidt tot mijn beste mogelijke uitkomst.

Vandaar de naam: mini (tegenstander minimaliseert mijn score) max (ik maximaliseer mijn score).

Een uitgewerkt voorbeeld

Stel: er zijn nog drie lege vakjes over, ik ben aan zet. Ik bouw mentaal een boom van mogelijke zetten:

Mijn zet A → tegenstander zet B1 → ik zet C1 → REMISE
Mijn zet A → tegenstander zet B2 → ik zet C2 → WINST (voor mij)

Mijn zet B → tegenstander zet A1 → ik zet C → VERLIES
Mijn zet B → tegenstander zet C1 → ik zet A → REMISE

Mijn zet C → tegenstander zet A1 → ik zet B → WINST (voor mij)
Mijn zet C → tegenstander zet B1 → ik zet A → REMISE

Stap 1: bepaal per pad de uitkomst. Winst voor mij = +10, remise = 0, verlies = -10.

Stap 2: per tegenstander-zet, kiest de tegenstander de slechtste uitkomst voor mij (de minimum).

• Na zet A: tegenstander kiest tussen “remise” en “winst voor mij” → kiest remise (0).
• Na zet B: tegenstander kiest tussen “verlies” en “remise” → kiest verlies voor mij (-10).
• Na zet C: tegenstander kiest tussen “winst voor mij” en “remise” → kiest remise (0).

Stap 3: ik kies de zet met de hoogste minimax-score.

• Zet A: 0 (remise)
• Zet B: -10 (verlies)
• Zet C: 0 (remise)

A of C zijn beide goede zetten (remise). B vermijd ik (verlies). Minimax heeft de optimale zet gevonden.

De pseudo-code

function minimax(bord, mijnBeurt) {
    als bord gewonnen door mij: return +10
    als bord gewonnen door tegenstander: return -10
    als bord vol (remise): return 0

    als mijnBeurt:
        besteScore = -oneindig
        voor elk leeg vakje:
            plaats mijn teken
            score = minimax(bord, false)
            verwijder mijn teken
            besteScore = max(besteScore, score)
        return besteScore
    anders:
        besteScore = +oneindig
        voor elk leeg vakje:
            plaats tegenstander-teken
            score = minimax(bord, true)
            verwijder tegenstander-teken
            besteScore = min(besteScore, score)
        return besteScore
}

Recursief. Twintig regels. Dit is letterlijk hoe onze AI denkt.

Waarom het werkt voor 3×3

De zoekruimte is klein. Vanuit een leeg bord zijn er ~250.000 unieke partijen. Vanuit een halfvol bord zijn er nog veel minder. Een moderne smartphone berekent dit binnen één milliseconde. Voor 3×3 boter kaas en eieren is minimax perfect én snel.

Waarom het niet werkt voor schaak

Schaak heeft naar schatting 10^40 mogelijke partijen. Een complete minimax zou langer duren dan het bestaan van het heelal. Voor schaak gebruik je daarom heuristieken — vuistregels die zonder volledig door te rekenen een “goede genoeg” zet kiezen. Daarom verliest Magnus Carlsen soms nog steeds van een schaakcomputer, maar niet altijd.

Alpha-beta pruning: 100x sneller

De basis-minimax is werkbaar, maar je kunt ‘m slimmer maken. Tijdens het doorrekenen kom je vaak situaties tegen waarvan je weet: “deze tak kan nooit beter zijn dan een tak die ik al gevonden heb.” Sla die over. Dat heet alpha-beta pruning, en het maakt minimax tussen tien en honderd keer sneller.

Onze “Onverslaanbaar”-AI gebruikt alpha-beta. Het is een paar regels extra code maar maakt het verschil tussen “merkbaar even denken” en “instant”.

Bouw je eigen versie

Wil je dit zelf implementeren? Onze game-engine staat open source op de site — alle zeventig regels Javascript zijn leesbaar in /wp-content/plugins/boterkaaseieren-game/assets/game-engine.js. Voor wie Python of een andere taal gebruikt: het concept vertaalt direct. De moeilijkheid zit niet in de code maar in het bord representeren als data — voor 3×3 werkt een simpel array van 9 elementen.

Een leuke programmeer-uitdaging voor jezelf of voor een groep 8-leerling: bouw een Python-script dat minimax doet voor tic-tac-toe. Drie avonden werk, en je hebt iets gebouwd dat fundamenteel hetzelfde is als wat ChatGPT in de kern doet — namelijk: vooruitkijken naar de beste optie. AlphaGo, Stockfish, Watson — ze zijn allemaal varianten op dit idee, gecombineerd met enorm veel rekenkracht en slimme heuristieken.

Voor wie wil doorlezen

• Artificial Intelligence: A Modern Approach van Russell & Norvig — hoofdstuk 5 behandelt minimax
• De originele paper van John von Neumann (1928) — wiskundig zwaar maar historisch interessant
• Onze AI-modus — speel tegen het algoritme om te voelen wat het kan