momente şi schiţe de informatică

Modelarea tablei şi jocului de şah (XIV)

Creat: 2012/jul       Comentarii

int | javaScript | reprezentare 0x88 | șah

În cadrul unui program care joacă şah este esenţial să avem o codificare internă eficientă, pentru mutări - fiindcă pentru a alege mutarea pe care să o joace, programul procedează în general astfel: generează lista mutărilor posibile în poziţia respectivă (şi eventual face o primă ordonare a ei, după un anumit criteriu valoric); apoi, ia pe rând fiecare dintre aceste mutări, o efectuează temporar pe o tablă de joc internă şi pentru poziţia rezultată, generează lista mutărilor posibile (răspunsurile adversarului, la mutarea proprie considerată), ş.a.m.d.

Se repetă aceşti paşi, pe o "adâncime" prestabilită, evaluând poziţiile rezultate şi reordonând valoric listele (arborescente) de mutări - încât după terminarea investigaţiei pe adâncimea stabilită, să se poată furniza ca răspuns mutarea care a obţinut cea mai mare valoare.

Într-un limbaj C este absolut firesc (şi eficient) să codificăm mutările prin valori de tip int - de exemplu, folosind primul octet pentru a înregistra indexul câmpului de start, al doilea octet pentru indexul câmpului final, etc.; ulterior, informaţiile necesare vor putea fi extrase din codul unei mutări folosind operaţii de deplasare, sau alte operaţii "pe biţi".

Pentru JavaScript (JS) această idee poate să fie una improprie, numerele fiind reprezentate similar tipului double din C. Operaţiile cu numere "întregi" implică o conversie internă prealabilă (de la "double" la "int" pe 32 de biţi) şi apoi una finală (de la "int" intern, la "double"); corectitudinea acestui mecanism de operare cu întregi de 32 de biţi (implicând conversii "double" - "int") decurge din faptul că "double" asigură înregistrarea exactă a întregilor de 32 de biţi (fără pierderea preciziei, specifică reprezentării în "virgulă mobilă").

Totuşi chiar şi în aceste condiţii (neavând o modelare specială pentru "număr întreg"), browserele moderne reuşesc să facă în mod eficient, operaţiile specifice cu numere întregi (fiind important şi pentru browser: DOM angajează şi tablouri de obiecte, iar indecşii tablourilor sunt numere întregi).

Şi la urma urmelor, browserele chiar folosesc o codificare perfect analogă celeia pe care o vrem pentru mutările de şah: modelul RGB, care codifică o culoare printr-un întreg în care primul octet corespunde proporţiei de roşu, al doilea - pentru verde, iar al treilea pentru negru - punându-se probleme precum compunerea unei culori din componente date, sau extragerea unei componente.

Reprezentarea binară a mutării

Pentru mutări adoptăm următoarea codificare, ca întregi pe 32 de biţi:

31 | 30..28 | 27..24  | 23..16 | 15..8  |  7..4  |  3..0        bit 31..0
0  |   xxx  | SPECIAL |  FROM  |   TO   |  PIECE | CAPTURED     valoare înscrisă

Într-un întreg pe 32 de biţi, bitul 31 indică totdeauna semnul valorii (fiind 1 pentru număr negativ); în contextul nostru, îl vom fixăm totdeauna pe zero - evitând astfel unele particularităţi legate de bitul "de semn", ale operaţiilor de deplasare (de exemplu, deplasarea spre dreapta conservă bitul de semn: alert((0x80000000 >> 1).toString(16)); a proba şi înlocuind ">>" cu ">>>").

Ignorăm aici următorii 3 biţi (de ranguri 30..28); într-un "chess-engine" (program care joacă şah) ei ar putea fi utilizaţi pentru a păstra anumite informaţii despre mutare în procesul de căutare a acelei mutări pe care să o joace programul, când acesta ar fi la mutare.

Pe cei 4 biţi 27..24 înregistrăm informaţii asupra unor cazuri "speciale" de mutare:

Valoare      Semnificaţie
    1        O-O (rocadă mică)
    2        O-O-O (rocadă mare)
    3        mutare reversibilă: NU-pion, NU-captură, NU-rocadă
                    (incrementează contorul pentru "regula celor 50 de mutări")
    6        mutare de pion normală (NU-transformare, NU-cu 2 câmpuri)
    7        mutare de piesă (NU pion) cu efect de captură
    0x0E     avansează pion cu 2 câmpuri
    0x0F     pion capturează pion advers "en-passant"
4, 5, 8..13  codul piesei în care se transformă pionul (regele este fireşte, exclus)

Pe următorii doi octeţi înregistrăm indexul câmpului de start (FROM) şi respectiv, al câmpului final (TO), iar pe primul octet al mutării înregistrăm codul piesei mutate (pe biţii 7..4) şi codul piesei capturate (pe biţii 3..0) - "codul piesei" fiind una dintre valorile 2..13 asociate de variabila PIECE_COD celor 12 piese (vezi (XII)), sau fiind eventual valoarea 0 (indicând "fără captură").

Construirea codului binar al mutării

Fie FROM indexul câmpului de start al mutării, iar TO indexul câmpului final - cu valori 0x00..0x7F şi astfel încât mascarea cu 0x88 dă zero (altfel câmpul ar fi înafara tablei "reale" din x88Board[]). Fie PIECE şi CAPT codul piesei mutate, respectiv capturate (când este cazul).

Ca să construim codul de 32 biţi al mutării trebuie să ţinem seama de următorul aspect: fiecare dintre valorile considerate ocupă în reprezentarea ca întreg primul octet (biţii 8..31 fiind zero); de exemplu, FROM = 0x73 (indexul câmpului 'd8') are ca reprezentare întreagă 0x00000073. Deci va trebui să deplasăm spre stânga cu un anumit număr de biţi aceste reprezentări - pentru FROM, TO, etc. - (încât primul octet să ajungă în poziţia specificată de codificarea adoptată mai sus pentru mutare) şi apoi să le "adunăm" (folosind operatorul pe biţi "OR").

Exemplificăm pentru mutarea negrului Qd8-h4 (negrul mută dama de pe d8 pe h4):

FROM: 0x00000073
FROM <<= 16: 0x00730000    FROM trebuie să ocupe al treilea octet

TO: 0x00000037
TO <<= 8: 0x00003700       TO trebuie să ocupe al doilea octet

PIECE: 0x0D: 0x0000000D    codul damei negre
PIECE <<= 4: 0x000000D0    PIECE trebuie să ocupe prima jumătate a octetului

SPECIAL: 0x03              mutare "reversibilă"
SPECIAL <<= 24: 0x03000000 SPECIAL ocupă al patrulea octet din codul mutării

codul mutării: SPECIAL | FROM | TO | PIECE = 0x037337D0

Putem scrie următoarea funcţie pentru a construi codul binar al unei mutări:

function cod_mutare( from, to, piece, spec, capt ) {
    return piece << 4 | from << 16 | to << 8 | spec << 24 | capt;
}
alert( cod_mutare(0x73, 0x37, 0x0D, 3).toString(16) );

Aici, am pus 'capt' (codul piesei capturate) ca ultimul, în lista parametrilor de apel: dacă nu este precizat la apelarea funcţiei (ca în cazul indicat în "alert"), atunci el va fi automat convertit la 0 când trebuie implicat în operaţii cu întregi.

Puteam formula şi aşa: return (FROM << 8 | TO) << 8 | piece << 4 | spec << 24 | capt (FROM este deplasat în al doilea octet şi i se alipeşte la dreapta TO; apoi aceşti 16 biţi sunt deplasaţi spre stânga cu 8 poziţii, astfel că FROM ajunge în al treilea octet, iar TO în al doilea).

Extragerea informaţiilor din codul mutării

Putem obţine orice câmp de biţi mascându-i pe ceilalţi; de exemplu, pentru FROM trebuie selectaţi numai biţii din al treilea octet - deci folosim "masca" 0x00FF0000: 0x037337D0 & 0x00FF0000 ne dă 0x00730000 (în care este "vizibil" numai câmpul FROM).

Dar rezultatul obţinut - folosind & cu o anumită mască - trebuie "corectat", mutând câmpul izolat astfel în primul octet; nu 0x00730000 este indexul FROM dorit, ci 0x00000073! Pentru aceasta, trebuie să deplasăm rezultatul spre dreapta, cu un anumit număr de biţi.

Aceste două operaţii - mascarea şi deplasarea - pot fi şi inversate: întâi deplasăm codul mutării spre dreapta cu 16 biţi (câmpul FROM ajunge astfel în primul octet) şi apoi mascăm cu 0xFF.

Putem scrie o funcţie care să returneze câmpurile din codul unei mutări, astfel:

function move_fields( move_cod ) {
    var fields = {
        'FROM' : (move_cod >> 16) & 0xFF,
        'TO'   : (move_cod >> 8) & 0xFF,
        'SPEC' : (move_cod >> 24) & 0x0F,
        'PIECE': (move_cod & 0xF0) >> 4,
        'CAPT' : move_cod & 0x0F   
    };
    return fields;
}

var fld = move_fields(0x037337D0);

Imaginea pe care am alăturat-o redă inspecţia variabilei "fld", folosind instrumentele browserului Chromium (valorile fiind redate zecimal). Desigur, puteam "alerta" direct rezultatul, adăugând de exemplu alert( fld.FROM +'\n'+ fld['TO'] +'\n'+ fld.SPEC +'\n'+ fld.PIECE +'\n'+ fld.CAPT ).

În treacăt fie spus, deprinderea folosirii instrumentelor de investigare oferite de browserele moderne poate să ne uşureze pe parcurs, punerea la punct a unui program de şah (folosind JS).

Urmează mai departe să ne ocupăm de generarea listei mutărilor legale (în codificarea specificată mai sus), pentru partea aflată la mutare într-o poziţie dată.

Media Dinamică

Articolul 50

Drumuri

ŞahStartTemp

25
32
17
4
19
34
14
3
26
33
16
5
31
24
15
18
35
20
2
13
27
6
9
23
30
11
8
21
28
12
22
29
10
7

Ambiţiile Cavalerului

Localităţi

Judeţ:

Constituirea unei baze de date colectând cu Python de pe web

Bliţuri

Load another random Bliţ

//slightchess

Decoraţiuni hiperbolice

SALARII 2017, 2018

//bacMath
variante BAC matematică

Bacalaureat 2015 -
de la forma microsoftizată, la R

modelare ŞAH, I-XX
construcţia unui PGN-browser()

Linux şi aplicaţii Web
în 24 de ore

Orar şcolar - exemplu
după un orar generat de "aSc Orare"

Orar Adjust
ajustează orarul şcolar