Pojedynek czarodziejów.

[NogaWeza]

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.

[kerajs]

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.

Dodatkowo zakładamy, że czarodzieje mają kompletne informacje o różdżkach przeciwników.

oraz że czarodziejami nie kierują dawne urazy lub tajne sojusze.

Jaka jest optymalna strategia - atakowanie najsilniejszego?

Tak

Czy da się prawdopodobieństwa wyliczyć jawnie?

Tak

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.

Intuicja Cię nie zawodzi, można je zsumować.

[a4karo]

Nieskończone drzewka pojawiają się tylko wtedy gdy A zginie. W przeciwnym razie jego 100% różdżka kończy sprawę.

[Dasio11]

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?

[a4karo]

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]

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

Ale tak jest tylko wtedy gdy A wybiera różdżkę o 100% skuteczności.

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 \%}\)

[a4karo]

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]

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]

Zgadzam się z kerajsem odnośnie interpretacji, że wybór różdżki dokonuje się na początku i jest ostateczny.

Strategia optymalna oznacza, że ci pozostali też potrafią liczyć swoje szanse.

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]

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 )

[NogaWeza]

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]

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ą,

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.

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.