Imbunatatiri ale Algorimului Alpha Beta cu Aplicare In Jocul de Sah

Îmbunătățiri ale algorimului Alpha-Beta

cu aplicare în jocul de șah

Abstract

This work focuses on presenting the algorithms used to search in games of perfect information, and especially in chess.

Starting in the mid fifties, a theory on how to play zero sum perfect games was developed. The theory is essentially based on traversing a tree called Minimax tree, and find a path from the root to one of its leaves that will maximize a player’s chances of winning. Each node in the tree represents a configuration in the game.

In programs that play Minimax games such as chess and checkers, the efficiency of the search is of crucial importance. Over the years, a large number of theoretical works have been done to improve the algorithm. Two major algorithms have raised attention: Alpha-Beta, a dept-first search algorithm, and SSS*, a best-first search algorithm. Although SSS* promised better results, it was abandoned due to its complexity and slowness. Research on Alpha-Beta has yielded many enhancements, such as transposition tables, parallelization of the algorithm, null moves, move ordering and null windows with re-searches, which are responsible for the success of depth-first Minimax search. The enhancements have made it possible to use a depth-first procedure to expand nodes in a best-first sequence.

Chess has been the game that attracted the most interest from the Artificial Intelligence researchers. This and the recent advances in hardware have made it possible that top computer chess playing programs beat human world-champions.

Introducere

Prezentare generală

Lucrarea prezentă se axează pe descrierea algoritmilor și a tehnicilor folosite pentru a căuta cea mai bună mutare, la un moment dat, în jocuri cu informație perfectă, de sumă 0, și în special în șah.

În primul capitol se face o scurta introducere în inteligența artificială și aplicația sa în jocuri, prezentând un scurt istoric al evoluției programelor de joc pe calculator de-a lungul anilor.

În cel de-al doilea capitol sunt prezentați algoritmii generali folosiți în jocurile cu informație perfectă de sumă 0, astfel acest capitol putând fi un punct de plecare și pentru documentarea în vederea implementării altor jocuri asemănătoare (Go, Dame, Othello, etc.). Algoritmul de bază implică traversarea unui arbore numit arbore Minimax, și găsirea mutării optime. Există 2 abordări pentru traversare: în adâncime, iar algoritmul ce face acest lucru poartă numele de Alpha-Beta, și traversarea în ordinea scorului nodurilor (cel mai bun primul), algoritmul cel mai folosit fiind SSS*. Având în vedere că surplusul de calcul și memorie duc ca algoritmul SSS* să fie mai puțin eficient decât Alpha-Beta, în acest capitol va fi prezentat pe larg doar acesta din urmă, cât și îmbunătățirile aduse: ferestrele de aspirație, ferestre nule, ordonarea mutărilor, tabele de transpoziții, metode de paralelizare a algoritmului.

În cel de-al treilea capitol sunt prezentate metode specifice de implementare al jocului de șah: modurile de reprezentare ale tablei folosite cel mai des în practică, tehnici de generarea a mutărilor, tehnici de căutare specifice șahului, cât și descrierea factorilor principali ce trebuie luați în considerare în alcătuirea unei funcții de evaluare pentru jocul de șah.

În ultimul capitol este prezentat modul de proiectare al aplicației ce însoțește lucrarea, menită a fi o exemplificare a algoritmilor descriși. Aplicația este implementă în Java, un limbaj larg utilizat în ultima perioadă, folosind NetBeans ca mediu de dezvoltare.

Inteligența artificială și jocurile

Inteligența Artificială este domeniul de cercetare ce se ocupă cu studiul și proiectarea agenților inteligenți, în special programe de calculator inteligente.

Inteligența artificială este o știință destul de nouă. După al doilea război mondial, un număr de oameni au început, independent, să muncească la dezvoltarea mașinilor artificiale. Matematicianul englez Alan Turing ar putea fi primul dintre ei. El a fost primul care a decis că cea mai buna metodă pentru cercetările în domeniul inteligenței artificiale este programarea computerelor si nu prin construirea mașinilor. În articolul „Computing Machinery and Intelligence” (1950) aparținând lui Alan Turing, se discuta despre cum poate fi o mașină considerată inteligentă. El a propus un test destul de simplu: mașina e considerată inteligentă dacă un interogator, după ce pune un set de întrebări scrise, nu își poate da seama dacă răspunsul vine de la o persoana sau nu.

O problemă clasică în inteligența artificială sunt jocurile. De-a lungul anilor cercetătorii au depus multe eforturi pentru a îmbunătății calitatea lor. Eforturile nu au fost în zadar, jocuri ca Moara, Connect Four, Qubic fiind rezolvate. Totuși jocurile mai complicate necesită algoritmi speciali și metode euristice. Astăzi programele de calculator sunt printre cei mai buni jucători de table, fiind capabile să bată campioni mondiali. În Othello (Reversi) nici cei mai buni jucători nu au șanse în fața programelor de calculator. De asemenea jocul de dame pe calculator Chinook este imbatabil. Jocul de dame a fost rezolvat de curând, în prezent fiind cel mai mare joc rezolvat, spațiul de căutare fiind de ordinul 5×1020 . Dintr-o poziție standard, jocul duce la egalitate dacă ambii jucători mută perfect.

La șah, programele de top au ajuns capabile să bată campioni mondiali. În 1997 Deep Blue, un calculator creat special pentru jocul de șah l-a bătut pe Garry Kasparov, campionul mondial la acea vreme. A fost un start, care a fost continuat de programele de șah moderne. În 2006 Deep Fritz rulând pe un calculator personal conținând 2 procesoare Intel Core 2 Duo, l-a învins pe campionul mondial Vladimir Kramnik. Conform profesorului Monty Newborn de la universitatea McGill din Montreal acest rezultat ar putea duce la dezinteresul pe viitor asupra competițiilor dintre oameni si calculatoare. În alte jocuri ca Shogi, Go, Bridge, oamenii încă surclasează programele de calculator.

Văzute din punct de vedere științific, jocurile furnizează un domeniu închis, ce reflectă proprietăți din lumea reală, fiind facile pentru experimente și idei noi în rezolvarea problemelor. Astfel aplicațiile practice ale acestora includ domenii ca: matematică, economie, informatică cum ar fi teoria jocurilor, jocuri combinatoriale, teoria complexității, optimizare combinatorială, programare logică, demonstrarea teoremelor, satisfacerea constrângerilor, recunoașterea șabloanelor, calcul distribuit, etc.

Capitolul 1

Strategii de căutare utilizate în jocuri

1.1 Minimax

În majoritatea jocurilor de calculator o mare importanță o are algoritmul de căutare. În alegerea următorii mutări, un om, în mod normal ar anticipă câteva mutări în față, încercând să ghicească mutările oponentului la mutările lui. Astfel el alege mutarea cea mai favorabilă. Programele de calculator imită acest comportament, parcurgând întreg spațiul de căutare până la un anumit nivel, încercând să găsească cea mai bună mutare. Presupunând că ambii jucători aleg mutările cu cea mai mare probabilitate de câștig, la fiecare poziție valoarea celei mai bune mutări este returnată la poziția părinte. Jucătorul A încearcă sa își maximizeze șansele de câștig. Același lucru face și jucătorul B, acțiune echivalentă cu a minimiza șansele jucătorului A. Din acest motiv, algoritmul poartă numele de Minimax.

Pentru a determina cea mai bună mutare jucătorul care face mutarea va încerca să maximizeze valoarea minimă a poziției rezultată din mutările posibile ale adversarului. Astfel se creează un arbore ce reprezintă spațiul de stări ale problemei. Spațiul de stări poate fi foarte mare, iar parcurgerea întreagă a acestuia devine imposibilă. De exemplu jocul de șah presupune în medie o ramificare de ordinul 35 la fiecare pas. Un joc de șah jucat decent conține cel puțin 30 de mutări. Astfel spațiul de stări ajunge la 3530 = 20991396429661901749543146230280399322509765625. Din acest motiv căutarea va fi limitată la un anumit nivel. Când acest nivel este atins, programul va atribui frunzei o valoare obținută printr-o funcție de evaluare, ce va lua în calcul proprietăți ale mutării curente pentru a determina valoarea aproximativă a poziției[14].

1.1.1 Funcțiile de evaluare

Funcțiile de evaluare sunt o componentă esențială a algoritmilor de căutare practici. Sunt folosite în jocuri pentru a evalua valoarea unei anumite poziții. Performanța unui joc de calculator este extrem de dependentă de calitatea funcției de evaluare. Dacă aceasta nu este precisă, va conduce programul în poziții care aparent sunt bune, dar se dovedesc a fi dezastruoase. Funcția de evaluare trebuie să returneze un rezultat într-un timp cât mai scurt posibil, evaluând doar poziția curentă, fără a explora și altele.

O strategie populară în crearea funcțiilor de evaluare este calcularea sumei ponderate a diverșilor factori care sunt considerați ca pot influența valoarea unei poziții. De exemplu, o funcție de evaluare pentru șah poate lua forma: c1 * valoare materială + c2 * mobilitate + c3 * siguranța regelui + c4 * controlul centrului

Un exemplu de parcurgere al algoritmului Minimax este prezentat în figura 1.1. Presupunem că jocul are doar 2 mutări posibile pentru fiecare tură a celor 2 jucători. Algoritmul generează un arbore ca în figura 1.1, unde cercurile reprezintă mutările jucătorului ce rulează algoritmul (maximizatorul), și pătratele reprezintă mutările adversarului. Din cauza resurselor limitate ale calculatorului (după cum a fost explicat mai sus) arborele este limitat la o adâncime de 4 mutări. Algoritmul evaluează fiecare nod frunză folosind o metodă de evaluare euristică, obținând astfel valorile arătate. Mutările în care jucătorul care este la rând câștigă sunt notate cu plus infinit, în timp ce mutările ce duc la câștigul adversarului sunt notate cu minus infinit. La nivelul 3, algoritmul va alege, pentru fiecare nod, cea mai mică valoare dintre cele ale copiilor nodului, și o va atribui acelui nod (de exemplu nodul din stânga va alege valoarea minimă dintre 10 și +∞ , așadar atribuindu-și valoarea 10). La următorul pas, la nivelul 2, se va alege, pentru fiecare nod, cea mai mare valoare dintre cele ale fiilor nodului. Încă odată, valorile sunt atribuite nodurilor părinte. Algoritmul continuă evaluarea minimului și maximului valorilor nodurilor copil, alternativ, până când se ajunge la nodul rădăcină, unde alege mutarea cu cea mai mare valoare (reprezentată în figură cu o săgeată albastră). Aceasta este mutarea pe care jucătorul trebuie să o facă pentru a minimiza maximul pe care poate să îl piardă.

Căutarea cât mai adâncă crește calitatea deciziei. Mulți cercetători au studiat algoritmul Minimax pentru a-i îmbunătăți performanțele, permițându-le să caute mai adânc într-o limită de timp precizată. În jocuri, o mutare nu poate dura, în general, mai mult decât câteva minute. Căutarea în timp real este un element central în multe domenii din domeniul informaticii, așa că multe din ideile create în căutarea Minimax s-au dovedit folositoare și în alte domenii. De exemplu căutarea iterativă în adâncime (IDA), tabelele de transpoziții, căutarea în timp real (RTA), căutarea bi-direcțională (BIDA) au fost aplicate atât în căutarea multi-agent cât și uni-agent.

1.2 Alpha-Beta

Odată cu creșterea în adâncime a arborelui Minimax, numărul de noduri crește exponențial. Pentru un arbore Minimax de înălțime uniformă d și un factor de ramificare w, numărul de noduri frunză este w*d. Rata exponențială de creștere ar limita căutarea în adâncime la nivele mici. Pentru șah, date fiind o rată de 1 milion de evaluări ale pozițiilor pe secundă, un factor de ramificare de 35, fără alte optimizări, și constrângerea ca 40 de mutări să fie calculate în 2 ore (rata standard în turneu), ar însemna, ca în condiții de turneu căutarea va fi limitată la 5 sau 6 nivele (o astfel de mașină poate calcula în jur de 180 de milioane de poziții pentru a minimiza maximul pe care poate să îl piardă.

Căutarea cât mai adâncă crește calitatea deciziei. Mulți cercetători au studiat algoritmul Minimax pentru a-i îmbunătăți performanțele, permițându-le să caute mai adânc într-o limită de timp precizată. În jocuri, o mutare nu poate dura, în general, mai mult decât câteva minute. Căutarea în timp real este un element central în multe domenii din domeniul informaticii, așa că multe din ideile create în căutarea Minimax s-au dovedit folositoare și în alte domenii. De exemplu căutarea iterativă în adâncime (IDA), tabelele de transpoziții, căutarea în timp real (RTA), căutarea bi-direcțională (BIDA) au fost aplicate atât în căutarea multi-agent cât și uni-agent.

1.2 Alpha-Beta

Odată cu creșterea în adâncime a arborelui Minimax, numărul de noduri crește exponențial. Pentru un arbore Minimax de înălțime uniformă d și un factor de ramificare w, numărul de noduri frunză este w*d. Rata exponențială de creștere ar limita căutarea în adâncime la nivele mici. Pentru șah, date fiind o rată de 1 milion de evaluări ale pozițiilor pe secundă, un factor de ramificare de 35, fără alte optimizări, și constrângerea ca 40 de mutări să fie calculate în 2 ore (rata standard în turneu), ar însemna, ca în condiții de turneu căutarea va fi limitată la 5 sau 6 nivele (o astfel de mașină poate calcula în jur de 180 de milioane de poziții pentru fiecare dintre cele 40 de mutări, intre marja de 355 și 356). Studiile au arătat că, pentru a juca la un nivel de maestru, programul trebuie să calculeze mai mult de 5 mutări în față. Dacă n-ar fi fost introduse tehnicile de tăiere, programele de joc n-ar fi avut un așa mare succes[8].

Regula de atribuire Minimax alternează prin luarea maximului și minimului dintr-un set de numere. Să presupunem că suntem la rădăcina arborelui din figura 1.2

Primul copil returnează +1. Rădăcina este un nod maxim, deci valoarea sa poate crește doar examinând noduri cu valoare > +1. Dar având în vedere că valorile posibile pentru nodul rădăcină sunt {-1,0,+1} observăm că +1 este limită superioară, deci continuarea căutării nu va schimba valoarea maximă a nodului rădăcină. Restul de noduri pot fi eliminate (tăiate).

Tăierea nodurilor aduce beneficii importante în performanță, reducând complexitatea găsirii valorii unui nod rădăcină până la rădăcina pătrată a ordinului inițial de complexitate.

Algoritmul Alpha-Beta îmbunătățește algoritmul Minimax prin introducerea tăierilor. Alpha-beta a fost folosit de către comunitatea de programatori de jocuri pe calculator de la sfârșitul anilor 1950. Se pare că a fost gândit independent de către mai mulți cercetători.

Prima publicație ce descrie o formă de tăiere aparține lui Newell, Shaw și Simon (Chess playing programs and the problem of complexity). Se presupune că John McCarthy a avut idea originală și de asemenea el ar fi cel care a dat numele de Alpha-Beta. Totuși, potrivit Knuth și Moore[3], Samuel a declarat că ideea a fost deja prezentă în programele sale de jucat șah de la sfârșitul anilor 1950, dar nu a menționat acest lucru pentru că a considerat că alte aspecte ale programului erau mai importante. O analiză complexă a algoritmului, introducând conceptul de arbore minimal , a fost publicată de către Knuth și Moore în 1975 [3].

În figura 1.3 este prezentat pseudo-codul pentru algoritmul Alpha-Beta. Acesta constă în funcția Minimax, plus încă 2 argumente de intrare și teste de tă1iere. Parametrii α și β împreună sunt numiți fereastra de căutare. La nodurile max, g reprezintă marginea de jos la valoarea returnată. Marginea de jos e înaintată nodurilor copil ca și parametru. Atunci când oricare dintre copii realizează că nu poate întoarce o valoare peste marginea de jos, continuarea căutării devine de prisos și este oprită. Acest lucru se poate întâmpla la copii de tip min, deoarece acolo g este margine superioară. Parametrul b transmite marginea mai departe ca oricare copil max cu o margine mai mică să se poate opri din căutare atunci când e necesar. Împreună, α și β formează o fereastră de căutare care poate fi privită ca o sarcină pentru un nod de a returna o valoare din intervalul dat de fereastră. Dacă un nod descoperă că valoarea sa nu se află în intervalul dorit, căutarea e oprită. Acest lucru e ilustrat în figura 1.4. Presupunând că Alpha-Beta este apelată cu o fereastră inițială cuprinsă între (-∞, +∞) nodul e este căutat cu o fereastră (12, +∞). După ce nodul f returnează, valoarea nodului e este <= 10, valoare ce cade în afara intervalului ferestrei de căutare, așadar căutarea este oprită înainte ca nodul g să fie traversat.

Dacă valoarea de retur a unui nod se află în interiorul ferestrei de căutare, atunci valoarea sa a fost găsită. Altfel valoarea de retur reprezintă o limită. Din acest motiv, pentru a fi siguri că obținem valoarea poziției, Alpha-Beta trebuie apelată în felul următor: Alpha-Beta (n, -∞,+∞).

1.3 Îmbunătățiri aduse algoritmului Alpha-Beta

Performanța algoritmului Alpha-Beta depinde de cum sunt ordonate nodurile copil. In această secțiune vom prezenta câteva metode ce îmbunătățesc performanța algoritmului, ducând-o mai aproape de valoarea teoretică.

1.3.1 Arborele minimal

Dacă cea mai bună mutare este examinată prima în fiecare nod, atunci arborele traversat de algoritmul Alpha-Beta este minimal. Acest arbore minimal are o importanță teoretică deoarece mărimea sa este un reper pentru căutare. Pentru arborii uniformi cu factor de ramificare W și o adâncime D există W[D/2]+W[D/2]-1 noduri terminale în arborele minimal. Deși alții au obținut acest rezultat, cea mai bună dovadă a fost dată de Knuth și Moore [3].

1.3.2 Ferestre de căutare mai mici

Alpha-Beta taie un sub-arbore atunci când valoarea unui nod cade în afara ferestrei de căutare. O idee de a crește frecvența tăierii arborelui este de a căuta cu ferestre mai mici. Presupunând că c ≤ a și b ≤ d, o căutare cu o fereastră [c, d] va vizita cel puțin atâtea noduri ca și o căutare cu fereastra [a,b] (dacă ambele caută în același arbore). În mod normal, căutarea cu fereastra mai largă va vizita noduri în plus. Totuși, Alpha-Beta folosește deja toate valorile de retur ale căutării în adâncime pentru a limita fereastra de căutare cât mai mult posibil. Reducerile adiționale ale ferestrei de căutare duc la riscul de a nu mai găsi valoarea Minimax dacă α < g < β. Dacă valoarea returnată se află în afara ferestrei de căutare, atunci suntem informați doar că s-a găsit o limită la valoarea Minimax. Pentru a găsi adevărata valoare Minimax în acest caz, va fi necesară efectuarea unei noi căutări, cu mărimea ferestrei corecte. În practică, beneficiile folosirii unei ferestre mai mici depășesc pierderea de performanță cauzată de căutările repetate, lucru evidențiat în multe publicații (de exemplu [6]). În plus, surplusul de calcul datorat căutărilor repetate poate fi redus prin folosirea unor metode de stocare.

1.3.3 Ferestre de aspirație

În multe jocuri, valorile nodurilor părinte si copii sunt corelate, așadar putem obține relativ ușor estimări ale rezultatului returnat de o căutare la o anumită adâncime (Putem face o căutare puțin costisitoare la o adâncime mică pentru a obține estimarea). Această estimare poate fi folosită pentru a crea o fereastră mai mică. De exemplu în șah aceasta este de regula ± valoarea unui pion. Acest tip de fereastră poartă numele de fereastră de aspirație. Cu această fereastră se efectuează o căutare Alpha-Beta. Dacă obținem un succes, atunci am găsit valoarea Minimax, altfel căutarea va trebui repetată, folosind limita returnată de căutare, evitând astfel fereastra -∞,+∞.

1.3.4 Ferestre nule

Împingând ideea de căutări cu ferestre mici la limită obținem o căutare cu fereastră nulă. Valorile pentru α și β sunt alese astfel încât Alpha-Beta va întoarce întotdeauna o limită.

O căutare Alpha-Beta cu fereastră având α = β- 1 asigură cel mai mare număr de tăieri. Pe de altă parte, garantează de asemenea că o nouă căutare este necesară pentru a găsi valoarea Minimax. Deoarece dorim o valoare Minimax la rădăcină, logic ar fi să folosim o fereastră de aspirație mai mare acolo, cu o probabilitate mică de a fi necesară efectuarea unei noi căutări. Totuși, dacă ne uităm la structura arborelui minimal, observăm că pentru nodurile interioare tot ce ne trebuie este o limită. În figura 1.5 este prezentată o versiune sortată a arborelui minimal, pentru un exemplu Alpha-Beta, cu nodurile notate cu cele 3 tipuri de noduri, așa cum sunt definite de Knuth și Moore [6].

Nodurile care au doar un copil în arbore sunt notate cu 2, nodurile care au toți copiii sunt notate cu 3, și nodurile care fac parte și din ambele soluții (min și max) sunt notate cu 1. Nodurile de tip 1 formează calea de la rădăcină la cea mai bună frunză. Această intersecție a arborilor de soluție poartă numele de calea critică sau variația principală (principal variation – PV). Interpretarea sa este linia de joc pe care căutarea o prezice. Valoarea Minimax e calculată pentru nodurile notate cu 1. Într-un arbore de adâncime d, există doar d+1 noduri de tip 1. Singura sarcină a nodurilor de tip 2 și 3 este de a dovedi că nu are rost de a le căuta în continuare, pentru că sunt mai puțin eficiente decât cele de tip 1.

Pentru nodurile ce nu se află pe calea PV se va folosi o fereastră nulă de căutare, pentru că tot ce avem nevoie este o limită. În arborii reali, care nu sunt ordonați perfect, nodul PV nu este cunoscut în prealabil, deci există riscul de fi nevoie să se facă o nouă căutare. Din nou, în practică, căutările cu fereastră mică au performanțe atât de bune, încât surplusul de calcul datorat faptului că sunt necesare mai multe căutări este neglijabil. Așadar se poate crea un algoritm ce folosește o fereastră largă pentru primul copil, sperând că va face parte din PV, și o fereastră nulă pentru restul copiilor. La un nivel de tip max, primul nod ar trebui sa fie cel mai mare. Dacă una din căutările cu ferestre nule returnează o limită care este mai mare, atunci acest copil devine noul candidat PV și ar trebui efectuată o nouă căutare pe el cu o fereastră mai largă, pentru a-i determina valoarea. Pentru nivelul min, primul nod ar trebui să aibă valoarea minimă. Dacă prin căutarea cu fereastră nulă unul din nodurile de pe același nivel are o limită mai mică,atunci acel nod devine noul candidat PV.

Primii algoritmi în care s-a implementat această idee au fost Palphabeta, Scout

și PVS [11,12]. În 1982 Reinefeld publică un articol în care prezintă un nou algoritm, bazat pe Scout [9]. Algoritmul se numește NegaScout (vezi figura 1.6), și este folosit în multe din programele de șah performante. Îmbunătățirea căutării fail-soft adusă de NegaScout face ca pentru ultimele 2 nivele să fie returnate întotdeauna valori corecte Minimax, deci nu mai este necesară efectuarea unei noi căutări. Dovezile empirice au arătat că, și fără memorarea pozițiilor, algoritmul NegaScout găsește mai multe tăieturi decât Alpha-Beta cu o fereastră de (-∞,+∞). Majoritatea programelor de joc folosesc o combinație între NegaScout și căutare aspirată la rădăcină.

Un alt algoritm Minimax ce s-a dovedit că dă rezultate bune în practică este MTD(f) (prescurtare pentru MTD(n,f) – Memory-enhanced Test Driver cu nodul n și valoarea f). Autorul algoritmului, Aske Plaat, arată în lucrarea în care a prezentat algoritmul, prin teste practice, că acesta are performanțe mai bune chiar și decât NegaScout[7]. Algoritmul efectuează doar căutări cu fereastră nulă, returnând întotdeauna o limită inferioară sau superioară. Căutările cu fereastră nulă generează mai multe tăieri, dar returnează mai puțină informație. Pentru a afla valoarea Minimax, MTD(f) apelează Alpha-Beta de mai multe ori, apropiindu-se de valoare și găsind-o până la urmă. O tabelă de transpoziții este necesară pentru a reduce calculele adiționale necesare parcurgerii repetate a arborelui. Datorită simplității lui, este de preferat atunci când se dorește o implementare paralelă. Pseudocodul pentru algoritmul MTD(f) este prezentat în figura 1.7.

1.3.5 Ordonarea mutărilor

Un alt mod de a crește performanțele algoritmului Alpha-Beta este de a alege mai bine ordinea în care nodurile copii sunt analizate. Într-un arbore perfect ordonat și uniform Alpha-Beta va efectua numărul maxim de tăieturi. O primă abordare ar fi să fie folosite cunoștințele specifice aplicației pentru a ordona mutările. De exemplu, la șah, în marea majoritate a cazurilor ar trebui încercate mutările care capturează o piesă a oponentului. În Othello, anumite mutări în apropierea colțurilor sunt adesea cele mai bune. Totuși, există un număr de tehnici care acționează independent de specificațiile aplicației.

1.3.6. Euristica Istoric

În majoritatea jocurilor există mutări care sunt bune în mai multe poziții (de exemplu mutările din șah și Othello pe care le-am amintit mai sus). Schaeffer a introdus euristica istoric, o tehnică ce identifică mutările ce au fost bune în repetate rânduri [12]. Tehnica istoricului constă în menținerea unei tabele în care pentru fiecare mutare un scor este incrementat atunci când acea mutare se dovedește a fi cea mai bună mutare sau cauzează o tăiere. Într-un nod, copiii sunt analizați în ordinea scorului din istoric. În acest mod programul învață ce mutări sunt bune într-o anumită poziție, și care nu, fără a fi nevoie de cunoștințe specifice aplicației. Schaeffer a publicat un studiu intens asupra beneficiilor de performanță aduse de această tehnică.

1.3.7. Tabele de transpoziții și căutarea iterativă în adâncime

În multe domenii de aplicații Minimax, spațiul de căutare este un graf, în timp ce algoritmii Minimax sunt adaptați pentru căutarea în arbori. Tabelele de transpoziții sunt folosite pentru a crește eficiența algoritmului de căutare, prin împiedicarea expandării în mod repetat a copiilor prin părinți diferiți. O tabelă de transpoziții este de obicei implementată ca și o tabelă de hashing în care sunt memorate nodurile de căutare. Astfel, algoritmul de căutare este modificat pentru a căuta în această tabelă înainte de a analiza un nod, și dacă nodul este găsit în tabelă, folosește valoarea deja calculată, în loc să o calculeze din nou prin căutare. În aplicații în care sunt multe muchii ce duc la un nod, această tehnică îmbunătățește substanțial performanțele algoritmului.

Majoritatea programelor de joc folosesc căutarea iterativă în adâncime. Aceasta se bazează pe faptul că un arbore de căutare de adâncime mică reprezintă o aproximare bună pentru o căutare mai în adâncime. Se pornește cu o căutare la nivelul întâi, care se încheie aproape instant, apoi se crește nivelul de adâncime cu câte un pas, de fiecare dată căutarea fiind pornită de la început. Datorită creșterii exponențiale a arborelui, iterațiile anterioare consumă un timp neglijabil în comparație cu ultima. Printre avantajele căutării iterative în adâncime sunt ordonarea mai bună a mutărilor și controlul mai bun al timpului dacă acesta este restricționat. Tabelele de transpoziții sunt deseori folosite alături de căutarea în adâncime pentru a obține o ordonare a mutărilor. Valoarea de căutare și ramura ce conduce la cel mai bun scor sunt salvate pentru fiecare nod. Atunci când algoritmul de căutare iterativ trece la un nivel mai adânc și revizitează nodurile, această informație este folosită pentru a căuta mai întâi în mutarea care s-a dovedit a fi cea mai bună la pasul precedent. Deoarece am presupus că o căutare până la un nivel mic este o aproximare bună a căutării mai adânci, cea mai bună mutare pentru nivelul d se va dovedi în multe cazuri ca fiind cea mai bună mutare și pentru nivelul d+1. În cazul algoritmilor iterativi de căutare în adâncime tabelele de transpoziții au de asemenea rolul de a preveni efectuarea unei noi căutări asupra unui nod care a fost procesat într-o iterație anterioară.

1.3.8 Căutarea Alpha-Beta paralelă

Paralelizarea algoritmului Alpha-Beta și a derivaților săi s-a dovedit a fi o sarcină dificilă, deoarece Alpha-Beta este un algoritm secvențial, tăierea depinzând de căutarea în întregime a unui subarbore pentru a stabili limitele pentru căutarea în subarborele următor.

Cei mai folosiți algoritmi de paralelizare sunt:

Principal Variation Splitting (PVS)

Ideea din spatele algoritmului este de a explora prima dată în mod secvențial o cale de la rădăcină până la cea mai din stânga frunză. Prin această traversare se obțin limitele Alpha și Beta, iar următoarele ramuri pot fi parcurse cu versiunea paralelă a Alpha-Beta.

Young Brothers Wait (YBW)

Ideea din spatele algoritmului YBW este de a căuta în primul nod înainte de a împărți restul nodurilor de pe același nivel în paralel. Acest lucru se bazează pe observația că prima mutare fie va cauza o tăiere ( caz în care căutarea în restul nodurilor devine inutilă) sau va returna limite mult mai bune. Acest proces este recursiv.

Dynamic Tree Splitting

Este un algoritm complex, creat de echipa ce a dezvoltat jocul Cray Blitz. Deși oferă cea mai mare scalabilitate, nu este prea popular din cauza complexității. Algoritmul se aseamănă cu PVS până la un moment dat. Acesta analizează prima dată, folosind un singur procesor, ramura cea mai din stânga, apoi împarte celelalte noduri între procesoare. Noutatea vine atunci când un procesor își termină treaba și nu mai are alte noduri de preluat. În acest moment, „se oferă” ca ajutor altui procesor care este ocupat, pentru a-i prelua acestuia din sarcini. Astfel acesta din urmă alege o poziție în care se va face împărțirea. Procesul se repetă atunci când unul din cele 2 procesoare rămâne fără lucru.

1.4 Algoritmi alternativi

Cu toate că în prezent Alpha-Beta și derivații săi sunt algoritmii folosiți în aproape toate aplicațiile ce execută căutări în arbori Minimax, de-a lungul anilor au apărut alternative la căutarea în adâncime, dar care au fost repede abandonate.

Poate cel mai popular algoritm alternativ a fost SSS* ce folosește o tehnică de căutare „cel mai bun primul” (best-first). Creat de G. Stockman în 1977, algoritmul propunea o abordare total diferită față de Alpha-Beta. Arborele Minimax este construit parcurgând prima dată nodurile cele mai promițătoare, și nu în ordine cum se întâmplă la Alpha-Beta. Stockman spunea că SSS* domină Alpha-Beta prin faptul că nu va căuta niciodată în mai multe noduri decât acesta. Cu toate că rezultatele teoretice păreau promițătoare, acesta nu a fost aplicat în practică deoarece, necesită multă memorie, iar complexitatea sa îl face greu de paralelizat. Aceste dezavantaje îl fac să fie mai încet decât Alpha-Beta (și în special decât derivații săi) , astfel încât timpul salvat prin eliminarea unor noduri în plus din căutare nu este de ajuns.

Capitolul 2

Jocul de șah pe calculator

2.1 Istorie

Dintre primele mașini capabile să joace șah, cea mai populară a fost Thurk a lui Baron von Kempelen (1769). Aceasta s-a dovedit până la urmă a fi un fals, în realitate în interiorul cutiei se afla un om ce efectua mutările. Totuși în 1890 Torres y Quevedo, un inginer spaniol a conceput o mașină ce era capabilă să joace situația terminal de rege și tură împotriva regelui oponentului. În ciuda succesului acestei mașini mecanice, alte succese în automatizarea jocului de șah nu au mai apărut decât după 1940. În acel deceniu, entuziasmați de puterea crescândă a calculatoarelor, un număr mare de ingineri și matematicieni au început să studieze acest domeniu. Printre aceștia îi putem aminti pe Tihamer Nemes și Konrad Zuse care au încercat o abordare hardware, dar calculatorul lor capabil să joace șah nu s-a bucurat de o atenție largă.. Alții, ca de exemplu Alan Turing, au găsit succesul punând accentul pe o abordare bazată pe conceptul de program stocat. Articol lui Claude Shannon[13] despre algoritmii de jucat a fost citit si răscitit de pasionații de șah pe calculator, și a reprezentat bazele pentru programele de șah timpurii. În ciuda trecerii timpului, acest articol este încă recomandat pentru lectură[5].

2.2 Reprezentarea tablei

În șahul pe calculator dezvoltatorii programelor de șah trebuie să aleagă o structură de date ce va fi folosită pentru a reprezenta tabla de șah. Motoarele de șah folosesc deseori mai multe tipuri de reprezentări în diferite momente ale jocului, pentru eficiență.

O descriere completă a unei poziții de șah trebuie să conțină următoarele informații:

Locația fiecărei piese pe tablă

Cine trebuie să mute

Statusul regulii celei de-a 50-a mutare. Numele acestei reguli este oarecum confuz, deoarece presupune 50 de mutări din partea fiecărui jucător, deci 100 de mutări în total. Regula celei de-a 50-a mutare acordă dreptul oricărui dintre jucători de a declara remiză daca în ultimele 100 de mutări nu s-a mutat un pion sau nu s-a capturat nimic.

Dacă unul dintre jucători nu mai are dreptul de a efectua rocada.

Dacă o capturare en passant este posibilă.

Reprezentarea tablei nu include statusul regulii de 3 repetiții. Pentru a determina această regulă, se menține un istoric complet al mutărilor de la ultima capturare, mutare a pionilor sau mutări ce duc la pierderea dreptului de a face rocada într-o anume direcție. Deci, acest lucru este memorat, în general, în alte structuri de date.

În continuare vom prezenta succint câteva din tipurile de reprezentări folosite în programele de șah.

2.2.1 Liste de piese

Unele din cele mai vechi programe de șah lucrau cu memorie foarte limitată, încât si cele 64 de locații de memorie necesare reprezentării tabelei de șah erau un consum prea mare de memorie. Aceste programe țineau în schimb liste cu locațiile a până la 16 piese albe și negre. Listele de piese sunt încă folosite de multe din programele de astăzi, în conjuncție cu alte metode de reprezentare a tablei pentru a mări viteza de acces la piese. În loc să se parcurgă toate cele 64 de pătrate pentru a găsi toate piesele, listele oferă acces instant la ele.

2.2.2 Tablouri

Una din cele mai simple metode de a reprezenta o tablă este printr-un tablou bidimensional de dimensiune 8×8 (sau, un tablou uni-dimensional de 64 de elemente). Fiecare element al tabloului va identifica ce piesă ocupă un anume pătrat pe tablă sau dacă pătratul este gol.

O problemă cu această metodă apare atunci când se generează mutările. Fiecare mutare trebuie verificată pentru a nu depăși limitele tablei, încetinind astfel procesul. Programul SARGON original a extins tabela de 64 de octeți înconjurând-o cu două rânduri de pătrate „false” conținând santinele, marcând pătratele ca fiind ilegale. Această metodă a accelerat generarea de mutări: de exemplu, un nebun generează mutări parcurgând câte un pătrat până când ajunge într-o poziție ilegală. Nu mai sunt necesare calcule complicate pentru a verifica dacă o mutare nu scoate piesa de pe memoria asociată tabelei.  Al doilea rând de pătrate false este necesar pentru mutările calului: de exemplu, un cal aflat într-un colț al tablei ar putea încerca să sară în afara tablei cu 2 coloane, deci o singură linie de protecție nu e de ajuns.

Unele din motoarele de șah folosesc tablouri de dimensiune 16×16 pentru a mări viteza conversiei numărului liniei și coloanei și pentru a îngădui artificii speciale pentru atacuri.

2.2.3 Metoda 0x88

Metoda 0x88 profită de avantajul că dimensiunile tablei de șah sunt un multiplu al lui 2. Reprezentarea folosește un tablou de 16×8 = 128, numerotat de la 0 la 127. Sunt de fapt 2 table așezate una lângă cealaltă. Masca binară a unei coordonate legale este [0 r r r 0 f f f] (r r r – identificator linie, f f f – identificator coloană). Când sunt generate mutările, se poate face o verificare dacă mutarea este pe tablă aplicând un AND binar între numărul pătratului și 0x88 ([1 0 0 0 1 0 0 0]). Un rezultat diferit de 0 indică faptul că pătratul nu se află pe tablă. În plus, se poate afla foarte ușor dacă 2 coordonate sunt pe aceeași linie, coloană sau diagonală (util când se determină poziția de șah).

2.2.4 Tabele de biți

Una din metodele cele mai comune în ziua de azi sunt tabelele de biți. O tabelă de biți are dimensiunea de 64 biți, indicând prezența sau absența unei stări pentru fiecare locație pe tablă (0 sau 1). Astfel o poziție în tablă poate fi reprezentată printr-o serie de tabele de biți. Avantajul acestei reprezentări constă în abilitatea de a folosi operațiile pe biți asupra entităților de 64 de biți, folosind la maxim hardware-ul din ziua de azi, unde procesoarele de 64 de biți au apărut și pe calculatoarele personale.[2]

2.3 Generarea mutărilor

Șahul este un joc complex. În aproape orice situație, un jucător poate avea 30 sau mai multe mutări legale dintre care trebuie să aleagă, unele bune, altele sinucigașe. Jucătorilor umani cu experiență le este ușor să catalogheze majoritatea mutărilor proaste. Chiar și începătorii învață că le trebuie un plan solid înainte de a-și lăsa regina într-o poziție în care aceasta poate fi atacată. Maeștrii pe de altă parte știu care sunt cele mai bune 1-2 mutări într-o anume poziție (mai mult prin identificarea instinctivă a șabloanelor decât prin efort conștient). Totuși, codificarea acestor informații (în special cele inconștiente) într-un calculator s-a dovedit a fi o sarcină mult prea complexă, și cele mai bune programe de șah nu folosesc această abordare, ci folosesc metoda forței brute: dacă poți analiza toate mutările posibile într-un timp relative scurt și poți prezice consecințele pe termen lung în urma mutărilor respective, nu contează dacă nu pornești cu o idee clară asupra ce dorești să realizezi, pentru că la un moment dat vei descoperi o mutare bună.  Așadar, generarea mutărilor și căutarea ar trebui făcute cât mai eficiente, pentru a minimiza efortul necesar metodei forței brute.

De-a lungul timpului, 3 mari strategii de generarea a mutărilor au fost folosite:

Generarea selectivă: examinează tabla, selectează un număr de mutări „convenabile” și renunță la analiza restului de mutări.

Generare prin adăugare: Generează un număr mic de mutări, în speranța că una din ele se va dovedi atât de bună sau atât de proastă încât să poată fi întreruptă căutarea pe calea respectivă înainte de a genera restul mutărilor.

Generarea completă: Generează toate mutările, în speranța că tabela de transpoziții (descrisă în Capitolul I) va conține informații relevante despre majoritatea și nu va fi necesară efectuarea unei căutări.

Generarea selectivă (și metoda de căutare asociată numită „Forward Pruning”) a dispărut de la mijlocul anilor 1970.  Cât despre celelalte două, se poate spune că reprezintă două părți ale aceleași monezi, alegând între efortul de a genera mutările și căutare. 

2.3.1 Tăiere înainte (Forward Prunning)

În 1949, Claude Shannon a descris 2 metode de a crea un algoritm de jucat șah[13]:

Analizează toate mutările posibile, recursiv.

Examinează doar mutările “cele mai bune”, determinate din analiza detaliată a unei poziții, și mai apoi doar cele mai bune replici pentru fiecare dintre mutările găsite.

La început, a doua alternativă părea să aibă mai mult succes. Până la urmă, jucătorii umani gândesc în acest fel, și pare logic că examinând doar un număr mic de mutări pentru fiecare poziție va fi mai rapid decât dacă am examina toate mutările. Din păcate, rezultatele au contrazis această teorie: programele ce foloseau căutarea selectivă nu jucau bine.  În cel mai fericit caz, atingeau nivelul unui jucător începător spre mediu, comițând adesea gafe în cele mai proaste momente. Învingerea unui campion mondial era mult peste limitele lor.

Problema este că pentru a fi bun, un generator de “mutări bune” trebuie să fie aproape perfect.  Să presupunem că un program este dotat cu o funcție care obține cele mai bune 5 mutări într-o poziție, și că cea mai bună mutare se află în acele mutări în cel puțin 95% dintre cazuri (o presupunere îndrăzneață). Asta înseamnă că probabilitatea ca generatorul să aleagă întotdeauna cea mai bună mutare pe tot parcursul unui joc de 40 de mutări, este mai mică de 13%.  Chiar și un generator ieșit din comun, cu o acuratețe de 99% va eșua cel puțin o data într-o treime din jocurile sale, în timp ce o funcție cu o probabilitate mai rezonabilă de 90% va juca un joc întreg fără să facă o greșeală în mai puțin din 1.5% din cazuri!

În anii 1970, legendara echipă Northwestern formată din Slate și Atkin a decis să se abată de la această metodă; s-a dovedit că timpul necesar analizării mutărilor generate era destul încât să acopere costul efectuării unei căutări complete (examinarea tuturor mutărilor). Această descoperire a dus la abandonarea metodei de tăiere înainte.

2.3.2 Generarea tuturor mutărilor

Odată ce eliminăm din considerație metoda forward pruning, cea mai directă metodă de a efectua o căutare completă este:

Găsirea tuturor mutărilor legale dintr-o anume poziție

Ordonarea lor, printr-un anume mod, în speranța că va îmbunătății căutarea, alegând o ordonare avantajoasă.

Examinarea fiecărei mutări, rând pe rând, până când toate au fost analizate sau o teiere a avut loc.

Primele programe, de exemplu Sargon, au făcut acest lucru examinând tabla, pătrat cu pătrat, căutând piese ale jucătorului curent și calculând mutările posibile pe moment.  Memoria fiind limitata, costul timpului de procesor, necesar recalculării acestor mutări de fiecare dată era un rău necesar.

În zilele noastre, o structură de date pre-calculată poate economisi un număr mare de calcule, cu un cost de câțiva zeci de Kilo-octeți.  Când această metodă e combinată cu o tabelă de transpoziții, se obține un plus important de performanță : dacă chiar și o singură mutare a fost analizată în precedent, și dacă evaluarea ei produce o tăiere, nu va fi necesar să se mai analizeze nici o mutare. În mod evident, cu cât tabela de transpoziții este mai mare, și cu cât probabilitatea unei transpoziții într-un joc este mai mare, cu atât rezultatul este mai bun.

2.3.3 Generarea unei singure mutări pe rând

Programele de șah complexe începând de la CHESS 4.5 au adoptat o strategie opusă: generarea câtorva mutări la un moment dat, efectuarea unei căutări asupra lor, iar dacă o tăiere este posibilă asupra lor, nu va mai fi necesară generarea celorlalte mutări.

O combinație de factori au făcut această metodă populară:

Căutarea nu necesită multă memorie. Programele din anii ‘70 trebuiau să se mulțumească cu tabele de transpoziții mici, și nu își permiteau structuri de date pre-procesate pentru generarea mutărilor, limitând generarea completă descrisă mai sus.

Generarea mutărilor este mai complicată in șah decât în alte jocuri, diferitele tipuri de piese au reguli de mutare diferite, la care se adaugă mutările de tip en passant și rocadă.

Foarte des, o mutare ce implică o capturare a unei piese oponente duce la tăiere.  De exemplu, dacă jucătorul A lasă oponentului o regină fără apărare, acesta o va captura distrugând jocul jucătorul A.  Din moment ce, de obicei, sunt puține mutări ce duc la capturarea unei piese dintr-o anumită poziție, și din moment ce generarea separată a capturărilor este relative simplă, calcularea capturilor este deseori o condiție suficientă pentru a cauza o tăiere cu un cost redus.

Capturarea este una din puținele (daca nu și singura) mutări examinate în timpul etapei de ”liniște” (quiescence), așa că generarea lor separată este de două ori utilă.

Așadar, multe programe vor genera mutările ce duc la capturări prima dată, de obicei începând cu piesele de valoare mare, căutând o tăiere rapidă.  Un număr de tehnici au fost dezvoltate pentru a mări viteza generării, majoritatea implicând tabele de biți:

CHESS 4.5 menține 2 seturi de tabele de 64 de biți, una conține pătratele atacate de piesă (dacă acestea există), cealaltă conține toate pătratele ocupate de piese ce atacă acel pătrat.  Așadar, dacă programul caută mutări ce pot duce la capturarea reginei de negru, caută poziția sa (într-o tabela de biți), pe care o folosește în aceste 2 noi structuri pentru a determina piesele ce atacă regina, și generează mutări doar pentru aceste piese.

Menținerea acestor tabele de atac după fiecare mutare necesită o tehnică aparte, iar folosirea unor tabele de biți rotate poate accelera semnificativ munca.

2.4 Tehnici de căutare

Un program cu adevărat strălucit ar putea să determine cine are avantajul, cât de mare este acesta și ce plan ar trebui implementat pentru a profita de acest avantaj, analizând poziționarea pe tablă. Din nefericire există atât de multe șabloane de identificat, atât de multe reguli și atâtea excepții încât nici cele mai bune programe existente nu sunt capabile de acest lucru. Totuși programele se pot folosi de puterea mare de calcul pe care o oferă dispozitivul hardware.

În capitolul trecut am analizat algoritmul Minimax și modul în care acesta poate fi folosit în jocurile ce au 2 adversari. Alpha-Beta iterativ combinat cu o tabela de transpoziții (și o tabela de istoric pentru un plus de eficiență) îi îngăduie calculatorului să caute fiecare poziție relativ adânc, fiind capabil să joace o partidă rezonabilă de șah. Pe lângă aceste tehnici vom prezenta în continuare alte câteva tehnici avansate folosite în programarea jocurilor de șah.

2.4.1 Căutarea poziției de repaus (Quiescence search)

Până acum, algoritmii de căutare analizați căutau până la o anumită adâncime fixă. Totuși acest lucru este rareori benefic. De exemplu să presupunem că programul de șah folosește un algoritm Alpha-Beta iterativ cu adâncimea maximă 5. Să privim acum cazurile următoare:

De-a lungul unei anumite direcții de joc, programul descoperă o poziție în care unul din jucători este în șah-mat sau remiză la adâncimea 3.  În mod evident, nu se mai vrea continuarea căutării, pentru că starea finală a jocului a fost rezolvată.  Pe lângă efortul inutil de a căuta până la adâncimea 5, programul ar putea găsi o soluție ilegală!

Acum, să presupunem că la adâncimea 5, capturează un pion.  Programul ar decide că această poziție este una favorabilă și ar putea alege o mutare care să ducă spre această poziție. Totuși, dacă ar fi fost analizată încă o mutare în adâncime ar fi descoperit că acea capturare este una dezastroasă, lăsând regina fără apărare.

În final, să presupunem că regina este blocată. Orice ar face, regina va fi capturată la mutarea 4, cu o excepție, când acest lucru se va întâmpla la poziția 6.  Dacă programul execută o căutare până la adâncimea 5, direcțiile în care regina e capturată la poziția 4 vor fi examinate cu acuratețe, și punctate ca fiind dezastruoase.  Totuși, pe direcția în care regina este capturată la mutarea 6 (în afara arborelui de căutare) programul nu descoperă capturarea, considerând regina într-o poziție sigură, dându-i un scor mult mai bun. Acum, dacă tot ce ar trebui programul să facă pentru a amâna capturarea reginei este de a amâna adversarul cu o diversiune, acest risc ar putea da roade. Deși acest lucru ar putea duce la un dezavantaj pozițional, l-ar putea face pe adversar să greșească, îngăduindu-i reginei să scape.  Dar dacă singura metodă de a amâna capturarea reginei este de a sacrifica turnul?  Pentru calculator, a pierde un turn la mutarea 4 este mai puțin distructiv decât pierderea unei regine, deci ar ceda turnul, fără a știi că în afara arborelui de căutare urmează o capturare inevitabilă a reginei.   Hans Berliner a descris acest "efect de orizont" cu mult timp în urmă.

Concluzia este că multe poziții în șah sunt prea haotice pentru a fie evaluate corect. O funcție de evaluare poate fi aplicată doar pe pozițiile liniștite, unde probabilitatea ca o întorsătură să se producă în viitorul imediat este minimă.

Există 2 moduri de a evalua o poziție: evaluare dinamică (privește la ce ar putea duce poziția respectivă) și evaluare statică (privește cum arată la momentul dat, fără a lua în calcul consecințele).  Evaluarea dinamică este realizată prin căutare. Evaluarea statică este, după cum am amintit mai sus, posibilă doar în poziții în care nu se vor întâmpla schimbări drastice a balanței în viitorul apropiat. Aceste poziții relativ stabile se numesc „liniștite” și sunt identificate prin căutarea repausului (quiescence search).

Conceptul de bază al acestei căutări este următorul: odată ce programul a căutat până la o anumită adâncime, continuăm căutarea pe fiecare direcție de joc, selectiv, căutând doar mutările “neliniștite”, până când găsim o poziție liniștită, și doar atunci se aplică funcția de evaluare.

Găsirea unei poziții liniștite necesită cunoștințe despre joc. De exemplu, ce mutări pot cauza o schimbare drastic a balanței pe tablă? Pentru șah, balanța materială are o pondere foarte mare în evaluare, deci orice mutare ce schimbă balanța materială trebuie luată în considerare: capturile (în special cele ale pieselor importante) și promoțiile pionilor, și chiar șahul poate fi luat în considerare (poate că va duce la șah-mat). 

2.4.2 Mutarea nulă

Una din cele mai eficace metode de a mări viteza unui program de șah este de a introduce conceptul de mutare nulă în ecuație.

Mutarea nulă constă în a sări tura și a lăsa oponentul să joace 2 mutări la rând.  În majoritatea pozițiilor a nu face nimic este o idee proastă. Aproape întotdeauna ar trebui să poți să îți îmbunătățești situația mutând.

Totuși îngăduindu-i calculatorului să încerce mutarea nulă în timpul căutării duce la o serie de avantaje legate de viteză și acuratețe. De exemplu:

Să presupunem că o poziție este atât de mult în favoarea ta, încât chiar dacă ai sări rândul, adversarul nu poate răspunde cu nimic să-l ajute.  (În termenii programării, s-ar obține o tăietură beta fără nici o mutare)  Să presupunem în continuare că această mutare este planificată să fie analizată până la adâncimea N.  Mutarea nulă, efectuată, sustrage un întreg sub-arbore din arborele de căutare (se caută doar mutarea nulă, în locul tuturor celor legale) și dacă factorul de ramificare este B, aplicarea mutării nule este echivalentă cu a căuta într-un singur arbore de dimensiune N-1 și nu în B sub-arbori.  Cu B=35 ca fiind factorul de ramificare tipic într-un joc de șah, căutarea folosind mutarea nulă ar consuma 3% din resursele necesare unei căutări complete de adâncime N.  Dacă această căutare arată că ești foarte puternic chiar și fără a juca (creează o tăietură), s-a salvat 97% din efort; dacă nu, trebuie examinate toate mutările ca de obicei, și s-a pierdut doar 3% din performanță.  În medie, avantajul este mare.

Acum, să presupunem că în timpul „căutării de repaus”, se analizează o poziție în care singura mutare legală este: turnul capturează pionul, urmată de mutarea oponentului calul capturează turnul.  Ar fi mult mai avantajos să nu se efectueze această capturare, și să se efectueze orice altă mutare ce nu duce la capturare.  Se poate simula această situație introducând mutarea nulă în algoritmul de căutare a repausului: dacă, într-o anume poziție în timpul căutării, se dovedește că mutarea nulă este mai bună decât orice capturare, se poate presupune că a continua capturările este o idee proastă, și deoarece cea mai bună mutare este una liniștită, aceasta este o poziție în care ar trebui aplicată funcția de evaluare.

În medie, euristica mutării nule poate aduce beneficii de calcul între 20% și 75%.  Efortul pare să merite, implementarea acestei metode fiind destul de simplă.

2.4.3 Extensii singulare

În șah, unele mutări sunt în mod evident mai bune decât altele, și poate nu ar fi necesar să fie pierdut timpul analizând celelalte alternative.

De exemplu, să presupunem că după ce am parcurs algoritmul iterativ până la adâncimea N-1, am descoperit că una din mutări valorează 9000 (de ex: capturarea unei regine a oponentului) iar celelalte sunt sub 0. Dacă luăm în considerare economisirea timpului, de exemplu în turnee, am putea sări peste căutarea întreg nivelului N și să analizăm doar mutarea cea mai bună la nivelul N: dacă această mutare nu scade mult valoarea, atunci putem presupune că celelalte mutări nu vor putea ajunge din urmă această valoare și putem opri căutarea timpuriu.  (De reținut că dacă există 35 de mutări valide în medie, am economisit 97% din efort!).

Echipa ce a creat mașina Deep Blue a împins această idee cu un pas mai departe, și au implementat conceptul de „extensii singulare”. Dacă, la un moment dat în căutare, o mutare pare să fie mult mai bună decât alternativele, atunci va fi examinată cu un nivel în plus pentru a se asigura că nu există capcane ascunse. Extensiile singulare sunt costisitoare: adăugarea unei mutări în plus de analizat aproape dublează numărul de frunze în arbore, cauzând un număr mult mai mare de apeluri ale funcției de evaluare.

2.4.4 Tabele de memorie

Tabelele de hashing pot avea și alte întrebuințări decât folosirea lor ca tabele de transpoziții. Un prim rol adițional îl au în deschideri. Deoarece la începutul jocului pozițiile sunt foarte deschise, necesitând multe calcule pentru căutare, se poate pre-calcula o listă cu mutările puternice. O astfel de listă reduce dramatic numărul de calcule pentru primele mutări (aproximativ primele zece). Mutările de început pot fi alese din numeroasele strategii de deschidere existente în literatura de șah. Astfel programul poate începe defensiv, sau poate porni un joc deschis. Același principiu se poate aplica și pentru închideri (când rămân puține piese pe tablă, maxim 4-5). Astfel folosind o tabelă de închidere, un joc de șah poate deveni imbatabil pe final, sau poate recupera dezavantajul prin efectuarea mutării optime de fiecare dată.

O altă utilizare a tabelelor de hashing este pentru a memora informațiile despre formațiile de pioni. Din moment ce există mult mai multe mutări efectuate de alte piese decât de pioni, valoarea formației de bază a pionilor trebuie recalculată de mai multe ori. Se poate construi o cheie de hash folosind doar locațiile pionilor, iar valorile formațiilor de pioni pot fi stocate într-o tabelă de hash, pentru acces imediat. Hyatt a dovedit că această tabelă este utilă, deoarece 10-20% din timpul de calcul este folosit pentru evaluarea formațiilor de pioni. Metoda a dat o rată mare de succes (98-99%). Această metodă poate fi extinsă și pentru verificarea siguranței regelui, deoarece regale execută puține mutări, și pentru perioade lungi, nu este atacat.

2.5 Funcția de evaluare

Funcția de evaluare are un rol aparte, deoarece spre deosebire de tehnicile de căutare, care sunt generice, și generarea mutărilor, care poate fi dedusă din regulile jocului, evaluarea necesită o analiză aprofundată a strategiei. După cum vă puteți imagina, este imposibil de a determina valoarea relativă a unei poziții dacă nu știi ce particularități pot duce la victoria unui jucător sau a celuilalt. Așadar, multe din conceptele discutate mai jos se pot aplica foarte puțin sau chiar deloc în alte jocuri.

2.5.1 Balanța materială

Balanța materială este un bilanț asupra pieselor rămase pe tablă, pentru fiecare parte. Potrivit literaturii de șah o regină valorează aproximativ 900 puncte, o tură 500, un nebun 325, un cal 300 și un pion 100; regele are valoare infinită. Calcularea balanței materială este așadar simplă: valoarea materială a unei părți este: BM = Suma( Np * Vp), unde Np este numărul de piese de un anumit tip pe tablă și Vp este valoarea piesei. Dacă o parte are o balanță materială mai bună decât adversarul, atunci acea parte este într-un oarecare avantaj.

Balanța materială este cel mai important factor într-o funcție de evaluare. Creatorii programului CHESS 4.5 estimează că un avantaj mare în poziție, mobilitate și siguranță valorează mai puțin de 1.5 pioni. De fapt, se poate juca șah decent, fără a lua în considerare altceva!

Desigur, există poziții în care se merită sacrificial unei piese (câteodată și o regină) în schimbul unui avantaj în joc. Acestea sunt totuși cel mai bine descoperite prin căutare: dacă sacrificiul unei regine duce la șah-mat în 3 mutări, algoritmul de căutare va găsi acest lucru fără a fi necesare alte verificări.

Totuși foarte puține programe folosesc o asemenea funcție primitivă. Deoarece surplusul de calcul este minim, sunt introduse evaluări adiționale. De exemplu, este bine știut că dacă un jucător are avantaj material, capturarea reciprocă de piese de aceeași valoare este avantajoasă. Schimbul de pioni este de obicei o idee bună, pentru că deschide tabla, dar este de preferat menținerea majorității pionilor pe masă până aproape de final pentru o defensivă cât mai bună și pentru a putea promova. Totodată, trebuie avut în vedere ca programul să nu se panicheze dacă face o mutare din tabela de deschidere ce duce la sacrificarea unui pion, adăugându-i un plus în evaluarea materială.

2.5.2 Mobilitatea și controlul tablei

Una din caracteristicile șahului-mat este că oponentul nu mai are mutări legale de făcut. Intuitiv, a avea mai multe posibilități duce la un avantaj: probabilitatea de a găsi o mutare bună dacă un jucător are 30 de mutări legale este mai mare decât dacă poate efectua doar 3 mutări legale.

În șah, mobilitatea este evaluată ușor: se calculează numărul de mutări legale pentru fiecare parte, pentru o anume poziție. Totuși, această statistică s-a dovedit a nu avea o valoare mare în luarea unei decizii. De ce? În primul rând multe mutări în șah nu își au rostul. Chiar dacă este legal să muți tura câte o poziție, este rareori productiv. Alt motiv este acela că, încercând să limitezi mutările oponentului cu orice cost ar putea conduce programul în a-și strica propria defensivă în căutarea „șahurilor inutile”, deoarece de obicei sunt mai mult de 3-4 mutări de a evada din șah, astfel un program care pune accent pe mobilitate ar putea face mutări imprudente realizând mai târziu că nu a obținut nimic, ci doar și-a împrăștiat piesele pe tablă.

Totuși, câteva evaluări sofisticate în privința mobilității sunt întotdeauna un lucru bun. De exemplu ar putea fi penalizați nebunii a căror mutări sunt blocate de o serie mare de pioni pe aceeași culoare, caii ce stau prea aproape de marginea tablei, ture ce nu au un drum liber (sunt blocate de piese de aceeași culoare).

În strânsă legătură cu mobilitatea se află controlul tablei. În șah, o parte controlează un pătrat dacă are mai multe piese ce îl atacă decât oponentul. De obicei mutarea într-o poziție controlată este sigură, iar mutarea într-o poziție controlată de oponent este dezastruoasă. Există și excepții: mutarea reginei pe un pătrat atacat de un pion oponent este rar o idee bună, indiferent de numărul de moduri în care poți captura acel pion după ce a capturat regina. De asemenea poți pune voluntar o piesă în pericol pentru a conduce un apărător de pe o poziție și mai valoroasă. În șah, controlul centrului tablei este un țel fundamental în deschidere. Totuși controlul este dificil de calculat: necesită menținerea unei baze de date cu toate pătratele atacate de toate piesele de pe tablă în orice moment.

În timp ce mobilitatea este mai puțin importantă într-un joc de șah, este foarte importantă într-un joc de Othello, unde partea cu cele mai puține mutări posibile la sfârșit este în mare încurcătură. Cât despre controlul tablei, este condiția necesară victoriei în Go.

2.5.3 Dezvoltarea

O maximă veche în șah este că piesele minore (nebunii și caii) ar trebui aduși în luptă cât mai curând posibil, că regele ar trebui să facă rocada cât mai repede și că turele și regina ar trebui să rămână în defensivă până când este momentul pentru un atac decisiv. Există multe motive pentru acest lucru: caii și nebunii (și pionii) pot controla centrul, sprijină atacurile reginei, și mutarea lor din locul inițial eliberează linia de fund pentru ture.

În evaluarea dezvoltării pot fi luați în considerarea următorii factori: penalizarea pozițiilor în care pionii din fața regelui și a reginei nu au fost mutați, penalizarea cailor și a nebunilor localizați pe linia de fund, unde blochează mutările turei, încercarea de a menține regina în poziția inițială până ce restul pieselor au fost mutate, acordarea unui bonus substanțial atunci când regele efectuează rocada (și bonusuri mai mici atunci când regele nu a efectuat încă rocada, dar mai are această posibilitate) atunci când adversarul are o regină pe tablă. Așadar, dezvoltarea are un rol important în deschidere, dar își pierde din această importanță rapid. După aproximativ 10 mutări, aproape tot ce poate fi măsurat aici s-a întâmplat deja.

2.5.4 Formațiile pionilor

Maeștrii șahului spun deseori că pionii sunt sufletul jocului. În timp ce această afirmație este greu de acceptat pentru un începător, faptul că marii jucători cedează jocul după pierderea unui singur pion dovedește că această afirmație este adevărată.

Literatura de șah menționează câteva tipuri de formații de pioni, unele cu valoare pozitivă, altele negative. Câteva dintre ele sunt:

Pioni dublați sau triplați. Doi sau mai mulți pioni de aceeași culoare pe aceeași coloană sunt de obicei un dezavantaj, pentru că își împiedică unul altuia mutările.

Pioni în blocaj. Doi pioni de culori opuse unul în fața celuilalt, blocându-și astfel mutările unul altuia, reprezintă un obstacol enervant.

Pioni avansați. Pionii ce au avansat atât de mult încât nu mai pot fi atacați sau blocați de pionii oponenți sunt foarte puternici, fiind o amenințare dacă ajung pe ultima linie promovând astfel.

Pioni izolați. Un pion ce nu are pioni de aceeași culoare în una din vecinătățile sale este vulnerabil la atac și ar trebui să caute protecție.

Opt pioni. A avea prea mulți pioni pe tablă reduce mobilitatea; deschiderea cel puțin a unei coloane pentru a lăsa cale liberă turei este o idee bună.

O notă finală la formațiile de pioni: un pion avansat este foarte periculos dacă are o tură în spatele său, pentru că orice piesă care încearcă să captureze pionul este sortită pierzaniei. Așadar, în evaluarea pionului acestuia i se acordă o valoare mai mare dacă are o tură in spatele său.

2.5.5 Siguranța regelui și tropismul

Am atins deja subiectul de siguranță a regelui mai devreme: în deschidere și la mijlocul jocului protejării regelui trebuie acordată o importanță mare, și rocada este cel mai bun mod de a o face.

Totuși, spre finalul jocului, majoritatea pieselor din ambele părți sunt capturate, iar regele devine deodată unul din cele mai bune arme de atac. Ascunderea lui după un zid de pioni însemnă risipă de resurse.

Cât despre tropism, este măsurat în cat de ușor îi este unei piese să atace regele oponent, și de obicei este măsurat în distanța dintre cele două piese. Regulile exacte de a calcula tropismul variază în funcție de tipul de piesă dar se reduc la următoarea regulă: cu cât ești mai aproape de regele oponent, cu atât mai mult impui presiune asupra lui.

2.5.6 Alegerea corectă a ponderilor

Odată identificați factorii ce trebuie măsurați, trebuie alese ponderile ce le atribuim fiecăruia.

Acest lucru este cheia succesului. Dezvoltatorii de programe petrec deseori ani întregi jucându-se cu aceste ponderi în funcția de evaluare, uneori acordând ai multă importanță mobilității, alteori siguranței, etc. Nu există o soluție absolută. Totul se reduce la teste și metoda învățării din greșeli. Dacă programul nu joacă destul de bine, ponderile pot fi ajustate, testând noul rezultat prin confruntarea noii versiuni de program cu versiunea veche. Dacă în majoritatea cazurilor câștigă, noua variantă este o îmbunătățire. [4]

Câteva lucruri ce trebuie avute în vedere:

Este foarte dificil de perfecționat o funcție de evaluare astfel încât să se obțină o performanță echivalentă cu analizarea încă unei mutări în adâncime. Evaluarea trebuie să fie cât mai simplă, lăsând puterea de procesare algoritmului de căutare.

Dacă nu dorești ca programul tău să învingă campionul mondial, funcția de evaluare nu trebuie să fie foarte puternică!

Capitolul 3

Proiectarea jocului de șah

În continuare vom prezenta, pe scurt, pașii necesari în crearea unui program capabil să joace șah cu un utilizator, sau cu el însuși. Programul va prezenta o interfață grafică familiară, în care utilizatorul va putea juca fără mari dificultăți.

3.1 Reguli de bază

Primul pas în proiectarea unui joc de șah este documentarea asupra regulilor jocului. Șahul este un joc ce se joacă pe o tablă împărțită în 64 de pătrate alternând în câmpuri de culoare deschisă și câmpuri de culoare închisă. Se dispută între 2 parteneri ce au fiecare câte 16 piese (8 pioni, 2 cai, 2 nebuni, 1 regină și 1 rege). Scopul jocului este de a lăsa regele adversarului încolțit, fără ca acesta să mai aibă posibilitatea să scape de capturare. Atunci când nici unul din jucători nu poate câștiga, partida este declarată remiză.

La începutul jocului, piesele trebuie aranjate ca in figura de mai jos:

Tabla trebuie așezată între jucători în așa fel, încât fiecare dintre ei să aibă la dreapta sa un pătrat alb, în colțul tablei de șah. Fiecare pătrat este identificat prin combinația unică dintre o cifră (1 – 8) pentru numărul liniei și o literă (a – h) ca identificator al coloanei (vezi figura de mai sus).

Fiecare jucător are controlul asupra unuia dintre cele 2 seturi de piese colorate. Albul mută întotdeauna primul, și ca în majoritatea jocurilor pe tablă, jucătorii alternează la mutare.

Fiecare tip de piesă are propriul stil de mutare. Mutările sunt posibile doar în locurile libere, excepție făcând capturarea unei piese inamice. Cu excepția calului, piesele nu pot sări una peste alta. Când o piesă este capturată, piesa ce o capturează trece în locul ei (excepție face mutarea en-passant). Regele poate fi atacat, dar nu poate fi capturat. Piesele pot executa mutări după cum urmează:

Calul – o mutare constă în deplasarea a două pătrate pe orizontală/verticală și încă un pătrat perpendicular cu acea direcție (mutare în formă de L).

Nebunul – poate se muta în orice pătrat liber de pe diagonale.

Turnul – poate muta în orice pătrat liber pe orizontala/verticală.

Regina – poate muta în orice pătrat liber pe diagonală, orizontală sau verticală

Regele – poate se poate muta doar într-un pătrat vecin pe diagonală, verticală sau orizontală. El nu poate muta într-o poziție în care este atacat.

Pionul – poate muta un pătrat înainte, dacă pătratul este neocupat. Dacă nu a fost mutat încă, pionul poate fi mutat și două pătrate înainte, cu condiția ca ambele pătrate să fie neocupate. Pionii sunt excepția de la regulă la capturare. Pot captura piesele din cele două pătrate de pe diagonala din fața pionului, dar nu se pot muta în acele locuri dacă sunt neocupate.

Mutări speciale:

Rocada – constă în mutarea regelui cu 2 pătrate spre turn, și plasarea apoi a turnului în cealaltă parte a regelui. Rocada este posibilă doar dacă toate condițiile următoare sunt împlinite:

Regele și tura implicată în rocadă trebuie să nu fi fost mutate în prealabil.

Nu trebuie să existe nici o piesă între rege și turn.

Regele nu trebuie să plece din șah, să treacă printr-un pătrat amenințat și nici să ajungă în șah.

En passant – Dacă jucătorul A mută pionul 2 pătrate în față și jucătorul B are un pion pe a cincea linie (prima linie – linia sa de fund) și pe o coloană adiacentă, pionul jucătorului B poate captura pionul jucătorului A ca și când acesta ar fi înaintat cu un singur pătrat. Această captură poate fi efectuată doar la mutarea imediat următoare.

Promovarea pionilor – Dacă un pion avansează la linia 8 pentru el, este promovat (convertit) într-o regină, un cal, nebun sau un turn, alegerea rămânând jucătorului. Alegerea nu este limitată de capturile precedente, deci teoretic este posibil ca un jucător să aibă nouă regine sau zece turnuri, nebuni sau cai.

3.2 Specificații

Reprezentarea tablei

Următorul pas ce trebuie urmat este alegerea modului de reprezentare a tablei, deoarece va influența foarte mult dezvoltarea ulterioară a aplicației.

După analizarea mai multor metode de reprezentare ne-am oprit la reprezentarea prin metoda 0x88. Cu toate că reprezentarea prin tablouri de biți pare o alegere mai bună, beneficiul de performanță fiind mai mare, am ales prima metodă, deoarece programul se vrea a fi unul cu scop didactic, iar prin această reprezentare codul e mai ușor de înțeles.

În capitolul precedent am prezentat principalul avantaj al utilizării metodei 0x88, acela de a efectua foarte ușor verificări dacă printr-o mutare se ajunge într-o poziție ilegală, simplificând astfel calculele. Așadar, se va folosi un tablou de 128 de elemente, fiecare având dimensiunea de 1 octet. Se observă că jumătate din spațiul alocat nu este folosit. Pentru a nu irosi memoria în această jumătate vom stoca câteva informații adiționale, despre care vom vorbi mai jos.

Reprezentarea pieselor

Următoarea decizie ce trebuie luată este modul de a reprezenta piesele. Pentru reprezentarea unei piese vom folosi cei 8 biți disponibili astfel: pentru tipul și culoarea piesei vor fi folosiți cei mai nesemnificativi 4 biți: primul bit reprezintă culoarea (0 alb, 1 negru), iar tipul piesei este codificat în felul următor: pion=0, cal=2, nebun=4, turn=6, regină=8, rege=10. De exemplu regele de negru va avea valoarea 11 (1011 în binar). Următorii 4 biți vor fi folosiți pentru a atașa un identificator unic piesei. Acest identificator va fi folosit pentru a calcula un indice într-un alt tablou ce va păstra pozițiile fiecărei piese (necesar pentru îmbunătățirea vitezei accesului la piesele disponibile). Fizic acest de-al doilea tablou face parte tot din tabloul folosit pentru reprezentarea tablei (vezi figura 3.2), utilizând astfel o parte din memoria nefolosită. Astfel de fiecare dată când o piesă va fi mutată, sau capturată, indicele elementul ce conține poziția acestuia poate fi modificat rapid, indicele acestuia putând fi calculat relativ ușor, cu următoarea formulă: 8+(index modulo 8)+[index/8]*16+culoare*32, unde culoare poate fi 0 sau 1.

Generarea mutărilor

Pentru o anumită poziție se generează toate mutările legale. Folosind reprezentarea curentă, se pot face ușor deplasări ale pieselor pe tablă verificându-se dacă aceste mutări sunt pseudo-legale (nu se verifică încă daca mutarea lasă jucătorul în șah, sau dacă o rocadă este ilegală, regele trecând printr-o poziție atacată, pentru că acest lucru este costisitor; acest lucru se va face la căutare, deoarece putem avea o tăiere și să nu fie necesar să analizăm toate mutările).

Căutarea

Pentru aflarea celei mai bune mutări de către calculator se folosește varianta MTD(f) a algoritmului minimax. Această implementare depinde foarte mult de folosirea unei tabele de transpoziții, tabela ce va folosi metoda lui Zobrist pentru generarea unui hash pentru o poziție dată pe tablă. Această metodă constă în generarea aleatoare a unor șiruri de biți, fiecare șir reprezentând ce piesă se află pe un anumit pătrat, și aplicarea operației XOR pe acele șiruri ce sunt adevărate (piesa X se găsește pe pătratul Y).

Pentru a optimiza și mai mult algoritmul de căutare, după generarea mutărilor, acestea vor fi ordonate, folosind o tabela de istoric, având prioritate mutările cu scor mare. Tabela de istoric va conține 128*128*2 elemente, adică fiecărei mutări posibile de pe tablă îi va fi asociat un scor (diferit pentru fiecare jucător). Atunci când o mutare generează o tăiere, scorul mutării va fi incrementat. Tabela istoric va fi golită periodic pentru a evita ordonarea mutărilor după rezultate vechi din căutare.

Pentru căutarea stării de liniște se iau în considerare doar mutările ce duc la o captură.

Evaluarea

Evaluarea unei poziții este dată de formula: valoarea materială + siguranța regelui + poziționarea turelor + poziționarea nebunilor + dezvoltarea. Prima dată va fi verificată balanța materială, iar dacă aceasta înclină mult către o parte nu se vor face și restul evaluărilor, deoarece șansele ca cealaltă parte să recupereze din dezavantaj sunt mici. Calculul valorii materiale este unul necostisitor și arată in felul următor: min( 2400, diferența_materială) + ( diferența_materială * ( 12000 – suma_val_materială) * număr_pioni_culoare_câștigătoare) / ( 6400 * (număr_pioni_culoare_câștigătoare + 1 ) )

Interfața cu utilizatorul

Interfața cu utilizatorul va trebui să cuprindă o reprezentare a tablei de șah, cu forma pieselor de șah apropiată de cele răspândite, astfel încât acesta să le poată recunoască ușor. Utilizatorul va putea să mute o piesă prin selectarea ei și alegerea pătratului de destinație. Odată ce o mutare va fi efectuată aceasta trebuie notată într-o listă ce cuprinde istoricul mutărilor, în caz că se dorește analizarea ulterioară a partidei. Timpii în care fiecare jucător mută trebuie cronometrați și afișați în caz că utilizatorii doresc să joace după regulile de turneu, în care timpul este limitat.

3.3 Proiectare

Având aceste detalii, putem proiecta diagramele de clase pentru pachetul Logic:

Iar pentru interfața cu utilizatorul diagrama de clase arată in felul următor:

Cazuri de utilizare:

Utilizator – Începe un joc nou

Din meniul principal utilizatorul alege opțiunea „Joc Nou”, apărând astfel o fereastră în care acesta poate selecta tipul fiecărui jucător (uman sau calculator). Odată selectat acesta apasă butonul „OK” astfel începând un nou joc.

Utilizator – Efectuează o mutare

Utilizatorul poate muta selectând o piesă și alegând pătratul în care aceasta va fi mutată. Se verifică dacă mutarea este validă, iar dacă este se aplică, verificându-se apoi dacă jocul este într-o stare finală (remiză, sau unul dintre jucători câștigă).

Utilizator – Cedează jocul adversarului

Atunci când unul dintre jucători decide că nu mai are șanse să recupereze dezavantajul față de oponent, poate ceda partida, fără a fi nevoit să aștepte finalul previzibil. Pentru a face acest lucru trebuie să selecteze din meniul „Fișier”, opțiunea „Cedează jocul curent”.

Utilizator – Oprește jocul temporar

Utilizatorul poate opri temporar jocul, oprind astfel ceasurile și neîngăduind nici unei părți să mute. Acest lucru îl face selectând opțiunea „Pauză joc” din meniul „Fișier”. Pentru a reîncepe jocul, utilizatorul va selecta opțiunea „Stop pauză” nou apărută.

Utilizator – Părăsește aplicația

Utilizatorul poate părăsi aplicația accesând opțiunea „Ieșire” din meniul „Fișier”.

Calculator – Efectuează mutare

Calculatorul va trebui să calculeze (folosind algoritmul MTD(f)) o mutare atunci când îi este rândul. Va trebui să facă acest lucru în fundal, fără a bloca interfața utilizatorului. Odată ce a calculat mutarea, va notifica aplicația, aplicând astfel mutarea.

3.4 Implementare

Limbajul ales pentru dezvoltare este Java. Cu toate că folosind acest limbaj nu vom avea o exploatare la maxim a puterii de calcul (programul fiind rulat pe o mașină virtuală, deci cu un surplus de calcul), avem totuși avantajul că aplicația va fi independentă de platformă, Java fiind implementat pe o serie de sisteme de operare. De asemenea în anumite situații aplicația poate fi mai performantă decât un program compilat fără a ține cont de trăsăturile avansate ale procesoarelor, lucru pe care Java îl are în evidență. Vom prezenta câteva metode cu un rol important în implementarea aplicației, discutându-le puțin.

Prima metodă prezentată este cea a generării mutărilor. Este o funcție generică ce folosind un tablou cu coeficienți de deplasare poate genera mutări pentru toate piesele ce se pot deplasa mai mult de 1 pătrat (regină, nebun, tură). Funcția pentru cal și rege este asemănătoare, singura modificare fiind că după executarea mutării nu se mai caută în continuare mutări pe calea curentă. În plus pentru pion și rege există metode adiționale pentru a trata cazurile speciale.

private boolean GenerateMultiDeltaMoves(int pos,int[] deltas) {

int curPiece=board.getSquareAt(pos);

for (int i=0;i<deltas.length;i++) {

int newPos=pos+deltas[i];

while (Board.isOnBoard(newPos)) {

Piece piece=board.getPieceAt(newPos);

if(piece.isEmpty()||(board.getSideToMove()!= piece.getColor())) {

Move move = new Move();

move.Source = pos;

move.Destination = newPos;

move.Piece = curPiece;

if (piece.isEmpty()) {

move.Type=Move.MOVE_NORMAL;

moves.add(move);

}

else {

move.Type=Move.MOVE_CAPTURE_ORDINARY;

if (piece.getPieceType()==Piece.KING)

return false; //illegal move

move.CapturedPiece=piece.getPiece();

moves.add(move);

break;

}

}

else break;

newPos+=deltas[i];

}

}

return true;

}

Următoarea metodă implementează algoritmul MTD(f). Această metodă este apelată de mai multe ori, de fiecare dată crescându-se adâncimea până la care căutăm. Nu vom descrie din nou partea teoretică a algoritmului. Singurul lucru diferit față de algoritmul prezentat în primul capitol este acela ca algoritmul a fost modificat pentru a întoarce o mutare și nu doar valoarea minimax.

private MoveMTDF( Board theBoard, int target, int depth ) {

int beta;

Move Mov;

int estimate = target;

int upperbound = ALPHABETA_MAXVAL;

int lowerbound = ALPHABETA_MINVAL;

// execută apeluri repetate ale algoritmului alpha-beta, apropiindu-ne de valoarea minimax, strângând limitele

do {

if ( estimate == lowerbound )

beta = estimate + 1;

else

beta = estimate;

Mov = UnrolledAlphaBeta( theBoard, depth, beta – 1, beta );

estimate = Mov.MoveEvaluation;

if ( estimate < beta )

upperbound = estimate;

else

lowerbound = estimate;

} while ( lowerbound < upperbound && !mustStop );

return Mov;

}

Un rol important în căutare îl are funcția ce verifică dacă un pătrat este atacat. Aceasta va fi apelată pentru fiecare mutare ce urmează a fi analizată pentru a verifica dacă aceasta este validă (regele nu rămâne atacat, sau la efectuarea unei rocade regele nu trece prin pătrate atacate).

public final boolean isAttacked(int side,int square) {

// verifică diagonalele

for (int i=0;i<Diagonals.length;i++) {

int newPos=square+Diagonals[i];

while(Board.isOnBoard(newPos)&&getSquareAt(newPos)==Piece.PIECE_NONE){

newPos+=Diagonals[i];

}

if (Board.isOnBoard(newPos)) {

Piece piece=getPieceAt(newPos);

if (piece.getColor()!=side && (piece.getPieceType()==Piece.BISHOP || piece.getPieceType()==Piece.QUEEN))

return true;

}

}

// verifică vertical și orizontal

for (int i=0;i<RookDeltas.length;i++) {

int newPos=square+RookDeltas[i];

while (Board.isOnBoard(newPos) && getSquareAt(newPos)==Piece.PIECE_NONE) {

newPos+=RookDeltas[i];

}

if (Board.isOnBoard(newPos)) {

Piece piece=getPieceAt(newPos);

if (piece.getColor()!=side && (piece.getPieceType()==Piece.ROOK || piece.getPieceType()==Piece.QUEEN))

return true;

}

}

// verifică mutările calului

for (int i=0;i<KnightDeltas.length;i++) {

int newPos=square+KnightDeltas[i];

if (Board.isOnBoard(newPos)) {

Piece piece=getPieceAt(newPos);

if (piece.getColor()!=side && piece.getPieceType()==Piece.KNIGHT)

return true;

}

}

// verifica daca este atacat de un pion

int sign;

if (side==Player.PLAYER_WHITE)

sign=+1;

else

sign=-1;

for (int i=0;i<2;i++) {

int newPos=square+sign*Diagonals[i];

if (Board.isOnBoard(newPos)) {

Piece piece=getPieceAt(newPos);

if (piece.getColor()!=side && piece.getPieceType()==Piece.PAWN)

return true;

}

}

return false;

}

În interfața cu utilizatorul, un rol important îl au metodele ce desenează tabla de joc. Mai jos este prezentată metoda principală ce face acest lucru, metodă care va apela la rândul ei o alta ce va face desenarea propriu-zisă pentru o celulă. Pentru evitarea efectului de flicker se va desena întâi într-o imagine tampon, urmând ca apoi să se facă desenarea efectivă pe componenta vizibilă.

private void paintBoard(Graphics g) {

if (!gamePaused) {

final String letters="abcdefgh";

//desenează doar partea ecranului ce a fost modificată

Rectangle clipRec=g.getClipBounds();

if (clipRec==null) return;

Point topLeftCell=getCellCoords(clipRec.x, clipRec.y+clipRec.height);

Point BottomRightCell=getCellCoords(clipRec.x+clipRec.width, clipRec.y);

//desenează întâi pe o imagine tampon

Graphics graph= buffImg.getGraphics();

// activează efectul de interpolare, pentru a face piesele să arate mai bine atunci când sunt redimensionate

((Graphics2D)graph).setRenderingHint(RenderingHints.KEY_INTERPOLATION,

RenderingHints.VALUE_INTERPOLATION_BILINEAR);

graph.setColor(getBackground());

graph.fillRect(clipRec.x,clipRec.y,clipRec.width,clipRec.height);

for (int i=Math.min(topLeftCell.y,0);i<=Math.min(BottomRightCell.y,BOARD_SIZE-1);i++)

for (int j=Math.min(topLeftCell.x,0);j<=Math.min(BottomRightCell.x,BOARD_SIZE-1);j++) {

PaintCell(graph,i,j);

}

//desenează coordonatele tablei

graph.setColor(Color.black);

graph.setFont(new Font(g.getFont().getFontName(),Font.BOLD,11));

final Rectangle rowIdsRect=new Rectangle(0,0,PADDING,cellSize*BOARD_SIZE);

if (clipRec.intersects(rowIdsRect)) {

for (int i=0;i<BOARD_SIZE;i++) {

graph.drawString(""+(i+1), PADDING/2, (BOARD_SIZE-i-1)*cellSize+(cellSize/2));

}

}

final Rectangle colIdsRect=new Rectangle(PADDING,cellSize*BOARD_SIZE,cellSize*BOARD_SIZE,PADDING);

if (clipRec.intersects(colIdsRect))

for (int i=0;i<BOARD_SIZE;i++) {

graph.drawString(""+letters.charAt(i), i*cellSize+PADDING+(cellSize/2), BOARD_SIZE*cellSize+PADDING/2);

}

g.drawImage(buffImg, 0, 0, null);

}

else { //ascunde tabla dacă jocul este în pauză

Rectangle clipRec=g.getClipBounds();

g.setColor(getBackground());

g.fillRect(clipRec.x, clipRec.y, clipRec.width, clipRec.height);

g.setColor(Color.black);

g.drawString(LangConsts.PAUSE_CAPTION,getWidth()/2, getHeight()/2);

}

}

Concluzii

Deși marea majoritate a programelor de șah din zilele noastre folosesc toate îmbunătățirile recente aduse pentru a reduce timpul necesar traversării arborelui de căutare, doar la sfârșitul jocului este posibilă o căutare consistent mai mică decât cea necesară arborelui minimal, prin intermediul tabelelor de transpoziții. Căutarea selectivă și tăierea sunt singurele speranțe în reducerea spațiului de căutare. Înainte ca acest lucru să fie posibil, este necesar ca programele să poată deduce logic ce ramuri pot fi ignorate din arbori. Acestea sunt de obicei ramuri ce creează întotdeauna slăbiciuni. Dificultatea va fi în a face acest lucru fără a pierde din vedere factorii tactici. Performanța îmbunătățită va veni și de la calculatoarele mai puternice. Odată cu apariția calculatoarelor personale cu mai multe procesoare (sau procesoare cu mai multe nuclee), programele de șah construite cu abilitatea de a paraleliza calculele devin un adevărat adversar și acasă pentru marii campioni. În 2006 programul Deep Fritz, rulând pe o mașină cu 8 procesoare, l-a învins pe campionul mondial la șah Vladimir Kramnik cu scorul final de 4-2.

Țelul final, acela de a rezolva șahul poate fi atins în câteva secole. Deși teoretic numărul de mutări în șah este infinit, aplicând regula de 50 de mutări, emisă de Federația internațională de șah, numărul maxim de mutări într-un joc de șah ajunge undeva la aproximativ 6000 de mutări. Luând acest lucru în calcul, rezolvarea șahului pare posibilă, dacă evoluția hardware avansează cel puțin în același ritm ca până acum.

Bibliografie

[1]. Louis Victor Allis, Searching for Solutions in Games and Artificial Intelligence, 1994.

[2] Robert Hyatt, Chess program board representations, http://www.cis.uab.edu/hyatt/boardrep.html

[3]. Donald E. Knuth, Ronald W. Moore. An analysis of alpha-beta pruning. Artificial Intelligence, Vol. 6, 1975, pag. 293–326.

[4] François Dominic Laramée, Chess Programming, http://archive.gamedev.net/reference/programming/features/chess1/

[5]. T.A. Marsland. Computer Chess Methods, Encyclopedia of Artificial Intelligence, John Wiley & sons, New York, mai 1987

[6]. Judea Pearl. Heuristics – Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishing Co., Boston, SUA, 1984

[7] Aske Plaat, A New Paradigm for Minimax Search, University of Alberta,Raport tehnic EUR-CS-95-03, 1994

[8] Aske Plaat, RESEARCH RE: SEARCH & RE-SEARCH, 1996

[9] A. Reinefeld, An improvement to the Scout tree search Algorithm, ICCA Journal, Vol. 6, Nr. 4, decembrie 1983, pag. 4-14

[10]. Stuart Russel, Peter Norvig. Artificial Intelligence, a modern approach 2nd edition, Prentice Hall, New Jersey 2003.

[11]. Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, Checkers is solved, Science, Vol. 317. nr. 5844, 2007, pag. 1518 – 1522

[12] Jonathan Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, nr. 11, noiembrie 1989, pag. 1203–1212

[13] Claude E. Shannon, Programming a Computer for Playing Chess, Philosophical Magazine, Ser.7, Vol. 41, Nr. 314, martie 1950

[14] http://en.wikipedia.org/wiki/Minimax

Bibliografie

[1]. Louis Victor Allis, Searching for Solutions in Games and Artificial Intelligence, 1994.

[2] Robert Hyatt, Chess program board representations, http://www.cis.uab.edu/hyatt/boardrep.html

[3]. Donald E. Knuth, Ronald W. Moore. An analysis of alpha-beta pruning. Artificial Intelligence, Vol. 6, 1975, pag. 293–326.

[4] François Dominic Laramée, Chess Programming, http://archive.gamedev.net/reference/programming/features/chess1/

[5]. T.A. Marsland. Computer Chess Methods, Encyclopedia of Artificial Intelligence, John Wiley & sons, New York, mai 1987

[6]. Judea Pearl. Heuristics – Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishing Co., Boston, SUA, 1984

[7] Aske Plaat, A New Paradigm for Minimax Search, University of Alberta,Raport tehnic EUR-CS-95-03, 1994

[8] Aske Plaat, RESEARCH RE: SEARCH & RE-SEARCH, 1996

[9] A. Reinefeld, An improvement to the Scout tree search Algorithm, ICCA Journal, Vol. 6, Nr. 4, decembrie 1983, pag. 4-14

[10]. Stuart Russel, Peter Norvig. Artificial Intelligence, a modern approach 2nd edition, Prentice Hall, New Jersey 2003.

[11]. Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, Checkers is solved, Science, Vol. 317. nr. 5844, 2007, pag. 1518 – 1522

[12] Jonathan Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, nr. 11, noiembrie 1989, pag. 1203–1212

[13] Claude E. Shannon, Programming a Computer for Playing Chess, Philosophical Magazine, Ser.7, Vol. 41, Nr. 314, martie 1950

[14] http://en.wikipedia.org/wiki/Minimax