Sprinkfield megoldó

Posted by | · · · · | Cégélet · Webstar Works | 2 hozzászólás Sprinkfield megoldó című bejegyzéshez

Sprinkfield egy logikai játék, amiben különböző szabályok alapján kell locsolni egy adott területet, pályát (szabályokról röviden itt olvashattok). Kezdetben jó ötletnek tűnt kézzel megrajzolni egy pályát, azonban ezzel 2 nehézség is adódott:

  • nehéz volt eldönteni, hogy megoldható-e,
  • nem tudtuk, hogy mi a legjobb (legrövidebb és legtöbb pontot adó) megoldás.
A fenti problémák kezelésére nekiálltunk egy megoldó programot készíteni, hogy automatizáljuk a pályaellenőrzést.

A cikkben összefoglalom, hogy mivel is töltöttük a megoldó készítésére szánt kb. 2 hónapot. Ahogy lenni szokott, elsőre nem sikerült az itt leírtakat jól megvalósítani, így az érdekesebb zsákutcákat is megemlítem, mert a tapasztalat nagyon hasznos volt (és az lehet mások számára is).

Legjobb megoldás

A pálya megoldhatóságának vizsgálatát egybe vettük a legjobb megoldás keresésével (először külön-külön álltunk neki, de kiderült, hogy nem nyerünk annyit a futásidőben, ami igazolta volna a kétféle megoldó párhuzamos fejlesztését).

A legegyszerűbb módon álltunk neki a feladatnak: brute-force módon kipróbáljuk az összes lehetséges locsolás-kombinációt, és a megoldást eredményezők közül kiválasztjuk a legjobbat (Puzzle módban a legrövidebb és azon belül a legtöbb pontot adó; Fullfield módban csak a legtöbb pontot adó).

A kimerítő keresést egy mélységi gráfbejárással valósítottuk meg.

Egyszerű, ugye?

Az alábbiakban kicsit betekintünk az 1 hetes futásidő 14 másodpercre csökkentésének módszerébe a teljesség igénye nélkül.

Gráf

A játékteret a megoldó gráfként ábrázolja, ahol a gráf csúcsai egy-egy játékállásnak felelnek meg, az élei pedig egy szabályos lépésnek (azaz locsolásnak), ami egyik állapotból (játékállásból) a rákövetkezőbe visz át. Ezeket az éleket a lépésgenerátor állítja elő.

sprinkfield-solver-1

A megoldó így ábrázolja a játékot. A bejárás sorrendje: fentről lefelé és balról jobbra.

A brute-force megoldó ezt a gráfot járja be a kezdőállásból indulva úgy, hogy minden állásban minden szabályos lépést kipróbál, majd az ottani állásokat tovább bontja. Egészen addig, ameddig van lépés. Ha nincs, visszalép egy korábbi álláshoz (azaz visszalépéses keresést csinálunk).

Futásidő

A fenti koncepció rendkívül egyszerű, de sajnos nagyon lassú.

Amikor egy pályán a legjobb megoldás keresése egy asztali PC-n 1 hétig tart, akkor ott valamit muszáj tenni. A játékba 70+60 pályát akartunk beletenni, aminek a megoldása 130 hétig futott volna. És akkor még nem számoltuk azokat a pályákat, amiket ugyan megoldattunk, de helyettük inkább másik pályát tennénk a játékba.

Párhuzamosítás 1.

A kézenfekvő megoldás: párhuzamosítsunk! Egyszerre több szálon futtassuk a megoldót, így hamarabb végez. Igen ám, de egy gráfkeresést nem a legegyszerűbb párhuzamosítani…

Ennek ellenére megcsináltuk a legegyszerűbben kivitelezhető verzióját. Közös hash táblát használtak a szálak, amikbe mindegyik beleírta azt az állást, amit kielemzett, illetve mielőtt nekiállt egy újnak, megnézte, hogy más megcsinálta-e már.

Mikor kész lett, örültünk. De csak egy kicsit, mert ahogy lenni szokott, a párhuzamos algoritmus a szálak számával csak logaritmikusan gyorsult, nem lineárisan. Azaz 4 szálon futtatva kb. 2,5-3-szoros gyorsulást értünk el, nem négyszereset.

Párhuzamosítás 2.

Jött a következő ötlet: egyszerre több független szálon indítsuk el a megoldót, és így mindegyik külön pályán tud dolgozni.

Ez egy végtelenül egyszerű ötlet, kivitelezni sem tartott sokáig, és a gyorsulás pedig (a teljes futásidőt tekintve) közel lineárisan arányos a szálak számával. Hogy miért nem ezzel kezdtük…

Lényegében visszaírtuk az algoritmust 1 szálasra, annyival kiegészítve, hogy parancssori argumentumban kapja a megoldandó pályák listáját. Amikor megold egy pályát, egy log fájlba elmenti a megoldást. Viszont mielőtt nekiállna egy pályának, megnézi, hogy van-e hozzá tartozó log, és csak akkor kezdi el, ha nincs. A párhuzamosítást így egyszerűen az operációs rendszerre bíztuk: egyszerre annyi példányban indíthatjuk el, amennyiben akarjuk, mindegyik más-más pályán fog dolgozni.

Hatékonyság

A párhuzamosítás részével elégedettek voltunk, de még mindig ott tartottunk, hogy egy-egy pálya megoldása akár 1 hétig is eltartott. Ezen még volt mit javítanunk…

Paradigma-váltások sorozata

Korábban említettem, hogy mélységi gráfbejárással álltunk neki a megoldásnak. Aztán kipróbáltunk más módszereket is:

Valamilyen szinten minden módszer működött. Két nagy problémával szembesültünk ezeknél:
  • túl sok memóriát igényelt és/vagy,
  • nem tudta az algoritmus, hogy pontosan mikor is ér véget a keresés.
Az A* algoritmus tűnt a legjobb ötletnek. Azonban az implementáláshoz kell egy priorításos sor, ami viszont rengeteg memóriát fogyaszt, ami el is fogy. Implementáltuk ezt a sort egy IntervalHeap struktúrával is, ami lehetővé teszi a sor hosszának korlátozását úgy, hogy a leggyengébb jelölt kiesik a sor végéről. Ezzel a memóriafogyást megoldottuk, de nagyon sokszor fontos elem esett ki a sor végén, ami miatt nem találta meg a legjobb megoldást.

Így végül jobb ötlet híján visszatértünk a mélységi bejáráshoz (ott legalább pontosan tudjuk, hogy mikor néztük végig a teljes gráfot, és ehhez nem kell sok memória sem).

Mi a baj a mélységi bejárással?

Több is van. Az egyik, hogy a gráfunk hatalmas. Egy tipikus 10×10-es pályán átlagosan 100 érvényes kezdőlépés van. A lépések száma átlagosan 10-el csökken minden lépés végrehajtás után. Így egy 10 lépéses megoldás esetén 100*90*80*…*10 állapotot kell megvizsgálni, ami 36 288 000 000 000 000 kiírva.

A nagyobbik probléma viszont az (ami részben ebből a számból is következik), hogy a bejárás nem “emlékszik” arra, hogy melyik csúcsokban járt már, így azokat hajlamos újra bejárni, ha egy másik útvonalon ér egy korábban már vizsgált állapotba.

Azaz faként járja be a gráfot.

Újra gráf

A megoldás: minden pályaálláshoz egy Zobrist kulcsot rendelünk, ami egy véletlen számokból álló XOR-olt 64 bites kulcsot ad. Erről annyit elég most tudnunk, hogy inkrementálisan számolható (azaz a pálya változott részeit elég átszámolni, nem kell mindig a teljes pályára számolni), és ugyanabban a pályaállapotban mindig ugyanaz lesz az értéke, míg különböző állapotokban nagyon kicsi (elhanyagolható) az ütközés esélye. Ez viszont kezelhető.

Tehát a Zobrist kulcsok használatával definiálhatunk egy tetszőleges méretű hash táblát (minél nagyobb, annál jobb – egy darabig), amit a kulcs alsó néhány bitjével indexelünk. Ha a hash táblában megtaláljuk az éppen vizsgálat alatt lévő állapotot, akkor megúsztuk a vizsgálatot, mehetünk a következő állapotra.

Fontos tudni, hogy ezzel a hash táblával nem tudjuk az összes ismétlődést felismerni, azonban minden felismert ismétlődés nagyságrendekkel gyorsítja a bejárást (ha a gráf „tetején” találunk ismétlődést, egy hatalmas részgráfot kihagyhatunk).

sprinkfield-solver-2

Különböző lépéssorozatok, amiknek az eredménye ugyanaz az állás. Ha a fentivel kezdjük, az alsó vonalon a “közös” állapottól már felesleges még egyszer elemezni a gráfot.

Favágás

Lényegében a Zobrist kulcsokkal annyit érünk el, hogy a fa bejárása közben levághatunk bizonyos ágakat, azaz kihagyhatjuk a keresésből. Mindezt anélkül, hogy az eredmény pontosságát kockáztatnánk.

Ezt az ötletet lehet még finomítani. Azaz előállnak olyan állapotok a keresés során, amikről matematikailag bizonyítható, hogy elhagyhatók, mert az eredményt nem fogják befolyásolni.

Ilyenek:

  • (adott állapotból) elérhető legnagyobb pontszám felső becslése: ha ez a becsült érték nem jobb, mint az eddig talált legjobb megoldás pontszáma, felesleges tovább vizsgálni az adott lépéssorozatot,
  • ha a rendelkezésre álló locsolók által lefedhető területlapok száma kisebb, mint a még lefedendő területlapok száma, szintén elhagyhatjuk ezt az ágat,
  • ha mélyebben vagyunk (azaz hosszabb a lépéssorozatunk), mint az eddig ismert legjobb megoldás hossza (Puzzle módban a legrövidebb megoldást keressük),
  • ha több izolált területlap (nem locsolható) állt elő, mint ahány madárijesztőnk van (mivel nem locsolt területre madárijesztőt kell helyezni), a lépéssorozat nem ad megoldást, vághatunk,
  • illetve a lépésgenerátort felokosítottuk, hogy megoldás közben ne csak a szabályokat figyelje, hanem a rendelkezésre álló erőforrásokat is (pl: ha már csak annyi locsolatlan területlap van a pályán, ahány madárijesztőt le kell tenni, akkor olyan lépést nem generál le, ami egy ilyen területlapot is érint)
Lényegében minden vágás, amit felismerünk (és végrehajtunk) exponenciálisan csökkenti a bejárandó gráf méretét. Éppen ezért cél, hogy minél több vágást találjunk, akár még viszonylag nagy (idő)ráfordítással, mert amit nyerünk vele, az többszörösen megtérül.

Feleslegesen kivágott fák

A fenti lista jóval bővebb lehetne, de sok vágás, amit menet közben kitaláltunk végül nem hozta az elvárt pluszt. Általában ez a két ok miatt hagytunk el vágást:

  • hibás módszer: valójában többet vágtunk, mint amit kellett volna, így a legjobb megoldást is,
  • túl költséges vágás: több volt a ráfordítás, mint amit nyertünk vele.
Olyan is volt (egyszer), amikor azért hagytunk el vágást, mert egy másikkal sikerült kiváltani.

A teljesség igénye nélkül álljon itt pár az elhagyottak közül:

  • A bejárás során építettünk a lépések méretének a sorrendjére: egy mélyebb ponton nem próbáltunk ki olyan lépést, ami nagyobb, mint egy magasabb ponton (közelebb a kezdőállapothoz) végrehajtott lépés. Azaz először a nagyokkal indítottunk, aztán a kisebbekkel, és egy kisebb után soha nem próbáltunk nagyobbat. Hiba volt.
  • Előre történő valószínűségi vágás: különböző mágikus számokkal próbáltuk finomhangolni, hogy a lehetséges lépések közül rendezés után csak az első 50-60-..-95%-ot próbáljuk ki. Tudtuk, hogy ezzel megoldást veszthetünk, de reméltük, hogy nem fogunk. Sajnos nem lett olyan jó a lépésrendezés, hogy minden pályán használható legyen (vagy túl sokat vágtunk, vagy nem volt értelme az egésznek).
  • Az elérhető pontszám felső becslését sokszor újragondoltuk. A nehézség abból adódott, hogy mindenképpen felső becslést kellett adni anélkül, hogy bejártuk volna a gráfot. A felső becslés viszont akkor hasznos, ha minél kevésbé becsüli túl a valós pontszámot.
  • Eleinte figyeltük, hogy nincs-e túl sok sáros-, vagy túl kevés föld területlap. Azonban ezt a feladatot delegáltuk a lépésgenerátor felé, így ezek vizsgálata a keresés közben feleslegessé vált.

Fontos tanulság volt, ha egyetlen vágás miatt egy nagyságrenddel gyorsult az algoritmus, akkor az valószínűleg hibás vágás.

Sorrend

A fenti lista egy kulcsfontosságú vágása a pontszám becslés alapján történő vágás.

Ha be tudjuk úgy járni a gráfot, hogy a legjobb megoldást a vizsgálódás elején megtaláljuk, akkor ezzel a vágással a munka nagy részét kikerülhetjük.

Észrevettük, hogy mi emberek viszonylag gyorsan találunk minden pályán egy elég jó megoldást (vagy akár a legjobbat is). Kielemeztük, hogy hogyan is gondolkodunk eközben, és az alábbiakra jöttünk rá:

  • a nagy locsolásokat hamarabb próbáljuk, mint a kicsiket,
  • a pálya által kényszerített lépéseket (pl. sarok) gondolkodás nélkül meglépjük,
  • először a teljes lefedésre összpontosítunk, aztán a pontszám növelésére (Fullfield módban).

Ezeket átültettük a megoldóba, aminek az eredménye az lett, hogy az egy állásban érvényes lépéseket a következő sorrendben próbálja ki az algoritmus:

  1. fontos lépések: ezek azok, amik közül mindenképpen le kell tenni (pl. még száraz terület lapot érint) egyet vagy többet,
  2. minél több locsolatlan területlapot érint, annál hamarabb próbáljuk,
  3. méret szerint a legnagyobbat először.

A fenti sorrendiséget figyelembe véve a megoldó a pályák többségénél néhány másodpercen belül eljut a legjobb megoldásig, az idő hátralevő részét az indirekt bizonyítással tölti (azaz, hogy nincs jobb megoldás).

sprinkfield-solver-3

A gráf (világos háromszög, kezdő csúcs a felső hegy) bejárásnál elhagyott részgráfjai (sötét háromszögek).
Bal oldal: rendezetlen bejárásnál elhagyható részgráfok
Jobb oldal: rendezett bejárásnál elhagyható részgráfok

 

Szimmetria

Az algoritmust tovább lehet javítani, ha a szimmetrikus (a 4 fő szimmetria tengelyre nézve) állások közül csak az egyiket elemezzük. Felmerülhet a kérdés, hogy van-e értelme ennek, hiszen nagyon kevés pálya szimmetrikus.

A játéktér bejárása közben viszont számos olyan állapot áll elő, ami lényegében szimmetrikus (szigorúan véve nem, de az érvényes lépéseket tekintve igen).

img5

Szimmetrikus játékállás: a lerakható lépéseket tekintve a mellékátlóra szimmetrikus a pálya, így elég csak az egyik felét érintő lépéseket kipróbálni

 

A szimmetrikus állásokban ha csak az egyik lehetőséget próbáljuk végig, azzal ugyan elveszthetünk megoldásokat, de pontszámot biztosan nem.

Optimalizáció

A fentiekben összefoglaltuk az algoritmikus szempontból használt eszközöket, amiket a megoldás során alkalmazunk.

Azonban még további értékes órákat nyertünk a programkód hatékonyabbá tételével.

Nyelv

Írtunk megoldót több nyelven is:

  • JavaScript
  • Java
  • C
  • Pascal

Az, hogy melyik nyelven írt megoldót használjuk végül, egy következő blog bejegyzésben kiderül. Ott arról is írni fogok, hogy milyen nyelvspecifikus optimalizációkat használtunk.


2 hozzászólás

Sprinkfield pálya nehézség | Webstar Blog says:

2013. március 28. at 14:50

[…] már írtunk, hogy egy pályán megkeresni a legjobb megoldást nem egyszerű feladat. Miután kiderült, hogy […]

Reply

Sprinkfield megoldó optimalizációja | Webstar Blog says:

2013. április 11. at 11:00

[…] korábbi cikkemben írtam, a Sprinkfield megoldójának több programnyelven is nekiálltunk, azt remélve, […]

Reply