Pamcenje sahovske pozicije

Da krenemo odnekud - sa rasipanjem memorije ;) Na primer, uzmemo trodimenzionalni niz (8, 8, enum), gde je enum figura (pion, top, skakač, lovac, kralj, kraljica)... 'Ajmo suziti :) Ideja: umesto int-a možemo u jedan bajt spakovati "šemu" zauzetosti reda
 
Gde to planiraš da spakuješ poziciju kada ti je memorija problem? ZX81?

Da vidimo, 1 bit za boju figure, 7 različitih figura (kralj, dama, lovac, skakač, top, pešak, "nema figure") - 3 bita, te sledi da ti je za jedno polje potrebno 4bita * 8 * 8 = 256bitova ili 32 bajtova. Ukoliko krenemo od toga da se pamte figure i njihovo mesto, za svaku mesto ti treba 3 + 3 bita + 4 bita za oznaku figure tj. 10bita po figuri * 32 figure = 320 bita tj. 40 bajtova za početnu poziciju.

Dakle, prvi način zahteva manje prostora i ujedno je konstantan bez obzira na broj figura koje se nalaze na tabli. Imaš li slobodnih 32 bajta ili da probamo još nešto da sabijemo?
 
Nisi me razumeo...da bi pozicija bila korektno zapamcena i interpretirana mora sadrzati i informaciju o mogucnosti vrsenja rokade, i mogucnosti uzimanja pesaka en passant naravno. A koja je rokada vrsena nije bitno, kao ni da li je pesak pojeden ili pretvoren u figuru. Recimo da zadajem kompu problem, i moram zadati te informacije radi pronalazenja najboljeg poteza.
 
Da, u pravu si. Možemo da dodamo osmu "figuru", pešak u prethodnom potezu pomeren za dva polja i to ne povećava memoriju. Ostaje da se razreši da li je kralj i/ili top pomeran. Obzirom da nije bitno koliko se puta desilo, već da li se uopšte desilo ili ne, onda je dovoljno imati samo informaciju da li je pomenuta figura pomerana ili ne. Dakle tri bita: beli top a1, beli kralj i beli top h1, odnosno takođe tri bita za crne figure. Znači treba još 6 dodatnih bitova.

Dakle za prvi predlog još 6 bitova, pa je ukupno potrebno 262 bita odnosno 33 bajta. Za drugi predlog logično bi bilo da se ove informacije za svaku figuru, ali u tom slučaju bi bilo potrebno 5 bita za svaku figuru što iznosi 11 bita * 32 = 352 bita, odnosno 44 bajta.

Ovde nedostaje još informacija da li je takva pozicija već postojala (ovo bi zahtevalo pamćenje prethodnih pozicija), kao i koliko je poteza prošlo od poslednjeg pomeranja pešaka odnosno uzimanja figure (pravilo 50 poteza). Za brojanje poteza dovoljno je 6 bitova, a za pamćenje pozicije onoliko koliko je izračunato.

Nadam se da su sada sve neophodne informacije upamćene, da bi se tačno znalo šta je moguće odigrati. Možda ima neko pravilo koje sam propustio?
 
Mislim da nema vise pravila :D (Mozda vreme na satu? :>) )
Dobro si se setio za ponavljanje pozicije i 50 poteza nepomeranja pesaka, to sam bio zaboravio.
Za rokadu mi se cini da je dovoljno po dva bita, da li moze malu i da li moze veliku. Znaci 2 bita manje u odnosu na prvi predlog. (260).
Za ponavljanje pozicije nije bitno da li se desilo 4 ili 20 puta, bitno je da li je bilo tri ponavljanja da bi protivnik mogao traziti remi, znaci jos dva bita (262). Plus onih 6 za pravilo 50 poteza, to je 268 bitova.

Pre glasanja bih predlozio i treci predlog:
Usvoji se redosled figura cije se pozicije citaju , recimo sleva nadesno odozdo na gore (od a1 do h8) i fiksna sirina polja za informacije o toj figuri. Recimo, prvih 5 bita su za topa sa pocetnog polozaja a1, drugih 5 za konja sa b1...decetih 4 bita za pesaka sa a2,...
Da bi se opisala pozicija potrebno je po 3 bita za x i y koordinatu, plus jos jedan za poziciju 'van table', znaci 7 ukupno.
Pesaku ne treba dodatni bit za 'van table' jer se za to moze iskoristiti mesto u prvom redu (tu ne moze da bude pa se smatra da je van table). Takodje, mesto u osmom redu neka znaci da je odigrao za dva polja na 4-ti red (moguc an pasan sto se njega tice) u koloni koju opisuju ostala 3 bita. Znaci za pesaka je dovoljno 6 bita.
Kralj takodje ne moze van table, dosta mu je 6 bita.
Znaci, samo za poziciju, ukupno ((8+1) * 6 + 7 * 7) * 2 = 206 bitova.
Za mogucnost rokade jos 4 bita, za 50 poteza jos 6, za tri ponavljanja jos 2 bita, to je ukupno 218 bitova.
Manjkavost ovog nacina je promocija pesaka, jer onda ne znam iz onih 6 bitova za pesaka, da li je to jos uvek pesak ili je promovisan u neku drugu figuru. Najbanalniji nacin koji mi pada napamet je dodavanje jos po dva bita za svakog pesaka da bi se kodirala figura u koju je promovisan (top, skakac, lovac, kraljica), plus jos jedan za info da li je i ta nova figura na tabli (jer sada ona fora sa prvim redom ne prolazi), znaci pot tri bita za pesaka, to je ukupno ( 3 * 8 ) * 2 = 48 bitova.
Sa onih 218 to je 218 + 48 = 266 bitova :8)
 
@Garwor
Za ponavljanje poziije nije dovoljno samo da li je ponovljena bar tri puta do sada, jer moguće da onaj ko je na potezu je jači i ne bi želeo da ponovi već neku poziciju zato što bi time pružio šansu protivniku da traži remi.

Da 2 bita za jednu stranu je sasvim dovoljno da se zna da li se može napraviti mala ili velika rokada.

Predlog jako zanimljiv, ali ni malo jednostavno. No, vredi se potruditi za 2 bita. :)

Drugi predlog nema konstantan broj bitova (zavisi od broja figura na tabli), te bi bilo neophodno naći neki prosek da bi se njegova efikasnost mogla uporediti sa prvim i trećim.


 
hm, da. Trebalo bi pamtiti sve prethodne pozicije da bi/ne bi u sledecem potezu ponovili treci put. Ali to nema nacina da zapamtimo u okviru jedne pozicije, tako da jedino sto se moze uraditi je pamcenje koliko se puta tekuca pozicija do sada ponovila. No te dodatne stvari (brojanje poteza, rokada, tri ponavljanja) su ionako fiksne za vecinu predloga. Bacimo se na samu poziciju.
Ima tu jos neko mozda potencijalno poboljsanje, odredjenom pesaku je dovoljno 5 bita za poziciju!
Tj, pesak sa pocetnog polja d2 npr se, cak i ako maksimalno jede, moze naci na samo 32 polja, tako da je 5 bita dovoljno. U mom predlogu se ovo tesko moze iskoristiti, ali moze li u nekom od prva dva?
 
Na žalost ideja od smanjenju potrebnog broja bitova za pamćenje pozicije pešaka ne može se primeniti na prvi predlog jer tamo su sve pozicije unapred date na fiksnim mestima. Kod drugog predloga takođe nije moguće primeniti, jer je u pitanju lista figura tako da se ne zna početna pozicija pojedine figure.

Probaću da negde nađem statistiku za ukupan broj figura posle svakog poteza, pošto za 25 figura ili manje, predlog broj dva ima kraći zapis od prvog i trećeg.

Sem toga predlog broj dva se može modifikovati tako što će se izbaciti boja figure, jer bi se prvo navodile sve bele figure, a onda sve crne figure. U tom slučaju osma "figura" bi bila oznaka za promenu boje. Na osnovu toga za jednu figuru je potrebno 9 bita (s tim što bi prvo išla oznaka figure, a potom pozicija), pa bi za poziciju sa 32 figure bilo potrebno 9 * 32 + 3 (promena boje) + 4 (rokada) = 295 bitova. Ono što je zanimljivo je da već sa 28 figura ovo rešenje zahteva svega 259 bitova. 8-)
 
pozicija:array[1..8,1..8] of char;

a u majcinu. pa sad imas 255 znakova za svako polje pa nek svaki znak bude nesto
a - crni pesak
b - beli pesak
c - crni pesak moze an passant
d - crni -||-

Al to mu dodje...hm...8**3=512 valjda...

bolji ste...

dobro. ajd da smanjimo onda bitnost chara na 7. ostaje 128 kombinacija, opet i vise neko dovoljno
(u optimalnom slucaju - 32 figure+ neke njihove osobine).
onda ima 8*8*7 = 448 bita

sa 4 bita (16 kombinacija) vec ne moze nista da se uradi...ebiga, a to je 256 :D

a ako bi promenio pristup i uopste ne koristio niz... hm...

odo da vidim nesto pa cu se vratim kad mi slegne

----

paz ovako. ako zanemarimo an passant i rokadu, nego se pamti samo trenutni polozaj figura onda moze i ovako:
odredi se niz figura (beli pesak1, beli pesak2, beli pesak3 ... top2, dama, kralj, crni pesak1 ...)
za polozaj figure na tabli 8x8 potrebno je 6 bita
za definisanje da li je figura na tabli ili ne potreban je 1 bit

sve zajedno = 32* (6+1) = 224 bita najmanje


paz majku mu pa ovo je tacno pola od 7bitnog niza 8x8 ... interesantno
 
236 bitova za sad

ono prethodno nije tacno nista

za rokadu treba za svaku stranu po 2 bita, ukupno 4
za odredjivanje da li je figura na tabli ili ne treba 32 bita
za an passant treba 16 bitova

za 1. i 8. pesaka treba 5 bitova jer imaju 28 polja na raspolaganju
to je 4*5 = 20 bitova

za ostale pesake treba 6 bitova, to je 12*6 = 72 bita

za lovce treba isto 5 bitova, to je 4*5 = 20 bitova

za ostale figure treba po 6 bitova, a to je 12*6 = 72 bita

sve ukupno ima

2*2 + 32*1 + 16*1 + 4*5 + 12*6 + 4*5 + 12* 6 = 236 bitova



moram da dodam jos da kod pesaka ostaje odredjen broj kombinacija neupotrebljen, i to veliki broj

konkretno, ako se broje s leva na desno

1. 4
2. 30
3. 26
4. 20
5. 20
6. 26
7. 30
8. 4


to je ukupno 320 kombinacija. poprilicno nezanemarljivo. u ovo moze da se strpa rokada i prikazivanje figura na tabli
naravno ostaje problem kako da se procita to lepo
 
Odlicna ideja sa lovcima!
Treba samo 30 bitova za informacije koje su figure na tabli (kraljevi su uvek).
Problem kod ovog resenja sa usvojenim redosledom figura je ako je pesak promovisan u figuru, tj sta ako su na tabli 8 lovaca i 6 dama npr.
Treba i jedan bit da se zna ko je na potezu.
 
Dakle, treba ipak nekad nesto i procitati, mada mi nije to bio cilj, nego da dodjemo do optimalnog resenja sopstvenim snagama. Ali nema veze:
uzmimo 64 bita da oznacavaju zauzetost polja na tabli i to u unapred odredjenom redosledu polja. Ako je polje 1 onda 4 bita(figura + boja) u drugom delu zapisa oznacavaju figuru na tom polju. Tako se dobija 64 + (32 * 4) = 192 bita. Plus 6 bita za 50 poteza, plus 4 bita za rokade, plus 2 bita za tri poteza (jes da je bezveze ali cisto da poredimo sa gornjim predlozima). Fali bit za ko je na potezu ( taj treba dodati i u gornje predloge) i an pasan info. Za an pasan se moze iskoristiti kod figure, recimo 8 znaci da je to pesak na svom cetvrtom redu i to odigrao za 2. Sve u svemu, 192 + 6 + 4 + 2 + 1 = 205 bitova!
Ludo zar ne! Granica od 200 je blizu, moze li ispod nje? :D
 
Eto ti sad, ako ne može ispod 200 kao da ništa i nismo uradili.

Dakle modifikacija poslednjeg predloga koji je dao @Garwor. Jedino što može da se uradi da se napravi kompresija table. Umesto jednog bita za svako polje koristimo 2 ili 4 bita. Ukoliko je prvi bit polja 0 tada sledeći bit kaže da li je na tom polju figura ili ne. Ukoliko je prvi bit 1, tada sledeća 3 bita kažu koliko ima praznih polja. S ovom promenom sledi da nam je za 1, 2, 7 i 8 red potrebno (8 * 4) = 16 bita, a za 3, 4, 5 i 6 red (4 * 4) = 16 bita, pa je ukupno za pamćenje table u početnoj poziciji, potrebno 32, a ne 64 bita. U skladu s tim, ukupan broj bitova za poziciju je 32 + 128 + 6 + 4 + 2 + 1 = 173 bita. :)

Dakle, može li manje od 200 bita? Može. 8)

Ispravka:
Ne može, jer nije dobro izračunato. Za početnu poziciju treba (8 * 4 * 2) + (4 * 4) = 80 bitova, dakle 16 više nego ukoliko se koristi samo bit po polju.
 
Lukav pokusaj, ali avaj, neuspesan ;) (ako sam dobro razumeo, ako nisam izvinjavam se)
Pocetna pozicija se vrlo retko snima u fajl :) DakleM kao sto znamo, sah je vrlo dinamicna igra :) , pa shodno tome figure cesto menjaju polozaje, pa kad uzmemo prosecan broj poteza * verovatnoca igranja figurom...bla bla...dobijamo da je pozicija vrlo cesto popunjena figurama koje nisu gusto grupisane.
Elem, treba izanalizirati najgoru poziciju a to je kad je svako drugo polje popunjeno figurom, dakle:
8 redova * (2_za_ima_nema + 3 * 4_za_jedan_rastojanja) = 8 *14 = 112 bitova samo za zauzetost polja. + 128 za figure = 240 bitova.
Kompresija je ok kad je tabla retko popunjena ali ovde je u najgorem slucaju tacno 50% table popunjeno.
 
Slažem se da u većini slučajeva pozicija nije retko popunjena, ali evo male modifikacije predloga.

Možemo da dodamo 1 bit koji bi rekao da li su polja po redovima ili po dijagonalama. U tom slučaju može da se izabere način koji omogućava bolju kompresiju, tako da korišćenjem pomenutog načina broj bitova može da se smanji na broj koji je manji od 200. Za slučaj koji si naveo i koji se ne može kompresovati ako se to radi red po red, kompresovanje po dijagonali dolazi do punog izražaja.
 
Prijavite se ili registrujte da biste poslali poruku.

Back
Top