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

Modelarea tablei şi jocului de şah (XIX)

jQuery | javaScript | widget
2012 aug

Testarea generatorului de mutări

Prin "poziţia curentă" înţelegem conţinutul tabloului intern this.x88Board[], împreună cu valorile variabilelor interne .castle, .en_pass, etc. ("flagurile" poziţiei) - existente la momentul respectiv.

Pentru poziţia curentă, _gen_moves() ne dă lista tuturor mutărilor posibile (unele pot fi ilegale), în tabloul global bin_moves[]; apelând _makeMove(), constatăm dacă mutarea este legală - caz în care se face şi actualizarea poziţiei curente.

Aceste metode funcţionează corect, dacă pentru fiecare poziţie curentă - bin_moves[] include toate mutările legale pentru acea poziţie. Putem testa corectitudinea lor, aplicându-le pe un set de poziţii pentru care cunoaştem numărul de mutări legale ce trebuie obţinut; desigur, poziţiile alese trebuie să permită verificarea tuturor categoriilor de mutări.

De exemplu, în poziţia iniţială standard albul are 20 de mutări legale: 4 mutări de cai (cel din 'g1' poate muta pe 'f3', sau pe 'h3') şi câte 8 mutări de avansare cu o linie, respectiv cu două linii, a unui pion. Dacă bin_moves[] conţine 20 de elemente (de data aceasta, nu vor fi generate decât mutări legale) atunci putem fi siguri că mutările obişnuite de pion sunt generate corect; dacă ar fi mai mult de 20 de elemente, atunci o listare a mutărilor generate ne va putea indica ce anume nu funcţionează corect.

În (XVI) am adăugat temporar widget-ului din "pgnbrw.js" metoda allMovesTable() prin care am obţinut tabelele ALL_MOVES[]. Putem folosi aceeaşi manieră de lucru pentru a adăuga temporar metoda publică perft(), prin care să obţinem numărul de mutări legale care au fost generate în bin_moves[] - fie pentru poziţia al cărei FEN este indicat în textul PGN transmis widget-ului, fie pentru poziţia al cărei şir FEN este furnizat ca parametru de apel:

perft: function(id_dest, fen) {
    var fen = fen || this.tags['FEN'], 
        N = 0; // numărul mutărilor legale generate
    this._setBOARD(fen); // poziţia iniţială, conform FEN-ului dat
    this._gen_moves();   // bin_moves[] = lista mutărilor posibile
    for(var i = 0, n = bin_moves.length; i < n; i++) { 
        var m = bin_moves[i];
        if (this._makeMove(m)) { // dacă mutarea este şi legală
            N++;                 // o contorizează
            this._setBOARD(fen); // şi revine la poziţia iniţială
        } // mutările respinse de _makeMove() sunt ignorate
    }
    $('#' + id_dest).html('<p>' + (this.to_move ? 'Negrul': 'Albul') + 
                          ' are <b>' + N + '</b> mutări legale</p>');
},

Perft ("performance test") este o subrutină de depanare obişnuită în programele care joacă şah (sau alte jocuri bazate pe "mutări"); aici nu performanţele ca timp de generare ne interesează (fiindcă vizăm numai poziţia curentă, nu şi pe cele derivate în urma răspunsurilor posibile ale adversarului) şi mai sus avem o formă particulară de "perft", în termenii constituiţi în pgnbrw.

Pentru a invoca metoda introdusă putem folosi un fişier HTML similar celui din (XVI) (şi cu aceeaşi secţiune de <head>, pe care n-o mai redăm aici):

<body>
<textarea id="txtPGN">
[White "M. Bezzel, 1848"]
[FEN "8/2R5/3N4/6R1/3BBN2/1Q6/3K3k/8 w "]
</textarea>
<div id="nr-legale"></div>
<script>
$(function() {
    $('#txtPGN')
    .pgnbrw({show_PGN: false, with_FEN:false})
    .pgnbrw('perft', 'nr-legale');
});

</script>
<!-- .pgnbrw('perft', 
             'nr-legale', 
             'R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w ') -->
</body>

În <textarea> am înscris numai tagul [FEN] (lipseşte secţiunea mutărilor); dar pgnbrw acceptă şi PGN-uri cu asemenea "defecte" - aceasta fiind mai mult un avantaj, decât un "defect". Am adăugat şi un tag [White], în care am înscris numele autorului poziţiei.

Max Bezzel (care a creat şi celebra problemă a damelor - Eight_queens_puzzle) a pus problema de a amplasa toate piesele albe (exceptând pionii) astfel încât numărul de mutări posibile să fie maxim şi a arătat că sunt numai două astfel de poziţii - cea reprezentată mai sus şi aceea care provine din aceasta punând turnul din 'g5' pe 'a5' - iar numărul de mutări în această poziţie este 100.

Încărcând în browser fişierul HTML obţinem ceea ce am redat în imaginea de mai sus; numărul de mutări generate în bin_moves[] este într-adevăr 100 - ceea ce ar înseamna că generarea mutărilor obişnuite ale pieselor (fără capturi, fiindcă poziţia nu acoperă acest caz) este corectă.

În comentariul adăugat înainte de </body> am indicat apelarea metodei perft() pentru un FEN dat ca parametru; în poziţia respectivă numărul de mutări legale este cunoscut: 218.

Imaginea alăturată corespunde reîncărcării fişierului HTML în browser, după înlocuirea în <textarea> cu parametrul menţionat; constatăm că în bin_moves[] au fost generate într-adevăr, 218 mutări (nu-i cazul nici aici, să avem mutări "posibile" dar "ilegale"); iar de această dată, avem generate corect şi nişte mutări cu efect de captură.

Desigur, această poziţie a fost creată artificial, urmărind crearea unei poziţii legale în care să fie posibil un număr cât mai mare de mutări. Se pune atunci problema (de obicei, nebanală) de a dovedi că poziţia creată este legală (adică poate fi obţinută plecând de la cea iniţială standard); se vede uşor că dacă regele alb ar fi fost pus pe 'b3' în loc de 'f1', atunci poziţia ar fi ilegală: care a fost în acest caz ultima mutare, a negrului? - nu există nici una, pe care negrul să o fi putut face şi să rezulte poziţia în care acum albul mută. Pe când în poziţia redată, ultima mutare a negrului a fost b3-b2 (acoperind şahul de la dama din 'e5'); nu putea fi c3xb2: lipsind numai pionii albi (promovaţi în dame), negrul nu avea ce să captureze.

Desigur, putem adăuga pe tiparul de mai sus şi alte exemple - poziţii potrivite pentru testarea generării corecte a mutărilor de transformare, a acelora de luare "en-passant", a acelora în care apare problema legalităţii mutărilor pieselor "legate", a acelora care corespund diverselor situaţii în care rocada este restricţionată, etc.

Pare îndoielnic că am putea găsi o raţiune pentru a păstra metoda perft() în cadrul widget-ului pgnbrw (noi o inclusesem "temporar", pentru verificarea generatorului de mutări), având în vedere că scopul asumat de acesta este de a permite parcurgerea unei partide de şah (pe cine ar interesa "numărul de mutări legale"?). Dar nu este rea, ideea de a prevedea o opţiune suplimentară pentru aceasta, sau un buton (similar celui care inversează tabla) care la click să apeleze perft() şi să afişeze undeva numărul de mutări legale în poziţia curentă.

vezi Cărţile mele (de programare)

docerpro | Prev | Next