Miesiąc: Kwiecień 2016

Probabilistyczny model poruszania się w grze Talisman: Magia i Miecz

/ Piotr / Dodaj komentarz

W tym wpisie postanowiłem zająć się problem związanym z grą planszową Magia i Miecz (współczesne wydanie nazywa się Talisman: Magia i Miecz)

Magia i Miecz to gra, w której każdy z graczy wciela się w postać jednego z poszukiwaczy wybierającego się na wyprawę po legendarną Koronę Władzy.
Plansza gry składa się z trzech krain: zewnętrznej, środkowej i wewnętrznej.

Źródło: fantasyflightgames.com

Źródło: fantasyflightgames.com

Przygodę rozpoczynamy w krainie zewnętrznej i tam raczej spędzamy większość rozgrywki. W każdej kolejce gracz rzuca kością i może poruszyć się o wylosowaną liczbę oczek w kierunku zgodnym lub przeciwnym do ruchu wskazówek zegara. W trakcie rozgrywki różne wydarzenia powodują, że chcemy dotrzeć na wybrane miejsce na planszy. Możliwość dotarcia na dane pole zależy od dystansu jaki musimy przebyć, rzutu kostką i naszej decyzji co do kierunku poruszania się. W sytuacji, gdyby nic nie zakłócało nam podróży, zwykle próbujemy dostać się w dane miejsce jak najkrótszą drogą. Problem, którym będziemy się zajmować to właśnie prawdopodobieństwo przejścia zadanego dystansu na planszy, podejmując decyzje o ruchu jak najkrótszą drogą. Na końcu wpisu zamieszczę tablice prawdopodobieństw, stworzone w Excel a w artykule przedstawię teoretyczny model poruszania się po planszy z decyzjami co do kierunku.

Schemat planszy krainy zewnętrznej wygląda następująco:

plansza

znajdują się na niej 24 pola, które będziemy numerować od 0 do 23.

Zacznijmy od tego jak będziemy rozumieć odległość. Za odległość między polem i oraz j będziemy przyjmować najmniejszą ilość pól, która pozwala dotrzeć z punktu i do punktu j (lub na odwrót) poruszając się w kierunku zgodnym lub przeciwnym do ruchu wskazówek zegara. Liczbę tę będziemy oznaczać d(i,j). Teraz mała dygresja dla matematyków.

Metryka  modulo m

Definiujemy odległość d_m na planszy (składającej się z m pól) wzorem d_m(i,j)=\min\{(i-j) \mod m, (j-i)\mod m\}. Okazuje się, że powyższa formuła definiuje metrykę w \mathbb{Z}_m. Oczywiście d_m(i,j)=0 zachodzi wtedy i tylko wtedy gdy i \equiv j \mod m oraz dla dowolnych j,i zachodzi własność symetrii d_m(i,j)=d_m(j,i). Aby dowieść, że d_m spełnia nierówność trójkąta wystarczy zauważyć, że w każdym przypadku, przy ustalonych i,j,k, zachodzi d_m(i,j)=d_m(i,k)+d_m(k,j) lub  d_m(k,j)=d_m(i,k)+d_m(i,j) lub d_m(i,k)=d_m(i,j)+d_m(k,j).Przypuszczam, że  tego rodzaju metryka jest specjalnym przypadkiem metryki na brzegu zbioru i może to wynika z jakichś ogólniejszych własności. Tak czy owak, w modelu będziemy korzystać z odległości określonej jako d=d_{24}.

Proces ruchu

Wracając do modelu, będziemy rozpatrywać zmienne losowe określające kolejne rzuty kostką
K_1, K_2, \dots K_n, \dots
w podstawowym modelu zakładamy oczywiście, że są one niezależne oraz, że z równym prawdopodobieństwem wypada na nich liczba od 1 do 6.
Będziemy również rozważać zmienne losowe obrazujące decyzje co do kierunku poruszania się w poszczególnych kolejkach
D_1, D_2, \dots D_n, \dots
o  wartościach w zbiorze \{-1,1\}.
Proces ruchu, który będzie określał pozycję na planszy po n kolejkach, definiujemy jako sumę wyników rzutu kostką w poszczególnych kolejkach przemnożonych przez decyzję co do kierunku (1 to poruszanie się zgodnie z ruchem wskazówek zegara , -1 to ruch przeciwny) i jeszcze to wszystko podzielone z resztą przez liczbę pól na planszy (bo zataczamy po niej kręgi), czyli krótko mówiąc:
R_N =\displaystyle \sum_{n=1}^N K_n D_n \mod 24,
Możemy proces też  wyrazić rekurencyjnie
R_{n+1}=R_n +K_{n+1} D_{n+1} \mod 24
R_0=0 – pole startowe dla ułatwienia przyjmujemy i_0=0.
Przyjmijmy, że cel podróży to pole j, skoro już to wszystko ustaliliśmy, możemy określić sposób podejmowania decyzji. Niech D_{n+1}(\omega)=1 gdy d(R_n(\omega)+K_{n+1}(\omega),j) \leq d(R_n(\omega)-K_{n+1}(\omega),j), co oznacza, że wybieramy kierunek zgodny z ruchem wskazówek zegara, gdy przemieszczenie  się w tym kierunku sprawi, że wylądujemy na polu, którego odległość od celu j jest niewiększa niż jak gdybyśmy poszli w przeciwnym kierunku. W pozostałym przypadku przyjmujemy D_{n+1}=-1.
Zauważmy, że w przypadku gdy dystans jest jednakowy preferujemy kierunek zgodny z ruchem wskazówek zegara. Wydaje mi się, że w tej sytuacji tak naprawdę możnaby przyjąć dowolny rozkład podejmowania decyzji, ale definiując w ten sposób będzie nam się po prostu łatwiej liczyło.
Proces ten jest w istocie jednorodnym łańcuchem Markowa, ale pominiemy wykazanie tego faktu, nie jest to zupełnie konieczne, aby skorzystać z odpowiedniego wzoru.Obliczymy teraz odpowiednie prawdopodobieństwo warunkowe:
P(R_{n+1}=i_{n+1}|R_{n}=i_{n})= \dfrac{P(R_{n+1}=i_{n+1},R_{n}=i_{n})}{P(R_{n}=i_n)}=

=\dfrac{P(K_{n+1} D_{n+1} \equiv i_{n+1}-i_n, R_n=i_n)}{P(R_n=i_n)}
i teraz nakreślmy sobie sytuację: stoimy na polu i_n i wypadło na kości tyle, że możemy dojść na pole i_{n+1} i chcemy dotrzeć do pola j lub przynajmniej się do niego zbliżyć. Zawsze jednak możemy pójść w przeciwnym kierunku, jeśli tamten będzie bliższy celu – wtedy prawdopodobieństwo, że wejdziemy na pole i_{n+1} wynosi 0 (Rys. 1. oraz Rys. 2.) .

Rys. 1.

Rys. 1.

Rys. 2.

Rys. 2.

W przeciwnym wypadku prawdopodobieństwo będzie wynosiło tyle ile prawdopodobieństwo wyrzucenia kostką odpowiedniej liczby oczek, musimy jeszcze wcześniej ustalić, czy na pole i_{n+1} dostaniemy się w wyniku ruchu zgodnie czy przeciwnie do ruchu wskazówek zegara (Rys. 3., Rys. 4.)

Rys. 3.

Rys. 3.

Rys. 4.

Rys. 4.

Tyle w kwestii budowania intuicji, wracamy do obliczeń:

\dfrac{P(K_{n+1} D_{n+1} \equiv i_{n+1}-i_n, R_n=i_n)}{P(R_n=i_n)}

=\displaystyle \dfrac{P(K_{n+1} \equiv i_{n+1}-i_n, D_{n+1}=1,R_n=i_n)+P(K_{n+1}\equiv i_n-i_{n+1}, D_{n+1}=-1, R_n=i_n)}{P(R_n=i_n)}.

Przekształcimy osobno powyższe prawdopodobieństwa występujące w liczniku. Najpierw dla sytuacji K_{n+1} \equiv i_{n+1}-i_n. Gdy d(i_{n+1},j)\leq d(2i_{n+1}-i_n,j), to D_{n+1}=1, zatem zdarzenie \{ \omega \colon D_{n+1}(\omega)=1 \} zawiera zdarzenie \{ \omega \colon R_n(\omega)=i_n, K_{n+1}(\omega) \equiv i_{n+1}-i_n \}. Oznacza to następującą równość:
P(K_{n+1}\equiv i_{n+1} - i_n, D_{n+1}=1,R_n=i_n)=P(K_{n+1}\equiv i_{n+1}-i_n, R_n=i_n).
W przeciwnym przypadku, tj. gdy d(2i_n-i_{n+1},j)<d(i_{n+1}, j), decyzja wyniesie D_{n+1}=-1 zatem
P(K_{n+1}\equiv i_{n+1} - i_n, D_{n+1}=1,R_n=i_n)=P(\emptyset)=0.

Analogicznie rozumujemy w sytuacji K_{n+1} \equiv i_n-i_{n+1}. Tym razem nierówność d(2i_n-i_{n+1},j) \leq d(i_{n+1},j) oznacza decyzję D_{n+1}=1, i co za tym idzie równość
P(K_{n+1} \equiv i_n-i_{n+1},D_{n+1}=-1, R_n=i_n)=0.
Natomiast w przypadku d(i_{n+1},j)<d(2i_n-i_{n+1},j), decyzja będzie wynosić D_{n+1}=-1, zatem
P(K_{n+1} =\equiv i_n -i_{n+1}, D_{n+1}=-1,R_n=i_n)=P(K_{n+1} \equiv i_n -i_{n+1}, R_n=i_n).

Doprowadziliśmy prawdopodobieństwa z licznika do wygodnej postaci, gdyż zdarzenia \{ K_{n+1}=k \} oraz \{R_n=i_n \} są niezależne, ponieważ R_n jest pewnym „produktem” rzutów kostką K_1, \dots K_n, które są niezależne. Zauważmy, że D_{n+1}=2\chi_{\{\omega: d(R_n+K_{n+1},j) \leq d(R_n-K_{n+1},j)\}}-1, gdzie \chi jest funkcją charakterystyczną zbioru.  Oznacza to, że R_n=f(K_1,K_2, \dots K_n) gdzie f jest pewną funkcją borelowską określoną przy pomocy złożeń, sum, iloczynów oraz funkcji charakterystycznych zbiorów mierzalnych. Mając na uwadze powyższe, można skorzystać z niezależności zmiennych losowych K_{n+1} oraz R_n i skrócić wszystkie P(R_n=i_n). Dzięki temu ostatecznie otrzymujemy, że prawdopodobieństwo przejścia, które próbujemy obliczyć jest następujące:

  1. Gdy d(i_{n+1},j)<d(2i_n-i_{n+1},j), to prawdopodobieństwo przejścia wynosi
    P(K_{n+1}\equiv i_{n+1}-i_n)+P(K_{n+1} \equiv i_n-i_{n+1})
    przy czym zawsze co najmniej jedno z powyższych prawdopodobieństw  będzie zerowe.
  2. Gdy d(i_{n+1},j)>d(2i_n-i_{n+1},j), to prawdopodobieństwo przejścia jest równe
    0
  3. W ostatnim przypadku, tj. gdy d(i_{n+1},j)=d(2i_n-i_{n+1},j), prawdopodobieństwo przejścia wynosi
    P(K_{n+1}\equiv i_{n+1}-i_n)

Dodatkowo zauważmy, że kostki mają identyczny rozkład zatem powyższa formuła określająca prawdopobieństwo nie zależy od n. Możemy więc przyjąć oznaczenie p_{il}=P(R_{n+1}=l|R_n=i).
Ostatecznie korzystając z równości
P(R_{n+1}=l)=\displaystyle \sum_{i=0}^{23} p_{il}P(R_n=i),
widzimy, że da się wykorzystać znany wzór macierzowy:
(P(R_n=0), P(R_n=1), \dots P(R_n=23) )=
=(P(R_0=0, P(R_0=1), \dots P(R_0=23) )P^n=(1,0,\dots 0)P^n
gdzie P=(p_{il})_{i=0,\dots 23, l=0, \dots 23}.
Po wprowadzeniu powyższego wzoru do Excela policzyłem ostatecznie prawdopodobieństwo przebycia dystansu j w ciągu co najwyżej n kolejek jako:
1-(1-P(R_n=j))(1-P(R_{n-1}=j)) \cdot \dots \cdot (1-P(R_0=j))
i tak dla wszystkich możliwych j oraz pewnej liczby kolejek n, co przedstawione jest w poniższej tablicy:
https://drive.google.com/file/d/0B4_zL3Fb5Co7bFptc1JsSmVxcHc/view?usp=sharing
Wnioski: szanse są dosyć małe, np. około 38,5% w ciągu 3 kolejek, o ile jesteśmy w zasięgu rzutu kostką.  A więc takie kluczenie dookoła celu przypomina próbę trafienia kluczem do zamka przez zataczająca sie osobę. :)