momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Modelarea tablei şi jocului de şah (XIII)

javaScript | reprezentare 0x88
2012 jul

Pentru a genera lista mutărilor legale trebuie să vedem întâi cum se mută piesele în reprezentarea 0x88 adoptată aici (aceeaşi problemă se pune pentru orice altă reprezentare posibilă). O aplicaţie imediată (şi importantă, pentru generarea mutărilor legale) constă în realizarea unei funcţii care să indice dacă un anumit câmp este sau nu, atacat de partea adversă.

Calculul traiectoriilor în reprezentarea 0x88

Dacă sq este indexul unui câmp de pe tabla "reală" a tabloului x88Board[], atunci sq+1 este indexul câmpului din dreapta, iar sq-1 al celui din stânga; sq+16 este indexul câmpului de deasupra, iar sq-16 al celui dedesubt:

Putem avea ca excepţie câmpurile marginale; de exemplu, pentru sq = 7716 (indexul câmpului 'h8') avem sq+1 = 7816 şi câmpul vizat este în afara tablei "reale". Amintim că sq & 0x88 este zero numai dacă sq vizează un câmp "real".

De exemplu - fiindcă nebunul se poate deplasa numai pe diagonale, indecşii câmpurilor pe care poate muta un nebun se vor obţine adunând ±15 sau ±17 la indexul câmpului curent şi putem scrie astfel o funcţie care să returneze tabloul acestor câmpuri:

function moveBishop(square) {
    var STEP = [15, -15, 17, -17], to_sq = []; 
    for(var i = 0, n = STEP.length; i < n; i++) 
        for(var sq = square; !(sq & 0x88); sq += STEP[i])
            to_sq.push(sq); // sq.toString(16)
    return to_sq; 
}; // câmpurile accesibile nebunului de pe 'square'
alert( moveBishop(0x36) );

Alăturat, am redat (în hexazecimal) rezultatul apelului moveBishop(0x36) - mutările posibile ale nebunului aflat pe câmpul g4 (de coordonate: linia 3 şi coloana 6); '*' marchează prelungirile diagonalelor în afara tablei "reale" (cu indecşi care stopează ciclul "for" interior, în funcţia redată).

În mod analog se pot scrie funcţii pentru mutările posibile ale calului, turnului, etc. Să observăm însă că tabloul furnizat va conţine şi câmpul 'square' pe care se află piesa (şi încă de atâtea ori câte valori are tabloul STEP) - fiindcă to_sq.push(sq) se execută începând cu var sq = square; (reluând pentru fiecare valoare STEP, când la iteraţia curentă se depăşesc limitele tablei "reale"). O corectare banală ar implica un test prealabil if(sq != square) to_sq.push(sq), care însă ar fi executat pentru fiecare sq; corectarea preferabilă se bazează pe reformularea ciclului interior folosind "while", în loc de "for" (cum vom vedea în funcţia _isAttacked(), mai jos).

Ţinând seama de regula evidenţiată mai sus pentru calculul indexului câmpului vecin (în sus, în jos, la stânga, la dreapta, sau diagonal), instituim următoarele variabile (în exteriorul widget-ului), care ne vor servi pentru gestionarea mutărilor pieselor:

// deplasamente de index în x88Board[] pentru mutările pieselor
var STEP_r = [-16, -1, 1, 16];                     // turn
var STEP_b = [-17, -15, 15, 17];                   // nebun
var STEP_k = [-17, -16, -15, -1, 1, 15, 16, 17];   // rege
var STEP_n = [-33, -31, -18, -14, 14, 18, 31, 33]; // cal

Pentru cazul damei - putem reuni STEP_r cu STEP_b (fiindcă dama se mişcă şi ca turn şi ca nebun). Pentru pion - nu-i cazul să considerăm un tablou "STEP", fiindcă mişcarea pionului depinde de culoare (cel alb avansează cu +16, cel negru cu -16), după cum depinde şi de linia lui (de pe linia 2, respectiv de pe linia 7 - poate avansa cu +16 sau cu +32, respectiv cu -16 sau -32), iar în cazul unei capturi diagonale, depinde şi de contextul "en-passant".

Câmp aflat sub atacul direct al unei piese adverse

Am văzut mai sus cum putem determina tabloul câmpurilor pe care ar putea muta o piesă - altfel spus, tabloul câmpurilor atacate de piesa respectivă - dar numai în contextul fictiv al unei table pe care s-ar afla numai piesa respectivă. De fapt, o piesă nu poate muta pe un câmp ocupat de o piesă proprie; ciclul interior din funcţia redată mai sus ar trebui stopat nu numai când se ating limitele tablei "reale", dar şi dacă sq-curent este ocupat de o piesă proprie.

Mai mult, poziţia regelui propriu în corelaţie cu poziţiile pieselor adverse, poate determina noi restricţii asupra câmpurilor pe care poate muta o piesă sau alta; dacă prin mutarea respectivă, regele ar rămâne în şah (câmpul pe care se află fiind atacat direct de o piesă adversă), atunci mutarea devine imposibilă. În plus, regele nu poate muta pe un câmp atacat (direct, fără a avea o piesă "acoperitoare" pe traiectorie) de o piesă adversă şi deasemenea, pentru a efectua o rocadă - regele nu poate trece peste câmpuri atacate de către adversar.

Prin urmare, dacă vrem să determinăm mutările legale ale unei piese (într-un context real de joc, nu cel fictiv al funcţiei de mai sus) - trebuie să implicăm starea curentă x88Board[] (absent în "contextul fictiv" evocat) şi ne-ar trebui în general, o funcţie care să testeze dacă un anumit câmp este sau nu atacat de o piesă adversă:

/* este câmpul de index SQ atacat de o piesă a adversarului 'side'?  */
_isAttacked: function(SQ, side) { // side = 0 / 1, pentru alb / negru 
    var sq1, dir, BOARD = this.x88Board;
    var knight = 4, rook = 10, queen = 12, bishop = 8, king = 6; // alb
    /* este SQ atacat de către un Pion advers? */
    if (!side) { // SQ atacat de pion alb: de pe SQ-15, sau de pe SQ-17
        sq1 = SQ - 15;
        if (!(sq1 & 0x88) && (BOARD[sq1] == 2)) 
            return 1;
        sq1 -= 2;
        if (!(sq1 & 0x88) && (BOARD[sq1] == 2)) 
            return 1
    } else { // SQ atacat de pion negru: de pe SQ+15, sau de pe SQ+17
        sq1 = SQ + 15;
        if (!(sq1 & 0x88) && (BOARD[sq1] == 3)) 
            return 1;
        sq1 += 2;
        if (!(sq1 & 0x88) && (BOARD[sq1] == 3)) 
            return 1;
        knight++; rook++; queen++; // 'side' fiind în acest caz Albul,
        bishop++; king++; // comută pe negru piesele atacatoare
    }
    /* este SQ atacat de un cal advers, sau de regele advers? */
    for (dir = 0; dir < 8; dir++) {
        sq1 = SQ + STEP_n[dir];
        if (!(sq1 & 0x88) && (BOARD[sq1] == knight)) 
            return 1;
        sq1 = SQ + STEP_k[dir];
        if (!(sq1 & 0x88) && (BOARD[sq1] == king)) 
            return 1
    }
    /* este SQ atacat de turn, damă sau nebun advers? */
    for (dir = 0; dir < 4; dir++) {
        var step = STEP_r[dir];
        sq1 = SQ + step;
        while (!(sq1 & 0x88)) {
            var p = BOARD[sq1];
            if (p > 0) {
                if ((p == rook) || (p == queen)) return 1;
                break
            }
            sq1 += step
        }
        step = STEP_b[dir];
        sq1 = SQ + step;
        while (!(sq1 & 0x88)) {
            var p = BOARD[sq1];
            if (p > 0) {
                if ((p == bishop) || (p == queen)) return 1;
                break
            }
            sq1 += step
        }
    }
    return 0 // câmpul SQ nu este atacat de către adversar
},

Ca exemplu, să presupunem că albul este la mutare (adică, în termenii pe care i-am introdus, avem this.to_move == 0) şi că nu a pierdut dreptul de a face rocada mică (adică avem this.castle & 1 !== 0); această mutare - notată SAN prin O-O - este legală dacă:
    - regele nu este în şah: !this._isAttacked(4, 1) ('e1', de index 0416, nu este atacat de negru);
    - câmpurile 'f1' şi 'g1' sunt libere: !(this.x88Board[5] || this.x88Board[6]);
    - câmpurile 'f1' şi 'g1' nu sunt atacate: !(this._isAttacked(5, 1) || this._isAttacked(6, 1)).
Analog pentru O-O-O albă şi deasemenea, pentru cazul rocadelor negrului.

Încă un exemplu de folosire a funcţiei _isAttacked(), în cadrul "generatorului de mutări" pe care urmează să-l scriem: regele părţii care se află la mutare poate să mute pe câmpul liber SQ1, dacă !this._isAttacked(SQ1,this.to_move ^ 1), unde ^ este operatorul "XOR" (permiţând aici indicarea părţii adverse celeia indicate de .to_move).

vezi Cărţile mele (de programare)

docerpro | Prev | Next