Un ghid pas cu pas pentru construirea unui șah simplu AI

de Lauri Hartikka

să explorăm câteva concepte de bază care ne vor ajuta să creăm un șah simplu AI:

mutare generație
evaluare bord
Minimax
și tăiere alfa beta.

la fiecare pas, ne vom îmbunătăți algoritmul cu una dintre aceste tehnici de programare a șahului testate în timp. Voi demonstra modul în care fiecare afectează stilul de joc al algoritmului.

puteți vizualiza algoritmul AI final aici pe GitHub.

Pasul 1: Mutați generarea și vizualizarea bordului

vom folosi șahul.biblioteca js pentru generarea de mișcare și tablă de șah.js pentru vizualizarea bord. Biblioteca move generation implementează practic toate regulile șahului. Pe baza acestui fapt, putem calcula toate mișcările legale pentru o anumită stare de bord.

o vizualizare a funcției de generare a mișcării. Poziția de pornire este utilizată ca intrare, iar ieșirea este toate mișcările posibile din acea poziție.

utilizarea acestor biblioteci ne va ajuta să ne concentrăm doar pe cea mai interesantă sarcină: crearea algoritmului care găsește cea mai bună mișcare.

vom începe prin crearea unei funcții care returnează doar o mișcare aleatorie din toate mișcările posibile:

deși acest algoritm nu este un jucător de șah foarte solid, este un bun punct de plecare, deoarece putem juca împotriva lui:

Black joacă mișcări aleatorii. Pot fi redate pe https://jsfiddle.net/lhartikk/m14epfwb/4

Pasul 2 : Evaluarea poziției

acum, să încercăm să înțelegem care parte este mai puternică într-o anumită poziție. Cel mai simplu mod de a realiza acest lucru este să numărați puterea relativă a pieselor de pe placă folosind următorul tabel:

cu funcția de evaluare, putem crea un algoritm care alege mișcarea care oferă cea mai mare evaluare:

singura îmbunătățire tangibilă este că algoritmul nostru va capta acum o piesă dacă poate.

Negru joacă cu ajutorul funcției de evaluare simplă. Pot fi redate pe https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Pasul 3: arborele de căutare folosind Minimax

în continuare vom crea un arbore de căutare din care algoritmul poate alege cea mai bună mișcare. Acest lucru se face folosind algoritmul Minimax.

în acest algoritm, arborele recursiv al tuturor mișcărilor posibile este explorat la o anumită adâncime, iar poziția este evaluată la sfârșitul „frunzelor” arborelui.

după aceea, returnăm fie cea mai mică, fie cea mai mare valoare a copilului la nodul părinte, în funcție de faptul dacă este alb sau negru să se miște. (Adică încercăm să minimizăm sau să maximizăm rezultatul la fiecare nivel.)

o vizualizare a algoritmului minimax într-o poziție artificială. Cea mai bună mișcare pentru alb este b2-c3, deoarece putem garanta că putem ajunge într-o poziție în care evaluarea este -50

cu minimax în loc, algoritmul nostru începe să înțeleagă câteva tactici de bază ale șahului:

Minimax cu nivelul de adâncime 2. Pot fi redate pe: https://jsfiddle.net/k96eoq0q/1/

eficacitatea algoritmului minimax se bazează în mare măsură pe adâncimea de căutare putem realiza. Acesta este un lucru pe care îl vom îmbunătăți în pasul următor.

Pasul 4: Tunderea alfa-beta

tunderea alfa-beta este o metodă de optimizare a algoritmului minimax care ne permite să ignorăm unele ramuri din arborele de căutare. Acest lucru ne ajută să evaluăm arborele de căutare minimax mult mai profund, în timp ce folosim aceleași resurse.tăierea alfa-beta se bazează pe situația în care putem opri evaluarea unei părți a arborelui de căutare dacă găsim o mișcare care duce la o situație mai gravă decât o mișcare descoperită anterior.

tăierea alfa-beta nu influențează rezultatul algoritmului minimax — îl face doar mai rapid.

algoritmul alfa-beta este, de asemenea, mai eficient dacă se întâmplă să vizităm mai întâi acele căi care duc la mișcări bune.

pozițiile pe care nu trebuie să le explorăm dacă se utilizează tăierea alfa-beta și arborele este vizitat în ordinea descrisă.

cu alfa-beta, obținem un impuls semnificativ algoritmului minimax, așa cum se arată în exemplul următor:

numărul de poziții care sunt necesare pentru a evalua dacă dorim să efectuăm o căutare cu adâncimea de 4 și poziția „rădăcină” este cea care este afișată.

urmați acest link pentru a încerca versiunea îmbunătățită alfa-beta a șah ai.

Pasul 5: Funcția de evaluare îmbunătățită

funcția de evaluare inițială este destul de naivă, deoarece numărăm doar materialul care se găsește pe tablă. Pentru a îmbunătăți acest lucru, adăugăm la evaluare un factor care ține cont de poziția pieselor. De exemplu, un cavaler din centrul tablei este mai bun (deoarece are mai multe opțiuni și, prin urmare, este mai activ) decât un cavaler de pe marginea tablei.

vom folosi o versiune ușor ajustată a tabelelor pătrate care sunt descrise inițial în șah-programare-wiki.

piesele vizualizate-tabele pătrate vizualizate. Putem reduce sau crește evaluarea, în funcție de locația piesei.

cu următoarea îmbunătățire, începem să obținem un algoritm care joacă un șah „decent”, cel puțin din punctul de vedere al unui jucător casual:

evaluare îmbunătățită și tăiere alfa-beta cu adâncimea de căutare de 3. Pot fi redate pe https://jsfiddle.net/q76uzxwe/1/

concluzii

puterea chiar și un simplu algoritm de joc de șah este că nu face greșeli stupide. Acestea fiind spuse, încă nu are înțelegere strategică.

cu metodele pe care le-am introdus aici, am reușit să programăm un algoritm de joc de șah care poate juca șah de bază. „AI-parte” (mișcare-generație exclusă) a algoritmului final este de doar 200 de linii de cod, ceea ce înseamnă că conceptele de bază sunt destul de simple de implementat. Puteți verifica versiunea finală este pe GitHub.

unele îmbunătățiri suplimentare pe care le-am putea face algoritmului ar fi, de exemplu:

ordonarea mișcărilor
generarea de mișcări mai rapide
și evaluarea specifică jocului final.

KGSAU