Minimax je v teoriji iger metoda, katere cilj je zmanjšati pričakovano izgubo. Za to igralec predpostavlja, da bo odločitev nasprotnika neugodna. Se pravi, najslabši scenarij se pričakuje pred nasprotnikovim gibanjem.
Povedano drugače, metoda minimax je sestavljena iz tega, kako sprejeti najboljšo odločitev ob predpostavki, da bo drugi igralec izbral najslabši možni scenarij za vas.
Upoštevati moramo, da je ta metoda uporabna v igri za dve osebi (dva igralca) in da ni kooperativna, temveč igra z ničelno vsoto. To pomeni, da tisto, kar en igralec zmaga, izgubi drugi in obratno. Posledično bo vsakega agenta zanimalo, kako povečati svojo korist, četudi to drugega boli.
Na tem mestu se moramo tudi spomniti, da je teorija iger veja matematike in ekonomije, ki preučuje izbiro, ki optimizira položaj posameznika, ko stroški in koristi niso vnaprej določeni, ampak so odvisni od odločitev drugih.
Minimax algoritem v odločitvenem drevesu
Vidimo lahko, kako se metoda minimax uporablja v odločitvenem drevesu z več vozlišči. Igra se začne na dnu in konča z rezultatom na najvišji ravni.
Na dnu drevesa nasprotnik naredi prvi premik, zato se pričakuje najslabši rezultat. Nato je na drugi stopnji igralec x tisti, ki si bo prizadeval maksimirati svoj dobiček ob upoštevanju odločitve, ki jo je predhodno sprejel nasprotnik.
Na tretji stopnji je spet na vrsti nasprotnik in tako naprej. Spodaj bomo prikazali primer.
Primer algoritma Minimax
V naslednjem drevesu odločitev prikazujemo rezultate, ki jih je igralec x dosegel v vsakem trenutku igre. V osnovi, na prvi stopnji, nasprotnik sprejema odločitev. Iz tega razloga so podani scenariji, v katerih lahko igralec izgubi -10 ali zmaga 5.
Na drugi ravni je odvisno od igralca x, zato bo maksimiral svoj dobiček. Med izgubo 10 ali zmago 1 boste zmagali 1. Prav tako boste med zmago 5 ali 7 zmagali 7.
Nato je spet na vrsti nasprotnik, zato bodo podani scenariji, v katerih ima igralec x najslabši rezultat, -3 in 4, odvisno od primera. Nazadnje, med izgubo 3 ali zmago 4 bo igralec x sprejel odločitev, ki bo omogočila slednje.
Upoštevati moramo, da bodo vrednosti vsakega vozlišča odvisne od funkcije pripomočka.
Za boljše razumevanje drevesa predpostavimo, da je v osnovi odločitev o distribuciji izdelka. Tekmovalec (nasprotnik) lahko distribucijo odda zunanjim izvajalcem (glej levo stran drevesa). V tem primeru mora izbrati na primer med prodajalcem A in B. Tako izbere prvega, zaradi česar igralec x izgubi 10 (če bi izbral B, bi igralec x zmagal 12).
Morda pa nasprotnik svoje blago raje distribuira sam, saj lahko najame motorna vozila ali kupi tovornjak. Med obema scenarijema izberite prvega, ki je manj laskav za igralca x, ker zmaga 5 in ne 10.