To znaczy tak mi się wydawało…
Motywacja
Domyślam się, że wśród dorosłych wojna nie jest zbyt popularna, chyba że mają dzieci. Grałem ostatnio ze swoją córką i zastanawiałem się, czy to się kiedyś skończy. Graliśmy w uproszczoną wersję: tylko pięć różnych kart, ale więcej powtarzających się, żeby “wojna” była częściej. Obstawiałem, że mimo tego uproszczenia będzie to trwało wieki, więc ustaliliśmy, że skończymy, jak coś tam się wydarzy.
Później stwierdziłem, że ciekawe byłoby policzyć, czy to naprawdę trwałoby wieki.
Monte Carlo
Jeśli ktoś nie słyszał o metodzie Monte Carlo, to najprościej przedstawić ją na przykładzie rzutu niesymetryczną monetą. Można próbować policzyć, jakie jest prawdopodobieństwo wyrzucenia orła, proponując fizyczny model monety i całego procesu rzucania. Jest to jednak bardzo trudne zadanie. Zamiast tego możemy po prostu rzucać taką monetą wielokrotnie i notować wyniki. Odsetek rzutów, w których wypadł orzeł, to oszacowanie szukanego prawdopodobieństwa. Możemy otrzymać praktycznie dowolnie dokładny wynik, zwiększając liczbę rzutów.
W praktyce najczęściej wykorzystujemy tę metodę, używając komputera do “rzucania”. Opisujemy jakiś proces losowy przy pomocy ulubionego języka programowania, następnie uruchamiamy go wielokrotnie i zliczamy, jak często zaszło jakieś zdarzenie. Użyłem tej metody np. do oszacowania prawdopodobieństw stanięcia na poszczególnych polach w Eurobiznesie oraz oszacowania długości gry w węże i drabiny. Natomiast możliwości wykorzystania są znacznie szersze, np. w szacowaniu całek.
Przyznam, że uwielbiam metodę Monte Carlo. Jak pomyślałem o tym, że ciekawe byłoby się przekonać, ile średnio trwa wojna – i natychmiast uświadomiłem sobie, że przecież umiem to oszacować – poczułem jakiś rodzaj wyższej przyjemności, ciężkiej do opisania.
Założenia
Przyjąłem, że gramy w dwie osoby talią 52 kart, bez jokerów. Musiałem założyć jakieś czasy trwania pojedynków, tzn. wyłożenia kart, porównania ich i zabrania. Do tego dochodzą wojny, w których każdy gracz wykłada w sumie trzy karty, środkową zakrytą. Zagrałem kilkadziesiąt pojedynków (tzn. wyłożeń kart) i wyszło mi, że zwykły pojedynek (bez wojny) trwa średnio 3,5 sekundy, a jeśli zakończy się wojną, to dodatkowe 10 sekund (najwięcej zabiera odwrócenie kart na drugą stronę). Wojna może być dłuższa, gdy znów jest remis (“podwójna wojna”) i założyłem, że trwa to kolejne 10 sekund. W praktyce raczej trochę mniej, choć taka sytuacja jest na tyle rzadka, że nie ma dużego wpływu na ostateczny wynik. Im gra jest dłuższa, tym te czasy mogą się zmieniać, ale zignorowałem ten fakt. Z jednej strony z powodu zmęczenia gra może zwolnić, ale z drugiej z racji znudzenia możemy przyspieszyć, żeby szybciej skończyć.
Gra trwa do czasu, gdy któryś z graczy straci wszystkie karty. Założyłem, że jeśli jest wojna i brakuje nam karty do wyłożenia, to też przegrywamy. Teoretycznie może wystąpić remis: gracze mają tyle samo kart i cały czas jest wojna. W takiej sytuacji dla talii 52 kart każdemu będzie brakować ostatniej, by tę wojnę rozstrzygnąć — i zakładam, że mamy wtedy remis. Jest to BARDZO mało prawdopodobne: gracze muszą mieć co drugą kartę taką samą. Z szacunkowych obliczeń wyszło mi, że prawdopodobieństwo wynosi mniej więcej jeden na 20 biliardów.
Jak się jednak okazało, remisy mogą wystąpić z innego powodu.
Sposób odkładania kart
Jest jeszcze jedno założenie, przez które z jednej strony zacząłem żałować, że w ogóle zająłem się tym tematem, ale z drugiej uzyskane wyniki okazały się zaskakujące. Gdy wygramy zwykły pojedynek lub wojnę, w jaki sposób zbieramy karty? Zakładam, że pod spód, ale w jakiej kolejności? Najpierw naszą kartę (czyli kartę wygranego gracza, silniejszą), a potem przeciwnika (słabszą) czy odwrotnie? I jaką metodę stosuje przeciwnik?
Okazało się, że ma to ogromne znaczenie. Póki co przedstawiam wyniki w sytuacji, gdy najpierw kładę pod spód mocniejszą kartę, a przeciwnik postępuje tak samo. Dla uproszczenia będę pisał o mocniejszej i słabszej karcie, natomiast w przypadku wojny przez mocniejsze karty rozumiem wszystkie przez nas wyłożone (którymi wygraliśmy), a przez słabsze wszystkie przeciwnika.
Wyniki
Wykonałem 100 tysięcy symulacji, poniżej rozkład czasów trwania całej gry w minutach. Szerokość słupka to 5 minut, ograniczyłem oś X do 100 minut.
Typowe gry trwają od 9 do 27 minut (rozstęp kwartylowy), mediana jest równa 16 minut. Najkrótsza gra trwała trochę poniżej 2 minut, a najdłuższa ponad 3 godziny. Tak długie gry to jednak rzadkość i jedynie 3% trwało dłużej niż godzinę. Dodajmy też, co nie jest zaskakujące, że połowę gier wygrał jeden z graczy, połowę drugi.
Szczerze mówiąc, spodziewałem się dłuższych czasów. Cóż, gdy jest się dzieckiem, czas biegnie inaczej. Poza tym te założone przeze mnie czasy pojedynków są pewnie dłuższe u dzieci. Natomiast jak później pokażę, być może to nie jest jedynie kwestia poczucia czasu.
Taki sam rozkład otrzymamy, jeśli obaj gracze będą stosować inną metodę kładzenia kart: najpierw karta słabsza, potem mocniejsza. A co się stanie, jeśli pomieszamy te metody, tzn. ja będę chował najpierw mocniejszą kartę, a przeciwnik słabszą? (Innymi słowy, obaj kładziemy moją kartę jako pierwszą, niezależnie od wyniku). Poniżej rozkład czasów gry przy takiej metodzie naniesiony na poprzedni.
Gry trwają znacznie dłużej… To znaczy te, które się zakończyły. Na wykresie nie widać najważniejszego: został on narysowany jedynie dla około 17,5% gier, gdyż pozostałe wciąż trwają!
Cykle
Okazuje się, że przy takiej metodzie kładzenia kart otrzymujemy cykle: po jakimś czasie układ kart się powtarza. W takich przypadkach gra nigdy nie zostanie ukończona.
Większość cykli identyfikowałem jawnie, tzn. sprawdzałem, czy układ kart jest taki sam, jak któryś z poprzednich. Natomiast w pojedynczych przypadkach długość takiego cyklu była ekstremalna, np. wynosiła ponad 200 tysięcy pojedynków (przy przyjętych założeniach oznacza to, że dopiero po około 210 godzinach otrzymałem układ kart, który już wcześniej wystąpił). Ostatecznie, żeby symulacje nie trwały zbyt długo, założyłem, że jeśli liczba pojedynków przekracza 10 tysięcy, to mamy do czynienia z cyklem.
Podsumowując, przy takiej metodzie kładzenia kart, w 82,5% przypadków gra nigdy się nie skończy. W takim razie moje wspomnienie, że gra w wojnę ciągnie się nieskończoność, może mieć solidniejsze podstawy!
Losowe odkładanie kart
Rozważmy jeszcze jedną metodę odkładania kart: robimy to losowo, tzn. czasem najpierw kładziemy pod spód mocniejszą kartę, czasem słabszą. Tak naprawdę jest to cały zbiór metod, bo możemy odkładać kartę mocniejszą lub słabszą z dowolnym prawdopodobieństwem. Załóżmy na razie, że wynosi ono 50%.
Sprawdźmy najpierw przypadek, gdy obaj gracze stosują taką metodę. Okazuje się, że czas gry jest trochę dłuższy niż w przypadku, gdy obaj gracze kładli albo najpierw silniejszą kartę, albo najpierw słabszą. Poniżej wykresy gęstości czasu trwania (na histogramach trudno odróżnić losową metodę od “najpierw silniejsza”).
Połowa gier trwa od 13 do 40 minut, mediana to 23 minuty. Prawdopodobieństwo, że gra potrwa dłużej niż godzinę, wynosi ok. 12%. Odnotujmy też, że przy takiej metodzie nie są możliwe cykle.
A jeśli pierwszy gracz konsekwentnie kładzie najpierw silniejszą kartę, a drugi robi to losowo? Czas jest praktycznie taki sam, jak wyżej, natomiast prawdopodobieństwo wygranej pierwszego gracza zwiększa się do 64%! Gdy pierwszy gracz odkłada najpierw słabszą kartę, a drugi wciąż losową, prawdopodobieństwo też jest większe od 50%, choć niewiele (55%). Innymi słowy, właśnie odkryliśmy STRATEGIĘ gry w wojnę.
Trzeba od razu zaznaczyć, że ta strategia zadziała, jeśli przeciwnik będzie losowo odkładał karty – a ciężko go do tego zmusić. Jeśli jednak nie zna on zaprezentowanych tu wyników oraz kładzie karty pod spód konsekwentnie (nielosowo), to ta jego konsekwencja zapewne będzie opierać się nie na sile karty, ale na jej położeniu na stole czy podłodze. Na przykład jako pierwszą będzie brał do ręki kartę po swojej lewej stronie. Możemy to wykorzystać, kładąc swoją kartę losowo po lewej lub po prawej stronie. Trzeba to zrobić szybko, żeby przeciwnik musiał dostosować się do tego układu.
Problem w tym, że nie jest to naturalny sposób gry w wojnę, bo najłatwiej kłaść karty zawsze w tym samym miejscu. Przez to przeciwnik może się domyślić, że coś kombinujemy. Ale to tym lepiej: możemy mu wtedy opowiedzieć o metodzie Monte Carlo.
Czy da się lepiej?
Wcześniej założyłem jednakowe prawdopodobieństwa (równe 50%) odłożenia albo mocniejszej, albo słabszej karty jako pierwszej. W praktyce, jeśli przeciwnik odkłada karty losowo, najpewniej będzie miał jakieś preferencje, tzn. te prawdopodobieństwa będę różne od 50%. Oznaczmy przez p prawdopodobieństwo odłożenia najpierw słabszej karty. My odkładamy jako pierwszą zawsze silniejszą. Na poniższym wykresie prawdopodobieństwo wygranej w wojnę w zależności od p.
Prawdopodobieństwa są oszacowane dla p od 0% do 95% co 5 p.p., od 95% do 100% zrobiłem to dokładniej. Jak widać, prawdopodobieństwo wygranej może być jeszcze wyższe: wynosi ok. 70%, jeśli przeciwnik odkłada karty losowo, ale zwykle słabszą (w 80-90% przypadków). Co ciekawe, przy jeszcze bardziej regularnym odkładaniu słabszej karty prawdopodobieństwo naszej wygranej zaczyna spadać. Gdy przeciwnik robi tak zawsze, jest mniejsze od 10%, ponieważ zaczynają występować cykle (choć dodajmy, że prawdopodobieństwo wygranej przeciwnika też jest wtedy tak samo niskie).
Dodajmy, że im częściej przeciwnik odkłada słabszą kartę jako pierwszą, tym dłużej trwa cała gra. Dla p równego 80% zwykle od 22 do 73 minut.
Wnikliwy Czytelnik może się jeszcze zastanawiać, czy te niższe prawdopodobieństwa wygranej dla p powyżej 90% nie wynikają z tego, że wykrywam cykle. Zauważmy, że układ kart może się powtórzyć, ale to nie będzie oznaka cyklu, bo przez dodanie losowości nie może on wystąpić (wystarczy, że p będzie minimalnie mniejsze od 100%). Dlatego zwiększyłem maksymalną liczbę pojedynków potrzebnych do zakończenia gry z 10 tysięcy do 100 tysięcy, żeby takich pozornych cykli nie wykrywać.
Podsumowanie
Efekt kolejności kładzenia kart (wzrost prawdopodobieństwa nawet do 70%) jest naprawdę duży. Jak to wyjaśnić? Co prawda wydaje się logiczne, że jeśli najpierw odłożę silniejszą kartę, to szybciej pojawi się ona w grze, ale na pierwszy rzut oka jest to niewielka różnica. Natomiast ważne jest, że po pierwsze, postępujemy w ten sposób za każdym razem, a po drugie, pojedynków (a więc i okazji na zastosowanie tej metody) jest w wojnie bardzo dużo. Przy 24 kartach gra trwa krócej i zysk stosowania opisanej strategii jest mniejszy: maksymalne prawdopodobieństwo wygranej wynosi ok. 56%. Z kolei przy 104 kartach (dwie talie) możemy dojść do 86%.
Z drugiej strony, zauważmy, że nawet przy stosowaniu strategii, w której zawsze odkładamy słabszą kartę, a przeciwnik losową (z prawdopodobieństwem 50%), prawdopodobieństwo wygranej wynosi 55%, czyli jest większe niż 50%. Co więcej, jeśli przeciwnik rzadziej odkłada słabszą kartę (w 10-20% przypadków), wygrywamy z prawdopodobieństwem 60%! Z tego wynika, że równie ważna jest konsekwencja, a nie tylko kolejność. Co więcej, powinniśmy dostosować strategię do tego, co robi przeciwnik: czy częściej odkłada jako pierwszą słabszą czy mocniejszą kartę.
Gdyby ktoś chciał poeksperymentować, udostępniam kod w języku R. Jest sporo rzeczy, które można jeszcze sprawdzić, np. inne metody odkładania kart. Możemy naprzemiennie kłaść słabszą lub mocniejszą kartę, podejmować tę decyzję na podstawie jakiegoś zdarzenia lub stosować taką kolejność, żeby dostosować się do kart przeciwnika.
Warto też dodać, że w praktyce, nawet jeśli chcielibyśmy odkładać karty “losowo”, to nie jesteśmy w stanie robić tego tak, jak w wykonanych tutaj symulacjach. Bo rzecz nie tylko w tym, żeby np. w 80% przypadków wybierać słabszą kartę. Założyłem, że robimy to niezależnie (dokładnie: losuję kartę z tzw. rozkładu dwumianowego). Człowiek nie potrafi “sam z siebie” losować w taki sposób, potrzebujemy do tego jakiegoś narzędzia: monety, kostki czy generatora liczb pseudolosowych. Dlatego warto byłoby sprawdzić, na ile różne wyniki otrzymamy, jeśli przeciwnik będzie wybierał karty nie w sposób losowy, ale “niby-losowy” (choć nie jest łatwo zaproponować odpowiedni model).
Gdy ktoś chciał więcej poczytać na ten temat, poniżej kilka publikacji:
- Winning at War: Comparing different strategies in a card game
- When Will (Game) Wars End?
- Finiteness in the Card Game of War
- Combinatorial Aspects of the Card Game War
W tej pierwszej też rozważane są różne strategie, które zwiększają prawdopodobieństwo wygranej, choć autor założył trochę inne zasady gry oraz uwzględnia jedynie przypadek p równego 50%.