Mravce a šach 4 – OCK site

Translate/Share:

V mravenisku sa šach stal veľmi populárny, nanešťastie majú stále iba jednu šachovnicu. Problém dočasne vyriešili tak, ako ho riešia často profesionáli, teda naraz hrajú na jednej šachovnici štyri mravce.

Nedávno sa vo finále veľkého turnaja stretli štyria borci. Udeľovala sa iba prvá cena, ale tá stála za to, víťaz si mohol zahrať s majstrom sveta 4096 partií. Pretože sa jednalo o veľa, tak mali hrať viacero partií a prvý kto by dosiahol päť výhier (remízy sa nepočítali) by sa stal víťazom.

Najskôr ľahká otázka: Koľko (rezultatívnych) partií mohli za týchto podmienok odohrať minimálne a koľko maximálne?

Ťažká otázka: Zápas bol z neznámeho dôvodu predčasne ukončený za stavu 1:2:3:4 (Zelený:Červený:Modrý:Žltý). Je jasné, že nikto nedosiahol 5 výhier, a preto nemohol byť vyhlásený za víťaza. Ale aby cena neprepadla, tak riaditeľ turnaja rozhodol, že cenu rozdelí. Ako? Predpoklad je, že hráči boli a sú rovnako silní a každý má v každej ich vzájomnej partii šancu vyhrať \(\frac{1}{4}\).

Táto úloha je voľným pokračovaním úloh Mravce – šprintéri, Mravce – maratónci, Mravce a dúha, Mravce a šach a Mravce a šach 2.

Keďže ide o delenie, tak táto úloha súvisí aj s úlohami Úloha o polienkach, Úloha o polienkach 2 a Mravce a šach 3.

Riešenie

Minimálne odohrajú 1 rezultatívnu partiu (vyhrá žltý) a maximálne 7 (dostanú sa do stavu 4:4:4:4 a posledná partia rozhodne).

Z úlohy Mravce a šach 3 už vieme musíme uvažovať všetky možné situácie. Pretože musíme uvažovať 7 hier a v každej môže vyhrať ľubovoľný zo 4 hráčov, tak máme \(4^7 = 16 384\) možností. To je veľa na vypísanie všetkých možností a aj na graf.

Našťastie v dobe keď každý vie troška programovať nie je problém urobiť programček, ktorý to spočíta.

from itertools import product

hranica = 5
stav = (1, 2, 3, 4)

pocetHracov = len(stav)
maxPocetHier =  (hranica - 1) * pocetHracov - sum(stav) + 1

# hráčov číslujeme od 0 
vsetkyMoznosti = (x for x in product(range(pocetHracov), repeat = maxPocetHier))
    
pocetVyhier=[0] * pocetHracov
for moznost in vsetkyMoznosti:
    body = list(stav)
    for i in moznost:
        body[i] += 1
        if body[i] == hranica:
            pocetVyhier[i] += 1
            break

print([x for x in pocetVyhier])

from itertools import product

hranica = 5

stav = (1, 2, 3, 4)

pocetHracov = len(stav)

maxPocetHier = (hranica - 1) * pocetHracov - sum(stav) + 1

# hráčov číslujeme od 0

vsetkyMoznosti = (x for x in product(range(pocetHracov), repeat = maxPocetHier))

pocetVyhier=[0] * pocetHracov

for moznost in vsetkyMoznosti:

body = list(stav)

for i in moznost:

body[i] += 1

if body[i] == hranica:

pocetVyhier[i] += 1

break

print([x for x in pocetVyhier])

Pretože celkový počet situácií je 16 384, tak program vypíše [372, 1 148, 3 524, 11 340]. To sa dá vykrátiť 4 a dostaneme [93, 287, 881, 2 835], čo dá súčet 4 096.

Preto s majstrom sveta odohrá Zelený 93, Červený 287, Modrý 881 a Žltý 2 835 partií.

Ak by sme chceli týmto programom vypočítať úlohu Mravce a šach 3, tak stačí v ňom zmeniť stav na (2, 4).

Čo ak by sme zadanie zmenili a požadovali pre celkové víťazstvo 7 výhier. Táto malá zmena by spôsobila, že by sa počet možností zvýšil zo \(4^7=16\ 384\) na \(4^{15}=1\ 073\ 741\ 824\). To by veľmi predĺžilo výpočet a niektoré prostredia by to nezvládli a vypísali by chybu. Preto sa treba vrátiť k Pascalovi a k jeho myšlienke využívať stav, kde treba odohrať o partiu menej. Program bude využívať rekurziu.

from functools import cache

hranica = 7
stav = (1, 2, 3, 4)

pocetHracov = len(stav)

@cache
def f(i, s):
    if s[i] == hranica:
        return 1
    elif s[0] == hranica or s[1] == hranica \
    or s[2] == hranica or s[3] == hranica:
        return 0
    else:
        return (f(i, (s[0] + 1, s[1], s[2], s[3])) + \
                f(i, (s[0], s[1] + 1, s[2], s[3])) + \
                f(i, (s[0], s[1], s[2] + 1, s[3])) + \
                f(i, (s[0], s[1], s[2], s[3] + 1))) / pocetHracov

print([f(i,stav) for i in range(pocetHracov)])

from functools import cache

hranica = 7

stav = (1, 2, 3, 4)

pocetHracov = len(stav)

@cache

def f(i, s):

if s[i] == hranica:

return 1

elif s[0] == hranica or s[1] == hranica \

or s[2] == hranica or s[3] == hranica:

return 0

else:

return (f(i, (s[0] + 1, s[1], s[2], s[3])) + \

f(i, (s[0], s[1] + 1, s[2], s[3])) + \

f(i, (s[0], s[1], s[2] + 1, s[3])) + \

f(i, (s[0], s[1], s[2], s[3] + 1))) / pocetHracov

print([f(i,stav) for i in range(pocetHracov)])

Program počíta pravdepodobnosť výhry a vypočíta to okamžite.

Hráči si rozdelia výhru v pomere 0.05830810219049454 : 0.1273341104388237 : 0.26806915551424026 : 0.5462886318564415.

K rovnakému výsledku sa môžeme dopracovať aj využitím iných zaujímavých postupov z článku Thirteen Correct Solutions to the ‘‘Problem of Points’’ and Their Histories.

Napríklad využitím integrálu: \( \frac{\Gamma (18)} {\Gamma (6) \Gamma (5) \Gamma (4) \Gamma (3)} \int_1^{\infty} \int_1^{\infty} \int_1^{\infty} \frac{a^4 b^3 c^2}{(a+b+c+1)^{18}} \mathrm{d}a\text{ d}b\text{ d}c \), čo dá výsledok v tvare zlomku \(\frac{7\ 825\ 981}{134\ 217\ 728}\), čo znamená, že zelený hráč by vyhral iba \(7\ 825\ 981\) partií zo \(134\ 217\ 728\).

Alebo využiť vytvárajúce funkcie a pomocou napríklad Wolfram Mathematica \(\text{SeriesCoefficient}\left[\frac{a b c d}{\left(b-1\right) \left(c-1\right) \left(d-1\right) \left (a+b+c+d-4\right)}, \left\{a,0,6\right\}, \left\{b,0,5\right\}, \left\{c,0,4\right\}, \left\{d,0,3\right\}\right]\) dostať rovnaký výsledok ako vyššie.

Keep Reading