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

2024 Autor: John Day | [email protected]. Zadnja izmjena: 2024-01-30 08:06

Jeste li se ikada zapitali kako nastaju računari protiv kojih igrate u šahu ili damu? Pa ne tražite dalje od ovog Instructable -a jer će vam pokazati kako napraviti jednostavnu, ali efikasnu umjetnu inteligenciju (AI) koristeći Minimax Algoritam! Koristeći Minimax Algoritam, AI čini dobro planirane i smiš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. Objasniću logiku iza izbora računara.

U ovom Instructable -u ću vas provesti kroz korake kako napraviti AI za Othello (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 Instructable -a 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 se pravi 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 AI kroz ljetni program u Columbia SHAPE. Bilo mi je lijepo tamo pa pogledajte njihovu web stranicu da vidite da li biste bili zainteresovani.

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

(Stavila sam nekoliko napomena na slike pa ih svakako pogledajte)

Supplies

Ovo je lako:

1) Računar sa python okruženjem kao što je Spyder ili IDLE

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

3) Vaš mozak sa 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 šta datoteke rade:

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

2) othello_game.py ova datoteka igra dva računara jedan protiv drugog bez ploče za igru i prikazuje samo rezultat i pozicije za pomicanje

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

4) randy_ai.py ovo je već pripremljena AI koja nasumično bira svoje poteze

5) othello_shared.py gomilu unaprijed izrađenih funkcija koje možete koristiti za izradu 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 AI sa jedinstvenim kodovima

Korak 2: Kako otvoriti i igrati Python Othello

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

Ako ne znate igrati Othello, pročitajte ova pravila sa web stranice ultra odbora:

Crno se uvijek kreće prvo. Pokret se vrši postavljanjem diska u boji igrača na ploču tako da "zaobiđe" 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 zaobići 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 originalne igre i ove python igre je u tome što kada nema preostalih valjanih poteza za jednog igrača, igra se završava

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

Korak 3: Minimaksni algoritam: Generiranje scenarija

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

Kako bi algoritam odredio koji potez je najbolji? Zastanite i razmislite kako biste odabrali sljedeći potez. Većina ljudi bi odabrala 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 je način na koji minimaksni algoritam razmišlja. Gleda unaprijed u sve buduće postavke odbora i čini potez koji bi doveo do najviše bodova.

Nazvao sam ovo algoritmom za vraćanje unatrag, jer počinje tako što prvo stvara i procjenjuje sva buduća stanja ploče s pripadajućim vrijednostima. To znači da će algoritam igrati igru koliko god je potrebno (povlačeći poteze 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 čvor. Svi čvorovi na dnu stabla su konačna stanja ploče nakon svih poteza. Očigledno su neke države odbora bolje za jednog igrača od drugog. Dakle, sada moramo natjerati AI da izabere u koje stanje odbora želi doći.

Korak 4: Minimax: Procjena konfiguracija ploče

Da bismo dali vrijednosti državama na tabli, moramo naučiti strategije igre koju igramo: u ovom slučaju strategije Otela. 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 prevrnuti. Na primjer, ugao je mjesto gdje se disk ne može promijeniti u drugu boju kada se postavi. Stoga bi to mjesto bilo izuzetno vrijedno. Ostali dobri položaji uključuju stranice ploče koje bi vam omogućile da uzmete mnogo kamenja. Na ovoj web stranici postoji više strategija.

Sada možemo dodijeliti vrijednosti pozicijama svakom državnom odboru odbora. Kada poziciju 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, dio može imati vrijednost 0. Nakon što se uzmu u obzir sve vrijednosti pozicijama dodjeljujete vrijednost stanju ploče. Na primjer, ako AI ima dio u kutu, stanje ploče može imati ocjenu 50, dok drugo stanje ploče s AI -jevim dijelom 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 vlastitu vrstu 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 kada bi umjetna inteligencija mogla samo izabrati sve poteze kako bi došla do stanja ploče s najvećim brojem bodova. Ali zapamtite da je umjetna inteligencija također birala poteze za protivnika kada je stvarala sva stanja na ploči i ako je protivnik pametan, neće dozvoliti AI da dođe do najvećeg rezultata na tabli. Umjesto toga, pametan protivnik napravio bi potez kako bi AI prešao u najniže stanje na tabli. U algoritmu dva igrača nazivamo igračem koji maksimizira i minimizira igrača. Vještačka inteligencija bi bila igrač koji maksimizira jer želi sebi prikupiti najviše bodova. Protivnik bi bio igrač koji minimizira jer protivnik pokušava napraviti potez gdje AI dobiva najmanje bodova.

Nakon što su sva stanja ploče generirana i vrijednosti dodijeljene pločama, algoritam počinje uspoređivati stanja ploče. Na slikama sam stvorio stablo koje predstavlja kako će algoritam birati svoje poteze. Svaki rascep u granama je drugačiji potez koji AI ili protivnik mogu odigrati. Lijevo od redova čvorova napisao sam ide li igrač s maksimiziranjem ili minimiziranjem. 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: nadređeni čvor - čvor koji rezultira ili stvara čvorove ispod njega; porijeklo 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, sada su na redu igrači koji minimiziraju. Međutim, čvor s kojim bismo usporedili 10 je prazan, pa moramo prvo procijeniti taj čvor prije nego što igrač za minimiziranje može izabrati. Vraćamo se na potez igrača koji maksimizira i uspoređujemo djecu susjednog čvora: 8, -2. Maksimiziranje će izabrati 8 i to zapisujemo u prazan roditeljski čvor. Sada kada je algoritam završio popunjavanje praznih mjesta za podređene čvorove iznad njega, igrač za minimiziranje može uporediti tu djecu - 10 i 8 i izabrati 8. Algoritam zatim ponavlja ovaj postupak dok se cijelo stablo ne ispuni. Na kraju ovog primjera imamo ocjenu 8. To je najviše stanje ploče koje AI 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 mnogo. Ako ste jedan od onih tipova kojima je potrebno da neko razgovara s vama da bi nešto razumio, evo nekoliko video zapisa koje sam pogledao kako bih 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) sa wikipedije:

funkcija minimaksa (čvor, dubina, maximizingPlayer) je

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

vraća heurističku vrijednost čvora

ako maximizingPlayer onda

vrijednost: = −∞

za svako dijete čvora

vrijednost: = max (vrijednost, minimaks (dijete, dubina - 1, FALSE))

povratna vrednost

else (* minimiziranje igrača *)

vrijednost: = +∞

za svako dijete čvora

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

povratna vrednost

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 je mjesto na kojem želite da program započne pretraživanje. 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 gdje postoje tisuće, ako ne i milijuni konfiguracija ploče, vaš laptop kod kuće neće moći obraditi sve te konfiguracije. Dakle, ograničavamo dubinu pretraživanja AI -a i stavljamo ga 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: Napravite svoju AI sa Ai_template.py

Prije nego što pogledate moj Minimax AI kôd, pokušajte napraviti vlastitu 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.

Kada dobijete svoju AI, pokušajte je pokrenuti, randy_ai.py. Da biste pokrenuli dva aisa jedan protiv drugog, upišite "python othello_gui.py (umetnite naziv ai datoteke).py (umetnite naziv datoteke).py" u mac terminal ili upišite "pokrenite othello_gui.py (umetnite ime datoteke ai).py (umetnite naziv datoteke).py "i provjerite jeste li u pravom direktoriju. Također pogledajte moj video za tačne korake.

Korak 8: Vrijeme je da se AI borite

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