Kombinace, variace, permutace

Přemýšleli jste někdy nad tím, kolik kombinací může vznikat v deskových hrách? Určitě vás to někdy alespoň napadlo. Obvykle je to tak velké množství, že z lidského pohledu je to nevyčerpatelné a tudíž "nekonečné". Ale podívejme se na to trochu blíž.

U některých her - jako je např. Amoriax - se dá počet možných herních pozic spočítat snadno, protože se nevyřazují kameny a jen se přeskládávají na hrací desce. Takže hledáme počet možných přeskládání těchto kamenů, tj. permutaci. Víme, že tam bude vždy 56 prázdných polí, 12 tmavých a 12 světlých kamenů a 1 červený. Celkově je tedy v Amoriaxu možných herních variant:

(56+12+12+1)! / (56!*12!*12!*1!)

= 3.55361255095E+28

 

Jinak matematicky vyjádřeno, možných variant (přesně):

35 536 125 509 403 000 000 000 000 000

 

Pokud bychom chtěli být zcela poctiví, pak v Amoriaxu vznikají kombinace kamenů, které jsou zrcadlově totožné a jsou v této sadě variant jsou započteny. Eliminujeme-li je, pak je jejich počet ještě dělitelný 4. Tzn.:

3.55361255095E+28 / 4

= 8.8840314E+27

 

U jiných deskových her je to obtížné nebo i polynomiálně (tj. algebraicky, nějakým vzorcem) nemožné spočítat. To se děje hlavně proto, že pravidla jsou natolik komplikovaná a rozsáhlá, že je nelze převést do algebraických podmínek. Např. u šachů se rádoby uvádí, že počet možných tahů v partii je víc než atomů ve vesmíru. To jsou ovšem marketingové repliky, které mají přitáhnout pozornost a málokdy se zakládají na pravdě. Odmyslíme-li fakt, že ani nevíme, jak je vesmír vlastně velký, tudíž logicky nemůžeme znát počet atomů v něm, počet možných herních pozic v šachu se pohybuje mezi 10E+43 až 10E+50. Ve skutečnosti jsou tam ale započteny stamiliardy zcela nelogických i naprosto naivních dětských tahů (např. nastrčení krále do matu apod.). V čísle 10E+120, o kterém se hovoří jako o tzv. Shannonově čísle, jsou započteny mnohonásobněkrát stejné pozice, ke kterým lze dospět jen různými cestami. Další stamiliardy jsou započteny byť sice legálních tahů, ale v praxi nerealizovatelných (např. nejsou známy partie, ve kterých by hráč proměnil 3 pěšce za 3 jezdce nebo 8 pěšců za 8 dam apod.). Pak máme celou polovinu pozic zrcadlově černými a bílými, tzn. ty samé pozice, které akorát vzniknou jednou s černými a podruhé s bílými figurkami, jinak jsou úplně stejné.

Také je třeba brát v úvahu, že dospěje-li partie ke zlomovému bodu, kdy hráč intuitivně vidí, že by při své maximální úrovni hru už nevyhrál (např. ztratí významně materiál), pak hru nedohrává a vzdá ji. Ta samotná partie by trvala možná ještě 10-30 tahů. Tím se cca polovina kombinací škrtá, protože jsou tam navíc a nedávají pro hru žádný rozumný smysl.

Jakmile se tedy na situaci podíváme z hlediska praktického, zjistíme, že šachy zdaleka tolik kombinací nemají a že se jejich kombinatorika záměrně přeceňuje.

 

Podobně je na tom středověká desková hra Mlýn. Uvádí se, že počet možných kombinací je 10E+50, ale víme, že počet možných platných tahů je jen 10E+10.

 

Mimochodem, počet možných tahů v partii, kterých je víc než atomů ve vesmíru, má teoreticky každá hra s deskou 8x8 či 9x9 polí, některé budou mít počet tahů dokonce víc než atomů v mnoha vesmírech, např. africké mankalové hry nebo čínské Go. U Go se mimochodem uvádí při počtu 19x19 průsečíků počet herních variant na 10E+800, což je třeba pro strojové výpočty bez zapojení hlubokých neuronových sítí absolutně mimo současné možnosti.

 

Počet možných kombinací Rubikovy kostky je opět jednoduché spočítat, protože se kostičky opět jen přeskládávají (čili jde o permutaci). Počet možných přeskládání Rubikovy kostky je:

= 43 252 003 274 489 856 000

 

Dá se tedy říci, že Amoriax má celkem 821 milionkrát více kombinací než Rubikova kostka.

 

Pokud jde o zahájení, tam se opět velmi těžko srovnává. Např. v šachu můžete zahájit partii 20 platnými tahy. V Amoriaxu hned 36 platnými tahy. Rozvoj partie v Amoriaxu se ale nevyvíjí stejně jako v šachu, protože oblast kolem středu se utahuje a počet kombinací, které dávají smysl, se spíš snižuje.

U šachů je to zase jinak. Počet kombinací se po nějakou dobu ve střední hře rozšiřuje, nicméně díky vyřazování figurek se zase snižuje (záleží na tom, kolik jich bylo vyřazeno) a hra postupně ztrácí na dynamice (některé věžové koncovky jsou doslova "nekonečné").

 

Koncovky jsou opět velká kapitola. V šachu - a jiných hrách s materiální disproporcí - se většinou stává, že ve chvíli, kdy dojde k výraznější materiální ztrátě, tak hra ztrácí smysl a soupeř ji automaticky vzdává. Takže další stamiliardy variant ve hře představují víceméně jen teoretickou větev, která se nerealizuje, neboť soupeř vidí, že už nemá šanci partii vyhrát a zbytečně by jí tak dohrával do konce.

V Amoriaxu jde výhradně o pozici a taktické postavení kamenů. Kombinací na středovém kříži je sice výrazně méně, ale těžko se dopočítává konec až ke korunovému tahu (člověk zvládne max. 4-5 tahů dopředu, dobří hráči i 7-10, ale ne o moc více). Vidět tak konečnou kombinaci, kde je ještě nějakých 12 tisíc možností, se tak (pro lidského hráče) stává prakticky nemožné.

 

Kombinatorika v deskových hrách je velké a krásné téma. Doufám, že vás zaujalo a těším se na vaše postřehy a obohacení!