Pojedynek czarodziejów.

Matematyczne łamigłowki i zagadki...
Awatar użytkownika
NogaWeza
Użytkownik
Użytkownik
Posty: 1479
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.

Post autor: NogaWeza » 5 wrz 2018, o 11:16

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.

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7793
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 237 razy
Pomógł: 3061 razy

Re: Pojedynek czarodziejów.

Post autor: kerajs » 5 wrz 2018, o 13:20

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.
NogaWeza pisze: Dodatkowo zakładamy, że czarodzieje mają kompletne informacje o różdżkach przeciwników.
oraz że czarodziejami nie kierują dawne urazy lub tajne sojusze.
NogaWeza pisze: Jaka jest optymalna strategia - atakowanie najsilniejszego?
Tak
NogaWeza pisze: Czy da się prawdopodobieństwa wyliczyć jawnie?
Tak
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.
Intuicja Cię nie zawodzi, można je zsumować.

a4karo
Użytkownik
Użytkownik
Posty: 18790
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 6 razy
Pomógł: 3179 razy

Re: Pojedynek czarodziejów.

Post autor: a4karo » 5 wrz 2018, o 14:30

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

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9329
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 2041 razy

Re: Pojedynek czarodziejów.

Post autor: Dasio11 » 5 wrz 2018, o 17:18

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
Użytkownik
Użytkownik
Posty: 18790
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 6 razy
Pomógł: 3179 razy

Re: Pojedynek czarodziejów.

Post autor: a4karo » 5 wrz 2018, o 18:02

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

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7793
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 237 razy
Pomógł: 3061 razy

Re: Pojedynek czarodziejów.

Post autor: kerajs » 5 wrz 2018, o 19:09

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
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
Użytkownik
Użytkownik
Posty: 18790
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 6 razy
Pomógł: 3179 razy

Re: Pojedynek czarodziejów.

Post autor: a4karo » 5 wrz 2018, o 19:28

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

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7793
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 237 razy
Pomógł: 3061 razy

Re: Pojedynek czarodziejów.

Post autor: kerajs » 5 wrz 2018, o 20:05

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%.

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9329
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 2041 razy

Re: Pojedynek czarodziejów.

Post autor: Dasio11 » 5 wrz 2018, o 20:35

Zgadzam się z kerajsem odnośnie interpretacji, że wybór różdżki dokonuje się na początku i jest ostateczny.
a4karo pisze: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
Użytkownik
Użytkownik
Posty: 18790
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 6 razy
Pomógł: 3179 razy

Re: Pojedynek czarodziejów.

Post autor: a4karo » 5 wrz 2018, o 21:30

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 )

Awatar użytkownika
NogaWeza
Użytkownik
Użytkownik
Posty: 1479
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.

Post autor: NogaWeza » 5 wrz 2018, o 21:48

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.

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9329
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 2041 razy

Re: Pojedynek czarodziejów.

Post autor: Dasio11 » 5 wrz 2018, o 22:33

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

ODPOWIEDZ