Notaţia minimală (SAN) şi contextul legal al mutării

Am văzut mai înainte că o mutare SAN (din secţiunea de mutări a textului PGN al partidei) cuprinde - explicit sau implicit - aceste informaţii: tipul mutării (piesă, pion, rocadă), efectul mutării (captură, sau transformare) şi câmpul final; numai când este necesar (pentru a asigura unicitatea mutării, dacă ar exista mai multe mutări legale de tipul respectiv care au acelaşi câmp final)- se mai prevede o indicaţie minimală asupra câmpului iniţial (coloana acestuia, sau linia, sau chiar câmpul întreg - în această ordine şi în măsura în care este suficient pentru disociere).

axb6 este o mutare de pion cu captură pe câmpul final b6. Ţinând cont de regulile de mutare a pionilor, putem deduce de pe ce câmp a plecat pionul (obligatoriu, de pe a5) - dar nu putem deduce dacă s-a capturat o piesă - şi în acest caz, ce piesă - sau s-a capturat pionul advers b6, sau dacă nu cumva este vorba de o captură "en-passant" (a pionului advers tocmai trecut de pe b7 pe b5); nu putem deduce acestea, decât dacă vedem acea poziţie în care se face mutarea menţionată:

Acest exemplu arată că SAN nu ne poate permite să reconstituim poziţia precedentă (măcar pentru piesele din contextul mutării), decât dacă dispunem de informaţii asupra contextului anterior mutării - de exemplu, dacă păstrăm FEN-urile poziţiilor succesive de pe parcursul partidei (şi pentru aceasta, am instituit câmpul .FEN în fiecare obiect Move() din tabloul this.moves); având toate FEN-urile, putem asigura parcurgerea partidei (folosind handlerele de navigare pe care le-am constituit anterior) înainte sau înapoi, eventual şi "pe sărite" (nu neapărat în ordinea consecutivă, a mutărilor).

În (XI) tocmai am completat acele câmpuri care ţin de notaţie, în fiecare Move() din this.moves (câmpul .SAN, în care am extras mutarea curentă din textul PGN al partidei; câmpul .variant pentru variantele de joc indicate în PGN pentru mutarea respectivă; etc.) - dar nu şi câmpul .FEN menit să conţină şirul FEN corespunzător după executarea mutării; cum obţinem acum şi aceste FEN-uri?

Oricare ar fi prima mutare în poziţia iniţială standard, FEN-ul poziţiei rezultate este simplu de stabilit; la fel - după răspunsul negrului şi la fel poate pentru încă vreo câteva mutări următoare.

1. Ne2

Dar există poziţii pentru care cunoaştem FEN-ul, însă (numai pe baza acestui fapt) mutarea SAN curentă nu ne permite să mai scriem FEN-ul care ar rezulta! Astfel în poziţia alăturată, cunoscând numai FEN-ul poziţiei şi mutarea menţionată - nu putem stabili FEN-ul poziţiei rezultate, pentru că pe e2 poate veni atât calul din g1, cât şi calul din c3 (deci am obţine două FEN-uri rezultat, distincte).

Este drept, calul din c3 nu poate muta (ar lăsa regele în şah, ceea ce este ilegal) şi tocmai acest aspect a fost avut în vedere de SAN pentru a nota minimal "Ne2" în loc de "Nge2" - numai că acest aspect (care ţine de legalitatea mutării) nu poate fi dedus cunoscând numai FEN-ul iniţial şi însăşi mutarea SAN menţionată.

Deci pentru a stabili FEN-ul poziţiei este necesar uneori şi un mecanism pentru verificarea legalităţii mutării SAN curente (putând astfel să eliminăm FEN-ul care ar corespunde mutării calului c3, în figura de mai sus). SAU… ar mai fi o soluţie - să renunţăm la SAN, adoptând în schimb o notaţie care să fie independentă de context: Smith Notation (dar marea comunitate şahistă nu poate renunţa la SAN, fiind deja constituită o cantitate imensă de date bazate pe SAN).

Determinarea şirurilor FEN consecutive ale partidei

Angajăm o reprezentare internă (fără nicio legătură directă cu infrastructura DOM şi CSS pe care am creat-o anterior) - să-i zicem generic, BOARD - care să păstreze (într-o anumită codificare), poziţia curentă, atributele de joc necesare (cine este la mutare, ce drepturi de rocadă mai există, etc.) şi totodată, să furnizeze lista tuturor mutărilor legale în poziţia respectivă.

Această nouă infrastructură ne va permite să reflectăm una după alta mutările înscrise deja în this.moves[]; dacă mutarea curentă ("tradusă" în prealabil din SAN, în codificarea adoptată de BOARD) se găseşte în lista mutărilor legale din BOARD-ul curent, atunci actualizăm corespunzător BOARD-ul şi calculăm şirul FEN pentru poziţia rezultată:

    BOARD = set_BOARD( FEN_iniţial );
    for( Move in this.moves[] ) {
        Bmove = convert( Move.SAN );
        if( Bmove in BOARD.legal_moves[] ) {
            actualizează BOARD;
            Move.FEN = get_FEN(BOARD);
        }
    }

Desigur, avem aici o schemă generală de lucru; în realitate, "convert"() ar implica în mod firesc şi verificarea legalităţii mutării (nu ca în schema improvizată aici).

Reprezentarea 0x88

Ca bază pentru infrastructura BOARD vom folosi reprezentarea 0x88. Aceasta înseamnă în primul rând un tablou de 2*64 = 128 întregi, pe care o să-l numim x88Board[] şi care poate fi imaginat alăturând două table de şah (una "reală" şi una "imaginară"):

Folosim indecşi hexazecimali 0..7 pentru linii şi 0..F pentru cele 16 coloane. Alipind un index de linie şi unul de coloană (în această ordine), obţinem indexul obişnuit 00..7F (în notaţie hexazecimală) al unuia dintre cele 128 de elemente ale tabloului; astfel, colţurile au indecşii 00₁₆ (câmpul 'a1'), 0F₁₆ (dreapta-jos), 7F₁₆ (dreapta-sus) şi 70₁₆ (câmpul 'a8'). Dacă a doua cifră este restrânsă la domeniul 0..7, atunci indexul respectiv corespunde unui câmp al tablei "reale" (şi mai indicăm colţurile 07₁₆ pentru 'h1' şi 77₁₆ pentru 'h8').

Dat un câmp al tablei "reale" - ce index îi corespunde? De exemplu, pentru câmpul e4: fiind situat pe a patra linie, este precedat în x88Board[] de 3 linii a câte 16 elemente şi încă de cele 4 câmpuri existente pe linia a patra în stânga sa - deci indexul este 3*16 + 4 = 3*(10)₁₆ + 4 = (34)₁₆.

Mai general, dat un câmp "real" în notaţia obişnuită [a-h][1-8] - indexul său în x88Board[] este 16*(câmp.charCodeAt(1) - 49) + (câmp.charCodeAt(0) - 97), unde .charCodeAt(rang) este o metodă a obiectelor javaScript String() care dă codul caracterului al cărui rang s-a specificat (şi ţinem seama că '1' are codul ASCII 49, iar 'a' are codul 97).

Vom prefera "operaţii pe biţi": înmulţirea cu 16 = 2⁴ echivalează cu deplasarea spre stânga cu 4 biţi, iar adunarea - cu "OR" pe biţi; calculul indicat mai sus revine la (row << 4) | col unde row este linia redusă 0..7 şi col este coloana 0..7 (redusă faţă de codul lui 'a') a câmpului.

Rangul liniei pe care se află câmpul de index dat este câtul împărţirii indexului prin 16 (fiindcă o linie are 16 elemente), deci se poate folosi deplasarea spre dreapta cu 4 biţi: row = index >> 4. Rangul coloanei pe care se află un câmp pe tabla "reală" este dat de restul împărţirii prin 8 a indexului acestuia, deci poate fi obţinut prin col = index & 7 ("AND" cu 7, restul fiind cel mult 7).

În x88Board[] - şi anume pe partea "reală" a sa - vom înscrie valori întregi, reprezentând piesele existente în poziţia curentă (valoarea 0 indicând "câmp liber"); partea "imaginară" pentru servi şi pentru a păstra diverse alte valori, dar ea serveşte în principal pentru simplificarea căutării mutărilor posibile: un câmp al cărui index dă o valoare nenulă când este mascat cu 0x88 este deja în partea imaginară şi deci mutarea pe acest câmp este imposibilă.

Într-adevăr - dacă indexul are a doua cifră 0..7 (deci indică un câmp din partea "reală"), atunci index & 0x88 = 0; dacă a doua cifră este 8..F (vizând în partea "imaginară"), atunci index & 0x88 > 0.

Pentru codificarea pieselor în BOARD instituim (în exteriorul widget-ului) variabila:

    var PIECE_COD = {
        'P': 2, 'p': 3, 
        'N': 4, 'n': 5,
        'K': 6, 'k': 7,
        'B': 8, 'b': 9,
        'R': 10, 'r': 11,
        'Q': 12, 'q': 13
    };

Codurile n-au fost alese chiar la întâmplare; piesele albe având coduri pare, iar cele negre - impare, distincţia rezultă simplu prin mascarea bitului de rang zero (cod & 1 este 0 pentru piesă albă şi este 1 pentru negru); codul piesei omonime de cealaltă culoare, rezultă prin setarea sau resetarea bitului zero (cod |= 1 setează bitul zero, cod &= ~1 îl resetează, iar cod ^= 1 îl comută).

Tabloul x88Board[] îl definim intern, în metoda _init():

_init: function() {
    this.tags = {};   // from the 'tag pairs' section of PGN
    this.moves = [];  // Move() objects, for each move from the 'movetext' PGN-section
    /* ... */ 
    this.x88Board = new Array(128); // 0x88 reprezentation
    this.sq_king = [0, 0];   // the square occupied by the white/black king
    /* ... */
},

Am prevăzut şi un tablou intern de 2 întregi this.sq_king[], pe care vom păstra indecşii câmpurilor ocupate de cei doi regi (poziţia regilor fiind esenţială pentru stabilirea legalităţii unei mutări).

Pentru exemplu, poziţia iniţială se va codifica precum în imaginea alăturată, prin tabloul de valori this.x88Board = [10, 4, 8, 12, 6, 8, 4, 10, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ..., 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 11, 5, 9, 13, 7, 9, 5, 11, 0, 0, 0, 0, 0, 0, 0, 0].

Aici, this.sq_king = [4, 0x74].

Prima problemă care se pune este obţinerea reprezentării x88Board[], dintr-un FEN dat şi apoi invers: cum obţinem şirul FEN corespunzător unei reprezentări BOARD date. Dar problema esenţială (care justifică introducerea infrastructurii BOARD) va consta în obţinerea listei mutărilor legale într-o poziţie dată (şi validarea mutării SAN tocmai preluate din textul PGN al partidei).

De la şir FEN, la reprezentarea binară internă

Un şir FEN conţine şase câmpuri, separate prin câte un spaţiu şi var recs = FEN.split(/\s+/) ne dă un tablou recs[] conţinând câmpurile respective.

recs[0] codifică poziţia pieselor, ca o secvenţă de 8 subşiruri separate prin '/', fiecare reprezentând poziţia pieselor (de la stânga spre dreapta) de pe câte o linie a tablei, începând de la linia 8 (primul subşir) şi încheind cu linia 1 (ultimul subşir); ne-am referit deja la acest câmp, începând din (III).

Tabloul x88Board[] indexează câmpurile tablei tot de la stânga spre dreapta pe fiecare linie, dar începând de la linia 1 şi încheind cu linia 8 (am dat un exemplu mai sus); deci vom inversa subşirurile respective în recs[0], folosind poziţie = recs[0].split(/\x2f/).reverse().join(''): separăm la '/' (de cod 0x2F), inversăm tabloul rezultat şi realipim liniile într-un şir "poziţie".

recs[1] este litera 'w', sau litera 'b' - indicând partea (alb, respectiv negru) care este la mutare în poziţia respectivă. În contextul BOARD vom institui variabila internă .to_move, cu valoarea 0 pentru 'w' şi 1 pentru 'b'.

recs[2] este caracterul '-' dacă în poziţia respectivă nici una dintre părţi nu mai are dreptul de a face vreo rocadă, sau este o secvenţă de caractere [KQkq] indicând ce tip de rocadă poate face fiecare parte în poziţia respectivă (dacă ar fi la mutare): [Kk] vizează rocada mică, iar [Qq] - rocada mare (majusculele corespund albului). Vom înfiinţa corespunzător variabila internă .castle, reflectând drepturile de rocadă pe primii patru biţi ai acestui întreg.

recs[3] este '-' dacă poziţia nu a rezultat în urma unei mutări de avansare cu două câmpuri a unui pion; altfel (în urma avansării unui pion cu două câmpuri) recs[3] este câmpul peste care a trecut pionul, numit câmp "en-passant". De exemplu, după mutarea b7-b5 am avea recs[3] = 'b6'; dacă există un pion alb pe un câmp vecin cu b5 (pe c5, sau pe a5), atunci acesta va putea captura pionul negru pe câmpul b6 (cxb6, respectiv axb6. Vezi imaginea de la începutul articolului).

Pentru recs[3] înfiinţăm .en_pass, care va păstra indexul câmpului peste care a trecut pionul, sau - dacă nu este cazul "en-passant" - punându-i ca valoare -1.

recs[4] este '0' (cifra zero) dacă mutarea care a condus la poziţia respectivă este o mutare de pion, sau dacă este o mutare cu efect de capturare; altfel, recs[4] este incrementat după fiecare mutare (a albului, sau a negrului) care nu este mutare de pion şi nici nu are ca efect o captură. Justificarea considerării acestui contor este dată de "regula celor 50 de mutări": dacă pe parcursul a 50 de mutări consecutive ("mutare" însemnând aici o pereche: mutarea albului şi răspunsul negrului) nu s-a făcut nici o captură şi nu s-a mişcat nici un pion - atunci partida este declarată "remiză".

În sfârşit, recs[5] este '1' în cazul poziţiei iniţiale standard (dar poate fi setat '1' şi pentru o poziţie iniţială setată prin tagul [FEN] în textul PGN) şi este incrementat după fiecare răspuns al negrului - reflectând numărul de perechi de mutări efectuate până la obţinerea poziţiei respective.

Vom folosi .fifty şi .nr_move pentru recs[4] şi recs[5]. În baza celor de mai sus, transformarea de la FEN la infrastructura BOARD poate decurge astfel:

/* Dat FEN, setează tabloul x88Board[] şi setează caracteristicile poziţiei */ 
_setBOARD: function(fen) {
    var BOARD = this.x88Board; 
    for (var i = 0; i < 128; i++) 
        BOARD[i] = 0; // iniţial, toate câmpurile sunt făcute "libere"
    var recs = fen.split(/\s+/); // tabloul celor 6 câmpuri ale FEN-ului
    var board = recs[0].split(/\x2f/) // [Linia8, Linia7, ..., Linia1] (separând la '/')
                       .reverse() // [Linia1, Linia2, ..., Linia8]       
                       .join(''); // poziţia, ca şir compatibil cu indexarea 'a1'..'h8'
    var ofs = 0; // indexul curent în şirul de 64 de câmpuri 'a1'..'h8' (pe tabla 8x8)    
    var self = this;
    board.replace(/[prbnqk]|[1-8]/ig,
        function(x) { // caracterul de la indexul ofs (piesă sau "număr câmpuri libere")
            if (x <= '8') ofs += x - 0; // "sare" peste câmpurile libere
            else { // calculează indexul câmpului în tabloul BOARD[] (8 linii, 16 coloane):
            /* linia câmpului pe tabla 8x8 = ofs/8; înmulţim apoi cu 2^4, fiindcă pe tabla
               8x16 o linie are 16 câmpuri; apoi adăugăm rangul coloanei câmpului, ofs & 7 */
                var sq = ( (ofs >> 3) << 4 ) | (ofs & 7);
                BOARD[sq] = PIECE_COD[x];
                if (x == 'K' || x == 'k') // salvează indecşii câmpurilor regilor
                    self.sq_king[PIECE_COD[x] & 1] = sq;
                ofs++ // vizează următorul caracter
            }
    }); // .replace() a fost folosit aici numai pentru "efectul lateral"
    this.to_move = (/^w$/i.test(recs[1])) ? 0 : 1; // 0/1 alb/negru
    this.castle = 0;  // 1|2 alb O-O|O-O-O; 4|16 negru O-O|O-O-O
    this.en_pass = -1; // câmpul de "en-passant" (sau -1)
    var roq = recs[2].split('');
    for (var i = 0, n = roq.length; i < n; i++) {
        switch (roq[i]) {
            case 'K': this.castle |= 1; break;  // O-O alb
            case 'Q': this.castle |= 2; break;  // O-O-O alb
            case 'k': this.castle |= 4; break;  // O-O negru
            case 'q': this.castle |= 8          // O-O-O negru 
        }
    }
    var ep = recs[3] || "-";
    if (ep != "-") 
        this.en_pass = (ep.charCodeAt(0) - 97) + 16 * (ep.charCodeAt(1) - 49);
    this.fifty = recs[4] || 0; // mutări consecutive fără pion sau captură  
    this.nr_move = recs[5] || 1; // numărul de perechi de mutări 
},

Metoda _init va apela întâi ._extract_pgn() - obţinând tablourile .tags[] şi .moves[] pentru tagurile şi mutările extrase din textul PGN prezentat; apoi, va stabili .FEN_initial (sau şirul din tagul [FEN] dacă există, sau FEN-ul poziţiei iniţiale standard) şi va lansa ._setBOARD(.FEN_initial) - definind infrastructura BOARD care va servi pentru parcurgerea secvenţială a mutărilor din this.moves[] în vederea stabilirii valorilor FEN corespunzătoare fiecăreia (stabilind implicit, legalitatea mutării).

Şirul FEN corespunzător stării binare interne curente, a jocului

Pentru a obţine şirul FEN corespunzător unei reprezentări BOARD date, introducem metoda:

/* Returnează FEN pentru x88Board[] şi caracteristicile curente de joc */
_getFEN: function() {
    var position = [], BOARD = this.x88Board;
    var PIECE_CHAR = [, ,  // nu avem piese de cod 0 sau de cod 1
        'P', 'p', 'N', 'n', 'K', 'k', 'B', 'b', 'R', 'r', 'Q', 'q'
    ]; // dă litera FEN a piesei, pe baza codului 2..13 din BOARD 
    
    /* parcurge BOARD de la linia 8 la linia 1 şi de la stânga la dreapta 
       reţinând în 'position' "număr câmpuri libere" şi piesele întâlnite */
    for (var row = 7; row >= 0; row--) {
        var str = "", empty = 0;
        for (var col = 0; col < 8; col++) {
            var pc = BOARD[(row << 4) | col];
            if (pc > 0) {
                if (empty) str += empty;
                empty = 0;
                str += PIECE_CHAR[pc]
            } else empty++
        }
        if (empty) str += empty;
        position.push(str);
    }
    var fen = [position.join("/")]; // primul câmp FEN (poziţia pieselor)
    fen[1] = this.to_move ? "b": "w"; // al doilea câmp FEN
    var q = "";
    if (this.castle) {
        if (this.castle & 1) q += 'K';
        if (this.castle & 2) q += 'Q';
        if (this.castle & 4) q += 'k';
        if (this.castle & 8) q += 'q'
    } else q = "-";
    fen[2] = q; // drepturile de rocadă
    fen[3] = this.en_pass > 0 ? // stabileşte indexul câmpului de trecere
                (String.fromCharCode(97 + (this.en_pass & 7)) // coloana 
                + ((this.en_pass >> 4) + 1)) // şi linia câmpului de trecere
            : "-"; // câmpul de "en-passant"
    fen[4] = this.fifty; // regula celor 50 de mutări
    fen[5] = this.to_move ? +this.nr_move + 1 : this.nr_move; // numărul de mutări
    return fen.join(" ");
},

Desigur că dacă BOARD ar corespunde unei poziţii ilegale, atunci FEN-ul rezultat va fi şi el ilegal; dar aceasta nu se va întâmpla: la crearea sa, BOARD corespunde lui .FEN_initial (iar FEN-ul iniţial este în mod firesc, corect) iar după aceea, BOARD va fi actualizat intern după fiecare mutare angajând "generatorul de mutări legale" (pe care urmează să-l elaborăm mai departe) - încât tot timpul BOARD va corespunde unor poziţii de joc legale.