În (XIII) am introdus patru variabile STEP_* conţinând deplasamentele indexului mutărilor de turn, nebun, cal, sau rege. Pentru cazul când piesa nu este nominalizată - fiind o valoare posibilă a unei anumite variabile, setate în cursul execuţiei - prevedem şi variabila:
var STEP = { 6 : [-17, -16, -15, -1, 1, 15, 16, 17], // STEP_k 12 : [-17, -16, -15, -1, 1, 15, 16, 17], // deplasamentele damei 10 : [-16, -1, 1, 16], // STEP_r 8 : [-17, -15, 15, 17], // STEP_b 4 : [-33, -31, -18, -14, 14, 18, 31, 33] // STEP_n /* adaugă eventual şi pentru piesele negre (7, 13, 11, 9, 5) */ };
Am considerat aici numai piesele albe; dacă Piece este piesa vizată curent, atunci STEP[ Piece - this.to_move ] este tabloul deplasamentelor corespunzătoare ei (.to_move este 0 pentru alb şi 1 pentru negru). Desigur, operaţia suplimentară necesară pentru acces (reducerea la codul piesei albe) ar fi evitată, dacă am extinde STEP[] şi pentru piesele negre (dar "câştigul" ar fi nesemnificativ).
Un "generator de mutări" se scrie de obicei compunând funcţii separate: una pentru mutările de pion, altele pentru generarea mutărilor pieselor - ba chiar separând şi după culoare (câte un generator pentru diversele categorii de mutări ale albului, respectiv ale negrului).
În schimb, metoda _gen_moves() pe care o vom reda aici este una "monolitică" (vezi PGN-browser); procedând însă didactic-intuitiv (şi regândind lucrurile), o vom reda aici "pe bucăţi" semnificative (folosind indentarea, pentru a sugera legătura dintre bucăţile de cod succesive). Astfel redată - şi cu atâtea comentarii - ea poate părea foarte lungă; însă în forma obişnuită ea are sub 150 de linii (sub 200, dacă adăugăm şi liniile de la _isAttacked(), pe care o invocă în cazul mutărilor de rocadă) - ceea ce este chiar onorabil, pentru un generator de mutări bazat pe reprezentarea 0x88.
Adăugăm în widget-ul pe care l-am dezvoltat în părţile anterioare ale acestui studiu, metoda:
/* Lista mutărilor posibile pentru partea la mutare în poziţia BOARD[] curentă */ _gen_moves: function(moves) { var ocsq = []; // câmpurile ocupate de piesele părţii aflate la mutare var /* scurtături către unele variabile interne */ to_move = this.to_move, castle = this.castle, BOARD = this.x88Board, en_pass = this.en_pass; for (var i = 0; i < 120; i++) if ( !(i & 0x88) && // câmp al tablei "reale" BOARD[i] && // ocupat de o piesă ((BOARD[i] & 1) == to_move)) // aparţinând părţii aflate la mutare ocsq.push(i);
Variabilele interne this.castle, etc. pentru care am creat "scurtături" mai sus, au fost înfiinţate la iniţializarea infrastructurii BOARD (vezi metoda _setBOARD(), (XII)).
ocsq[] conţine indecşii câmpurilor ocupate de piesele părţii aflate la mutare (indecşii 120..127 vizează câmpuri dinafara tablei "reale", încât am limitat "for" până la 120).
Condiţia ((BOARD[i] & 1) == to_move)) poate fi scrisă mai simplu !(BOARD[i] & 1 ^ to_move).
Mai departe, în cadrul metodei iniţiate mai sus urmează: o secvenţă de cod pentru generarea mutărilor "rocadă" (pentru alb şi respectiv, pentru negru - la execuţie fiind aleasă aceea care corespunde valorii curente .to_move); o secvenţă de cod pentru generarea mutărilor posibile pentru pioni (pentru alb şi respectiv, pentru negru) şi apoi, cea care generează mutările pieselor.
Mutările vor fi înscrise în tabloul extern referit de parametrul de apel moves. Pentru codificarea mutărilor (ca întregi pe 32 biţi) - trebuie văzut (XIV).
this.castle indică drepturile de rocadă rămase, rezervând pentru alb primii doi biţi şi pentru negru - următorii doi biţi. Deci o rocadă albă este posibilă dacă (în primul rând) rezultatul mascării valorii castle cu 112 = 3 este nenul; analog pentru rocada neagră, masca fiind 11002 = 0x0C.
În al doilea rând - trebuie verificat că regele nu se află în şah, iar câmpurile dintre rege şi turn sunt libere şi sunt neatacate de către vreo piesă adversă (metoda _isAttacked() este redată în (XIII)):
/* Generează mutările "rocadă" pentru alb, respectiv pentru negru */
if (!to_move) { // Albul este la mutare; E1 = 4, G1 = 6, C1 = 2
if ((castle & 3) && !this._isAttacked(4, 1)) { // albul poate roca
if ( (castle & 1) && // O-O este posibilă
!( BOARD[5] || BOARD[6] // câmpuri libere între rege şi turn
|| this._isAttacked(5, 1) // şi neatacate de negru
|| this._isAttacked(6, 1)))
moves.push(0x01040660); // O-O este legală (pentru alb)
if ((castle & 2) && !( BOARD[3] || BOARD[2] || BOARD[1]
|| this._isAttacked(3, 1)
|| this._isAttacked(2, 1)))
moves.push(0x02040260); // O-O-O este legală
}
} else { // Negrul la mutare; E8 = 0x74, G8 = 0x76, C8 = 0x71
if ((castle & 0x0C) && !this._isAttacked(0x74, 0)) { // negrul poate roca
if ((castle & 4) && !( BOARD[0x75] || BOARD[0x76]
|| this._isAttacked(0x75, 0)
|| this._isAttacked(0x76, 0)))
moves.push(0x01747670); // O-O este legală (pentru negru)
if ((castle & 8) && !( BOARD[0x73] || BOARD[0x72] || BOARD[0x71]
|| this._isAttacked(0x73, 0)
|| this._isAttacked(0x72, 0)))
moves.push(0x02747270); // O-O-O este legală
}
}
"Riguros" vorbind (dar numai pentru acest moment al dezvoltării) - ne-a scăpat ceva: am verificat că 'e1' (respectiv 'e8') este neatacat de vreo piesă adversă, dar… nu am verificat şi faptul că pe 'e1' (respectiv, pe 'e8') există ca piesă chiar regele alb (respectiv, cel negru)…
Însă această verificare este deja acoperită de castle, care trebuie să indice drepturile de rocadă rămase; în cursul metodei _makeMove() (de care ne vom ocupa mai târziu), imediat ce regele sau un turn este mutat (inclusiv, printr-o rocadă), urmează şi modificarea corespunzătoare a lui castle (resetând biţii de rocadă ai părţii respective).
În principiu, variabilele interne considerate (this.castle, this.en-pass, etc.) sunt definite şi iniţializate în _setBOARD(), sunt actualizate în _makeMove() şi servesc (prin valorile actuale) pentru stabilirea legalităţii mutărilor, în cursul metodei _gen_moves().
Aceste variabile (tradiţionale în programele de şah) ar putea fi "reunite" într-un singur întreg de 32 biţi (castle de exemplu, măsoară doar 4 biţi!), urmând să separăm după caz câmpurile necesare…
Mai departe în _gen_moves() urmează să generăm şi celelalte mutări posibile:
/* Generează mutările de pion, apoi şi mutările pieselor */
for (var i = 0, np = ocsq.length; i < np; i++) {
var sq = ocsq[i];
var p = BOARD[sq];
Anume, urmează să generăm mutările posibile ale piesei p, aflate pe câmpul de index sq - repetând aceasta de-a lungul întregului tablou ocsq (care vizează piesele părţii aflate la mutare).
Avem de subliniat că generăm aici mutările posibile (nu neapărat şi legale). Secvenţa redată mai sus pentru generarea rocadelor asigură ea însăşi (folosind _isAttacked()), că rocadele generate sunt legale - dar pentru mutările pe care urmează să le generăm nu vom mai verifica dacă nu cumva regele propriu rămâne în şah, după efectuarea mutării (deci de fapt, mutarea este ilegală).
Această verificare este lăsată în sarcina metodei _makeMove() şi este mai bine aşa: proporţia mutărilor care ar lăsa regele în şah este de obicei, foarte mică în raport cu numărul de mutări posibile - încât este firesc să generăm rapid (fără a mai apela _isAttaked()) mutările posibile, urmând ca testarea finală de legalitate să se facă în momentul când mutarea respectivă ar trebui eventual să fie şi efectuată pe tablă (ceea ce se petrece în _makeMove()).
Generăm mutările posibile ale pionului în această ordine: mutările de avansare, eventual cu efect de transformare; apoi, mutările cu efect de captură laterală (inclusiv, "en-passant").
Redăm întâi (şi mai detaliat) cazul când albul este la mutare, piesa curentă p fiind un pion.
Dacă pionul nu a ajuns pe linia a 7-a (deci indexul câmpului său nu depăşeşte 0x60), atunci el poate avansa pe câmpul din faţă (dacă acesta este liber); iar dacă pionul se află pe linia 2 (adică nu a făcut anterior nici o mutare), atunci el poate avansa şi cu două câmpuri (dacă sunt libere):
if (p == (2 | to_move)) { // 2 pentru pion Alb, 3 pentru Negru
/* Mutările de pion ale părţii aflate la mutare */
if (!to_move) { /* Albul este la mutare */
if (sq < 0x60) { // pionul nu este pe linia 7
if (!BOARD[sq + 16]) { // câmpul din faţă este liber
moves.push(
0x06000020 | (((sq << 8) | (sq + 16)) << 8)) // d3-d4
}
if ( (sq < 0x18) && // pionul este pe linia 2
!BOARD[sq + 16] && // câmpul din faţă este liber şi
!BOARD[sq + 32]) { // câmpul din faţa acestuia este liber
moves.push(
0x0E000020 | (((sq << 8) | (sq + 32)) << 8)) // d2-d4
}
}
Acum, dacă pionul este pe linia a 7-a şi câmpul din faţa sa este liber - atunci pionul poate avansa şi urmează să fie transformat în damă, rege, nebun sau cal (şi adăugăm 4 mutări posibile):
else { // pionul este pe linia 7; pe câmpul din faţă avem 4 transformări
if (!BOARD[sq + 16]) { // câmpul din faţă este liber
var frto = ((sq << 8) | (sq + 16)) << 8; // combină FROM şi TO
moves.push(0x0C000020 | frto, // d7-d8 = Q (transformă în damă)
0x0A000020 | frto, // d7-d8 = R
0x08000020 | frto, // d7-d8 = B
0x04000020 | frto) // d7-d8 = N
}
}
Pentru capturile cu pionul (spre stânga şi spre dreapta) trebuie să verificăm întâi dacă nu se iese înafara tablei (de exemplu, un pion alb de pe coloana 'h' nu poate captura la dreapta).
Apoi, trebuie să vedem dacă nu cumva câmpul pe care se face captura este exact cel indicat în momentul respectiv de this.en-pass - aceasta ar însemna că mutarea precedentă (a adversarului) a fost înaintarea cu două câmpuri a unui pion negru aflat pe coloana pe care se face acum captura, deci avem de înscris ca posibilă mutarea "en-passant" corespunzătoare - şi observăm că nu este necesar să mai verificăm că pionul alb este pe linia 5 (fiindcă numai de pe linia 5, pionul alb poate accesa câmpul care tocmai a fost înscris în "en-pass"). Gestionarea în acest fel a variabilei .en-pass este realizată iarăşi prin _makeMove().
Dacă nu este cazul "en-passant", atunci trebuie să vedem dacă pe câmpul de captură se află o piesă neagră şi dacă este aşa - atunci adăugăm ca posibilă mutarea de captură corespunzatoare; desigur, daca pionul alb este pe linia a 7-a, atunci avem de adăugat chiar 4 mutări de captură, incluzând şi transformările posibile:
for (var j = 15; j <= 17; j += 2) { // captură la stânga şi la dreapta
var sq1 = sq + j;
if (! (sq1 & 0x88)) { // Nu iese înafara tablei "reale"
var p1 = BOARD[sq1];
if (this.en_pass == sq1) { // captură "en-passant" (d5xf6 ep)
moves.push(
0x0F000023 | (((sq << 8) | sq1) << 8))
} else if (p1 & 1) { // piesă sau pion Negru
if (sq >= 0x60) { // captură cu transformare (pe linia 8)
var frto = ((sq << 8) | sq1) << 8;
moves.push(0x0C000020 | frto | p1, // d7 x c8 = Q
0x0A000020 | frto | p1, // d7 x c8 = R
0x08000020 | frto | p1, // d7 x c8 = B
0x04000020 | frto | p1) // d7 x c8 = N
} else { // captură obişnuită (d3 x e4)
moves.push(
0x06000020 | (((sq << 8) | sq1) << 8) | p1)
}
}
}
} /* încheie generarea capturilor cu pion alb */
} /* încheie generarea mutărilor pionilor pentru Alb */
Pentru cazul când negrul este la mutare (şi p este un pion negru) avem o tratare similară, inversând sensul avansării pionului (acum deplasamentele vor fi negative); redăm şi această secvenţă, acum într-un singur bloc de cod:
else { /* Negrul mută (pion negru, p = 3) */
if (sq >= 0x20) { // pionul nu este pe linia 2
if (!BOARD[sq - 16]) { // câmpul din faţă este liber
moves.push(
0x06000030 | (((sq << 8) | (sq - 16)) << 8)) // d7-d6
}
if ( (sq >= 0x60) && // pionul este pe linia 7
!BOARD[sq - 16] && // câmpul din faţă este liber şi
!BOARD[sq - 32]) { // câmpul din faţa acestuia este liber
moves.push(
0x0E000030 | (((sq << 8) | (sq - 32)) << 8)) // d7-d5
}
} else { // pionul este pe linia 2; pe câmpul din faţă avem 4 transformări
if (!BOARD[sq - 16]) { // câmpul din faţă este liber
var frto = ((sq << 8) | (sq - 16)) << 8;
moves.push(0x0D000030 | frto, // d2-d1 = Q (damă neagră)
0x0B000030 | frto, // d2-d1 = R
0x09000030 | frto, // d2-d1 = B
0x05000030 | frto) // d1-d1 = N
}
}
for (var j = 15; j <= 17; j += 2) { // captură la stânga şi la dreapta
var sq1 = sq - j;
if (! (sq1 & 0x88)) {
var p1 = BOARD[sq1];
if (en_pass == sq1) { // captură "en-passant" (d4xe3 ep)
moves.push(0x0F000032 | (((sq << 8) | sq1) << 8))
} else if ((p1 > 0) && !(p1 & 1)) {
if (sq < 0x20) { // captură şi transformare
var frto = ((sq << 8) | sq1) << 8;
moves.push(
0x0D000030 | frto | p1, // d2 x c1 = Q (damă neagră)
0x0B000030 | frto | p1, // d2 x c1 = R
0x09000030 | frto | p1, // d2 x c1 = B
0x05000030 | frto | p1) // d2 x c1 = N
} else { // captură obişnuită (d6 x e5)
moves.push(
0x06000030 | (((sq << 8) | sq1) << 8) | p1)
}
}
}
} /* încheie generarea mutărilor pionilor pentru Negru */
} /* încheie generarea mutărilor de pion pentru Alb şi pentru Negru */
Desigur, ar fi cazul să şi testăm aceste secvenţe de cod; nu mai indicăm aici, cum anume am putea testa lucrurile în acest moment - mai târziu vom aborda direct şi chestiunea testării globale a generatorului de mutări ("mai târziu" pentru că avem nevoie şi de _makeMove(), întrucât testarea vizează mutările legale).
În cazul pieselor, codul este unitar şi mai scurt (fiindcă deplasamentele pieselor nu depind de culoare, spre deosebire de cele pentru pioni). Pentru fiecare dintre deplasamentele indicate de STEP[] pentru piesa respectivă, se testează dacă la acel deplasament corespunde un câmp liber şi în acest caz se generează mutarea (exceptând cazul când p este regele şi câmpul pe care ar fi mutat este atacat de adversar); iar dacă pe câmpul vizat prin deplasamentul respectiv se află o piesă adversă, atunci se generează mutarea cu captură corespunzătoare.
Dar după generarea acestei mutări, se trece imediat la următorul deplasament numai în cazul când p este cal sau rege; celelalte piese (nebun, turn sau damă) pot glisa mai departe pe traiectoria dată de deplasamentul curent, încât sunt generate şi mutările care ar rezulta angajându-l din nou pe acesta (încheind şi abia atunci trecând la următorul deplasament, când se ajunge la un câmp ocupat de o piesă proprie, sau când traiectoria curentă iese de pe tabla "reală"):
else { /* Mutări ale pieselor (p este acum o piesă, nu pion) */
var ofdir = STEP[p - to_move]; // deplasamentele acelei piese
for (var d = 0, nd = ofdir.length; d < nd; d++) {
var sq1 = sq;
for (;;) { // se va ieşi din ciclu prin 'break'
sq1 += ofdir[d]; // va continua pe direcţia respectivă,
// pentru Nebun, Turn, sau Damă
if (sq1 & 0x88) break; // TO este înafara tablei "reale"
if ((p == (6 | to_move)) // se mută regele pe un câmp atacat?
&& this._isAttacked(sq1, to_move ^ 1)) break;
var p1 = BOARD[sq1];
if (!p1) { // mută pe un câmp liber
moves.push(
0x03000000 | (((sq << 8) | sq1) << 8) | (p << 4))
} else {
if ((!to_move && (p1 & 1))
|| (to_move && !(p1 & 1))) { // mutare cu captură
moves.push(
0x07000000 | (((sq << 8) | sq1) << 8)
| ((p << 4) | p1));
break
} else break
}
if (!(p & 8)) break // p nu este Nebun, Turn, sau Damă
}
}
} // încheie generarea mutărilor pieselor
} // încheie ciclul for (var i = 0, np = ocsq.length; i < np; i++) {
}, // încheie _gen_moves()
Dacă ne-am apuca să testăm - ar trebui să rezulte maximum 8 mutări pentru cal sau rege şi maximum 27 de mutări posibile pentru o damă. Dar chiar vom face aceasta mai departe - imaginând o funcţie care să folosească _gen_moves() pentru a furniza pentru fiecare piesă sau pion, tabele conţinând câmpurile pe care poate muta piesa respectivă plecând din fiecare câmp al tablei.
De exemplu, tabela mutărilor nebunului va trebui să arate cam aşa:
var Bishop_Moves = { 'a1': ['b2', 'c3', 'd4', 'e5', 'f6', 'g7', 'h8'], // unde poate muta nebunul din 'a1' // ş.a.m.d. 'c3': ['a1', 'b2', 'd4', 'e5', 'f6', 'g7', 'h8', 'e1', 'd2', 'b4', 'a5'], // ş.a.m.d. 'h8': ['a1', 'b2', 'c3', 'd4', 'e5', 'f6', 'g7'] // unde poate muta nebunul din 'h8' };
Iar tabelele obţinute astfel vor servi ulterior pentru simplificarea conversiei de la formatul SAN al mutării (din textul PGN al partidei), la forma binară internă specifică infrastructurii BOARD; după această conversie, mutarea va fi pasată metodei _makeMove(), care va încheia verificarea legalităţii mutării (şi va efectua mutarea pe BOARD[], dacă ea este legală).
vezi Cărţile mele (de programare)