Jak učinit vaši hru Tic Tac Toe bezkonkurenční pomocí algoritmu minimax

Snažil jsem se celé hodiny procházet tutoriály, dívat se na videa a bouchat hlavou do stolu a pokoušet se vytvořit spolehlivou hru Tic Tac Toe se spolehlivou umělou inteligencí. Pokud tedy procházíte podobnou cestou, rád bych vám představil algoritmus Minimax.

Stejně jako profesionální šachový hráč i tento algoritmus vidí pár kroků dopředu a postaví se do obuvi svého protivníka. Neustále hraje dopředu, dokud nedosáhne terminálového uspořádání rady (stav terminálu), což má za následek remízu, výhru nebo prohru. Jakmile je terminál ve stavu terminálu, přidělí AI libovolné kladné skóre (+10) pro výhru, záporné skóre (-10) pro ztrátu nebo neutrální skóre (0) pro remízu.

Algoritmus zároveň vyhodnocuje pohyby, které vedou do stavu terminálu na základě tahu hráčů. Bude to tah s maximálním skóre, když je na řadě AI, a vybere tah s minimálním skóre, když je na řadě lidský hráč. Při použití této strategie se Minimax vyhýbá ztrátě lidskému hráči.

Vyzkoušejte si to v následující hře.

Algoritmus Minimax lze nejlépe definovat jako rekurzivní funkci, která provádí následující věci:

  1. vrácení hodnoty, pokud je nalezen stav terminálu (+10, 0, -10)
  2. projít dostupnými místy na desce
  3. volání funkce minimax na každém dostupném místě (rekurze)
  4. vyhodnotit vrácené hodnoty z volání funkcí
  5. a vrátit nejlepší hodnotu

Pokud jste novým konceptem rekurze, doporučujeme sledovat toto video z Harvardu CS50.

Pro úplné pochopení myšlenkového procesu Minimaxu jej implementujme do kódu a uvidíme ho v akci v následujících dvou sekcích.

Minimax v kódu

Pro tento tutoriál budete pracovat na stavu konce hry, který je zobrazen na obrázku 2 níže. Protože minimax vyhodnocuje každý stav hry (stovky tisíc), stav blízkého konce vám umožňuje snáze sledovat rekurzivní volání minimaxu (9).

Pro následující obrázek předpokládejme, že AI je X a lidský hráč je O.

obrázek 2 ukázka stavu hry

Pro snazší práci s deskou Ti Tac Toe byste ji měli definovat jako pole s 9 položkami. Každá položka bude mít index jako hodnotu. To se hodí později. Protože výše uvedená deska je již osazena některými pohyby X a Y, definujme desku s pohyby X a Y již v ní (origBoard).

var origBoard = ["O", 1, "X", "X", 4, "X", 6, "O", "O"];

Poté deklarujte proměnné aiPlayer a huPlayer a nastavte je na „X“ a „O“.

Dále potřebujete funkci, která hledá výherní kombinace a vrátí true, pokud ji najde, a funkci, která uvádí indexy dostupných spotů na desce.

Nyní pojďme do dobrých částí definováním funkce Minimax se dvěma argumenty newBoard a player. Pak musíte najít indexy dostupných míst na desce a nastavit je na proměnnou zvanou availSpots.

Rovněž je třeba zkontrolovat stav terminálů a podle toho vrátit hodnotu. Pokud O vyhrajete, měli byste se vrátit -10, pokud X vyhrajete, měli byste se vrátit +10. Pokud je délka pole availableSpots nulová, to znamená, že již není místo na hraní, hra skončila remízou a vy byste měli vrátit nulu.

Dále je třeba shromáždit skóre z každého z prázdných míst, abyste je mohli později vyhodnotit. Proto vytvořte pole zvané tahy a opakujte prázdné body, zatímco shromažďujte index každého tahu a skóre v objektu zvaném tah.

Potom nastavte číslo indexu prázdného místa, které bylo uloženo jako číslo v origBoard, na vlastnost index objektu přesunu. Později nastavte prázdné místo na newboardu na aktuálního hráče a zavolejte funkci minimax s jiným hráčem a nově změněnou newboard. Dále byste měli uložit objekt, který byl výsledkem volání funkce minimax a který zahrnuje vlastnost skóre do vlastnosti skóre objektu přesunu.

Pokud funkce minimax nenalezne stav terminálu, udržuje rekurzivně na úrovni hlouběji do hry. K této rekurzi dochází, dokud nedosáhne stavu terminálu a nevrátí skóre o jednu úroveň výše.

Nakonec Minimax resetuje newBoard na to, co bylo dříve, a posune objekt přesunu do pole tahů.

Algoritmus minimax musí poté vyhodnotit nejlepší tah v poli tahů. Měl by si zvolit tah s nejvyšším skóre, když hraje AI, a tah s nejnižším skóre, když hraje člověk. Proto, pokud je hráč aiPlayer, nastaví proměnnou zvanou bestScore na velmi nízké číslo a smyčky skrz pole tahů, pokud má tah vyšší skóre než bestScore, algoritmus ukládá tento pohyb. V případě, že existují tahy s podobným skóre, bude uložen pouze první.

Stejný proces hodnocení se stane, když je hráč huPlayer, ale tentokrát by bestScore byl nastaven na vysoké číslo a Minimax hledá tah s nejnižším skóre, které má uložit.

Nakonec Minimax vrátí objekt uložený v bestMove.

To je pro funkci minimax. :) výše uvedený algoritmus najdete na githubu a codepenu. Hrajte si s různými deskami a zkontrolujte výsledky v konzole.

V další části přejdeme přes řádek kódu po řádku, abychom lépe porozuměli tomu, jak se funkce minimax chová vzhledem k desce uvedené na obrázku 2.

Minimax v akci

Na následujícím obrázku sledujeme volání funkcí algoritmu (FC) jeden po druhém.

Poznámka: Na obrázku 3 velká čísla představují každé volání funkce a úrovně odkazují na to, kolik kroků před hraním hry hraje algoritmus.

Obrázek 3 Volání funkce Minimax pomocí volání funkce

1.origBoard a aiPlayer jsou přiváděny do algoritmu. Algoritmus vytvoří seznam tří prázdných míst, které najde, zkontroluje stav terminálů a smyčky skrz každé prázdné místo počínaje prvním. Poté změní newBoard umístěním aiPlayer na první prázdné místo. Poté se nazývá newBoard a huPlayer a čeká, až FC vrátí hodnotu.

2. Zatímco první FC stále běží, druhý začíná spuštěním seznamu dvou prázdných míst, které najde, kontroluje stav terminálů a opakuje prázdné místo počínaje prvním. Poté změní newBoard umístěním huPlayer na první prázdné místo. Poté se zavolá s newBoard a aiPlayer a čeká, až FC vrátí hodnotu.

3. Nakonec algoritmus vytvoří seznam prázdných míst a po kontrole terminálových stavů najde vítězství pro hráče. Proto vrací objekt s vlastností skóre a hodnotou -10.

Protože druhý FC uvedl dvě prázdná místa, Minimax změní newBoard umístěním huPlayer do druhého prázdného místa. Poté se volá novým panelem a aiPlayerem.

4. Algoritmus vytvoří seznam prázdných míst a po kontrole terminálových stavů najde pro hráče lidskou výhru. Proto vrací objekt s vlastností skóre a hodnotou -10.

Na druhém FC algoritmus shromažďuje hodnoty přicházející z nižších úrovní (3. a 4. FC). Protože tah huPlayer vyústil ve dvě hodnoty, algoritmus vybere nejnižší z těchto dvou hodnot. Protože obě hodnoty jsou podobné, vybere první a vrátí ji do prvního FC.
V tomto okamžiku první FC vyhodnotil skóre přesunu aiPlayer na prvním prázdném místě. Dále změní newBoard umístěním aiPlayer na druhé prázdné místo. Poté se volá s newBoard a huPlayer.

5. V pátém FC algoritmus vytvoří seznam prázdných míst a po kontrole stavu terminálu najde lidský vítězství. Proto vrací objekt s vlastností skóre a hodnotou +10.

Poté se první FC přesune změnou newBoard a umístěním aiPlayer na třetí prázdné místo. Poté se volá novou deskou a huPlayerem.

6. Šestý FC začíná vytvořením seznamu dvou prázdných míst, které najde, kontroluje stav terminálů a opakuje obě prázdné místa od prvního. Poté změní newBoard umístěním huPlayer na první prázdné místo. Poté se nazývá newBoard a aiPlayer a čeká, až FC vrátí skóre.

7. Nyní je algoritmus ve dvou úrovních hluboko do rekurze. Vytvoří seznam jednoho prázdného místa, které najde, zkontroluje stav terminálů a změní newBoard umístěním aiPlayer na prázdné místo. Poté se zavolá s newBoard a huPlayer a čeká, až FC vrátí skóre, aby jej mohl vyhodnotit.

8. Na 8. FC provede algoritmus prázdný seznam prázdných míst a po kontrole stavu terminálu najde vítězství pro aiPlayer. Proto vrací objekt s vlastnostmi skóre a hodnotou +10 o jednu úroveň výše (7. FC).

7. FC obdržel pouze jednu kladnou hodnotu z nižších úrovní (8. FC). Protože tah aiPlayer vyústil v tuto hodnotu, musí algoritmus vrátit nejvyšší hodnotu, kterou obdržel z nižších úrovní. Proto vrací svou jedinou kladnou hodnotu (+10) o úroveň výš (6. FC).
Protože 6. FC uvedl dvě prázdná místa, Minimax změní newBoard umístěním huPlayer na druhé prázdné místo. Poté se zavolá s novou deskou a aiPlayerem.

9. Dále algoritmus vytvoří seznam prázdných míst a po kontrole stavu terminálu najde vítězství pro aiPlayer. Proto vrací objekt s vlastnostmi skóre a hodnotou +10.

V tomto okamžiku si musí 6 FC vybrat mezi skóre (+10), které bylo vysláno ze 7. FC (vráceno původně z 8 FC) a skóre (-10) vrácené z 9. FC. Protože tah huPlayer vyústil v tyto dvě vrácené hodnoty, algoritmus najde minimální skóre (-10) a vrátí ho jako objekt obsahující vlastnosti skóre a indexu.
Nakonec byly vyhodnoceny všechny tři větve prvního FC (-10, +10, -10). Ale protože tah aiPlayer vyústil v tyto hodnoty, algoritmus vrací objekt obsahující nejvyšší skóre (+10) a jeho index (4).

Ve výše uvedeném scénáři Minimax dochází k závěru, že přesunutí X do středu desky vede k nejlepšímu výsledku. :)

Konec!

Nyní byste měli být schopni porozumět logice algoritmu Minimax. Pomocí této logiky se pokuste implementovat algoritmus Minimax sami nebo najít výše uvedený vzorek na githubu nebo codepenu a optimalizovat jej.

Děkuji za přečtení! Pokud se vám tento příběh líbil, doporučujeme jej kliknutím na tlačítko ❤ na boku a jeho sdílením na sociálních médiích.

Zvláštní poděkování patří Tuba Yilmazovi, Rickovi McGavinovi a Javidovi Askerovovi za přezkoumání tohoto článku.