AI pro piškvorky v rubrice C,C++

Něco o základech umělé inteligence pro tuto hru.

Umělá inteligence pro piškvorky Úvod - trocha teorie Umělá inteligence je bezesporu jedna z oblastí, které dělají hru lepší hrou. Udělat piškvorky pro dva hráče (lidi) je věc vcelku jednoduchá. Stačí obyčejné dvojrozměrné pole celočíselného typu pro zaznamenávání tahu - čtverečkový papír. Kde jednotlivé hodnoty budou znamenat například: 0 = pole je prázdné - tedy nikdo sem ještě netáhl 1 = táhl sem hráč 1 - například křížek 2 = táhl sem hřáč 2 - tedy kolečko Toto je v podstatě nejdůležitější záznam. Teoreticky by stačily dvě stějně velká boolová pole - byla by však s nimy horší manipulace (stejně zabírají stejně), a krom toho do budoucna se nehodí. Podle hodnoty v poli se rozhodneme zda chceme vykreslit na dané souřadnice kolečko nebo křížek. Dále je potřeba, opět boolová hodnota, pro označení hráče, který je právě na tahu - pro zápis. Ta se bude "přepínat" po každém tahu. Teď jen stačí vše nějak "nakreslit", A piškvokry pro dva lidské hráče jsou hotovy. Problém však nastává pokud druhého hráče chceme nahradit počítačem. Ano, tušíte správně, nevystačíme si s jednoduchým dvourozměrným polem a "flagem" pro hráče. Budeme potřebovat ještě jedno podobné pole - opět celočíselné - o stejné velikosti jako to předchozí. Nejjednoduší bude přidat třetí rozměr = [výška][šířka][2]. Tento rozměr nám bude značit jak moc by sem měl počítač táhnout. A to jak z hlediska útoku, tak také aby zabránil vaší expanzi. Šlo by také použít oddělená pole - jedno pro útok a druhé pro obranu tedy [výška][šířka][3]. Nesmíme zapomenout vše na začátku nastavit na nulu. Jak již je asi patrné počítač se bude rozhodovat globálně - tedy po celé ploše, a ne podle posledního tahu. To sice může vézt k menším komplikacím (o těch se zmíním později), ale na druhou stranu pak může počítač svým tahem překvapit (nepříjemně samozřejmě). Nyní stojíme před rozhodnutím jestli je lepší počítat s posledním tahem, nebo vždy celé pole přepočítat. Obě cesty mají své klady i zápory, proberu tedy oba způsoby: metoda 1. - poslední tah Na první pohled se vám pravděpodobně zdá být výhodnější. Její velký klad je určitě v mnohem menší časové naročnosti, nebo chcete-li v menším počtu operací, které jsou nutné k samotnému rozhodnutí. Vyhodnocení tahu se provede ihned po tahu hráče, tedy samozřejmě jen pokud byl platný. Do pole, které nám znazorňuje hrací plochu zapíšeme číslo hráče. Následně do ohodnocení útoku a obrany o těch samých souřadnících vložíme nuly - na místo, které je již obsazené by asi počítač táhnout opravdu neměl. Teď se podíváme do nejblizšího okolí bodu. Lze ho projít dvěma jednoduchými for cykly: (příklady uvádím v jazyce C++ - sám jsem v něm toto dělal a doufám že následující zápis pochopí i neznalý tohoto jazyka) for(int i=-1; i<2; i++) { for(int j=-1; j<2; { //sem přijde další kód } } Jak jste si jistě všimli, jedná se o opravdu nejblizší, a myslím že pro naše učely plně postačí. Tyto hodnoty v podstatě slouží jako ukazatel směru, kudy se právě ubírame. Na tomto poli se nám naskýtají tři možnosti (0,1,2) a) možnost nula - je tu volno. Stačí do obranného indexu tohoto pole přičíst 1, tedy základ. Dále se můžeme podívat, jestli v tomto směru již předtím hráč netáhl. Zkontrolujeme tedy prvek ob jedna. Docílíme toho velmi snadno - stačí vynásobit atribut směru(obě jeho části) dvěmi. Pokud je zde hráč, je nutné zjistit jakou zde má řadu (jak dlouhou). Zavedeme tedy proměnnou "Pocet", a provedeme následující: int Pocet = 1; //kontroluje radu ve smeru (i,j) ob jedno pole, x,y jsou souřadnice tahu while(Pole[x+i+Pocet*i][y+j+Pocet*j][0] == Hrac) { Pocet++; } Tedy budeme jednoduše pokračovat v daném směru, dokud zde bude hráč. Nesmíme zapomenout, že proměnná Pocet je o jedna vyšší, než je skutečná délka. V případě, že jeho řada je dlouhá tak, že by mohl příště vyhrát (Pocet je tedy roven 4), Přičteme do obranného hodnocení tohoto pole nějaké velké číslo. O Druhou stranu se starat nemusíme, ta bude vyhodnocena samostatně - vždy se tedy stačí starat pouze o jeden směr. b) možnost jedna - hrač táhl také sem. Je tedy nutné zjistit, jak dlouhou zde již má řadu. - pomocí podobného, výše uvedeného postupu zjistíme délku řady v onom směru. To však nestačí. Teď zjistíme skutečnou délku řady. budeme postupovat od konce, opět podobně (směr stačí vynásobit (-1)) Teď máme několik hodnot: Délku řady a dvě souřadnice - na každém konci jedna. Nemusíme (ale kdo chce může) starat o to co je dále za řadou a za koncem řad. Zjistíme co řadu ukončuje, v případě, že ji ukončuje oponent, budeme chtít do obranného atributu druhého konce přičíst menší číslo. To sem přičteme pokud je zde prázdno, Do každého konce řady asi budeme chtít přičítat různou hodnotu, která bude vycházet z delky řady, rovnici ať si udělá každý sám. Také si musíme dávat pozor aby jsme to nepočítali 2x (při vyhodnocení na druhé straně) c) možnost dvě - táhl sem počítač. - v podstatě pro jednoduchou hru, by se zde nic dít nemuselo, a samozřejmě jako vždy může. Po ohodnocení tahu hráče vybere počítač souřadnice s nejvyšším ohodnocením (lze dělat poměry mezi útočným a obranným atributem, a tak řídit, jestli má spíše útočit, nebo bránit) A sem táhnout. A další problém: jak ohodnotit počítač?? - a odpověď - jednodušše - v podstatě stejně jako hráče, jen zaměnit obranný a útočný atribut, hráče za počítač. metoda 2. - bod po bodu Tato metoda asi všem připadne jako poněkud zdlouhavá, je však ale důležité uvědomit si, co vlastně chceme počítat - a tady to jde lépe. Není vůbec důležité, kam naposledy táhnul hráč. Na začátku tohoto počítání bude nutné smazat všechny hodnoty pro rozhodování, tedy: // Sirka značí šířku pole for(int x = 0; x < Sirka; x++) { // Vyska značí výšku pole for(int y = 0; y < Vyska; y++) { // Pole je ona proměnná (resp.pole) // představující hrací plochu // Nastáví ohodnocení obrany na 0 // (NULL představuje nulu, kupodivu :-) Pole[x][y][1] = NULL; // Nastaví ohodnocení útoku na 0 Pole[x][y][2] = NULL; // Pozor v Pole[*][*][0] je základní // herní plocha !! } } Tak teď již máme připravenou půdu. Stačí jen postupně projít všechny body a přiřadit jim ohodnoceni(tedy hodnoty pro útok a obranu). Toto zkoumání má smysl pouze tehdy poku je pole prázdné (nikdo sem ještě netáhl) Opět se budeme rozhodovat podle bodů v okolí. Projdeme tedy okolí podle výše uvedeného postupu. V případě, že je ve zkoumaném bodě v okolí prázdno, tak se nic neděje. Pokud je zde ale protivník opět musíme zjistit délku jeho řady. Také se hodí zjistit čím je zakončena, a jestli v opačném směru již také netáhl (tady ale pozor). Pomocí nějakého vztahu si určete hodnotu kterou zapíšete. Podobný postup, se aplikuje v případě že je to jeho vlastní značka. Vždy však ale budeme zapisovat pouze do souřadnice (x;y)! Problém... Problém může nastat v případě, že se hraje na okraji plochy. V ohodnocování se totiž v tomto případě budeme snažit číst data (ba někdy i dokonce zapisovat) z oblasti, která nám nepatří. Řešení však není tak složité, jak se na první pohled zdá. V podstatě stačí závezt funkci, která nám zkontroluje zda souřadnice jsou v "mezích". Také by se hodilo, aby se dala pužít v ohodnocování - tedy v případě že kontrolujeme v určité vzdálenosti a směru od výchozí souřadnice, a snad by se pro použití dali použít i implicitní hodnoty: inline bool JeVMezich(Souradnice Sor, int i=0, int j=0, int Vzdalenost=1) { if((0 <= Sor.x+i*Vzdalenost && Sor.x+i*Vzdalenost < Sirka) && (0 <= Sor.y+j*Vzdalenost && Sor.y+j*Vzdalenost < Vyska)) retrun TRUE; return FALSE; } Tuto funkci pak stačí vložit před každé čtení (zapis se provádí pouze na základě čtení). V jazyce C++ lze výhodně využít postupného vyhodnocování. Zapis while(Pole[Sor.x+Pocet*i][Sor.y+Pocet*j][0] == Hrac) tímto: while(JeVMezich(Sor, i, j, Pocet) && Pole[Sor.x+Pocet*i][Sor.y+Pocet*j][0] == Hrac). Vpřípadě kontroly pole mimo meze se cyklus automaticky ukončí. Závěr Tak to by snad mohlo byt vše pro začátek.. alespoň ukázání směru, kudy se ubírat. Není zde vysvětleno vše - všchny problémy, chyby, atd.. prostě začátek. Krom toho konec by asi neexistoval. Jinak pro ty, kteří se dočetli až sem, zde 11,633 kB jsou moje piškvorky...snažte se...:-). Kdo by chtěl kompletní zdorják, tak napište, pošlu.

Autor: Martin Bosak e-mail: some_one@seznam.cz web:

Nová soutěž na 3D Contestu CZ Czech 3D Contest Kurz Visual C++ (6.) Kurz Visual C++ (5.) C++ Builder - Design aplikací