De minimax is in de speltheorie een methode die tot doel heeft het verwachte verlies te minimaliseren. Om dit te doen, gaat de speler ervan uit dat de beslissing van zijn tegenstander ongunstig zal zijn. Dat wil zeggen, het slechtste scenario wordt verwacht vóór de beweging van de tegenstander.
Anders gezegd, de minimax-methode bestaat uit hoe je de beste beslissing kunt nemen, ervan uitgaande dat de andere speler het worstcasescenario voor jou kiest.
We moeten er rekening mee houden dat deze methode toepasbaar is in een tweepersoonsspel (twee spelers) en dat het geen coöperatief, maar een nulsomspel is. Dit betekent dat wat de ene speler wint, de andere verliest en vice versa. Bijgevolg zal elke agent geïnteresseerd zijn in het maximaliseren van zijn eigen nut, zelfs als dat de ander schaadt.
Op dit punt moeten we ook bedenken dat speltheorie een tak van wiskunde en economie is die de keuze bestudeert die de situatie van een individu optimaliseert wanneer kosten en baten niet van tevoren zijn vastgesteld, maar afhankelijk zijn van de beslissingen van anderen.
Minimax-algoritme in een beslisboom
We kunnen zien hoe de minimax-methode wordt toegepast in een beslisboom met meerdere knooppunten. Het spel begint onderaan en eindigt met een resultaat op het hoogste niveau.
Aan de voet van de boom doet de tegenstander de eerste zet, dus het slechtste resultaat wordt verwacht. Vervolgens, in het tweede niveau, is het aan speler x die zal proberen zijn winst te maximaliseren, rekening houdend met de beslissing die eerder door de tegenstander is genomen.
Op het derde niveau is het weer de beurt van de tegenstander, enzovoort. We zullen hieronder een voorbeeld laten zien.
Voorbeeld van Minimax-algoritme
In de volgende beslisboom laten we de resultaten zien die speler x op elk moment van het spel heeft behaald. Aan de basis, op het eerste niveau, neemt de tegenstander de beslissing. Om die reden worden de scenario's gegeven waarin de speler -10 kan verliezen of 5 kan winnen.
Op het tweede niveau is het aan speler x, dus hij zal zijn winst maximaliseren. Tussen 10 verliezen of 1 winnen, win je 1. Evenzo, tussen 5 of 7 winnen, win je 7.
Daarna is de tegenstander weer aan de beurt, dus de scenario's worden gegeven waarin speler x het slechtste resultaat heeft, -3 en 4, afhankelijk van het geval. Ten slotte, tussen 3 verliezen of 4 winnen, zal speler x de beslissing nemen die de laatste toelaat.
We moeten er rekening mee houden dat de waarden van elk knooppunt afhankelijk zijn van een hulpprogramma-functie.
Om de boom beter te begrijpen, veronderstel dat aan de basis de beslissing gaat over de distributie van het product. De concurrent (de tegenstander) kan de distributie uitbesteden (zie de linkerkant van de boom). In dat geval moet hij bijvoorbeeld kiezen tussen dealer A en B. Hij kiest dus de eerste, waardoor speler x 10 verliest (als hij B kiest, wint speler x 12).
Maar misschien geeft de tegenstander er de voorkeur aan zijn koopwaar zelf te distribueren, waarbij hij gemotoriseerde voertuigen kan huren of een vrachtwagen kan kopen. Kies van beide scenario's de eerste die minder flatterend is voor speler x omdat hij 5 wint en niet 10.