Minimax algoritmus alfa-béta metszéssel

a mesterséges intelligencia (AI) megjelenése óta a játék az AI egyik legérdekesebb alkalmazása.

az első sakkprogramokat Claude Shannon és Alan Turing írta 1950-ben, szinte amint a számítógépek programozhatóvá váltak.

az olyan játékok, mint a sakk, a tic-tac-toe és a Go, azért érdekesek, mert a két hadsereg közötti verseny tiszta absztrakcióját kínálják.

ez az absztrakció teszi a játékot vonzó területté az AI kutatás számára.

ebben a cikkben áttekintjük a Minimax algoritmus alapjait, valamint az algoritmus működését.

áttekintjük a minimax algoritmus, az alfa-béta metszés optimalizálását is.

mi a Minimax algoritmus?

a Minimax egy rekurzív algoritmus, amely egy játékos optimális mozdulatának kiválasztására szolgál, feltételezve, hogy a másik játékos is optimálisan játszik.

olyan játékokban használják, mint a tic-tac-toe, go, sakk, Isola, dáma és sok más kétjátékos játék.

az ilyen játékokat tökéletes információs játékoknak nevezzük, mert egy adott játék minden lehetséges mozdulatát láthatjuk.

lehetnek olyan kétjátékos játékok, amelyek nem rendelkeznek tökéletes információkkal, mint például a Scrabble, mert az ellenfél mozdulatát nem lehet megjósolni.

hasonló ahhoz, ahogyan gondolkodunk egy játék során: “ha megteszem ezt a lépést, akkor az ellenfelem csak ezeket a lépéseket tudja megtenni” stb.

a Minimax-ot azért hívják így, mert segít a veszteség minimalizálásában, amikor a másik játékos a maximális veszteséggel rendelkező stratégiát választja.

terminológia

• Game Tree: ez egy olyan struktúra formájában egy fa, amely az összes lehetséges mozog, amely lehetővé teszi, hogy mozog egy állam a játék, hogy a következő állam.

egy játék Keresési problémaként definiálható a következő összetevőkkel:

• kezdeti állapot: a tábla helyzetét tartalmazza, és megmutatja, kinek a mozdulata.
• Utódfunkció: Meghatározza, hogy a játékos milyen jogi lépéseket tehet.
• terminálállapot: ez a tábla helyzete, amikor a játék véget ér.
• segédprogram funkció: Ez egy olyan funkció, amely numerikus értéket rendel a játék kimeneteléhez. Például a sakkban vagy a Tic-tac-toe-ban az eredmény vagy győzelem, veszteség vagy döntetlen, és ezeket a +1, -1 vagy 0 értékekkel lehet ábrázolni. Vannak olyan játékok, amelyeknek sokkal nagyobb a lehetséges kimenetele; például a Backgammon segédprogramjai +192-től -192-ig terjednek. A segédprogram funkciót kifizetési funkciónak is nevezhetjük.

hogyan működik az algoritmus?

két játékos vesz részt a játékban, az úgynevezett MIN és max. A játékos MAX megpróbálja a lehető legmagasabb pontszámot elérni, MIN pedig a lehető legalacsonyabb pontszámot, azaz MIN és MAX megpróbálnak egymással szemben fellépni.

a Minimax algoritmus általános folyamata a következő:

1.lépés: először generálja a teljes játékfát a játék aktuális helyzetétől kezdve egészen a terminál állapotokig. Így néz ki a játékfa a Tic-tac-toe játékhoz.

értsük meg a meghatározott terminológia szempontjából a fenti ábra.

1. a kezdeti állapot az első réteg, amely meghatározza, hogy a tábla üres, MAX pedig játszik.
2. utód funkció felsorolja az összes lehetséges utód mozog. A fa minden rétegére meg van határozva.
3. a terminálállapot a fa utolsó rétege, amely megmutatja a végső állapotot, vagyis azt, hogy a játékos MAX nyer, veszít vagy kapcsolatba lép-e az ellenféllel.
4. ebben az esetben a terminálállapotok segédprogramjai 1, 0 és -1, amint azt korábban tárgyaltuk, és felhasználhatók a többi csomópont segédprogramjainak meghatározására is.

2. lépés: alkalmazza a segédprogram funkciót, hogy megkapja az összes terminálállapot hasznossági értékeit.
3. lépés: Határozza meg a magasabb csomópontok segédprogramjait a terminálcsomópontok segédprogramjai segítségével. Például az alábbi ábrán a négyzetekbe írt terminálállapotok segédprogramjai vannak.

számítsuk ki a terminál feletti réteg bal oldali csomópontjának(piros) segédprogramját. Mivel ez a játékos mozgása MIN, kiválasztjuk az összes segédprogram minimumát. Ebben az esetben ki kell értékelnünk a MIN{3, 5, 10} értéket, amelyről tudjuk, hogy minden bizonnyal 3. Tehát a piros csomópont hasznossága 3.

Hasonlóképpen, az ugyanabban a rétegben lévő zöld csomópont esetében ki kell értékelnünk MIN{2,2} ami 2.

4. Lépés: Számítsa ki a hasznossági értékeket a levelek segítségével, figyelembe véve egy-egy réteget a fa gyökeréig.
5. lépés: végül az összes mentett érték eléri a fa gyökerét, azaz a legfelső pontot. Ezen a ponton Maxnek ki kell választania a legmagasabb értéket.

példánkban csak 3 rétegünk van, így azonnal elértük a gyökeret, de a tényleges játékokban sokkal több réteg és csomópont lesz. Tehát ki kell értékelnünk MAX{3,2} ami 3.

ezért a MAX számára a legjobb nyitó lépés a bal csomópont(vagy a piros). Ezt a lépést minimax döntésnek nevezzük, mivel maximalizálja a hasznosságot, feltételezve, hogy az ellenfél is optimálisan játszik annak minimalizálása érdekében.

összefoglalva,

Minimax döntés = MAX{MIN{3,5,10}, MIN{2,2}}
= MAX{3,2}
= 3

Psuedocode:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

optimalizálás

a Játékfák felépítése általában nagyon időigényes, és csak egyszerű játékokhoz lehet rövid idő alatt előállítani.

ha vannak\ (b\) jogi lépések, azaz., \(b\) csomópontok minden ponton, és a fa maximális mélysége \(m\), a minimax algoritmus időbonyolultsága \(b^m(O (b^m))\).

ennek a helyzetnek a megfékezéséhez néhány optimalizálás hozzáadható az algoritmushoz.

szerencsére életképes megtalálni a tényleges minimax döntést anélkül, hogy a játékfa minden csomópontját megnéznénk. Ezért elemzés nélkül eltávolítjuk a csomópontokat a fáról, ezt a folyamatot metszésnek nevezzük.

alfa-béta metszés

a módszert, amelyet ebben a cikkben megvizsgálunk, alfa-béta metszésnek nevezzük.

ha alfa-béta metszést alkalmazunk egy standard minimax algoritmusra, akkor ugyanazt a lépést adja vissza, mint a standard, de eltávolítja (szilva) az összes csomópontot, amelyek esetleg nem befolyásolják a végső döntést.

először értsük meg az intuíciót, majd formalizáljuk az algoritmust. Tegyük fel, hogy a következő játékfánk van:

ebben az esetben
Minimax döntés = MAX{MIN{3,5,10}, MIN{2, a, b}, MIN{2,7,3}}
= MAX{3, c,2}
= 3

meg lennél lepve!

hogyan tudjuk kiszámítani a maximumot hiányzó értékkel? Itt van a trükk. MIN{2, a, B} minden bizonnyal kisebb vagy egyenlő 2-vel, azaz c<=2,ezért MAX{3,c, 2} – nek 3-nak kell lennie.

a kérdés most az, hogy valóban ki kell-e számolnunk a c-t? Persze, hogy nem.

következtethettünk volna anélkül, hogy megnéztük volna ezeket a csomópontokat. És itt jön képbe az alfa-béta metszés.

néhány definíció:

Alpha: ez a legjobb választás eddig a játékos max. Itt a lehető legmagasabb értéket akarjuk elérni.
béta: Ez a legjobb választás eddig MIN számára, és a lehető legalacsonyabb értéknek kell lennie.

Megjegyzés: minden csomópontnak nyomon kell követnie az alfa és béta értékeit. Az Alpha csak akkor frissíthető, ha MAX a sor, és hasonlóképpen, a béta csak akkor frissíthető, ha MIN esélye van.

hogyan működik az alfa-béta metszés?

1. az alpha = -infinity és a beta = infinity inicializálása a lehető legrosszabb esetekben. A csomópont metszésének feltétele az, amikor az alfa nagyobb vagy egyenlő lesz a bétával.
2. Kezdje azzal, hogy az alfa és a béta kezdeti értékeit hozzárendeli a gyökérhez, és mivel az alfa kevesebb, mint a béta, nem metszjük meg.
3. vigye ezeket az alfa és béta értékeket a bal oldali gyermekcsomópontra. És most a terminálállapot hasznossági értékéből frissítjük az alpha és a be értékeit, így nem kell frissítenünk a beta értékét. Ismét nem metszünk, mert az állapot változatlan marad. Hasonlóképpen, a harmadik gyermek csomópont is. Ezután visszalépve a gyökérbe, beállítjuk az alpha=3 értéket, mert ez az alpha minimális értéke.
   
4. most, alfa=3 és béta = végtelen a gyökér. Tehát nem metszünk. Ha ezt a középső csomópontba visszük, és kiszámítjuk a MIN{2, infinity} értéket, akkor megkapjuk az alfa=3-at és a béta=2-t.
5. metszeni a második és harmadik gyermek csomópont, mert az alfa most nagyobb, mint a béta.
6. az Alfa a gyökérben 3 marad, mert nagyobb, mint 2. Ha ezt a jobb szélső gyermekcsomópontra viszi,értékelje MIN{infinity, 2}=2. Frissítse a béta – T 2-re, az alfa pedig 3 marad.
7. metszeni a második és harmadik gyermek csomópont, mert az alfa most nagyobb, mint a béta.
8. ezért 3, 2, 2-et kapunk a bal, a középső és a jobb oldali min csomópontoknál. A MAX{3,2,2} kiszámításával 3-at kapunk. Ezért anélkül, hogy négy levelet is megnéznénk, helyesen találhatjuk meg a minimax döntést.

pszeudokód (forrás: NPTEL tanfolyam):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

következtetés

a játékok nagyon vonzóak, és a játékprogramok írása talán még izgalmasabb. Mi a Grand Prix verseny az autóipar számára, a játék az AI számára.

ahogy azt sem várnánk el, hogy egy versenyautó tökéletesen működjön egy göröngyös úton, úgy azt sem várhatjuk el, hogy a játék algoritmusai minden helyzetben tökéletesek legyenek.

tehát a minimax algoritmus. Lehet, hogy nem a legjobb megoldás mindenféle számítógépes játékra, amelyeknek AI-vel kell rendelkezniük.

de jó megvalósítás esetén kemény versenytársat hozhat létre.