Minimax är en beslutsregel som används inom artificiell intelligens, beslutsteori, spelteori, statistik och filosofi för att minimera den största möjliga förlusten i ett värstafall. Vid val mellan strategier väljs den strategi vars sämsta möjliga utfall är bättre än de andra strategiernas sämsta utfall. I situationer där fokus i stället ligger på vinst används ofta den närbesläktade principen maximin.

Begreppet är särskilt viktigt i analysen av nollsummespel, där en spelares vinst motsvarar den andras förlust. I sådana spel hänger minimax nära samman med Nashjämvikt, och för ändliga tvåpersoners-nollsummespel ger minimaxteoremet att det finns optimala blandade strategier för båda spelarna.

Spelteori Inom spelteori används minimax för att analysera strategiska situationer där en aktör vill skydda sig mot det sämsta möjliga utfallet. För en spelare innebär minimaxvärdet den minsta nytta som motspelarna kan tvinga fram, givet att de försöker motverka spelarens intressen.

Nollsummespel I tvåpersoners-nollsummespel sammanfaller minimaxlösningen med spelets värde enligt minimaxteoremet. Satsen, formulerad av John von Neumann, säger att varje ändligt nollsummespel med två spelare har ett värde och att båda spelarna har optimala strategier som garanterar detta värde.

Algoritm Inom artificiell intelligens syftar minimaxalgoritmen vanligen på en rekursiv sökalgoritm för spel med två motståndare, där den ena spelaren försöker maximera värdet av en position och den andra försöker minimera det. Algoritmen används bland annat i program för schack och liknande spel för att välja det drag som ger bäst resultat under antagandet att motståndaren spelar optimalt.

I praktiska tillämpningar begränsas sökdjupet ofta, och ställningar som inte är slutpositioner värderas med en heuristisk evalueringsfunktion. Algoritmens effektivitet kan förbättras avsevärt genom alfa-betabeskärning, som undviker att söka igenom delar av spelträdet som ändå inte kan påverka det slutliga valet av drag.

Pseudokod funktion minimax(nod, djup, maximerandeSpelare) om djup = 0 eller nod är en slutnod returnera heuristiskt värde för nod

om maximerandeSpelare värde := −∞ för varje barn till nod värde := max(värde, minimax(barn, djup − 1, falskt)) returnera värde annars värde := +∞ för varje barn till nod värde := min(värde, minimax(barn, djup − 1, sant)) returnera värde

Beslutsteori Inom beslutsteori används minimax som en regel för beslutsfattande under osäkerhet när sannolikheter för olika utfall inte är kända eller inte anses tillförlitliga. Beslutsfattaren väljer då det alternativ som minimerar den största möjliga förlusten. Ett närliggande begrepp är minimaxånger, där man i stället minimerar den största möjliga ångern av ett beslut.

Filosofi Inom politisk filosofi förknippas maximin ofta med John Rawls och hans rättviseteori. I A Theory of Justice använder Rawls maximinresonemang som en del av diskussionen om hur sociala och ekonomiska ojämlikheter bör ordnas så att de gynnar de minst gynnade i samhället.

Se även Alfa-betabeskärning Artificiell intelligens Beslutsteori Minimax-teorem Nashjämvikt Nollsummespel Spelteori

Referenser

Kategori:Algoritmer Kategori:Artificiell intelligens Kategori:Beslutsteori Kategori:Spelteori