Umelá inteligencia doskovej hry: Minimax algoritmus: 8 krokov

2024 Autor: John Day | [email protected]. Naposledy zmenené: 2024-01-30 11:58

Zaujímalo vás niekedy, ako sú vyrobené počítače, proti ktorým hráte v šachu alebo v dámach? Nehľadajte nič iné, než tento návod, pretože vám ukáže, ako vytvoriť jednoduchú, ale efektívnu umelú inteligenciu (AI) pomocou algoritmu Minimax! Pomocou algoritmu Minimax AI robí dobre naplánované a premyslené pohyby (alebo aspoň napodobňuje myšlienkový proces). Teraz by som vám mohol dať kód pre AI, ktorý som vytvoril, ale to by nebola zábava. Vysvetlím logiku za voľbami počítača.

V tomto návode vás prevediem krokmi, ako vytvoriť AI pre Othello (AKA Reversi) v pythone. Predtým, ako sa pustíte do tohto projektu, mali by ste mať stredne pokročilé znalosti o tom, ako kódovať v pythone. Tu je niekoľko dobrých webových stránok, na ktoré sa môžete pripraviť, aby vás pripravili na tento návod: w3schools alebo learnpython. Na konci tohto pokynu by ste mali mať AI, ktorá bude vykonávať vypočítané pohyby a mala by byť schopná poraziť väčšinu ľudí.

Pretože tento návod sa bude primárne zaoberať tým, ako vytvoriť AI, nebudem vysvetľovať, ako navrhnúť hru v pythone. Namiesto toho poskytnem kód pre hru, kde môže človek hrať proti inému človeku, a upravím ho tak, aby ste mohli hrať hru, kde človek hrá proti AI.

Naučil som sa, ako vytvoriť túto AI, prostredníctvom letného programu v Columbia SHAPE. Mal som sa tam dobre, tak sa pozrite na ich webovú stránku, aby ste zistili, či by vás to zaujímalo.

Teraz, keď sme sa zbavili logistiky, začnime s kódovaním!

(K obrázkom som vložil niekoľko poznámok, takže sa na ne určite pozrite)

Zásoby

Je to ľahké:

1) Počítač s prostredím python, ako je Spyder alebo IDLE

2) Stiahnite si súbory pre hru Othello z môjho GitHubu

3) Váš mozog s nainštalovanou trpezlivosťou

Krok 1: Stiahnite si potrebné súbory

Keď prejdete do môjho GitHubu, mali by ste vidieť 5 súborov. Stiahnite si všetkých 5 a umiestnite ich všetky do rovnakého priečinka. Pred spustením hry otvorte všetky súbory v prostredí spyder.

Súbory robia takto:

1) othello_gui.py tento súbor vytvára herný plán, na ktorom môžu hráči hrať (ľudský alebo počítačový)

2) othello_game.py tento súbor hrá dva počítače proti sebe bez hracieho plánu a zobrazuje iba skóre a presúvanie pozícií

3) ai_template.py to je miesto, kam vložíte všetok svoj kód, aby ste vytvorili svoju AI

4) randy_ai.py toto je vopred pripravená AI, ktorá vyberá svoje pohyby náhodne

5) othello_shared.py veľa vopred pripravených funkcií, ktoré môžete použiť na vytvorenie svojej AI, napríklad na kontrolu dostupných pohybov, skóre alebo stavu dosky

6) Tri ďalšie súbory: Puma.py, erika_5.py a nathan.py, ktoré som vytvoril ja, Erika a Nathan z programu SHAPE, sú to tri rôzne AI s unikátnymi kódmi

Krok 2: Ako otvoriť a hrať Python Othello

Keď máte všetky súbory otvorené, v pravom dolnom rohu obrazovky napíšte „run othello_gui.py“a stlačte kláves Enter v konzole IPython. Alebo v termináli Mac zadajte „python othello_gui.py“(potom, čo ste samozrejme v správnom priečinku). Potom by sa na vašej obrazovke mala objaviť doska. Tento režim je režim medzi ľuďmi a ľuďmi. Svetlo ide druhé a prvé tmavé. Ak ste zmätení, pozrite sa na moje video. iVrchu je skóre každej farebnej dlaždice. Ak chcete hrať, kliknite na platný ťahový priestor, umiestnite tam dlaždicu a potom dajte počítač svojmu súperovi, ktorý urobí to isté a zopakuje to.

Ak neviete, ako hrať Othello, prečítajte si tieto pravidlá na webe ultra boards:

Čierna sa vždy pohybuje ako prvá. Ťah sa vykoná umiestnením disku hráčovej farby na hraciu plochu do polohy, ktorá „obchádza“jeden alebo viac diskov súpera. Disk alebo rad diskov je obšitý, ak je na koncoch obklopený diskami opačnej farby. Disk môže obísť ľubovoľný počet diskov v jednom alebo viacerých radoch v ľubovoľnom smere (horizontálne, vertikálne, diagonálne)…. (dokončite čítanie na ich webových stránkach)

Rozdiel medzi pôvodnou hrou a touto krajinou je ten, že ak pre jedného hráča nezostanú žiadne platné ťahy, hra sa končí

Teraz, keď môžete hrať hru s priateľom, vytvorte si AI, s ktorou sa môžete hrať.

Krok 3: Minimax algoritmus: Generovanie scenárov

Predtým, ako budeme hovoriť o tom, ako to napísať do kódu, prejdeme si logiku. Algoritmus minimax je algoritmus s rozhodovaním a spätným sledovaním a zvyčajne sa používa v ťahových hrách pre dvoch hráčov. Cieľom tejto AI je nájsť ďalší najlepší ťah a nasledujúce najlepšie pohyby, kým nevyhrá.

Ako by potom algoritmus určil, ktorý pohyb je najlepší? Zastavte sa a premýšľajte, ako by ste vybrali ďalší krok. Väčšina ľudí by si vybrala krok, ktorý by im poskytol najviac bodov, však? Alebo ak by mysleli dopredu, zvolili by ťah, ktorý by nastolil situáciu, v ktorej by mohli získať ešte viac bodov. Druhý spôsob myslenia je spôsob, akým uvažuje algoritmus Minimax. Pozerá sa dopredu na všetky budúce nastavenia dosiek a robí krok, ktorý by viedol k čo najväčšiemu počtu bodov.

Nazval som to algoritmus spätného sledovania, pretože začína najskôr vytvorením a vyhodnotením všetkých budúcich stavov dosky s ich priradenými hodnotami. To znamená, že algoritmus bude hrať hru toľko, koľko potrebuje (robí ťahy pre seba a súpera), kým sa nehrá každý scenár hry. Aby sme mali prehľad o všetkých stavoch dosky (scenáre), môžeme nakresliť strom (pozrite sa na obrázky). Strom na obrázku vyššie je jednoduchým príkladom hry Connect 4. Každá konfigurácia dosky sa nazýva stav dosky a jej miesto na strome sa nazýva uzol. Všetky uzly v spodnej časti stromu sú konečnými stavmi dosky po vykonaní všetkých ťahov. Niektoré stavy tabuliek sú pre jedného hráča evidentne lepšie ako pre ostatných. Teraz teda musíme nechať AI, aby sa rozhodla, do ktorého stavu rady sa chce dostať.

Krok 4: Minimax: Vyhodnotenie konfigurácií dosky

Aby sme dali hodnotám rady, musíme sa naučiť stratégie hry, ktorú hráme: v tomto prípade stratégie Othella. Pretože je táto hra bojom o prevrátenie súperových a vašich diskov, najlepšie polohy diskov sú tie, ktoré sú stabilné a nemožno ich prevrátiť. Roh je napríklad miesto, kde pri vložení disku nie je možné zmeniť farbu na inú. Toto miesto by preto bolo veľmi cenné. Medzi ďalšie dobré pozície patria boky dosky, ktoré vám umožnia vziať veľa kameňov. Na tomto webe je viac stratégií.

Teraz môžeme poziciam pre každú dosku štátu priradiť hodnoty. Keď je pozícia obsadená figúrkou AI, dáte určitý počet bodov v závislosti od pozície. Napríklad na doske, kde je figúrka AI v rohu, môžete udeliť bonus 50 bodov, ale ak by bola na nepriaznivom mieste, figúrka môže mať hodnotu 0. Po zohľadnení všetkých hodnôt pozíciám, priradíte stavu dosky hodnotu. Napríklad, ak má AI figúrku v rohu, stav dosky môže mať skóre 50, zatiaľ čo iný stav dosky s figúrkou AI v strede má skóre 10.

Existuje mnoho spôsobov, ako to urobiť, a mám tri rôzne heuristiky na vyhodnotenie dielov dosky. Povzbudzujem vás, aby ste si urobili vlastný typ heuristiky. Do svojho githubu som nahral tri rôzne AI od troch rôznych výrobcov s tromi rôznymi heuristikami: Puma.py, erika5.py, nathanh.py.

Krok 5: Minimax algoritmus: Výber najlepšieho ťahu

Teraz by bolo pekné, keby si AI mohla vybrať všetky pohyby a dostať sa do stavu rady s najvyšším skóre. Nezabudnite však, že AI vyberala aj ťahy pre súpera, keď generovala všetky stavy rady, a ak je súper múdry, nedovolí AI, aby sa dostala k najvyššiemu skóre na palube. Namiesto toho by inteligentný protivník urobil krok, aby sa AI dostala do najnižšieho stavu rady. V algoritme nazývame dvoch hráčov maximalizujúcim hráčom a minimalizujúcim hráčom. AI by bola maximalizujúcim hráčom, pretože chce pre seba získať čo najviac bodov. Súper by bol minimalizujúci hráč, pretože sa pokúša urobiť ťah, v ktorom AI získa najmenej bodov.

Akonáhle sú generované všetky stavy dosiek a sú im priradené hodnoty, algoritmus začne porovnávať stavy dosiek. Na obrázkoch som vytvoril strom, ktorý predstavuje, ako algoritmus vyberie svoje pohyby. Každé rozdelenie vo vetvách je iný ťah, ktorý môže hrať AI alebo súper. Vľavo od riadkov uzlov som napísal, či ide maximalizujúci alebo minimalizujúci hráč. V dolnom riadku sú všetky stavy tabule s ich hodnotami. Vnútri každého z týchto uzlov je číslo a to sú skóre, ktoré priraďujeme každému z dosiek: čím vyššie sú, tým lepšie to AI má.

Definície: nadradený uzol - uzol, ktorý vytvára alebo vytvára uzly pod ním; pôvod podradených uzlov - uzly, ktoré pochádzajú z rovnakého nadradeného uzla

Prázdne uzly predstavujú, ktoré pohyby urobí AI, aby sa dostali do najlepšieho stavu dosky. Začína sa to porovnávaním potomkov krajného uzla: 10, -3, 5. Pretože maximalizujúci hráč urobí ťah, zvolí ťah, ktorý mu poskytne najviac bodov: 10. Potom ho vyberieme a uložíme pohnite so skóre tabule a napíšte ho do nadradeného uzla. Teraz, keď je 10 v rodičovskom uzle, teraz je rad na minimalizujúcich hráčoch. Uzol, ku ktorému by sme prirovnali 10, je však prázdny, takže ho musíme najskôr vyhodnotiť, než si môže minimalizujúci hráč vybrať. Vrátime sa teda k maximalizácii ťahu hráča a porovnáme deti susedného uzla: 8, -2. Maximalizácia vyberie 8 a napíšeme to do prázdneho nadradeného uzla. Teraz, keď algoritmus dokončil vypĺňanie prázdnych miest pre deti uzla nad ním, hráč na minimalizácii môže porovnať tieto deti - 10 a 8 a zvoliť 8. Algoritmus potom opakuje tento proces, kým nie je vyplnený celý strom. Na konci tohto príkladu máme skóre 8. To je najvyšší stav dosky, ktorý môže AI hrať, za predpokladu, že súper hrá optimálne. AI teda vyberie prvý ťah, ktorý vedie do stavu 8 boardov, a ak súper hrá optimálne, AI by mal hrať všetky ťahy, aby sa dostal do stavu 8 na boarde (riaďte sa poznámkami na mojich obrázkoch)

Viem, že to bolo veľa. Ak patríte k tým typom, ktoré s vami potrebujú hovoriť, aby vám niečo rozumeli, tu je niekoľko videí, ktoré som sledoval, aby mi pomohli pochopiť myšlienku tohto: 1, 2, 3.

Krok 6: Minimax algoritmus: pseudokód

Potom, čo porozumiete logike algoritmu minimax, pozrite sa na tento pseudokód (funkcie, ktoré sú univerzálne pre všetky kódy) z wikipédie:

funkcia minimax (uzol, hĺbka, maximalizujúci hráč) je

ak je hĺbka = 0 alebo uzol je koncovým uzlom, potom

vráti heuristickú hodnotu uzla

ak maximalizujePlayer tak

hodnota: = −∞

pre každé dieťa uzla urobte

hodnota: = max (hodnota, minimax (dieťa, hĺbka - 1, NEPRAVDA))

návratová hodnota

else (* minimalizácia hráča *)

hodnota: = +∞

pre každé dieťa uzla urobte

hodnota: = min (hodnota, minimax (dieťa, hĺbka - 1, PRAVDA))

návratová hodnota

Jedná sa o rekurzívnu funkciu, to znamená, že sa volá znova a znova, kým nedosiahne bod zastavenia. Po prvé, funkcia má tri hodnoty, uzol, hĺbku a na rade je. Hodnota uzla je miesto, kde má program začať hľadať. Hĺbka je, ako ďaleko chcete, aby program vyhľadával. Napríklad v mojom stromovom príklade má hĺbku 3, pretože po 3 ťahoch prehľadal všetky stavy dosky. Samozrejme by sme chceli, aby AI skontrolovala každý stav dosky a vybrala víťaznú výhru, ale vo väčšine hier, kde existujú tisíce, ak nie milióny konfigurácií dosiek, váš laptop doma nebude schopný spracovať všetky tieto konfigurácie. Obmedzíme teda hĺbku vyhľadávania AI a necháme ho prejsť do najlepšieho stavu dosky.

Tento pseudokód reprodukuje proces, ktorý som vysvetlil v predchádzajúcich dvoch krokoch. Poďme teraz o krok ďalej a napravte to v kóde pythonu.

Krok 7: Vytvorenie vašej AI pomocou Ai_template.py

Predtým, ako sa pozriete na môj kód AI Minimax, vyskúšajte si vytvoriť vlastnú AI pomocou súboru ai_template.py a pseudokódu, o ktorom sme hovorili v poslednom kroku. V šablóne ai sú dve funkcie s názvom: def minimax_min_node (doska, farba) a def minimax_max_node (doska, farba). Namiesto toho, aby sa funkcia minimax volala sama rekurzívne, máme dve rôzne funkcie, ktoré sa navzájom volajú. Aby ste vytvorili heuristiku na vyhodnotenie stavov predstavenstva, budete musieť vytvoriť vlastnú funkciu. V súbore othello_shared.py sú vopred pripravené funkcie, ktoré môžete použiť na zostavenie svojej AI.

Akonáhle budete mať svoju AI, skúste ju spustiť proti, randy_ai.py. Ak chcete spustiť dva ais proti sebe, zadajte „python othello_gui.py (vložte názov súboru ai).py (vložte názov súboru).py“do terminálu mac alebo napíšte „run othello_gui.py (vložte názov súboru ai).py (vložte názov súboru).py a uistite sa, že ste v správnom adresári. Presné kroky nájdete aj v mojom videu.

Krok 8: Čas na boj proti AI

Teraz získajte partiu svojich počítačových priateľov a prinútite ich navrhnúť vlastnú AI! Potom môžete urobiť súťaž a nechať svoju AI bojovať. Našťastie, aj keď ste nemohli vytvoriť vlastnú AI, dokázali ste pochopiť, ako funguje algoritmus minimax. Ak máte akékoľvek otázky, neváhajte sa ich spýtať v komentároch nižšie.