Specializarea Informatic a [608827]

Licență

Specializarea Informatic a [608827]

Byadmin ianuarie 1, 2024

Ministerul Educa¸ tiei Na¸ tionale
Universitatea "OVIDIUS" Constan¸ ta
Facultatea de Matematic ˘a ¸ si Informatic ˘a
Specializarea Informatic ˘a
StrategoAI – analiza ¸ si implementarea unui
juc˘ator inteligent pentru jocul Stratego
Lucrare de licen¸ t ˘a
Coordonatori ¸ stiin¸ tiﬁci:
Lect. univ. dr. B ˘autu Elena
Prof. univ. dr. Popovici Dorin Mircea
Absolvent: [anonimizat]¸ ta
2018

Abstract
Inteligen¸ ta artiﬁcial ˘a este folosit ˘a în jocurile video pentru a genera comportamente adaptive
¸ si inteligente, similare cu inteligen¸ ta uman ˘a. Stratego este un joc extrem de diﬁcil de în¸ te-
les de c ˘atre un program de calculator. Multitudinea de reguli ¸ si strategii, dar ¸ si informa¸ tia
incomplet ˘a pus ˘a la dispozi¸ tia juc ˘atorului fac din acesta unul din problemele nerezolvate în
domeniul agen¸ tilor software inteligen¸ ti pentru jocuri.
Scopul acestei lucr ˘ari este analiza diferitelor abord ˘ari propuse de-a lungul timpului ¸ si
implementarea unui juc ˘ator inteligent, la un nivel intermediar, pentru jocul Stratego. În
cadrul lucr ˘arii sunt descrise etapele implement ˘arii agentului inteligent, denumit "Strate-
goAI". Acesta folose¸ ste euristici pentru formula de start ¸ si planiﬁcarea mut ˘arilor. Aplica¸ tia
permite oric ˘arui juc ˘ator s ˘a î¸ si testeze abi lit ˘a¸ tile ¸ si cuno¸ stin¸ tele legate de Stratego într-un joc
împotriva agentului "StrategoAI".
Artiﬁcial Intelligence is used in video games to generate adaptive and intelligent behav-
iors similar to human intelligence. Stratego is an extremely difﬁcult game for a computer
program to understand. The multitude of rules and strategies, but also the incomplete in-
formation that is available to the player make it one of the unresolved issues in the ﬁeld of
intelligent software agents for games.
The purpose of the present study is to analyze the various approaches proposed over
time and to implement an intellinget, intermediate level bot for the game of Stratego. In the
paper, the implementation stages of the intelligent agent are described. "StrategoAI" – the
agent that is created uses heuristics for the initial setup of the board for the game and also,
for planning the moves. The application allows any player to test their skills and knowledge
of Stratego in a game against "StrategoAI".
i

Prefa¸ t ˘a
Aceast ˘a lucrare concluzioneaz ˘a o lung ˘a ¸ si anevoioas ˘a, dar în acela¸ si timp frumoas ˘a perioad ˘a
în care mi-am permis s ˘a m˘a joc cu ideile ce puteau, sau nu, s ˘a ofere rezultate. A fost o c ˘al˘a-
torie diﬁcil ˘a, la începutul c ˘areia, obstacolele p ˘areau de nedoborât, îns ˘a cu cât m ˘a apropiam
mai mult de ﬁnal, nici o problem ˘a nu mai p ˘area s ˘a ﬁe de nerezolvat. În acest moment, micile
probleme "r ˘amase" sunt nesemniﬁcative fa¸ t ˘a de cele peste care am trecut pan ˘a acum ¸ si pot
privi în urm ˘a cu satisfac¸ tie la ceea ce am realizat.
¸ Tin s˘a le mul¸ tumesc celor doi coordonatori, doamnei Lector dr. Elena B ˘autu ¸ si domnului
Profesor dr. Dorin-Mircea Popovici, f ˘ar˘a ajutorul c ˘arora nu a¸ s ﬁ reu¸ sit s ˘a duc la bun sfâr¸ sit
aceast ˘a c˘al˘atorie. Mul¸ tumesc ¸ si familiei care mi-a fost al ˘aturi ¸ si m-a sus¸ tinut în aceast ˘a
perioad ˘a. Nu în ultimul rând le sunt recunosc ˘ator colegilor ¸ si prietenilor mei care mi-au
suportat întreb ˘arile, pove¸ stile ¸ si au fost de acord s ˘a joace Stratego pentru a-mi testa aplica¸ tia.
ii

Cuprins
Abstract i
Prefa¸ t ˘a ii
Cuprins iii
Lista Figurilor 1
1 Introducere 2
1.1 Jocul Stratego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 De ce Stratego? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Starea actual ˘a a domeniului 4
2.1 Abord ˘ari Similare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Algoritmul Minmax . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Algoritmi Genetici . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.3 Juc ˘atori inteligen¸ ti existen¸ ti . . . . . . . . . . . . . . . . . . . . . 10
2.2 Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Caracteristici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Exemplu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
iii

Cuprins Cuprins
3 Stratego: Concepte de baz ˘a 14
3.1 Valorile euristice ale pieselor . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1.1 Deﬁni¸ tia problemei . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1.2 Implementare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Valoarea informa¸ tiei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2.1 Implementare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Stadiul jocului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Pozi¸ tii strategice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4.1 Culoar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Crearea unei formule ini¸ tiale de start 20
4.1 Importan¸ ta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Euristic ˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2.1 Pozi¸ tionarea Steagului . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.2 Pozi¸ tionarea Bombelor . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.3 Piese de rang mare . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2.4 Piese de rang mediu ¸ si mic . . . . . . . . . . . . . . . . . . . . . . 22
4.3 Implementare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 Planiﬁcarea mut ˘arilor 24
5.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.1.1 Avantaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.1.2 Dezavantaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 Algoritm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.3 Planuri folosite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.4 Planuri tactice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.4.1 Planul de capturare imediat ˘a . . . . . . . . . . . . . . . . . . . . . 27
5.4.2 Planul de defensiv ˘a tactic ˘a . . . . . . . . . . . . . . . . . . . . . . 28
iv

Cuprins Cuprins
5.4.3 Planul de atac tactic . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.4.4 Planul de dezamorsare a Bombelor . . . . . . . . . . . . . . . . . . 29
5.4.5 Ap ˘ararea Mare¸ salului . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.5 Planuri strategice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.5.1 Planul de atac strategic . . . . . . . . . . . . . . . . . . . . . . . . 30
5.5.2 Planul de defensiv ˘a strategic ˘a . . . . . . . . . . . . . . . . . . . . 30
5.6 Planuri generale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.6.1 Plan aleator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.6.2 Planul de pedeaps ˘a pentru mutare . . . . . . . . . . . . . . . . . . 31
6 Concluzie 32
6.1 Lucru pe viitor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Referin¸ te bibliograﬁce 33
Anexa 1: Stratego 35
1.1 Jocul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Cum sa preg ˘ate¸ sti jocul? . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Mod de joc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Reguli de mutare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Reguli de atac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Reguli de rang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Sugestii de strategii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Victoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.2 Reguli de repeti¸ tie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Regula celor 2 p ˘atrate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Implementare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Exempliﬁcare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Regula de mai multe p ˘atrate . . . . . . . . . . . . . . . . . . . . . . . . . 39
v

Cuprins Cuprins
1.3 Reguli Adi¸ tionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Avantajul Agresorului . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Defensiv ˘a Silen¸ tioas ˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Salvare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
vi

Lista Figurilor
1.1 Stratego.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 X ¸ si O, Go, Awari.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Arbore MinMax3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Arbore MinMax + Alpha-Beta-Prunning4. . . . . . . . . . . . . . . . . . . . 6
2.3 Albastru câ¸ stig ˘a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Pa¸ sii unui Algoritm Genetic5. . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.5 Probe6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Harta României7colorat ˘a în func¸ tie de jude¸ tul în care locuiesc: Exemplu în
Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1 Albastru are avantaj? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Albastru folose¸ ste culoarele pentru ap ˘arare . . . . . . . . . . . . . . . . . . . . 19
5.1 G ˘asirea celei mai bune mut ˘ari . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2 Colonelul este în pericol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.1 Regula celor 2 p ˘atrate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1

Capitolul 1
Introducere
1.1 Jocul Stratego
Jocul Stratego a fost creat de Jacques Johan Mogendorff ¸ si mai târziu produs de compania
Jumbo [1]. Este un joc în care juc ˘atorii de¸ tin informa¸ tii incomplete. Fiecare juc ˘ator are
o armat ˘a iar scopul ﬁnal este capturarea steagului inamic. Locul exact al pieselor este, la
început, cunoscut doar de cel ce le de¸ tine. Juc ˘atorii î¸ si mut ˘a câte o pies ˘a, pe rând, pe o pozi¸ tie
al˘aturat ˘a, liber ˘a sau pe care se aﬂ ˘a o pies ˘a a inamicului. În cel de-al doilea caz, o b ˘at˘alie are
loc. Piesa mai slab ˘a este eliminat ˘a iar identitatea piesei câ¸ stig ˘atoare este descoperit ˘a. Pe
m˘asur˘a ce jocul progreseaz ˘a, se cunoa¸ ste tot mai mult ˘a informa¸ tie. Mai multe informa¸ tii
legate de Stratego cât ¸ si regulamentul complet al jocului se g ˘asesc în Anexa 1.
Figura 1.1 : Stratego.1
1Imaginea, https://ru.wikipedia.org/wiki/Stratego_setup.jpg , este etichetat ˘a cu per-
misiune de reutilizare la data de 15.06.2018
2

Introducere De ce Stratego?
1.2 De ce Stratego?
Am ales aceast ˘a tem ˘a, deoarece sunt pasionat de jocurile de strategie, precum,¸ Sah, Go, Dame
¸ si Stratego. Acest tip de jocuri dezvolt ˘a gândirea analitic ˘a ¸ si ajut ˘a la imbun ˘at˘a¸ tirea memoriei.
De-a lungul timpului implementarea unor juc ˘atori inteligen¸ ti eﬁcien¸ ti pentru astfel de
jocuri a reprezentat un pas esen¸ tial în dezvoltarea inteligen¸ tei artiﬁciale ¸ si in¸ telegerea gândirii
umane. În prezent, exist ˘a o mul¸ time de algoritmi dezvolta¸ ti pentru jocuri precum ¸ sahul, unde
calculatorul poate investiga toate posibilele mut ˘ari chiar ¸ si cu un anumit num ˘ar de pa¸ si în
viitor. X ¸ si O, Go sau Awari sunt alte jocuri considerate ca ﬁind rezolvate, însemnând c ˘a,
pentru toate situa¸ tiile, calculatorul ¸ stie care este cea mai bun ˘a solu¸ tie pentru a ca¸ stiga jocul.
Go reprezint ˘a cea mai recent rezolvat ˘a problem ˘a. În 2015, AlphaGo [2], juc ˘atorul in-
teligent creat de compania Google DeepMind, este primul program de calculator ce învinge
un juc ˘ator profesionist la Go. Acest program este bazat pe algoritmul de c ˘autare Monte-Carlo
¸ si înva¸ t ˘a din jocurile precedente datorit ˘a unei re¸ tele neuronale.
Figura 1.2 : X ¸ si O, Go, Awari.2
În cazul jocului Stratego, spre deosebire de celelalte, enumerate anterior, informa¸ tia
este incomplet ˘a ceea ce înseamn ˘a c˘a necesit ˘a abilit ˘a¸ ti umane precum analizarea gândirii
adversarului. Juc ˘atorii nu numai c ˘a încearc ˘a s˘a ascund ˘a cât mai mult ˘a informa¸ tie fa¸ t ˘a de
adversar în timp ce încearc ˘a s˘a intre în mintea sa, trebuie ¸ si s ˘a foloseasc ˘a informa¸ tiile pe
care le de¸ tin pentru a utiliza tactici ¸ si strategii cât mai bune. Este, adesea, extrem de greu
s˘a g˘ase¸ sti "cea mai bun ˘a" mutare, deoarece nu conteaz ˘a doar ce ¸ sti despre situa¸ tia actual ˘a a
jocului, ci ¸ si ce crede oponentul c ˘a ¸ stie.
Misiunea unui juc ˘ator inteligent de Stratego este extrem de diﬁcil ˘a. Acesta este nevoit
s˘a "ghiceasc ˘a" piesele adversarului ¸ si în acela¸ si timp s ˘a intuiasc ˘a urm ˘atoarele mi¸ sc ˘ari. Juc ˘a-
torul, pe care mi-am propus s ˘a îl realizez, este capabil s ˘a creeze formule de start cât mai
originale, s ˘a fac ˘a presupuneri legate de piesele necunoscute ale adversarului ¸ si s ˘a fac ˘a mut ˘ari
cât mai corecte pentru al ajuta în câ¸ stigarea unui joc de Stratego.
2Imaginile https://commons.wikimedia.org/wiki/File:Go_game_Kobayashi-Kato.
png ¸ sihttps://upload.wikimedia.org/wikipedia/commons/0/0e/Awalé.png sunt
etichetate cu permisiune de reutilizare la data de 15.06.2018
3

Capitolul 2
Starea actual ˘a a domeniului
Un juc ˘ator inteligent este un agent software (Bot), ce poate juca un anumit joc în locul unei
persoane. Acesta reprezint ˘a conceptul de inteligent ˘a artiﬁcial ˘a aplicat în domeniul jocurilor.
În 1950, Alan Turing creaz ˘a "Testul Turing" [3] cunoscut ¸ si ca "Jocul Imita¸ tiei", ¸ si astfel a
fost dezvoltat primul juc ˘ator inteligent din istorie.
În 1951, folosind calculatorul universit ˘a¸ tii din Manchester, Ferranti Mark 1, Christopher
Strachey a scris primul program ce poate juca Dame, iar Dietrich Prinz scrie primul juc ˘ator
de ¸ sah din lume.
2.1 Abord ˘ari Similare
De-a lungul timpului, matematicienii ¸ si informaticienii s-au concentrat foarte mult pe in-
teligenta artiﬁcial ˘a ¸ si pe dezvoltarea juc ˘atorilor inteligen¸ ti. Odat ˘a cu trecerea anilor, teoria
se transform ˘a în cod ¸ si astfel apar primii algoritmi implementa¸ ti pentru a rezolva problemele
ridicate de jocurile de strategie.
Multitudinea de jocuri ¸ si diferitele încerc ˘ari de rezolvare a acestora duc la apari¸ tia mul-
tor algoritmi, euristici ¸ si strategii. Fiecare dintre acestea serve¸ ste unui tip de abordare diferit
care dore¸ ste s ˘a ob¸ tin ˘a rezultate mai bune decât al celor precedente.
În aceasta sec¸ tiune sunt prezenta¸ ti doi dintre cei mai des întâlni¸ ti algoritmi în dez-
voltarea de juc ˘atori inteligen¸ ti cât ¸ si câteva dintre cele mai populare abord ˘ari ale jocului
Stratego.
4

Starea actual ˘a a domeniului Abord ˘ari Similare
2.1.1 Algoritmul Minmax
Introducere
Algoritmul Minmax [4] este de departe cel mai popular algoritm folosit la jocurile "de mas ˘a"
de doi juc ˘atori. Permite programatorului sa creeze un adversar computerizat rezonabil.
Deoarece este exponen¸ tial in numarul de mut ˘ari, num ˘arul de viitori pa¸ si în care poate c ˘auta
este limitat.
Algoritmul
Minmax este un depth-ﬁrst search (DFS) peste arborele de c ˘autare al jocului pana la o an-
umit ˘a adâncime. Denumirea vine de la cei doi juc ˘atori, numi¸ ti MIN ¸ si MAX deoarece,
juc˘atorul ce face o mutare dore¸ ste sa i¸ si maximizeze câ¸ stigul iar scopul adversarului s ˘au este
s˘a il minimizeze. La ﬁecare nod, când MIN trebuie s ˘a faca o mutare, valoarea minim ˘a a
copiilor este valoarea acestui nod. Când este rândul lui MAX s ˘a mute, valoarea nodului este
maximul dintre valorile copiilor s ˘ai. În ﬁgura 2.1, este ilustrat un arbore de c ˘autare Minmax.
Valorile celui de-al doilea nivel reprezint ˘a minimul dintre valorile nodurilor de pe nivelul
trei iar nodul de pe primul nivel preia valoarea maxim ˘a dintre cele de pe nivelul doi. Acest
algoritm nu returneaz ˘a cea mai buna solu¸ tie, ci o solu¸ tie de "compromis".
Figura 2.1 : Arbore MinMax1
1Imagine adaptat ˘a dup ˘a [4]
5

Starea actual ˘a a domeniului Abord ˘ari Similare
Alpha-Beta-Prunning
Alpha-Beta-Prunning este un plus adus algoritmului Minmax, menit s ˘a scurteze timpul com-
puta¸ tional. Datorit ˘a faptului c ˘a algoritmul alterneaz ˘a între alegerea minimului ¸ si al maximu-
lui, putem s ˘a ne folosim de rezultatul precedent pentru a scurta c ˘autarea. Dac ˘a este c ˘autat ˘a o
valoare maxim ˘a iar primul rezultat de pe nivelul juc ˘atorului MIN este 2, pentru a se produce
modiﬁc ˘ari este nevoie ca urm ˘atorul nod s ˘a aibe ca rezultat un num ˘ar mai mare decât 2. Îns ˘a,
având în vedere c ˘a acest nod caut ˘a valoarea minim ˘a dintre copii iar primul copil are valoarea
1, indiferent ce valoare are cel de-al doilea copil MAX va primi ca rezultat 2.
Figura 2.2 : Arbore MinMax + Alpha-Beta-Prunning2
MinMax pentru jocuri
Unii dintre cei mai puternici juc ˘atori inteligen¸ ti de pân ˘a acum folosesc, la baz ˘a, algoritmul
Minmax. Cel mai bun exemplu este DeepBlue [5], bot-ul care a învins în 1997 campionul
mondial la ¸ sah. Avantajul acestei metode const ˘a în faptul c ˘a necesit ˘a un minim de cuno¸ stin¸ te
despre joc din partea programatorului, ceea ce o face o metod ˘a ideal ˘a pentru dezvoltarea de
juc˘atori inteligen¸ ti pentru jocuri mai pu¸ tin cunoscute. Succesul algoritmului depinde, îns ˘a,
de tipul jocului.
Informa¸ tia complet ˘a este foarte important ˘a în construirea unui arbore de c ˘autare. În
cadrul jocurilor cu informa¸ tie incomplet ˘a, apar multe momente în interiorul arborelui unde
algoritmul nu ¸ stie cum s ˘a continue far ˘a sa cunoasc ˘a informa¸ tie ascuns ˘a. Aceast ˘a problem ˘a
poate ﬁ dep ˘a¸ sit˘a cu ajutorul unor presupuneri, dar acest lucru face ca rezultatul corect s ˘a nu
mai ﬁe garantat. Cu cât jocul este mai complex, cu atât algoritmul devine mai slab.
Majoritatea juc ˘atorilor inteligen¸ ti de Stratego sunt baza¸ ti pe algoritmul de c ˘autare Min-
Max. De¸ si acest tip de abordare poate, cu foarte mare u¸ surin¸ t ˘a, rezulta într-un bot superﬁcial,
2Imagine adaptat ˘a dup ˘a [4]
6

Starea actual ˘a a domeniului Abord ˘ari Similare
s-a dovedit c ˘a acesta nu poate ajunge niciodat ˘a la nivelul unui juc ˘ator de Stratego experimen-
tat.
MinMax pentru Stratego
De¸ si Stratego este un joc cu informa¸ tie incomplet ˘a, ceea ce ar putea face func¸ tionarea algo-
ritmului extrem de diﬁcil ˘a, adev ˘arata problem ˘a nu este acest lucru, ci adâncimea c ˘aut˘arii.
Un simplu exemplu unde un Cerceta¸ s se aﬂ ˘a la o distan¸ t ˘a de 8 mut ˘ari fa¸ t ˘a de Steagul
inamic necesit ˘a o c ˘autare pe 16 niveluri. Având în vedere faptul c ˘a Stratego este un joc
complex, num ˘arul de noduri pe ﬁecare nivel poate ﬁ extrem de mare. O pies ˘a ce se aﬂ ˘a în
mijlocul plan¸ sei poate face 4 mut ˘ari, iar cerceta¸ sul poate face chiar 18 mut ˘ari. Acest lucru
face ca o c ˘autare in adâncime pe 16 niveluri sa ﬁe imposibil de realizat. Lucrurile se pot
complica ¸ si mai mult din cauza situa¸ tiilor repetitive. În cazul în care o pies ˘a este amenin¸ tat ˘a
de inamic, dac ˘a juc ˘atorul nu i¸ si permite s ˘a piard ˘a aceast ˘a pies ˘a, acesta este nevoit s ˘a sacriﬁce
o mutare pentru a se indep ˘arta de zona primejdioas ˘a. Datorit ˘a regulilor de repeti¸ tie, la un
moment dat, cel ˘alalt juc ˘ator va trebui s ˘a se opreasc ˘a din a amenin¸ ta piesa, dar chiar ¸ si în
cele mai simple situa¸ tii este permis ˘a folosirea a 3 astfel de mut ˘ari pentru ﬁecare alt ˘a mutare.
Astfel adâncimea arborelui creste de 3 ori. Dou ˘a astfel de situa¸ tii fac ca num ˘arul de niveluri
s˘a se multiplice de 6 ori ¸ si situa¸ tii ¸ si mai rele pot ﬁ posibile.
S˘a lu˘am ca exemplu ﬁgura 2.3: Este rândul juc ˘atorului albastru. Dac ˘a toate piesele sunt
cunoscute, aceasta este o victorie sigur ˘a pentru albastru. Poate folosi Mare¸ salul pentru a
elimina Colonelul, iar Maiorul din fa¸ ta Steagului poate ﬁ folosit ca ¸ si ultima linie de ap ˘arare
pentru a elimina Minerii, în cazul în care ace¸ stia reu¸ sesc s ˘a se apropie ¸ si s ˘a dezamorseze
Bombele. În aceast ˘a situa¸ tie juc ˘atorul ro¸ su nu are nici o ¸ sans ˘a s˘a câ¸ stige, indiferent de
mut˘arile pe care le face. Cel mai scurt drum spre victorie pentru albastru const ˘a, îns ˘a din 17
mut˘ari ceea ce înseamn ˘a o adâncime de 34 de niveluri. Asta doar dac ˘a juc ˘atorul ro¸ su nu î¸ si
mut˘a Minerii simultan în încercarea de a coordona un atac p ¸entru a deruta adversarul a¸ step-
tând o gre¸ seal ˘a. Dac ˘a asta se întâmpl ˘a, se poate ajunge într-o bucl ˘a repetitiv ˘a de maxim 3
mut˘ari. În acest caz, primele 8 mut ˘ari se multiplica de 3 ori, apoi mai este nevoie de inc ˘a 11
mut˘ari pentru a captura Steagul. Se ajunge la un total de 35 de mut ˘ari, adic ˘a o adâncime de
70 niveluri. Dac ˘a lu˘am în considerare faptul c ˘a algoritmul Minmax are o complexitate expo-
nen¸ tial ˘a cu cât arborele are o adâncime mai mare, este foarte pu¸ tin probabil ca un calculator
s˘a î¸ si poat ˘a da seama din aceast ˘a pozi¸ tie c ˘a este victoria albastrului.
7

Starea actual ˘a a domeniului Abord ˘ari Similare
Figura 2.3 : Albastru câ¸ stig ˘a
Se pare c ˘a, pentru Stratego, spre deosebire de ¸ Sah, Go sau alte jocuri de acest gen, unde
computer-ul are rezultate mult mai bune decât un om, num ˘arul de mut ˘ari pe care o persoan ˘a
le poate vedea în viitor este mult mai mare decât ale unui calculator. Chiar ¸ si în acest caz,
unde bot-ul are la dispozi¸ tie informa¸ tie complet ˘a, num ˘arul de mut ˘ari este mult prea mare.
Cum este posibil ca un om s ˘a poat ˘a calcula mai mult decât un calculator în Stratego?
Motivul pentru care acest lucru este posibil, este faptul c ˘a, pentru Stratego, oamenii gândesc
în planuri. Nu gândesc ﬁecare mutare separat, ci privesc în ansambul mut ˘arile ce îi ajut ˘a sa
ating ˘a anumite ¸ teluri.
În cadrul situa¸ tiei precedente juc ˘atorul are doar 2 scopuri. Elimin ˘a Minerii ¸ si captureaz ˘a
Steagul. Importan¸ ta primului plan poate ﬁ m ˘asurat ˘a prin faptul c ˘a, în caz c ˘a acesta este omis,
juc˘atorul ro¸ su poate câstiga înaintea celui albastru. A¸ sadar capturarea Minerilor ro¸ sii este o
prioritate.
În loc s ˘a se uite la ﬁecare mutare ¸ si s ˘a analizeze unde ar putea duce aceasta, o persoan ˘a
se gânde¸ ste la un plan, apoi caut ˘a mut ˘arile care l-ar putea ajuta la îndeplinirea acestuia.
8

Starea actual ˘a a domeniului Abord ˘ari Similare
2.1.2 Algoritmi Genetici
Introducere
Algoritmii genetici [6] sunt tehnici adaptive de c ˘autare euristic ˘a, bazate pe principiile
geneticii ¸ si ale selec¸ tiei naturale, enun¸ tate de Darwin, în care indivizii mai buni au ¸ sanse mai
mari s ˘a supravie¸ tuiasc ˘a ¸ si s ˘a produc ˘a urma¸ si în genera¸ tiile urm ˘atoare.
Algoritmul
Algoritmul lucreaz ˘a cu o mul¸ time de posibile solu¸ tii, numit ˘a Popula¸ tie, ini¸ tializat ˘a aleator.
Evalueaz ˘a ﬁecare solu¸ tie ¸ si îi atribuie un "scor". Selecteaz ˘a apoi indivizi din popula¸ tie, dup ˘a
anumite criterii, care evolueaz ˘a prin aplicarea operatorului de încruci¸ sare ¸ si se formeaz ˘a o
nou˘a genera¸ tie. Copilul, ce rezult ˘a din aceast ˘a combina¸ tie poate suferi o muta¸ tie prin care i
se modiﬁc ˘a u¸ sor materialul genetic. Este eliminat ˘a apoi o solu¸ tie de care nu mai este nevoie
pentru a face loc noului individ.
Figura 2.4 : Pa¸ sii unui Algoritm Genetic3
9

Starea actual ˘a a domeniului Abord ˘ari Similare
Begin
t:=0
Initialize Population(t)
Evaluate Population(t)
While (not stop condition) do
t:=t+1
Select Population(t)
Crossover
Mutate
Survivor Selection
Evaluate Population(t)
End While
Return Best
End
Listing 2.1 : Schema clasic ˘a a unui algoritm genetic
Algoritmi Genetici pentru Stratego
S-a încercat pân ˘a acum folosirea algoritmilor genetici pentru a crea juc ˘atori inteligen¸ ti de
Stratego. Bot-ul lui Ryan Albarelli [7] creat în 2003 este bazat pe un algoritm genetic ¸ si
algoritmul Minmax pentru a-i permite s ˘a calculeze mut ˘ari în viitor. Acesta nu a reu¸ sit, îns ˘a,
s˘a implementeze un bot suﬁcient de inteligent pentru a ﬁ la acela¸ si nivel cu o persoana.
Algoritmul se descurca bine ¸ si evolua doar când juca împotriva sa. Prin lucrarea sa a deschis,
îns˘a, por¸ tile pentru urm ˘atoare studii ¸ si încerc ˘ari de implementare a algoritmilor genetici cu
Minmax pentru alte jocuri de mas ˘a.
În 2012, în cadrul lucr ˘arii sale de licen¸ t ˘a în Inteligen¸ t ˘a Artiﬁcial ˘a, R.M. de Boer [8],
continu ˘a ceea ce a început Ryan Albarelli. Tehnica pe care o folose¸ ste pentru algoritmul
genetic const ˘a într-o popula¸ tie formata din juc ˘atori ¸ si utilizeaz ˘a 2 tipuri de parametri. Prima
categorie motiveaz ˘a dorin¸ ta de a face anumite mut ˘ari, iar a doua reprezint ˘a valoarea pozi¸ tiilor
pe plan¸ s ˘a. "ViCKI", a¸ sa cum a fost denumit bot-ul, este un juc ˘ator rezonabil, capabil s ˘a fac ˘a
mut˘ari soﬁsticate ¸ si s ˘a se adapteze la stilul de joc al oponentului.
2.1.3 Juc ˘atori inteligen¸ ti existen¸ ti
De-a lungul timpului au fost crea¸ ti mul¸ ti juc ˘atori inteligen¸ ti de Stratego. "Probe" [9] este
primul bot, creat în 1983, acesta necesita un supercomputer pentru a rula. Cu timpul, a
fost imbun ˘at˘a¸ tit, ajungând ca în momentul de fa¸ t ˘a s˘a ﬁe cel mai puternic bot de Stratego.
Folose¸ ste algoritmul Minimax cu o func¸ tie de evaluare soﬁsticat ˘a. Face predic¸ tii legate de
piesele adversarului ¸ si detecteaz ˘a tipare în stilul de joc al oponentului.
3Imagine adaptat ˘a dup ˘ahttps://www.tutorialspoint.com/genetic_algorithms/
genetic_algorithms_fundamentals.htm , accesat la data de 15.06.2018
10

Starea actual ˘a a domeniului Processing
Figura 2.5 : Probe4.
"RandomBot" este folosit ca un bot de test. Formula de start ini¸ tiala este generat ˘a com-
plet aleator ¸ si mut/u arile sunt gasite prin alegerea unei piese, ce se poate muta, la întâmplare,
repozi¸ tionarea ei ﬁind f ˘acut˘a tot aleator.
"StarBot" [10], creat în 2010, folose¸ ste minimax cu alpha-beta-prunning. Cu ajutorul
minimax caut ˘a mut ˘ari câ¸ tiva pa¸ si înainte. Pentru ﬁecare rund ˘a toate posibilele mut ˘ari sunt
returnate ¸ si presupune c ˘a inamicul va face cea mai dezavantajoas ˘a mutare. Pentru a scurta
timpul computa¸ tional aplic ˘a alpha-beta-prunning. Puterea bot-ului depinde de dimensiunea
de c˘autare.
"Invincible" [11], dezvoltat în 2007 de c ˘atre Vincent de Boer, este concentrat pe ¸ teluri
sau planuri speciﬁce în Stratego. Atunci când detecteaz ˘a steagul inamic, va muta piesele
necesare pentru a câ¸ stiga.
"ViCKI"[8], folose¸ ste un algoritm genetic pentru a se antrena. Folose¸ ste atât parametrii
ce motiveaz ˘a anumite ac¸ tiuni, cât ¸ si parametrii ce con¸ tin valoarea pieselor de pe plan¸ s ˘a.
2.2 Processing
Limbajul de programare pe care l-am ales pentru a programa "StrategoAI" este Processing.
Am ales acest limbaj datorit ˘a u¸ surin¸ tei cu care elementele graﬁce [12] pot ﬁ implementate ¸ si
controlate, pentru a m ˘a putea concentra asupra dezvolt ˘arii inteligen¸ tei artiﬁciale.
4Captur ˘a de ecran de pe https://download.cnet.com/Probe/3000-18516_4-10922206.
html , accesat la data de 15.06.2018
11

Starea actual ˘a a domeniului Processing
Processing [13] este un limbaj de programare, open-source, pentru codare în contextul
artelor vizuale ¸ si un mediu de dezvoltare integrat (IDE). Este bazat pe limbajul Java dar
folose¸ ste sintaxe simpliﬁcate ¸ si o interfa¸ t ˘a graﬁc ˘a (GUI). Reprezint ˘a o modalitate u¸ soara de
programare, cu peste 100 de libr ˘arii implementate peste soft-ul Java. Are ca scop înv ˘a¸ tarea
non-programatorilor fundamentele program ˘arii într-un context vizual.
Proiectul a fost ini¸ tiat, în 2001, de c ˘atre Ryan Hopkins, Casey Reas ¸ si Ben Fry. În 2012
au început Funda¸ tia Processing împreun ˘a cu Daniel Shiffman.
2.2.1 Caracteristici
Processing folose¸ ste schi¸ te , o alternativ ˘a pentru un mediu integrat de dezvoltare, pentru a
organiza proiectele. Fiecare schi¸ t ˘a Processing este de fapt o subclas ˘a a clasei PApplet din
Java ce implementeaz ˘a majoritatea caracteristicilor limbajului Processing.
Toate clasele adi¸ tionale sunt tratate ca ﬁind clase interioare atunci când codul este tradus
în Java pur înainte de compilare. Acest lucru face ca utilizarea variabilelor ¸ si metodelor
statice sa ﬁe interzise în Processing dac ˘a nu se folose¸ ste modul de programare pur Java.
2.2.2 Exemplu
Processing este un limbaj de programare graﬁc ˘a ¸ si de aceea am ales ca exemplu prelucrarea
unei imaginii ¸ si colorarea acesteia.
Figura 2.6 : Harta României5colorat ˘a în func¸ tie de jude¸ tul în care locuiesc: Exemplu în Processing
12

Starea actual ˘a a domeniului Processing
PShape romania;
PShape judet;
// ROU *** reprezinta id-urile judetelor
String [] Locuiesc = { "ROU133" };
String [] Celelalte = {"ROU122", "ROU123", "ROU124", "ROU126", "ROU127",
"ROU128", "ROU129", "ROU130", "ROU131", "ROU132", "ROU276",
"ROU277", "ROU278", "ROU280", "ROU287", "ROU294", "ROU295", "ROU296", "
ROU297", "ROU298", "ROU299", "ROU300", "ROU301", "ROU302",
"ROU303", "ROU304", "ROU305", "ROU306", "ROU307", "ROU308", "ROU309", "
ROU310", "ROU311", "ROU312", "ROU313", "ROU314", "ROU315", "ROU316", "
ROU317", "ROU4844", "ROU4847"
};
void setup() {
size(990, 700);
romania = loadShape("ro.svg");
smooth(); // Imbunatateste calitatea SVG-ului
noLoop();
}
void draw() {
background(255);
// Deseneaza harta
shape(romania, 0, 0);
// Cu verde sunt colorate judetele
statesColoring(Celelalte , color(0, 100, 0));
// Cu rosu este colorat judetul in care locuiesc
statesColoring(Locuiesc, color(255, 0, 0));
// Salveaza harta ca si imagine
saveFrame("map output.png");
}
void statesColoring(String[] judete, int c){
for (int i = 0; i < judete.length; ++i) {
PShape judet = romania.getChild(judete[i]);
// Dezactiveaza culorile volosite in fisierul SVG
judet.disableStyle();
// Foloseste propriile culori
fill(c);
noStroke();
// Deseneaza un singur judet
shape(judet, 0, 0);
}
}
Acest exemplu6în Processing aﬁ¸ seaz ˘a harta Romaniei ¸ si coloreaz ˘a jude¸ tul în care locui-
esc în culoarea ro¸ sie ¸ si celelalte jude¸ te ale ¸ t ˘arii cu verde. Este demonstrat ˘a u¸ surin¸ ta cu care
se pot prelucra imagini ¸ si obiecte graﬁce prin intermediul acestui limbaj de programare.
5Fi¸ sierul ro.svg are licen¸ ta gratuit ˘a pentru uz personal ¸ si comericial. https://simplemaps.com/
resources/svg-ro accesat la data de 15.06.2018
6Exemplu adaptat dupa "United States presidential election map" de pe site-ul https://
en.wikipedia.org/wiki/Processing_(programming_language) accesat la data de
15.06.2018
13

Capitolul 3
Stratego: Concepte de baz ˘a
În aceast capitol sunt explicate câteva concepte de baz ˘a pentru Stratego. Aceast ˘a parte const ˘a
doar din cuno¸ stin¸ tele mele legate de joc ¸ si modul în care am ales s ˘a le implementez în
"StrategoAI".
3.1 Valorile euristice ale pieselor
V oi explica, în cele ce urmeaz ˘a, felul în care am abstractizat problema jocului Stratego,
pentru o implementare potrivit ˘a. Pentru c ˘a abordarea pe care o voi folosi este una de tip
euristic, am avut nevoie s ˘a ata¸ sez ﬁec ˘arei piese din joc o valoare numerica.
3.1.1 Deﬁni¸ tia problemei
Este foarte important ca piesele s ˘a aib ˘a valori numerice. Acest lucru ajut ˘a, spre exemplu, la
calcularea proﬁtului atac ˘arii unei piese, sau pentru a alege dac ˘a este mai bine s ˘a atac ˘am o
anumit ˘a pies ˘a sau o alta.
Problema de a da o valoare unei anumite piese este una foarte diﬁcil ˘a în Stratego. De
obicei, este adev ˘arat c ˘a piesa de rang mai mare trebuie s ˘a aib ˘a o valoare mai mare, dar pentru
atribuirea unei valori trebuie luate în calcul abilit ˘a¸ tile pe care le au piesele. Este adev ˘arat c ˘a
piesele mai puternice au mai multe abilit ˘a¸ ti decât cele mai slabe deoarece pot captura mai
multe piese, îns ˘a s˘a nu uit ˘am ca exist ˘a piese cu puteri speciale. Spionul este singurul care
poate învinge Mare¸ salul, Minerul este singurul care poate dezamorsa o Bomb ˘a. ¸ Si mut ˘arile
pe care o pies ˘a le poate face sunt luate în calcul. Bomba, cu toate c ˘a poate captura aproape
toate piesele, nu se poate mi¸ sca. Nu putem sa îi calcul ˘am valoarea Cerceta¸ sului f ˘ar˘a s˘a ¸ tinem
cont de faptul c ˘a se poate muta mai multe pozi¸ tii pe tur ˘a, ba chiar poate ¸ si ataca în acela¸ si
timp. Este greu s ˘a g˘ase¸ sti o formul ˘a pentru a calcula valoarea piesei ¸ si în func¸ tie de rang dar
¸ si în func¸ tie de abilit ˘a¸ ti speciale.
14

Stratego: Concepte de baz ˘a Valorile euristice ale pieselor
Dup˘a rezolvarea acestei probleme, mai apare înc ˘a una. Un Mare¸ sal (10) este mult
mai valoros decât un Colonel (8) deoarece Mare¸ salul poate captura orice pies ˘a în timp ce
Colonelul nu poate, ba chiar poate ﬁ capturat de Generalul (9) sau Mare¸ salul adversarului.
S˘a presupunem c ˘a oponentul nu mai are nici Mare¸ salul, nici Generalul. Atunci Mare¸ salul
î¸ si pierde avantajul pe care îl de¸ tinea în fa¸ ta Colonelului deoarece în situa¸ tia de fa¸ t ˘a ambele
piese pot captura orice alt ˘a pies ˘a de¸ tine adversarul. Mare¸ salul ¸ si Colonelul vor avea acea¸ si
valoare.
În ﬁgura 3.1 pare ca juc ˘atorul albastru are un avantaj deoarece de¸ tine piese mai puter-
nice decât cel ro¸ su. Acest lucru este pe jum ˘atate adev ˘arat. La începutul jocului, s ˘a sacriﬁci
2 Locotenen¸ ti pentru a putea s ˘a capturezi Mare¸ salul oponentului este o strategie proﬁtabil ˘a.
S˘a presupunem, îns ˘a, c˘a în situa¸ tia de fa¸ t ˘a Mare¸ salul albastru este singura pies ˘a cunoscut ˘a
de pe tabl ˘a, ceea ce este un lucru extrem de posibil în stadiul ﬁnal al unei partide. Atât timp
cât îi cunoa¸ ste loca¸ tia, juc ˘atorul ro¸ su se poate plimba lini¸ stit pe plan¸ s ˘a capturând Minerii si
eventual Steagul. Singura speran¸ t ˘a a albastrului este s ˘a reu¸ seasc ˘a s˘a se protejeze cu C ˘api-
tanul ¸ si s ˘a se ajung ˘a la o situa¸ tie de egalitate.
Figura 3.1 : Albastru are avantaj?
15

Stratego: Concepte de baz ˘a Valorile euristice ale pieselor
Acest exemplu demonstraz ˘a c˘a piesele nu ar trebui s ˘a aib ˘a valori absolute, ci acestea
trebuie s ˘a se modiﬁce in func¸ tie de piesele pe care le de¸ tine oponentul. De asemenea de-
mostraz ˘a ¸ si faptul c ˘a nici piesele de acela¸ si rang nu ar trebui s ˘a aib ˘a mereu aceea¸ si valoare.
Minerii alba¸ stri au o valoare mai mare decât cei ro¸ sii deoarece ace¸ stia reprezint singura ¸ sans ˘a
a juc ˘atorului albastru s ˘a ajung ˘a la Steagul ro¸ su. Piesele ro¸ sii au drumul deschis c ˘atre Steagul
oponentului ceea ce face ca valoarea Minerilor s ˘a scad ˘a.
3.1.2 Implementare
Pentru calcularea valorilor numerice asociate pieselor, implementez aceea¸ si metod ˘a utilizat ˘a
de "Invincible". Valorile pieselor se recalculeaz ˘a dup ˘a ﬁecare mutare. Regula prin care
atribui valori pieselor este urm ˘atoarea: O pies ˘a valoreaz ˘a mai mult decât o pies ˘a de rang mai
mic doar dac ˘a oponentul are o pies ˘a ce poate ﬁ capturat ˘a de aceasta dar nu ¸ si de piesa mai
mic˘a. Mai jos este descris ˘a, în pseudo-cod, metoda. Prima valoare este constant ˘a iar apoi
se trece prin toate rangurile pieselor ¸ si se veriﬁc ˘a regula descris ˘a anterior. "factor-diferent ˘a-
rang" este o valoare euristic ˘a pe care o setez 1.55 prin încercare ¸ si eroare
Valoare[1] = 0.02
for( rang = 2..10 )
if( (nr_rosu[rang-1] + nr_rosu[rang] > 0) AND (nr_albastru[rang-1] +
nr_albastru[rang] > 0) )
Valoare[rang] = Valoare[rang-1] *factor_diferenta_rang
else
Valoare[rang] = Valoare[rang-1]
endif
endfor
Valoare[0] = 2
Valoare[1] = Valoare[10] / 2
Valoare[11] = 0.5
Listing 3.1 : Metoda de atribuire a valorilor numerice
Pentru a da valori numerice pieselor cu puteri speciale, se folosesc euristici. Steagul
(rang 0), prime¸ ste o valoare numeric ˘a mare pentru c ˘a este cea mai important ˘a pies ˘a din joc.
Valoarea Spionului este jum ˘atate din valoare Mare¸ salului. Bombele primesc valoarea de 0.5,
adic˘a aproximativ jum ˘atate din valoarea celei mai puternice piese.
16

Stratego: Concepte de baz ˘a Valoarea informa¸ tiei
3.2 Valoarea informa¸ tiei
Deﬁni¸ tia problemei
Atacarea unei piese cu rangul mult mai mare decât cel al propriei piese este o practic ˘a obi¸ s-
nuit˘a în Stratego. Un juc ˘ator bot ar putea crede c ˘a acest lucru este gre¸ sit, pentru c ˘a rezultatul
imediat ar ﬁ pierderea unei piese. Nimic mai gre¸ sit. Sacriﬁcarea unui Cerceta¸ s pentru a aﬂa
loca¸ tia Mare¸ salului inamic, pe care nu o cuno¸ steam înainte, este un câ¸ stig enorm.
A¸ sadar, informa¸ tia are valoare. Ba mai mult, are o valoare ce poate ﬁ comparat ˘a cu
valoarea piesei.
Cu cât este mai mare rang-ul piesei pe care o sacriﬁc ˘am, cu atât mai pu¸ tin ferici¸ ti suntem
cu rezultatul. Bineîn¸ teles c ˘a acest lucru trebuie tradus în numere. Efectul negativ al pierderii
unei piese de rang mai mare este deja implementat prin pierderea acelei piese, mai trebuie,
îns˘a, ad ˘augat ˘a o valoare pozitiv ˘a pentru descoperirea piesei adversarului, care este în strâns ˘a
leg˘atur˘a cu valoarea piesei descoperite.
Ne folosim de valoare, ci nu de rang pentru calcule, deoarece la fel cum valoarea
pieselor difer ˘a in func¸ tie de rang, la fel ¸ si importan¸ ta descoperirii lor este diferit ˘a. A¸ sa
cum am explicat mai sus, este posibil ca 2 piese de acela¸ si rang, una a juc ˘atorului ¸ si una a
inamicului s ˘au, s ˘a aib ˘a valori diferite în fuc¸ tie de starea în care se aﬂ ˘a jocul. Este mult mai
important pentru juc ˘atorul în dezavantaj s ˘a ¸ stie loca¸ tia pieselor puternice ale adversarului
decât viceversa.
Dac˘a pionul cel mai puternic de pe plan¸ s ˘a este descoperit, ¸ stim ¸ si c ˘a celelalte piese nu
pot ﬁ piesa cu cel mai mare rang. A doua pies ˘a ca putere poate ataca lini¸ stit celelalte piese,
pentru c ˘a ¸ stie ca nu are cum sa ﬁe oprit. Asta poate însemna ¸ si c ˘a jum ˘atatea opus ˘a a celei în
care ¸ stim c ˘a se aﬂ ˘a pionul puternic este neprotejat ˘a, inamicul nemaiputând s ˘a se foloseasc ˘a
de piesele slabe pentru ap ˘arare, blufând în încercarea de a-¸ si face oponentul s ˘a cread ˘a c˘a
acolo se aﬂ ˘a o pies ˘a puternic ˘a.
Dac˘a, în schimb, o pies ˘a de rang mediu este descoperit ˘a, nu este limitat ˘a puterea de
ap˘arare deoarece piesele puternice r ˘amân ascunse, îns ˘a, limiteaz ˘a puterea de atac. Piesele
medii sunt totu¸ si importante, ceea ce înseamn ˘a c˘a trebuie ap ˘arate dac ˘a le este cunoscut ˘a
loca¸ tia.
În ﬁnal, dezv ˘aluirea unei piese de rang mic ne afecteaz ˘a cel mai pu¸ tin, dar tot poate avea
un efect negativ. Acestea nu mai pot ﬁ sacriﬁcate pentru a aﬂa loca¸ tia unei piese puternice a
inamicului deoarece acesta, cel mai probabil, o va captura folosind o pies ˘a cu rangul imediat
mai mare. Acest dezavantaj este si mai mic atunci când juc ˘am împotriva unei alte persoane
deoarece, oamenii, nu re¸ tin aceste piese pentru foarte mult timp.
17

Stratego: Concepte de baz ˘a Stadiul jocului
3.2.1 Implementare
Pentru a calcula pedeapsa pentru dezv ˘aluirea informa¸ tiei folosesc o constant ˘a pe care am
setat-o la 25/100. Aceasta este o valoare euristic ˘a ce d ˘a rezultate bune în jocurile lui "Stra-
tegoAI". Formula este valoarea-pies ˘a*pedeaps ˘a-dezv ˘aluire, unde valoare-pies ˘a este valoarea
piese ce î¸ si dezv ˘aluie identitatea.
Formula pe care o folosesc pentru a calcula valoarea sacriﬁc ˘arii unei piese pentru dezv ˘aluirea
unei alte piese este aplicat ˘a doar de piesele mai mici în rang decât C ˘apitanul. Aceasta este
dat˘a de probabilitatea ca piesa atacat ˘a sa ﬁe o pies ˘a de rang cel pu¸ tin cu 2 mai mare decât
piesa ce atac ˘a. Cu cât ¸ sansele sunt mai mari, cu atât proﬁtul atacului este mai mare.
3.3 Stadiul jocului
Un aspect important pentru luarea de decizii este stadiul în care se aﬂ ˘a jocul. În func¸ tie de
pozi¸ tia în care se aﬂ ˘a juc ˘atorul fa¸ t ˘a de oponentul s ˘au deciziile pe care acesta le poate lua
difer ˘a. În cadrul turneelor de Stratego, juc ˘atorii se uit ˘a adesea la piesele eliminate pentru a-¸ si
da seama dac ˘a se aﬂ ˘a într-o pozi¸ tie mai puternic ˘a decât adversarul sau nu.
De exemplu, nu este o idee prea bun ˘a s˘a blufezi atunci când oricum e¸ sti în avantaj ¸ si
jocul poate ﬁ u¸ sor câstigat dac ˘a joci la sigur. În schimb, oponentul nu are nimic de pier-
dut dac ˘a încearc ˘a un bluf din moment ce oricum pierde. În acest caz bluf-ul poate p ˘ac˘ali
adversarul ¸ si poate oferi o ¸ sans ˘a de câ¸ stig.
De asemenea, atacarea unei piese ce nu s-a mutat pe tot parcursul partidei cu o pies ˘a de
rang mare este, din nou, o idee gre¸ sit ˘a. Acea pies ˘a poate ﬁ o Bomb ˘a ce distruge piesa care a
atacat-o, acest lucru reducând semniﬁcativ ¸ sansele la victorie. Dac ˘a e¸ sti în dezavantaj, îns ˘a,
aceast ˘a strategie poate ﬁ singurul lucru care poate întoarce situa¸ tia oferindu-¸ ti un avantaj în
fa¸ ta oponentului.
3.4 Pozi¸ tii strategice
3.4.1 Culoar
Scopul unor strategii nu este numai acela de a captura piesele inamicului. O strategie im-
portant ˘a este ¸ si ocuparea anumitor pozi¸ tii strategice de pe plan¸ s ˘a. Din cauza lacurilor de pe
mijlocul tablei de joc, toate atacurile trebuie s ˘a treac ˘a prin unul dintre cele trei culoare dintre
ele. Acesta este locul în care este cel mai u¸ sor s ˘a î¸ ti aperi piesele deoarece o singur ˘a pies ˘a
poate bloca un culoar. Chiar dac ˘a oponentul are piese mai puternice, e bine s ˘a ocupi aceste
pozi¸ tii deoarece ajut ˘a la oprirea Minerilor, din moment ce este nevoie de 2 piese de rang
mare pentru a trece peste una singur ˘a ce blocheaz ˘a un culoar. În orice alt loc, este foarte u¸ sor
18

Stratego: Concepte de baz ˘a Pozi¸ tii strategice
s˘a treci de o pies ˘a în ap ˘arare cu o pies ˘a de rang mai mare ¸ si un Miner, dar nu ¸ si atunci când
piesa ap ˘ar˘atoare se aﬂ ˘a pe unul din cele 4 careuri ce formeaz ˘a un culoar.
Figura 3.2 : Albastru folose¸ ste culoarele pentru ap ˘arare
În ﬁgura 3.2, este prezentat ˘a o situa¸ tie în care albastru pare a ﬁ în total dezavantaj. Se
aﬂ˘a în inferioritate numeric ˘a ¸ si nici nu de¸ tine cele mai puternice piese. Ar ﬁ fost o victorie
u¸ soar ˘a pentru ro¸ su dac ˘a juc ˘atorul albastru nu ar ﬁ ocupat acele culoare. În aceast ˘a situa¸ tie,
juc˘atorul ro¸ su nu poate trece de piesele ce protejeaz ˘a culoarele ¸ si risc ˘a s˘a î¸ si piard ˘a Minerii
ceea ce poate duce la o înfrângere sau cu pu¸ tin noroc, egalitate.
În situa¸ tii mai pu¸ tin extreme, în care juc ˘atorul albastru ar ﬁ avut cele mai mari piese,
probabilitatea ca ro¸ su s ˘a treac ˘a de culoare ¸ si s ˘a câ¸ stige ar ﬁ fost nul ˘a.
De asemenea, în situa¸ tia în care unul dintre juc ˘atori are 4 cele mai mari piese din joc
dar adversarul de¸ tine avantajul din punct de vedere numeric exist ˘a o posibilitate prin care
juc˘atorul cu piesele puternice poate câstiga. Acesta poate bloca culoarele cu trei din cele
patru piese, iar cu a patra poate bloca piesele inamice ce se apropie prea mult de unul dintre
culoare. În acest mod poate captura piesele inamice f ˘ar˘a ca acestea s ˘a aib ˘a posibilitatea de a
trece de cele trei pasaje.
19

Capitolul 4
Crearea unei formule ini¸ tiale de start
În aceast capitol discut ˘am despre ce sunt, ¸ si care este importa¸ ta formulelor ini¸ tiale de start.
Scopul acestui capitol este eviden¸ tierea tipurilor de probleme ce apar atunci când piesele
sunt aranjate pe tabl ˘a pentru prima dat ˘a. În aplica¸ tia mea, am oferit posibilitatea gener ˘arii
automate a formulei de start pentru joc. De aceea, am studiat implica¸ tiile deﬁnirii formulei
de start ¸ si am elaborat sau adaptat diverse procedee pentru aceasta.
4.1 Importan¸ ta
La începutul ﬁec ˘arui joc de Stratego, juc ˘atorii trebuie s ˘a î¸ si a¸ seze toate piesele pe cele 40
de spa¸ tii care le sunt repartizate. O bun ˘a formul ˘a de start este esen¸ tial ˘a pentru un juc ˘ator
de Stratego de succes, îns ˘a, o formul ˘a imprevizibil ˘a poate ﬁ ¸ si mai important ˘a. Din aceast ˘a
cauz ˘a nu poate exista o formul ˘a optim ˘a.
Dac˘a ar exista o formul ˘a de start perfect ˘a, aceasta ar ﬁ repede înv ˘a¸ tat˘a ¸ si utilizat ˘a de
toat˘a lumea, devenind astfel, o formul ˘a foarte slab ˘a. Este nevoie s ˘a se men¸ tin ˘a echilibrul
între a avea piese pe pozi¸ tii corecte ¸ si a surprinde oponentul.
4.2 Euristic ˘a
Sunt multe euristici pe care un juc ˘ator le ia în calcul atunci când î¸ si creaz ˘a o formul ˘a de
start. Un factor important este strategia pe care dore¸ ste s ˘a o foloseasc ˘a împotriva unui anumit
oponent. Aceea¸ si formul ˘a poate ﬁ ceea ce a dus la victorie împotriva unui adversar, ¸ si motivul
înfrângerii împotriva altuia.
20

Crearea unei formule ini¸ tiale de start Euristic ˘a
4.2.1 Pozi¸ tionarea Steagului
Una din primele întreb ˘ari ce apar atunci când aranj ˘am piesele este ce facem cu Steagul.
Este cea mai important ˘a pies ˘a din joc ¸ si trebuie protejat ˘a. Cel mai sigur loc, unde poate
ﬁ a¸ sezat Steagul este pe ultima linie, înconjurat de 3 Bombe, sau în col¸ t, înconjurat de 2
Bombe. Col¸ tul, îns ˘a, este mult mai diﬁcil de ap ˘arat din moment ce, celelalte piese pot veni
s˘a protejeze Steagul doar dintr-o singur ˘a parte ¸ si pot ﬁ chiar blocate de o singur ˘a pies ˘a de
rang mare a oponentului. În mijloc, pot veni ajutoare din ambele p ˘ar¸ ti în caz c ˘a Steagul este
în pericol, iar dac ˘a se aﬂ ˘a în spatele unui lac, drumul pe care un Miner inamic trebuie s ˘a îl
parcurg ˘a este mai mare. A¸ sadar cea mai bun ˘a pozi¸ tie în care poate ﬁ a¸ sezat Steagul este pe
unul din cele 4 p ˘atrate din spatele lacului, pe ultima linie, înconjurat de 3 bombe. Cunoscând
acest lucru, aceast ˘a pozi¸ tie este una previzibil ˘a. Este o ap ˘arare puternic ˘a dar, practic, îi spui
oponentului unde s ˘a mearg ˘a.
O alternativ ˘a este ca Steagul s ˘a ﬁe pozi¸ tionat într-un loc imprevizibil. Aceasta este o
strategie bun ˘a pentru ﬁnalul jocului, când oponentul, având avantaj, cel mai probabil î¸ si va
sacriﬁca piese pentru a c ˘auta Steagul ¸ si poate ajunge pe o bomb ˘a, acest lucru întorcând jocul
în favoarea ta. Aceast ˘a strategie nu e bine s ˘a ﬁe folosit ˘a, îns ˘a, împotriva unor juc ˘atori slabi
care atac ˘a piese la întâmplare ¸ si pot avea noroc s ˘a nimereasc ˘a Steagul, acesta neﬁind la fel
de bine protejat.
4.2.2 Pozi¸ tionarea Bombelor
În Stratego, Bombele reprezint ˘a cea mai bun ˘a defensiv ˘a. Atât timp cât loca¸ tiile Bombelor
sunt necunoscute, oponentul nu poate risca s ˘a atace piesele nemutate din moment ce oricare
dintre aceasta poate ﬁ o Bomb ˘a.
Deoarece Bombele nu se pot muta, acestea pot reprezenta ¸ si un obstacol uria¸ s pentru cel
ce le de¸ tine, deoarece este obligat s ˘a le ocoleasc ˘a. Amplasate incorect acestea pot chiar bloca
piese ale juc ˘atorului, acesta neputând s ˘a le mute pân ˘a ce Bombele nu au fost dezamorsate.
Acestea sunt motivele pentru care Bombele trebuie a¸ sezate cât mai în spate, pentru a ﬁ
greu pentru adversar s ˘a ajung ˘a la ele dar ¸ si pentru a nu bloca piese importante din a se muta.
Acest lucru îi permite juc ˘atorului s ˘a foloseasc ˘a primele 2 rânduri pentru a manevra piesele
f˘ar˘a ca acestea s ˘a r˘amân ˘a blocate. În al doilea rând, din moment ce Bombele sunt necesare,
în general, la ﬁnalul jocului, atunci când toate piesele mari sunt deja cunoscute, dac ˘a acestea
s-ar aﬂa pe primele rânduri, ar ﬁ evident c ˘a sunt Bombe din moment ce toate celelalte piese
de pe acele rânduri sunt mutate deja în acel stadiu al jocului.
Motivul pentru care nu este bine ca Bombele s ˘a ﬁe a¸ sezate mereu pe ultimele 2 rânduri
este previzibilitatea. Atunci când un juc ˘ator ¸ stie c ˘a oponentul s ˘au î¸ si pozi¸ tioneaz ˘a mereu
bombele în acela¸ si loc, acesta poate lua o pies ˘a de rang mare, ¸ si poate ataca cu ea toate
piesele necunoscute de pe primele 2 rânduri din moment ce ¸ stie ca adversarul s ˘au nu a¸ seaz ˘a
niciodat ˘a bombele acolo.
21

Crearea unei formule ini¸ tiale de start Implementare
4.2.3 Piese de rang mare
Urm ˘atorul lucru la care un juc ˘ator se gânde¸ ste este pozi¸ tionarea pieselor de rang mare. De
obicei, este nevoie de acestea destul de devreme, în cadrul unei partide de Stratego, ceea ce
face ca ele s ˘a ﬁe a¸ sezate pe primele linii, unde se pot muta ¸ si ataca cu u¸ surin¸ t ˘a. În acela¸ si
timp se dore¸ ste ca loca¸ tia lor s ˘a ﬁe secret ˘a cât mai mult timp, de aceea trebuie ferite de
atacurile Cerceta¸ silor.
Mare¸ salul pe liniile din spate este o strategie bun ˘a pentru bluf deoarece oponentul nu se
a¸ steapt ˘a la asa ceva.
4.2.4 Piese de rang mediu ¸ si mic
O bun ˘a formul ˘a de start ia în considerare toate piesele, chiar ¸ si pe cele cu cea mai mic ˘a va-
loare. Cele mai multe jocuri încep cu juc ˘atorii testând puterea adversarului prin sacriﬁcarea
pieselor slabe pentru a aﬂa pozi¸ tia pieselor puternice. Acest lucru este posibil doar dac ˘a
câteva piese de rang mic sunt pozi¸ tionate pe primele linii ¸ si în acest fel pot ﬁ folosite ¸ si ca
scut pentru a proteja piesele puternice din a ﬁ descoperite prea devreme.
Piesele de rang mediu sunt mereu folosite în ordine descresc ˘atoare. Aceste piese sunt
importante ¸ si nu dorim s ˘a ﬁe sacriﬁcate în zadar. Spre exemplu, dac ˘a se aﬂ ˘a pe pozi¸ tii al ˘a-
turate, C ˘apitanul trebuie a¸ sezat mereu în fa¸ ta Locotenentului. Este considerat un dezavantaj
folosirea Locotenentului atunci când este nevoie de un C ˘apitan. Acest lucru duce la pierderea
Locotenentului f ˘ar˘a motiv ¸ si avantajeaz ˘a adversarul.
4.3 Implementare
Am ales ca pentru "StrategoAI" s ˘a optez pentru o formul ˘a de start semi-aleatoare. Aceasta
folose¸ ste euristici pentru plasarea Steagului ¸ si Bombelor iar restul pieselor sunt a¸ sezate
aleator pe pozi¸ tiile r ˘amase libere.
for(piesa = 1..40)
if(piesa = Steag) //rang 0 – Steag, rang 11 – Bomba
AseazaPiesa(piesa,ultimulRandMijloc)
PozitieBomba[1] = PozitieSteag[x+1][y] //dreapta
PozitieBomba[2] = PozitieSteag[x-1][y] //stanga
PozitieBomba[3] = PozitieSteag[x][y+1] //in fata
PozitieBomba[4] = pozitie[aleator]
PozitieBomba[5] = pozitie[aleator]
PozitieBomba[6] = pozitie[aleator]
else if (piesa = Bomba)
AseazaPiesa(piesa,PozitieBomba[bomba_nr])
bomba_nr = bomba_nr + 1;
else
if(pozitie[aleator] nu e ocupata)
22

Crearea unei formule ini¸ tiale de start Implementare
AseazaPiesa(piesa,pozitie[aleator])
endif
endif
endfor
Listing 4.1 : Metoda folosit ˘a pentru generarea formulei de start
Algoritmul selecteaz ˘a piesele, pe rând, prima ﬁind Steagul, pe care îl plaseaz ˘a pe ul-
timul rând, pe o pozi¸ tie aleatoare, mai pu¸ tin cele din col¸ turi. Metoda "rezerv ˘a", apoi, pozi¸ tiile
pe care vor ﬁ a¸ sezate Bombele, primele 3 ﬁind pozi¸ tiile adiacente Steagului, iar urm ˘atoarele
3 alese aleator. Restul pieselor sunt a¸ sezate complet aleator pe pozi¸ tiile ce nu au fost deja
ocupate. În ﬁnal, Bombele sunt a¸ sezate pe pozi¸ tiile ce le sunt destinate.
23

Capitolul 5
Planiﬁcarea mut ˘arilor
5.1 Introducere
În Stratego, planiﬁcarea mut ˘arilor este mult mai diferit ˘a decât la celelalte jocuri. Pentru ¸ Sah,
spre exemplu, toate mut ˘arile sunt în strâns ˘a leg ˘atur˘a una cu cealalt ˘a, ceea ce face ca un om s ˘a
nu poat ˘a planiﬁca foarte mult în viitor. La Stratego, mi¸ sc ˘arile sunt mult mai încete ¸ si plan¸ sa
este mai mare ceea ce face ca o singur ˘a mutare s ˘a nu afecteze prea mult planul.
Planurile sunt strategii folosite pentru îndeplinirea unui anumit obiectiv [14]. Juc ˘atorii
de Stratego gândesc în planuri, nu în mut ˘ari. Acest lucru se datoreaz ˘a atât faptului c ˘a Stratego
este un joc cu un num ˘ar extrem de mare de mut ˘ari cât ¸ si informa¸ tiei incomplete pe care o
pune la dispozi¸ tie juc ˘atorului. Problema nu este g ˘asirea celei mai bune mut ˘ari, ci g ˘asirea
unei mut ˘ari bune. Multe mut ˘ari au efect abia dup ˘a un anumit num ˘ar de ture, care este foarte
greu de atins de c ˘atre orice metod ˘a de c ˘autare. În abordarea mea, o mutare este bun ˘a dac ˘a
contribuie la un plan bun. O alt ˘a mutare poate ﬁ mai bun ˘a dac ˘a contribuie la un plan mai
bun.
"StrategoAI" este compus dintr-o colec¸ tie de planuri care dau valori ﬁec ˘arei mut ˘ari posi-
bile. Mutarea cu cel mai mare scor, dupa ce toate planurile au fost veriﬁcate, este considerat ˘a
cea mai bun ˘a mutare în acel moment. Planurile sunt evaluate în l ˘a¸ time (BFS), de la primul
pân˘a la ultimul, o singur ˘a dat ˘a pe mutare, din moment ce nu se fac c ˘aut˘ari cu o adâncime mai
mare de 1. Deoarece aceast ˘a colec¸ tie nu poate ﬁ niciodat ˘a complet ˘a, nu pot spune c ˘a cel mai
bun plan în toate situa¸ tiile se aﬂa printre ele. Cu cât mai multe planuri bune sunt ad ˘augate cu
atat mut ˘arile pot deveni mai bune în ﬁecare situa¸ tie.
Acest tip de abordare are, de asemenea, avantajele ¸ si dezavantajele sale, pe care urmeaz ˘a
s˘a le prezint.
24

Planiﬁcarea mut ˘arilor Algoritm
5.1.1 Avantaje
Timpul de calcul scurt
Timpul de calcul este aproape instant. Ca s ˘a vad ˘a dac ˘a un Miner poate ajunge la Steag,
trebuie doar s ˘a gaseasc ˘a un drum dintr-un punct în altul pe o plan¸ s ˘a de 10×10 ce poate ﬁ
vazut ˘a ca un graf cu 100 de noduri. Aceasta este o problem ˘a de c ˘autare extrem de mic ˘a ce
poate ﬁ cu u¸ surin¸ t ˘a calculat ˘a de mii de ori f ˘ar˘a ca m ˘acar s ˘a se observe vre-o întârziere pe
calculatoarele moderne. De asemenea, calculul este concentrat pe situa¸ tii interesante ¸ si nu
se calculeaz ˘a toate secven¸ tele de mut ˘ari posibile, de multe dintre care nici nu este nevoie.
Posibilitatea de a blufa
Acest lucru este, în principiu, implementat prin ac¸ tionarea unui plan bun cu o pies ˘a gre¸ sit ˘a.
5.1.2 Dezavantaje
¸ Stie doar ce i se spune
"StrategoAI" alege mut ˘arile doar în func¸ tie de colec¸ tia de planuri ce îi este implementat ˘a.
Dac˘a, spre exemplu, nici un plan nu men¸ tioneaz ˘a c˘a ar trebui s ˘a î¸ si mute Colonelul atunci
când Generalul inamic se apropie pentru a ataca, acesta nu o va face. Acest lucru necesit ˘a ¸ si
cuno¸ stin¸ te foarte multe legate de joc din partea programatorului.
Informa¸ tie calculat ˘a de mai multe ori
Planurile nu î¸ si pot împ ˘ar¸ ti rezultatele calculelor de¸ si multe dintre acestea folosesc aceea¸ si
informa¸ tie.
5.2 Algoritm
În implementarea mea, planurile sunt metode diferite în cadrul unei clase. Fiecare dintre
acestea returneaz ˘a o valoare pentru ﬁecare mutare în func¸ tie de aportul ei la scopul planului
respectiv. Fiecare plan are o importan¸ t ˘a diferit ˘a în func¸ tie de stadiul jocului ceea ce se reﬂect ˘a
în scorurile pe care acestea le returneaz ˘a.
25

Planiﬁcarea mut ˘arilor Algoritm
Figura 5.1 : G˘asirea celei mai bune mut ˘ari
În ﬁgura 4.3 este ilustrat modul în care se alege cea mai bun ˘a mutare din acest moment.
Se aleg, pe rând, mut ˘ari din mul¸ timea tuturor mut ˘arilor posibile. Fiecare mutare trece prin
toate planurile, ﬁecare dintre acestea returnând o valoare. Aceste valori se adun ˘a iar rezul-
tatul ﬁnal este reprezentat de valoarea maxim ˘a pe care o poate avea aceast ˘a mutare. Dup ˘a ce
sunt veriﬁcate toate mut ˘arile, cea cu valoarea cea mai mare este aleas ˘a ca ﬁind mutarea cea
mai bun ˘a de la acel moment.
Nu toate mut ˘arile au leg ˘atur˘a cu toate planurile. Spre exemplu, pentru o mutare ce face
o pies ˘a s˘a înainteze c ˘atre inamic, planul de defensiv ˘a este inactiv ¸ si returneaz ˘a valoarea 0. În
acest caz, mut ˘arile care nu respect ˘a un anumit plan nu sunt afectate cu nimic.
Selec¸ tia celei mai bune mut ˘ari nu ¸ tine cont de planuri, ci de suma tuturor valorilor
returnate de acestea. Dac ˘a o mutare face parte dintr-un plan important, dar o alt ˘a mutare este
o parte din mai multe planuri mai mici, iar aceasta din urm ˘a prime¸ ste ca valoare un num ˘ar
mai mare decât prima, a doua mutare este executat ˘a.
Planurile au acces la toate informa¸ tiile de care au nevoie. În particular, ele pot vedea:
.Întreaga plan¸ s ˘a ¸ si pozi¸ tia tuturor pieselor.
.Cimitirul pieselor.
.Valoarea pieselor de pe tabl ˘a
.Istoric al mut ˘arilor executate anterior
26

Planiﬁcarea mut ˘arilor Planuri folosite
5.3 Planuri folosite
Un num ˘ar potrivit de planuri este necesar pentru buna func¸ tionare a juc ˘atorului inteligent.
Prea pu¸ tine planuri îl face s ˘a nu ﬁe destul de "inteligent", iar un num ˘ar prea mare de planuri
poate rezulta în repetarea unora dintre acestea ceea ce nu este necesar.
Pentru a prevenii apari¸ tia planurilor ce se suprapun, le-am implementat pe 3 categorii.
Planuri tactice, planuri strategice ¸ si planuri generale.
Planurile tactice se ocup ˘a de mut ˘arile ce au un efect imediat. Acest lucru se poate
întâmpla doar dac ˘a piesele sunt deja aproape una de cealalt ˘a. Aceste planuri sunt cele mai
importante ¸ si returneaz ˘a cea mai mare valoare. Acest lucru se datoreaz ˘a faptului c ˘a acestea
duc adesea la capturarea unei piese sau salvarea alteia. Valoarea returnat ˘a este în strâns ˘a
leg˘atur˘a cu valoarea piesei, sau pieselor implicate.
Planurile strategice au ca scop mutarea pieselor pe pozi¸ tiile unde acestea sunt necesare.
Nu ar trebui s ˘a se preocupe cu ce se întâmpl ˘a atunci când piesa ajunge pe acea pozi¸ tie. Este
mult mai greu ca aceste planuri s ˘a returneze o valoare corect ˘a. Pentru c ˘a nu sunt planuri
tactice, acestea nu au un impact mare asupra jocului ¸ si nu pot returna un rezultat speciﬁc.
Misiunea lor este de a crea situa¸ tii de pe urma c ˘arora juc ˘atorul s ˘a proﬁte, acest lucru neputând
ﬁ calculat în vre-un fel. Valorile returnate de aceste planuri trebuie s ˘a ﬁe mult mai mici decât
cele returnate de planurile tactice. Acest lucru asigur ˘a faptul c ˘a atunci când are de ales
intre o mutare ce face parte dintr-un plan tactic, ¸ si una ce face parte dintr-un plan strategic,
"StrategoAI" alege planul tactic.
Planurile generale au o valoare ¸ si mai mic ˘a decât cele strategice. Acestea au ca rol
repartizarea mut ˘arilor atunci când acestea au valori egale.
5.4 Planuri tactice
5.4.1 Planul de capturare imediat ˘a
Acest plan veriﬁc ˘a pozi¸ tia pe care pies ˘a este mutat ˘a dupa executarea mut ˘arii. Dac ˘a pe acea
pozi¸ tie se aﬂ ˘a o pies ˘a a inamicului, planul se activeaz ˘a.
Odat ˘a activat, veriﬁc ˘a dac ˘a piesa inamicului este descoperit ˘a. Dac ˘a rezultatul este poz-
itiv atât timp cât piesa este mai puternic ˘a decât cea a adversarului aceasta atac ˘a. Îns ˘a, dac ˘a
inamicul nu este descoperit, planul calculeaz ˘a probabilitatea ca acea pies ˘a s˘a ﬁe mai mai
puternic ˘a sau mai slab ˘a decât piesa bot-ului.
Acest plan aplic ˘a conceptul de baz ˘a al valorii informa¸ tiei discutat în capitolul 4.1.2
astfel încât exist ˘a posibilitatea ca o pies ˘a slab ˘a s˘a atace o pies ˘a necunoscut ˘a pentru a-i aﬂa
identitatea. În acela¸ si timp "StrategoAI" poate alege s ˘a nu atace o pies ˘a a adversarului chiar
dac˘a aceasta se aﬂ ˘a lâng ˘a el, dac ˘a piesa oponentului este cunoscut ˘a ¸ si are un rang mic iar
27

Planiﬁcarea mut ˘arilor Planuri tactice
singura pies ˘a cu care acesta o poate ataca este o pies ˘a de rang foarte mare. Capturarea unui
Cerceta¸ s nu merit ˘a dezv ˘aluirea loca¸ tiei Mare¸ salului. Ba dimpotriv ˘a, dac ˘a acest lucru s-ar
întâmpla adversarul ar ie¸ si victorios.
Valoarea returnat ˘a de planul de capturare imediat ˘a este cea mai mare deoarece nici un
alt plan nu este mai important decât reducerea num ˘arului de piese al adversarului. În acela¸ si
timp, poate returna ¸ si valori negative dac ˘a atacul nu trebuie sub nici o form ˘a ini¸ tiat de o
anumit ˘a pies ˘a.
5.4.2 Planul de defensiv ˘a tactic ˘a
Un lucru extrem de important într-un joc de Stratego este protejarea, pe cât de mult posibil,
a pieselor în fa¸ ta atacurilor inamice. Acest plan are ca scop protejarea pieselor lui "Strate-
goAI".
În prim ˘a faz ˘a veriﬁc ˘a careurile vecine ale pozi¸ tiei pe care se va aﬂa piesa la ﬁnalul
mut˘arii. Dac ˘a pe unul din aceste p ˘atrate vecine se aﬂ ˘a o pies ˘a inamic ˘a, descoperit ˘a ¸ si cu
rangul mai mare decât piesa mutat ˘a, mutarea prime¸ ste o valoare negativ ˘a. Astfel, juc ˘atorul
se asigur ˘a c˘a nu î¸ si va muta o pies ˘a slab ˘a lâng ˘a o pies ˘a puternic ˘a a oponentului.
Urm ˘atoarea problem ˘a pe care acest plan o rezolv ˘a este salvarea pieselor de inamicii ce
pot reprezenta un pericol dac ˘a se apropie de ele. Pentru a implementa acest lucru, este nevoie
ca bot-ul s ˘a ¸ stie atunci când una din piesele sale se aﬂ ˘a într-o zon ˘a periculoas ˘a. Aceast ˘a
problem ˘a este reprezentat ˘a în ﬁgura 4.4. Juc ˘atorul albastru cunoa¸ ste identitatea Generalului
ro¸ su. În acest caz, Colonelul se aﬂ ˘a într-o zon ˘a periculoas ˘a. Chiar dac ˘a identitatea sa este
necunoscut ˘a adversarului, atât timp cât acesta a fost mutat pe plan¸ s ˘a, este clar pentru oponent
c˘a nu este o Bomb ˘a, iar faptul c ˘a acesta ¸ stie c ˘a Generalul s ˘au este cea mai puternic ˘a pies ˘a în
momentul de fa¸ t ˘a, face ca Colonelul s ˘a ﬁe o ¸ tint ˘a sigur ˘a în urm ˘atoarele 4 mut ˘ari. Pentru a
p˘ar˘asi zona periculoas ˘a, Colonelul trebuie s ˘a se mute în stânga sau în dreapta.
Planul de defensiv ˘a tactic ˘a de¸ tine informa¸ tii legate de toate piesele de pe tabla de joc
¸ si pozi¸ tiile acestora, cât ¸ si despre piesele ce au fost eliminate deja. Pentru a putea salva o
pies˘a dintr-o zon ˘a periculoas ˘a, acesta calculeaz ˘a drumul ¸ si distan¸ ta de la pies ˘a puternic ˘a a
inamicului p ˘an˘a la piesa mai slab ˘a. Pentru a se asigura c ˘a poate salva piesa înainte s ˘a ﬁe
prea târziu, returneaz ˘a valori mut ˘arilor salvatoare in func¸ tie de distan¸ ta dintre piese. Cu cât
distan¸ ta este mai mic ˘a cu atât mutarea prime¸ ste o valoare mai mare. Se poate întâmpla ca,
din cauza regulii de 2 p ˘atrate, explicat ˘a în Anexa 1, s ˘a ﬁe uneori prea târziu pentru ca o pies ˘a
s˘a mai poat ˘a ﬁ salvat ˘a.
Acest plan ia în considerare ¸ si mut ˘arile unor piese ce pot bloca zona periculoas ˘a. În
general, acestea sunt piese mai puternice decât cea care amenin¸ t ˘a, care sunt a¸ sezate pe zona
periculoas ˘a pentru a bloca drumul c ˘atre piesa de rang mai mic. Asta creaz ˘a ¸ si posibilitatea
de cacealma.
28

Planiﬁcarea mut ˘arilor Planuri tactice
Figura 5.2 : Colonelul este în pericol
5.4.3 Planul de atac tactic
Planul de atac tactic este similar cu cel de defensiv ˘a, singura diferen¸ t ˘a ﬁind c ˘a de data aceasta
"StrategoAI" este cel ce trebuie s ˘a se apropie cu piesele sale puternice, de piesele slabe ale
adversarului.
¸ Si acest plan poate duce la Regula celor 2 p ˘atrate, caz în care, piesa ¸ tint ˘a poate ﬁ cap-
turat ˘a sau poate sc ˘apa, în func¸ tie de cel ce a început primul aceast ˘a repeti¸ tie. Din p ˘acate,
lipsa implement ˘arii regulii de mai multe p ˘atrate, pentru "StrategoAI", acest plan poate duce
la o urm ˘arire la nesfâr¸ sit, sau, în cazul în care adversarul are o pies ˘a mai puternic ˘a decât cea
care a început urm ˘arirea, aceasta din urm ˘a poate ﬁ atras ˘a într-o capcan ˘a ¸ si capturat ˘a.
5.4.4 Planul de dezamorsare a Bombelor
Planul de dezamorsare a Bombelor este un plan tactic ce are ca obiectiv utilizarea Minerilor
pentru a elimina Bombele adversarului.
Acest plan intr ˘a în aplicare doar dac ˘a este cunoscut ˘a, cel pu¸ tin, loca¸ tia unei Bombe a
adversarului. "StrategoAI" ia în considerare mutarea unui Miner c ˘atre acea Bomb ˘a doar dac ˘a
¸ stie c ˘a de¸ tine deja un avantaj în fa¸ ta oponentului.
29

Planiﬁcarea mut ˘arilor Planuri strategice
Rezultatul returnat se aﬂ ˘a în strâns ˘a leg ˘atur˘a cu valoarea numeric ˘a a Bombei ¸ si distan¸ ta
de la Miner la aceasta. Pentru orice alt ˘a mutare ce nu are ca pies ˘a ce trebuie mutat ˘a un Miner,
acest plan returneaz ˘a valoarea 0.
5.4.5 Ap ˘ararea Mare¸ salului
Acest plan const ˘a în moduri de a feri Mare¸ salul de Spionul inamic. Cu cât mai mult se
reu¸ seste men¸ tinerea Mare¸ salului în via¸ t ˘a, cu atât ¸ sansele de câ¸ stig sunt mai mari.
Implementarea acestui plan este extrem de simpl ˘a ¸ si se aplic ˘a doar mut ˘arilor ce au ca
pies˘a de mutat Mare¸ salul. Pentru restul mut ˘arilor acest plan returneaz ˘a valoarea 0.
La ﬁecare mutare, acesta veriﬁc ˘a dac ˘a Spionul inamic este înc ˘a în via¸ t ˘a. Dac ˘a r˘aspunsul
este da, atunci calculeaz ˘a probabilitatea ca pe pozi¸ tiile vecine ale careului pe care se va aﬂa
Mare¸ salul dup ˘a executarea mut ˘arii s ˘a se aﬂe spionul. Dac ˘a aceast ˘a probabilitate este mai
mare de 30/100, procent implementat pentru o siguran¸ t ˘a cât mai mare, mutarea respectiv ˘a
prime¸ ste un scor negativ. Pentru rezultate cât mai corecte, acest plan se folose¸ ste de infor-
ma¸ tiile acumulate din mut ˘arile precedente. Spre exemplu, dac ˘a Mare¸ salul a fost deja mutat
lâng˘a o pies ˘a advers ˘a necunoscut ˘a iar acesta nu a fost atacat, urm ˘atoarea mutare va avea o
probabilitate mult mai mare ca una din piesele vecine s ˘a ﬁe Spion.
5.5 Planuri strategice
Planurile strategice reprezint ˘a strategii pe termen lung. De obicei nu au un efect imediat, ci
se ocup ˘a de pozi¸ tionarea strategic ˘a a pieselor.
5.5.1 Planul de atac strategic
Acest plan se ocup ˘a de aducerea pieselor pe pozi¸ tii strategice de atac. Am considerat ca
acest plan sa returneze o valoare mic ˘a, pozitiv ˘a pentru mut ˘arile ce aduc piesele pe pozi¸ tiile
din culoare, ¸ si apoi o valoare ¸ si mai mic ˘a pentru mut ˘arile ce fac piesele s ˘a intre în jum ˘atatea
de plan¸ s ˘a a
adversarului.
5.5.2 Planul de defensiv ˘a strategic ˘a
Planul de defensiv ˘a strategic ˘a, veriﬁc ˘a dac ˘a piesele slabe sau cele de rang mediu sunt de-
scoperite de adversar. Dac ˘a da, acesta returneaz ˘a o valoare mic ˘a mut ˘arilor ce aduc piese de
rang mai mare în vecin ˘atatea piesei descoperite. Acest lucru permite ap ˘ararea acelei piese,
30

Planiﬁcarea mut ˘arilor Planuri generale
sau folosirea ei ca momeal ˘a pentru a captura apoi piesa care a eliminat-o. Valoarea este cu
atât mai mic ˘a cu cât distan¸ ta dintre piesa descoperit ˘a de rang mic ¸ si piesa ce trebuie s ˘a o
apere este mai mare.
5.6 Planuri generale
Aceste planuri nu depind de o situa¸ tie speciﬁc ˘a, astfel nu pot ﬁ trecute în categoriile de
planuri tactice sau strategice.
5.6.1 Plan aleator
La începutul jocului toate mut ˘arile au valori egale deoarece, la acel moment nu exist ˘a situa¸ tii
ce ar putea activa planurile tactice pentru a se putea face o delimitare printre mut ˘ari, iar
planurile strategice dau valori foarte mici ¸ si uneori egale pentru mai multe mut ˘ari. Pentru a
putea executa totu¸ si o mutare, "StrategoAI" va alege una la întamplare. Acest plan returneaz ˘a
o valoare aleatoare între 0 ¸ si 1 ﬁec ˘arei mut ˘ari pentru a exista o diferen¸ t ˘a de valoare între ele.
5.6.2 Planul de pedeaps ˘a pentru mutare
În acest joc, doar mutând o pies ˘a îi oferi adversarului informa¸ tii. Practic îi spui c ˘a acea pies ˘a
nu este nici o Bomb ˘a ¸ si nici Steagul. Dac ˘a o pies ˘a este mutat ˘a mai mult de un p ˘atrat este clar
c˘a acea pies ˘a este un Cerceta¸ s.
Acest tip de oferire de informa¸ tie trebuie penalizat. F ˘ar˘a o astfel de penalizare, "Stra-
tegoAI" ar putea crede ca nu este nici o problem ˘a în a-¸ si muta toate piesele cât mai repede
posibil, ne¸ stiind c ˘a acest lucru informeaz ˘a adversarul despre loca¸ tia Bombelor ¸ si a Steagului.
Planul aﬂ ˘a num ˘arul de piese de pe plan¸ s ˘a ce au fost mutate pân ˘a la momentul apel ˘arii
sale. Returneaz ˘a ca valoare negativ ˘a, pentru mut ˘arile a c ˘aror piese nu au fost mutate, num ˘arul
total de piese mutate calculat anterior.
31

Capitolul 6
Concluzie
Cu acest program am propus o solu¸ tie pentru implementarea unui bot capabil s ˘a joace
Stratego la un nivel intermediar, acesta putând s ˘a ia decizii potrivite pentru toate situa¸ tiile în
care este pus.
"StrategoAI" este un juc ˘ator inteligent ce are o în¸ telegere a jocului la nivelul unui juc ˘ator
de Stratego încep ˘ator. Algoritmii ¸ si euristicile folosite reprezint ˘a motivul pentru care se
întâmpl ˘a acest lucru.
Bot-ul meu, î¸ si creaz ˘a propriile formule de start semi-aleator, acesta ¸ tinând cont de
câteva reguli. Acest lucru îl face imprevizibil pentru oponent, datorit ˘a faptului c ˘a nu este
niciodat ˘a repetat un anumit aranjament al pieselor.
În¸ telegerea jocului ¸ si modul prin care sunt luate decizii legate de modul de a alege cea
mai bun ˘a mutare la un moment dat sunt implementate pe baz ˘a de planuri. Strategiile cu efect
imediat dar ¸ si cele cu efect pe termen lung, ce sunt extrem de greu de implementat printr-un
algoritm de c ˘autare complet ˘a, sunt foarte u¸ sor formulate cu ajutorul planurilor. În prezent
sunt folosite 9 planuri, incluzând Regula de 2 p ˘atrate, care sunt mult mai u¸ sor de implementat
decât un sistem întreg bazat doar pe reguli [15].
6.1 Lucru pe viitor
Implementarea unui sistem mai complex pentru crearea formulelor de start este necesar ˘a
pentru ca puterea ini¸ tial ˘a juc ˘atorului inteligent s ˘a creasc ˘a. O baz ˘a de date cu formule folosite
de juc ˘atorii profesioni¸ sti din care acesta s ˘a inve¸ te pentru ca apoi s ˘a î¸ si poat ˘a aranja singur
piesele este o metod ˘a bun ˘a prin care acest lucru poate ﬁ implementat.
De asemenea, îmi doresc s ˘a adaug mai multe planuri, ¸ si sa abordez strategii mai avansate
ale jocului. Pentru moment, pot ap ˘area multe situa¸ tii în care juc ˘atorul meu nu ar putea lua
cea mai bun ˘a decizie.
32

Referin¸ te bibliograﬁce
[1] Royal Jumbo. About Stratego. http://www.stratego.com/en/
about-stratego/ . [Online; accessed 15-Iunie-2018].
[2] Jim X Chen. The evolution of computing: Alphago. Computing in Science & Engi-
neering , 18(4):4–7, 2016.
[3] Stuart J Russell and Peter Norvig. Artiﬁcial intelligence: a modern approach .
Malaysia; Pearson Education Limited„ 2016.
[4] Ding-Zhu Du and Panos M Pardalos. Minimax and applications , volume 4. Springer
Science & Business Media, 2013.
[5] Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep blue. Artiﬁcial
intelligence , 134(1-2):57–83, 2002.
[6] Oliver Kramer. Genetic algorithm essentials , volume 679. Springer, 2017.
[7] Ryan Albarelli. Optimizing stratego heuristics with genetic algorithms. Technical
report, Technical report, Missouri University of Science and Technology, 2003.
[8] RM de Boer. Reachable level of stratego using genetic algorithms. B.S. thesis, 2012.
[9] Imer Satz. Probe. http://www.probe.imersatz.com/ , 2008. [Online; ac-
cessed 15-Iunie-2018].
[10] AFC Arts. Competitive play in stratego . PhD thesis, Master’s thesis, Department of
Knowledge Engineering, Maastricht University, 2010.
[11] Vincent de Boer, Léon JM Rothkrantz, and Pascal Wiggers. Invincible-a stratego bot.
International Journal of Intelligent Games & Simulation , 5(1), 2008.
[12] John F Hughes, Andries Van Dam, James D Foley, Morgan McGuire, Steven K Feiner,
David F Sklar, and Kurt Akeley. Computer graphics: principles and practice . Pearson
Education, 2014.
33

Referin¸ te bibliograﬁce Referin¸ te bibliograﬁce
[13] Casey Reas and Ben Fry. Getting Started with Processing: A Hands-On Introduction
to Making Interactive Graphics . Maker Media, Inc., 2015.
[14] John Baaki and James L Moseley. Strategic planning and strategic thinking clothed in
stratego. Performance Improvement , 50(7):17–24, 2011.
[15] Mohannad Ismail. Multi-agent stratego . PhD thesis, B. Sc thesis, Rotterdam University,
The Netherlands.[2], 2004.
[16] Hasbro. Stratego Original rules. https://www.hasbro.com/common/
instruct/Stratego.pdf . [Online; accessed 15-Iunie-2018].
34

Anexa 1: Stratego
1.1 Jocul
Regulile oﬁciale Stratego [16]
Obiectivul jocului const ˘a în capturarea steagului inamic.
Fiecare armat ˘a este format ˘a din:
– 33 piese mobile:
10 – Mare¸ sal – 1 buc.
9 – General – 1 buc.
8 – Colonel – 2 buc.
7 – Maior – 3 buc.
6 – C ˘apitan – 4 buc.
5 – Locotenent – 4 buc.
4 – Sergent – 4 buc.
3 – Miner – 5 buc.
2 – Cerceta¸ s – 8 buc.
1 – Spion – 1 buc.
– 7 piese imobile:
Bomb ˘a – 6 buc.
Steag – 1 buc.
Cum sa preg ˘ate¸ sti jocul?
1. A¸ seaz ˘a tabla de joc între tine ¸ si adversar cu numele Stratego îndreptat c ˘atre oricare dintre
voi.
2. Ascunde o pies ˘a ro¸ sie într-o mân ˘a ¸ si o pies ˘a albastr ˘a în cealalt ˘a mân ˘a. Oponentul alege o
mân˘a ¸ si joac ˘a cu piesele de culoarea celei pe care a ales-o. Armata de cealalt ˘a culoare este a
ta.
3. Aranja¸ ti-v ˘a armatele folosind sugestiile de strategii ¸ si regulile de mutare ¸ si atac ce sunt
35

Anexa 1: Stratego Anexa 1: Stratego
prezentate mai jos.
4. A¸ seaz ˘a piesele cu partea printat ˘a indreptat ˘a c˘atre tine astfel încât oponentul s ˘a nu le poat ˘a
vedea.
5. Un careu poate ﬁ ocupat doar de o singur ˘a pies ˘a. A¸ seaz ˘a-le oriunde pe ultimele 4 rânduri
din jum ˘atatea ta de plan¸ s ˘a. Cele 2 rânduri din mijloc sunt l ˘asate neocupate la începutul par-
tidei.
Mod de joc
Fiecare juc ˘ator poate face doar o mutare pe tur ˘a.
La ﬁecare tur ˘a po¸ ti face unul din urm ˘atoarele lucruri:
Mut˘a – una din piesele tale pe un spa¸ tiu al ˘aturat, liber.
Atac ˘a – una din piesele adversarului.
Reguli de mutare
1. Piesele se mut ˘a un singur careu pe tur ˘a, înainte, înapoi sau în lateral. (Exceptie: Vezi
Privilegii Speciale ale Cerceta¸ sului, Regula 6).
2. Piesele nu se pot muta pe diagonal ˘a. Nu pot s ˘ari peste alte piese. Nu se pot muta pe o
pozi¸ tie deja ocupat ˘a de alt ˘a pies ˘a ( doar dac ˘a nu este cazul unui atac).
3. Piesele nu se pot muta sau s ˘ari peste cele dou ˘a zone din centrul tablei de joc, ce sunt
indicate prin linii punctate.
4. O pies ˘a nu se poate muta înainte ¸ si înapoi pe dou ˘a p˘atrate mai mult de 3 ture consecutive.
5. Doar o singur ˘a pies ˘a poate ﬁ mutat ˘a pe tur ˘a.
6. Privilegii Speciale ale Cerceta¸ sului: Un cerceta¸ s se poate muta orice num ˘ar de pozi¸ tii
libere înainte, înapoi sau în lateral. De re¸ tinut c ˘a acest tip de mutare îi va dezv ˘alui oponen-
tului faptul c ˘a acea pies ˘a este un cerceta¸ s. Pute¸ ti muta cerceta¸ sul o singur ˘a pozi¸ tie pe tur ˘a
pentru ai p ˘astra ascuns ˘a identitatea. Este singura pies ˘a c˘areia îi este permis s ˘a se mute ¸ si s ˘a
atace în acela¸ si timp.
De re¸ tinut c ˘a Bomba ¸ si Steagul sunt piese ce nu se pot muta ¸ si trebuie s ˘a r˘amân ˘a pe pozi¸ tia
lor original ˘a pe tot parcursul jocului.
Reguli de atac
1. Pozi¸ tia de atac: Atunci când o pies ˘a albastr ˘a ¸ si una ro¸ sie ocup ˘a pozi¸ tii adiacente, spate în
spate, în lateral sau fa¸ t ˘a în fa¸ t ˘a, acestea se aﬂ ˘a în pozi¸ tie de atac.
2. Cum s ˘a ataci: Pentru a ataca în timpul turei tale, ridic ˘a piesa cu care dore¸ sti s ˘a ataci ¸ si
atinge u¸ sor pionul oponentului. Apoi, arat ˘a rangul piesei tale. Oponentul, trebuie la rândul
lui s˘a declare rangul pionului s ˘au.
3. Piesa cu rangul mai mic este capturat ˘a ¸ si eliminat ˘a de pe plan¸ s ˘a. Dac ˘a pionul t ˘au (cel
care ataca) este cel care a câ¸ stigat b ˘at˘alia, se mut ˘a pe pozi¸ tia ocupat ˘a de piesa care se ap ˘ara.
Dac˘a piesa care supravie¸ tuie¸ ste b ˘at˘aliei este piesa care se ap ˘ara, aceasta î¸ si p ˘astreaz ˘a pozi¸ tia
pe care se aﬂa înainte s ˘a ﬁe atacat ˘a.
36

Anexa 1: Stratego Anexa 1: Stratego
4. Când piese de acela¸ si rang se lupt ˘a, ambele sunt eliminate din joc.
5. Atacul este întotdeauna op¸ tional.
Reguli de rang
1. Un Mare¸ sal (Num ˘arul 10) întrece în rang un General (Num ˘arul 9) ¸ si orice alt ˘a piesa de
rang mai mic. Un General (Num ˘arul 9) dep ˘a¸ se¸ ste în rang un Colonel (Num ˘arul 8) ¸ si orice
alt˘a pies ˘a cu rang mai mic. Un Colonel (Num ˘arul 8) întrece în rang un Maior (Num ˘arul 7)
¸ si tot a¸ sa pân ˘a la Spion, care este pisa cu cel mai mic rang.
2. Privilegii Speciale ale Minerului: Atunci când orice pies ˘a (Exceptând Minerul – rang 3)
atac˘a o Bomb ˘a, acea pies ˘a este distrus ˘a ¸ si eliminat ˘a din joc. Dac ˘a un Miner atac ˘a o Bomb ˘a,
Bomba este dezamorsat ˘a ¸ si înl ˘aturat ˘a de pe tabla de joc. Apoi, Minerul se mut ˘a pe spa¸ tiul
ocupat anterior de Bomb ˘a. Bombele nu se pot muta sau ataca.
3. Privilegii Speciale ale Spionului: Dac ˘a orice pies ˘a atac ˘a un Spion (Rang 1), acesta este
eliminat ¸ si înl ˘aturat de pe plan¸ s ˘a. Îns ˘a Spionul are o putere unic ˘a de atac. Este singura
pies˘a care dep ˘a¸ se¸ ste in rang un Mare¸ sal, ¸ tinând cont de faptul c ˘a Spionul atac ˘a primul. Dac ˘a
Mare¸ salul atac ˘a primul, atunci Spionul este eliminat.
Sugestii de strategii
1. A¸ seaz ˘a Bombe în jurul Steagului pentru a-l proteja. Plaseaz ˘a una sau dou ˘a Bombe în alt ˘a
parte pentru a deruta adversarul.
2. A¸ seaz ˘a câteva piese de rang mare pe prima linie, dar ai grij ˘a! Dac ˘a le pierzi într-o faz ˘a de
început a partidei vei ﬁ pus într-o situa¸ tie diﬁcil ˘a.
3. Cerceta¸ sii ar trebui sa ﬁe pe liniile frunta¸ se pentru a ajuta la descoperirea puterii pieselor
inamice.
4. Plaseaz ˘a câ¸ tiva Mineri pe margine pentru ﬁnalul partidei, când te vor ajuta s ˘a dezamorsezi
Bombele.
Victoria
Primul juc ˘ator care atac ˘a Steagul oponentului este declarat câ¸ stig ˘atorul partidei.
Dac˘a toate piesele tale mobile au fost eliminate ¸ si nu mai po¸ ti muta sau ataca, trebuie s ˘a te
dai b ˘atut ¸ si s ˘a î¸ ti declari oponentul înving ˘ator.
1.2 Reguli de repeti¸ tie
În Stratego, exist ˘a 2 reguli pentru a preveni repetarea mut ˘arilor la inﬁnit. Textul lor original
este destul de complex ¸ si greu de în¸ teles, acesta ﬁind probabil motivul pentru care multe din
programele existente nu le cunosc, nu le-au implementat complet sau dac ˘a au încercat s ˘a
o fac ˘a au f ˘acut-o incorect. Trebuie men¸ tioat faptul c ˘a, în cazul jocurilor de relaxare aceste
reguli nu au nici o semniﬁca¸ tie din moment ce, de obicei, nu vrei s ˘a intri într-o bucl ˘a inﬁnit ˘a
37

Anexa 1: Stratego Anexa 1: Stratego
de mut ˘ari atunci când joci de distrac¸ tie. Chiar ¸ si în cadrul meciurilor oﬁciale, sunt doar in-
struc¸ tiuni pentru a ¸ stii când trebuie sa închei urm ˘arirea.
Sunt câteva motive pentru care cred c ˘a este necesar ca "StrategoAI" s ˘a aib ˘a implemen-
tate aceste reguli. În primul rând, orice joc serios de Stratego trebuie s ˘a ¸ tin˘a cont de aceste
reguli. Atât timp cât ambii juc ˘atori î¸ si doresc s ˘a câ¸ stige, se poate ajunge foarte u¸ sor la o
remiz ˘a dac ˘a aceste reguli nu ar preveni asta. Dac ˘a un juc ˘ator ar putea s ˘a aleag ˘a s˘a fac ˘a o alt ˘a
mutare pentru a evita bucla nesfâr¸ sit ˘a, un calculator nu ar face asta niciodat ˘a dac ˘a nu ar ﬁ
obligat.
Regula celor 2 p ˘atrate
Prima dintre aceste reguli este Regula celor 2 p ˘atrate sau Regula de 3 mut ˘ari. Se nume¸ ste asa
deoarece esen¸ ta acestei reguli este faptul c ˘a repeti¸ tia are loc pe 2 p ˘atrate iar num ˘arul maxim
de repet ˘ari posibile este 3.
Textul oﬁcial al acestei reguli este urm ˘atorul:
10. Trei mut˘ ari pe dou˘ a p˘ atrate: Regula celor dou˘ a p˘ atrate
10.1 Nu este permis˘ a mutarea unei piese de mai mult de 3 ori non-stop între acelea¸ si 2
p˘ atrate, indiferent de ce face oponentul. Nu conteaz˘ a dac˘ a o pies˘ a se mut˘ a pentru a ataca o
pies˘ a a oponentului, sau doar se muta pe un spatiu liber.
10.2 Atunci când un Cerceta¸ s este implicat în Regula celor 2 p˘ atrate, se consider˘ a c˘ a
Cerceta¸ sul porne¸ ste de la pozi¸ tia de start a mut˘ arii plus toate p˘ atratele peste care trece, ¸ si
se termin˘ a pe pozi¸ tia ﬁnal˘ a a mut˘ arii sale plus toate p˘ atratele peste care trece.
10.1 este destul de simplu, de¸ si, dintre toate regulile de repeti¸ tie, aceasta are cel mai
mare impact asupra jocului.
10.2 complic ˘a pu¸ tin aceasta regula, mai ales din punct de vedere al implement ˘arii, dar
este foarte important ˘a atunci când vrei s ˘a capturezi un Cerceta¸ s sau s ˘a i¸ ti aprei Steagul de
unul. F ˘ar˘a aceast ˘a parte a regulii (respectând doar 10.1) ai nevoie de 6 piese pentru a captura
un Cerceta¸ s. Cu aceast ˘a regul ˘a sunt necesare doar 4.
Implementare
Din cauza propozi¸ tiei 10.2, implementarea nu const ˘a doar dintr-o veriﬁcare a ultimelor 3
mut˘ari pentru a veriﬁca dac ˘a au avut loc intre acelea¸ si dou ˘a p˘atrate. Problema poate ﬁ redus ˘a
la g˘asirea p ˘atratelor ce se suprapun în ultimele 3 mut ˘ari. Dac ˘a toate cele 3 mut ˘ari au în-
ceput, au trecut prin, sau s-au încheiat pe cel pu¸ tin 2 p ˘atrate identice, atunci, mut ˘arii curente
nu îi este permis s ˘a treac ˘a prin acele locuri. Acest lucru poate ﬁ implementat calculând
maximul dintre cea mai mic ˘a coordonat ˘a y dintre ultimele 3 mut ˘ari ¸ si mutarea curent ˘a, ¸ si
minimul dintre cea mai mare coordonata y din ultimele 3 mut ˘ari dac ˘a toate au început ¸ si s-au
terminat pe acela¸ si rând. Dac ˘a minimul dintre cele mai mari coordonate y este mai mare
38

Anexa 1: Stratego Anexa 1: Stratego
decât maximul dintre cele mai mici coordonate y sunt cel pu¸ tin 2 p ˘atrate care se suprapun
în aceste mut ˘ari, deci mutarea curent ˘a nu este permis ˘a.Dac ˘a toate au început ¸ si s-au terminat
pe aceea¸ si coloan ˘a, se aplic ˘a acelea¸ si reguli pentru coordonata x. Dac ˘a mut ˘arile nu au loc
pe aceea¸ si coloan ˘a sau pe acela¸ si rând, atunci regula nu are cum s ˘a ﬁe înc ˘alcat ˘a de mutarea
curent ˘a.
Dac˘a ultimele 3 mut ˘ari nu au fost efectuate de aceea¸ si pies ˘a, regula nu poate ﬁ înc ˘alcat ˘a.
Este foarte important s ˘a veriﬁcam acest lucru deoarece este posibil s ˘a trecem prin acelea¸ si
2 p˘atrate cu 2 Cerceta¸ si diferi¸ ti ¸ si apoi s ˘a ne întoarcem înapoi cu ultimul. Acest lucru face
posibil ˘a trecerea prin acelea¸ si 2 p ˘atrate de 4 ori f ˘ar˘a ca regula s ˘a ﬁe înc ˘alcat ˘a.
Exempliﬁcare
În ﬁgura al ˘aturat ˘a voi demonstra importan¸ ta
regulii celor 3 mut ˘ari. Dac ˘a Colonelul albas-
tru se mut ˘a în dreapta, se va ajunge inevitabil
la o repeti¸ tie de mut ˘ari. C ˘apitanul ro¸ su se va
muta în dreapta în încercarea de a sc ˘apa ¸ si face
prima mutare din seria celor 3. Colonelul îl
urmeaz ˘a pe ultima coloan ˘a. Din moment ce
C˘apitanul a fost primul care a început aceasta
serie, tot el trebuie s ˘a o încheie ¸ si s ˘a se sacri-
ﬁce.
Figura 6.1 : Regula celor 2 p ˘atrate
Dac˘a, îns ˘a, Colonelul albastru s-ar ﬁ aﬂat pe pozi¸ tia marcat ˘a cu triunghi ¸ si s-ar ﬁ mutat
în stânga, el ar ﬁ primul care începe seria de repeti¸ tii ¸ si de asemenea tot el ar ﬁ obligat s ˘a o
încheie. C ˘apitanul are o ¸ sans ˘a de sc ˘apare. Acestea sunt dou ˘a situa¸ tii aparent asem ˘an˘atoare,
dar cu un rezultat foarte diferit. Chiar dac ˘a, în prima situa¸ tie, Colonelul albastru ini¸ tiaz ˘a
secven¸ ta, nu el este cel care începe repeti¸ tia, din moment ce porne¸ ste de pe o pozi¸ tie care nu
face parte din cele 2 care se repet ˘a.
Regula de mai multe p ˘atrate
A doua regul ˘a de repeti¸ tie despre care vom discuta este Regula de mai multe p ˘atrate. Aceasta
este ¸ si mai vag ˘a ¸ si extrem de greu de aplicat într-un joc real. Este cunoscut ˘a ca ¸ si regula ce nu
î¸ ti permite s ˘a urm ˘are¸ sti la nesfâr¸ sit o pies ˘a inamic ˘a f˘ar˘a s˘a îi oferi o mutare "gratuit ˘a" în care
nu trebuie s ˘a fug ˘a de tine. O regul ˘a care, practic, îl oblig ˘a pe atacator s ˘a opreasc ˘a urmarirea
dac˘a aceasta nu duce la capturarea piesei. Nu poate obliga un juc ˘ator s ˘a î¸ si sacriﬁce o pies ˘a,
la fel ca Regula celor 2 p ˘atrate, deoarece cel care este obligat s ˘a se opreasc ˘a din mut ˘arile
repetitive este juc ˘atorul care atac ˘a. La fel ca ¸ si regula precedent ˘a, îns ˘a, consecin¸ tele aplic ˘arii
sale pot avea un impact decisiv asupra partidei.
39

Anexa 1: Stratego Anexa 1: Stratego
Faptul c ˘a aceast ˘a regul ˘a este întâlnit ˘a extrem de rar, iar textul ei este foarte vag, o face
cea mai pu¸ tin ¸ stiut ˘a regula din joc. Nici chiar mul¸ ti dintre juc ˘atorii profesioni¸ sti de Strat-
ego nu îi cunosc cu adev ˘arat efectele la ﬁnalul partidei. "Invincible" este singurul juc ˘ator
inteligent care implementeaz ˘a aceast ˘a regul ˘a. Motivul pentru care nu este implementat ˘a este
probabil textul vag ¸ si non-descriptiv ce o face aproape imposibil de implementat. Este foarte
greu pentru o persoan ˘a s˘a î¸ si dea seama care mutare este ilegal ˘a în timpul unei partide de
Stratego, de aceea, acest lucru nu se a¸ steapt ˘a de la juc ˘atori, doar c ˘a, "la un moment dat",
atacatorul opre¸ ste urm ˘arirea.
Textul regulii din ISF (Federa¸ tia Interna¸ tional ˘a de Stratego):
11 Repeti¸ tia de mi¸ sc˘ ari amenin¸ t˘ atoare: Regula de mai multe p˘ atrate
11.1 Nu este permis˘ a urm˘ arirea uneia sau mai multor piese la nesfâr¸ sit. Urm˘ aritorul
nu poate face o mutare amenin¸ t˘ atoare din nou dac˘ a acesta ar ajunge într-o pozi¸ tie în care a
mai fost.
11.2 Excep¸ tie: Mut˘ arile ce urm˘ aresc o pies˘ a înapoi în locul de unde a venit la mu-
tarea precedent˘ a sunt mereu permise atât timp cât nu este înc˘ alcat˘ a regula celor 2 p˘ atrate.
Pe scurt, înseamn ˘a c˘a nu ai voie s ˘a faci o mutare care ar putea duce la o situa¸ tie, pe
tabla de joc, care a avut deja loc în timpul unei secven¸ te neîntrerupte de mut ˘ari amenin¸ t ˘a-
toare. Dup ˘a o singur ˘a mutare inofensiv ˘a, toat ˘a istoria legat ˘a de secven¸ t ˘a este ¸ stears ˘a ¸ si toate
mut˘arile sunt din nou permise.
1.3 Reguli Adi¸ tionale
Exist ˘a trei alte reguli adi¸ tionale ce pot ﬁ utilizate de juc ˘atori dac ˘a vor s ˘a aib ˘a parte de o
provocare mai mare.
Avantajul Agresorului
Când dou ˘a piese cu acela¸ si rang se lupt ˘a, câstig ˘a piesa care a ini¸ tiat atacul.
Defensiv ˘a Silen¸ tioas ˘a
Atunci când un atac are loc, atacatorul este singurul juc ˘ator care trebuie s ˘a declare rangul
piesei sale. Ap ˘ar˘atorul nu î¸ si dezv ˘aluie piesa, dar rezolv ˘a atacul prin eliminarea piesei cu
num˘arul mai mic de pe tabl ˘a. Juc ˘atorii î¸ si p ˘astreaz ˘a propriile piese capturate. Excep¸ tie:
Când un Cerceta¸ s atac ˘a, ap ˘ar˘atorul trebuie s ˘a dezv ˘aluie num ˘arul piesei atacate.
40

Anexa 1: Stratego Anexa 1: Stratego
Salvare
Când un juc ˘ator mut ˘a o pies ˘a pe un p ˘atrat de pe ultima linie din jum ˘atatea adversarului,
prime¸ ste op¸ tiunea de a recupera una din piesele capturate. Acesta poate lua orice pies ˘a
capturat ˘a de oponent ¸ si o poate rea¸ seza pe tabla de joc. Plaseaz ˘a piesa recuperat ˘a pe orice
spa¸ tiu neocupat de pe jum ˘atatea proprie de plan¸ s ˘a. Aceast ˘a ac¸ tiune încheie runda.
Restric¸ tii
.Cerceta¸ sul nu poate salva piese.
.Bomba nu poate ﬁ recuperat ˘a
.Doar dou ˘a salv ˘ari pot ﬁ efectuate de c ˘atre ﬁecare juc ˘ator.
.Ambele recuper ˘ari nu pot ﬁ f ˘acute de aceea¸ si pies ˘a.
41

Copyright Notice

© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.

Acest articol: Specializarea Informatic a [608827] (ID: 608827)

Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.

Specializarea Informatic a [608827]

Copyright Notice

Tartalomjegyzék [305632]

Aspecte criminalistice în cercetar ea [630707]

F A C U L T A T E A D E G E O G R A F I E [625856]

Journal for the Study of Religions an d Ideologies, 7, 21 (Winter 2008): 188-192 CARMEN SANDU [616293]

Cu titlu de manuscris [604093]

1. Brief history & 2. The field of activity The first McDonald ’s restaurant was established by two brothers: Dick and McDonald in California on… [602873]

Copyright Notice

Similar Posts