Programování umělý inteligence

Dnes jsem musel oslavit významný krok v programování umělý inteligence v Naší hře. Napsal jsem stěžejní funkci která pomůže počítači odhadovat, jaký karty mají jeho soupeřové. (Nechci, aby se jim přímo podíval do karet. To by bylo podvádění.) Funkce je to rekurzívní. Dvanáct jednoduchejch řádků programu, ale je za tím 1,5 dne přemejšlení. Najít algoritmus, který by ty možný kombinace systematicky prošel a žádnou nevynechal, nebylo tak těžký protože byl rekurzivní, ale sepsat ho jako funkci mi dalo zabrat.

To, co jsem naprogramoval, řekne počítači všechny možný kombinace karet v rukou soupeřů. V Naší hře je před vynesením první karty 184 756 možností kombinací karet v rukou soupeřů. (Každý z hráčů totiž vidí svých 10 karet, a ví, které 2 karty byly odhozeny. Jeden soupeř má 10 z 20 zbylých karet a druhý soupeř má pak už jen to, co zbyde.) Z tohoto (z počítačovýho hlediska přehledně malýho) množství kombinací se v průběhu hry musí postupně vyškrtávat ty, který nezapadaj do průběhu sehrávky. Například není třeba zabývat se nadále možnostmi s žaludskými kartami v rukou soupeře, který nemohl ctít žaludskou barvu.

Zhruba polovinu času jsem musel věnovat stochastickým výpočtům. Karetní hry skýtají mnoho krásnejch matematickejch úkolů. Například jsem spočítal, že v Naší hře, tak jako v mariáši nebo skatu je 2 753 294 408 504 640 (2,75 biliard) možných rozdání (samozřejmě bez ohledu na pořadí karet). Nebo že sehrávek bez pravidel (kdy každý hraje libovolnout kartu) je přesně 2 375 880 867 360 000 (2,4 biliardy). Zatím nevím jak spočítat, kolik je možných sehrávek pokud se ctí barva. Je to totiž závislý na rozdání. Asi je třeba projít všechny možnosti a najít horní a dolní hranici. Ještě těžší by bylo to spočítat, kdyby se musela ctít barva a přebíjet (tak jako v Mariáši, v Naší hře se přebíjet nemusí.)

Úspěsný naprogramování jsem oslavoval tak, že jsem celou noc (8 hodin) nechal hrát počítač Naší hru. Zahrál 6,5 miliónů sehrávek (225 sehrávek za sekundu). Počítačový hráči zatím nepřemejšlej. Uměj jenom ctít barvu. Možnou kartu vybíraj náhodně. Jeden hráč tak v jedný hře uhraje průměrně 8 bodů. Z výpisu podrobných histogramů jsem zjistil, že systém bodování, který je v Naší hře zvýhodňuje štychy za 4 body. Vynásobím-li četnost štychů jejich bodovou hodnotou, jsou na tom nejlíp štychy za 4 body, hůř pak štychy za 3 nebo 5, pak za 2 nebo 6 bodů, a nejvíc podceněný jsou štychy za 1 nebo 7 bodů. Štychy za 1 bod se uhrajou často, ale jeden bod za ně je málo (rozhodně nejsou 4x častější než štychy za 4 body, aby se jim svou efektivitou vyrovnaly). Štychy za 7 bodů se podaří uhrát málokdy, a 7 bodů za ně je taky málo (jejich efektivita (četnost × hodnota) je zrovna tak malá jako u štychů za 1 bod).

Systém bodování zatím měnit nehodlám. Jsou to statistický výsledky náhodný hry a v reálu to je tak, že se nehraje náhodně. Počkám až jak se výsledky změní budou-li hrát inteligentnější přemejšlecí algoritmy.