- Mini-max algoritmas yra rekursyvus arba atgalinis algoritmas, naudojamas priimant sprendimus ir žaidimų teoriją. Tai suteikia žaidėjui optimalų judesį, darant prielaidą, kad priešininkas taip pat žaidžia optimaliai.
- Mini-Max algoritmas naudoja rekursiją ieškodamas žaidimų medyje.
- Min-Max algoritmas dažniausiai naudojamas žaidžiant AI. Tokie kaip šachmatai, šaškės, „tic-tac-toe“, „go“ ir įvairūs vilkimo žaidėjų žaidimai. Šis algoritmas apskaičiuoja minimalų dabartinės būsenos sprendimą.
- Pagal šį algoritmą žaidimą žaidžia du žaidėjai, vienas vadinamas MAX, o kitas vadinamas MIN.
- Abu žaidėjai kovoja su tuo, nes priešininkas gauna mažiausią naudą, o jie gauna didžiausią naudą.
- Abu žaidimo žaidėjai yra vienas kito priešininkai, kur MAX pasirinks maksimalią vertę, o MIN – sumažintą.
- Minimax algoritmas atlieka giluminės paieškos algoritmą, skirtą viso žaidimo medžio tyrinėjimui.
- Minimax algoritmas tęsiasi iki galo iki galutinio medžio mazgo, tada grąžina medį kaip rekursiją.
MinMax algoritmo pseudokodas:
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
Pradinis skambutis:
Minimax (mazgas, 3, tiesa)
Min-Max algoritmo veikimas:
- Minimax algoritmo veikimą galima lengvai apibūdinti naudojant pavyzdį. Žemiau pateikiame žaidimo medžio pavyzdį, kuris reprezentuoja dviejų žaidėjų žaidimą.
- Šiame pavyzdyje yra du žaidėjai, vienas vadinamas Maksimalizatoriumi, o kitas - Minimizer.
- „Maximazer“ stengsis gauti maksimalų įmanomą balą, o „Minimizer“ – kuo mažiau.
- Šis algoritmas taiko DFS, todėl šiame žaidimų medyje turime pereiti visą kelią per lapus, kad pasiektume terminalo mazgus.
- Galutiniame mazge pateikiamos galinės reikšmės, todėl palyginsime tas vertes ir grįšime nuo medžio iki pradinės būsenos. Toliau pateikiami pagrindiniai žingsniai, susiję su dviejų žaidėjų žaidimo medžio sprendimu:
1 žingsnis: Pirmajame žingsnyje algoritmas sugeneruoja visą žaidimų medį ir taiko naudingumo funkciją, kad gautų galinių būsenų naudingumo reikšmes. Žemiau esančioje medžio diagramoje paimkime, kad A yra pradinė medžio būsena. Tarkime, kad maksimizatorius imasi pirmojo posūkio, kurio prasčiausios atvejo pradinė vertė =- begalybė, o minimizatorius pasuks kitą posūkį, kurio pradinė prasčiausia reikšmė = +begalybė.
2 žingsnis: Dabar pirmiausia randame maksimizatoriaus komunalinių paslaugų reikšmę, jos pradinė vertė yra -∞, todėl kiekvieną reikšmę terminalo būsenoje palyginsime su pradine maksimizatoriaus reikšme ir nustatome aukštesnes mazgų reikšmes. Tarp visų jis ras maksimumą.
- Mazgui D max(-1,- -∞) => max(-1,4)= 4
- Mazgui E max(2, -∞) => max(2, 6)= 6
- Mazgui F max(-3, -∞) => max(-3,-5) = -3
- Mazgui G max(0, -∞) = max(0, 7) = 7
3 veiksmas: Kitame žingsnyje bus minimazeris, todėl jis palygins visų mazgų vertę su +∞ ir suras 3rdsluoksnio mazgo reikšmės.
- Mazgas B = min(4,6) = 4
- Mazgui C = min (-3, 7) = -3
4 veiksmas: Dabar atėjo eilė „Maximazer“ ir vėl pasirinks didžiausią visų mazgų reikšmę ir suras didžiausią šakninio mazgo reikšmę. Šiame žaidimų medyje yra tik 4 sluoksniai, todėl iš karto pasiekiame šakninį mazgą, tačiau tikruose žaidimuose bus daugiau nei 4 sluoksniai.
- Mazgui A max(4, -3)= 4
Tai buvo visa „minimax“ dviejų žaidėjų žaidimo eiga.
Mini-Max algoritmo savybės:
Minimax algoritmo apribojimas:
Pagrindinis „minimax“ algoritmo trūkumas yra tai, kad jis tampa labai lėtas sudėtingiems žaidimams, tokiems kaip šachmatai, eiti ir pan. Šio tipo žaidimai turi didžiulį išsišakojimą, o žaidėjas turi daug pasirinkimų. Šį „minimax“ algoritmo apribojimą galima patobulinti alfa-beta genėjimas kurią aptarėme kitoje temoje.