Slide a lama solver - zitmen/slide-a-lama GitHub Wiki

Jedná se o přepis mého blogpostu ze dne 9.9.2011

Zřejmě znáte populární hru, jenž se proslavila prostřednictvím ICQ, zvanou Slide-a-lama. Jde o logickou hru pro dva hráče, kteří sdílí plochu 5x5 kamenů, na kterých jsou různé vzory. Střídavě do ní vsunují další kameny, čímž se snaží vytvořit řádky/sloupce se třemi, čtyřmi nebo pěti po sobě jdoucími kameny stejného vzoru. Existuje ještě pokerový mód, kde se skládají karetní kombinace jako ve hře poker.

Bohužel, i když se mi hra líbí, ji hraju opravdu mizerně a moje přítelkyně mě v ní drtivě poráží, což jako soutěživý člověk těžce nesu. Tomu je ale konec, protože jsem se rozhodl napsat si program, který bude hrát za mě a pěkně mého soupeře podrtí. Tento program jsem již dokončil a nyní Vám ho představím.

1. Taktika pro umělou inteligenci

Taktika vedoucí k vítězství je jednoduchá - stačí prozkoumat všechny tahy, které má hráč k dispozici - je jich pouze 15. Vzhledem k tomu, že kromě kostky, kterou v každém tahu manipuluji, znám ještě jakou kostku bude mít k dispozici soupeř a taky jakou kostku budu mít při příštím tahu já.

Když tedy zkouším 15 různých tahů, tak v každém tahu se podívám i na to, jak nejlépe dokáže na takový tah odpovědět soupeř - opět 15 možností a v každé této možnosti zkoumám, jak nejlépe bych na takový tah dokázal odpovědět ve svém dalším tahu já. Jasně je z toho vidět, že problém vede na prohledávání stavového prostoru, který tvoří úplný 15-ární strom hloubky 3, tedy 153 = 3375 stavů. To je dost malé číslo pro počítač, tudíž lze projít všechny tyto tahy, a to ve velice krátkém čase.

To, který z 15ti původních tahů bude vybrán jako nejlepší, se řídí podle skóre tahu, tedy: počet bodů mého prvního tahu - počet bodů soupeřova tahu + počet bodů mého druhého tahu. Ze všech 3375ti hodnot vyberu tu s nejvyšším skóre a tah, který tomuto výsledku náleží, prohlásím za optimální.

Nedostatky umělé inteligence:

• program sice počítá s komby, ale nenásobí body, které jimi vzniknout, tudíž by takto bylo možné počítač nachytat, když mu obětujeme třeba hrušky za 40b a v zásobě bude kombo zvonečků za 10b a banánů za 20b, tak počítač vyhodnotí, že soupeřův tah je za 30b, ale ve skutečnosti je za 50b (=10+2*20); sice zakomponování tohoto výpočtu do programu by bylo otázkou asi jedné minuty, ale tak dejme člověku šanci - stejně pravděpodobnost, že se to stane není zas tak velká
• zbytečná opatrnost v koncovce -- hra končí v okamžiku, kdy má jeden hráč alespoň o 300b více než jeho soupeř; program s tímto nepočítá, takže když by vyhrával o 290b a mohl dalším tahem vzít zvonečky za 10b a hru ukončit, tak si je nevezme například v případě, že soupeř může v dalším tahu zahrát švestky za 30b -- program totiž netuší, že už má soupeř na kahánku a že další tah už by se nekonal, takže ty zvonečky nevezme, jelikož se mu to zdá nevýhodné; tohle taky není nijak fatální (pro program), protože mu jen trvá o pár tahů víc než hráče dorazí; dodělat tam počítání skóre se mi už nechtělo, protože to není úplně primitivní, pokud bych nechtěl, aby to uživatel zadával ručně -- řekl bych, že za tu námahu to nestojí
• program počítá vždy s nejlepším možným tahem soupeře -- snadno se může stát, že ten bude táhnout jinak díky tomu, že vidí ve svém tahu kostku, kterou program v předchozím tahu vidět nemohl a tak se situace změnila a hráč může udělat tah, který počítač nemohl propočítat; tohle není ani chyba, protože je to pouze o štěstí a to se spočítat nedá

2. Realizace

Program jsem psal v C++ za použití Win32API. Nejkritičtější bylo zařídit interakci programu se hrou samotnou, protože hra beží jako Flashová aplikace vložená do ActiveX prvku Internet Exploreru a ten je vložen v okně ICQ.

Získání obsahu okna probíhá zjištěním handlu okna podle jeho titulku, následně čtením barev některých vybraných pixelů (vždy cca veprostřed každé kostky) - podle barvy tohoto pixelu je pak rozhodnuto, o který druh kostky se jedná, případně zda kostka chybí.

Následně je proveden výpočet nejlepšího tahu - výsledkem je souřadnice v okně, kam vložit kostku. Na tuto pozici přemístím kurzor a pomocí DirectInput (protože se jedná o Flashovou aplikaci, není možné použít systém zpráv systému Windows) pošlu oknu událost o kliknutí.

V programu je zabudovaná i detekce toho, kdo je na tahu - to se detekuje podle podkladu jména v horních rozích - aktivní hráč má bílý podklad.

3. "Gameplay"

Jak se program ovládá? Stačí ho spustit, pak spustit i Slide-a-lama (nebo obráceně, to je fuk), vybrat hru s automatovými kostkami (na pokerové není program dělaný). Následně je potřeba počkat až budete na tahu - když jste na tahu, napište do konzole velkými písmeny typ kostky, kterou budete táhnout (ta nemá statickou pozici, proto není zjišťována automaticky programem) - stiskněte ENTER a už to jede.

Dostupné jsou 2 módy přepínání hráčů: automatický sám detekuje, kdo hraje, takže není potřeba vůbec u počítače být, abyste vyhráli. Pak je tu manuální mód, kterému řeknete, že je na tahu krátkým (asi 0,5s) přidržením klávesy CTRL (konzolové okno nemusí být aktivní).

Zajisté si všimnete, že okno se hrou krade při tazích focus. Pokud tedy chcete být schopni u hry i chatovat, doporučuji manuální mód, protože ten automatický také vyžaduje focus, takže se kromě hry nedá nic jiného dělat.

Jinak je ovládání velice snadné...stačí se držet instrukcí, které program vypisuje, viz video. Tady se snažíme s hanakusem program potrápit, ale moc se nám to nedaří...

Nedostatky v ovládání, které jsem neřešil nebo nevyřešil:

• pokud jste v automatickém režimu a vyskočí vám informační bublina v nástrojové liště nebo vám přijde zpráva na ICQ nebo tak něco, tak se čekání zasekne, protože okno přijde o focus - v tom případě počkejte na svůj tah a podržte CTRL jako v manuálním módu a vše zas začne běžet tak, jak má
• občas nedojde k automatickému kliknutí, pouze se nastaví pozice pro vložení kostky - v módu hry, kde je každý tah omezen na 10s to vůbec nevadí, protože po vypršení tohoto časového limitu se kostka správně zasune; pokud hrajete mód bez časového intervalu, musíte kliknout ručně
• pokud jste v automatickém módu programu a zároveň hrajete hru bez časového limitu a potřebujete kliknout, musíte trochu intenzivněji poklikat (třeba 3x) -- okno totiž krade každých 500ms focus, takže se musíte trefit do tohoto intervalu - stačí tedy rychlý dvojklik nebo mít štěstí při jednokliku

Zní ty složitě, ale ty nedostatky jsou fakt jen malý blbinky. Přeci jen jsem to psal pro zábavu, takže se s tím nechci mořit do dokonalosti - obzvláště s ovládáním. To radši strávím čas nad vylepšováním umělé inteligence.

4. Závěrem

Program splnil účel, konečně vyhrávám. Navíc můžu mít čisté svědomí, že to není podvod, protože hra zkoumá intelekt hráče a já ten svůj použil takto, aneb proč mlátit do hřebíku rukou, když mám kladivo. Takže podvádět bude ten, kdo si to stáhne a použije proti někomu, koho se jemu nedaří porazit :P

Na místě je taky poděkování mému ACM parťákovi Martinu Hanákovi (hanakus), který mi pomohl s testováním - díky.

Odkaz ke stažení: Slide-a-lama_solver.exe

Zdrojový kód: solver.cpp