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

Modelarea tablei şi jocului de şah (X)

PGN | javaScript | perl | regexp
2012 jul

În precedentele nouă părţi ale acestui studiu elementar, ne-am ocupat de crearea infrastructurii DOM + CSS pentru un widget a cărui intenţie finală este aceea de a permite parcurgerea în browser a unei partide de şah. În părţile următoare ne ocupăm de reprezentarea standard pentru partidă de şah, abordând şi elementele necesare de modelare a jocului de şah.

Infrastructura unitară DOM + CSS creată anterior are la bază un set de sprite-uri de piese de şah. CSS defineşte dimensiunile specifice fiecărui sprite (pentru piesă, câmp şi tabla de şah) şi defineşte independent de sprite (folosind procente) criteriile de poziţionare pe tablă a câmpurilor şi pieselor. DOM-ul creat constă dintr-un număr de diviziuni - pentru tabla de şah cu cele 64 de câmpuri ale ei, pentru etichete de linii şi coloane, bara de navigare, lista mutărilor, etc. - şi totodată, un anumit număr de handlere asociate (pe butoanele de navigare, pe lista mutărilor, etc.).

Sprite-urile şi parţial, fişierul CSS - au putut fi create în mod automat (prin scripturi Bash). DOM-ul este constituit "inline" (în cursul metodei _create()), la instanţierea widget-ului.

Premisele finalizării widget-ului

Pentru a definitiva lucrurile (conform "intenţiei finale" tocmai amintite), trebuie acum să modelăm acest scenariu: preia (din elementul <textarea> pe care s-a instanţiat widget-ul) textul unei partide de şah; analizează acest text, extrăgând informaţiile despre partidă (cine cu cine joacă, la ce dată, cu ce rezultat, etc.) precum şi lista mutărilor efectuate.

Bineînţeles (în primul rând) că acest scenariu trebuie regizat după crearea infrastructurii DOM (operată de _create(), în momentul instanţierii widget-ului) - deci în cursul metodei _init().

Apoi (ca de obicei când se preiau date introduse de utilizator) trebuie verificat că input-ul respectiv este textul unei "partide de şah" şi nimic altceva. În scopul acestei verificări va trebui să avem în vedere un format standard pentru reprezentarea textuală a partidelor de şah - PGN.

În sfârşit, trebuie să avem în vedere ca, înainte de a înscrie mutările (preluate din textul partidei) în diviziunea constituită în DOM pentru "lista mutărilor" - să ne asigurăm că aceste mutări sunt legale.

Verificarea legalităţii mutărilor presupune neapărat să cunoaştem regulile jocului de şah (ceea ce n-a fost necesar în părţile anterioare). În principal este vorba de regulile de mutare specifice fiecărui tip de piesă - inclusiv mutarea "en-passant" şi mutările de tip "transformare" pentru pioni, mutările de tip "rocadă" - şi desigur, de reguli privitoare la poziţia de "şah", de "mat" sau de "remiză".

Mecanismul prin care se verifică legalitatea mutării curente - câtă vreme nu inventăm altceva - este unul tipic (fiind folosit în majoritatea programelor de şah): se generează o listă a tuturor mutărilor legale posibile în poziţia curentă, pentru partea care este la mutare; dacă mutarea indicată se găseşte în această listă, atunci rezultă că acea mutare este legală.

Pentru a fi eficient, acest mecanism implică o reprezentare specială (binară) a tablei de şah şi a poziţiei, dublând reprezentarea DOM constituită anterior (şi "dublând" reprezentarea textuală a mutărilor); ca urmare, vor fi necesare anumite secvenţe de cod pentru conversii şi legături între aceste reprezentări.

Vom folosi aici o astfel de "reprezentare specială" (vizând astfel şi "modelarea jocului de şah", cum specifică titlul comun al acestor prezentări). Dar de fapt, acest mecanism este absolut firesc pentru un chess engine, când se pune problema de a găsi o mutare cât mai bună în lista celor posibile; el se poate folosi şi în cadrul unui PGN-browser - fiind totuşi "prea tare" în acest caz, când se are în vedere doar mutarea curent citită (fără nicio sarcină de alegere) - încât generarea tuturor mutărilor este acum un mic lux, faţă de ce ar putea fi suficient pentru stabilirea legalităţii acelei mutări.

Construcţia unui şablon pentru tagurile PGN

Formatul standard de reprezentare textuală a partidelor de şah este PGN (introdus de Steven J. Edwards în 1994). Pentru baze de date cu milioane de partide de şah şi numeroase criterii de organizare se folosesc şi formate de reprezentare binară (vezi ChessBase Database programs).

Formatul PGN conţine o secţiune informativă, urmată de lista mutărilor; se pot concatena mai multe partide într-un fişier text, având extensia standard .pgn.

Secţiunea informativă ar fi importantă dacă am avea de rezolvat cereri asupra partidelor dintr-un fişier .pgn (de exemplu, "lista partidelor care aparţin cutărui jucător"). Dar aici avem în vedere o singură partidă, iar antetul ei serveşte cel mult pentru a constitui conţinutul diviziunii .GameInfo (şi eventual, pentru a seta poziţia iniţială, dacă este specificată în antetul respectiv); este firesc atunci, să permitem şi cazul (incorect pentru PGN) când antetul este omis, permiţând "browsarea" şi pentru o partidă ad-hoc (care conţine numai lista mutărilor).

Antetul este constituit din "taguri PGN", cu sintaxa: [Cheie "Valoare"] (unde parantezele pătrate, spaţiul separator după Cheie şi ghilimelele care încadrează Valoare sunt toate, obligatorii):

[White "alexo 99"] [Black "vlad.bazon"] [Event "InstantChess"]
[WhiteElo "1936"] [BlackElo "2038"] [Result "0-1"]

Să construim treptat o expresie regulată care să identifice în textul PGN toate tagurile (şi numai pe acestea). Primul caracter dintr-un tag PGN este "[" - deci şablonul trebuie să înceapă cu \[ (prefixul "\" schimbă semnificaţia unui anumit caracter: "[" are prestabilită semnificaţia de constructor de "clasă de caractere" şi aici, "\[" îi redă semnificaţia de caracter obişnuit).

Urmează numita mai sus Cheie, constând dintr-o secvenţă nevidă de caractere alfanumerice - deci adăugăm în şablon \w+ (acum "\" eludează semnificaţia de literă "w", rezultând semnificaţia de caracter posibil într-un "word" - adică literă, cifră sau "_"; iar + înseamnă "cel puţin o apariţie").

Urmează unul sau poate mai multe spaţii, pentru care şablonul este \s+. Până acum, şablonul este: /\[\w+\s+/ (unde slash-urile - iniţial şi final - joacă rolul de "constructor" de expresii regulate).

Mai departe, urmează ghilimele, Valoare, ghilimele şi în final ]. Aici, Valoare poate conţine orice caracter (nu numai \w), cu excepţia caracterului " încât şablonul potrivit pentru Valoare este [^"]* (unde * înseamnă zero sau mai multe apariţii, iar [^"] desemnează orice caracter diferit de "). Implicit, avem în vedere şi taguri "vide" (de forma Cheie "").

Prin urmare, şablonul căutat este \[\w+\s+"[^"]*"\]. El va permite extragerea primului tag din textul PGN; pentru a extinde căutarea pe întregul text PGN, trebuie să adăugăm constructorului specificatorul g (de la "global"), obţinând forma finală /\[\w+\s+"[^"]*"\]/g>.

Extinzând "pe întregul text", vom găsi eventual şi secvenţe de tipul respectiv care de fapt nu sunt taguri PGN: astfel de secvenţe pot exista şi în interiorul unora dintre comentariile existente în lista mutărilor; dar acest caz este absolut netipic pentru PGN şi este preferabil să-l ignorăm.

Pentru o verificare expeditivă, alegem să folosim perl. Copiem un text PGN într-o construcţie heredoc pentru o variabilă $PGN, apoi folosim operatorul =~ pentru a găsi (în tabloul @tags) potrivirile între şirul $PGN şi şablonul nostru:

$PGN = <<PGN;
[White   "alexo 99"]
[Black "vlad.bazon"]
[Event "InstantChess"]
[WhiteElo "1936"]
[BlackElo "2038"]
[Result "0-1"]
[ICCause "2"]
[ICEcause   "3"]

1.d4 Nf6 2.Bf4 c5 {comentariu [xxx "xxx"]} 3.e3 Qb6 
4.b3 cxd4 5.exd4 Nc6 6.Nf3 Nd5 7.Be3 Nxe3 8.fxe3 e5 9.Bc4 d5 10.Be2 Be7 11.O-O O-O 
12.h3 Be6 13.c3 Rac8 14.Nbd2 e4 15.Nh2 Bg5 16.Ng4 f5 17.Nh2 Bxe3+ 18.Kh1 Nxd4 
19.cxd4 Qxd4 20.Nhf3 exf3 21.Nxf3 Qf6 22.Bd3 f4 23.Nh2 Qg5 24.Ng4 Bc5 25.Qf3 h5 
26.Nh2 Be3 27.Qe2 Qh6 28.Nf3 g5 29.Ne5 g4 30.h4 Bf5 31.Rad1 Qf6 32.Bxf5 Qxh4#  0-1
PGN

@tags = $PGN =~ /\[\w+\s+"[^"]*"\]/g;
print "@tags\n";

Executând programul, se afişează tagurile extrase din şirul $PGN prin şablonul respectiv:

vb@vb:~$ perl test.pl
[White   "alexo 99"] [Black "vlad.bazon"] [Event "InstantChess"] [WhiteElo "1936"]
[BlackElo "2038"] [Result "0-1"] [ICCause "2"] [ICEcause   "3"] [xxx "xxx"]
vb@vb:~$

Observăm că s-a extras inclusiv "tagul" din comentariul artificial dinaintea mutării 3.

Faptul că am folosit Perl pentru acest mic experiment nu este întâmplător: javaScript, PHP, Python, etc. au adoptat pentru expresiile regulate sintaxa introdusă de Perl.

Extragerea antetului PGN

Instituim în _init() un obiect intern this.tags = {}; în care să păstrăm eventual, tagurile extrase din PGN - de exemplu, this.tags['White'] = 'alexo 99'.

Pentru a separa Cheie de Valoare în cadrul unui tag (extrăgând-ule separat), putem folosi şablonul /(\w+)\s+\"(.*)\"\]/; aici "()" grupează caracterele din Cheie şi respectiv pe cele din Valoare, iar grupele rezultate pot fi extrase folosind (în javaScript) RegExp.$N unde N este rangul grupului.

Următorul fişier HTML prezintă o funcţie extract_tags() care extrage tagurile din şirul PGN primit ca parametru (folosind în acest scop cele două şabloane precizate mai sus) şi returnează un "tablou asociativ" tags (cu tags[Key] = Val):

<!DOCTYPE html>
<head>
<script>
    function extract_tags(PGN) {
        var sablon_tag = /\[\w+\s+"[^"]*"\]/g,
            sablon_KeyVal = /(\w+)\s+\"(.*)\"\]/, // grupează Key şi Val
            tags = {}; // tags[Key] = Val
            
        var matches = PGN.match(sablon_tag); // alert(matches.join('\n'));

        for(var i=0, n=matches.length; i < n; i++) {
            var tag = matches[i]
                      .match(sablon_KeyVal); //alert(RegExp.$1);
            tags[RegExp.$1] = RegExp.$2;
        }

        return tags;
    }
</script>
</head>
<body>
<script>
    var PGN = '[White   "alexo 99"][Black "vlad.bazon"][Event "InstantChess"]' +
'[WhiteElo "1936"][BlackElo "2038"][Result "*"][ICCause "2"][ICEcause   "3"]' +
'1.d4 Nf6 2.Bf4 c5 {comentariu [xxx "xxx"]} 3.e3 Qb6' +
'4.b3 cxd4 5.exd4 Nc6 6.Nf3 Nd5 7.Be3 Nxe3 8.fxe3 e5 9.Bc4 d5 *';    

    var tags = extract_tags(PGN);

    result = [];
    for(var key in tags) 
        result.push(key + ": " + tags[key]); 
    alert(result.join('\n'));
</script>
</body>

N-avem decât să încorporăm funcţia redată aici în cadrul metodei _init() (rescriind-o eventual, ca metodă privată a widget-ului) şi… putem uita de-acum de "taguri PGN". Tagurile care sunt utile în contextul nostru sunt cele de chei White, Black, Result şi Date - valorile acestora servesc pentru a constitui (în cursul metodei _init) conţinutul diviziunii .GameInfo.

Un singur tag ar mai fi important: dacă antetul PGN conţine un tag FEN, atunci acesta trebuie să aibă ca valoare un şir FEN, reprezentând poziţia iniţială (alta decât cea standard) pentru partida respectivă.

"Putem uita" înseamnă că putem elimina antetul informativ din textul PGN al partidei. Dar această eliminare nu se poate face în interiorul funcţiei extract_tags(PGN) redate mai sus, fiindcă în javaScript şirurile (aici, şirul PGN) sunt transmise prin valoare şi nu prin referinţă.

Dar mai sus avem doar o ilustrare independentă a lucrurilor - de aceea am considerat ca parametru, şirul PGN. De fapt, şirul PGN este furnizat widget-ului nostru într-un element <textarea> (referit intern prin this.element); deci nu este necesar să-l precizăm ca parametru funcţiei extract_tags().

După extragerea tagurilor, PGN-ul fără partea de antet se va putea obţine prin var PGN = this.element.val().replace(/\[\w+\s+"[^"]*"\]/g, ''); (folosind iarăşi şablonul de tag).

Eliminând antetul, şirul PGN rămas poate să înceapă cu un comentariu introductiv, referitor la partida respectivă (sau la poziţia indicată în tagul FEN existent în antet). Extrăgând eventual şi acest comentariu - rămâne "lista mutărilor" (în care unele mutări pot fi şi acestea, comentate), de care ne vom ocupa în părţile următoare.

vezi Cărţile mele (de programare)

docerpro | Prev | Next