Expectimax keresőfa optimalizálása
2015-11-26T03:35:19+01:00
2015-11-26T03:35:19+01:00
2022-07-22T03:08:42+02:00
  • Hello!

    Egy viszonylag összetett probléma megoldásán dolgozom, melyet sikerült egy szép modellre redukálnom, ez így egy kétszemélyes nem zéróösszegű játék.
    Legyen mondjuk a két játékos Fekete és Fehér.

    Egy nxn-es mátrix (kezdetben 0-kal van feltöltve) a játéktér. Kétféle lépés létezik:
    - Fekete lépése a mátrix egy (azonos valószínűséggel) véletlenszerűen választott 0 elemét 1-be billenti;
    - Fehér lépése egy összetett, a modell szempontjából irreleváns matematikai művelet, mely során minden nem nulla érték vagy megnő, vagy 0 lesz. Tudjuk azt is, hogy Fehér egy lépésének eredményeként a mátrix elemeinek összege nem csökken (tehát ha egy lépés során egy cella értéke 0 lesz, egy másik cella értéke legalább a cella eredeti értékével megnő).

    Fekete kezd, a játék vége akkor következik be, amikor Fekete lépne és nem talál 0 mezőt.
    Fehér "pontszáma" a mátrix elemeinek összege a játék végén. Az algoritmusunk célja Fehér pontszámának maximalizálása.

    Az expectimax algoritmust használom, ez tulajdonképpen egy szépen optimalizált brute-force. Aki nem ismeri: ezen pdf első 5 diájából fel lehet fogni a működését.

    Ami eddig történt:
    - adaptív mélységkorlátot vezettem be a fához egy olyan heurisztika alapján, mely mérésekkel igazoltan jól működik
    - a levelekben lévő pályaállapotokhoz is sikerült egy elég jó értékelő függvényt írni (nem pusztán a jelenlegi pontszám a pálya értéke a levelekben, hanem előrebecsül egy csomó mindent egy algoritmus és az alapján saccol egy várható pontszámot az adott pályán)
    - úgy implementáltam az algoritmust, hogy a fa felépítésekor minden csúcsot csak 2-szer látogat meg (lefelé a fa felépítésekor egyszer be kell járni, de visszafelé a fa kiértékelésekor az értékek súlyozása és felfelé propagálása mellett lezajlik a node-ok törlése is)


    A baj, hogy még mindig vagy nagyon lassú (mélyebb keresőfánál), vagy nem elég jó (sekélyebb keresőfánál) az algoritmus.

    Mérések (4x4 pálya):
    - random lépésekkel egy teljes "játék" szimulációja néhány 10 mikroszekundum nagyságrendű, persze így hamar terminál a játék és nagyon alacsony a pontszám
    - az expectimax ugyanekkora pályán kb. 1 millió node-ig bontja ki a gráfot, 0.5s nagyságrendű az egy lépéshez szükséges idő
    - expectimax-szal a játék átlagosan 1500 lépés után terminál (randomnál ez alig 100 volt)
    - random által szerzett pontszám 500 körül, az expectimax 50000 körül

    Ekkora pályán az 50000 pont már jó, de nagyobb mátrixnál exponenciálisan lassul a keresés és nem elég a számítási kapacitás kielégítő pontszám eléréséhez.


    Sokat foglalkoztam magával a szimulátorral, a heurisztikus kiértékelőkkel és az implementáció gyorsításával.
    Úgy látom, eljutottunk odáig, hogy most már az expectimax a szűk keresztmetszet, viszont elméletileg nem lehet a keresőfát vágni (mint pl. minimax esetén alpha-beta nyeséssel), nem tudok ismert egyszerűsítést vagy párhuzamosítási módot ehhez az algoritmushoz.


    Bármi ötlet jó lenne, amivel le lehet vágni bizonyos esetekben részgráfokat, nem kell a teljes fát bejárni, nem kell minden node-ot kiértékelni, esetleg teljesen más koncepció mentén a játékban nagyobb pontszámot elérni, stb.
    Egy kis brainstorming jellegű eszmecserét is nagyon szívesen látnék a témában, igazából bármi jól jönne, ami előrébb mozdítana.


    Köszi, ha eljutottál idáig az olvasásban. :)
    Mutasd a teljes hozzászólást!
abcd