Minimax

Zie Minimax (doorverwijspagina) voor andere betekenissen van Minimax.

Minimax (minimum maximorum) is het minimaliseren van het maximaal haalbare voor tegenpartijen bij een competitie. Het wordt in verschillende gebieden toegepast, zoals bij verkiezingen (methode Condorcet) en bij zoekbomen in spelen. Maximin (maximum minimorum) is het maximaliseren van het minimaal haalbare en heeft overeenkomsten met het verschilbeginsel uit A Theory of Justice van John Rawls. Minimin (minimum minimorum) is het minimaliseren van het minimaal haalbare en maximax (maximum maximorum) is het maximaliseren van het maximaal haalbare.

Het laatste gebied komt onder meer voor bij schaakprogramma's. Het programma maakt in dat geval een zoekboom van alle mogelijke zetten, de zetten die de tegenstander daarop weer kan doen en de volgende zetten van het programma zelf. Wanneer aan alle resultaten een score wordt toegekend, kan de beste zet bepaald worden. Hierbij is een hoge score een voor het programma goed resultaat. De beste zet wordt dan vervolgens bepaald door in iedere vertakking van de boom de maximale score voor een eigen zet te verkiezen en de minimale score voor een zet van de opponent. Zodoende wordt de beste zet verkregen.

Voorbeeld

In het voorbeeld van het spel dat hiernaast is afgebeeld, stelt het bovenste plaatje het speelbord voor. Het spel begint door een muntstuk op het bovenste cirkeltje te leggen. De spelers zetten om beurt: Alice schuift de munt langs een rood lijntje en daarna schuift Bob de munt langs een groen lijntje. Uiteindelijk komt de munt in een cirkeltje waarin een cijfer staat en dat is het bedrag dat Alice aan Bob moet betalen.

Kenmerken van het spel zijn onder andere:

• Er zijn geen kringlopen, het is niet mogelijk dat het spel in een toestand komt die al eerder is voorgekomen en het spel moet dan ook een keer eindigen.
  • Dat geldt ook bij schaken, want daar zijn spelregels toegevoegd om herhaling van zetten te voorkomen.
• Beide spelers hebben perfecte en complete informatie over de situatie.
  • Dit geldt niet voor een kaartspel, waarbij de spelers meestal niet weten hoe de kaarten verdeeld zijn.
• Het spelverloop wordt niet door toeval bepaald.
  • Er is geen dobbelsteen, er worden geen kaarten geschud.

Bob zal dus proberen een hoge score te krijgen en Alice streeft naar een lage score. Wat is nu de juiste speelwijze?

Ligt de munt in het blauwe cirkeltje, dan is Bob aan zet. Hij kan kiezen tussen 3, 8 en 6 en kiest de hoogste waarde, dus 8. Het blauwe cirkeltje heeft dus de waarde 8. Op dezelfde manier kunnen ook de andere cirkeltjes op dat niveau een waarde krijgen en zo ontstaat het tweede plaatje.

Ligt de munt in het roze cirkeltje, dan is Alice aan zet. Zij kan kiezen tussen 8 en 6 en kiest de laagste waarde, dus 6. Het roze cirkeltje heeft dus de waarde 6.

Door de boom verder terug te rekenen ontstaat het derde plaatje. Het bovenste cirkeltje toont hoe het spel moet eindigen als Alice en Bob zo goed mogelijk spelen.

Toepassing

Theoretisch is het mogelijk elk spel dat aan bovenstaande voorwaarden voldoet, volledig door te rekenen. Zo zou van elke stelling in het schaakspel bekend zijn wat de juiste zet is en hoe het spel zal eindigen.

Een belangrijke stelling in de speltheorie, de stelling van Zermelo, zegt dat niet-stochastische spellen met twee spelers, waar er sprake is van perfecte informatie oplosbaar zijn. Dat wil zeggen dat in zulk soort spellen of een van de spelers een winnende strategie heeft, of beiden een gelijkspel kunnen garanderen.

De praktijk is minder eenvoudig: het schaakspel heeft daarvoor te veel mogelijkheden en de snelste computers zouden er vele miljarden jaren voor nodig hebben. Daardoor blijft het schaakspel interessant en verrassend. Bij eenvoudigere spellen als boter-kaas-en-eieren en het hierboven gegeven spel tussen Alice en Bob, is dit wel mogelijk.

In de notatie van bordspellen worden vaak een vraagteken en een uitroepteken gebruikt om respectievelijk slechte en sterke zetten te markeren. Het is duidelijk wat een sterke zet is: heeft een speler zetten tot zijn beschikking die tot winst leiden, dan moet een van die zetten uitgevoerd worden. Dit is dan een sterke zet, elke andere zet is een slechte zet en wordt in de notatie van een vraagteken voorzien.

De conclusie is eigenlijk ook dat echt sterke zetten niet bestaan. Een sterkere zet dan de juiste zet bestaat niet. Toch wordt er vaak een uitroepteken toegevoegd aan een zet en de bedoeling is dan eerder dat het een zet is die groot inzicht in het spel vereist om te maken.

Verschilbeginsel

Het verschilbeginsel uit A Theory of Justice van John Rawls heeft grote overeenkomsten met het maximin-criterium, maar Rawls vermeed deze term, aangezien het maximin-criterium van toepassing is bij besluitvorming onder grote onzekerheid, terwijl het verschilbeginsel rechtvaardigheid heeft als uitgangspunt.