logo

„Mini-Max“ dirbtinio intelekto algoritmas

  • 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ė.

Mini-Max algoritmas AI

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
Mini-Max algoritmas AI

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
Mini-Max algoritmas AI

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
Mini-Max algoritmas AI

Tai buvo visa „minimax“ dviejų žaidėjų žaidimo eiga.

Mini-Max algoritmo savybės:

    Pilnas -Min-Max algoritmas yra baigtas. Jis tikrai ras sprendimą (jei yra) baigtiniame paieškos medyje.Optimalus-Min-Max algoritmas yra optimalus, jei abu varžovai žaidžia optimaliai.Laiko sudėtingumas -Kadangi jis atlieka DFS žaidimų medžiui, Min-Max algoritmo laiko sudėtingumas yra O (bm) , kur b yra medžiojamojo medžio šakojimosi koeficientas, o m yra didžiausias medžio gylis.Erdvės sudėtingumas -Mini-max algoritmo erdvės sudėtingumas taip pat panašus į DFS, kuris yra Apie .

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.