Pojedynek czarodziejów.
- NogaWeza
- Użytkownik
- Posty: 1481
- Rejestracja: 22 lis 2012, o 22:24
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 147 razy
- Pomógł: 300 razy
Pojedynek czarodziejów.
Mamy trzech czarodziejów: \(\displaystyle{ A,B,C}\), każdy z nich ma inną różdżkę:
- czarodziej \(\displaystyle{ C}\) zabija swoją różdżką ze skutecznością \(\displaystyle{ 90\%}\)
- czarodziej \(\displaystyle{ B}\) zabija swoją różdżką ze skutecznością \(\displaystyle{ 80\%}\)
- czarodziej \(\displaystyle{ A}\) ma do wyboru trzy, o skuteczności kolejno \(\displaystyle{ 60\%, 80\%, 100\%}\),
Pojedynek jest turowy, czarodzieje atakują się w kolejności \(\displaystyle{ A, B, C}\) i robią to pojedynczo (nie da się ustrzelić dwóch na raz). Dodatkowo zakładamy, że czarodzieje mają kompletne informacje o różdżkach przeciwników.
Nurtujące mnie pytania: różdżkę o jakiej skuteczności powinien wybrać czarodziej \(\displaystyle{ A}\), żeby mieć największe szanse na zwycięstwo? Jaka jest optymalna strategia - atakowanie najsilniejszego? Czy da się prawdopodobieństwa wyliczyć jawnie? Wydaje się, że drzewka probabilistyczne będą się rozrastać w nieskończoność, ale być może da się jakoś je pozamykać sumując szeregi geometryczne.
Przykładowo, jeśli \(\displaystyle{ A}\) wybierze \(\displaystyle{ 100\%}\) i zabije \(\displaystyle{ C}\), to \(\displaystyle{ B}\) strzeli w \(\displaystyle{ A}\) i ma \(\displaystyle{ 80\%}\) szans na zabicie, ale jeśli mu się nie uda, to \(\displaystyle{ A}\) go zabija i wygrywa - łącznie ma \(\displaystyle{ 20\%}\) szans na zwycięstwo z tą różdżką i grając optymalnie. Widać od razu, że gdyby \(\displaystyle{ A}\) zamiast w \(\displaystyle{ C}\) strzelił w \(\displaystyle{ B}\) miałby tylko \(\displaystyle{ 10\%}\).
A co się dzieje, gdy \(\displaystyle{ A}\) wybierze \(\displaystyle{ 60\%}\)? Być może jeśli strzeli w \(\displaystyle{ B}\) lub \(\displaystyle{ C}\), którzy są silniejsi od niego, to tamci w swoich turach będą próbować zabić się nawzajem, a \(\displaystyle{ A}\) zostawią w spokoju, dopóki oczywiście któryś z nich zabije tego drugiego. Wtedy \(\displaystyle{ A}\) w tym ostatecznym pojedynku będzie miał dość małe szanse, ale sumarycznie być może to prawdopodobieństwo będzie większe niż \(\displaystyle{ 20\%}\), które miał w pierwszym scenariuszu.
- czarodziej \(\displaystyle{ C}\) zabija swoją różdżką ze skutecznością \(\displaystyle{ 90\%}\)
- czarodziej \(\displaystyle{ B}\) zabija swoją różdżką ze skutecznością \(\displaystyle{ 80\%}\)
- czarodziej \(\displaystyle{ A}\) ma do wyboru trzy, o skuteczności kolejno \(\displaystyle{ 60\%, 80\%, 100\%}\),
Pojedynek jest turowy, czarodzieje atakują się w kolejności \(\displaystyle{ A, B, C}\) i robią to pojedynczo (nie da się ustrzelić dwóch na raz). Dodatkowo zakładamy, że czarodzieje mają kompletne informacje o różdżkach przeciwników.
Nurtujące mnie pytania: różdżkę o jakiej skuteczności powinien wybrać czarodziej \(\displaystyle{ A}\), żeby mieć największe szanse na zwycięstwo? Jaka jest optymalna strategia - atakowanie najsilniejszego? Czy da się prawdopodobieństwa wyliczyć jawnie? Wydaje się, że drzewka probabilistyczne będą się rozrastać w nieskończoność, ale być może da się jakoś je pozamykać sumując szeregi geometryczne.
Przykładowo, jeśli \(\displaystyle{ A}\) wybierze \(\displaystyle{ 100\%}\) i zabije \(\displaystyle{ C}\), to \(\displaystyle{ B}\) strzeli w \(\displaystyle{ A}\) i ma \(\displaystyle{ 80\%}\) szans na zabicie, ale jeśli mu się nie uda, to \(\displaystyle{ A}\) go zabija i wygrywa - łącznie ma \(\displaystyle{ 20\%}\) szans na zwycięstwo z tą różdżką i grając optymalnie. Widać od razu, że gdyby \(\displaystyle{ A}\) zamiast w \(\displaystyle{ C}\) strzelił w \(\displaystyle{ B}\) miałby tylko \(\displaystyle{ 10\%}\).
A co się dzieje, gdy \(\displaystyle{ A}\) wybierze \(\displaystyle{ 60\%}\)? Być może jeśli strzeli w \(\displaystyle{ B}\) lub \(\displaystyle{ C}\), którzy są silniejsi od niego, to tamci w swoich turach będą próbować zabić się nawzajem, a \(\displaystyle{ A}\) zostawią w spokoju, dopóki oczywiście któryś z nich zabije tego drugiego. Wtedy \(\displaystyle{ A}\) w tym ostatecznym pojedynku będzie miał dość małe szanse, ale sumarycznie być może to prawdopodobieństwo będzie większe niż \(\displaystyle{ 20\%}\), które miał w pierwszym scenariuszu.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Pojedynek czarodziejów.
Faktycznie, zakładając że B i C wiedzą jaką różdżkę ma A i że każdy z czarodziejów próbuje unicestwić tego który ma najbardziej morderczy przyrząd to wybór przez A najsłabszej różdżki daje mu ponad 1/3 szans na przeżycie.
A co gdyby A wybrał najsilniejszą różdżkę i tak ją zaczarował że jego strzał by chybił? B sadząc że A ma jedną ze słabszych różdżek zaatakowałby C. Ta strategia dałaby największe szanse A na przeżycie.-- 5 wrz 2018, o 13:55 --Ech, znów odpowiedziałem nie wczytawszy się w treść problematu.
A co gdyby A wybrał najsilniejszą różdżkę i tak ją zaczarował że jego strzał by chybił? B sadząc że A ma jedną ze słabszych różdżek zaatakowałby C. Ta strategia dałaby największe szanse A na przeżycie.-- 5 wrz 2018, o 13:55 --Ech, znów odpowiedziałem nie wczytawszy się w treść problematu.
oraz że czarodziejami nie kierują dawne urazy lub tajne sojusze.NogaWeza pisze: Dodatkowo zakładamy, że czarodzieje mają kompletne informacje o różdżkach przeciwników.
TakNogaWeza pisze: Jaka jest optymalna strategia - atakowanie najsilniejszego?
TakNogaWeza pisze: Czy da się prawdopodobieństwa wyliczyć jawnie?
Intuicja Cię nie zawodzi, można je zsumować.NogaWeza pisze: Wydaje się, że drzewka probabilistyczne będą się rozrastać w nieskończoność, ale być może da się jakoś je pozamykać sumując szeregi geometryczne.
- Dasio11
- Moderator
- Posty: 10226
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Pojedynek czarodziejów.
Na razie moim zdaniem pytanie nie jest ściśle postawione. Prawdopodobieństwo przeżycia czarodzieja \(\displaystyle{ A}\) po wybraniu przezeń ustalonej różdżki zależy od tego, którego czarodzieja zdecydują się zaatakować jego przeciwnicy. Skoro tej informacji brakuje w treści zadania, to na pytanie nie można odpowiedzieć.
Uprzedzając odpowiedź: "pozostali czarodzieje przyjmują optymalne strategie", zapytam od razu: co to znaczy optymalna strategia?
Uprzedzając odpowiedź: "pozostali czarodzieje przyjmują optymalne strategie", zapytam od razu: co to znaczy optymalna strategia?
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Pojedynek czarodziejów.
Strategia optymalna oznacza, że ci pozostali też potrafią liczyć swoje szanse. W szczególności, dla każdego z nich przegrywająca strategią jest zabicie "nie A", bo zginą w następnej rundzie
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Pojedynek czarodziejów.
Ale tak jest tylko wtedy gdy A wybiera różdżkę o 100% skuteczności.a4karo pisze:Strategia optymalna oznacza, że ci pozostali też potrafią liczyć swoje szanse. W szczególności, dla każdego z nich przegrywająca strategią jest zabicie "nie A", bo zginą w następnej rundzie
Prawdopodobieństwo przeżycia A w zależności od wyboru różdżki
\(\displaystyle{ P_A(100 \% )=20 \% \\
P_A(80 \% ) \approx 28,25 \% \\
P_A(60 \% ) \approx 33,46 \%}\)
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Pojedynek czarodziejów.
Jak nie jest idiotą (a nie jest), to co wybierze w sytuacji jeden na jeden?-- 5 wrz 2018, o 18:31 --Dla mnie nie jest jasne czy A wybiera jedną różdżkę "na zawsze", czy może je zmieniać w zależności od sytuacji
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Pojedynek czarodziejów.
Możliwość zmiany różdżki byłaby okolicznością niesprzyjającą A, gdyż będąc potencjalnie najsilniejszym czarodziejem zawsze będzie obiektem ataków B i C. Wtedy użycie słabszej różdżki przy pierwszym ataku zmniejsza jego szanse przeżycia w stosunku do użycia różdżki o skuteczności 100%.
- Dasio11
- Moderator
- Posty: 10226
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Pojedynek czarodziejów.
Zgadzam się z kerajsem odnośnie interpretacji, że wybór różdżki dokonuje się na początku i jest ostateczny.
Ta definicja nie rozwiązuje problemu. "Najlepsza strategia" dla czarodzieja \(\displaystyle{ A}\) jest zdefiniowana jako taka, która daje najwyższe prawdopodobieństwo przeżycia. Prawdopodobieństwo zależy od tego, jakie strategie przyjmą przeciwnicy. Powiedzmy, że przyjmą optymalne strategie, czyli takie, które zapewniają im największe szanse przeżycia. Ale te szanse znów zależą od strategii pozostałych czarodziejów, a więc wracamy do punktu wyjścia. Nie muszę chyba dodawać, że cykliczne definicje są niepoprawne i mogą prowadzić do sprzeczności.a4karo pisze:Strategia optymalna oznacza, że ci pozostali też potrafią liczyć swoje szanse.
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Pojedynek czarodziejów.
Jeżeli wybór różdżki jest ostateczny, to wydaje się, że strategie wszystkich graczy są zdefiniowane jednoznacznie.
Ciekawostka: jeżeli A wybierze najsłąbszą różdżkę, to jego optymalną strategią będzie gorąca modlitwa, aby w pierwszym strzale SPUDŁOWAĆ. (to dość klasyczne zadanie o rewolwerowcach )
Ciekawostka: jeżeli A wybierze najsłąbszą różdżkę, to jego optymalną strategią będzie gorąca modlitwa, aby w pierwszym strzale SPUDŁOWAĆ. (to dość klasyczne zadanie o rewolwerowcach )
- NogaWeza
- Użytkownik
- Posty: 1481
- Rejestracja: 22 lis 2012, o 22:24
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 147 razy
- Pomógł: 300 razy
Re: Pojedynek czarodziejów.
No to załóżmy, że wybór jest ostateczny. Co do strategii optymalnej, to niech będzie to taka strategia, której gracz nie chce zmienić na inną, bo wtedy jego szanse na przeżycie spadną, tak na przykład dla \(\displaystyle{ A}\) z najsilniejszą różdżką strategią optymalną jest atakować najsilniejszego (poza nim) czarodzieja, gdyby zrobił inaczej, to jego szanse spadłyby z \(\displaystyle{ 20\%}\) do \(\displaystyle{ 10\%}\) - taka luźna inspiracja teorią gier, tyle, że w tym przypadku gra jest turowa i potencjalnie nieskończona.
- Dasio11
- Moderator
- Posty: 10226
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: Pojedynek czarodziejów.
To jest ta sama definicja, jaka została już podana, i dotyczą jej te same zastrzeżenia. Nie można określić prawdopodobieństwa przeżycia czarodzieja stosującego daną strategię bez znajomości strategii pozostałych czarodziejów i nie można wyznaczyć optymalnej strategii dla czarodzieja bez znajomości tegoż prawdopodobieństwa.NogaWeza pisze:Co do strategii optymalnej, to niech będzie to taka strategia, której gracz nie chce zmienić na inną, bo wtedy jego szanse na przeżycie spadną,
Też myślę, że pojęcie optymalnej strategii ma sens w tym kontekście, ale trzeba pomyśleć głębiej, żeby sformułować dobrą definicję. Dopóki ktoś tego nie zrobi, zadanie pozostaje niedookreślone.
-- 6 wrz 2018, o 12:04 --
Pomyślałem trochę i wygląda na to, że przeceniłem głębię tego zadania.
Załóżmy, że wybór różdżki i strategie przeciwników są ustalone.
\(\displaystyle{ \bullet}\) Jeśli czarodziej \(\displaystyle{ A}\) zdecyduje się zaatakować czarodzieja \(\displaystyle{ B}\), to z prawdopodobieństwem \(\displaystyle{ p}\) (które oznacza skuteczność wybranej przez niego różdżki) zostanie w pojedynku z czarodziejem \(\displaystyle{ C}\), przy czym \(\displaystyle{ C}\) zaczyna, oraz z prawdopodobieństwem \(\displaystyle{ 1-p}\) chybi, zostając w pojedynku z \(\displaystyle{ B}\) i \(\displaystyle{ C}\) z kolejnością ataku \(\displaystyle{ B \to C \to A}\).
\(\displaystyle{ \bullet}\) Jeśli zaś zaatakuje czarodzieja \(\displaystyle{ C}\), to z prawdopodobieństwem \(\displaystyle{ p}\) zostanie w pojedynku z \(\displaystyle{ B}\), który zaczyna, i z prawdopodobieństwem \(\displaystyle{ 1-p}\) zostanie w pojedynku z \(\displaystyle{ B}\) i \(\displaystyle{ C}\) z kolejnością \(\displaystyle{ B \to C \to A}\).
Sensowność zadania ratuje fakt, że choć nie znamy szans czarodzieja \(\displaystyle{ A}\) na przeżycie w wypadku chybienia (a próbując je obliczyć, wpadamy w pętlę), to nie zależą one od wybranego celu, więc możemy porównać te szanse dla różnych wyborów biorąc pod uwagę tylko przypadek, gdy przy życiu zostaje dwóch czarodziejów. Wtedy optymalną strategią rzeczywiście okazuje się atakowanie silniejszego, aby zostać sam na sam ze słabszym. I choć wciąż uważam to podejście za matematycznie nieścisłe - bo heurystyczna obserwacja, że możemy pewien czynnik ominąć w obliczeniach, nie zwalnia od uprzedniego zdefiniowania tego czynnika - to teraz przynajmniej wydaje mi się przekonujące.
W związku z tym zaproponuję inny wariant: do walki staje \(\displaystyle{ n}\) czarodziejów numerowanych liczbami \(\displaystyle{ 1, \ldots, n}\), mających różdżki o celnościach \(\displaystyle{ p_1, \ldots, p_n \in [0, 1]}\) (celność oznacza prawdopodobieństwo zabicia wybranego celu). Zaczyna czarodziej o numerze \(\displaystyle{ 1}\), wybierając numer \(\displaystyle{ j \in \{ 2, \ldots, n \}}\) czarodzieja, którego zaatakuje. Jeśli trafi, to wybrany czarodziej ginie, a czarodziej pierwszy znów może wybrać cel. Jeśli zaś chybi, inicjatywę przejmuje czarodziej atakowany (tak jak w 1 z 10).
Zadanie polega na tym, żeby wyznaczyć optymalną strategię dla czarodzieja \(\displaystyle{ 1}\) przy założeniu, że pozostali czarodzieje postępują optymalnie.