Minimax
Uit Wikipedia, de vrije encyclopedie
Minimax staat voor het minimaliseren van het maximale. Het wordt in verschillende gebieden toegepast, zoals bij verkiezingen (Condorcet methode), en bij zoekbomen in spelen.
Het laatste gebied komt men bijvoorbeeld tegen bij schaakprogramma's. Het programma maakt in dat geval een (zoek)boom van alle mogelijke zetten, de zetten die de opponent daarop weer kan doen, de volgende zetten van het programma zelf, et cetera. Wanneer we aan alle resultaten een score toekennen kan de beste zet bepaald worden. Hierbij is een hoge score een voor het programma goed resultaat. Het bepalen van de beste zet doet men dan vervolgens 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 verkrijgt men de beste zet.
[bewerk] Voorbeeld
Wij dienen hier een zet te doen, en vervolgens doet de opponent een zet. Er zien vier eindresultaten: 8, 2, 4 en 3. Acht zou normaliter de beste uitkomst zijn voor het programma. Maar we dienen ook rekening te houden met een opponent die ons resultaat probeert te minimaliseren (om zo zelf een goed resultaat te behalen). Volgens de minimax zou de linkerzet ons maximaal een score van 2 opleveren, omdat de opponent vervolgens voor zijn/haar rechterzet zou kiezen. Kiezen wij de rechterzet, dan kan de opponent onze score hooguit verkleinen tot 3. Hierom zal het programma de rechteroptie kiezen en een eindresultaat van drie behalen. Het hoogst haalbare bij optimale zetkeuze van beide spelers.
De minimaxkeuze is te beredeneren door van onderaf te redeneren. Bij een opponent-regel minimaliseren we. Hierdoor verkrijgen we in de middelste regel de tussenresultaten 2 en 3. Bij een eigen regel maximaliseren we het resultaat. Wanneer we 2 en 3 maximaliseren komen we uit op 3. Vandaar de keuze voor de rechterzet.
