Lojë me Borde Inteligjenca Artificiale: Algoritmi Minimax: 8 Hapa

2024 Autor: John Day | [email protected]. E modifikuara e fundit: 2024-01-30 12:18

A keni menduar ndonjëherë se si bëhen kompjuterët kundër të cilëve luani në shah apo damë? Pra, mos shikoni më tej se ky Instructable sepse do t'ju tregojë se si të bëni një inteligjencë artificiale të thjeshtë por efektive (AI) duke përdorur Algoritmin Minimax! Duke përdorur Algoritmin Minimax, AI bën lëvizje të planifikuara dhe të menduara mirë (ose të paktën imiton një proces mendimi). Tani, unë thjesht mund t'ju jap kodin për AI që kam bërë, por kjo nuk do të ishte argëtuese. Unë do të shpjegoj logjikën prapa zgjedhjeve të kompjuterit.

Në këtë Udhëzues, unë do t'ju tregoj hapat se si të bëni një UA për Othello (AKA Reversi) në python. Ju duhet të keni një kuptim të ndërmjetëm se si të kodoni në python para se të merreni me këtë projekt. Këtu janë disa faqe interneti të mira për t'u parë për t'ju përgatitur për këtë Udhëzues: w3schools ose learnpython. Në fund të këtij Udhëzuesi, duhet të keni një AI që do të bëjë lëvizje të llogaritura dhe duhet të jetë në gjendje të mposhtë shumicën e njerëzve.

Meqenëse ky Instructable do të merret kryesisht me mënyrën e krijimit të një AI, unë nuk do të shpjegoj se si të krijoj një lojë në python. Në vend të kësaj, unë do të jap kodin për lojën ku një person mund të luajë kundër një personi tjetër dhe ta modifikojë atë në mënyrë që ju të luani një lojë ku një njeri luan kundër AI.

Mësova se si ta krijoj këtë UA përmes një programi veror në Columbia SHAPE. Kalova mirë atje, kështu që hidhini një sy faqes së tyre të internetit për të parë nëse do të interesoheshit.

Tani që dolëm jashtë logjistikës, le të fillojmë kodimin!

(Unë vendos disa shënime në imazhe, kështu që sigurohuni t'i shikoni ato)

Furnizimet

Kjo është e lehtë:

1) Kompjuter me një mjedis python siç është Spyder ose IDLE

2) Shkarkoni skedarët për lojën Othello nga GitHub im

3) Truri juaj me durim të instaluar

Hapi 1: Shkarkoni skedarët e nevojshëm

Kur hyni në GitHub tim, duhet të shihni 5 skedarë. Shkarkoni të 5 dhe vendosini të gjithë në të njëjtën dosje. Para se të fillojmë lojën, hapim të gjithë skedarët në mjedisin spyder.

Këtu është ajo që bëjnë skedarët:

1) othello_gui.py ky skedar krijon tabelën e lojës për lojtarët për të luajtur (qofshin ato njerëzore apo kompjuterike)

2) othello_game.py ky skedar luan dy kompjuterë kundër njëri -tjetrit pa tabelën e lojërave dhe tregon vetëm pozicionet e rezultatit dhe lëvizjes

3) ai_template.py këtu do të vendosni të gjithë kodin tuaj për të bërë AI -në tuaj

4) randy_ai.py kjo është një UA e paracaktuar që zgjedh lëvizjet e saj rastësisht

5) othello_shared.py një sërë funksionesh të paracaktuara që mund t'i përdorni për të bërë AI-në tuaj si për të kontrolluar lëvizjet në dispozicion, rezultatin ose gjendjen e tabelës

6) Tre skedarët e tjerë: Puma.py, erika_5.py, dhe nathan.py, të bëra nga unë, Erika dhe Nathan respektivisht nga programi SHAPE, këto janë tre UA të ndryshme me kode unike

Hapi 2: Si të Hapni dhe Luani Python Othello

Pasi të keni hapur të gjithë skedarët, në këndin e poshtëm të djathtë të ekranit, shtypni "drejto othello_gui.py" dhe shtypni enter në IPython Console. Ose në terminalin Mac, shkruani "python othello_gui.py" (pasi të jeni në dosjen e duhur natyrisht). Pastaj një tabelë duhet të shfaqet në ekranin tuaj. Kjo mënyrë është mënyra njerëzore kundrejt njeriut. Drita shkon e dyta dhe errësira e para. Shikoni videon time nëse jeni të hutuar. në krye, ekziston rezultati i secilës pllakë me ngjyra. Për të luajtur, klikoni në një hapësirë lëvizëse të vlefshme për të vendosur një pllakë atje dhe pastaj jepni kompjuterin kundërshtarit tuaj i cili do të bëjë të njëjtën gjë dhe do të përsërisë.

Nëse nuk dini si të luani Othello, lexoni këto rregulla nga faqja e internetit e bordeve ultra:

E zeza lëviz gjithmonë e para. Një lëvizje bëhet duke vendosur një disk me ngjyrën e lojtarit në tabelë në një pozicion që "del jashtë" një ose më shumë disqeve të kundërshtarit. Një disk ose rresht i disqeve tejkalohet kur rrethohet në skajet nga disqe të ngjyrës së kundërt. Një disk mund të tejkalojë çdo numër disku në një ose më shumë rreshta në çdo drejtim (horizontale, vertikale, diagonale)…. (përfundoni leximin në faqen e tyre të internetit)

Dallimi midis lojës origjinale dhe kësaj loje python është se kur nuk kanë mbetur lëvizje të vlefshme për një lojtar, loja përfundon

Tani që mund të luani lojën me një mik, le të bëjmë një AI me të cilën mund të luani.

Hapi 3: Algoritmi Minimax: Gjenerimi i skenarëve

Para se të flasim se si ta shkruajmë këtë në kod, le të kalojmë mbi logjikën që qëndron pas tij. Algoritmi minimalax është një algoritëm i vendimmarrjes, i ndjekjes së prapme dhe përdoret zakonisht në lojëra me dy lojtarë, të bazuar në kthesa. Qëllimi i këtij AI është të gjejë lëvizjen tjetër më të mirë dhe lëvizjet më të mira në vijim derisa të fitojë lojën.

Tani si do të përcaktonte algoritmi se cila lëvizje është lëvizja më e mirë? Ndaloni dhe mendoni se si do të zgjidhni lëvizjen tjetër. Shumica e njerëzve do të zgjidhnin lëvizjen që do t'u jepte më shumë pikë, apo jo? Ose nëse do të mendonin përpara, ata do të zgjidhnin lëvizjen e cila do të krijonte një situatë ku ata mund të fitonin edhe më shumë pikë. Mënyra e fundit e të menduarit është mënyra sesi mendon Algoritmi Minimax. Ai shikon përpara të gjitha konfigurimet e bordit të ardhshëm dhe bën lëvizjen që do të çonte në më shumë pikë.

Unë e quaj këtë një algoritëm të kthimit mbrapa, sepse fillon duke krijuar dhe vlerësuar së pari të gjitha shtetet e ardhshme të bordit me vlerat e tyre të lidhura. Kjo do të thotë që algoritmi do ta luajë lojën aq sa i duhet (duke bërë lëvizje për veten dhe kundërshtarin) derisa të ketë luajtur çdo skenar i lojës. Për të mbajtur nën kontroll të gjitha gjendjet e tabelës (skenarët), ne mund të vizatojmë një pemë (shikoni figurat). Pema në figurën e mësipërme është një shembull i thjeshtë i një loje të Connect 4. Çdo konfigurim i tabelës quhet një gjendje bordi dhe vendi i saj në pemë quhet një nyje. Të gjitha nyjet në fund të pemës janë gjendjet përfundimtare të tabelës pasi të keni bërë të gjitha lëvizjet. Shtë e qartë se disa shtete të bordit janë më të mira për njërin lojtar sesa tjetrin. Pra, tani duhet të bëjmë që AI të zgjedhë se në cilin shtet të bordit dëshiron të arrijë.

Hapi 4: Minimax: Vlerësimi i Konfigurimeve të Bordit

Për t'i dhënë vlera shteteve të bordit, ne duhet të mësojmë strategjitë e lojës që po luajmë: në këtë rast, strategjitë e Othello. Për shkak se kjo lojë është një betejë e kthimit të disqeve të kundërshtarit dhe tuaj, pozicionet më të mira të diskut janë ato që janë të qëndrueshme dhe nuk mund të përmbysen. Këndi, për shembull, është vendi ku kur vendoset një disk nuk mund të ndryshohet në ngjyrën tjetër. Kështu, ai vend do të ishte jashtëzakonisht i vlefshëm. Pozicione të tjera të mira përfshijnë anët e tabelës që do t'ju lejojnë të merrni shumë gurë. Ka më shumë strategji në këtë faqe interneti.

Tani ne mund t'i caktojmë vlerat pozicioneve për secilin bord shtetëror të bordit. Kur një pozicion është i zënë nga pjesa e AI, atëherë ju jepni një numër të caktuar pikësh në varësi të pozicionit. Për shembull, një tabelë ku pjesa e AI është në qoshe, mund të jepni një bonus prej 50 pikësh, por nëse do të ishte në një vend të pafavorshëm, pjesa mund të ketë një vlerë 0. Pasi të keni marrë parasysh të gjitha vlerat e pozicionet, ju i caktoni gjendjes së bordit një vlerë. Për shembull, nëse AI ka një pjesë në qoshe, gjendja e tabelës mund të ketë një rezultat prej 50 ndërsa një gjendje tjetër e bordit me pjesën e AI në mes ka një rezultat 10.

Ka shumë mënyra për ta bërë këtë, dhe unë kam tre heuristikë të ndryshëm për të vlerësuar pjesët e tabelës. Unë ju inkurajoj që të bëni llojin tuaj heuristik. Kam ngarkuar tre AI të ndryshëm në githubin tim nga tre krijues të ndryshëm, me tre heuristika të ndryshme: Puma.py, erika5.py, nathanh.py.

Hapi 5: Algoritmi Minimax: Zgjedhja e Lëvizjes më të Mirë

Tani do të ishte mirë nëse AI mund të zgjidhte të gjitha lëvizjet për të arritur në gjendjen e tabelës me rezultatin më të lartë. Por mbani mend se AI po zgjidhte lëvizjet për kundërshtarin kur gjeneronte të gjitha gjendjet e bordit dhe nëse kundërshtari është i zgjuar, nuk do të lejojë që AI të arrijë në rezultatin më të lartë të tabelës. Në vend të kësaj, një kundërshtar i zgjuar do të bënte lëvizjen për ta bërë AI të shkojë në gjendjen më të ulët të bordit. Në algoritëm, ne i quajmë dy lojtarë një lojtar maksimal dhe një lojtar minimizues. AI do të ishte lojtari maksimal pasi dëshiron të marrë më shumë pikë për vete. Kundërshtari do të ishte lojtari që minimizon pasi kundërshtari po përpiqet të bëjë lëvizjen aty ku AI merr më pak pikë.

Pasi të krijohen të gjitha gjendjet e bordit dhe vlerat u janë caktuar bordeve, algoritmi fillon të krahasojë gjendjet e bordit. Në fotografi, unë krijova një pemë për të përfaqësuar sesi algoritmi do të zgjidhte lëvizjet e tij. Çdo ndarje në degë është një lëvizje e ndryshme që AI ose kundërshtari mund të luajë. Në të majtë të rreshtave të nyjeve, unë shkrova nëse lojtari i maksimizimit ose minimizimit po shkon. Rreshti i poshtëm është të gjitha shtetet e bordit me vlerat e tyre. Brenda secilës prej atyre nyjeve është një numër dhe ato janë pikët që i caktojmë secilës prej tabelave: sa më të larta të jenë, aq më mirë është që UA të ketë.

Përkufizimet: nyja mëmë - një nyje që rezulton ose krijon nyje nën të; origjina e nyjeve të fëmijëve - nyjet që vijnë nga e njëjta nyje mëmë

Nyjet e zbrazëta përfaqësojnë lëvizjen e AI -së për të arritur në gjendjen më të mirë të tabelës. Fillon me krahasimin e fëmijëve të nyjës më të majtë: 10, -3, 5. Meqenëse lojtari maksimal do të bënte lëvizjen, ai do të zgjidhte lëvizjen që do t'i jepte më shumë pikë: 10. Pra, ne pastaj e përzgjedhim dhe ruajmë atë lëviz me rezultatin e tabelës dhe shkruajeni në nyjen mëmë. Tani që 10 është në nyjen mëmë, tani është radha e minimizimit të lojtarëve. Sidoqoftë, nyja me të cilën do të krahasojmë 10 është bosh, kështu që ne duhet ta vlerësojmë atë nyje para se lojtari që minimizon të zgjedhë. Pra, kthehemi te radha e lojtarit maksimal dhe krahasojmë fëmijët e nyjës ngjitur: 8, -2. Maksimizimi do të zgjedhë 8 dhe ne e shkruajmë atë në nyjen bosh të prindit. Tani që algoritmi ka përfunduar mbushjen e hapësirave boshe për fëmijët e një nyje mbi të, lojtari që minimizon mund t'i krahasojë ata fëmijë - 10 dhe 8 dhe të zgjedhë 8. Algoritmi pastaj e përsërit këtë proces derisa të mbushet e gjithë pema. Në fund të këtij shembulli, ne kemi rezultatin 8. Kjo është gjendja më e lartë e bordit që AI mund të luajë për të supozuar se kundërshtari po luan në mënyrë optimale. Pra, AI do të zgjedhë lëvizjen e parë që të çon në gjendjen e tabelave 8, dhe nëse kundërshtari luan në mënyrë optimale, AI duhet të luajë të gjitha lëvizjet për të arritur në gjendjen e bordit 8. (Ndiqni shënimet në fotografitë e mia)

E di që ishte shumë. Nëse jeni një nga ata lloje që duhet të keni dikë që të flasë me ju për të kuptuar diçka, këtu janë disa video që kam parë për të më ndihmuar të kuptoj idenë pas kësaj: 1, 2, 3.

Hapi 6: Algoritmi Minimax: Pseudokod

Pasi të keni kuptuar logjikën prapa algoritmit minimalax, hidhini një sy këtij pseudokodi (funksionet që janë universale për të gjitha kodet) nga wikipedia:

funksioni minimaks (nyja, thellësia, maksimizimi i Lojtarit) është

nëse thellësia = 0 ose nyja është një nyje përfundimtare atëherë

kthejnë vlerën heuristike të nyjës

nëse maximizingPlayer atëherë

vlera: =

për secilin fëmijë të nyjës bëni

vlera: = max (vlera, minimumi (fëmija, thellësia - 1, FALSE))

vlera e kthimit

tjetër (* minimizimi i lojtarit *)

vlera: = +∞

për secilin fëmijë të nyjës bëni

vlera: = min (vlera, minimumi (fëmija, thellësia - 1, E VUERTET))

vlera e kthimit

Ky është një funksion rekursiv, që do të thotë se e thërret veten pa pushim derisa të arrijë një pikë ndalimi. Së pari, funksioni merr tre vlera, nyjen, thellësinë, dhe radha e së cilës është. Vlera e nyjes është vendi ku dëshironi që programi të fillojë kërkimin. Thellësia është sa larg dëshironi që programi të kërkojë. Për shembull, në shembullin tim të pemës ka një thellësi prej 3, sepse kërkoi të gjitha gjendjet e tabelës pas 3 lëvizjes. Sigurisht, ne do të donim që AI të kontrollonte çdo gjendje bordi dhe të zgjidhte një fitore fituese, por në shumicën e lojërave ku ka mijëra, nëse jo miliona konfigurime të bordit, laptopi juaj në shtëpi nuk do të jetë në gjendje të përpunojë të gjitha ato konfigurime. Pra, ne kufizojmë thellësinë e kërkimit të AI dhe e bëjmë atë të shkojë në gjendjen më të mirë të bordit.

Ky pseudokod po riprodhon procesin që shpjegova në dy hapat e mëparshëm. Tani le ta bëjmë këtë një hap më tej dhe ta drejtojmë këtë në kodin python.

Hapi 7: Marrja e AI -së tuaj me Ai_template.py

Para se të hidhni një sy në kodin tim Minimax AI, bëni një përpjekje për të provuar të krijoni AI tuaj me skedarin ai_template.py dhe pseudokodin për të cilin folëm në hapin e fundit. Ekzistojnë dy funksione në shabllonin ai të quajtur: def minimax_min_node (bordi, ngjyra) dhe def minimax_max_node (bordi, ngjyra). Në vend që funksioni minimalax të thirret në mënyrë rekursive, ne kemi dy funksione të ndryshme, të cilat thërrasin njëra -tjetrën. Për të krijuar heuristikën për të vlerësuar gjendjet e bordit, do të duhet të krijoni funksionin tuaj. Ekziston një funksion i paravendosur në skedarin othello_shared.py që mund të përdorni për të ndërtuar AI -në tuaj.

Pasi të keni AI -në tuaj, provoni ta kundërshtoni atë, randy_ai.py. Për të drejtuar dy ais kundër njëri -tjetrit, shkruani "python othello_gui.py (futni emrin e skedarit ai).py (futni emrin e skedarit).py" në terminalin mac ose shkruani "run othello_gui.py (futni emrin e skedarit ai).py (futni emrin e skedarit).py "dhe sigurohuni që jeni në drejtorinë e duhur. Gjithashtu, shikoni videon time për hapat e saktë.

Hapi 8: Koha për të bërë luftë me AI

Tani merrni një mori shokësh të kompjuterit tuaj dhe bëni që ata të krijojnë AI -në e tyre! Atëherë mund të bëni një konkurs dhe ta nxirrni AI -në tuaj. Shpresojmë, edhe nëse nuk mund të ndërtoni AI -në tuaj, keni qenë në gjendje të kuptoni se si funksionon algoritmi minimalax. Nëse keni ndonjë pyetje, mos ngurroni të postoni ndonjë pyetje në komentet më poshtë.