Inteligență artificială de joc de masă: algoritmul Minimax: 8 pași

2024 Autor: John Day | [email protected]. Modificat ultima dată: 2024-01-30 11:43

V-ați întrebat vreodată cum sunt fabricate computerele împotriva cărora jucați în șah sau în dame? Ei bine, nu căutați mai departe de acest instructabil, deoarece vă va arăta cum să creați o inteligență artificială (AI) simplă, dar eficientă, utilizând algoritmul Minimax! Prin utilizarea algoritmului Minimax, AI face mișcări bine planificate și gândite (sau cel puțin imită un proces de gândire). Acum, aș putea să vă dau codul pentru AI pe care l-am făcut, dar asta nu ar fi distractiv. Voi explica logica din spatele alegerilor computerului.

În acest Instructable, vă voi îndruma prin pașii despre cum să creați un AI pentru Othello (AKA Reversi) în python. Ar trebui să aveți o înțelegere intermediară a modului de codificare în python înainte de a aborda acest proiect. Iată câteva site-uri web bune pentru a vă pregăti pentru acest instructabil: w3schools sau learnpython. La sfârșitul acestui Instructable, ar trebui să aveți un AI care să facă mișcări calculate și ar trebui să poată învinge majoritatea oamenilor.

Deoarece acest Instructable se va ocupa în primul rând de modul de realizare a unei AI, nu voi explica cum să proiectăm un joc în python. În schimb, voi da codul jocului în care un om poate juca împotriva altui om și îl pot modifica astfel încât să puteți juca un joc în care un om joacă împotriva AI.

Am învățat cum să creez acest AI printr-un program de vară la Columbia SHAPE. M-am distrat bine acolo, așa că aruncați o privire pe site-ul lor web pentru a vedea dacă ați fi interesat.

Acum că am scos logistica din drum, să începem codarea!

(Am pus câteva note în imagini, așa că asigurați-vă că le priviți)

Provizii

Asta e ușor:

1) Computer cu mediu python, cum ar fi Spyder sau IDLE

2) Descărcați fișierele pentru jocul Othello de pe GitHub

3) Creierul tău cu răbdare instalat

Pasul 1: Descărcați fișierele necesare

Când intrați în GitHub, ar trebui să vedeți 5 fișiere. Descărcați toate cele 5 și plasați-le pe toate în același folder. Înainte de a rula jocul, deschideți toate fișierele din mediul spyder.

Iată ce fac fișierele:

1) othello_gui.py acest fișier creează tabla de joc pe care jucătorii să o poată juca (fie că este vorba de oameni sau de computer)

2) othello_game.py acest fișier redă două calculatoare unul împotriva celuilalt fără tabloul de joc și arată doar punctele de scor și mișcare

3) ai_template.py aici vă veți pune tot codul pentru a vă crea AI

4) randy_ai.py acesta este un AI premade care își alege mișcările la întâmplare

5) othello_shared.py o grămadă de funcții prestabilite pe care le puteți utiliza pentru a vă crea AI, cum ar fi pentru a verifica mișcările disponibile, scorul sau starea tabloului

6) Celelalte trei fișiere: Puma.py, erika_5.py și nathan.py, realizate de mine, Erika și respectiv Nathan din programul SHAPE, acestea sunt trei AI diferite cu coduri unice

Pasul 2: Cum să deschizi și să joci Python Othello

După ce ați deschis toate fișierele, în colțul din dreapta jos al ecranului, tastați „rulați othello_gui.py” și apăsați Enter în consola IPython. Sau în terminalul Mac, tastați „python othello_gui.py” (după ce vă aflați în dosarul corect, desigur). Apoi, o tablă ar trebui să apară pe ecran. Acest mod este modul uman vs uman. Lumina merge al doilea și întunericul întâi. Uită-te la videoclipul meu dacă ești confuz. În partea de sus, există scorul fiecărei plăci de culoare. Pentru a juca, faceți clic pe un spațiu de mișcare valid pentru a plasa o țiglă acolo și apoi dați computerul adversarului dvs. care va face același lucru și va repeta.

Dacă nu știi cum să joci Othello, citește aceste reguli de pe site-ul ultra board-urilor:

Negrul se mișcă întotdeauna primul. O mișcare se face prin plasarea unui disc de culoarea jucătorului pe tablă într-o poziție care „depășește” unul sau mai multe dintre discurile adversarului. Un disc sau un rând de discuri este flancat atunci când este înconjurat la capete de discuri de culoarea opusă. Un disc poate depăși orice număr de discuri pe unul sau mai multe rânduri în orice direcție (orizontală, verticală, diagonală)…. (termină de citit pe site-ul lor)

Diferența dintre jocul original și acest joc de piton este că atunci când nu mai există mișcări valide rămase pentru un jucător, jocul se termină

Acum, că poți juca jocul cu un prieten, haideți să creăm un AI cu care poți juca.

Pasul 3: Algoritm Minimax: Generarea de scenarii

Înainte de a vorbi despre cum să scrieți acest lucru în cod, să trecem peste logica din spatele acestuia. Algoritmul minimax este un algoritm de luare a deciziilor, de urmărire înapoi și este de obicei utilizat în jocurile cu doi jucători, bazate pe ture. Scopul acestei AI este de a găsi următoarea cea mai bună mișcare și următoarele cele mai bune mișcări până când câștigă jocul.

Acum, cum ar determina algoritmul care mișcare este cea mai bună mișcare? Opriți-vă și gândiți-vă cum ați alege următoarea mișcare. Majoritatea oamenilor ar alege mișcarea care le-ar da cele mai multe puncte, nu? Sau dacă s-ar gândi înainte, ar alege mișcarea care ar crea o situație în care ar putea câștiga și mai multe puncte. Ultimul mod de gândire este modul în care gândește algoritmul Minimax. Se uită la toate configurările viitoare ale consiliului și face mișcarea care ar duce la cele mai multe puncte.

Am numit acest lucru un algoritm de backtracking, deoarece începe prin crearea și evaluarea mai întâi a tuturor stărilor viitoare ale plăcii cu valorile lor asociate. Acest lucru înseamnă că algoritmul va juca jocul oricâte trebuie (făcând mișcările pentru el și pentru adversar) până când fiecare scenariu al jocului a fost jucat. Pentru a urmări toate stările tablourilor (scenarii), putem desena un copac (uitați-vă în imagini). Arborele din imaginea de mai sus este un exemplu simplu de joc Connect 4. Fiecare configurație a plăcii se numește stare a plăcii și locul său în copac se numește nod. Toate nodurile din partea de jos a arborelui sunt stările finale ale plăcii după ce au făcut toate mișcările. Evident, unele state de bord sunt mai bune pentru un jucător decât pentru celălalt. Deci, acum trebuie să facem AI să aleagă în ce stat de bord vrea să ajungă.

Pasul 4: Minimax: Evaluarea configurațiilor plăcii

Pentru a da valori statelor de pe tablă, trebuie să învățăm strategiile jocului pe care îl jucăm: în acest caz, strategiile lui Othello. Deoarece acest joc este o bătălie de a răsturna adversarul și discurile dvs., cele mai bune poziții de disc sunt cele care sunt stabile și nu pot fi răsturnate. Colțul, de exemplu, este locul în care atunci când este plasat un disc nu poate fi schimbat cu cealaltă culoare. Astfel, acel loc ar fi extrem de valoros. Alte poziții bune includ părțile laterale ale scândurii, care vă permit să luați o mulțime de pietre. Există mai multe strategii pe acest site web.

Acum putem atribui valori pozițiilor pentru fiecare consiliu de stat. Când o poziție este ocupată de piesa AI, atunci acordați un anumit număr de puncte în funcție de poziție. De exemplu, o stare de tablă în care piesa AI este în colț, puteți oferi un bonus de 50 de puncte, dar dacă ar fi într-un loc nefavorabil, piesa poate avea o valoare de 0. După luarea în considerare a tuturor valorilor de pozițiile, atribuiți statului de bord o valoare. De exemplu, dacă AI are o piesă în colț, starea plăcii poate avea un scor de 50, în timp ce o altă stare a plăcii cu piesa AI în mijloc are un scor de 10.

Există multe modalități de a face acest lucru și am trei euristici diferite pentru a evalua piesele de bord. Vă încurajez să vă faceți propriul tip de euristică. Am încărcat trei AI diferite pe github de către trei producători diferiți, cu trei euristici diferite: Puma.py, erika5.py, nathanh.py.

Pasul 5: Algoritm Minimax: Alegerea celei mai bune mișcări

Acum ar fi frumos dacă AI ar putea alege toate mișcările pentru a ajunge la starea de bord cu cel mai mare scor. Dar amintiți-vă că AI a ales, de asemenea, mișcările pentru adversar atunci când a generat toate stările de bord și, dacă adversarul este inteligent, nu va permite AI să ajungă la cel mai mare scor de bord. În schimb, un adversar inteligent ar face mișcarea pentru a face AI să meargă în starea de jos a bordului. În algoritm, îi numim pe cei doi jucători un jucător de maximizare și un jucător de minimizare. AI ar fi jucătorul care maximizează, deoarece dorește să obțină cele mai multe puncte pentru sine. Adversarul ar fi jucătorul care minimizează, deoarece adversarul încearcă să facă mișcarea acolo unde AI obține cele mai puține puncte.

Odată ce toate stările plăcii sunt generate și valorile au fost atribuite plăcilor, algoritmul începe să compare stările plăcii. În imagini, am creat un copac pentru a reprezenta modul în care algoritmul și-ar alege mișcările. Fiecare împărțire în ramuri este o mișcare diferită pe care AI sau adversarul o poate juca. În stânga rândurilor de noduri, am scris dacă jucătorul de maximizare sau de minimizare merge. Rândul de jos este toate stările tabloului cu valorile lor. În interiorul fiecăruia dintre aceste noduri este un număr și acestea sunt scorurile pe care le atribuim fiecărei plăci: cu cât sunt mai mari, cu atât este mai bine pentru AI să aibă.

Definiții: nod părinte - un nod care rezultă sau creează noduri sub acesta; originea nodurilor copii - nodurile care provin din același nod părinte

Nodurile goale reprezintă ce mișcare va face AI pentru a ajunge la cea mai bună stare de bord. Începe cu compararea copiilor nodului din stânga: 10, -3, 5. Deoarece jucătorul care maximizează ar face mișcarea, ar alege mișcarea care i-ar oferi cele mai multe puncte: 10. Deci, apoi selectăm și stocăm deplasați-vă cu scorul de bord și scrieți-l în nodul părinte. Acum că 10 se află în nodul părinte, acum este rândul jucătorilor care minimizează. Cu toate acestea, nodul cu care am compara 10 este gol, deci trebuie să evaluăm mai întâi acel nod înainte ca jucătorul de minimizare să poată alege. Așadar, ne întoarcem la rândul jucătorului maxim și comparăm copiii nodului adiacent: 8, -2. Maximizarea va alege 8 și vom scrie asta în nodul părinte gol. Acum că algoritmul a terminat de completat spațiile goale pentru copiii unui nod de deasupra acestuia, jucătorul minimizator poate compara acei copii - 10 și 8 și alege 8. Algoritmul repetă apoi acest proces până când întregul copac este completat. La sfârșitul acestui exemplu, avem scorul 8. Aceasta este cea mai înaltă stare pe care o poate juca AI, presupunând că adversarul joacă optim. Deci AI va alege prima mișcare care duce la starea de 8 borduri și, dacă adversarul joacă optim, AI ar trebui să joace toate mișcările pentru a ajunge la starea de bord 8. (Urmați notele din imaginile mele)

Știu că a fost mult. Dacă sunteți unul dintre acele tipuri care trebuie să vorbească cu cineva pentru a înțelege ceva, iată câteva videoclipuri pe care le-am vizionat pentru a mă ajuta să înțeleg ideea din spatele acestui lucru: 1, 2, 3.

Pasul 6: Algoritm Minimax: Pseudocod

După ce înțelegeți logica din spatele algoritmului minimax, aruncați o privire la acest pseudocod (funcțiile care sunt universale pentru toate codurile) din Wikipedia:

funcția minimax (nod, adâncime, maximizingPlayer) este

dacă adâncimea = 0 sau nodul este un nod terminal atunci

returnează valoarea euristică a nodului

dacă maximizingPlayer atunci

valoare: = −∞

pentru fiecare copil de nod do

valoare: = max (valoare, minimax (copil, adâncime - 1, FALS))

valoare returnată

else (* jucător minimizant *)

valoare: = + ∞

pentru fiecare copil de nod do

valoare: = min (valoare, minimax (copil, adâncime - 1, ADEVĂRAT))

valoare returnată

Aceasta este o funcție recursivă, ceea ce înseamnă că se numește de la sine până când ajunge la un punct de oprire. În primul rând, funcția ia trei valori, nodul, adâncimea și al cui rând este. Valoarea nodului este locul în care doriți ca programul să înceapă căutarea. Adâncimea este cât de mult doriți să caute programul. De exemplu, în exemplul meu de copac are o adâncime de 3, deoarece a căutat în toate stările plăcii după 3 mutări. Desigur, ne-ar plăcea ca AI să verifice fiecare stare de bord și să aleagă un câștig câștigător, dar în majoritatea jocurilor în care există mii, dacă nu milioane de configurații de bord, laptopul dvs. de acasă nu va putea procesa toate aceste configurații. Deci, limităm adâncimea de căutare a AI și o ducem la cea mai bună stare de bord.

Acest pseudocod reproduce procesul pe care l-am explicat în cei doi pași anteriori. Acum, să facem acest lucru un pas mai departe și să corectăm acest lucru în codul Python.

Pasul 7: Realizarea AI cu Ai_template.py

Înainte de a arunca o privire asupra codului meu Minimax AI, aruncați o încercare de a vă crea propria AI cu fișierul ai_template.py și pseudo-codul despre care am vorbit în ultimul pas. Există două funcții în șablonul ai numite: def minimax_min_node (bord, culoare) și def minimax_max_node (bord, culoare). În loc să avem funcția minimax care se numește recursiv, avem două funcții diferite, care se apelează reciproc. Pentru a crea euristica de evaluare a stărilor plăcii, va trebui să vă creați propria funcție. Există o funcție premade în fișierul othello_shared.py pe care îl puteți utiliza pentru a vă construi AI.

După ce ai AI-ul tău, încearcă să îl folosești, randy_ai.py. Pentru a rula două ais unul împotriva celuilalt, tastați „python othello_gui.py (introduceți numele fișierului).py (introduceți numele fișierului. (introduceți numele fișierului).py și asigurați-vă că vă aflați în directorul potrivit. De asemenea, uitați-vă la videoclipul meu pentru pașii exacți.

Pasul 8: E timpul să te lupți cu AI

Acum, obțineți o grămadă de prieteni pe computer și faceți-i să-și proiecteze propria AI! Apoi, puteți face o competiție și puteți să-l faceți pe ducele dvs. AI. Sperăm că, chiar dacă nu ți-ai putea construi propriul AI, ai reușit să înțelegi cum funcționează algoritmul minimax. Dacă aveți întrebări, nu ezitați să postați orice întrebări în comentariile de mai jos.