Krok-za-krokem průvodce k budování jednoduché šachy AI

tím, že Lauri Hartikka

podíváme se na některé základní pojmy, které nám pomohou vytvořit jednoduché šachy AI:

pohyb-generace
hodnocení činnosti správní rady
minimax
a alfa-beta prořezávání.

v každém kroku vylepšíme náš algoritmus jednou z těchto osvědčených technik šachového programování. Ukážu, jak každý ovlivňuje herní styl algoritmu.

konečný algoritmus AI si můžete prohlédnout zde na Githubu.

Krok 1: Přesun generování a vizualizace desky

použijeme šachy.knihovna js pro generování tahů, a šachovnice.js pro vizualizaci desky. Knihovna move generation v podstatě implementuje všechna pravidla šachu. Na základě toho můžeme spočítat všechny právní kroky pro daný stát.

vizualizace funkce generování přesunu. Výchozí pozice se používá jako vstup a výstupem jsou všechny možné pohyby z této polohy.

Pomocí těchto knihoven nám pomůže zaměřit se pouze na nejzajímavější úkol: vytvořit algoritmus, který najde nejlepší tah.

začneme tím, že vytvoří funkci, která vrátí náhodný pohyb ze všech možných tahů:

Přestože tento algoritmus není velmi solidní šachový hráč, je to dobrý výchozí bod, jako můžeme skutečně hrát proti to:

Černý hraje náhodné pohyby. Hratelné na https://jsfiddle.net/lhartikk/m14epfwb/4

Krok 2 : Hodnocení pozice

nyní se pokusíme pochopit, která strana je v určité pozici silnější. Nejjednodušší způsob, jak toho dosáhnout, je počítat relativní sílu figurky na šachovnici pomocí následující tabulky:

S hodnotící funkci, jsme schopni vytvořit algoritmus, který vybere pohyb, který dává nejvyšší hodnocení:

pouze hmatatelné zlepšení je, že náš algoritmus bude nyní zachytit kus, pokud to půjde.

Black hraje pomocí jednoduché vyhodnocovací funkce. Hratelné na https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Krok 3: Vyhledávací strom pomocí Minimax

Dále vytvoříme vyhledávací strom, ze kterého algoritmus můžete vybrat nejlepší tah. To se provádí pomocí algoritmu Minimax.

V tomto algoritmu rekurzivní strom všech možných tahů je prozkoumat dané hloubky, a pozice je hodnocena na konec „listů“ stromu.

poté vrátíme buď nejmenší nebo největší hodnotu dítěte do nadřazeného uzlu, v závislosti na tom, zda se pohybuje bílá nebo černá. (To znamená, že se snažíme minimalizovat nebo maximalizovat výsledek na každé úrovni.)

vizualizace minimax algoritmus v umělé poloze. Nejlepší tah bílého je b2-c3, protože můžeme zaručit, že se můžeme dostat do situace, kdy hodnocení je -50

S minimax v místě, náš algoritmus začíná pochopit některé základní taktiky šachy:

Minimax s hloubkou úroveň 2. Hratelné na: https://jsfiddle.net/k96eoq0q/1/

účinnost minimax algoritmus je silně založena na hledání hloubky můžeme dosáhnout. To je něco, co v následujícím kroku vylepšíme.

Krok 4: Alfa-beta prořezávání

alfa-beta prořezávání je optimalizační metoda algoritmu minimax, která nám umožňuje ignorovat některé větve ve vyhledávacím stromu. To nám pomáhá vyhodnotit vyhledávací strom minimax mnohem hlouběji, při použití stejných zdrojů.

alfa-beta prořezávání je založen na situaci, kdy se můžeme zastavit vyhodnocení části vyhledávacího stromu, když jsme našli pohyb, který vede k horší situaci než dříve objeveného pohybu.

alfa-beta prořezávání neovlivňuje výsledek algoritmu minimax — pouze to zrychluje.

algoritmus alfa-beta je také efektivnější, pokud náhodou navštívíme nejprve ty cesty, které vedou k dobrým pohybům.

pozice nepotřebujeme, aby prozkoumala, zda alfa-beta prořezávání proto je-li použito a strom je navštívil v popsaném pořadí.

s alfa-beta získáme významnou podporu algoritmu minimax, jak je ukázáno v následujícím příkladu:

počet pozic, které jsou nutné pro vyhodnocení, zda chceme provést hledání s hloubkou 4 a „root“ pozici, je ten, který je zobrazen.

následujte tento odkaz a vyzkoušejte alfa-beta vylepšenou verzi šachové AI.

Krok 5: Vylepšená hodnotící funkce

počáteční hodnotící funkce je poměrně naivní, protože počítáme pouze materiál, který se nachází na desce. Abychom to zlepšili, přidáme k hodnocení faktor, který bere v úvahu polohu kusů. Například rytíř ve středu desky je lepší (protože má více možností a je tedy aktivnější) než rytíř na okraji desky.

použijeme mírně upravenou verzi tabulek piece-square, které jsou původně popsány v šachovém programování-wiki.

vizualizovaný kus-čtvercové tabulky vizualizované. Hodnocení můžeme snížit nebo zvýšit v závislosti na umístění kusu.

S následujícími zlepšení, začneme algoritmus, který hraje nějaké „slušné“ šachy, alespoň z hlediska příležitostný hráč:

Lepší hodnocení a alfa-beta prořezávání s vyhledávací hloubky 3. Hratelné na https://jsfiddle.net/q76uzxwe/1/

Závěry

síla i jednoduchý šachový algoritmus je, že to nedělá hloupé chyby. To znamená, že stále postrádá strategické porozumění.

s metodami, které jsem zde představil, jsme byli schopni naprogramovat algoritmus hraní šachů, který dokáže hrát základní šachy. „AI-part“ (move-generation vyloučen) konečného algoritmu je jen 200 řádků kódu, což znamená, že základní pojmy jsou poměrně jednoduché implementovat. Můžete se podívat na finální verze je na GitHub.

Některé další vylepšení můžeme udělat, aby algoritmus by být například:

pohyb-objednávání
rychlejší pohyb generace
a na konci hry zvláštní hodnocení.

KGSAU