Stratégiai játékok lejátszása a Minimax algoritmussal

Ebben a leckében egy minimális algoritmust fogunk felfedezni . Megtanulunk néhány barátságos szomszédsági kiegészítő funkciót is, például a heurisztikus pontszámokat , az iteratív mélyítést és az alfa-béta metszést . Ezekkel a technikákkal rugalmasabb és erőteljesebb játékügynököt hozhatunk létre. Számos kihívásban versenyezhet, beleértve az Isolation stratégiai játékot is.

A How to Win Sudoku előző bejegyzésemben megtanultuk, hogyan kell megtanítani a számítógépeket a Sudoku rejtvény megoldására. Ha még nem olvasta el, folytassa és gyorsan olvassa el. De ez valójában csak egy módszer volt arra, hogy nedvesítsük a lábunkat, mielőtt a játékügynökök kifinomultabb módszereibe merülnénk. Különösen azok a módszerek, amelyek stratégiai lépéseket tehetnek az ellenfél ellen!

Ne ragadjon el

Az Isolation (vagy Isola) egy körön alapuló stratégiai társasjáték, ahol két játékos megpróbálja ellenfelét egy 7x7-es checker-szerű táblára szorítani. Végül már nem tudnak mozogni (így elszigetelik őket).

Minden játékosnak van egy darabja, amelyet úgy mozgathatnak, mint egy királynőt sakkban - fel-le, balra-jobbra és átlósan. Három feltétel van a darabok mozgatására -

  1. Nem helyezhetik el darabjukat egy már meglátogatott téren.
  2. Nem léphetik át a már meglátogatott tereket (átlósan átpréselni őket rendben).
  3. Nem léphetik át egymás darabját.

A fenti képen a fekete négyzetekből látható, hogy mindkét játékos a táblájának különböző részeire helyezte a darabjait. De a játék előrehaladtával ez azt mutatja, hogy a sárga játékosnak még három lehetséges mozdulata van. Fel és jobbra, jobbra egy négyzet, és jobbra két négyzet. De a kék játékosnak nincs lehetősége. Ezért itt a sárga játékos a győztes.

Most ez egyszerű játéknak tűnhet - és hogy őszinte legyek, ez az. Nem mintha pókert vagy Starcraftot játszanánk. Ennek ellenére még mindig hatalmas mennyiségű mozgás lehetséges, amelyet bármelyik játékos megtehet a játék során.

Az olyan rejtvényekben, mint a Sudoku, van egy „válasz”, amelyet meg akarunk oldani. De a stratégiai játékokra nincs válasz.

Egy másik ellenféllel játszunk - mint például egy személy, számítógép vagy macska nyomozó. Ehhez stratégiára van szükség, és el kell gondolkodni azon, hogyan alakulhat a játék, ahogy gördül.

Az ilyen játékok fejlődhetnek és abszurd mennyiségű lehetséges eredményt hozhatnak létre. Ezért gondolkodnunk kell abban, hogy miként választhatjuk ki a lehető legjobb mozgást, anélkül, hogy eltöltenénk azt az időtartamot, amelyre a macskáknak a Föld benépesítése kellett.

Oké, nincs több macska!

Hatalmas Minimax és barátai

Most, hogy tudod, hogyan kell játszani az Izolációt, vessünk egy pillantást arra, hogyan használhatjuk a minimumx algoritmust; alapanyag az AI közösségben. Megvizsgáljuk a heurisztikus pontszámokat , az iteratív mélyítést és az alfa-béta metszést is . Ezekkel együtt felépíthetünk egy versenyképes AI ügynököt.

Minimax

A minimax algoritmus nagyon népszerű az AI ügynökök körökre osztott stratégiai játékainak megtanítására. Ennek oka az, hogy figyelembe veszi az összes lehetséges mozgást, amelyet a játékosok a játék során bármikor megtehetnek. Ezekkel az információkkal azután megpróbálja minimalizálni az ellenfél előnyét, miközben maximalizálja az ügynökét minden lépésnél, amikor az AI ügynök játszani kezd.

Most hogy néz ki ez?

Nos, hasonlóan ahhoz, ahogyan egy AI ügynök olyan játékot játszana, mint a Sudoku, mi is modellezhetjük a következő lehetséges lépéseket, amelyeket bármelyik játékos egy keresőfán keresztül elvégezhet . Ugyanakkor változó szélességű keresőfát kell használnunk - vagy más szavakkal, egy fa szint szélességű. Ennek oka az, hogy változó számú mozdulat van, amelyet minden játékos a játék során bármikor elvégezhet.

A fenti fa az Isolation játék során elérhető következő mozdulatokat jelöli. 2x3 rács van rajta, a jobb alsó négyzet elérhetetlen. Mint látható, a két játékos kék kör és piros kereszt.

A fa teteje (a gyökércsomópont) a piros játékos mozgását szemlélteti. A középső szint a kék játékos következő lehetséges lépéseit mutatja be. A harmadik szint pedig a piros játékos lehetséges mozdulatait szemlélteti, figyelembe véve a kék játékos előző lépését.

A fa minden játékállapotának vagy csomópontjának információi vannak arról, hogy melyik játékosnak van a legtöbb haszna minden lehetséges lépésből.

Most arra lehet kíváncsi, mi a fene azok a háromszögek az egyes mozdulatok alatt?

A lefelé mutató háromszög egy helyet jelent a fában, ahol a minimumx minimalizálja az ellenfél előnyét. Míg a felfelé mutató háromszögek azok a helyek, ahol a minimumx maximalizálja az ügynök előnyét.

De a minimumx csak akkor ismerheti meg bármelyik játékos előnyét, ha ismeri a fa azon útjait, amelyek bármelyik játékos győzelméhez vezetnek. Ez azt jelenti, hogy a minimxnek minden lehetséges mozdulatsoron át a fa legalsó részéig kell haladnia. Ezután meg kell rendelnie bizonyos pontszámokat (pl. +1 győzelemhez és -1 veszteséghez), és ezeket a számokat fel kell terjesztenie a fán. Így a fa minden játékállapotának vagy csomópontjának vannak információi arról, hogy melyik játékosnak van a legtöbb haszna minden lehetséges lépésből.

Ezen a képen tehetünk pár megfigyelést. Az első minimumx számot rendel a végső játék kimeneteléhez a levélcsomópontokban . Ezután felfelé terjeszti őket a fán, minimalizálva és maximalizálva az utat. Amint a minimumx befejezi a fa kitöltését, valahányszor az AI ügynökre kerül a sor, megtudja, hogy melyik mozdulatok vezethetnek valószínűleg győzelemhez vagy veszteséghez.

A gyökércsomópont utáni második szint a kék játékos (AI ügynökünk) következő lehetséges lépéseit mutatja. Ügynökünk a soron belül maximalizálni szeretné az elérhető pontszámokat. Tehát a gyökércsomópontot követő jobb oldali csomópontban ábrázolt lépést választaná. Baromi jó!

De van-e értelme egyszerűen +1 vagy -1 értéket rendelni a játék kimeneteléhez? Nem kellene ennek a pontszámnak figyelembe vennie a játék győzelmét vagy vesztését?

Spoiler riasztás: a válasz igen!

Heurisztikus pontszámok

A stratégiai játékok világában a heurisztikus pontszám lényegében szubjektív érték, amelyet valamilyen játékállapotnak tulajdonítunk. Ez az érték azon a megértésen alapul, hogy miként nyerjük és veszítjük el a játékot. Egy jól átgondolt heurisztikus pontszám kiválasztásával megtaníthatjuk AI ügynökünknek, hogyan válasszuk ki a legjobban a következő lépéseit az Izolálás játék közben.

Most valószínűleg korlátlan számú heurisztikus pontszám áll rendelkezésünkre. De itt csak néhányat nézünk meg, eltekintve a +1 és -1 naiv pontszámától (NS) .

Az egyik ötlet az lehet, hogy minden játékosnak meg kell számlálnia az összes következő lehetséges mozdulatot adott pillanatban, mivel a több lehetséges lépés kevesebb esélyt jelent az elszigeteltségre. Ezt hívjuk nyílt lépés pontszámnak (OMS) .

Másik ötlet lehet az OMS-től kapott érték felhasználása és az ellenfél következő lehetséges mozgásainak levonása. Ennek oka, hogy minden játékos növelni akarja a mozdulatok mennyiségét, miközben csökkenti az ellenfélét. Ezt hívjuk javított pontszámnak (IS) .

A fenti ábra mutatja az AI ügynökök között különböző heurisztikus pontszámokat használó sok szimulált izolációs játék nyerési arányát. Most láthatja, mennyire különböztek a pontszámaink a tényleges játék során. De volt néhány heurisztikus pontszám, amely felülmúlta az általunk kitaláltakat

Érdekes, hogy az első kettő majdnem pontosan megegyezik a jobb pontszámmal. Hívjuk őket agresszívan javított pontszámnak (AIS) és szuper agresszívan javított pontszámnak (SAIS) . De van egy kis különbség ezek között a pontszámok és az eredeti között. A legjobb két pontszám a kettő és a három tényezőt alkalmazza arra az értékre, amellyel kivonja (az ellenfél rendelkezésére álló mozdulatok száma), amikor kiszámítja a javított pontszámot.

Megtalálhatja az optimális „agresszív tényezőt”, amelyet alkalmazni kell a pontszám kiszámításakor!

Újabb spoiler riasztás - jobb értékek léteznek.

De mi van, ha előállunk egy heurisztikus pontszámmal, amelynek kiszámításához sok idő kell? Mi van, ha a fa hatalmas? Van-e elegendő ideje mesterséges ügynökünknek ahhoz, hogy megtalálja a következő legjobb lépéseit, miközben továbbra is elég reagálóképesek a játék során?

Iteratív mélyülés

Most már tudjuk, hogy AI ügynökünk minden lehetséges mozgást modellezhet egy keresőfa és annak csomópontjai megfelelő heurisztikus pontszámának felhasználásával. De sajnos az Isolation játékakor a fánk hatalmas lesz. Több időbe telik a fa keresése és ezen értékek kiszámítása, mint ahány év van az ősrobbanás óta!

Adja meg az iteratív mélyítést - a játékidős ügynökök időgazdálkodási stratégiáját. Ezzel a módszerrel csökkenthetjük a számítási és keresési időt az általunk kiválasztott maximális időre. Így AI ügynökünk legalább olyan gyorsan tud válaszolni, mint egy ember.

De hogyan működik az iteratív elmélyítés?

Lehetővé teszi a minimx számára, hogy szintenként haladjon, és a heurisztikus pontszámokat kiszámolja egy bizonyos határidőig. Amint elérte ezt az időkorlátot, az AI ügynök arra kényszerül, hogy a felfedezett legjobb mozdulatot használja, miközben egyre mélyebbre lépett a fán.

Ez most némi betekintést nyújt a nehézségbe. Olyan intelligens és ügyes AI-ügynökök létrehozása, amelyek elegendőek a stratégiai játékokhoz, meglehetősen trükkös lehet, még az AI varázslók számára is. Különösen, ha az ilyen játékok tartalmazzák a lehetőségek világát.

Sajnos az AI ügynök által elképzelhető továbblépések száma korlátozott. Tehát lehetséges, hogy olyan döntést hozhat, amely a pusztulásához vezet. Ez egy jól ismert jelenség, az úgynevezett horizonthatás . De még mindig meg kell vizsgálnunk a fák keresésekor alkalmazott vitathatatlanul leghatékonyabb időmegvágó algoritmust.

Alfa-béta metszés

Oké, ezek mazsola és nem aszalt szilva, de mégis - hogy voltak ezek valaha? Komolyan mondom, mazsolakék csoportot?

Lehet, hogy már sejtette, hogy az alfa-béta metszésnek semmi köze nincs az aszalt szilvához, és még inkább a keresési fa méretének (metszésének) csökkentéséhez. Ha nagyon nagy keresőfánk van, kiderül, hogy a minimx használatakor nem mindig szükséges minden csomópontot bejárni.

Meg kell adnunk a minimumx-nek azt a képességet, hogy abbahagyjuk a fa adott régiójának keresését, amikor megtalálja az adott szint garantált minimumát vagy maximumát.

Ha ezt meg tudjuk tenni, ez nagymértékben lerövidítheti AI ügynökünk válaszidejét és javíthatja a teljesítményt.

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

A minimumx algoritmus mélység-első kereséssel mozog a fán. Ez azt jelenti, hogy a fán balról jobbra halad, és mindig a legmélyebbre megy. Ezután felfedezi azokat az értékeket, amelyeket közvetlenül a fölötte lévő csomópontokhoz kell rendelni, anélkül, hogy valaha is a fa más ágait nézné.

Az alfa-béta metszés lehetővé teszi, hogy a minimumx ugyanolyan jó döntéseket hozzon, mint a minimumx egyedül, de magasabb teljesítmény mellett.

Tekintsük a következő képet, amelyen egy fát különféle pontszámokkal rendelünk az egyes csomópontokhoz. Egyes csomópontok piros színnel vannak árnyékolva, ami azt jelzi, hogy ezeket nem szükséges felülvizsgálni.

A fa bal alsó sarkában a minimumx az 5. és 6. értéket nézi az alsó max szinten. Meghatározza, hogy 5-öt a fölötte lévő min szinthez kell rendelni. Van értelme.

De miután megnézte a jobb és a jobb oldali elágazás 7-et és 4-ét, rájön, hogy a fenti min szintű csomóponthoz maximum 4 értéket kell rendelni. Mivel az első min szint felett közvetlenül a második max szint 5 és legfeljebb 4, egyértelmű, hogy az 5-öt választja. Ezt követően folytatja a fát, hogy ugyanazokat a műveleteket végezze el a fa többi ágán belül.

Az alábbiakban a minimumx algoritmikus ábrázolása látható alfa-béta metszéssel.

Ennek a módszernek a használata egyszerű módot kínál az AI ügynökünk keresési terének csökkentésére. Így az alfa-béta metszés lehetővé teszi, hogy a minimumx olyan jó döntéseket hozzon, amelyeket a minimumx egyedül képes megtenni, de magasabb szintű teljesítménnyel.

Isola-ter

Felfedeztük, hogyan építhetnénk fel saját AI ügynököket, amelyek meglehetősen versenyképes szinten képesek játszani az Izolálás játékot. A minmax algoritmus használatával láttuk, hogy az AI ügynök hogyan modellezheti a játékot, és hogyan tud döntéseket hozni heurisztikus pontszám alapján. Megtanultuk azt is, hogyan lehet meghatározni az adott feladatunkhoz jól meghatározott heurisztikát (Izolálás).

De azt is felfedeztük, hogy számítási szempontból túl intenzív lenne engedni a minimumxot vadul futni. Tehát olyan technikákat kellett alkalmaznunk, mint az iteratív mélyítés és az alfa-béta metszés. Ezek arra kényszerítenék AI ügynökünket, hogy ésszerű időn belül előálljon a következő lépéssel. De mi van, ha azt akarjuk, hogy AI ügynökünk magasabb nyerési arány mellett legalább olyan reagálóképes legyen, mint egy ember?

Nos, vannak más technikák, amelyeket felfedezhetünk ügynökünk győzelmi arányának és válaszidejének növelése érdekében. Megérintettük azt az ötletet, hogy módosítsuk heurisztikus pontszámunk paramétereit (emlékszel az „agresszív faktorra”?). Akár egy heurisztikus pontszámot is előállíthatunk, amely jobban megfelel az Isolation játékának.

Visszaverő tulajdonságok is vannak az Isolation táblán történő lehetséges elmozdulásokkal kapcsolatban. Ezek nyilvánvalóvá válnak, amikor elemezzük a teljesen feltöltött keresőfát, amely lehetővé tenné számunkra, hogy sok ágat levágjunk a keresőfáról. Továbbá, ha frissítenénk a hardverünket, az AI ügynökünk gyorsabb lenne - és így több lehetőséget tudna felfedezni.

Ha bele akarsz jutni a megvalósítás mikéntjébe, nézd meg a kódot, amelyet a probléma megoldására írtam az Udacity Mesterséges Intelligencia Nanodegree-hez. Megtalálhatja a GitHub repomon.

Szia, Grant vagyok! Szabadúszó dev és kvantum vagyok. Nézze meg a webhelyemet a //freelancequant.com címen. Egészségére!