Pamcenje sahovske pozicije
Strana 1 od 8 12345 ... PoslednjaPoslednja
Prikazujem rezultate 1 do 25 od 180

Tema: Pamcenje sahovske pozicije

  1. #1
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Pamcenje sahovske pozicije

    Evo pitanje za razgibavanje vijuga, najmanja kolicina informacija za pamcenje proizvoljne sahovske pozicije?



  2. #2
    Primećen član maksvel (avatar)
    Učlanjen
    30.06.2004.
    Pol
    muški
    Poruke
    778
    Reputaciona moć
    57

    Podrazumevano Re: 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
    Let the boy try

  3. #3
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    moze u jedan bajt zauzetost, ali je problem sto tad ne znas cime je zauzeto to polje

  4. #4
    Iskusan
    Učlanjen
    06.12.2004.
    Poruke
    5.596
    Reputaciona moć
    103

    Podrazumevano Re: Pamcenje sahovske pozicije

    [font=Verdana]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?
    [/font]

  5. #5
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    Ne planiram nigde, cisto malo da lupamo glavu necim...

    A rokadu si zaboravio

  6. #6
    Iskusan
    Učlanjen
    06.12.2004.
    Poruke
    5.596
    Reputaciona moć
    103

    Podrazumevano Re: Pamcenje sahovske pozicije

    [font=Verdana]Ako ćemo tako zaboravio sam i en passant i koja je rokada u pitanju mala ili velika i promociju pešaka u neku figuru.

    Ali to nema veze sa pamćenjem pozicije.[/font]

  7. #7
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    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.

  8. #8
    Iskusan
    Učlanjen
    06.12.2004.
    Poruke
    5.596
    Reputaciona moć
    103

    Podrazumevano Re: Pamcenje sahovske pozicije

    [font=Verdana]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?[/font]

  9. #9
    Primećen član maksvel (avatar)
    Učlanjen
    30.06.2004.
    Pol
    muški
    Poruke
    778
    Reputaciona moć
    57

    Podrazumevano Re: Pamcenje sahovske pozicije

    Garwore, tražio si samo poziciju... Nego, npr. za an-pasan treba znati da li je pešak išao odmah 2 polja ili jedno-po-jedno...
    Let the boy try

  10. #10
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    Mislim da nema vise pravila (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)
    Poslednji put ažurirao/la Garwor : 01.03.2007. u 22:34 Razlog: osmica

  11. #11
    Iskusan
    Učlanjen
    06.12.2004.
    Poruke
    5.596
    Reputaciona moć
    103

    Podrazumevano Re: Pamcenje sahovske pozicije

    Citat Original postavio maksvel
    Garwore, tražio si samo poziciju... Nego, npr. za an-pasan treba znati da li je pešak išao odmah 2 polja ili jedno-po-jedno...
    [font=Verdana]Jedino što treba znati da li se neki pešak može uzeti na taj način ili ne u sledećem potezu, dakle 1 bit dovoljan.[/font]

  12. #12
    Iskusan
    Učlanjen
    06.12.2004.
    Poruke
    5.596
    Reputaciona moć
    103

    Podrazumevano Re: Pamcenje sahovske pozicije

    @Garwor
    [font=Verdana]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.


    [/font]

  13. #13
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    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?

  14. #14
    Iskusan
    Učlanjen
    06.12.2004.
    Poruke
    5.596
    Reputaciona moć
    103

    Podrazumevano Re: Pamcenje sahovske pozicije

    [font=Verdana]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-)[/font]

  15. #15
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    Odlicno, bit po bit, polako ali sigurno smanjujemo!
    Moramo smanjiti ispod 200!

  16. #16
    Peruzzi nije na forumu
    је дошао тихо и ушао у легенду...
    Domaćin Peruzzi (avatar)
    Učlanjen
    03.08.2003.
    Pol
    muški
    Lokacija
    Shumadija
    Poruke
    3.924
    Reputaciona moć
    92

    Podrazumevano Re: Pamcenje sahovske pozicije

    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

    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


  17. #17
    Peruzzi nije na forumu
    је дошао тихо и ушао у легенду...
    Domaćin Peruzzi (avatar)
    Učlanjen
    03.08.2003.
    Pol
    muški
    Lokacija
    Shumadija
    Poruke
    3.924
    Reputaciona moć
    92

    Podrazumevano Re: Pamcenje sahovske pozicije

    a vidis tek sad videh za pesake.

    16 * 6 za pesake + 4*6 za lovce (jer idu samo po poljima jedne boje) + 12 * 7 za ostale = 96+24+84 = 204

    verovatno da ispod ovoga vise ne moze da se ide. naravno ako se pamti samo pozicija


  18. #18
    Peruzzi nije na forumu
    је дошао тихо и ушао у легенду...
    Domaćin Peruzzi (avatar)
    Učlanjen
    03.08.2003.
    Pol
    muški
    Lokacija
    Shumadija
    Poruke
    3.924
    Reputaciona moć
    92

    Podrazumevano Re: Pamcenje sahovske pozicije

    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


  19. #19
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    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.

  20. #20
    Primećen član maksvel (avatar)
    Učlanjen
    30.06.2004.
    Pol
    muški
    Poruke
    778
    Reputaciona moć
    57

    Podrazumevano Re: Pamcenje sahovske pozicije

    Heh, za ovo postoji čitava teorija - bacite pogled na ovo: http://en.wikipedia.org/wiki/Board_representation
    Let the boy try

  21. #21
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    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?

  22. #22
    Peruzzi nije na forumu
    је дошао тихо и ушао у легенду...
    Domaćin Peruzzi (avatar)
    Učlanjen
    03.08.2003.
    Pol
    muški
    Lokacija
    Shumadija
    Poruke
    3.924
    Reputaciona moć
    92

    Podrazumevano Re: Pamcenje sahovske pozicije

    ajd cu vam kazem sutra. idem u skolu ebiga, valjda ce mi biti dosta i skraceni casovi za ovako nesto


  23. #23
    Iskusan
    Učlanjen
    06.12.2004.
    Poruke
    5.596
    Reputaciona moć
    103

    Podrazumevano Re: Pamcenje sahovske pozicije

    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)

    [font=Verdana]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.[/font]
    Poslednji put ažurirao/la bojan p : 04.03.2007. u 16:48

  24. #24
    Poznat Garwor (avatar)
    Učlanjen
    27.04.2004.
    Pol
    muški
    Poruke
    7.152
    Reputaciona moć
    121

    Podrazumevano Re: Pamcenje sahovske pozicije

    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.

  25. #25
    Iskusan
    Učlanjen
    06.12.2004.
    Poruke
    5.596
    Reputaciona moć
    103

    Podrazumevano Re: Pamcenje sahovske pozicije

    [font=Verdana]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.[/font]

Strana 1 od 8 12345 ... PoslednjaPoslednja
Vrh strane

Slične teme

  1. Program za šahovske završnice
    Autor Zagor BG u forumu Softver
    Odgovora: 13
    Poslednja poruka: 18.03.2006., 01:48
  2. SeX pozE , poZiciJe :P
    Autor ZalePniCa u forumu Ljubav i seks
    Odgovora: 2
    Poslednja poruka: 15.07.2005., 12:32

Pravila za slanje poruka

  • Ne možete kreirati novu temu
  • Ne možete poslati odgovor
  • Ne možete dodati priloge
  • Ne možete prepraviti svoju poruku
  •