de Ben Carp

Construirea unui algoritm AI pentru provocarea Tic-Tac-Toe

Construirea unui algoritm AI pentru provocarea Tic Tac Toe

Ca parte a curriculumului Routech, am fost provocat să construiesc un Tic-Tac-Toe aplicație web. A fost o adevărată plăcere.

Aplicația include un player computerizat suprem. Poate optimiza orice situație dată pe placa Tic-Tac-Toe. Rezultatul m-a surprins.

Chiar și într-un joc atât de simplu, computerul ma învățat câteva mișcări noi. În ceea ce privește codul pe care l-am scris, este oarecum unic și interesant de explorat.

Verifică

Vizita acest link și alegeți să jucați împotriva computerului. Te provoc să câștigi. S-ar putea să descoperiți … că nu puteți.

Cu toate acestea, dacă sunteți greu în apărare, ați putea afla că nici computerul nu este capabil să câștige. Am învățat prin experiență că Tic-Tac-Toe are un simplu ne-pierde strategie.

Aceasta înseamnă că, dacă reușiți să obțineți o egalitate, faceți alegeri defensive corecte. Computerul își optimizează în continuare „mișcările”. Deci, cel mai bun rezultat pe care îl poate obține împotriva unui jucător ca tine ar putea fi doar o egalitate.

Pașii principali ai soluției

1. structura datelor plăcii

_gameBoard: [[“”, “”, “”],[“”, “”, “”],[“”, “”, “”]]

Tabloul tablou conține 3 tablouri, fiecare reprezentând un rând.
Fiecare matrice de rânduri conține 3 elemente de caractere sau șiruri.

Aceste elemente sunt fie:

  • „” Ca un șir gol, reprezentând o celulă goală
  • „X” reprezentând jucătorul X.
  • „O” reprezentând jucătorul O.

2. funcția getResult

Începe la Linia 59

În orice stat dat, consiliul va fi într-una și una dintre aceste posibile stări:

  • Incomplet
  • jucătorul X a câștigat
  • Jucătorul O a câștigat
  • sau o cravată

getResult funcția primește o matrice de plăci, iterează pe toate rândurile, prin toate coloanele și pe ambele diagonale. Verifică succesiunea simbolurilor. Apoi ne anunță starea actuală a acelei plăci.

3. Funcția getBestMove

Aici devine mai dificil. Când placa este goală, este foarte dificil să identifici cea mai bună mișcare posibilă. Uitați-vă la acest tablou.

1612115946 462 Construirea unui algoritm AI pentru provocarea Tic Tac Toe

Care este cea mai bună mișcare posibilă?

1612115946 695 Construirea unui algoritm AI pentru provocarea Tic Tac Toe

Când tabloul este populat, cea mai bună mișcare posibilă iese în ochii noștri.

1612115946 117 Construirea unui algoritm AI pentru provocarea Tic Tac Toe

Să folosim această placă populată ca punct de plecare. Să decidem că următoarea mișcare este a noastră și că simbolul nostru este un „X”.

Să încercăm să identificăm cea mai bună mișcare posibilă cu instrumentele pe care le avem deja. Există 3 celule goale care corespund cu 3 mișcări posibile. Să verificăm rezultatul pentru fiecare dintre aceste opțiuni.

Putem face acest lucru prin repetarea posibilelor mișcări și pentru fiecare dintre ele:

  • Creați o nouă placă
  • Adăugați simbolul nostru la celula goală corespunzătoare
  • Trimiteți acest forum la getResult funcţie
1612115946 782 Construirea unui algoritm AI pentru provocarea Tic Tac Toe
Mutați 1
1612115947 626 Construirea unui algoritm AI pentru provocarea Tic Tac Toe
Mutați 2
1612115947 719 Construirea unui algoritm AI pentru provocarea Tic Tac Toe
Mutați 3

Din cele 3 placi din figura de mai sus, când trimitem a doua placă către getResult funcție, vom primi trofeul nostru.

Vă rugăm să vă concentrați pentru următorii pași esențiali:

  1. Trebuie să evaluăm mișcările posibile, astfel încât să le putem compara. Să decidem că, dacă o mișcare produce o tablă câștigătoare, o vom nota 1. Dacă produce o tablă care pierde, va primi nota -1. O egalitate va primi nota 0.
  2. Muta 2 va primi nota 1. Când găsim o mișcare notată cu 1 putem ignora toate celelalte mișcări posibile. Nu există altă mișcare posibilă mai bună decât o victorie definitivă.
  3. Dar, de dragul înțelegerii, cum am califica mișcările 1 sau 3 sau orice altă mișcare cu un rezultat incomplet?

Să ne concentrăm asupra mișcării 3. Soluția este de a trimite placa corespunzătoare recursiv către getBestMove funcţie.

S-ar putea să vă gândiți: „Dar așteaptă! Adversarul nostru joacă următoarea mișcare. ” Asta e corect. Să aflăm ce notă obține adversarul nostru pentru cea mai bună mișcare viitoare.

Adversarul nostru are doar două mișcări posibile:

1612115947 113 Construirea unui algoritm AI pentru provocarea Tic Tac Toe
Mutați 3-1
1612115947 738 Construirea unui algoritm AI pentru provocarea Tic Tac Toe
Mutați 3-4

Mutare 3-1 va câștiga jocul în favoarea adversarului nostru. Deoarece folosim exact același lucru getBestMove funcție, Mutare 3-1 va primi nota 1.

Acest lucru ar putea fi puțin confuz, întrucât atât victoria noastră, cât și pierderea noastră vor primi note de 1. Trebuie să ne amintim că această apelare funcțională aparține adversarului nostru, iar victoria lui este pierderea noastră și invers.

Trebuie să negăm orice notă returnată la getBestMove funcție de getBestMove funcţie.

Mutați 3–1 primește nota 1. getBestMove funcția returnează o notă de 1 și putem nota Move 3 cu un -1.

1612115948 208 Construirea unui algoritm AI pentru provocarea Tic Tac Toe

În acest mod, getBestMove funcția continuă să exploreze mișcările și mișcările consecvente. Acest proces va continua până la:

  1. Acesta găsește o mutare notată cu 1, caz în care va returna mutarea imediat
  2. Va continua până când fiecare mișcare posibilă va avea o notă. Miscările posibile (cu gradele 0 și -1) sunt stocate într-un tablou
  3. Matricea va fi apoi:
    [a] randomizat
    [b] sortate de la mare la mic
    [c] primul element va fi returnat

Acești pași garantează că:

  1. O mișcare de pierdere va fi evitată dacă nu este singura opțiune
  2. Playerul computerului poate juca divers

Note de final:

  1. Există puternice îngrijorări legitime cu privire la riscuri Inteligența artificială (AI) aduce cu sine.
    Să folosim AI în beneficiul tuturor.
    Cel mai bun software AI posibil este acela care ne poate împiedica să folosim greșit AI.
  2. M-am consultat Assaf Weinberg în procesul de scriere a aplicației

Vedea codul meu pe GitHub.