Minimax je, u teoriji igara, metoda koja ima za cilj minimalizirati očekivani gubitak. Da bi to učinio, igrač pretpostavlja da će odluka koju je donio njegov protivnik biti nepovoljna. Odnosno, najgori scenarij očekuje se prije protivničkog kretanja.
Drugim riječima, metoda minimax sastoji se od toga kako donijeti najbolju odluku pretpostavljajući da će drugi igrač odabrati najgori scenarij za vas.
Moramo uzeti u obzir da je ova metoda primjenjiva u igri za dvije osobe (dva igrača) i da nije kooperativna, već igra s nultim zbrojem. To znači da ono što jedan igrač pobijedi drugi gubi i obrnuto. Slijedom toga, svaki će agent biti zainteresiran za maksimiziranje vlastite korisnosti, čak i ako to drugoga šteti.
U ovom se trenutku također moramo sjetiti da je teorija igara grana matematike i ekonomije koja proučava izbor koji optimizira situaciju pojedinca kada troškovi i koristi nisu unaprijed fiksni, već ovise o odlukama drugih.
Minimax algoritam u stablu odluka
Možemo vidjeti kako se metoda minimax primjenjuje u stablu odluka s nekoliko čvorova. Igra započinje na dnu, a završava rezultatom na najvišoj razini.
U podnožju stabla, protivnik čini prvi potez, pa se očekuje najgori rezultat. Zatim, na drugoj razini, na igraču x je koji će nastojati maksimizirati svoj profit, uzimajući u obzir odluku koju je protivnik prethodno donio.
Na trećoj razini opet je red na protivnika i tako dalje. U nastavku ćemo pokazati primjer.
Primjer algoritma Minimax
U sljedećem stablu odluka prikazujemo rezultate koje je igrač x postigao u svakom trenutku igre. U osnovi, na prvoj razini, protivnik donosi odluku. Iz tog razloga dati su scenariji u kojima igrač može izgubiti -10 ili pobijediti 5.
Na drugoj razini, ovisi o igraču x, tako da će maksimizirati svoju zaradu. Između 10 ili 1 dobitka dobit ćete 1. Isto tako, između 5 ili 7 dobit ćete 7.
Zatim, opet je red na protivnika, pa će se dati scenariji u kojima igrač x ima najlošiji rezultat, -3 i 4, ovisno o slučaju. Konačno, između gubitka 3 ili dobitka 4, igrač x će donijeti odluku koja će omogućiti potonje.
Moramo uzeti u obzir da će vrijednosti svakog čvora ovisiti o korisnoj funkciji.
Da bismo bolje razumjeli stablo, pretpostavimo da je u osnovi odluka o distribuciji proizvoda. Natjecatelj (protivnik) može prenijeti distribuciju (vidjeti lijevu stranu stabla). U tom slučaju mora odabrati, na primjer, između djelitelja A i B. Dakle, on odabire prvog, uzrokujući da igrač x izgubi 10 (ako je odabrao B, igrač x bi osvojio 12).
Međutim, možda protivnik radije sam distribuira svoju robu, budući da može unajmiti motorna vozila ili kupiti kamion. Od oba scenarija odaberite prvi koji je manje laskav za igrača x jer pobjeđuje 5, a ne 10.