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.
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:
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 oraz
będziemy przyjmować najmniejszą ilość pól, która pozwala dotrzeć z punktu
do punktu
(lub na odwrót) poruszając się w kierunku zgodnym lub przeciwnym do ruchu wskazówek zegara. Liczbę tę będziemy oznaczać
Teraz mała dygresja dla matematyków.
Metryka modulo m
Definiujemy odległość na planszy (składającej się z
pól) wzorem
. Okazuje się, że powyższa formuła definiuje metrykę w
Oczywiście
zachodzi wtedy i tylko wtedy gdy
oraz dla dowolnych
zachodzi własność symetrii
Aby dowieść, że
spełnia nierówność trójkąta wystarczy zauważyć, że w każdym przypadku, przy ustalonych
, zachodzi
lub
lub
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
Proces ruchu
Wracając do modelu, będziemy rozpatrywać zmienne losowe określające kolejne rzuty kostką
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
o wartościach w zbiorze
Proces ruchu, który będzie określał pozycję na planszy po 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:
Możemy proces też wyrazić rekurencyjnie
– pole startowe dla ułatwienia przyjmujemy
Przyjmijmy, że cel podróży to pole , skoro już to wszystko ustaliliśmy, możemy określić sposób podejmowania decyzji. Niech
gdy
, 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
jest niewiększa niż jak gdybyśmy poszli w przeciwnym kierunku. W pozostałym przypadku przyjmujemy
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:
i teraz nakreślmy sobie sytuację: stoimy na polu i wypadło na kości tyle, że możemy dojść na pole
i chcemy dotrzeć do pola
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
wynosi 0 (Rys. 1. oraz 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 dostaniemy się w wyniku ruchu zgodnie czy przeciwnie do ruchu wskazówek zegara (Rys. 3., Rys. 4.)
Tyle w kwestii budowania intuicji, wracamy do obliczeń:
Przekształcimy osobno powyższe prawdopodobieństwa występujące w liczniku. Najpierw dla sytuacji Gdy
to
zatem zdarzenie
zawiera zdarzenie
Oznacza to następującą równość:
W przeciwnym przypadku, tj. gdy decyzja wyniesie
zatem
Analogicznie rozumujemy w sytuacji Tym razem nierówność
oznacza decyzję
i co za tym idzie równość
Natomiast w przypadku decyzja będzie wynosić
zatem
Doprowadziliśmy prawdopodobieństwa z licznika do wygodnej postaci, gdyż zdarzenia oraz
są niezależne, ponieważ
jest pewnym „produktem” rzutów kostką
, które są niezależne. Zauważmy, że
, gdzie
jest funkcją charakterystyczną zbioru. Oznacza to, że
gdzie
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
oraz
i skrócić wszystkie
Dzięki temu ostatecznie otrzymujemy, że prawdopodobieństwo przejścia, które próbujemy obliczyć jest następujące:
- Gdy
to prawdopodobieństwo przejścia wynosi
przy czym zawsze co najmniej jedno z powyższych prawdopodobieństw będzie zerowe. - Gdy
to prawdopodobieństwo przejścia jest równe
- W ostatnim przypadku, tj. gdy
prawdopodobieństwo przejścia wynosi
Dodatkowo zauważmy, że kostki mają identyczny rozkład zatem powyższa formuła określająca prawdopobieństwo nie zależy od Możemy więc przyjąć oznaczenie
Ostatecznie korzystając z równości
widzimy, że da się wykorzystać znany wzór macierzowy:
gdzie
Po wprowadzeniu powyższego wzoru do Excela policzyłem ostatecznie prawdopodobieństwo przebycia dystansu w ciągu co najwyżej
kolejek jako:
i tak dla wszystkich możliwych oraz pewnej liczby kolejek
, 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ę. :)