Licenta Anton Roxana1 (1) [627610]

UNIVERSITATEA TEHNICĂ „Gheorghe Asachi” din IAȘI
FACULTATEA DE AUTOMATICĂ ȘI CALCULATOARE
DOMENIUL: CALCULATOARE ȘI TEHNOLOGIA INFORMAȚIEI
SPECIALIZAREA: CALCULATOARE
Jocul de șah folosind algoritmul
minimax
LUCRARE DE LICENȚĂ
Profesor coordonator,
Prof. dr. ing. FLORIN LEON
Absolvent: [anonimizat], 2017

DECLARAȚIE DE ASUMARE A AUTENTICITĂȚII
LUCRĂRII DE LICENȚĂ
Subsemnatul(a) ANTON ANA – ROXANA ,
legitimat(ă) cu C.I. seria MZ nr. 079423, CNP [anonimizat]
autorul lucrării JOCUL DE ȘAH FOLOSIND ALGORITMUL MINIMAX
elaborată în vederea susținerii examenului de finalizare a studiilor de licență
organizat de către Facultatea de Automatică și Calculatoare din cadrul Universității
Tehnice „Gheorghe Asachi” din Iași, sesiunea IULIE 2017 a anului universitar
2016-2017, luând în considerare conținutul Art. 34 din Codul de etică universitară al
Universității Tehnice „Gheorghe Asachi” din Iași (Manualul Procedurilor, UTI.POM.02 –
Funcționarea Comisiei de etică universitară), declar pe proprie răspundere, că această
lucrare este rezultatul propriei activități intelectuale, nu conține porțiuni plagiate, iar
sursele bibliografice au fost folosite cu respectarea legislației române (legea 8/1996) și a
convențiilor internaționale privind drepturile de autor.
Data Semnătura

Cuprins
Capitolul 1. Introducere ………………………………………………………………………………………………….. 1
1.1. Domeniul temei …………………………………………………………………………………………………… 1
1.2. Jocurile și Inteligența Artificială ……………………………………………………………………………. 1
1.3. Tema propusă ……………………………………………………………………………………………………… 1
Capitolul 2. Algoritmul Minimax …………………………………………………………………………………….. 4
2.1. Funcția de evaluare ……………………………………………………………………………………………… 5
2.2. Algoritmul Minimax cu retezarea alfa-beta …………………………………………………………….. 6
2.3. Alternative…………………………………………………………………………………………………………. 7
2.4. Realizări asemănătoare …………………………………………………………………………………………. 7
2.4.1. Deep Fritz 13 ……………………………………………………………………………………………….. 7
Capitolul 3. Proiectarea aplicației …………………………………………………………………………………… 10
3.1. Descrierea aplicației ………………………………………………………………………………………….. 10
3.2. Diagrame UML …………………………………………………………………………………………………. 10
3.2.1. Diagrama de utilizare ………………………………………………………………………………….. 10
3.2.2. Diagrama de activități …………………………………………………………………………………. 10
3.2.3. Diagrama de clase ……………………………………………………………………………………… 10
Capitolul 4. Implementarea jocului ………………………………………………………………………………… 13
4.1. Obiective………………………………………………………………………………………………………….. 13
4.2. Utilizarea aplicației ……………………………………………………………………………………………. 13
4.3. Analiza algoritmului …………………………………………………………………………………………… 17
4.4. Analiza aplicației ……………………………………………………………………………………………….. 17
4.5. Dificultăți întâmpinate ……………………………………………………………………………………….. 21
Capitolul 5. Rezultate experimentale ……………………………………………………………………………… 22
5.1. Studiu de caz……………………………………………………………………………………………………… 22
Capitolul 6. Concluzii ……………………………………………………………………………………………………. 23
6.1. Dezvoltări ulterioare ……………………………………………………………………………………………. 23
Capitolul 7. Bibliografie ………………………………………………………………………………………………… 24
Anexe………………………………………………………………………………………………………………………….. 25
Anexa 1.Cod sursă……………………………………………………………………………………………………. 25

Jocul de șah folosind algoritmul minimax
Ana – Roxana Anton
Rezumat
Scopul lucrării în cauză este realizarea unei aplicații tip joc de șah, având la bază
principiile acestuia .
În contextul virtual, jocul poate fi practicat și de un singur jucător în interacțiune cu
calculatorul(inteligență artificială), cel din urmă fiind creat pe baza algoritmului minimax.
Acest algoritm presupune găsirea celei mai bune mutări ale jucătorului, dintr-un arbore
de căutare, împotriva adversarului care joacă șahul la un nivel avansat și perfect.
Strategia pe care acest algoritm se bazează este aceea că ambii jucatori au propriile lor
mijloace de joc.Astfel, primul jucător(MAX-calculatorul) va încerca să facă cele mai bune
mutări,mărinduși șansele de câștig la fiecare mutare a sa , pe când cel de-al doilea (MIN-
adversarul) are ca scop minimizarea câștigului adus de acele mutări.
Astfel, ca o îmbunățire la acest algoritm a apărut retezarea(taietura) alpha-beta, ce are ca
scop optimizarea metodei MINIMAX.
Ca performanța programului să fie una mare va fi nevoie și de o functie de evaluare
euristică . În cazul nostru, și anume în jocul de șah, această funcție va fi dată de punctajul
pieselor(pion = 1 punct, cal/nebun = 3 puncte, turn = 5 puncte, regină = 9 puncte).
Aplicația propusă spre rezolvare este realizată în C#. Interfața grafică va fi realizată
folosind componentele grafice din System.Windows.Forms.
Ca rezultat, se dorește ca aplicația să respecte obiectivele propuse (descrise în capitolul 4
al lucrării), urmând ca în viitor să poată fi îmbunățit programul, tocmai pentru a avea mai mult
succes în fața adversarilor profesioniști umani.

Capitolul 1. Introducere
Capitolul 1. Introducere
1.1. Domeniul temei
Despre Inteligența Artificială s-a vorbit pentru prima dată în 1956, iar inițiatorul acestui
termen a fost prof.John McCarthy, care a prezentat această noțiune la întrunirea “Darthmouth
Summer Research Project on Artificial Intelligence”. După aproape 50 de ani,aceasta a devenit
realitate, termenul fiind folosit în dezvoltarea tehnologiilor.
Inteligența Artificială este importantă deoarece aceasta poate aborda noi clase de
probleme cum ar fi: luarea de decizii, planificarea, percepția, concepția. Acești factori sunt
utilizați în activități umane variate și au la bază valorificarea optimă a unor cantități vaste de
cunoștințe.
Astfel, acest termen se găsește în aproape toate domeniile de activitate cum ar fi :
matematică, medicină, tehnologii, jocurile pe calculator,construirea de roboți, contruirea de
mașini inteligente etc..
Din dorința de a se autodepășii, oamenii au folosit jocurile ce erau doar practicate ca
simple sporturi, într-un mod unic, de a testa diverși algoritmi de inteligență artificială, având ca
rezultat mașinării ce în ziua de astăzi ne facilitează munca. [1]
1.2. Jocurile și Inteligența Artificială
Jocurile în ziua de astăzi au un loc aparte în viața noastră. Acestea, fie că le joci de
plăcere, fie profesionist, au la bază diverși algoritmi, care imită acțiunile omului. De asemenea,
Inteligența Artificială joacă un rol important în creearea de jocuri la un nivel satisfacător.
Athur Samuel afirmă într-un studiu al său că o dată ce avansăm cu înțelegerea
programării unui calculator, cu scopul de a juca jocuri, vom putea reuși atfel să înțelegem
metodele implicate în simularea unor astfel de mașinării. [2]
1.3. Tema propusă
Am ales acestă temă datorită interesului meu asupra jocului de șah încă din copilărie.
Acest sport, este unul destul de greu, ce are nevoie de mult ă logică și răbdare. De asemenea, un
raport important adus în această temă este extinderea acestui sport, practicat la diferite niveluri
oriunde în lume. Fie că îl joci de plăcere, de relaxare, fie profesionist, acest joc este considerat
sport al minții. Este un joc cosmopolit practicat indiferent de vârstă. Asupra lui s-au făcut diverse
experimente deoarece este unul din puținele sporturi care pun în practică modul acționării
oamenilor sub anumite auspicii.
Acest joc are o lungă istorie,iar cercetătorii științifici nu au reușit de-a lungul anilor să
stabilească informații concrete legate de apariția acestui joc.
Șahul a fost dezoltat pe o scară largă în Europa,iar până în secolul al XV-lea, jocul a
reușit să treacă peste interdicțiile Bisericii Catolice,care au luat forma jocului modern. O data cu
evoluția istoriei, acest sport a avut parte de o creștere a popularității prin organizarea de turnee,cu
mulți jucători și reguli eficiente. Abia, din secolul XIX-lea au fost înființate cluburi de șah,
concursuri, oferind astfel o largă arie de acțiune a practicării acestui sport. [3]
În zilele de astăzi, șahul este jucat încă de la vârste fragede peste tot în lume, jucătorii
având oportunități mari de a-și pune în valoare capacitățile lor de a gândi, de a juca, în diferitele
competiții.
Încă de prin anii 1800 , au apărut tot felul de discuții serioase cu privire la jocurile
1

Ana-Roxana Anton
inteligente. Asftel, în 1846, a fost propus proiectarea unui motor analitic, care era capabil să
joace atât șah, cât și dame, iar în anul 1890 a fot creată o mașinărie de către Lonard Torres, care
reușea să joace finalul unei partide șah.
Un imblod mai mare asupra jocurilor, l-a avut Alan Turing , care a fost primul om ce a
reușit să scrie un program, capabil de a juca o întreagă partidă de șah.
Printre marii jucători de șah, se numără Anatoly Karpov, Emanuel Lasker, Bobbz Fischer,
Jose Capablana etc., dar cel mai remarcat a fost și este Gary Kasparov, care în 1985 a devenit cel
mai tânăr campion mondial, la vârsta de 22 de ani.
De prin anii 1989, a început o rivalitate între Deep Blue, un super-computer, ce a fost
realizat de IBM și Kasparov, care în cele din urmă s-a terminat în anul 1997, când campionul
mondial pierde în fața computerului. Prin urmare, acest rezultat, a uimit o întreagă lume, reușind
asftel , să pună în valoare faptul că, noi oamenii, suntem capabili de a dezvolta calculatoare, ce
depășesc limita noastă de gândire.De asemenea, s-a ajuns la concluzia că Deep Blue,care are
capacitatea de a calcula 200 de milioane de poziții, pe secundă, este cel mai rapid program de șah
cu care un campion mondial s-a putut confrunta.
Mai târziu, au început și alte programe să apară. Un prim exemplu, ar putea fi Junior sau
Deep Junior. El a fost creat de către programatorii Amir Ban și Shaz Bushinsky și totodata, este
realizat ca în orice poziție să caute diverse mutări de sacrificii, care în urma lor să îi aducă un
avantaj. În anul 2003, a jucat timp de 6 runde, împotriva lui Gary Kasparov, rezultatul fiind 3-
3,iar în 2006 l-a învins pe unul dintre cei mai buni jucători actuali, Teimour Radjabov, într-un
meci de șah rapid. În 2007, Deep Junior a reușit să-l învingă pe Deep Fritz, un alt program de
șah, cu scorul de 4-2, în competiția organizată de FIDE, cea din urmă reprezentând federația
mondială de șah.
Un alt exemplu de program, este Deep Fritz, care în 2002 a făcut egal cu un alt campion
mondial, Vladimir Kramnik. De-a lungul anilor, Deep Fritz a avut parte de mai multe schimbări,
cel mai recent fiind lansat în 2015, Fritz 15. Acesta are la bază un engine, Rybka, ce oferă
jucătorilor de a analiza diverse poziții de șah, la un nivel avansat.
Șahul este un sport complex. Deși pe dinafară pare destul de simplu, bazat pe o strategie,
atac și apărare, defapt lucrurile nu stau chiar așa. Toate aceste programe, care au avut rezultate
excepționale împotriva marilor campioni se bazează pe mai mulți factori. Aceștia vor fi ilustrați
în figura de mai jos.
2
Figura 1.1

Capitolul 1. Introducere
În ziua de astăzi putem observa cum lumea calculatoarele se îmbină cu cea reală. Această
afirmație se remarcă și în lumea șahului. Asftel, din ce în ce mai mulți jucători de șah, pentru a se
pregăti de adversar,folosesc așa zisele motoare de calcul, ce funționează în programele de șah.
Aceste motoare sunt realizate la un nivel avansat, ele reușind să calculeze mutări până la
o adâncime de 26 și totodată, oferă o un plan pentru continuarea unei poziții, ce poate aduce
câștigul prin calcularea a milioane de variante.
Conform ultimei statistici în 2017, s-a făcut un clasament cu cele mai bune engine-
uri1(eng.), acestea având la bază mai multe criterii precum : coeficient ELO2, numărul de partide
jucate, media adversarilor etc..
Astfel, clasamentul top 5 este alcătuit din:3
•Komodo 11 – Elo: 3405
•Stockfish 8 – Elo: 3390
•Houdini 5 – Elo: 3388
•Deep Shredder 13 – Elo: 3290
•Fire 5 – Elo: 3271
În continuare, vom prezenta o scurtă descriere a capitolelor următoare a lucrării de licență
astfel:
Capitolul 2, prezintă metoda de rezolvarea a jocului de șah prin Minimax. De asemenea,
tot în acest capitol vom vorbi și despre proprietățile algoritmului. Totodata, se va descrie funcția
de evaluare, dar și îmbunătățirile ce pot fi aduse acestui algoritm. Se va face de asemenea, și o
comparație alte aplicații.
Capitolul 3, se va descrie proiectarea aplicației
Capitolul 4, va cuprinde atât o prezentare a implementării jocului de șah, cât și o analiză
a algoritmului pe baza căruia funcționează jocul.
Capitolul 5, se vor prezenta rezultate experimentale obținute în urma realizării aplicației.

1engine(eng.) – motor de căutare ce găsește cele mai bune mutări într-o poziție dată
2ELO (conform DEX) reprezintă o metodă de evaluare a unui jucător de șah. Acesta poate să scadă sau să crească
în funcție de performanțele obținute de-a lungul turneelor de șah.
3Komodo 11, Stockfish 8, Houdini 5, Deep Shredder, Fire 5 reprezintă motoare de calcul
3

Ana-Roxana Anton
Capitolul 2. Algoritmul Minimax
În lucrarea propusă, ne-am propus abordarea jocului de șah, prin algoritmul Minimax.
Acest algoritm este unul de căutare într-un arbore. El are ca scop găsirea celei mai bune
mutări pentru calculator, într-un joc unde celălalt jucător este omul.
Teoretic, acest algoritm permite practicării șahului, într-un mod excelent. Acest lucru este
adevărat doar în pozițiile cu mutări unice, în special în finalurile cu puține piese și destul de
clare. În schimb, pentru jocul de mijloc este greu de definit un mod perfect de joc. [4]
Strategia pe care acest algoritm se bazează este aceea că ambii jucatori au propriile lor
mijloace de joc. Astfel, primul jucător(MAX-calculatorul) va încerca să facă cele mai bune
mutări, mărinduși șansele de câștig la fiecare mutare a sa, pe când cel de-al doilea (MIN-
adversarul) are ca scop minimizarea câștigului adus de acele mutări.
În continuare, pentru a studia și a înțelege acest algoritm, luând ca exemplu un arbore de
căutare. Să presupunem că pentru fiecare jucător sunt posibile doar două mutări, iar adâncimea
arborelui este de 4 niveluri, figura de mai jos vom ilustrând acest fapt.
Din figura de mai sus, putem spune că arborele de căutare este generat de către algoritm
din dreapta, nodurile de tip cerc reprezentând jucătorul Max-calculatorul, iar cele de tip pătrat
sunt mutările adversarului.
Algoritmul va evalua conform unei funcții de evaluare euristică, fiecare nod, obținându-
se astfel rezultate afișate. De asemenea, aceste valori vor exemplifica poziția cea mai bună de-a
lungul jocului, atât pentru calculator, cât și pentru adversar.
Așadar, la nivelul 3, corespunzător pentru mutările minimizante, se va alege din fiecare
nod de pe nivelul 4, cea mai mică valoare din nodurile copil. De exemplu, în partea dreaptă, intre
valorile -7 și -5, se va alege -5. Următorul nivel, va consta în alegerea valorii celei mai mari din
fiecare nod copil, acestea fiind distribuite către nodul părinte.
Algoritmul va continua să evalueze valorile maxime și minime ale nodului copil, până se
va ajunge în nodul rădăcina, valoarea fiind cea mai mare. Acest lucru este arătat în figură prin
săgeata albastră.
Trebuie luat în calcul și posibilitatea că algoritmul Minimax va evalua recursiv cele 9
„frunze” ale acestui arbore, mergând înapoi. În cele din urmă, va reuși să minimizeze mutărilor
omului și să maximizeze valoarea mutărilor calculatorului. Dacă este să ne uitam pe figură,
putem observa că cea mai bună mutare pentru calculator este nodul cu valoarea -7, deoarece este
mai mare decât valoarea din celălalt nod. La rândul ei, aceasta valoare va fi minimizată,
reflectând minimul dintre valorile 5 și -7. Următorul nod va maximiza și astfel va lua cea mai
mare valoarea cea mai mare, șamd. [5]
4
Figura 2.1. Arbore de căutare Minimax

Capitolul 2. Algoritmul Minimax
Un pseudocod ce ar descrie acest algoritm ar putea fi următorul:
int max( int depth )
{
if ( depth == 0 )
return evaluate();
int max = -oo;
for ( all moves)
{
score = mini( depth – 1 );
if( score > max )
max = score;
}
return max;
}
int mini( int depth )
{
if ( depth == 0 )
return -evaluate();
int min = +oo;
for ( all moves)
{
score = maxi( depth – 1 );
if( score < min )
min = score;
}
return min;
} [6]
Pentru jocul de șah , spațiul de căutare este de factorul de ramificare,35, și numărul de
mutări pe jucător care este aproximativ 50. Aceste valori dau atât dimensiunea arborelui de
căutare, 1040, cât și numărul de noduri 35100.[7]
2.1. Funcția de evaluare
Capacitatea de evaluarea constituie elementul central al funcționării unui calculator. Fiind
o funcție euristică, urmărește să reflecte într-o manieră certă șansele de câștig, oferind o estimare
a utilității asteptate. În orice joc, această funție trebuie să fie rapidă, să nu consume timpul de
utilizare. Totodată, această funție permite doar o aproximare a valorii optimale.
În cazul nostru, această funcție va fi dată de punctajul pieselor( pion = 1 punct, cal/nebun
= 3 puncte, turn = 5 puncte, regină = 9 puncte).Astfel spus,pentru a ne da seama pentru cine este
mai bună poziția de pe tabla de joc ,trebuie evaluate piesele rămase pe tablă după punctajul lor.
Pentru că se bazează pe valoarea materială, evaluarea devine o funție liniară și ponderată
în jocul de șah, putând fi exprimată ca raportul dintre piesele jucătorului calculator și cele ale
adversarului.
Jocul urmărește aducerea regelui în poziția de șah mat. Astfel, riscul ca această piesă să
se afle într-o poziție vulnerabilă pe tabla de joc devine aspectul central ce trebuie evaluat.
Utilizarea unei limite de căutare în adâncime devine unealta cea mai utilă în controlul
adâncimii căutării. Respectând perioada de timp alocată pentru fiecare mutare, reducerea se va
5

Ana-Roxana Anton
realiza la toate nodurile până la o adâncime d. Căutarea iterativă în adâncime este însă o variantă
alternativă mult mai optimă. Programul va rula o căutare în arbore, completă, iar la definitivarea
timpului va returna mutarea considerată cea mai corectă, până la adâncimea analizată. [8]
2.2. Algoritmul Minimax cu retezarea alfa -beta
După cum s-a mai spus, arborele de căutare în cazul lui Minimax crește foarte mult, ceea
ce îl face să nu fie foarte optim.
Așadar, s-a propus ca o soluție în rezolvarea complexității algoritmului retezarea unor
ramuri ale arborelui, ce presupune nealuare în considerare a mutărilor ce nu ne sunt de folos.
Astfel, această tehnică mai poate fi numită și reducerea Alfa-Beta. Atunci când se aplică
unui arbore, ea va întoarce aceeași mutare ca și Minimax, însă elimină ramuri care nu pot
influența decizia finală.
Ilustrarea o vom face, la fel ca și în cazul lui Minimax, tot pe un arbore de căutare din
figura următoare.[5]
În acest caz, contează foarte mult ordinea în care succesorii unui nod sunt analizați,
deoarece aceștia dau eficiența algoritmului. Astfel, la nodurile minimizante trebuie luate doar
acelea de la cea mai mică la cea mai mai mare valoare, iar nodurile maximizante de la cel mai
mare la cel mai mic scor.
De asemenea, aceast ă reducere nu va influența rezultatul final, ba chiar mai mult poate
calcula aproape dublu față de algoritmul clasic Minimax. Totodată, cu un calcul bine pus la punct
, jocul ce va avea la bază această retezare va putea fi jucat la un nivel mediu spre avansat.
În continuare, vom prezenta un scurt pseudocod al reducerii Alfa-Beta:
int alphabeta(node, depth, α, β, maximizingPlayer )
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
v := -∞
for each child of node
6
Figura 2.2. Arbore de căutare cu reducere Alfa-Beta

Capitolul 2. Algoritmul Minimax
v := max(v, alphabeta(child, depth – 1, α, β, FALSE))
α := max(α, v)
if β ≤ α
break
return v
else
v := +∞
for each child of node
v := min(v, alphabeta(child, depth – 1, α, β, TRUE))
β := min(β, v)
if β ≤ α
break
return v;
2.3. Alternative
Negamax este o altă variantă a algoritmului Minimax, care spre deosebire de
Alfa-Beta nu va mai mai folosi cele doua subrutine Mini și Max separat, ci le va trece pe un scor
negativ datorită formulei pe care el funcționează.:
max(a, b) == -min(-a, -b)
De explicat a ;i b
Ca un dezavantaj a acestei alternative, o poate reprezenta faptul că analiza va trebui
făcută din punctul de vedere a jucătorului care este la mutare. Astfel, în cazul jucătorului min
este necesar ca rezultatul returnat să fie înmulțit cu -1, tocmai pentru a respecta principiul pe care
algoritmul clasic Minimax îl are la bază. [9]
2.4. Realizări asemănătoare
Se poate observa, dând doar o singură căutare pe internet, că jocul de șah este unul dintre
cele mai populare jocuri pe tablă. Astfel, în acest capitol vom aborda o aplicație web, ce poate
rula atât pe Windows, cât și pe sisteme de tip Android,iOS. Totodată, va putea fi comparată cu
aplicația noastră, deoarece se regăsesc mai multe elemente comune.
2.4.1. Deep Fritz 13
Deep Fritz 13 este o aplicație web. Aceasta este folosita ca un mod de pregătire atât
pentru jucătorii amatori, cât și pentru cei profesioniști. Mai poate fi utilizată și într-un mod de
relaxare, prin jocul cu calculatorul.
În primul rând, acest program are ca opțiune alegerea nivelului jucătorului uman,
transmițând astfel calculatorului la ce nivel va trebui să joace.
În al doilea rând, putem observa din figura de mai jos, ca această aplicație are mai multe
funcționalități interesante, ce pot veni în ajutorul îmbunătățirii aplicației noastre. Aceste lucruri
sunt descrise în ultimul capitol al lucrării.
Ce ar fi interesant la Deep Fritz, este faptul că se folosește de motorul de calcul Deep
Fritz 13, unde afișează atât mutările cele mai bune ale calculatorului, cât și evaluarea poziției.
Cea din urmă are mai mulți factori luați în considerare precum: poziția pieselor, structura de
pioni, coloane, linii deschise etc..
De asemenea, aplicație prezintă meniul în diferinte limbi alte lumii, tocmai pentru a fi
accesibil tuturor.
7

Ana-Roxana Anton
8
Figura 2.3. Interfața grafică cu utilizatorul a aplicației Deep Fritz 13

Capitolul 2. Algoritmul Minimax
2.5. Euristica null-move(eng.)4
Observăm, în ziua de azi că programele de șah au la bază pentru funcționarea lor, viteza
de căutare. În ajutorul acestei afirmații, vine și euristica null-move, care poate să fie folosită în
îmbunătățirea vitezei de calcul. Totuși, această euristică are și un dezavantaj și anume faptul că
poate prezenta o mică șansă de eroare.
Acestă euristică poate fi evaluată cu o funcție de căutare în adâncime redusă și ajunge să
estimeze o limită inferioară a poziției ce este analizată. Astfel, folosind această metodă ca o
reducere înainte poate afecta precizia calculului minimax. [10]
4Null-move = mutarea vidă
9

Ana-Roxana Anton
Capitolul 3. Proiectarea aplicației
3.1. Descrierea aplicației
Scopul acestei lucrări constă în realizarea unei aplicații de tip joc între om și calculator.
Acesta va putea funcționa pe versiunea 4.0 a platformei .NET Framework. Limbajul de
programare este C#. Acesta este o combinație dintre C și C ++, dar aduce și o tentă de Java.
Ulterior, acest limbaj, a devenit disponibil și pentru alte platforme, precum Linux.
Am ales să fac în C# deoarece conține foarte multe librării, iar implementarea metodelor
este una mai ușoară spre deosebire de C/ C++. De asemenea, acest limbaj a luat o amploare foarte
mare în domeniul IT și totodată oferă un mod simplu de a realiza interfețe grafice. [11]
3.2. Diagrame UML
Diagramele UML5 sunt necesare pentru prezentarea structurii, ce este formată din entități
și clase.
3.2.1. Diagrama de utilizare
Diagrama de clase de utilizare ne ajută să înțelegem legătura dintre așa zișii „ actori” și
sistemul.
5UML (Unified Modeling Language) este un limbaj standard folosit pentru prezentarea modelelor și specificațiile
pentru software. Prima versiune a apărut în anul 1990.
10
Figura 3.1. Diagrama de utilizare

Capitolul 3. Proiectarea aplicației
3.2.2. Diagrama de activități
Diagrama de activități descrie într-un mod mai detaliat funcționalitatea sistemului.
3.2.3. Diagrama de clase
Diagrama de clasă descrie structura aplicației, cu componentele ei. Acest lucru se poate
observa și în figura de mai jos.
11
Figura 3.2. Diagrama de activități

Ana-Roxana Anton
12 Figura 3.3. Diagrama de clase

Capitolul 4. Implementarea jocului
Capitolul 4. Implementarea jocului
4.1. Obiective
Scopul principal al studiului de față este proiectarea unui sistem care poate să ofere
posibilitatea de antrenament, atât pentru jucătorii de șah amatori, cât și pentru cei profesioniști.
Pentru îndeplinirea temei propuse, au fost urmărite următoarele obiective secundare/
puncte cheie în crearea aplicatiei. Astfel, programul se dorește a fi unul usor de utilizat, prietenos
cu utilizatorul încă de la primul contact, prin simplitatea interfeței grafice.
Un alt obiectiv a fost proiectarea de așa natură a aplicației încât să permită dezvoltări,
îmbunătățiri ulterioare, precum adăugarea timpului de joc pentru fiecare jucător. O altă
îmbunățire ar putea fi conectarea la baza de date de șah, de unde poți lua diferite partide.
Ulterior. pe acestea le poți juca cu calculatorul. Acestea vor urmări linia centrală a jocului dar vor
putea conferi senzația unei noi experiențe.
4.2. Utilizarea aplicației
În acest capitol vom prezenta funcționarea aplicației, ce realizează un joc de șah. În
primul rând, pentru a rula acest program este nevoie de un calculator, cu un sistem de operare pe
care să poate fi rulat mediul de programare Visual Studio.
La execuția aplicației se va deschide o fereastră, iar pentru a putea începe jocul este
nevoie de a intra în meniul aplicației, dând click pe New Game. Acest lucru va fi ilustrat în
figura următoare. Apoi , jucătorul om va putea începe partida, deoarece acesta este cu albul.
13

Ana-Roxana Anton
După cum se poate observa, în partea stânga de sus a interfeței se află tabla de șah cu
piesele, unde se va desfășura partida dintre om și calculator. De asemenea, în josul interfeței în
label-ul (eng.) Moves se vor afișa mutările atât ale albului, cât și ale negrului.
În partea dreaptă, se vor afișa piesele mâncate de către ambele tabere (vezi Figura 4.1).
Apoi, între cele două jumătăți de tablă se mai afla două instrumente. Primul ne indică a cui rând
este la mutare, de exemplu pentru mutarea omului se va afișa Player turn, iar pentru calculator
PC_turn(vezi Figura 4.2). Al doilea instrument, este un buton pe care jucătorul om trebuie să-l
acceseze pentru a anunța faptul ca și-a terminat mutarea.
14
Figura 4.1. Interfața cu utilizatorul

Capitolul 4. Implementarea jocului
15
Figura 4.2. Zonă piese pierdute

Ana-Roxana Anton
În continuare vom descrie meniul aplicației. Acesta va conține următoarele
componente:
1.Game, ce are următoarele opțiuni:
•New Game, se produce începerea partidei. De asemenea,se poate accesa chiar și
în mijlocul jocului, cu scopul de a reîncepe o alta partidă.
•Load, cu opțiunea că oricând se poate încarca o altă partidă jucată de mai demult
sau chiar diferite poziții prin care se poate exersa diferite strategii, fără a avea nevoie de un mtor
de calcul.
•Save, are rolul de a salva partida în orice moment al jocului.
•Exit, prin această opțiune se poate ieși din aplicație.
2.Help, cu opțiunea About unde se va afișa un mesaj cu referire la jocul de șah.
Acest meniu este oricând funcțional, fie la început, fie în timpul jocului, fie la sfârșit.
16
Figura 4.3. Semnalare mutare calculator

Capitolul 4. Implementarea jocului
4.3. Analiza algoritmului
Posibilitatea jucătorului de a jucă un meci de șah împotrivă sistemului la un anumit nivel
de dificultate, cu timp de răspuns ce se încadrează într-un anumit timp limită specificat. Acest
obiectiv poate fi realizat prin implementarea unui jucător virtual folosind un algoritm eficient
care pornind de la o poziție data pe tablă de șah generează un anumit număr de mutări în avans și
o alege pe cea mai bună dintre ele.
Un alt aspect urmărit este acela de putea oferi jucătorului posibilitatea de a juca o partid ă
de șah, împotriva calculatorului, cu o dificultate anterior stabilită. Atingerea acestui obiectiv se
poate realiza prin implementarea unui jucător virtual care să utilizeze un algoritm eficient, ce are
ca punct de start o poziție anume pe tablă și care generează un număr de mutări în avans și alege
varianta cea mai bună.
În continuare, vom prezenta implementare acestui algoritm. Pentru realizarea acestuia, a
fost nevoie de următoarele funcții principale.
private void PcMoveWithMiniMax ()
{
List<Move> allPcPossibleMoves = GetAllPossiblePcMoves (_table);
int bestScore = -10000;
List<Move> allGoodMoves = new List<Move>();
foreach (Move possibleMove in allPcPossibleMoves )
{
possibleMove.Score = EvaluatePcMove(possibleMove, _table) +
MiniMax(possibleMove, _table);
if (bestScore < possibleMove.Score)
{
bestScore = possibleMove.Score;
allGoodMoves = new List<Move>();
allGoodMoves.Add(possibleMove);
}
else
{
if (bestScore == possibleMove.Score)
{
allGoodMoves.Add(possibleMove);
}
}
}
Random rnd = new Random();
if (allGoodMoves.Count > 0)
{
Move nextMove = allGoodMoves[rnd.Next(allGoodMoves.Count)];
PerformMove(nextMove.StartingPoint.X, nextMove.StartingPoint.Y,
nextMove.DestinationPoint .X, nextMove.DestinationPoint .Y, _table);
}
}
17

Ana-Roxana Anton
private int MiniMax(Move move, int[,] currentTable)
{
_minMax_running = true;
int bestPcScore = 0;
int depth = 3;
bool pcTurn = false;
int[,] temporaryTable = InitializeTemporaryTable (currentTable);
Move temporaryMove = new Move(move.Piece, move.StartingPoint.X,
move.StartingPoint.Y, move.DestinationPoint .X, move.DestinationPoint .Y);
for (int i = 0; i < depth; i++)
{
PerformMove(temporaryMove.StartingPoint.X,
temporaryMove.StartingPoint.Y, temporaryMove.DestinationPoint .X,
temporaryMove.DestinationPoint .Y, temporaryTable);
if (pcTurn)
{
List<Move> allPossibleMoves =
GetAllPossiblePcMoves (temporaryTable);
Move nextMove = GestBestPcMove(allPossibleMoves );//MAX
temporaryMove = new Move(nextMove.Piece,
nextMove.StartingPoint.X, nextMove.StartingPoint.Y, nextMove.DestinationPoint .X,
nextMove.DestinationPoint .Y);
bestPcScore += temporaryMove.Score;
pcTurn = false;
}
else
{
List<Move> allPossibleMoves =
GetAllPossiblePlayerMoves (temporaryTable);
Move nextMove = GestBestPlayerMove (allPossibleMoves );//MIN
temporaryMove = new Move(nextMove.Piece,
nextMove.StartingPoint.X, nextMove.StartingPoint.Y, nextMove.DestinationPoint .X,
nextMove.DestinationPoint .Y);
bestPcScore -= temporaryMove.Score;
pcTurn = true;
}
}
_minMax_running = false;
return bestPcScore;
}
4.4. Analiza aplicației
În acest subcapitol, vom prezenta principalele clase ale acestui sistem. Acestea sunt:
•Move, este clasa în care îmi ia coordonatele pieselor de pe câmpul inițial, dar și
18

Capitolul 4. Implementarea jocului
cele ale finalizării mutării.
•Coordinate, reține coordonatele x și y, ce reprezintă linia și coloana.
•Table
De asemenea, implementarea lor va putea fi urmărită în Anexă 1. Cod sursă.
În continuare, vom ilustra funcțiile cu ajutorul cărora am putut realiza aplicația.
În primul rând, vom prezenta metoda de desenare a pieselor pe tabla de joc.
public void DrawPieces()
{
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
{
switch (_table[i, j])
{
case 00: _boardCells[i, j].BackgroundImage = null; break;
case 01: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\BPawn.gif" ); break;
case 02: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\BRook.gif" ); break;
case 03: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\BKnight.gif" ); break;
case 04: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\BBishop.gif" ); break;
case 05: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FroFile("Resources\\BQueen.gif" ); break;
case 06: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\BKing.gif" ); break;
case 11: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\WPawn.gif" ); break;
case 12: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\WRook.gif" ); break;
case 13: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\WKnight.gif" ); break;
case 14: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\WBishop.gif" ); break;
case 15: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\WQueen.gif" ); break;
case 16: _boardCells[i, j].BackgroundImage =
System.Drawing.Image.FromFile("Resources\\WKing.gif" ); break;
}
}
}
Această funcție va luat fiecare figura din folderul Resources, în care sunt pozele și le va
pune conform indecșilor de pe tablă. Acest lucru va fi arătat prin inițializarea tablei de joc.
private void InitializeTable()
{
_table = new int[8, 8]
{
19

Ana-Roxana Anton
{02, 03, 04, 05, 06, 04, 03, 02}, //piese negre
{01, 01, 01, 01, 01, 01, 01, 01}, //piese negre
{00, 00, 00, 00, 00, 00, 00, 00},
{00, 00, 00, 00, 00, 00, 00, 00},
{00, 00, 00, 00, 00, 00, 00, 00},
{00, 00, 00, 00, 00, 00, 00, 00},
{11, 11, 11, 11, 11, 11, 11, 11}, //piese albe
{12, 13, 14, 15, 16, 14, 13, 12}, // piese albe
};
}
De asemenea modul prin care, jucătorul om, cel cu alb va putea să facă mutarea este
ilustrat prin funcția OnSquareClick. De asemenea, dacă a atins o piesă din greșeală, și ar dori să
mute alta, este suficient doar sa dea click înapoi pe piesa pe care a accesat-o prima dată.
void OnSquareClick(object sender, EventArgs e)
{
if(btnEndTurn.Enabled)
{
return;
}
Square currentCell = sender as Square;
if(_startingX == -1)
{
_startingX = currentCell.CoordX;
_startingY = currentCell.CoordY;
_boardCells[_startingX, _startingY].BorderStyle = BorderStyle.Fixed3D;
}
else
{
_destinationX = currentCell.CoordX;
_destinationY = currentCell.CoordY;
if(_startingX == _destinationX && _startingY == _destinationY)
{
//put the piece back and restart the move
ResetState();
return;
}
_boardCells[_destinationX, _destinationY].BorderStyle = BorderStyle.Fixed3D;
int piece = _table[_startingX, _startingY];
if (MoveIsValid(piece, _startingX, _startingY, _destinationX, _destinationY))
{
_boardCells[_startingX, _startingY].BorderStyle = BorderStyle.None;
PerformMove(_startingX, _startingY, _destinationX, _destinationY);
DrawPieces();
EndPlayerTurn();
}
else
{
20

Capitolul 4. Implementarea jocului
MessageBox.Show("This move is not valid!" );
_boardCells[_destinationX, _destinationY].BorderStyle = BorderStyle.None;
_boardCells[_startingX, _startingY].BorderStyle = BorderStyle.Fixed3D;
}
}
}
După cum se observă din codul prezentat avem nevoie de mai multe variabile și apelări
de funcții.
În primul rând variabilele, _startingX și _startingY reprezintă coordonatele inițiale ale
piesei, urmând ca cele finale să se numească _destinationX și _destinationY .
În al doilea rând, prin funcția MoveIsValid se poate verifica corectitudinea mutării,
urmând ca după prin apelarea lui PerformMove să putem muta pe un câmp liber.
private bool MoveIsValid(int piece, int startingX, int startingY, int
destinationX, int destinationY)
{
bool result = false;
Pieces(piece, startingX, startingY);
if (_stateMove[destinationX, destinationY] == 2)
result = true;
return result;
}
private void PerformMove(int startingX, int startingY, int destinationX,
int destinationY)
{
RegisterMove(startingX, startingY, destinationX, destinationY);
_table[destinationX, destinationY] = _table[startingX, startingY];
_table[startingX, startingY] = 00;
}
De-a lungul implementării aplicației am avut nevoie de diferite funcții, ce urmează a fi
descrise în continuare.
O funcție importantă de tip buton ar fi btnEndTurn_Click(). Ea are rolul , o dată ce este
accesat, de a transmite calculatorul că jucătorul cu piesele albe și-a finalizat mutarea. În urma
accesării butonului, se va afișa un mesaj pe interfață. Acest lucru anunță jucătorul om, că
calculatorul a văzut mutarea și acuma știe că el este la mutare. De asemenea, o dată cu apariția
mesajului, tot pe interfață, într-un label se va afișa și a a cui rând este la mutare. Acest lucru se
poate observa și din Figurile 4 și 4.1, din capitolul anterior.
Un rol important îl joacă și funcția de evaluare. Aici, fiecare piesă va primi punctajul
conform teoriei șahului. Astfel, atunci când se va apela această metodă, calculatorul va vedea ce
piese mai sunt pe tablă, generând astfel cea mai bună mutare pentru poziția respectivă.
private int EvaluatePcMove(Move move, int[,] currentTable)
{
int pct_pc = 0;
21

Ana-Roxana Anton
int pct_user = 0;
switch (currentTable[move.StartingPoint.X, move.StartingPoint.Y])
{
case 01:
pct_pc += 1;
break;
case 02:
pct_pc += 3;
break;
case 03:
pct_pc += 3;
break;
case 04:
pct_pc += 5;
break;
case 05:
pct_pc += 9;
break;
case 06:
pct_pc += 100;
break;
case 0:
pct_pc = -pct_user;
break;
default:
break;
}
switch (currentTable[move.DestinationPoint .X,
move.DestinationPoint .Y])
{
case 11:
pct_user += 1;
break;
case 12:
pct_user += 3;
break;
case 13:
pct_user += 3;
break;
case 14:
pct_user += 5;
break;
case 15:
pct_user += 9;
break;
case 16:
pct_user += 100;
break;
case 0:
22

Capitolul 4. Implementarea jocului
pct_user = -pct_pc;
break;
default:
break;
}
return pct_pc + pct_user;
}
După cum se observă, din această metodă atribuirea punctajelor pieselor se face pe baza
case-urilor. Acestea reprezintă index-ul de pe inițializarea tablei de joc. În partea de mai sus, este
prezentat doar o funcția de evaluare pentru negru și anume pentru jucătorul virtual. Pentru cele
albe, principiul este același. Această metodă joacă un rol important în proiectarea algoritmului
Minimax.
Pentru ca jocul să se poată desfășura pe interfață, este necesară implementarea mersului
pentru fiecare piesa în parte, atât pentru alb, cât și pentru negru. Acestea poartă denumiri
precum: WhiteKing, WhiteBishop, BlackKnight, BlackQueen șamd. Aceste metode vor fi
apelate într-o altă funcție, deoarece este mult mai ușor de uitat pe cod. De asemenea, funcțiile ce
implementează mișcarea pieselor se poate vedea în Anexa 1. Cod sursă.
4.5. Dificultăți întâmpinate
În cazul șahului, starea inițială a jocului poate fi considerată atît poziția inițială a pieselor
pe tabla de joc, cât și cine este la mutare. Practic analiza jocului trebuie făcute pe un arbore.
De aceea, acest lucru a fost destul de problematic de implementat. În sensul că, a trebuit
să am mereu grijă mereu de mutările făcute de adversarul uman, tocmai pentru a genera cele mai
bune mutări pentru calculator.
O soluție în rezolvarea acestui lucru a fost să creez două funcții. Una în care îmi
generează mutarea cea mai buna a calculatorul, iar alta pentru om. Pentru a vedea acest lucru, am
evaluat posibilele table generate în urma mutărilor. Aceste funcții vor putea fi apelate în
program, iar descrierea lor se poate regăsi în Anexa 1. Cod sursă.
O altă problemă întâmpinată a fost descoperirea dacă regele este în șah sau nu.
23

Ana-Roxana Anton
Capitolul 5. Rezultate experimentale
În acest capitol, vom putea afirma că aplicația rulează corect, iar obiectivele lucrării au
fost îndeplinite.
5.1. Studiu de caz
În acest subcapitol, am încercat sa demonstrăm funcționalitatea aplicației printr-o altă
metodă. Testarea s-a făcut prin importarea unor poziții cu diferite rezultate. Astfel, problema ce
va fi afișată pe tabla de joc, urmează a fi jucată. Mutările albului vor fi făcute de om, iar cele ale
negrului vor rezulta conform algoritmului.
De exemplu, în figura de mai jos avem ilustrat un final teoretic de remiză.
24
Figura 5.1: Demonstrație joc între om și calculator

Capitolul 5. Rezultate experimentale
După cum se observă, în acest final albul are în avantaj un pion. Dacă negrul este la
mutare, conform algoritmului va alege capturarea pionului advers. Acesta se poate mânca
deoarece nu este apărat de nici o altă piesă a albului. Astfel, după luarea pionului poziția va fi
alcătuită doar din regi, ceea ce conduce la rezultatul de remiză.
În continuare, se va prezenta o altă poziție cu avantaj pentru negru, adică pentru
calculator.
25Figura 5.2. Final teoretic de remiză

Ana-Roxana Anton
26

Capitolul 6. Concluzii
Capitolul 6. Concluzii
Principalele obiective ale acestei teme au fost îndeplinite. Scopul a fost realizarea unui
joc dintre om și calculator, iar acest lucru s-a putut realiza cu ajutorul algoritmului Minimax.
Totuși, nivelulul la care se afla computer-ul este unul slab, mutările lui cele mai bune fiind alese
din funcția de evaluare.
Un avantaj în dezvoltarea acestei aplicații ar fi interfața grafică, care este una destul de
simplă și concretă. Aceasta, de asemenea, poate fi și ea îmbunătățită, lucru ce vă va fi discutat în
subcapitolul următor.
6.1. Dezvoltări ulterioare
Asupra acestei lucrări se pot aduce diverse îmbunătățiri. Un prim pas, ar fi implementarea
algoritmului ce stă la baza lucrării, cu retezare alfa – beta. Deși acest lucru, are același mod de
funționare ca implementarea minimax simplu, reducerea aceasta este mai bună din punct de
vedere a complexității timpului.
De asemenea, această îmbunătățire ar putea duce la înfrângerea jucătorilor profesioniști
de către calculator.
O altă variantă, ce poate fi adusă în îmbunătățirea jocului ar fi dezvoltarea aplicației pe
diferite sisteme mobile precum Android, iOS etc..
În ceea ce privește interfața, se pot adauga diferite funcționalități precum: adaugarea
timpul de joc pentru întreaga partidă. De exemplu, pentru o partidă bullet, timpul de joc pentru
fiecare jucător ar fi de 1 minut/partida, iar pentru șah rapid 10 minute/ partida. O altă
îmbunătățire ar fi adaugarea a două butoane, unul pentru cedarea partidei, iar altul pentru
propunerea de remiză.
Un alt mod de dezvoltare, ar fi adugarea unei baze de date, ce va conține diferite strategii
de deschidere a jocului. Astfel, calculatorul își va putea alege din acea baza, cea mai bună
mutare, ce contracarează mutarea adversarului uman.
Nu în ultimul rând, aceste dezvoltări ce vor putea fi aduse asupra aplicației vor determina
o îmbunătățire a nivelului. Acest lucru este o consecință a ridicării gradului de pregătire a
jucătorilor de șah.
27

Ana-Roxana Anton
Capitolul 7. Bibliografie
[1]Ionut Ghionea, Inteligență Artificială [Online], Disponibil la adresa:
http://www.catia.ro/articole/ai/ai.htm, Accesat: 2017.
[2]Jonathan Schaeffer, H.Jaap van den Herik, „Games, computers, and artifical intelligence”, , .
[3]AlexD, Istoria Șahului [Online], Disponibil la adresa:
http://gandirelogica.blogspot.ro/2011/06/istoria-sahului.html, Accesat: 2017.
[4] David G. Stork, Arthur C. Clarke, „HAL's Legacy: 2001's Computer As Dream and Reality”, ,
1997.
[5]Florin Leon, „Inteligență artificială.Principii, tehnici, aplicații”, Tehnopress, 2006.
[6]Andrei, Laborator Minimax [Online], Disponibil la adresa:
http://andrei.clubcisco.ro/cursuri/2pa/laboratoare/Laborator%205-_Minimax_v2.pdf, Accesat:
2017.
[7]Florin Leon, Jocuri. Satisfacerea constrângerilor [Online], Disponibil la adresa:
http://florinleon.byethost24.com/Curs_IA/IA03_Jocuri_CSP.pdf, Accesat: 2016.
[8]Catalin Stoean, Teoria Jocurilor [Online], Disponibil la adresa: http://inf.ucv.ro/~cstoean., Accesat:
2017.
[9], Negamax [Online], Disponibil la adresa: https://chessprogramming.wikispaces.com/Negamax,
Accesat: 2017.
[10]G. Goetsch, M. S. Campbell, Computers, Chess, and Cognition [Online], Disponibil la adresa: ,
Accesat: 2017.
[11]Barbara Doyle, „C# Programming; From Problem Analysis to Program Design ”, , 2013.
28

Anexe.
Anexe.
Anexa 1.Cod sursă
29