7.5 Aplikace: simulace hry Hadi a žebříky

Existuje hra, kterou male deti miluji a jejich rodice nenavidi- Hadi a zebriky (v originale Snakes and ladders). Pravidla hry jsou jednoducha- kazdy hrac ma prave jednu figurku, kterou postavi na prvni pole hry. Hraci se pak po rade stridaji v tom, kdo hazi kostkou. Hrac, ktery prave hodil kostkou, posune svoji figurku o tolik poli, kolik mu na kostce padlo. Vitezem je ten hrac, ktery se jako prvni dostane na posledni, 100. pole. Hra je ozvlastnena specialnimi poli- kdo slapne na pole paty zebriku, ten se posune o dany pocet poli dopredu ("vyjede po zebriku"), kdo vsak slapne na hlavu hadovi, vrati se o dany pocet poli zpet ("sjede po hadovi"). Herni plan ukazuje obrazek 7.2

Obrázek 7.2: Koberec s deskovou hrou Snakes and ladders nabízený serverem Activities for elderly people with dementia and Alzheimer's, http://www.activitiestoshare.co.uk/snakes-and-ladders-floor-mat.

Už asi tušíte, proč děti hru milují: vše je dáno jen náhodou, jejíž zvraty jsou kvůli umístění žebříků a hadů často veliké, takže poslední hráč se může pár tahy vyšvihnout do začátku pelotonu, zatímco dosud první hráč může snadno spadnout na konec. Navíc hra trvá opravdu dlouho. Asi je také jasné, proč rodiče hru naprosto nenávidí: vlastně se nejedná o hru! Vše je dáno náhodou, chybí jakákoli interakce mezi hráči a hra může trvat neskutečně dlouho (nekonečně dlouho, zdá se znuděnému rodiči). Člověče nezlob se je proti této hře posledním výkřikem moderních strategických her.

Naším cílem bude nasimulovat deset tisíc krát průběh hry a zjistit, jaké je rozdělení počtu hodů potřebných k ukončení hry. Pro jednoduchost si problém zjednodušíme tak, že budeme uvažovat jen jednoho hráče. Dále budeme předpokládat, že k vítězství ve hře není potřeba se přesně trefit na 100. pole, ale že stačí se dostat na ně nebo za ně. Následně použijeme data ze simulace s jedním hráčem k odhadu počtu tahů, které potřebují k ukončení hry dva nebo tři hráči. Pro jednoduchost budeme předpokládat, že hra končí ve chvíli, kdy jeden z hráčů vyhrál, tj. že se nedohrává až do konce. (Nápověda: hráči nijak neinteragují.)

Začneme tím, že si první úkol rozebereme. Budeme potřebovat dvě proměnné: Zaprvé, proměnnou panacek, ve které budeme mít uložené pole, na kterém panáček stojí. Na začátku bude mít tato proměnná hodnotu 1. Zadruhé, budeme potřebovat proměnnou hody, kam si budeme zaznamenávat, kolik hodů už proběhlo. Počáteční hodnota této proměnné je samozřejmě 0.

Každá jednotlivá hra bude spočívat v opakování tří kroků: 1. Hodíme kostkou a posuneme panáčka o tolik kroků, o kolik bude potřeba. 2. Až se panáček posune, zkontrolujeme, na jakém poli figurka stojí: pokud je to žebřík, posuneme jej nahoru, pokud had, posuneme jej dolů, jinak jej necháme na místě. 3. Zvýšíme hodnotu počítadla hodů o 1. Tyto tři kroky budeme opakovat tak dlouho, dokud panáček nebude stát na poli 100 nebo za ním. Na konci si zapamatujeme, kolik hodů bylo k ukončení hry potřeba. Kód pro jednu hru tak bude vypadat nějak takto:

    panacek <- 1L
    hod <- 0L
    while (panacek < 100L) {
        hod <- hod + 1L
        panacek <- panacek + sample(6, size = 1)
        panacek <- pole[panacek]
    }

Funkce sample(6, size = 1) na předposledním řádku cyklu vrátí náhodné číslo z oboru 1, 2, …, 6 (tj. simuluje hod kostkou). Otázkou je, jak vyřešíme hady a žebříky. To je možné udělat celou řadů způsobů. Můžeme např. pro každého hada a žebřík napsat podmínku typu

if (panacek == 4)
    panacek <- 14

která posune panáčka ze 4. na 14. pole (1. žebřík). Já preferuji poněkud globálnější přístup, který ukazuje poslední řádek cyklu: vytvoříme vektor pole, který pro každé herní políčko řekne, kam se má panáček posunout. Pokud dané pole neobsahuje ani hada, ani žebřík, bude obsahovat svůj vlastní index. Proměnnou pole vytvoříme např. takto:

# inicializace hracího pole
pole <- 1:105
# -- žebříky
pole[4] <- 14L
pole[9] <- 31L
pole[20] <- 38L
pole[28] <- 84L
pole[40] <- 59L
pole[63] <- 81L
pole[71] <- 91L
# -- hadi
pole[17] <- 7L
pole[54] <- 34L
pole[62] <- 18L
pole[64] <- 60L
pole[87] <- 24L
pole[93] <- 73L
pole[95] <- 75L
pole[98] <- 78L

Nejdříve inicializujeme pole tak, aby platilo pole[i] = i, tj. aby hráč, který na toto pole šlápne, na něm i zůstal. Pak přidáme žebříky a hady. Všimněte si, že pole nemá 100 prvků, ale 105. To je proto, že panáček se může díky hodu kostkou dostat za 100. pole. Pokud bychom je neinicializovali, skript by skončil chybou. (Náš přístup k poli je poněkud nedbalý – pokud by se hrací pole zvětšilo, rostly by nároky na paměť počítače. Hra Hadi a žebříky se však, doufejme, nikdy nezvětší.)

Nyní tedy umíme zahrát jednu hru. Zbývá nám ji ještě deset tisíc krát zopakovat. To provedeme takto:

# počet simulací
N <- 1e4

# ... sem se vloží inicializace hracího pole...

# alokace vektoru výsledků
vysledek <- rep(NA, N)

# vlastní simulace
for (k in seq_len(N)) {
    # ... sem se vloží kód pro jednu hru
    vysledek[k] <- hod
}

Nyni nam staci cely kod spustit a vypsat popisne statistiky pomoci funkce summary() a pripadne vykreslit histogram rozdeleni poctu hodu pomoci funkce hist() (v kapitole 17 se naučíte kreslit hezčí grafy). Celý kód tedy vypadá takto:

# počet simulací
N <- 1e4

# inicializace hracího pole
pole <- 1:105
# -- žebříky
pole[4] <- 14L
pole[9] <- 31L
pole[20] <- 38L
pole[28] <- 84L
pole[40] <- 59L
pole[63] <- 81L
pole[71] <- 91L
# -- hadi
pole[17] <- 7L
pole[54] <- 34L
pole[62] <- 18L
pole[64] <- 60L
pole[87] <- 24L
pole[93] <- 73L
pole[95] <- 75L
pole[98] <- 78L

# alokace vektoru výsledků
vysledek <- rep(NA, N)

# vlastní simulace
for (k in seq_len(N)) {
    panacek <- 1L
    hod <- 0L
    while (panacek < 100L) {
        hod <- hod + 1L
        panacek <- panacek + sample(6, size = 1)
        panacek <- pole[panacek]
    }
    vysledek[k] <- hod
}

# shrnutí výsledků
summary(vysledek)
hist(vysledek)

Vysledky simulace ukazuje tabulka 7.1, rozdeleni poctu hodu potrebnych k ukonceni hry ukazuje obrazek 7.3. Průměrný počet hodů, potřebný k dokončení při v jednom hráči, je 47.9082; ve čtvrtině her však nebude stačit ani 61 hodů.

Tabulka 7.1: Souhrnné statistiky počtu hodů potřebných k ukončení hry Hadi a žebříky, pokud hraje jeden hráč.

Min.	1st Qu.	Median	Mean	3rd Qu.	Max.
8	25	39	47.9082	61	353

Obrázek 7.3: Rozdělení počtu hodů potřebných k ukončení hry Hadi a žebříky, pokud hraje jeden hráč.

Naším druhým úkolem je zjistit, kolik hodů kostkou by bylo potřeba, kdyby hru hrálo \(M > 1\) hráčů. Na první pohled by se mohlo zdát, že potřebujeme celou naši simulaci přepsat tak, aby v rámci každé dílčí hry hrálo \(M\) hráčů. To však vůbec není potřeba, a to díky tomu, že hráči ve hře nijak neinteragují. Pokud tedy hrají tři hráči, je to stejné, jako by nezávisle na sobě hráli tři hráči. Hra skončí, když kterýkoli z nich dojde na 100. políčko. Kolik hodů k tomu potřebuje, to máme uložené v proměnné vysledek. Přibližně správný odhad tedy můžeme získat tak, že z vektoru výsledek náhodně vybereme tři hodnoty (s opakováním) a z nich vezmeme nejmenší číslo (stanovili jsme si, že hra končí, když vyhrál první hráč). Tak zjistíme, kolikrát by musel hodit vítězný hráč. Jeho počet hodů musíme samozřejmě vynásobit počtem hráčů, protože ve skutečnosti každý hráč musel hodit tolikrát.

Pokud jsme estéti, můžeme ještě provést jistou korekci pro posledního hráče. Řekněme, že vítězný hráč hodil právě \(L\)-krát. Pokud hrají tři hráči, pak máme tři možnosti: 1) Vítězný hráč začínal hru; pak je celkový počet hodů \((L - 1) \times 3 + 1\). 2) Vítězný hráč házel jako druhý; pak je celkový počet hodů \((L - 1) \times 3 + 2\). A konečně 3) vítězný hráč házel jako poslední; pak je celkový počet hodů \(3L\). Každá z těchto možností se stala právě s pravděpodobností \(1/3\). Pokud tedy hrají tři hráči, musíme od jednoduchého výsledku získaného jako trojnásobek počtu hodů vítězného hráče odečíst s pravděpodobností \(1/3\) dvojku, s pravděpodobností \(1/3\) jedničku a s pravděpodobností \(1/3\) nulu. Obecně musíme odečíst \((M - 1) / 2\).

Tímto postupem zjistíme, jak dlouho by hrálo \(M\) hráčů v jedné konkrétní hře. Výsledkem je tedy opět náhodné číslo. Simulaci opět potřebujeme zopakovat (řekněme 10 000 krát), abychom dostali rozdělení počtu hodů.

Celou simulaci provedeme snadno takto:

# počet hráčů
hracu <- 3

# alokace vektorů výsledků
vysledek2 <- rep(NA, N)

# korekce počtu tahů (hráč, který hru ukončil nemusel hrát jako poslední)
korekce <- (hracu - 1) / 2

# vlastní simulace (bootstrap)
for (k in seq_len(N)) {
    vyber <- sample(N, size = hracu, replace = TRUE)
    vysledek2[k] <- hracu * min(vysledek[vyber]) - korekce
}

Nejdříve do proměnné hracu uložíme počet hráčů, v našem případě 3. Následně si předalokujeme vektor pro uložení výsledků simulace a spočítáme správnou korekci. Vlastní simulaci zopakujeme \(N\)-krát (10 000 krát). Při každé jednotlivé simulaci vybereme pomocí funkce sample() tři náhodná čísla z rozsahu \(1, 2, \ldots, N\) s opakováním. Tato čísla použijeme jako indexy k výběru tří náhodných délek hry z vektoru vysledek a s jejich pomocí spočítáme střední dobu délky hry tří hráčů. Nakonec se podíváme na souhrnné statistiky pomocí funkce summary() a na histogram pomocí funkce hist().

Tabulka 7.2 ukazuje zakladni statistiku pro tri hrace. Prumerny pocet nutnych hodu pri trech hracich vzrostl z 47.9082 na 74.4203; ve ctvrtine her vsak nebude stacit ani 92 hodu. Obrazek 7.4 ukazuje srovnani distribuce poctu hodu pri jednom a pri trech hracich. Takove obrazky se naucite kreslit v kapitole 17.

Tabulka 7.2: Souhrnné statistiky počtu hodů potřebných k ukončení hry Hadi a žebříky, pokud hrají tři hráči.

Min.	1st Qu.	Median	Mean	3rd Qu.	Max.
23	50	65	74.4203	92	329

Obrázek 7.4: Rozdělení počtu hodů potřebných k ukončení hry Hadi a žebříky, pokud hrají tři hráči.

Nas odhad distribuce poctu hodu nebude pri opakovani 10 000 krat uplne presny a pri kazdem spusteni vrati ponekud odlisne vysledky. Zvyseni presnosti muzete dosahnout zvysenim poctu simulaci, napr. na milion. Nas kod je mozne jeste zobecnit a doladit tim, ze je prepiseme pomoci funkci (viz kapitola 8) a funkce map_dbl() (viz kapitola 10).