Otázka:
Jaký je přibližný počet jedinečných pozic přidaných každou praktickou šachovou partií?
newshutz
2014-03-06 21:24:48 UTC
view on stackexchange narkive permalink

Průměrný počet tahů v šachové hře je asi 40. To by bylo průměrně asi 80 pozic v každé hře, ale mnoho pozic je sdíleno mezi hrami. Více sdílení nastává na začátku a na konci hry.

Při hraní her vznikají nové pozice. Když přidáváme nové hry do databáze šachových her, kolik nových pozic přidá každá hra?

Pokud jde o pravděpodobnost, je-li počet nových pozic přidaných hrou náhodná proměnná, jaký je očekávaná hodnota?

Praktickým výsledkem této odpovědi může být, jak velký klíč by tabulka pozic v databázi potřebovala.

Díky ~ 3M lichess hrám na nízké úrovni je to přibližně 85% jedinečných (odlišných) pozic ve 3M hrách. Udělal jsem několik testů a montážní funkce je velmi blízká 1.06-0.0128 * ln (num_games). Takže ~ 3% relativní nárůst po 10krát více her. U her na vyšší úrovni je pravděpodobně méně jedinečných pozic, alespoň na nižších vrstvách.
@Sopel váš komentář může být základem skutečné odpovědi na tuto otázku. Můžete rozšířit, prosím, včetně očekávané délky hry atd.?
Dva odpovědi:
Thomas Cleberg
2014-03-07 19:44:22 UTC
view on stackexchange narkive permalink

Celkový počet možných pozic v šachu se odhaduje na 10 ^ 43, takže klíč by musel být extrémně velký.

Pokud jde o to, kolik nových pozic byste mohli očekávat od postupného načítání hry , to by velmi záviselo na aktuálním stavu databáze. Například: první hra by nutně měla být všechny nové pozice, druhá by sdílela alespoň jednu pozici s první (výchozí pozice) a mohla by jinak buď úplně duplikovat první hru, nebo se úplně odchýlit.

Zdá se jisté, že jak vaše n stoupá o pozice, očekávaná hodnota nových pozic z postupně načtené hry by výrazně poklesla. Pokud jste nějakým způsobem načetli každou šachovou partii, kterou jste kdy hráli (nahranou nebo jinak), očekávání nové pozice nastávající v další načtené hře by bylo skutečně velmi malé.

Počet praktických pozic je poměrně menší než 10 ^ 43. Otázkou je růst nových pozic, jak se skutečné hry přidávají do databáze.
Chápu - i když je poměr z praktického hlediska tak malý jako jedna z milionu možných pozic, klíč by stále vyžadoval schopnost zvládnout až 10 ^ 38 jedinečných pozic.
V současné době mají velké databáze miliony her, 10 ^ 7 x 10 ^ 2 pozice na hru pro 10 ^ 9 pozic. TWIC v roce 2013 měl něco přes 200 000 her, což by v horším případě přidalo asi 2 x 10 ^ 7 pozic.
Omlouvám se - moje chyba byla v tom, že jste si mysleli, že jste odpovědí zamýšleli nové jedinečné pozice.
Ano, chci znát počet nových pozic přidaných praktickou hrou. Mám přiblížení pro celkové pozice v nových hrách.
Tihomir Georgiev
2014-03-08 15:21:24 UTC
view on stackexchange narkive permalink

Typické velké databáze jako chessbase, chess-db.com atd. obsahují celkem až 10 milionů šachových her, což je zhruba 500 milionů pozic. Pokud je tedy chcete nějakým způsobem kódovat / vyjmenovat, vyžadovalo by to alespoň 32bitový klíč.

Na druhou stranu něco jako Zobristův hash (viz toto nebo this) je jednosměrná zatřiďovací funkce považovaná za dobře fungující při kódování šachové pozice v 64 bitech bez kolizí.



ⓘ
Tyto otázky a odpovědi byly automaticky přeloženy z anglického jazyka.Původní obsah je k dispozici na webu stackexchange, za který děkujeme za licenci cc by-sa 3.0, pod kterou je distribuován.
Loading...