lecŢii de Şah – computer

Click here to load reader

Post on 30-Dec-2016

228 views

Category:

Documents

1 download

Embed Size (px)

TRANSCRIPT

  • Petre Ru

    LECII

    DE

    AH COMPUTER

    Editura InfoRapArt

  • C U P R I N S

    n loc de prefa 3 Concepte de baz n ahul programat 7 1. Reprezentarea tablei de ah 8 2. Codificarea pieselor 10 3. Direcii de cutare pentru efectuarea unei mutri 12 4. Determinarea mutrilor posibile 15 5. Codificarea mutrilor 17 6. Generatorul de mutri 19 7. Generatorul de mutri. Nivelul de joc 21 8. Funcia de evaluare 23 9. Alegera mutrii optime 2610. Tratarea excepiilor n ahul programat 2811. Fiiere de deschidere i finaluri 3112.Consideraii finale 32 Aspecte geometrice ale tablei de ah n programarea finalurilor 35 Funcia de evaluare n ahul programat 40

    2

  • n loc de prefa

    (Extras dintr-un interviu la Radio)

    Reporter: - Ce reprezint calculatorul pentru dumneavoastr?P.R.: - Calculatorul reprezint unealta cu care omul poate atinge mai repede

    perfeciunea n faa naturii. El este un instrument al cunoaterii, menit s-l apropie pe om de adevr, de esen.

    Reporter: - Mai concret, la ce v folosete calculatorul?P.R.: - n ceea ce m privete calculatorul mi-a fost mereu de mare ajutor i

    asta nu numai pentru c profesia mea este legat de acesta, ci i datorit faptului c aproape de fiecare dat cnd m-am aflat la limita imposibilitii de a rezolva o problem i-am cerut sprijinul. Desigur, nu m refer numai la ceea ce poate oferi calculatorul vizavi de societate, producie, de economie n general, ci i la ajutorul oferit cercettorului, n domeniul creativitii etc. Este nu numai util, dar i minunat s poi mnui asemenea instrumente.

    Reporter: - Din cte tim ai experimentat multe lucruri pe calculator. Putei oferi mai multe amnunte n acest sens?

    P.R.: - Da. n general m-au preocupat foarte mult problemele pe care le ridic astzi inteligena artificial. La noi n ar nceputurile acestora au fost foarte dificile, ele au vizat mai mult planul teoretic al fenomenului i mai puin realizrile practice. Poate i din acest motiv inteligena artificial nu i-a putut crea un drum sigur i nu s-a bucurat de popularitatea pe care ar fi meritat-o. Prerea mea este c, fiecare cercettor din acest domeniu ar trebui, mai devreme sau mai trziu, s experimenteze n mod practic cte ceva, de pild s vad nu numai teoretic ce nseamn un program autoinstruibil, sau un demonstrator de teoreme, atunci cnd sunt puse la lucru, ce nseamn un motor de inferene i s experimenteze un motor de inferene logice, ce dificulti apar atunci cnd ncerci s-i ceri calculatorului s comunice n limbaj natural sau s se supun unui limbaj logic n esena lui. Cercettorul poate sesiza mai bine n acest mod adevratele probleme care se nasc atunci cnd ncerci s-l faci pe calculator s se comporte la fel ca o inteligen uman. Este convenabil i, dac vrei, prea panic ;i comod s te mrgineti la a sesiza nuane ale comportamentului unei inteligene umane, mai greu este ns gsirea unor ,,reete'' pentru implementarea acestora pe un calculator.

    Reporter: - i dumneavoastr ai gsit? Ai experimentat ceva din toate acestea?

    P.R. - Eu am pornit tocmai de la aceast ultim idee i anume aceea de a experimenta ct mai multe similitudini de exprimare inteligent a unui program de calculator n faa inteligenei umane. Un mare cobai al inteligenei artificiale a fost, este i va mai rmne nc jocul de ah...

    Reporter: - Acesta a fost nceputul?

    3

  • P.R. - Da.Reporter: - De ce tocmai cu jocul de ah?P.R.: - Foarte simplu! Pentru acest joc planeta noastr a investit n ultimile

    dou secole poate cea mai mare cantitate de inteligen creatoare i astzi tot mai putem spune c tainele lui n-au fost pe deplin clarificare. A trebuit, periodic, s intervin mini aproape diabolice cum au fost toi marii campioni pentru a mai avansa civa pai n cunoaterea acestui joc. Va trebui deci s treac poate alte secole pentru ca el s devin n totalitate cunoscut minii omeneti. Singura salvare rmne totui calculatorul, dei el, pn astzi, n-a atins nici pe departe cele mai importante cote ale performanei umane.

    Reporter: - Considerai c ceea ce n-a putut face mintea omeneasc ar putea face calculatorul?

    P.R.: - Nu tocmai, dei, innd cont de finitudinea jocului i de logica niruirii operaiunilor pe tabla de ah calculatorul, dac ar fi suficient de nzestrat, ar trebui s-l trateze n ntregime. Dar deocamdat el se afl n dificultate n faa imensitii de variante ale jocului propriu zis. i atunci, pn cnd se va nate un calculator care s vad finalul jocului nc de la primele mutri, ceea ce eu cred c se va petrece nu peste mult timp, calculatorul este nvat doar s imite ceea ce gndete juctorul uman n faa tablei de ah i, eventual, s egaleze performanele acestuia.

    Reporter: - Ar trebui s nelegem c dumneavoastr v-ai ocupat de aceast ultim problem?

    P.R.: - Da. M-am ocupat nu s implementez nite strategii particulare de joc, cele pe care le aplic fiecare juctor avansat i care au fost copiate aproape identic n mai toate programele de ah existente astzi n lume, ci s implementez ceea ce juctorul singur nu ar putea face cu deplin facilitate n faa tablei de ah. Mai precis am pornit de la ideea c nu anumite stategii de joc aduc ctigul, ci mai degrab nelegerea, n ansamblul lor, a tuturor operaiunilor logice care se execut pe tabla de ah i corelarea acestora.

    Reporter: - i cum ai concretizat aceast idee?P.R.: - n primul rnd a aduga c eu am lansat ideea de dominare i de

    utilitate n joc. Cu fiecare mutare fcut, calculatorul trebuie s rein ca unic criteriu de eficien ideea de dominare caracterizat n principal de totalitatea operaiunilor de atac, de aprare i de control al pieselor i cmpurilor de joc. Din punct de vedere matematic, toate acestea sunt nglobate n ceea ce se cheam funcia de evaluare, care este o funcie mai mult sau mai puin liniar, alimentat de un sistem de constante prestabilite i de condiiile concrete care intervin pe tabla de ah. Totul depinde de stabilirea acestor constante care exprim, dac vrei, la modul cel mai simplu, valoarea relaiei de atac, aprare sau control. Aceast matrice a constantelor poate fi permanent mbuntit, ba mai mult, ea poate fi supus unui riguros sistem de adaptare ntr-un program autoinstruibil.

    Reporter: - Vrem s putem nelege diferena dintre ideea de care vorbii i celelalte utilizate pn n prezent n lumea ahului programat.

    P.R.: - S v dau un exemplu. Pornii, dac vrei, de la un joc oarecare cunoscut, care presupune doi parteneri de ntrecere. Dac exist o singur strategie de ctig, atunci lucrurile sunt clare, ctigul fiind asigurat celui care o stpnete i o respect cu strictee. El va efectua un ir logic de operaiuni fidele acestei strategii. Dac jocul ar avea dou strategii de ctig atunci lucrurile se complic, n timpul jocului putnd aprea condiii cnd sunt valabile ambele strategii sau numai una din ele. n acest caz, juctorul trebuie s sesizeze totdeauna corelarea acestora, altfel ctigul nu mai poate fi sigur. Dac vrei un exemplu mai simplu, s presupunem c doi parteneri se ntrec n a strbate cel mai scurt traseu al unui labirint necunoscut. Exist dou strategii simple de abordat: una care presupune parcurgerea labirintului

    4

  • urmnd fiecare perete din dreapta, i duala sa, pentru peretele din stnga. Oricare dintre ele poate fi ctigtoare sau nu. O a treia strategie, dac ar fi inventat, este aproape obligatoriu s mbine componente ale celorlalte dou i s coreleze pri ale acestora pentru a gsi un drum i mai scurt, mai optim...

    Reporter: - Despre punerea n practic a acestora idei ce ne putei spune?P.R.: - Ar trebui s ncep prin a v spune c, dei astzi lumea este invadat

    pur i simplu de claculatoare i programe de ah, problema algoritmizrii acestui joc nc este actual. Nicieri n lume nu s-a putut emite pretenia finalizrii acestei probleme i numeroase premii au fost i nc mai sunt oferite n acest scop. Eu am realizat mai nti, n anul 1985, dup aproape doi ani de munc, un program de rezolvare a problemelor de ah cu care am participat la faza final a concursului de programare Calculatorul n sprijinul societii, organizat n principal de revista tiin i tehnic. Programul a fost foarte apreciat la acea vreme, era primul de acest gen creat n ara noastr, dar eu personal nu am vrut s m opresc n aceast faz. Dorina mea era s creez un program de jucat ah. i parial am reuit. La cteva luni dup aceea am prezentat conceptul noului meu program la primul festival naional pe aceast tem, susinut la Bile Herculane n martie 1986. Ideile mele s-au bucurat de o larg apreciere, programul a fost declarat ca fiind a doua concepie original romneasc n acest domeniu, prima fiind semnat n 1976 de cunoscutul cercettor Viorel Darie. Imediat dup aceea am nceput s m bucur de sprijinul moral i documentar al unui mare animator al ahului electronic, pe atunci preedintele Comisiei Centrale de ah- Computer, Uly Vlureanu. Ideile au fost multe i frumoase, dar cine pe vremea aceea i putea oferi condiii favorabile pentru punerea lor n practic? M-am lovit de numeroase obstacole, multe dintre ele neputndu-le depi. Trebuie s menionez c de aceast problem m-am ocupat numai n timpul meu liber, lipsit de mijloace tehnice adecvate, singur, fr colaboratori, iar ntr-un ora de provincie, chiar dac este vorba de Galai, preocuprile i interesul pentru aceast activitate au fost i mai sunt nc foarte rare. Munca este ns imens i nu poate fi acoperit n ntregime de un singur om. Oricum, rezultatele la care am ajuns mi-au oferit destule satisfacii personale i muli consider c am realizat pai importani...

    Reporter: - S nelegem, prin cele ce ne-ai mrturisit, c ateptai propuneri de colaborare sau sprijin n acest sens?

    P.R.: - De ce nu? Experiena pe care am ctigat-o n acest domeniu este imens. Realizarea unui program de ah este astzi relativ uoar