- A Mini-max algoritmus egy rekurzív vagy backtracking algoritmus, amelyet a döntéshozatalban és a játékelméletben használnak. Optimális lépést biztosít a játékos számára, feltételezve, hogy az ellenfél is optimálisan játszik.
- A Mini-Max algoritmus rekurziót használ a játékfán való kereséshez.
- A Min-Max algoritmust leginkább az AI-ban való játékhoz használják. Ilyen például a sakk, a dáma, a tic-tac-toe, a go és a különféle vontatójátékok. Ez az algoritmus kiszámítja a minimális maximális döntést az aktuális állapothoz.
- Ebben az algoritmusban két játékos játszik a játékkal, az egyik a MAX, a másik a MIN.
- Mindkét játékos küzd ellene, mivel az ellenfél játékosa a minimális hasznot kapja, míg ők a maximális hasznot.
- A játék mindkét játékosa egymás ellenfele, ahol MAX választja ki a maximális értéket, MIN pedig a minimális értéket.
- A minimax algoritmus egy mélységi keresési algoritmust hajt végre a teljes játékfa feltárására.
- A minimax algoritmus egészen a fa terminális csomópontjáig halad, majd a fát rekurzióként visszalépi.
Pszeudokód a MinMax algoritmushoz:
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
Kezdeti hívás:
Minimax(csomópont, 3, igaz)
A Min-Max algoritmus működése:
- A minimax algoritmus működése egyszerűen leírható egy példán keresztül. Az alábbiakban példát vettünk a játékfára, amely a kétjátékos játékot képviseli.
- Ebben a példában két játékos van, az egyiket maximalizálónak, a másikat a Minimalizátornak hívják.
- A Maximizer megpróbálja megszerezni a Maximális lehetséges pontszámot, a Minimalizáló pedig a lehető legkisebb pontszámot.
- Ez az algoritmus DFS-t alkalmaz, így ebben a játékfában végig kell mennünk a leveleken, hogy elérjük a terminális csomópontokat.
- A terminális csomóponton a terminális értékek megadva vannak, így összehasonlítjuk ezeket az értékeket, és visszafelé haladunk a fán, amíg a kezdeti állapot be nem következik. A kétjátékos játékfa megoldásának fő lépései a következők:
1. lépés: Az első lépésben az algoritmus létrehozza a teljes játékfát, és a segédfunkciót alkalmazva megkapja a terminálállapotok hasznossági értékeit. Az alábbi fa diagramon vegyük úgy, hogy A a fa kezdeti állapota. Tegyük fel, hogy a maximalizáló veszi az első kört, amelynek a legrosszabb kezdeti értéke =- végtelen, és a minimalizáló veszi a következő kört, amelynek a legrosszabb kezdőértéke = +végtelen.
2. lépés: Most először keressük meg a maximalizáló segédprogramok értékét, a kezdeti értéke -∞, így minden terminál állapotú értéket összehasonlítunk a Maximizer kezdeti értékével, és meghatározzuk a magasabb csomópontértékeket. Meg fogja találni a maximumot az összes közül.
- A D csomóponthoz max(-1,- -∞) => max(-1,4)= 4
- Az E csomóponthoz max(2, -∞) => max(2, 6)= 6
- Az F csomóponthoz max(-3, -∞) => max(-3,-5) = -3
- A G csomóponthoz max(0, -∞) = max(0, 7) = 7
3. lépés: A következő lépésben a minimalizáló köre, tehát az összes csomópont értékét összehasonlítja +∞-vel, és megtalálja a 3-at.rdréteg csomópont értékeit.
- A B csomópontnál = min(4,6) = 4
- A C csomópontnál = min (-3, 7) = -3
4. lépés: Most a Maximizer soron van, és ismét kiválasztja az összes csomópont maximális értékét, és megkeresi a gyökércsomópont maximális értékét. Ebben a játékfában csak 4 réteg van, ezért azonnal elérjük a gyökércsomópontot, de a valódi játékokban több mint 4 réteg lesz.
- Az A csomópont esetén max(4, -3)= 4
Ez volt a minimax kétjátékos játék teljes munkafolyamata.
A Mini-Max algoritmus tulajdonságai:
A minimax algoritmus korlátozása:
A minimax algoritmus fő hátránya, hogy nagyon lelassul az olyan összetett játékoknál, mint a sakk, go stb. Az ilyen típusú játékoknak hatalmas elágazási tényezője van, és a játékosnak rengeteg választási lehetősége van. A minimax algoritmus ezen korlátozása javítható alfa-béta metszés amelyet a következő témában tárgyaltunk.