Desková hra Artificial Intelligence: the Minimax Algorithm: 8 Steps

2024 Autor: John Day | [email protected]. Naposledy změněno: 2024-01-30 08:21

Zajímalo vás někdy, jak jsou vyrobeny počítače, proti kterým hrajete šachy nebo dámu? Nehledejte nic jiného než tento Instructable, protože vám ukáže, jak vytvořit jednoduchou, ale efektivní umělou inteligenci (AI) pomocí algoritmu Minimax! Pomocí algoritmu Minimax AI dělá dobře naplánované a promyšlené pohyby (nebo alespoň napodobuje myšlenkový proces). Nyní bych vám mohl poskytnout kód pro AI, kterou jsem vytvořil, ale to by nebyla zábava. Vysvětlím logiku za volbami počítače.

V tomto Instructable vás provedu kroky, jak vytvořit AI pro Othello (AKA Reversi) v pythonu. Před řešením tohoto projektu byste měli mít středně pokročilé porozumění tomu, jak kódovat v pythonu. Zde je několik dobrých webových stránek, na které se můžete připravit a připravit vás na tento Instructable: w3schools nebo learnpython. Na konci tohoto Instructable byste měli mít AI, která bude provádět vypočítané pohyby a měla by být schopná porazit většinu lidí.

Protože se tento Instructable bude primárně zabývat tím, jak vytvořit AI, nebudu vysvětlovat, jak navrhnout hru v pythonu. Místo toho dám kód pro hru, kde může člověk hrát proti jinému člověku, a upravím ho tak, abyste mohli hrát hru, kde člověk hraje proti AI.

Naučil jsem se, jak vytvořit tuto AI, prostřednictvím letního programu v Columbia SHAPE. Měl jsem se tam dobře, takže se podívejte na jejich webové stránky, abyste zjistili, zda by vás to zajímalo.

Nyní, když jsme se zbavili logistiky, začněme kódovat!

(Do obrázků jsem vložil několik poznámek, takže se na ně určitě podívejte)

Zásoby

To je snadné:

1) Počítač s prostředím pythonu, jako je Spyder nebo IDLE

2) Stáhněte si soubory pro hru Othello z mého GitHubu

3) Váš mozek s nainstalovanou trpělivostí

Krok 1: Stáhněte si potřebné soubory

Když přejdete do mého GitHubu, měli byste vidět 5 souborů. Stáhněte si všech 5 a umístěte je všechny do stejné složky. Než spustíme hru, otevřete všechny soubory v prostředí spyderu.

Co soubory dělají:

1) othello_gui.py tento soubor vytvoří herní plán, na kterém mohou hráči hrát (ať už lidský nebo počítačový)

2) othello_game.py tento soubor hraje dva počítače proti sobě bez herního plánu a zobrazuje pouze skóre a přesouvá pozice

3) ai_template.py to je místo, kde budete vkládat veškerý svůj kód pro vytvoření AI

4) randy_ai.py toto je předem připravená AI, která si své tahy vybírá náhodně

5) othello_shared.py spousta předem připravených funkcí, které můžete použít k vytvoření své AI, například ke kontrole dostupných tahů, skóre nebo stavu desky

6) Tři další soubory: Puma.py, erika_5.py a nathan.py, které jsem vytvořil já, Erika a Nathan z programu SHAPE, to jsou tři různé AI s unikátními kódy

Krok 2: Jak otevřít a hrát Python Othello

Jakmile budete mít všechny soubory otevřené, v pravém dolním rohu obrazovky zadejte „spustit othello_gui.py“a stiskněte klávesu Enter v konzole IPython. Nebo v terminálu Mac zadejte „python othello_gui.py“(poté, co jste samozřejmě ve správné složce). Poté by se na obrazovce měla objevit deska. Tento režim je režim člověk vs. Světlo jde druhé a tmavé první. Pokud jste zmatení, podívejte se na moje video. iV horní části je skóre každé barevné dlaždice. Chcete -li hrát, klikněte na platný tahový prostor, vložte tam dlaždici a poté dejte počítač svému soupeři, který udělá totéž a opakuje.

Pokud nevíte, jak hrát Othello, přečtěte si tato pravidla z webu ultra boards:

Černá se vždy pohybuje jako první. Tah se provádí umístěním disku hráčovy barvy na hrací desku do polohy, která „vybočuje“jeden nebo více soupeřových disků. Disk nebo řada disků je obejita, když je na koncích obklopena kotouči opačné barvy. Disk může obejít libovolný počet disků v jedné nebo více řadách v libovolném směru (horizontální, vertikální, diagonální)…. (dočíst na jejich webových stránkách)

Rozdíl mezi původní hrou a touto hrou na python je ten, že když pro jednoho hráče nezbývají žádné platné tahy, hra končí

Nyní, když můžete hrát hru s přítelem, vytvořme AI, se kterou můžete hrát.

Krok 3: Minimax algoritmus: Generování scénářů

Než budeme mluvit o tom, jak to napsat do kódu, pojďme si projít logiku, která je za tím. Algoritmus minimaxu je algoritmus pro rozhodování a zpětné sledování a obvykle se používá v tahových hrách pro dva hráče. Cílem této AI je najít další nejlepší tah a následující nejlepší tahy, dokud hru nevyhraje.

Jak by tedy algoritmus určil, který tah je nejlepší? Zastavte se a přemýšlejte, jak byste zvolili další tah. Většina lidí by zvolila tah, který by jim dal nejvíce bodů, že? Nebo pokud by mysleli dopředu, zvolili by tah, který by nastolil situaci, kdy by mohli získat ještě více bodů. Druhý způsob myšlení je způsob, jakým Algoritmus Minimax uvažuje. Dívá se dopředu na všechna budoucí nastavení desek a dělá tah, který by vedl k nejvíce bodům.

Nazval jsem to algoritmem zpětného sledování, protože začíná nejprve vytvořením a vyhodnocením všech budoucích stavů desky s jejich přidruženými hodnotami. To znamená, že algoritmus bude hrát hru tolik, kolik potřebuje (dělá tahy pro sebe i pro protivníka), dokud se nepřehraje každý scénář hry. Abychom měli přehled o všech stavech desky (scénáře), můžeme nakreslit strom (podívejte se na obrázky). Strom na obrázku výše je jednoduchým příkladem hry Connect 4. Každá konfigurace desky se nazývá stav desky a její místo na stromě se nazývá uzel. Všechny uzly ve spodní části stromu jsou konečnými stavy desky po provedení všech tahů. Je zřejmé, že některé stavy desek jsou pro jednoho hráče lepší než pro druhého. Nyní tedy musíme nechat AI vybrat, do kterého stavu desky se chce dostat.

Krok 4: Minimax: Vyhodnocení konfigurací desky

Abychom získali hodnoty pro tabule, musíme se naučit strategie hry, kterou hrajeme: v tomto případě strategie Othella. Protože tato hra je bitva převrácení soupeřových a vašich disků, nejlepší pozice disku jsou ty, které jsou stabilní a nelze je převrátit. Roh je například místo, kde při umístění disku nelze změnit barvu na jinou. Toto místo by tedy bylo nesmírně cenné. Mezi další dobré pozice patří boky desky, které vám umožní vzít spoustu kamenů. Na tomto webu je více strategií.

Nyní můžeme pozicím pro každou desku stavové desky přiřadit hodnoty. Když je pozice obsazena figurkou AI, pak dáte určitý počet bodů v závislosti na pozici. Například stav desky, kde je figurka AI v rohu, můžete dát bonus 50 bodů, ale pokud by byla na nepříznivém místě, figurka může mít hodnotu 0. Po zohlednění všech hodnot pozice, přiřadíte stavu desky hodnotu. Pokud má například AI figurku v rohu, stav desky může mít skóre 50, zatímco jiný stav desky s figurkou AI uprostřed má skóre 10.

Existuje mnoho způsobů, jak toho dosáhnout, a mám tři různé heuristiky k vyhodnocení dílků. Doporučuji vám vytvořit si svůj vlastní typ heuristiky. Do svého githubu jsem nahrál tři různé AI od tří různých výrobců se třemi různými heuristikami: Puma.py, erika5.py, nathanh.py.

Krok 5: Minimax algoritmus: Výběr nejlepšího tahu

Nyní by bylo hezké, kdyby si AI mohla vybrat všechny tahy, aby se dostala do stavu desky s nejvyšším skóre. Pamatujte však, že AI také vybírala tahy pro protivníka, když generovala všechny stavy desek, a pokud je soupeř chytrý, nedovolí AI dosáhnout nejvyššího skóre desky. Místo toho by chytrý protivník udělal krok, aby se AI dostala do stavu nejnižší desky. V algoritmu nazýváme dva hráče maximalizujícím hráčem a minimalizujícím hráčem. AI by byla maximalizujícím hráčem, protože chce získat co nejvíce bodů pro sebe. Soupeřem by byl minimalizující hráč, protože se snaží udělat tah, kde AI získá nejméně bodů.

Jakmile jsou generovány všechny stavy desek a jsou jim přiřazeny hodnoty, začne algoritmus porovnávat stavy desek. Na obrázcích jsem vytvořil strom, který reprezentuje, jak by algoritmus vybíral své pohyby. Každé rozdělení ve větvích je jiný tah, který může AI nebo soupeř hrát. Vlevo od řad uzlů jsem napsal, zda jde maximalizující nebo minimalizující hráč. Spodní řádek jsou všechny stavy tabule s jejich hodnotami. Uvnitř každého z těchto uzlů je číslo a to jsou skóre, která přiřadíme každému z desek: čím jsou vyšší, tím je pro AI lepší.

Definice: nadřazený uzel - uzel, který vyústí nebo vytvoří uzly pod ním; původ podřízených uzlů - uzlů, které pocházejí ze stejného nadřazeného uzlu

Prázdné uzly představují pohyb, který AI provede, aby se dostal do nejlepšího stavu desky. Začíná to porovnáním potomků nejvíce levého uzlu: 10, -3, 5. Protože tah maximalizující hráč provede, zvolí tah, který mu dá nejvíce bodů: 10. Takže to vybereme a uložíme pohybujte se skóre tabule a zapište jej do nadřazeného uzlu. Nyní, když je 10 v nadřazeném uzlu, nyní přichází řada na minimalizující hráče. Uzel, ke kterému bychom porovnali 10, je však prázdný, takže než si minimalizující hráč může vybrat, musíme jej nejprve vyhodnotit. Vracíme se tedy k maximalizaci tahu hráče a porovnáváme děti sousedního uzlu: 8, -2. Maximalizace zvolí 8 a napíšeme to do prázdného nadřazeného uzlu. Nyní, když algoritmus dokončil vyplňování prázdných mezer pro děti uzlu nad ním, může minimalizující hráč tyto děti porovnat - 10 a 8 a zvolit 8. Algoritmus pak opakuje tento proces, dokud není vyplněn celý strom. Na konci tohoto příkladu máme skóre 8. To je nejvyšší stav desky, který může AI hrát, za předpokladu, že soupeř hraje optimálně. AI tedy vybere první tah, který vede do stavu 8 desky, a pokud soupeř hraje optimálně, AI by měla hrát všechny tahy, aby se dostala do stavu 8 na desce (postupujte podle poznámek na mých obrázcích)

Vím, že to bylo hodně. Pokud patříte k těm typům, které potřebují, aby s vámi někdo mluvil, aby něčemu porozuměl, zde je několik videí, která jsem sledoval, aby mi pomohla pochopit myšlenku: 1, 2, 3.

Krok 6: Minimax algoritmus: Pseudokód

Jakmile porozumíte logice algoritmu minimax, podívejte se na tento pseudokód (funkce, které jsou univerzální pro všechny kódy) z wikipedie:

funkce minimax (uzel, hloubka, maximizingPlayer) je

pokud je hloubka = 0 nebo uzel je koncový uzel, pak

vrátit heuristickou hodnotu uzlu

pokud maximalizujePlayer pak

hodnota: = −∞

pro každé dítě uzlu dělat

hodnota: = max (hodnota, minimax (dítě, hloubka - 1, NEPRAVDA))

návratová hodnota

else (* minimalizace hráče *)

hodnota: = +∞

pro každé dítě uzlu dělat

hodnota: = min (hodnota, minimax (podřízená, hloubka - 1, PRAVDA))

návratová hodnota

Jedná se o rekurzivní funkci, což znamená, že se volá znovu a znovu, dokud nedosáhne bodu zastavení. Za prvé, funkce má tři hodnoty, uzel, hloubku a na řadě je. Hodnota uzlu je místo, kde chcete, aby program začal hledat. Hloubka je, jak daleko chcete, aby program vyhledával. Například v mém stromovém příkladu má hloubku 3, protože po 3 tahech prohledalo všechny stavy desky. Samozřejmě bychom chtěli, aby AI zkontrolovala každý stav desky a vybrala vítěznou výhru, ale ve většině her, kde existují tisíce, ne -li miliony konfigurací desek, váš notebook doma nebude schopen zpracovat všechny tyto konfigurace. Omezíme tedy hloubku hledání AI a necháme ji přejít do nejlepšího stavu desky.

Tento pseudokód reprodukuje proces, který jsem vysvětlil v předchozích dvou krocích. Pojďme nyní o krok dále a napravte to v kódu pythonu.

Krok 7: Vytvoření vaší AI pomocí Ai_template.py

Než se podíváte na můj Minimax AI kód, zkuste si vytvořit vlastní AI pomocí souboru ai_template.py a pseudokódu, o kterém jsme mluvili v posledním kroku. V šabloně ai jsou dvě funkce: def minimax_min_node (deska, barva) a def minimax_max_node (deska, barva). Místo toho, aby se funkce minimax volala sama rekurzivně, máme dvě různé funkce, které se navzájem nazývají. Chcete -li vytvořit heuristiku pro vyhodnocení stavů desek, budete muset vytvořit vlastní funkci. V souboru othello_shared.py jsou předem připravené funkce, které můžete použít k vytvoření AI.

Až budete mít svoji AI, zkuste ji spustit proti, randy_ai.py. Chcete -li spustit dva ais proti sobě, zadejte do terminálu mac „python othello_gui.py (vložte název souboru ai).py (vložte název souboru).py“nebo zadejte „spustit othello_gui.py (vložte název souboru ai).py (vložte název souboru).py a ujistěte se, že jste ve správném adresáři. Přesné kroky najdete také v mém videu.

Krok 8: Čas, aby AI bojoval

Nyní získejte spoustu svých počítačových přátel a přimějte je navrhnout vlastní AI! Pak můžete udělat soutěž a nechat ji odvést AI. Naštěstí, i když jste nemohli vytvořit vlastní AI, dokázali jste pochopit, jak algoritmus minimax funguje. Pokud máte nějaké dotazy, neváhejte je zaslat do komentářů níže.