momente şi schiţe de informatică

Modelarea tablei şi jocului de şah (XVII)

Creat: 2012/jul       Comentarii

javaScript | reprezentare 0x88 | SAN | șah

Codurile parţiale asociate mutării SAN şi identificarea mutării legale

Mutarea SAN curentă (din textul PGN al partidei) precizează cel mai adesea, numai piesa şi câmpul TO pe care aceasta trebuie mutată. Din tabelul precalculat ALL_MOVES{} putem extrage câmpurile posibile FROM, de pe care poate veni pe TO piesa respectivă; reţinem numai acele tablouri [FROM, TO] pentru care pe .x88Board[] la indexul corespunzător lui FROM, există o piesă precum cea indicată în SAN. Pentru fiecare dintre aceste tablouri [FROM, TO] (până când întâlnim pe cel al mutării legale) constituim codul binar parţial (numai cu părţile FROM şi TO) al mutării.

Codul mutării este transmis metodei _makeMove(); aceasta simulează mutarea şi verifică dacă regele n-a rămas cumva în şah; dacă mutarea este legală - actualizează x88Board[] şi variabilele interne asociate (returnând "true").

Dar acest demers este dependent de concepţia metodei _makeMove(): aceasta poate accepta ca parametru codul binar parţial (deducând informaţiile care lipsesc, prin investigaţii suplimentare în x88Board[]), sau poate pretinde codul binar complet - generat deja de gen_moves() - al mutării.

Noi alegem varianta în care _makeMove() primeşte ca parametru codul binar complet al mutării. Deci înainte de a apela _makeMove(), trebuie să completăm câmpurile care lipsesc din codul parţial existent; câmpurile PIECE şi CAPTURED (v. (XIV)) sunt uşor de aflat (conţinuturile celulelor din x88Board[] corespunzătoare pentru FROM şi TO), dar câmpul SPECIAL poate pretinde analiza suplimentară a unor cazuri - şi în fond, n-am face decât să repetăm investigaţii deja efectuate în cursul lui _gen_moves() (în principiu, _gen_moves() este apelată înainte de _makeMove(): un program care joacă va alege răspunsul din lista mutărilor posibile, furnizată de _gen_moves()).

Pentru "completarea" codului parţial existent, vom proceda principial: apelăm _gen_moves(), obţinând lista tuturor mutărilor posibile în poziţia respectivă; unul singur dintre codurile binare din această listă se va putea potrivi pe câmpurile FROM şi TO, codului parţial existent (fiind posibilă o singură mutare de pe câmpul FROM pe câmpul TO) - exceptând cazul unei mutări de transformare (când pentru a identifica mutarea, trebuie adăugată codului parţial şi precizarea piesei în care se transformă pionul - ceea ce putem prelua imediat din SAN-ul mutării).

Să aplicăm mecanismul descris mai sus pentru poziţia alăturată, în care albul este la mutare şi SAN indică mutarea "Ne2".

Câmpurile FROM posibile sunt cele accesibile unui cal din TO = 'e2' şi sunt date de ALL_MOVES['N']['e2'] = ['c1', 'c3', 'd4', 'f4', 'g3', 'g1'] - iar pentru poziţia noastră, rămâne FROM = 'c3' sau FROM = 'g1'. Să considerăm pe rând cele două mutări posibile.

Pentru mutarea c3-e2, codul parţial este: 0x2214 (indexul 0x88 al lui FROM='c3' este 0x22; cel pentru TO='e2' este 0x14).

Apelăm _gen_moves(), obţinând lista tuturor mutărilor posibile ale albului în poziţia respectivă (listă în care va trebui să identificăm codul parţial 0x2214):

0: 0x3040360    03 04 03 60: Ke1-d1 (cod-rege = 6, index('e1') = 4, index('d1') = 3)
1: 0x3040560    Ke1-f1
2: 0x3041360    Ke1-d2
3: 0x3041460    
4: 0x3041560
5: 0x3061440    Ng1-e2 (cod-cal = 4, index('g1') = 6)
6: 0x3062540
7: 0x3062740
8: 0x3220140    Nc3-b1
9: 0x3220340    Nc3-d1
10: 0x3221040
11: 0x3221440   codul complet care se potriveşte cu cel parţial (Nc3-e2)
12: 0x3223040
13: 0x3223440
14: 0x3224140   Nc3-b5
15: 0x3224340

Lista are 16 elemente, ceea ce este corect: sunt posibile 5 mutări de rege, 3 ale calului 'g1' şi 8 ale celui din 'c3'. Dintre acestea, aceea care se potriveşte codului parţial existent este mutarea de la indexul 11 al listei - deci codul complet al mutării c3-e2 este 0x03221440.

_makeMove(0x03221440) va returna însă false (regele rămâne în şah). Trecem atunci la cea de-a doua mutare, cu FROM = 'g1' şi repetăm paşii de mai sus pentru acest caz: codul parţial pentru g1-e2 este 0x0614 şi este identificat la indexul 5 al listei de mai sus; iar de data aceasta, _makeMove(0x03221440) va returna true (şi va actualiza .x88Board[] corespunzător mutării).

Desigur, "repetând" paşii de mai sus pentru g1-e2, generăm a doua oară exact lista celor 16 mutări din cazul c3-e2. Va trebui să căutăm o formulare a mecanismului descris şi exemplificat mai sus, astfel încât _gen_moves() să nu fie apelată de două ori pentru o aceeaşi poziţie.

Verificarea legalităţii unei mutări codificate parţial

Aşa cum este formulată în (XV) - metoda _gen_moves(moves) constituie lista mutărilor posibile în tabloul extern referit prin parametrul "moves" (alternativa era: nu primeşte nici un parametru şi returnează tabloul de mutări constituit); aici avem de folosit generatorul de mutări numai pentru poziţia curentă (nu şi pentru răspunsurile posibile ale adversarului la fiecare mutare, ca în cazul unui program care joacă).

Iar acest tablou "moves" nu prezintă interes pentru o instanţă sau alta, a widget-ului (caz în care l-am defini în interior, cu this.moves = []); prin urmare este firesc să adăugăm şi acest tablou ca variabilă "externă" widget-ului (accesibil din interiorul dar nu şi din afara funcţiei care defineşte widget-ul): var bin_moves = []. Mai mult - este firesc acum să eliminăm parametrul "moves" (postat iniţial de dragul generalităţii) din definiţia anterioară pentru _gen_moves():

_gen_moves: function() { // moves) {
    var moves = bin_moves = []; /* reiniţializează tabloul mutărilor binare */
    /* restul codului rămâne nemodificat */
},

Următoarea metodă implementează aproape literal, mecanismul de stabilire a legalităţii mutării FROM-TO (codificate parţial) descris mai sus:

_legal: function(m) { // m este [FROM, TO]: ['e1', 'g1'] sau ['a7', 'a8Q'] etc.
    var from = TO_x88[m[0]]; 
    var prom; // piesa în care promovează pionul
    if (m[1].length == 3) { // 'a8Q' - pionul promovează în damă
        prom = m[1].charAt(2);
        prom = PIECE_COD[prom] | this.to_move;
        m[1] = m[1].replace(/.$/, ""); // reţine câmpul TO
    }
    var to = TO_x88[m[1]];  
    var move = ((from << 8) | to) << 8; // codul binar parţial (deplasat) al mutării
    // caută codul binar complet pentru `move`
    for(var i = 0, n = bin_moves.length; i < n; i++) {
        var m = bin_moves[i];
        if ((m & 0x00FFFF00) == move && (!prom || ((m >> 24) == prom))) 
            if (this._makeMove(m)) 
                return true;  // mutarea este legală (şi x88Board[] actualizat)
    }
    return false; // mutarea este ilegală (şi x88Board[] rămâne nemodificat)
},

Dacă foloseam pentru "codul binar parţial" var move = (from << 8) | to; (0x2214 în exemplificarea de mai sus pentru Ne2, şi nu 0x221400 cum am avea acum, datorită adăugării deplasării finale << 8) atunci în "if" trebuia ((m >> 8) & 0xFFFF) == move - adică pentru fiecare cod din bin_moves[] ar fi fost de făcut câte o deplasare suplimentară.

Tabloul [FROM, TO] primit este transformat în cod binar parţial de mutare, iar acesta este apoi căutat în tabloul bin_moves[]; dacă este identificat aici, atunci codul binar "complet" al mutării este pasat metodei _makeMove() - aceasta va verifica legalitatea mutării respective şi dacă este cazul, va actualiza infrastructura BOARD corespunzător efectuării mutării.

Obţinerea mutării legale corespunzătoare mutării SAN curente

Rămâne să modelăm determinarea valorilor [FROM-posibil, TO] cu care să apelăm metoda _legal(), plecând de la mutarea SAN extrasă din textul PGN al partidei.

În metoda _san_legal() pe care o descriem în continuare, mai întâi obţinem în tabloul "global" bin_moves[], lista mutărilor posibile în poziţia x88Board[] curentă:

/* mutare SAN --> coduri parţiale [FROM, TO] --> mutarea legală corespunzătoare */
_san_legal: function(SAN) {
    this._gen_moves(); // bin_moves[] = lista mutărilor posibile (codificate binar) 
    var m = ['', ''];    // câmpurile FROM-posibil şi TO 
    SAN = String(SAN);

Am convertit parametrul "SAN" (cu care este apelată metoda) la String(), fiindcă vom avea de folosit asupra valorii respective, metode proprii obiectelor String(). În fond, vom avea de apelat această metodă pentru câmpurile .SAN ale obiectelor Move() înregistrate în this.moves[] - vezi (XI) - iar apelul this._san_legal( movs[i].SAN ) - unde movs este o referinţă la this.moves[] - nu transmite valoarea proprietăţii .SAN (un String()), ci o referinţă la această variabilă.
Desigur, puteam evita conversia SAN = String(SAN), dacă presupuneam apelarea prin ._san_legal( '' + movs[i].SAN + '' ) - care converteşte în mod implicit variabila movs[i].SAN la valoare String().

Cazul când SAN reprezintă o rocadă este cel mai simplu: FROM este câmpul iniţial al regelui ('e1', respectiv 'e8'), iar TO este câmpul (specific tipului de rocadă) pe care trebuie mutat regele (desigur, turnul implicat în rocadă va fi "manevrat" de _makeMove(), dacă rocada este legală):

    if ((SAN == 'O-O-O') || (SAN == '0-0-0')) 
        return this.to_move ? 
            this._legal(['e8', 'c8']) : this._legal(['e1', 'c1']);
    if ((SAN == 'O-O') || (SAN == '0-0')) 
        return this.to_move ? 
            this._legal(['e8', 'g8']) : this._legal(['e1', 'g1']);

Dacă SAN nu este rocadă, atunci poate fi o mutare al cărei aspect este redat de aceste exemple:

a8=Q sau a8Q pionul promovează în damă (sau turn, nebun, cal)

bxa8=Q sau bxa8Q capturează şi apoi promovează pionul

f4 mutare de pion (sau de pe f3, sau de pe f2)

gxf6 mutare de pion (eventual, "en-passant") cu efect de captură

Ne2 sau Nxe2 mutare de piesă, eventual şi captură (un singur cal poate muta legal pe e2)

Nge2 sau Ngxe2 mutare de piesă, eventual şi captură (mai mulţi cai poate muta legal pe e2, dar mută cel de pe coloana 'g')

N2f4 sau N2xf4 mutare de piesă, eventual şi captură (doi cai aflaţi pe o aceeaşi coloană pot muta legal pe f4, dar mută cel aflat pe linia 2 a coloanei respective)

Ng6f4 sau Ng6xf4 (doi cai aflaţi pe o aceeaşi linie şi doi cai aflaţi pe o aceeaşi coloană pot muta legal pe f4; dezambiguizarea nu se poate face decât indicând complet câmpul de start)

Analizăm SAN începând de la sfârşit: dacă SAN se încheie cu [QRNB], precedat eventual de "=" - atunci avem o transformare de pion şi reţinem piesa în care promovează pionul, după care ştergem din SAN secvenţa respectivă (încât SAN rămâne "a8", sau "bxa8" în primele două exemple):

    var prom, mtch, piece;
    if (mtch = SAN.match(/=?[QRBN]$/)) { // dacă este mutare de transformare ("a8=Q")
        prom = SAN.charAt(SAN.length - 1); // reţine piesa în care promovează pionul
        SAN = SAN.replace(mtch, "") // rămâne "a8" (câmpul TO)
    }

Acum (după eliminarea secvenţei specifice transformării) SAN se termină în toate variantele ilustrate mai sus cu câmpul TO al mutării - îl reţinem în m[1], ştergându-l totodată din SAN; prin această ştergere, dacă SAN este o mutare de captură atunci la sfârşit rămâne caracterul "x" - îl eliminăm şi pe acesta, reţinând într-o variabilă booleană că avem "efect de captură":

    m[1] = SAN.substr(SAN.length - 2, 2); // reţine din SAN câmpul TO
    SAN = SAN.replace(/..$/, ""); // elimină TO din SAN

    var capt = false; // indică efectul de captură
    if (mtch = SAN.match(/x$/i)) { // mutare cu efect de captură?
        capt = true;
        SAN = SAN.replace(mtch, ""); // elimină "x" din SAN
    }

Să constituim în m[0], câmpul FROM-posibil pentru cazul unei mutări de transformare; coloana acestuia este caracterul rămas în SAN în cazul când există captură, sau primul caracter din m[1] (unde pusesem câmpul TO) dacă nu există şi captură; linia este 2 pentru negru şi 7 pentru alb:

    if (prom && capt) { // promovare de pion, cu efect de captură ("bxa8=Q")
        m[0] = SAN.charAt(0) + (this.to_move ? '2': '7'); // (FROM = "b7")
        m[1] += prom; //  (= "a8Q")
        return this._legal(m); // încheie prin _makeMove() dacă mutarea este legală
    } else {
        if (prom) { // promovare de pion fără efect de captură ("a8=Q")
            m[0] = m[1].charAt(0) + (this.to_move ? '2': '7'); // (FROM = "a7")
            m[1] += prom; // (= "a8Q")
            return this._legal(m); // încheie prin _makeMove() dacă mutarea este legală
        }
    }

În plus, am adăugat la sfârşitul valorii m[1] şi litera corespunzătoare piesei în care a promovat pionul - de exemplu pentru SAN = "a8Q" va rezulta m = ["a7", "a8Q"], urmând ca _makeMove() (invocată din this._legal()) să verifice dacă prin mutarea de transformare respectivă regele propriu rămâne sau nu în şah (adică dacă mutarea este sau nu, legală).

În acest moment avem în m[1] câmpul TO al mutării, iar SAN este: fie şirul vid (de exemplu, dacă iniţial SAN = "f4", atunci TO = "f4" şi după ştergere avem SAN = ''); fie un şir de un caracter, reprezentând o piesă (iniţial SAN = "Ne2"; după ştergerea lui TO rămâne SAN = "N"), sau o coloană ori o linie (SAN-iniţial = "gxf6" şi după ştergerile de "x" şi de TO, rămâne SAN = "g"); fie un şir de trei caractere reprezentând o piesă şi câmpul FROM al acesteia (pentru SAN-iniţial = Ng6xf4, după ştergerile consecutive menţionate rămâne SAN = "Ng6").

În cazul când SAN-ul rămas începe cu litera [KQRBN] asociată unei piese, determinăm valorile posibile ale câmpului FROM folosind tabloul ALL_MOVES[] (ceea ce am explicat de la început):

    // în acest punct, m[1]=TO şi SAN conţine eventual piesa şi coloana/linia/FROM
    var field, table_moves, poss_from, BOARD = this.x88Board;
    if (/^[KQRBN]/.test(SAN)) { // mutare de piesă (nu pion)
        piece = SAN.charAt(0);
        table_moves = ALL_MOVES[piece]; // tabelul tuturor mutărilor piesei
        SAN = SAN.replace(/^./, ""); // şterge piesa (primul caracter) din SAN
        if (/^[a-h][1-8]/.test(SAN)) { // când SAN-iniţial ar fi "Nf4g6" (SAN-rămas="f4")
            m[0] = SAN; 
            return this._legal(m);
        }
        if (this.to_move) piece = piece.toLowerCase();
        piece = PIECE_COD[piece];
        poss_from = table_moves[m[1]]; // FROM-posibile = ALL_MOVES[piece][TO]
        for(var i = 0, n = poss_from.length; i < n; i++) { 
            field = poss_from[i]; // un FROM posibil pentru mutarea `piece` pe TO
            if(BOARD[TO_x88[field]] == piece &&
               (!SAN || SAN == field.charAt(0) || SAN == field.charAt(1))) {
                    m[0] = field;
                    if(this._legal(m)) return true;
                }
        }
    }

Ne-a rămas un singur caz: mutările de pion obişnuite (fără transformări). Pentru cazul pionilor, constituim în prealabil (în zona variabilelor "globale" pentru widget-ul nostru) două tabele similare cu tabelele ALL_MOVES[] pe care le-am prevăzut pentru piese:

var WHITE_PAWN_FROM = {
    'a3': ['a2', 'b2'],        // pe 'a3' pionul vine sau din 'a2', sau din 'b2'
    'b3': ['b2', 'a2', 'c2'],  // SAN = "1.b3", sau SAN = "1.axb3", sau SAN = "1.cxb3" 
    // etc.
    'h3': ['h2', 'g2'],
    'a4': ['a2', 'a3', 'b3'],
    'b4': ['b2', 'b3', 'a3', 'c3'],
    // etc.
    'g7': ['g6', 'f6', 'h6'],
    'h7': ['h6', 'g6']
};
var BLACK_PAWN_FROM = {
    'a6': ['a7', 'b7'],
    'b6': ['b7', 'a7', 'c7'], // SAN = "1...b6", sau SAN = "1...axb6", sau SAN = "1...cxb6"
    // etc.
    'g2': ['g3', 'f3', 'h3'],
    'h2': ['h3', 'g3']
};

Pentru fiecare câmp al tablei, care poate fi destinaţia TO a unei mutări de pion (exceptând ultima linie - fiindcă mutările de transformare au fost tratate separat mai sus) tabelele precizează pentru alb şi respectiv pentru negru, care ar putea fi câmpurile FROM de pe care pionul poate fi mutat pe TO.

Folosind aceste tabele precalculate, putem trata cazul rămas în mod asemănător cazului mutărilor de piese de mai sus (şi scăpăm aşa, de problemele sâcâitoare pe care le-ar pune o tratare directă: găseşte coloana din stânga pionului, din dreapta, dacă există pe tabla "reală", etc.):

    poss_from = this.to_move ? BLACK_PAWN_FROM[m[1]]: WHITE_PAWN_FROM[m[1]];
    piece = this.to_move ? 3 : 2;
    var c = capt ? SAN.charAt(0) : m[1].charAt(0);
    for(var i = 0, n = poss_from.length; i < n; i++) { 
        field = poss_from[i];
        if (BOARD[TO_x88[field]] == piece && field.charAt(0) == c) {
            m[0] = field;
            if(this._legal(m)) return true;
        }
    }
    return 0 // dacă nu s-a încheiat până aici (printr-un "return" anterior),
             // atunci SAN-ul transmis este complet ilegal pentru contextul x88Board[]-curent
}, /* încheie metoda _san_legal() */

_extract_pgn() a constituit tabloul this.moves[], completând toate câmpurile prevăzute pentru mutări cu excepţia câmpului .moves[i].FEN. Acum putem înscrie şi .FEN în fiecare obiect-mutare din moves[] - apelând _san_legal(moves[i].SAN) şi folosind ._getFEN() pentru poziţia x88Board[] actualizată odată cu verificarea legalitaţii mutării, de către _makeMove().

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