Het Minimax algoritme staat (bijna) letterlijk voor het
minimaliseren van het maximaal haalbare voor tegenpartijen tijdens een
spel.
Het Minimax-algoritme wordt gebruikt om tijdens een spel continu
de optimale zet te vinden. Oftewel: het algoritme gaat op zoek naar eigen winst en dwarsboomt
graag de tegenpartij.
Het Minimax-algoritme is gebaseerd op een drietal aannames:
1. Er zijn twee spelers.
2. Er wordt geen informatie achtergehouden.
3. Iedere zet is het directe gevolg van de zet ervoor (dus toeval speelt
geen rol).
In deze categorie spellen vallen onder andere boter-kaas-en-eieren, vier-
op-een-rij, schaken en het Oost-Aziatische Go. Steen-papier-schaar valt
bijvoorbeeld weer niet onder deze categorie, omdat er informatie wordt
achtergehouden. Monopoly of Backgammon ook niet, omdat bij deze
spellen kans een rol speelt.
Het Minimax-algoritme is alleen toepasbaar in combinatie
met de eerder genoemde aannames. Daarnaast kan de game tree ook
simpelweg te groot worden om te analyseren.
Bij schaken zijn er na iedere zet gemiddeld 35 reacties mogelijk. Om alle
mogelijke scenario’s te evalueren die zich kunnen voordoen binnen twee
zetten, moeten er 35 x 35 = 1225 scenario’s worden bestudeerd. Drie zetten
betekent 42.875 scenario’s, vier zetten 1.500.625, en zo verder.
In het spelletje Go zijn er na iedere zet gemiddeld 250 reacties mogelijk.
Ga dat maar eens uittekenen... Computers beperken zich daarom vaak
tot een beperkt gedeelte van een beslisboom om, met behulp van het
Minimax-algoritme, een strategische keuze te maken.
