Umetna inteligenca družabnih iger: minimalni algoritem: 8 korakov

2024 Avtor: John Day | [email protected]. Nazadnje spremenjeno: 2024-01-30 12:04

Ste se kdaj vprašali, kako so narejeni računalniki, s katerimi igrate v šahu ali dahu? No, ne glejte dlje od tega navodila, saj vam bo pokazalo, kako narediti preprosto, a učinkovito umetno inteligenco (AI) z algoritmom minimaksa! Z uporabo algoritma minimaksa AI naredi dobro načrtovane in premišljene poteze (ali vsaj posnema miselni proces). Zdaj bi vam lahko dal samo kodo za umetno inteligenco, ki sem jo naredil, vendar to ne bi bilo zabavno. Razložil bom logiko izbire računalnika.

V tem navodilu vas bom popeljal skozi korake, kako narediti AI za Othello (AKA Reversi) v pythonu. Preden se lotite tega projekta, bi morali imeti vmesno razumevanje, kako kodirati v pythonu. Tukaj je nekaj dobrih spletnih mest, ki vas lahko pripravijo na ta Instructable: w3schools ali learnpython. Na koncu tega navodila bi morali imeti AI, ki bo naredila izračunane poteze in bi morala premagati večino ljudi.

Ker se bo ta Instructable ukvarjal predvsem s tem, kako narediti AI, ne bom razlagal, kako oblikovati igro v pythonu. Namesto tega bom dal kodo za igro, v kateri se lahko človek igra proti drugemu človeku in jo spremeni tako, da lahko igrate igro, kjer se človek igra proti AI.

Naučil sem se ustvariti to AI s poletnim programom v Columbia SHAPE. Tam sem se imel lepo, zato poglej na njihovo spletno stran, če te zanima.

Zdaj, ko smo odstranili logistiko, začnimo s kodiranjem!

(V slike sem dal nekaj zapiskov, zato jih poglejte)

Zaloge

To je enostavno:

1) Računalnik z okoljem python, kot sta Spyder ali IDLE

2) Prenesite datoteke za igro Othello z mojega GitHub -a

3) Vaši možgani s potrpežljivostjo

1. korak: Prenesite potrebne datoteke

Ko greste v moj GitHub, bi morali videti 5 datotek. Prenesite vseh 5 in jih postavite v isto mapo. Preden zaženete igro, odprite vse datoteke v okolju spyder.

Takole delajo datoteke:

1) othello_gui.py ta datoteka ustvari igralno ploščo, na kateri se bodo igralci igrali (človeški ali računalniški)

2) othello_game.py ta datoteka predvaja dva računalnika drug proti drugemu brez igralne plošče in prikazuje le rezultat in premikanje položajev

3) ai_template.py tukaj boste vnesli vso kodo za izdelavo svoje AI

4) randy_ai.py to je že pripravljena AI, ki svoje poteze izbira naključno

5) othello_shared.py kup vnaprej pripravljenih funkcij, s katerimi lahko naredite svojo umetno inteligenco, na primer za preverjanje razpoložljivih potez, rezultatov ali stanja plošče

6) Tri druge datoteke: Puma.py, erika_5.py in nathan.py, ki sem jih naredil jaz, Erika in Nathan iz programa SHAPE, to so tri različne AI z edinstvenimi kodami

2. korak: Kako odpreti in igrati Python Othello

Ko imate odprte vse datoteke, v spodnji desni kot zaslona vnesite "run othello_gui.py" in pritisnite enter v konzoli IPython. Ali pa v terminalu Mac vnesite "python othello_gui.py" (potem ko ste seveda v pravi mapi). Nato bi se morala na vašem zaslonu pojaviti deska. Ta način je način človek proti človeku. Svetloba gre na drugo mesto in najprej na temno. Če ste zmedeni, poglejte moj video. iNa vrhu je ocena vsake barvne ploščice. Če želite igrati, kliknite veljaven prostor za premikanje, da postavite ploščico, nato pa računalnik podarite nasprotniku, ki bo storil enako in ponovil.

Če ne veste, kako igrati Othello, preberite ta pravila na spletnem mestu ultra deske:

Črna se vedno premakne prva. Premik se izvede tako, da se plošča igralčeve barve postavi na tablo tako, da "zaobide" enega ali več nasprotnikovih diskov. Disk ali vrsta diskov je obrobljena, če je na koncih obdana z diski nasprotne barve. Disk lahko preseže poljubno število diskov v eni ali več vrsticah v kateri koli smeri (vodoravno, navpično, diagonalno)…. (dokončajte branje na njihovi spletni strani)

Razlika med prvotno igro in to igro Python je v tem, da se igra konča, ko za enega igralca ni veljavnih potez

Zdaj, ko se lahko igrate s prijateljem, naredimo AI, s katerim se lahko igrate.

3. korak: Minimaksni algoritem: ustvarjanje scenarijev

Preden govorimo o tem, kako to zapisati v kodo, pojdimo na logiko, ki stoji za tem. Algoritem minimaksa je algoritem za odločanje in sledenje nazaj in se običajno uporablja v poteznih igrah za dva igralca. Cilj te AI je najti naslednjo najboljšo potezo in naslednje najboljše poteze, dokler ne zmaga v igri.

Kako bi torej algoritem določil, katera poteza je najboljša? Ustavite se in razmislite, kako bi izbrali naslednjo potezo. Večina ljudi bi izbrala potezo, ki bi jim prinesla največ točk, kajne? Ali če bi razmišljali vnaprej, bi se odločili za potezo, ki bi ustvarila situacijo, ko bi lahko pridobili še več točk. Slednji način razmišljanja je način razmišljanja algoritma Minimax. Pričakuje vse prihodnje nastavitve odbora in naredi korak, ki bi pripeljal do največ točk.

To sem poimenoval algoritem za sledenje nazaj, ker se začne tako, da najprej ustvari in oceni vsa bodoča stanja plošče z njihovimi povezanimi vrednostmi. To pomeni, da bo algoritem igral igro toliko, kolikor je potrebno (poteze zase in za nasprotnika), dokler se ne odigra vsak scenarij igre. Za spremljanje vseh stanj plošče (scenarijev) lahko narišemo drevo (poglejte na slikah). Drevo na zgornji sliki je preprost primer igre Connect 4. Vsaka konfiguracija plošče se imenuje stanje plošče, njeno mesto na drevesu pa vozlišče. Vsa vozlišča na dnu drevesa so končna stanja plošče po vseh potezah. Očitno so nekatere države sveta boljše za enega igralca kot drugega. Zdaj moramo AI izbrati, do katerega stanja odbora želi priti.

4. korak: Minimax: Ocenjevanje konfiguracij plošč

Da bi državam dali vrednost, se moramo naučiti strategij igre, ki jo igramo: v tem primeru strategije Othella. Ker je ta igra bitka pri obračanju nasprotnika in vaših diskov, so najboljši položaji diskov tisti, ki so stabilni in jih ni mogoče prevrniti. Kotiček je na primer kraj, kjer diska ni mogoče spremeniti v drugo barvo. Tako bi bilo to mesto izredno dragoceno. Drugi dobri položaji vključujejo stranice deske, ki vam omogočajo, da vzamete veliko kamenja. Na tem spletnem mestu je več strategij.

Zdaj lahko dodelimo vrednosti položajem za vsak državni odbor odbora. Ko položaj AI zaseda del AI, mu daste določeno število točk, odvisno od položaja. Na primer, na tabli, kjer je del AI v kotu, lahko daste bonus 50 točk, če pa bi bil na neugodnem mestu, ima lahko kos vrednost 0. Po upoštevanju vseh vrednosti položajem dodelite vrednosti stanja plošče. Na primer, če ima AI kotiček v kotu, ima lahko stanje plošče 50 točk, drugo stanje plošče z umetniškim delom na sredini pa 10.

Obstaja veliko načinov za to in imam tri različne hevristike za oceno kosov plošče. Spodbujam vas, da naredite svojo vrsto hevristike. Tri različne izdelovalce sem v svoj github naložil tri različne AI, s tremi različnimi hevristikami: Puma.py, erika5.py, nathanh.py.

5. korak: Minimaksni algoritem: Izbira najboljšega premika

Zdaj bi bilo lepo, če bi AI lahko samo izbrala vse poteze, da bi prišla do stanja na deski z najvišjo oceno. Vendar ne pozabite, da je AI prav tako izbiral poteze za nasprotnika, ko je ustvarjal vsa stanja na deski, in če je nasprotnik pameten, AI ne bo omogočil, da bi dosegel najvišji rezultat na deski. Namesto tega bi pametni nasprotnik naredil korak, da bi AI šel v najnižje stanje. V algoritmu dva igralca imenujemo maksimirajoči in minimizirajoči. AI bi bil največji igralec, saj želi zase pridobiti največ točk. Nasprotnik bi bil najmanjši igralec, saj poskuša premakniti, kjer AI pridobi najmanj točk.

Ko so vsa stanja plošče ustvarjena in so plošče dodeljene vrednosti, algoritem začne primerjati stanja plošč. Na slikah sem ustvaril drevo, ki predstavlja, kako bo algoritem izbral svoje poteze. Vsak razcep v vejah je drugačna poteza, ki jo lahko igra AI ali nasprotnik. Levo od vrstic vozlišč sem napisal, ali gre za povečanje ali zmanjšanje igralca. Spodnja vrstica je vse stanje plošče z njihovimi vrednostmi. Znotraj vsakega od teh vozlišč je število in to so ocene, ki jih dodelimo vsaki plošči: višje so, bolje je, da jih ima AI.

Definicije: nadrejeno vozlišče - vozlišče, ki pod njim ustvari ali ustvari vozlišča; izvor podrejenih vozlišč - vozlišč, ki prihajajo iz istega nadrejenega vozlišča

Prazna vozlišča predstavljajo premik, ki ga bo AI naredil, da pride do najboljšega stanja plošče. Začne se s primerjavo podrejencev skrajnega levega vozlišča: 10, -3, 5. Ker bi igralec z največjo močjo naredil potezo, bi izbral potezo, ki bi ji dala največ točk: 10. Torej, nato izberemo in shranimo to premaknite se z rezultatom plošče in ga zapišite v nadrejeno vozlišče. Zdaj, ko je 10 v nadrejenem vozlišču, so na vrsti minimizirajoči igralci. Vendar je vozlišče, s katerim bi primerjali 10, prazno, zato moramo to vozlišče najprej oceniti, preden se lahko igralec za zmanjševanje vrednosti odloči. Zato se vrnemo k maksimiranju igralčevega obrata in primerjamo otroke sosednjega vozlišča: 8, -2. Če povečate, boste izbrali 8 in to zapišemo v prazno nadrejeno vozlišče. Zdaj, ko je algoritem dokončal zapolnjevanje praznih mest za podrejene vozlišča nad njim, lahko minimizirajoči igralec primerja te otroke - 10 in 8 in izbere 8. Algoritem nato ponovi ta postopek, dokler ni zapolnjeno celotno drevo. Na koncu tega primera imamo rezultat 8. To je najvišje stanje na deski, ki ga lahko igra AI, če domnevamo, da nasprotnik igra optimalno. Tako bo AI izbral prvi korak, ki vodi v stanje 8 plošče, in če nasprotnik igra optimalno, bi moral AI odigrati vse poteze, da bi prišel v stanje 8. (Sledite opombam na mojih slikah)

Vem, da je bilo to veliko. Če ste eden tistih, ki potrebujejo, da se nekdo pogovarja z vami, da bi kaj razumel, je tukaj nekaj videoposnetkov, ki sem si jih ogledal, da bi razumeli idejo, ki stoji za tem: 1, 2, 3.

6. korak: Minimaksni algoritem: psevdokoda

Ko razumete logiko algoritma minimax, si oglejte to psevdokodo (funkcije, ki so univerzalne za vse kode) iz wikipedije:

funkcija minimaksa (vozlišče, globina, maksimiziranjePlayer) je

če je globina = 0 ali je vozlišče končno vozlišče, potem

vrne hevristično vrednost vozlišča

če maximizingPlayer potem

vrednost: = −∞

za vsakega otroka vozlišča naredi

vrednost: = max (vrednost, minimaks (podrejen, globina - 1, FALSE))

vrnjena vrednost

else (* minimiziranje igralca *)

vrednost: = +∞

za vsakega otroka vozlišča naredi

vrednost: = min (vrednost, minimaks (podrejen, globina - 1, TRUE))

vrnjena vrednost

To je rekurzivna funkcija, kar pomeni, da se kliče vedno znova, dokler ne doseže točke ustavitve. Najprej funkcija vzame tri vrednosti: vozlišče, globino in na vrsti. Vrednost vozlišča je kraj, kjer želite, da program začne iskati. Globina je, kako daleč želite, da program išče. V mojem primeru drevesa ima na primer globino 3, ker je po treh potezah preiskal vsa stanja plošče. Seveda bi radi, da AI preveri vsako stanje plošče in izbere zmagovalno zmago, vendar v večini iger, kjer je na tisoče, če ne celo milijon konfiguracij plošč, vaš prenosnik doma ne bo mogel obdelati vseh teh konfiguracij. Tako omejujemo globino iskanja AI in jo postavimo v najboljše stanje plošče.

Ta psevdokoda reproducira postopek, ki sem ga razložil v prejšnjih dveh korakih. Zdaj pa naredimo korak dlje in to popravimo v kodi python.

7. korak: Ustvarite svojo umetno inteligenco z Ai_template.py

Preden si ogledate mojo kodo Minimax AI, poskusite narediti svojo AI z datoteko ai_template.py in psevdokodo, o kateri smo govorili v zadnjem koraku. V predlogi ai sta dve funkciji, imenovani def minimax_min_node (plošča, barva) in def minimax_max_node (plošča, barva). Namesto da bi se funkcija minimaksa klicala rekurzivno, imamo dve različni funkciji, ki se kličeta. Če želite ustvariti hevristiko za oceno stanja plošče, boste morali ustvariti svojo lastno funkcijo. V datoteki othello_shared.py so vnaprej pripravljene funkcije, ki jih lahko uporabite za izdelavo svoje AI.

Ko imate AI, ga poskusite zagnati, randy_ai.py. Če želite izvesti dva aisa drug proti drugemu, vnesite "python othello_gui.py (vstavite ime datoteke ai).py (vnesite ime datoteke).py" v terminal Mac ali vnesite "zaženi othello_gui.py (vstavite ime datoteke ai).py (vnesite ime datoteke).py "in se prepričajte, da ste v pravem imeniku. Za natančne korake si oglejte tudi moj video.

8. korak: Čas je, da se borite z AI

Sedaj si priskrbite kup računalniških prijateljev in jih pripravite, naj oblikujejo svojo umetno inteligenco! Potem lahko naredite tekmovanje in izgovorite svojega AI. Upajmo, da tudi če niste mogli zgraditi lastne AI, ste razumeli, kako deluje algoritem minimaksa. Če imate kakršna koli vprašanja, jih lahko v spodnjih komentarjih objavite.