Umjetna inteligencija za društvene igre: minimalni algoritam: 8 koraka

2024 Autor: John Day | [email protected]. Zadnja promjena: 2024-01-30 09:35

Jeste li se ikada zapitali kako nastaju računala protiv kojih igrate u šahu ili damu? Pa ne tražite dalje od ovog Instructablea jer će vam pokazati kako napraviti jednostavnu, ali učinkovitu umjetnu inteligenciju (AI) koristeći Minimax algoritam! Koristeći Minimax Algoritam, AI čini dobro planirane i promišljene poteze (ili barem oponaša misaoni proces). Mogao bih vam samo dati kôd za AI koji sam napravio, ali to ne bi bilo zabavno. Objasnit ću logiku iza izbora računala.

U ovom Instructable -u ću vas provesti kroz korake o tome kako napraviti AI za Othella (AKA Reversi) u pythonu. Trebali biste imati srednje razumijevanje kako kodirati u pythonu prije nego što se pozabavite ovim projektom. Evo nekoliko dobrih web stranica koje možete pogledati kako biste se pripremili za ovaj Instructable: w3schools ili learnpython. Na kraju ovog Instructablea trebali biste imati AI koji će napraviti proračunate poteze i trebao bi moći pobijediti većinu ljudi.

Budući da će se ovaj Instructable prvenstveno baviti načinom na koji je moguće napraviti AI, neću objašnjavati kako dizajnirati igru u pythonu. Umjesto toga, dat ću kôd za igru u kojoj se čovjek može igrati protiv drugog čovjeka i izmijeniti ga tako da možete igrati igru u kojoj se čovjek igra protiv umjetne inteligencije.

Naučio sam kako stvoriti ovu umjetnu inteligenciju kroz ljetni program u Columbia SHAPE. Bilo mi je lijepo tamo pa pogledajte njihovu web stranicu da vidite hoće li vas zanimati.

Sad kad smo logistiku maknuli s puta, počnimo kodirati!

(Na slike sam stavio nekoliko bilješki pa ih svakako pogledajte)

Pribor

Ovo je lako:

1) Računalo s python okruženjem poput Spydera ili IDLE -a

2) Preuzmite datoteke za igru Othello s mog GitHub -a

3) Vaš mozak s instaliranim strpljenjem

Korak 1: Preuzmite potrebne datoteke

Kad uđete na moj GitHub, trebali biste vidjeti 5 datoteka. Preuzmite svih 5 i stavite ih sve u istu mapu. Prije nego pokrenemo igru, otvorite sve datoteke u špijunskom okruženju.

Evo što datoteke rade:

1) othello_gui.py ova datoteka stvara ploču za igru na kojoj će se igrati igrači (bilo ljudski ili računalo)

2) othello_game.py ova datoteka igra dva računala jedno protiv drugog bez ploče za igru i prikazuje samo rezultat i pomiče pozicije

3) ai_template.py ovdje ćete staviti sav svoj kôd za izradu svoje umjetne inteligencije

4) randy_ai.py ovo je unaprijed pripremljena umjetna inteligencija koja nasumično bira svoje poteze

5) othello_shared.py gomilu unaprijed izrađenih funkcija koje možete koristiti za izradu svoje umjetne inteligencije, poput provjere dostupnih poteza, rezultata ili stanja ploče

6) Tri druge datoteke: Puma.py, erika_5.py i nathan.py, koje smo ja, Erika i Nathan napravili iz programa SHAPE, to su tri različite umjetne inteligencije s jedinstvenim kodovima

Korak 2: Kako otvoriti i igrati Python Othello

Nakon što otvorite sve datoteke, u donji desni kut zaslona upišite "run othello_gui.py" i pritisnite enter u konzoli IPython. Ili u Mac terminalu upišite "python othello_gui.py" (naravno, nakon što ste u pravoj mapi). Tada bi se na vašem zaslonu trebala pojaviti ploča. Ovaj način je način rada čovjek protiv čovjeka. Svjetlo ide drugo, a prvo tamno. Pogledajte moj video ako ste zbunjeni. iNa vrhu je ocjena svake pločice u boji. Da biste igrali, kliknite valjani prostor za pomicanje da biste tamo postavili pločicu, a zatim dajte računalo svom protivniku koji će učiniti isto i ponoviti.

Ako ne znate igrati Othello, pročitajte ova pravila s web stranice ultra zajednice:

Crna se uvijek kreće prva. Pokret se vrši postavljanjem diska u boji igrača na ploču u položaj koji "nadilazi" jedan ili više protivničkih diskova. Disk ili red diskova je bočan ako je na krajevima okružen diskovima suprotne boje. Disk može nadmašiti bilo koji broj diskova u jednom ili više redova u bilo kojem smjeru (vodoravno, okomito, dijagonalno)…. (dovršite čitanje na njihovoj web stranici)

Razlika između izvorne igre i ove igre Python je u tome što kada nema preostalih valjanih poteza za jednog igrača, igra prestaje

Sada kad možete igrati igru s prijateljem, napravimo AI s kojim se možete igrati.

Korak 3: Minimaksni algoritam: generiranje scenarija

Prije nego govorimo o tome kako to napisati u kodu, prijeđimo na logiku koja stoji iza toga. Minimaksni algoritam je algoritam za donošenje odluka i praćenje unatrag i obično se koristi u igrama s dva igrača, naizmjence. Cilj ove umjetne inteligencije je pronaći sljedeći najbolji potez i sljedeće najbolje poteze dok ne osvoji igru.

Kako bi algoritam odredio koji je potez najbolji? Zastanite i razmislite kako biste odabrali sljedeći potez. Većina ljudi odabrala bi potez koji bi im dao najviše bodova, zar ne? Ili da razmišljaju unaprijed, odabrali bi potez koji bi postavio situaciju u kojoj bi mogli osvojiti još više bodova. Potonji način razmišljanja način je na koji razmišlja minimaksni algoritam. Gleda unaprijed u sve buduće postavke odbora i čini potez koji bi doveo do najviše bodova.

Nazvao sam to algoritmom za vraćanje unatrag jer počinje stvaranjem i vrednovanjem svih budućih stanja ploče s pripadajućim vrijednostima. To znači da će algoritam igrati igru onoliko koliko je potrebno (povlačenjem za sebe i protivnika) dok se ne odigra svaki scenarij igre. Da bismo pratili sva stanja ploče (scenarije), možemo nacrtati stablo (pogledajte na slikama). Stablo na gornjoj slici jednostavan je primjer igre Connect 4. Svaka konfiguracija ploče naziva se stanje ploče, a njeno mjesto na stablu naziva se čvorom. Svi čvorovi na dnu stabla su konačna stanja ploče nakon što su napravili sve poteze. Očigledno su neke države odbora bolje za jednog igrača od drugog. Dakle, sada moramo natjerati AI da odabere u koje stanje odbora želi doći.

Korak 4: Minimax: Procjena konfiguracija ploče

Da bismo dali vrijednosti državama odbora, moramo naučiti strategije igre koju igramo: u ovom slučaju strategije Othella. Budući da je ova igra bitka okretanja protivnikovih i vaših diskova, najbolji položaji diskova su oni koji su stabilni i ne mogu se preokrenuti. Ugao je, na primjer, mjesto gdje se disk ne može promijeniti u drugu boju kad se postavi. Stoga bi to mjesto bilo iznimno vrijedno. Ostali dobri položaji uključuju stranice ploče koje bi vam omogućile da uzmete puno kamenja. Na ovoj web stranici postoji više strategija.

Sada možemo dodijeliti vrijednosti pozicijama za svaki odbor odbora. Kada mjesto zauzima dio AI -a, tada dajete određeni broj bodova ovisno o položaju. Na primjer, stanje ploče na kojoj se AI dio nalazi u kutu možete dati bonus od 50 bodova, ali ako je na nepovoljnom mjestu, komad može imati vrijednost 0. Nakon što se uzmu u obzir sve vrijednosti pozicijama dodjeljujete vrijednost stanja ploče. Na primjer, ako AI ima dio u kutu, stanje ploče može imati ocjenu 50, dok drugo stanje ploče s umjetnikovim komadom u sredini ima ocjenu 10.

Postoji mnogo načina za to, a ja imam tri različite heuristike za procjenu komada ploče. Potičem vas da napravite vlastiti tip heuristike. Prenio sam tri različita AI -a na svoj github od tri različita proizvođača, s tri različite heuristike: Puma.py, erika5.py, nathanh.py.

Korak 5: Minimaksni algoritam: odabir najboljeg poteza

Sada bi bilo lijepo kad bi umjetna inteligencija mogla samo odabrati sve poteze kako bi došla do stanja ploče s najvećim brojem bodova. Ali zapamtite da je AI također birao poteze za protivnika kada je stvarao sva stanja na ploči i ako je protivnik pametan, neće dopustiti AI -u da dođe do najvećeg rezultata na ploči. Umjesto toga, pametan protivnik napravio bi potez kako bi AI prešao u najniže stanje ploče. U algoritmu dva igrača nazivamo igračem koji maksimizira i minimizira igrača. Umjetna inteligencija bila bi igrač koji maksimizira jer želi za sebe dobiti najviše bodova. Protivnik bi bio igrač koji minimizira jer protivnik pokušava napraviti potez gdje umjetna inteligencija dobije najmanje bodova.

Nakon što se generiraju sva stanja ploče i dodijele vrijednosti pločama, algoritam počinje uspoređivati stanja ploče. Na slikama sam stvorio stablo koje predstavlja kako će algoritam birati svoje poteze. Svaki rascjep u granama različit je potez koji AI ili protivnik mogu odigrati. Lijevo od redova čvorova napisao sam ide li igrač za povećanje ili smanjenje. Donji red su sva stanja ploče s njihovim vrijednostima. Unutar svakog od tih čvorova nalazi se broj i to su bodovi koje dodjeljujemo svakoj ploči: što su veće, to je bolje za AI.

Definicije: roditeljski čvor - čvor koji rezultira ili stvara čvorove ispod njega; podrijetlo podređenih čvorova - čvorova koji dolaze iz istog roditeljskog čvora

Prazni čvorovi predstavljaju potez koji će AI učiniti da dođe do najboljeg stanja ploče. Počinje uspoređivanjem djece krajnjeg lijevog čvora: 10, -3, 5. Budući da bi igrač s maksimiziranjem napravio potez, odabrao bi potez koji bi mu dao najviše bodova: 10. Dakle, tada odabiremo i pohranjujemo to pomaknite se s rezultatom ploče i upišite ga u roditeljski čvor. Sada kada je 10 u roditeljskom čvoru, na redu su igrači koji minimiziraju. Međutim, čvor s kojim bismo usporedili 10 prazan je, pa moramo prvo procijeniti taj čvor prije nego što igrač za minimiziranje može izabrati. Vraćamo se na maksimiziranje poteza igrača i uspoređujemo djecu susjednog čvora: 8, -2. Maksimiziranjem će se izabrati 8 i to ćemo zapisati u prazan roditeljski čvor. Sada kada je algoritam završio s popunjavanjem praznih mjesta za djecu čvora iznad njega, igrač za minimiziranje može usporediti tu djecu - 10 i 8 i izabrati 8. Algoritam zatim ponavlja ovaj postupak dok se cijelo stablo ne ispuni. Na kraju ovog primjera imamo rezultat 8. To je najviše stanje na ploči koje umjetna inteligencija može odigrati pretpostavljajući da protivnik igra optimalno. Tako će AI odabrati prvi potez koji vodi do stanja 8 ploče, a ako protivnik igra optimalno, AI bi trebao odigrati sve poteze kako bi došao do stanja ploče 8 (Slijedite bilješke na mojim slikama)

Znam da je to bilo puno. Ako ste jedan od onih tipova kojima je potrebno da netko razgovara s vama kako bi nešto razumio, evo nekoliko videozapisa koje sam pogledao kako bih lakše shvatio ideju koja stoji iza ovoga: 1, 2, 3.

Korak 6: Minimaksni algoritam: pseudokod

Nakon što shvatite logiku iza algoritma minimaksa, pogledajte ovaj pseudokod (funkcije koje su univerzalne za sve kodove) s wikipedije:

funkcija minimaksa (čvor, dubina, maksimiziranjePlayer) je

ako je dubina = 0 ili je čvor terminalni čvor tada

vratiti heurističku vrijednost čvora

ako maximizingPlayer tada

vrijednost: = −∞

za svako dijete čvora učiniti

vrijednost: = max (vrijednost, minimaks (podređeno, dubina - 1, FALSE))

povratna vrijednost

else (* minimiziranje igrača *)

vrijednost: = +∞

za svako dijete čvora učiniti

vrijednost: = min (vrijednost, minimaks (dijete, dubina - 1, TRUE))

povratna vrijednost

Ovo je rekurzivna funkcija, što znači da se poziva iznova i iznova sve dok ne dosegne točku zaustavljanja. Prvo, funkcija uzima tri vrijednosti, čvor, dubinu i čiji je red. Vrijednost čvora mjesto je na kojem želite da program počne pretraživati. Dubina je koliko daleko želite da program pretražuje. Na primjer, u mom primjeru stabla ima dubinu od 3 jer je pretraživao sva stanja ploče nakon 3 poteza. Naravno, željeli bismo da AI provjeri svako stanje ploče i odabere dobitnu pobjedu, ali u većini igara u kojima postoje tisuće, ako ne i milijuni konfiguracija ploče, vaše prijenosno računalo kod kuće neće moći obraditi sve te konfiguracije. Dakle, ograničavamo dubinu pretraživanja umjetne inteligencije i stavljamo je u najbolje stanje ploče.

Ovaj pseudokod reproducira proces koji sam objasnio u prethodna dva koraka. Idemo sada korak dalje i ispravimo ovo u python kodu.

Korak 7: Izrada umjetne inteligencije pomoću Ai_template.py

Prije nego što pogledate moj Minimax AI kôd, pokušajte napraviti vlastiti AI s datotekom ai_template.py i pseudokodom o kojem smo govorili u posljednjem koraku. U ai predlošku postoje dvije funkcije koje se zovu: def minimax_min_node (ploča, boja) i def minimax_max_node (ploča, boja). Umjesto da se funkcija minimaksa poziva rekurzivno, imamo dvije različite funkcije koje se međusobno pozivaju. Da biste stvorili heuristiku za procjenu stanja ploče, morat ćete stvoriti vlastitu funkciju. U datoteci othello_shared.py postoje unaprijed pripremljene funkcije koje možete koristiti za izradu svoje umjetne inteligencije.

Nakon što ste dobili AI, pokušajte ga pokrenuti, randy_ai.py. Da biste pokrenuli dva aisa jedan protiv drugog, upišite "python othello_gui.py (umetnite naziv datoteke ai).py (umetnite naziv datoteke).py" u terminal za Mac ili upišite "pokrenite othello_gui.py (umetnite naziv datoteke ai).py (umetnite naziv datoteke).py "i provjerite jeste li u pravom direktoriju. Također, pogledajte moj video za točne korake.

Korak 8: Vrijeme je da se AI borite

Sada nabavite hrpu svojih kompjuterskih prijatelja i natjerajte ih da sami dizajniraju svoju AI! Tada se možete natjecati i natjerati svog umjetnog intelektualca da to izvede. Nadajmo se da ste, čak i ako niste mogli izgraditi vlastitu AI, mogli razumjeti kako funkcionira algoritam minimaksa. Ako imate pitanja, slobodno ih postavite u komentarima ispod.