• Mini-max algoritms ir rekursīvs vai atkāpšanās algoritms, ko izmanto lēmumu pieņemšanā un spēļu teorijā. Tas nodrošina optimālu gājienu spēlētājam, pieņemot, ka arī pretinieks spēlē optimāli.
• Mini-Max algoritms izmanto rekursiju, lai meklētu spēļu kokā.
• Min-Max algoritms galvenokārt tiek izmantots spēļu spēlēšanai AI. Piemēram, šahs, dambrete, tic-tac-toe, go un dažādas vilkšanas spēlētāju spēles. Šis algoritms aprēķina minimālo maksimālo lēmumu pašreizējam stāvoklim.
• Šajā algoritmā spēli spēlē divi spēlētāji, viens tiek saukts par MAX un otrs tiek saukts par MIN.
• Abi spēlētāji cīnās ar to, jo pretinieka spēlētājs saņem minimālo labumu, kamēr viņi saņem maksimālo labumu.
• Abi spēles spēlētāji ir viens otra pretinieki, kur MAX izvēlēsies maksimālo vērtību un MIN izvēlēsies minimālo vērtību.
• Minimax algoritms veic dziļuma pirmās meklēšanas algoritmu, lai izpētītu visu spēļu koku.
• Minimax algoritms virzās uz leju līdz koka gala mezglam, pēc tam atkāpjas no koka kā rekursijas.

MinMax algoritma pseidokods:

 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 

Sākotnējais zvans:

Minimax (mezgls, 3, patiess)

Min-Max algoritma darbība:

• Minimax algoritma darbību var viegli aprakstīt, izmantojot piemēru. Zemāk mēs esam paņēmuši spēļu koka piemēru, kas attēlo divu spēlētāju spēli.
• Šajā piemērā ir divi spēlētāji, viens tiek saukts par Maksimizatoru, bet otrs tiek saukts par Minimizer.
• Maksimizators mēģinās iegūt maksimālo iespējamo punktu skaitu, un Minimizer mēģinās iegūt minimālo iespējamo punktu skaitu.
• Šis algoritms izmanto DFS, tāpēc šajā spēļu kokā mums ir jāiet cauri lapām, lai sasniegtu termināļa mezglus.
• Termināla mezglā tiek norādītas gala vērtības, tāpēc mēs salīdzināsim šīs vērtības un atgriezīsimies kokā, līdz iestāsies sākotnējais stāvoklis. Tālāk ir norādīti galvenie soļi, kas jāveic, lai atrisinātu divu spēlētāju spēļu koku:

1. darbība: Pirmajā darbībā algoritms ģenerē visu spēļu koku un izmanto utilīta funkciju, lai iegūtu termināļa stāvokļu lietderības vērtības. Zemāk redzamajā koka diagrammā pieņemsim, ka A ir koka sākotnējais stāvoklis. Pieņemsim, ka maksimizators veic pirmo pagriezienu, kura sliktākā gadījuma sākotnējā vērtība = - bezgalība, un minimizētājs veiks nākamo pagriezienu, kura sākotnējā vērtība ir sliktākā gadījuma vērtība = + bezgalība.

2. darbība: Tagad vispirms mēs atrodam utilītu vērtību Maksimizatoram, tā sākotnējā vērtība ir -∞, tāpēc mēs salīdzināsim katru vērtību gala stāvoklī ar Maksimizatora sākotnējo vērtību un noteiksim augstākās mezglu vērtības. Tas atradīs maksimumu starp visiem.

• Mezglam D max(-1,- -∞) => max(-1,4)= 4
• Mezglam E max(2, -∞) => max(2, 6)= 6
• Mezglam F max(-3, -∞) => max(-3,-5) = -3
• Mezglam G max(0, -∞) = max(0, 7) = 7

3. darbība: Nākamajā solī tas ir pagrieziens uz minimizētāju, tāpēc tas salīdzinās visu mezglu vērtību ar +∞ un atradīs 3^rdslāņa mezglu vērtības.

• Mezglam B = min(4,6) = 4
• Mezglam C = min (-3, 7) = -3

4. darbība: Tagad ir kārta Maximizer, un tas atkal izvēlēsies visu mezglu maksimālo vērtību un atradīs maksimālo vērtību saknes mezglam. Šajā spēļu kokā ir tikai 4 slāņi, tāpēc mēs nekavējoties sasniedzam saknes mezglu, bet īstās spēlēs būs vairāk nekā 4 slāņi.

• Mezglam A max(4, -3)= 4

Tāda bija minimax divu spēlētāju spēles pilnīga darbplūsma.

Mini-Max algoritma īpašības:

Pabeigts-Min-Max algoritms ir pabeigts. Tas noteikti atradīs risinājumu (ja tāds ir) ierobežotajā meklēšanas kokā.Optimāls-Min-Max algoritms ir optimāls, ja abi pretinieki spēlē optimāli.Laika sarežģītība -Tā kā tas veic DFS spēļu kokam, Min-Max algoritma laika sarežģītība ir O(b^m) , kur b ir medījuma koka zarojuma koeficients, un m ir koka maksimālais dziļums.Kosmosa sarežģītība -Mini-max algoritma kosmosa sarežģītība ir līdzīga DFS, kas ir Par .

Minimax algoritma ierobežojums:

Galvenais minimax algoritma trūkums ir tas, ka tas kļūst ļoti lēns tādām sarežģītām spēlēm kā šahs, go utt. Šāda veida spēlēm ir milzīgs sazarošanas faktors, un spēlētājam ir daudz izvēles iespēju. Šo minimax algoritma ierobežojumu var uzlabot no alfa-beta atzarošana par ko mēs runājām nākamajā tēmā.