Game of Chess

[ElDoRado1239]

Game of Chess

V průběhu práce na mém vlastním HTML5 herním enginu se snažím vždy čas od času vytvořit taky nějakou hratelnou hru. Rád bych se podělil o svoji nejnovější práci, šachy pro dva hráče. Verze 0.9 zatím neobsahuje multiplayer po síti, ale na tom se pracuje.
Za sprity musím poděkovat serveru Kotaku a jeho nástroji pro vytváření postaviček z dílků.

Tak snad pobaví.


Hrát na Facebooku (záložka na mé oficiální FB stránce) :
http://statictab.com/qw5fcg9

Nebo přímo na mém serveru:
http://www.eldorado1239.com/chess/frame.html



P.S. Hledáte někoho pro tvorbu HTML5 hry? Napište!

[if.then]

Pěkné, ale má to pár nedostatků, které hru překvapivě značně mění - pěšci mohou při dvojkroku jít přes figuru před nimi, nepovedlo se mi udělat rošádu, nedá se brát en passant, neexistují remízy. A začínání hráčem na vršku šachovnice je celkem nestandardní.

Jinak postavičky jsou super!
_________________
For guns and glory, go to www.ceske-hry.cz.
For work and worry, execute VC++.

[ElDoRado1239]

Moc díky za poznatky!

To jsem si vůbec nevšiml, těch pěšců - to nebyl úmysl. Speciální pohyby a oznamování šach/garde... tam momentálně vůbec nejsou. Dokončuju multiplayer po síti, tak pak hned začnu ladit bugy a dodělám ty speciální tahy.

[Houp]

Spíš by byla fajn alespoň "jednoduchá" AI.
_________________

[mar]

[Ladis]

[Houp]

[mar]

Ladis: Ano, chtěli jsme si hlavně vyzkoušet, jak moc je/není reálný prodej na appstore.
houp: Já netvrdím, že je to jednoduché Každý šachový program dnes používá alphabetu, u her, které jsou složitější co do větvení se tento algoritmus použít nedá. Např. pro go se používá monte carlo.
Jinak souhlasím, že pro normální hráče nemá smysl hrát naplno. Já jsem obtížnost řešil tak, že jsem do vyhodnocovací funkce přidával náhodnou chybu podle úrovně, ale hlavní problém je to vyladit tak, aby obtížnost byla opravdu plynule odstupňovaná, k tomu by bylo ale potřeba hrát spoustu her, aby se určilo relativní elo, tzn. alespoň 3000 her na úroveň, kde je chyba +- 10 elo.

[Houp]

Já jsem se "nedávno" vyvažování obtížnosti zabýval(v rámci diplomové práce). AI do šachů jsem neimplementoval, ale zkusil bych tam jednoduchou úpravu, běžně AI algoritmy u takových her vybírají dle heuristik nejlepší možný tah pro sebe. Co jen to upravi,t aby udržovali vyrovnanou hru? Tedy, aby AI hráč vybíral přednostně tahy, které vedou k minimalizaci rozdílu heuristik obou hráčů?

Samozřejmě tato varianta má svá úskalí a chtělo by to prozkoumat. Minimálně alespon na základě heuristiky umět určit, který tah je zcela iracionální a takové tahy neuvažovat. (Např., ve chvíli, kdy lidský soupeř neohlídá svou královnu, tak by neměl být další tah AI hráče předhození vlastní královny soupeři)

Pořád taková varianta umožňuje mít "statické obtížnosti", které by určovali, které z tahů už jsou iracionální, a které ne. (s vyšší obtížností by se díky tomu snižovala možnost adaptivity hráče, mohl by "hloupnout" míň a míň.
_________________

[mar]

Nápad je to zajímavý, ale mám obavu, že by to dopadlo tak, že poté, co bych ztratil dámu, by AI začala nesmyslně skákat a ztrácet tempo, jen aby náhodou nevyhrála.
Další možnost by byla vyhodnotit k nejlepších tahů a z nich podle obtížnosti vybírat, tj. řekněme vybrat tah, který není od nejlepšího horší, než nějaké n.
Tak nebo tak je ale potřeba hrát dost her, aby se určila skutečná síla jednotlivých úrovní a vyladit to.
Tady bohužel neexistuje zkratka, pokud to má být opravdu plynule odstupňované, tj. aby pravděpodobnost výhry vyšší úrovně byla vždy stejná vůči předchozí (např. rozdíl 100 elo znamená pravděpodobnost výhry lepšího hráče 64%, což je dost, takže by úrovně bylo potřeba odstupňovat řekněme po 50 elo).
Obecně si myslím, že by mělo být pravidlem, aby autoři lehce porazili svůj program na nejnižší obtížnost (pokud jsou velmi slabí hráči jako například já

[Houp]

Chtělo by to samozřejmě testnout a nějak tyto problémy vychytat.

Případně jsem se setkal s relativně jednoduchým DDA algoritmem:
AI hráč má určitou úroveň(0-100, případně jiné 50-100), která je dynamická a mění se v průběhu hry.

Vždy každé kolo:
AI ohodnotí všechny následující tahy(např. minimaxem), seřadí je dle jejich hotnoty a zahraje tah odpovídající jeho úrovni. (při úrovni 50 zahraje tah v polovině, při úrovni 75 zahraje tah ve 3/4 atd)

Po odehrání lidského hráče se updatne úroveň AI:
dle heuristiky se určí, kdo a jak vyhrává a dle toho se updatne úroveň AI. Možností je více. V nejjednudušší variantě vyhrává-li AI, sníží si inteligenci o jedna, v opačném případě si ji zvýší o jedna.

Tohle by mělo být o něco stabilnější než předchozí návrh. Zde nemůže hráč "rapidně zhloupnout"
_________________

[mar]

To zní dobře, nicméně tu je pořád pár drobných problémů.
A to jsou singulární tahy, tzn. pozice, kde jeden tah je výrazně lepší, než zbytek ostatních. Velmi jednoduchý příklad je výměna - pokud mi hráč vezme figuru, kterou já můžu dobrat (řekněme je krytá pěšcem), tak dobrání bude nejlepší tak, ale všechny ostatní budou výrazně horší (řekněme -3, protože přijdu o figuru), takže vybírat čistě na úrovni 50 prostřední nejlepší tah by v těchto pozicích těžce selhalo, ale myslím, že v tomto je potenciál.
Další problém s úplným vyhodnocením všech tahů je náročnost - ta bude výrazně vyšší, než vyhodnocení jednoho nejlepšího tahu - takže už tímto se síla AI dost výrazně sníží např. pro 4 nejlepší tahy trvá dosažení stejné hloubky u počáteční pozice 3x dýl. Branching factor moderních šachových programů je kolem dvou, tj. 2x rychlejší odpovídá zhruba 100 elo. Průměrná šachová pozice má kolem 30ti možných tahů.
Adaptivní obtížnost by mohla být zajímavá, samozřejmě za předpokladu, že by bylo dobře vyřešené to omezení síly AI.
Ještě jsem viděl použité jako omezení jednoduše limitovat počet prohledaných pozic, tam by šla určitě najít i nějaká funkce, která by aproximovala skutečnou sílu.