- Mini-max-algoritmi on rekursiivinen tai backtracking-algoritmi, jota käytetään päätöksenteossa ja peliteoriassa. Se tarjoaa pelaajalle optimaalisen liikkeen olettaen, että myös vastustaja pelaa optimaalisesti.
- Mini-Max-algoritmi käyttää rekursiota hakeakseen pelipuuta.
- Min-Max-algoritmia käytetään enimmäkseen tekoälyn pelaamiseen. Kuten shakki, tammi, tic-tac-toe, go ja erilaiset hinauspelit. Tämä algoritmi laskee minimax-päätöksen nykyiselle tilalle.
- Tässä algoritmissa peliä pelaa kaksi pelaajaa, joista toinen on nimeltään MAX ja toinen MIN.
- Molemmat pelaajat taistelevat sitä vastaan, kun vastustaja saa minimiedun samalla kun he saavat suurimman hyödyn.
- Pelin molemmat pelaajat ovat toistensa vastustajia, jolloin MAX valitsee suurimman arvon ja MIN valitsee pienen arvon.
- Minimax-algoritmi suorittaa syvyys-ensimmäisen hakualgoritmin koko pelipuun tutkimiseksi.
- Minimax-algoritmi etenee aina alas puun päätesolmuun ja seuraa sitten puuta takaisin rekursiona.
MinMax-algoritmin pseudokoodi:
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
Alkusoitto:
Minimax(solmu, 3, tosi)
Min-Max-algoritmin toiminta:
- Minimax-algoritmin toiminta voidaan kuvata helposti esimerkin avulla. Alla on otettu esimerkki pelipuusta, joka edustaa kahden pelaajan peliä.
- Tässä esimerkissä on kaksi pelaajaa, joista toinen on nimeltään Maximizer ja toinen nimeltään Minimizer.
- Maximizer yrittää saada suurimman mahdollisen pistemäärän ja Minimizer yrittää saada mahdollisimman pienet pisteet.
- Tämä algoritmi käyttää DFS:ää, joten tässä pelipuussa meidän täytyy kulkea lehtien läpi päästäksemme päätesolmuihin.
- Päätesolmussa päätearvot annetaan, joten vertaamme näitä arvoja ja seuraamme puuta taaksepäin, kunnes alkutila tapahtuu. Seuraavat ovat tärkeimmät vaiheet kahden pelaajan pelipuun ratkaisemisessa:
Vaihe 1: Ensimmäisessä vaiheessa algoritmi luo koko pelipuun ja käyttää aputoimintoa saadakseen hyödyllisyysarvot päätetiloihin. Otetaan alla olevassa puukaaviossa A puun alkutila. Oletetaan, että maksimoija ottaa ensimmäisen kierroksen, jolla on pahimman tapauksen alkuarvo = - ääretön, ja minimointi ottaa seuraavan kierroksen, jolla on pahimman tapauksen alkuarvo = + ääretön.
Vaihe 2: Nyt löydämme ensin apuohjelman arvon Maximizerille, sen alkuarvo on -∞, joten vertaamme jokaista päätetilassa olevaa arvoa Maximizerin alkuarvoon ja määrittää korkeammat solmuarvot. Se löytää maksimin kaikista.
- Solmulle D max(-1,- -∞) => max(-1,4)= 4
- Solmulle E max(2, -∞) => max(2, 6)= 6
- Solmulle F max(-3, -∞) => max(-3,-5) = -3
- Solmulle G max(0, -∞) = max(0, 7) = 7
Vaihe 3: Seuraavassa vaiheessa se on minimoinnin vuoro, joten se vertaa kaikkien solmujen arvoa +∞:iin ja löytää 3rdkerroksen solmuarvot.
- Solmulle B = min(4,6) = 4
- Solmulle C = min (-3, 7) = -3
Vaihe 4: Nyt on Maximizerin vuoro, ja se valitsee jälleen maksimiarvon kaikista solmuista ja löytää suurimman arvon juurisolmulle. Tässä pelipuussa on vain 4 kerrosta, joten pääsemme välittömästi juurisolmuun, mutta todellisissa peleissä kerroksia on enemmän kuin 4.
- Solmulle A max(4, -3)= 4
Tämä oli kahden pelaajan minimax-pelin täydellinen työnkulku.
Mini-Max-algoritmin ominaisuudet:
Minimax-algoritmin rajoitus:
Minimax-algoritmin suurin haittapuoli on, että se hidastuu todella monimutkaisissa peleissä, kuten shakki, go jne. Tämän tyyppisissä peleissä on valtava haarautumistekijä, ja pelaajalla on paljon valinnanvaraa. Tätä minimax-algoritmin rajoitusta voidaan parantaa alfa-beta karsiminen josta olemme keskustelleet seuraavassa aiheessa.