Projekt do umělé inteligence - šachy

Autor: Lukáš Bábíček
Email: xbabice1@fi.muni.cz
Rok vytvoření: 2002

Úvod

V současné době existuje velké množství více či méně kvalitních programů pro hraní šachů. Tento projekt se v žádném případě nesnaží těmto programům konkurovat. Jedná se pouze o pokus, na kterém si chci vyzkoušet některé metody umělé inteligence.

Z pohledu umělé inteligence jsou šachy hra dvou hráčů s otevřenou informací, tj. hráč má přehled o všem, co má jeho soupeř k dispozici (narozdíl např. od většiny karetních her - pokeru,...). Uplatní se zde tedy metody prohledávání stavového prostoru (zde konkrétně Alfabeta - ale o tom již více v sekci o implementaci jednotlivých částí programu).

Program je napsán v jazyce C (tedy bez použití objektů). Grafické prostředí je vytvořeno pomocí knihoven OpenGL a Glut, které jsou volně k dispozici na Internetu. Mou snahou bylo, aby byl program maximálně přenositelný. Proto je k dispozici verze pro Windows (vyvíjena jako projekt v prostředí Microsoft Visual C++) a verze pro Linux (případně i jiný Unix) - viz sekce Download.

Ovládání programu

Ovládání programu je intuitivní - figurky se přesouvají pomocí metody drag-and-drop. Pokud má dojít k povýšení pěšce, potom je zobrazeno okno, které umožní hráči vybrat si figuru, na kterou chce pěšce povýšit.

Okno aplikace je rozděleno do dvou částí - okno s šachovnicí a oblast pro zobrazení vyhozených figurek. Pod oknem s šachovnicí je umístěn stavový řádek, který informuje o hráči, který je aktuálně na tahu, o ilegálních tazích a o konci hry.

Program se také ovládá pomocí dvou menu, které se objeví po stisku pravého tlačítka myši buď v okně s šachovnicí nebo v prostoru pro vyhozené figurky. Menu v okně s šachovnicí slouží pro nastavení barev. Menu v prostoru pro vyhozené figurky slouží ke spuštění nové partie a k ukončení programu.

Program se dá ukončit také pomocí uzavření hlavního okna. Zde je však chyba, která se mi nepodařila odstranit - v prostředí Windows se aplikace neukončí korektně - okno s konzolí je nutno uzavřít ručně.

Implementace jednotlivých částí programu

Reprezentace šachovnice

Šachovnice je reprezentována pomocí pole 12x12 čísel short int, přičemž každé číslo značí jednu z následujících možností:
- figurku, která se nachází na dané pozici
- prázdné pole
- tzv. "ilegální" pole

Proč pole 12x12 a ne 8x8? Pole 12x12 je podle mně výhodnější, protože vždy 2 okrajové sloupce (řádky) obsahují hodnotu "ilegálního" pole, tj. pole, na které se nesmí žádná figurka dostat. Toto pak velmi zjednodušuje kontrolu v generátoru tahů, zda se figurka nedostala mimo šachovnici.

Generátor tahů

Generátor tahů je rozdělen do 3 částí:
1) generování tahů pro pěšce - jednoduše se otestují tahy vpřed, braní a braní mimochodem, povýšení
2) generování tahů pro dalekonosné figury
3) generování tahů pro nedalekonosné figury

Pro 2) a 3) se používá speciální pole offsetů. Pro každou figuru v tomto poli je uvedeno, zda je dalekonosná či ne, dále pak hodnoty, které se mají přičítat k pozici figury při jejím pohybu. Toto velmi zjednodušuje generování tahů, protože pro dalekonosné figury např. stačí dva vnořené cykly for, které přičítají offsety (a generují tahy) tak dlouho, dokud není figura mimo šachovnici nebo nenarazí na jinou figuru.

Rošády a braní mimochodem jsou ošetřeny pomocí speciálních příznaků. Rošády jsou také ošetřeny pomocí tzv. phantom kings - jedná se o krále, kteří se na šachovnici přidají, aby se mohlo v následujícím tahu testovat, zda byla rošáda legální. Potom se tito phantom-kings odstraní.

Je nutné podotknout, že generátor generuje tzv. pseudo-legální tahy, tzn. tahy legální + tahy, které způsobí, že král je v šachu. Ošetřovat v generátoru, zda je král v šachu, by bylo příloš náročné. Tyto tahy se totiž dají jednoduše odstranit v rekurzivním propočtu (tedy vygeneruji tahy pro soupeře; pokud se vygeneruje i takový tah, ve kterém dojde k vyhození mého krále, potom byl můj předchozí tah nelegální).

Vygenerované tahy jsou potom ukládány do jednosměrně zřetězeného lineárního seznamu.

Prohledávání stavového prostoru

Pro prohledávání stavového prostoru je použita klasická metoda Alphabeta. Hloubka je pevně nastavena na 2 půltahy. Toto je zjevně největší chyba programu. Při vyšším nastavené však tahy trvaly "příliš" dlouho. I přesto však program podle mého názoru hraje obstojně, protože malá hloubka prohledávání je kompenzována tzv. dopočtem do tiché pozice (Quiesence search).

Jedná se v podstatě o to, že když metoda Alfabeta dojde do hloubky 0 (tedy do listů), nedojde k ohodnocení těchto listů, ale ke spuštění dopočtu do tiché pozice. Toto je speciálně upravená metoda Alfabeta, která zkoumá pouze tahy, při kterých dojde k drastické změně materiálu (tedy braní, braní mimochodem a rošády). Hloubka dopočtu do tiché pozice je nastavena na 10 (tak velkou hloubku si můžeme dovolit, protože počet tahů velmi rychle konverguje k nule). Statická vyhodnocovací funkce je potom spočítáná až v listech stromu dopočtu do tiché pozice.

Heuristika

Statická ohodnocovací funkce sestává ze dvou částí - z materiálu a ze strategické hodnoty pozice.
Hodnota materiálu je samozřejmě dominantní a je počítána průběžně v programu (tedy ne při volání ohodnocovací funkce ale v procedurách pro vykonání a navrácení tahu).
Strategická hodnota sestává z následujících částí:
- kladně se hodnotí věže na otevřených a polo-otevřených sloupcích
- kladně se hodnotí věže na 7.řádku (u soupeře)
- podporuje se rozvinutí centrálních pěšců
- podporují se koně na centrálních polích
- podporují se střelci na hlavních diagonálách
- záporně se hodnotí střelci a koně na zadních sloupcích
- záporně se hodnotí brzké rozvinutí královny
- podporuje se rošáda
- hodnotí se míra zablokování střelců

Download

Zde je k dispozici soubor ke stažení: chess.zip
Soubor obsahuje:
- kompletní zdrojové texty programu
- spustitelný soubor pro prostředí Windows
- knihovnu Glut
- projekt pro prostředí Visual C++
- Makefile pro Linux (asi bude nutné upravit cesty ke knihovnám)
- shellovský skript runme_linux - překlad + spuštění programu (asi bude nutné upravit cesty ke knihovnám)

Závěr

Závěrem bych chtěl podotknout, že na programu toho lze mnoho vylepšit. Bylo by asi velmi vhodné urychlit generátor tahů (což je asi nejkritičtější část celého programu) a umožnit tak rychlejší prohledávání do větší hloubky. Dalším nedostatkem programu je to, že pokud lidský hráč neútočí, pak počítač "neví, co dělat". To je způsobeno právě malou prohledávací hloubkou - počítači se pak zdají všechny tahy stejně dobré, a provede vždy ten první (např. pořád jezdí věží sem a tam).