• Mini-max algoritem je rekurziven ali povratni algoritem, ki se uporablja pri odločanju in teoriji iger. Zagotavlja optimalno potezo za igralca ob predpostavki, da tudi nasprotnik igra optimalno.
• Algoritem Mini-Max uporablja rekurzijo za iskanje po drevesu iger.
• Algoritem Min-Max se večinoma uporablja za igranje iger v AI. Kot so šah, dama, tic-tac-toe, go in različne igre za vlečenje. Ta algoritem izračuna minimalno odločitev za trenutno stanje.
• V tem algoritmu igrata dva igralca, eden se imenuje MAX, drugi pa MIN.
• Oba igralca se borita proti njemu, saj ima nasprotni igralec najmanjšo korist, on pa največjo.
• Oba igralca v igri sta nasprotnika drug drugega, pri čemer bo MAX izbral največjo vrednost, MIN pa bo izbral minimalno vrednost.
• Algoritem minimax izvede algoritem iskanja v globino za raziskovanje celotnega drevesa igre.
• Algoritem minimax nadaljuje vse do končnega vozlišča drevesa, nato pa vrne drevo kot rekurzijo.

Psevdo koda za algoritem MinMax:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

Začetni klic:

Minimax(vozlišče, 3, res)

Delovanje algoritma Min-Max:

• Delovanje algoritma minimax je enostavno opisati s primerom. Spodaj smo vzeli primer igralnega drevesa, ki predstavlja igro za dva igralca.
• V tem primeru sta dva igralca, eden se imenuje Maximizer, drugi pa Minimizer.
• Maximizer bo poskušal pridobiti najvišji možni rezultat, Minimizer pa bo poskušal pridobiti najmanjši možni rezultat.
• Ta algoritem uporablja DFS, zato moramo v tem igralnem drevesu iti vse skozi liste, da dosežemo terminalska vozlišča.
• Na končnem vozlišču so podane končne vrednosti, tako da bomo te vrednosti primerjali in sledili drevesu nazaj, dokler ne pride do začetnega stanja. Sledijo glavni koraki pri reševanju drevesne igre za dva igralca:

Korak 1: V prvem koraku algoritem ustvari celotno igralno drevo in uporabi funkcijo uporabnosti, da pridobi vrednosti uporabnosti za stanja terminala. V spodnjem drevesnem diagramu vzemimo A začetno stanje drevesa. Recimo, da maksimizator naredi prvi obrat, ki ima začetno vrednost v najslabšem primeru =- neskončnost, minimizator pa izvede naslednji obrat, ki ima začetno vrednost v najslabšem primeru = +neskončnost.

2. korak: Zdaj najprej poiščemo vrednost pripomočkov za Maximizer, njegova začetna vrednost je -∞, tako da bomo vsako vrednost v končnem stanju primerjali z začetno vrednostjo Maximizerja in določili višje vrednosti vozlišč. Med vsemi bo našel največ.

• Za vozlišče D max(-1,- -∞) => max(-1,4)= 4
• Za vozlišče E max(2, -∞) => max(2, 6)= 6
• Za vozlišče F max(-3, -∞) => max(-3,-5) = -3
• Za vozlišče G max(0, -∞) = max(0, 7) = 7

3. korak: V naslednjem koraku je na vrsti minimizator, tako da bo vrednost vseh vozlišč primerjal z +∞ in našel 3^rdvrednosti vozlišča plasti.

• Za vozlišče B= min(4,6) = 4
• Za vozlišče C = min (-3, 7) = -3

4. korak: Zdaj je na vrsti Maximizer, ki bo ponovno izbral največjo vrednost vseh vozlišč in našel največjo vrednost za korensko vozlišče. V tem igralnem drevesu so samo 4 plasti, zato takoj dosežemo korensko vozlišče, v resničnih igrah pa bo več kot 4 plasti.

• Za vozlišče A max(4, -3)= 4

To je bil celoten potek dela minimax igre za dva igralca.

Lastnosti algoritma Mini-Max:

Popoln-Algoritem Min-Max je dokončan. Zagotovo bo našel rešitev (če obstaja) v končnem iskalnem drevesu.Optimalno-Min-Max algoritem je optimalen, če oba nasprotnika igrata optimalno.Časovna zapletenost -Ker izvaja DFS za drevo iger, je časovna kompleksnost algoritma Min-Max O(b^m) , kjer je b faktor razvejanosti igralnega drevesa, m pa največja globina drevesa.Prostorska kompleksnost -Prostorska kompleksnost algoritma Mini-max je prav tako podobna DFS, ki je O tem .

Omejitev algoritma minimax:

Glavna pomanjkljivost algoritma minimax je, da postane zelo počasen pri zapletenih igrah, kot so šah, go itd. Ta vrsta iger ima ogromen faktor razvejanosti in igralec ima veliko izbire, da se odloči. To omejitev algoritma minimax je mogoče izboljšati alfa-beta obrezovanje o čemer smo razpravljali v naslednji temi.