Czy jest taka możliwość, że dwóch graczy w karcianą grę "Wojna" nigdy się nie dogra? Że w kółko powtarzać się będą te same sekwencje kart? Napisałem w C++ symulację "Wojny" i raz na kilka tysięcy partii zdarza się partia, która trwa "w kółko".
0
0
Istnieje przynajmniej jedno badanie, które mówi, że:
We have managed to prove that in this case the mathematical expectation of the length of the game is finite.
Edit: za pierwszym razem nie doczytałem, że ten whitepapier opiera się na pewnym założeniu (Assume now that each player can seldom but regularly change the returning order.), które niekoniecznie musi być prawdziwe w przypadku Twojej implementacji (+ Twoja implementacja może zawierać również inne błędy, w tym np. nieprawidłowe wykorzystanie generatora liczb pseudolosowych, które mogą wpływać na postać rzeczy) - praktycznie jednak zasadnym założyć jest, że gra w wojnę jest skończona.
1
Zwróciłbym uwagę na zasady z https://pl.wikipedia.org/wiki/Wojna_(gra_karciana)
Pierwszy i drugi zawodnik równocześnie wykładają po jednej karcie i porównują ich wartości ([...]). Gracz mający kartę o wyższej wartości odbiera karty i kładzie je pod spodem swojej talii.
Nie wiem, czy jest jakaś zasada decydująca o kolejności kart odkładanych po wygranym starciu. Jeśli kolejność może być losowa, to ją zaimplementuj, o ile tego nie zrobiłeś.
Swoją drogą wojna to wyjątkowo głupia gra karciana. Gracze mają marny wpływ na wynik rozgrywki, więc o ile nie musisz się nią zajmować, to się nią nie zajmuj :]
4
Na oko może. Prosty przykład: mamy dwóch graczy, każdy ma 2 karty w ręce -> asa i dwójkę, w różnej kolejności. Pierwsze rozdanie wygrywa 1, drugie wygrywa 2 i wróciliśmy właśnie do sytuacji początkowej. Można tą sytuacje rozszerzyć na więcej kart, dla każdej parzystej liczby kart.
Dla nieparzystej trochę gorzej, bo mamy nieparzystą liczbę rozdań do wygrania, więc taka konstrukcja musiałaby by być dużo bardziej skomplikowana (tzn wymagałaby większej liczby rozdań i używania zebranych wcześniej kart), ale myśle że może być możliwa.
2
Tak na szybko, (zeby sobie latwo wyobrazic) jedna osoba ma karty po kolei od najwiekszej do najmniejszej najpierw pik potem trefl, druga tak samo ma kier potem karo. Jednemu i drugiemu skoncza sie karty i mamy remis.
1
Shalom napisał(a):
Na oko może. Prosty przykład: mamy dwóch graczy, każdy ma 2 karty w ręce -> asa i dwójkę, w różnej kolejności. Pierwsze rozdanie wygrywa 1, drugie wygrywa 2 i wróciliśmy właśnie do sytuacji początkowej.
Ten dowód wymaga szczęśliwego niedeterminizmu w ustawianiu kart na końcu talii, albo jakiegoś posortowania graczy. Jeżeli przyjmiemy, że najpierw na końcu talii kładę kartę swoją, a potem przeciwnika, to mamy taki przebieg
Moje karty ; karty przeciwnika
A2 ; 2A
2A2; A
A2; A2
Jak najpierw dam na końcu przeciwnika, a potem swoją, to mam symetryczne odbicie:
A2 ; 2A
22A; A
2A; 2A
To zadziała dopiero wtedy, gdy przyjmiemy, że najpierw kładę kartę pierwszego gracza, a potem drugiego:
A2; 2A
2A2; A
A2; 2A
Ale to taka naciągana reguła. Kiedyś ze znajomymi symulowaliśmy "najdłuższą partię" w wojnę i o ile tam było kilka tysięcy rozdań, to wszystkie były skończone. Niektórzy bawili się w jakieś dowody, jak wygenerować najdłuższą permutację, ale nie przypominam sobie, żeby ktokolwiek wykazał, że gra może być nieskończona.
1
Zauważyłem, że to zależy od tego w jakiej kolejności są zbierane karty ze stołu, tak jak sugerował @Spine . Jeśli zbiera się "od spodu" - wtedy każda partia musi się skończyć. Jeśli zbieramy "od góry" - wtedy zdarza się, choć bardzo rzadko, że partia idzie "w kółko". Na miliard rozegranych partii otrzymuję tylko tysiąc nieskończonych.
Program rozgrywa parę milionów partii na sekundę. Proporcje wygranych dla obu graczy wychodzą równiutko po połowie. Zainteresowanym mogę podesłać źródło w C++.
Dziękuję forumowiczom za zainteresowanie tematem.