mi az optimális algoritmus a 2048-as játékhoz?
Bevezetés
2048 egy izgalmas cserép-változó játék, ahol mozog csempe körül, hogy összekapcsolják őket, amelynek célja az egyre nagyobb csempe értékeket.
ebben a bemutatóban megvizsgáljuk a 2048-as játék algoritmusát, amely segít eldönteni a legjobb lépéseket, amelyeket minden lépésben meg kell tenni a legjobb pontszám elérése érdekében.
hogyan kell játszani 2048
egy 2048-as játékot egy 4×4-es táblán játszanak., A tábla minden pozíciója üres lehet, vagy tartalmazhat egy csempe, minden csempe pedig egy számot tartalmaz.
amikor elkezdjük, a táblán két csempe lesz véletlenszerű helyeken, amelyek mindegyikén “2” vagy “4” van – mindegyiknek van egy független 10% esélye arra, hogy “4”, vagy más módon a “2”.
a mozgásokat úgy hajtjuk végre, hogy az összes csempét az egyik él felé – felfelé, lefelé, balra vagy jobbra., Ha ezt megteszi, az azonos értékű, egymással szomszédos és együtt mozgó csempék összeolvadnak, és egy új csempével végződnek, amely megegyezik a korábbi kettő összegével:
a lépés után egy új csempe kerül a táblára. Ez egy véletlenszerű helyre kerül, és “2” vagy “4” lesz, ugyanúgy, mint a kezdeti csempe – “2” az idő 90% – a, “4” az idő 10% – a.
a játék ezután folytatódik, amíg nincs több lehetséges lépés.
általában a játék célja egy “2048”értékű csempe elérése., A játék azonban itt nem áll meg, és amennyire lehet, folytathatjuk a játékot, a lehető legnagyobb csempére törekedve. Elméletileg ez egy “131 072″értékű csempe.
problémamegoldás
a játék megoldása érdekes probléma, mert véletlenszerű összetevővel rendelkezik. Nem lehet helyesen megjósolni, hogy nem csak az egyes új csempe kerül-e elhelyezésre, hanem hogy “2” vagy “4”lesz-e.
mint ilyen, lehetetlen olyan algoritmus, amely minden alkalommal helyesen oldja meg a puzzle-t., A legjobb, amit tehetünk, hogy meghatározzuk, mi lesz a legjobb lépés minden szakaszban, és játszani a valószínűségi játék.
bármikor, csak négy lehetséges lépés van, amit megtehetünk. Néha ezek közül a lépések közül néhánynak nincs hatása a táblára, ezért nem érdemes megtenni – például a fenti táblán a “lefelé” mozgás nem lesz hatással, mivel az összes csempe már az alsó szélén van.
ezután a kihívás annak meghatározása, hogy e négy lépés közül melyik lesz a legjobb hosszú távú eredmény.,
algoritmusunk az Expectimax algoritmuson alapul, amely maga is a Minimax algoritmus variációja, de ahol a lehetséges útvonalakat a fán keresztül súlyozzuk annak valószínűségével, hogy megtörténnek.
Lényegében úgy tartjuk, hogy a játék, mint egy-két játékos játék:
- első Játékos – az emberi játékos – átkerülhet a testület négy irányban
- második Játékos – a számítógépes játékos – hely, a cserép egy üres hely a táblán
ez Alapján tudunk generálni egy fa az eredmények minden mozgás, súlyozott által a valószínűsége, hogy minden egyes lépés történik., Ez megadhatja nekünk a szükséges részleteket annak meghatározásához, hogy melyik emberi lépés valószínűleg a legjobb eredményt adja.
3.1. A játékmenet folyamatábrája
a játékmenet működésének általános áramlása:
a játék véletlenszerű aspektusát azonnal láthatjuk a “véletlenszerű csempe hozzáadása” folyamatban – mind abban a tényben, hogy véletlenszerű négyzetet találunk a csempe hozzáadásához, mind pedig véletlenszerű értéket választunk a csempe számára.
kihívásunk az, hogy eldöntsük, mit kell tennünk a “következő lépés meghatározása” lépésben. Ez a mi algoritmusunk A játékhoz.,
ennek Általános túlcsordulása megtévesztően egyszerűnek tűnik:
csak annyit kell tennünk, hogy szimuláljuk az egyes lehetséges mozdulatokat, meghatározzuk, melyik adja a legjobb eredményt, majd használjuk ezt.
tehát most csökkentettük az algoritmusunkat, hogy szimuláljuk az adott mozdulatot, és létrehozzunk néhány pontszámot az eredményhez.
Ez egy két részből álló folyamat. Az első lépés az, hogy megnézze, lehetséges-e a lépés, ha nem, akkor korán megszakítja a “0”pontszámot., Ha a lépés lehetséges, akkor továbblépünk a valódi algoritmusra, ahol meghatározzuk, milyen jó ez a lépés:
3.2. A következő lépés meghatározása
algoritmusunk eddig kulcsfontosságú része egy lépés szimulálása, amelynek legfontosabb része az, hogy hogyan állítunk elő pontszámot minden lehetséges lépéshez. Itt jön be az Expectimax algoritmusunk.
mindkét játékos minden lehetséges lépését szimuláljuk több lépésben, majd meglátjuk, hogy ezek közül melyik adja a legjobb eredményt. Az emberi játékos számára ez azt jelenti, hogy mind a “fel”, “le”, “balra”, mind a “jobb” mozog.,
a számítógépes játékos, ez azt jelenti, forgalomba mind a “2” vagy “4” – es cserép minden lehetséges üres hely:
Ez az algoritmus rekurzív, minden rekurzív lépés megállás, csak akkor, ha ez egy bizonyos mélységet, a tényleges mozgás az igazi játék.,ulating egy gólt a jelenleg szimulált lap elrendezése
- Szimulálni minden lehetséges emberi mozgás
- mindegyik
- Recurse vissza az algoritmus
- Vissza a pontszám kiszámítása az emberi mozgás
- Hozzáadás a pontszám kiszámítása ez a számítógép mozgás, súlyozva a valószínűsége, hogy ez a lépés történik meg
Ha végeztünk ezzel, majd adja össze a kiszámított pontszámok, ez a végső pontszámot a mozgatni akarjuk, hogy a jelenlegi játék fórumon., Mivel ezt négyszer csináljuk – egy minden lehetséges mozdulatért a jelenlegi játéktábláról -, négy ponttal végzünk, ezek közül a legmagasabb a lépés.
3, 3. Pontozás tábla pozíció
Ezen a ponton, az egyetlen dolog, amit meg kell tennie, hogy kiszámítja a pontszámot a fórumon. Ez nem ugyanaz a pontozás, mint a játék, de figyelembe kell vennie, hogy milyen jó helyzetben van ez a játék folytatása.
számos módja van annak, hogy ezt több tényező hozzáadásával lehet elérni a megfelelő súlyozással együtt., Például:
- Száma üres helyek
- Számos lehetséges egyesíti, azaz, hogy hányszor ugyanazt a számot, az a két szomszédos helyeken
- A legnagyobb érték tetszőleges helyre
- Összege minden olyan helyen,
- Monotonicity a fórumon – így hát a táblára épül, ilyen helyen értékek növekedése egyetlen irányba.
Pseudocode
most, hogy tudjuk, hogyan fog működni az algoritmus, hogyan néz ki ez? Fedezzünk fel néhány pszeudokódot, amely részletesebben leírja az algoritmust.,
nem érdekli a játék tényleges lejátszása, csak a mozdulatok meghatározására szolgáló algoritmusban, így kezdjük ott:
mint korábban, ez eljuttat minket arra a pontra, ahol szimuláljuk az egyes lehetséges lépéseket a kiindulási tábláról, és visszaadjuk azt, amelyik a legjobb. Ez lehetővé teszi számunkra, hogy pontszámokat generáljunk az újonnan szimulált táblákhoz.
mélységi határértéket adtunk hozzá, hogy egy idő után megállítsuk a feldolgozást., Mert együtt dolgozunk egy rekurzív algoritmus, szükségünk van egy módja annak, hogy hagyja abba, különben potenciálisan örökké:
Ez adja a rekurzió, szimulálva ki minden lehetséges emberi számítógép lépés egy bizonyos lépések számát, illetve döntés, amely az emberi mozog a lehető legjobb eredmény.
az egyetlen dolog, ami maradt, hogy dolgozzanak ki egy végső pontszámot az adott tábla pozíció. Ehhez nincs tökéletes algoritmus, a különböző tényezők eltérő eredményeket adnak.,
Teljesítményoptimalizálás
eddig van egy algoritmusunk, amely megpróbálja megoldani a játékot, de ez nem olyan hatékony, mint lehetne. A játék véletlenszerű jellege miatt lehetetlen tökéletesen optimalizált megoldóval rendelkezni – mindig lesz valamilyen szintű ismétlés egyszerűen a folyamat jellege miatt.
legalább mindent megteszünk annak érdekében, hogy csökkentsük a munkát, amit nem kell tennünk.,
már egy kis optimalizálást végzünk a fenti algoritmusban azáltal, hogy nem dolgozunk fel olyan mozdulatokat, amelyek nem befolyásolják a játékot. Vannak más módok is, amelyekkel csökkenthetjük a elvégzendő munkát, például a mozgások halmozott valószínűségének nyomon követése, valamint a megállás, ha ez túl alacsony lesz. Ennek fennáll a veszélye a tökéletes megoldás eltávolításának, de ha a valószínűsége ilyen alacsony,akkor szinte biztosan nem fog megtörténni.
dinamikusan meghatározhatjuk a munka mélységhatárát is., A fenti pszeudokódunk kódolt határa 3, de ezt a számításaink kezdetén dinamikusan kiszámíthatjuk a tábla alakja alapján – például az üres négyzetek számára vagy a táblán lévő különálló lapok számára állítva. Ez azt jelentené, hogy kevesebb lépést haladunk át a táblákról, amelyeknek kevesebb lehetősége van a bővítésre.
Továbbá, mivel lehetőség van arra, hogy újra ugyanazt a tábla pozíciók többször, tudjuk emlékezni ezeket a cache a pontszám az ilyen pozíciók helyett újra számítás őket minden alkalommal., Potenciálisan tudunk generálni minden lehetséges fórumon helyzetben idő előtt, de van egy hatalmas számú ilyen – 281,474,976,710,656 különböző lehetséges tábla pozíciók segítségével csempe akár 2048 – így ez valószínűleg nem megvalósítható.
azonban a legfontosabb optimalizálás, amit tehetünk, az a tábla pontszámainak generálására szolgáló algoritmus beállítása. Ez úgy működik, hogy eldöntsük, mennyire jó a tábla a folytatáshoz, és az ehhez használt tényezők és súlyok közvetlenül kapcsolódnak ahhoz, hogy az algoritmusunk milyen jól játszik.,
következtetés
2048 egy rendkívül érdekes játék, hogy megpróbálja megoldani. Nincs tökéletes módja annak, hogy megoldja, de írhatunk heurisztikát, amely a lehető legjobb útvonalakat keresi a játékon keresztül.
ugyanazok az általános elvek működnek minden kétjátékos játékban – például a sakkban -, ahol nem lehet megjósolni, hogy a másik játékos mit fog tenni bármilyen bizonyossággal.
miért nem próbálja meg megírni ennek végrehajtását, és látni, hogy milyen jól működik?