de Lauri Hartikka

Un ghid pas cu pas pentru construirea unei AI simple de șah

Un ghid pas cu pas pentru construirea unei AI simple

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

  • generație de mișcare
  • evaluarea consiliului
  • minimax
  • și tăierea 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 GitHub.

Pasul 1: Mutați generarea și vizualizarea plăcii

Vom folosi șah.js bibliotecă pentru generarea mutării și chessboard.js pentru vizualizarea plăcii. Biblioteca generației de mutare implementează practic toate regulile șahului. Pe baza acestui fapt, putem calcula toate mișcările legale pentru un anumit stat de consiliu.

Un ghid pas cu pas pentru construirea unei AI simple
O vizualizare a funcției de generare a mutării. Poziția inițială este utilizată ca intrare, iar ieșirea reprezintă toate mișcările posibile din această 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 a crea o funcție care returnează 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:

Un ghid pas cu pas pentru construirea unei AI simple
Negrul joacă mișcări aleatorii. Se poate reda 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 de a număra puterea relativă a pieselor de pe tablă folosind următorul tabel:

1611619746 942 Un ghid pas cu pas pentru construirea unei AI simple

Cu funcția de evaluare, putem crea un algoritm care alege mutarea care oferă cea mai înaltă evaluare:

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

1611619746 731 Un ghid pas cu pas pentru construirea unei AI simple
Negrul se joacă cu ajutorul funcției simple de evaluare. Se poate reda pe https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Pasul 3: Căutați arborele folosind Minimax

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

În acest algoritm, arborele recursiv al tuturor mișcărilor posibile este explorat la o adâncime dată, iar poziția este evaluată la capătul „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ă vă mutați. (Adică, încercăm fie să minimalizăm, fie să maximizăm rezultatul la fiecare nivel.)

1611619747 301 Un ghid pas cu pas pentru construirea unei AI simple
O vizualizare a algoritmului minimax într-o poziție artificială. Cea mai bună mișcare pentru alb este b2-c3, pentru că putem garanta că putem ajunge la o poziție în care se află evaluarea -50

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

1611619747 867 Un ghid pas cu pas pentru construirea unei AI simple
Minimax cu nivelul de adâncime 2. Redabil pe: https://jsfiddle.net/k96eoq0q/1/

Eficacitatea algoritmului minimax se bazează în mare măsură pe adâncimea de căutare pe care o putem realiza. Acest lucru este ceva ce vom îmbunătăți în pasul următor.

Pasul 4: tăierea alfa-beta

Alfa-beta tăierea 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, utilizând în același timp resursele.

Tunderea alfa-beta se bazează pe situația în care putem opri evaluarea unei părți din arborele de căutare dacă găsim o mutare care duce la o situație mai gravă decât o mutare descoperită anterior.

Tunderea 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 primul acele căi care duc la mișcări bune.

1611619747 897 Un ghid pas cu pas pentru construirea unei AI simple
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 o creștere semnificativă a algoritmului minimax, așa cum se arată în următorul exemplu:

1611619748 801 Un ghid pas cu pas pentru construirea unei AI simple
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 afișată.

Urma acest link pentru a încerca versiunea îmbunătățită alfa-beta a șahului AI.

Pasul 5: funcție 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 de pe centrul plăcii este mai bun (deoarece are mai multe opțiuni și, prin urmare, este mai activ) decât un cavaler pe marginea plăcii.

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

1611619748 449 Un ghid pas cu pas pentru construirea unei AI simple
Vizualizate tabelele piese pătrate vizualizate. Putem micșora sau mări evaluarea, în funcție de locația piesei.

Cu următoarea îmbunătățire, începem să obținem un algoritm care joacă niște șahuri „decente”, cel puțin din punctul de vedere al unui jucător ocazional:

1611619748 745 Un ghid pas cu pas pentru construirea unei AI simple
Evaluare îmbunătățită și tăiere alfa-beta cu o adâncime de căutare de 3. Redare pe https://jsfiddle.net/q76uzxwe/1/

Concluzii

Puterea chiar și a unui algoritm simplu de joc de șah este că nu face greșeli stupide. Acestea fiind spuse, îi lipsește încă o î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ă. „Partea AI” (exclusă generația de mișcare) a algoritmului final este doar 200 de linii de cod, ceea ce înseamnă că conceptele de bază sunt destul de simple de implementat. Puteți verifica dacă versiunea finală este activată GitHub.

Câteva îmbunătățiri suplimentare pe care le-am putea aduce algoritmului ar fi, de exemplu:

Dacă doriți să aflați mai multe, consultați wiki de programare a șahului. Este o resursă utilă pentru explorarea dincolo de aceste concepte de bază pe care le-am introdus aici.

Mulțumesc pentru lectură!