csütörtök, szeptember 13, 2007

Jaés a megoldás :D

Íme a megoldásom a NavNGo-s kérdésre:
Leg "primkóbb" megoldás lenne 32 biten letárolni a lépést (melyik kockáról melyikre léptek). A rögzítés első lépésénél viszont már rengeteg információnk van. Tudjuk, hogy a fehér fog kezdeni, és hogy 16 bábuval indul és mindegyik bábunak ismert a helyzete, tehát elég csak a bábut "megszólítani" (0..15=4bit) és utána csak azt kell leírni, hogy merre és mennyit lépett.
Mikor "megszólítjuk" a bábut, abban a pillanatban már tudjuk a típusát ami sokat segít az optimalizálásban. Mivel tudjuk a pozíciót és a típust jöhet az irány:Király, Vezér, Huszár esetén ez 3 bit mert nyolc felé léphetnek, Bástya és Futó csak 2 bit mivel ők csak 4 irányba mehetnek a Gyalog meg egy irányba lép. Ezután jön a "mennyiség": A Király max 1-et léphet ígyhát azt nem kell tárolni (hiszen ha megjelöltük akkor ő lép és passz) a Vezér, a Bástya és a Futó mivel keresztül is szelhetik a pályát ezért 3 bitet kapnak a lépés hosszának (Futó esetén nincs értelme az 111-nek mint hossz (hiszen max 7-et léphet) viszont a Bástyánál jelentheti ez a sáncot (ezesetben +1bit ami azt mondja meg, hogy hosszú sánc vagy rövid sánc történt). A Gyalog ütési struktúrája miatt (félrelép az átok) két bitet kényszerülök adni. (ez tovább zsugorítható: ha az első bit 0 akkor csak lép és nincs további bit, ha 1 akkor üt és a második bit mondja meg, hogy jobbra vagy balra.)
Kezdeni csak 10 bábuval lehet, viszont ezzel sajna túlléptük a 8-as keretet amivel 3 biten lehetne tárolni a nyitó bábu azonosítóját, szóval marad a bábu ID 4 byte-on való tárolása, viszont a Gyalognál és a Huszárnál is felmerül az, hogy nem 3 illetve 8 felé indíthat, hanem 2-2 ezért csak egy bit kell ami azt mondja meg, hogy a Gyalog egyet vagy kettőt lép, a Huszár pedig jobbra vagy balra ugrik ki. Ígyhát 5 bit volt amit beküldtem mint nyitólépés letárolására szükséges mennyiség.
És, hogy hogyan lehet még 2 bitet lekapni? Ha úgy nézzük, hogy a bábu id 4 bitjének az első bitje 1 akkor a Gyalogokról van szó és ha 0 akkor a vezérkarról, akkor mindjárt látszik, hogy bár a Gyalog esetén megmarad az 5 bit (miszerint 1xxxY ahol Y az, hogy egyet v. kettőt lép 1xxx meg a gyalog azonosítója) viszont mivel huszárból csak kettő van (és a többi 6 bábut nem lehet megszólítani nyitásnál) ezért huszár esetén elég a 3 bit : 0xY ahol x azt mondja meg, hogy a bal vagy a jobb huszárról beszélünk, Y pedig hogy merre ugrik ki.

Így történt hát. Kicsit átmozgattam az agyamat :) jólesett :D

Nincsenek megjegyzések:

Megjegyzés küldése