Pojedynek cyborgów

[kihooj]

Jesteś cyborgiem A i stajesz do pojedynku na pistolety z dwoma innymi cyborgami B i C. Twoja skuteczność strzelecka została zaprogramowana na 33%. Cyborg B strzela z 50-procentową skutecznością, C zawsze trafia. Zasady pojedynku są następujące:

1) każdemu cyborgowi przysługuje jeden strzał w każdej rundzie,
2) kolejność strzelania - od najsłabszego do najlepszego (ty zaczynasz, potem B, ostatni C),
3) jeżeli jakiś cyborg nie żyje to go pomijamy, strzela następny w kolejności.

Jako jedyny z cyborgów kierujesz się rozumem. Jak postąpisz, żeby zmaksymalizować szanse przetrwania?

[smiechowiec]

Jeśli strzelę do B i przypadkiem go trafię wtedy C na pewno mnie wyeliminuje,
więc jedyne co mi pozostało to zacząć celować w C.
Jeśli uda mi się go wyeliminować mam jeszcze jakąś szansę z B jeśli on chybi.

[kornel-1]

smiechowiec napisał:

> Jeśli strzelę do B i przypadkiem go trafię wtedy C na pewno mnie
> wyeliminuje, więc jedyne co mi pozostało to zacząć celować w C.

No... można jeszcze strzelać w glebę albo na wiwat ;-)

k.

[kornel-1]

kornel-1 napisał:
> No... można jeszcze strzelać w glebę albo na wiwat ;-)

No chyba, że zaprogramowanie, zmusza cyborga zawsze do oddania strzału w
kierunku przeciwnika. Zastanawiam się teraz, co oznacza kierowanie się
"rozumem"? Rozumiem, ze oznacza to przyjęcie strategii maksymalnej szansy na
przeżycie. Ale czy ogranicza się do wyboru celu B lub C?
k.

[jacekstu]

zawszę celuje w cyborga C,
jeśli trafię to w kolejnych rundach mam 50% szans na przeżycie jeśli nie trafię
w cyborga B (jeśli trafię to oczywiście przetrwam)
natomiast jeśli nie trafięy to mam 50% szans na to, że zarówno cyborg B jak i C
nie będzie w ogóle do mnie celował a tym samym nie zginę

gdybyśmy natomiast celował do cyborga B i z 33% szansą go trafił to wówczas od
razu ginę zastrzelony przez cyborga C

oczywiście przy założeniu, ze wybór celu przez cyborgów B i C jest losowy, bo to
nie zostało ustalone w treści zagadki

[kornel-1]

jacekstu napisał:
> oczywiście przy założeniu, ze wybór celu przez cyborgów B i C jest
> losowy, bo to nie zostało ustalone w treści zagadki.

Hm. Czym kierują się B i C? Strzelają do przeciwnika o największej skuteczności?
Tak zakładam.
Zatem B będzie strzelać do C, zaś C - jeśli przeżyje - strzeli do B i go zabije.
Wówczas A strzeli do C zabijając go z prawd. 1/3 lub gdy chybi (2/3) - zostanie
zabity w następnej rundzie.
Jeśli w pierwszej rundzie C zostanie zabity, A i B będą się pojedynkować, aż do
bardziej prawdopodobnej śmierci A.

Co zrobi A? Ma do wyboru: strzelać do B, C lub celowo chybić...

k.

[jacekstu]

no niby celowe spudłowanie daje cyborgowi A wysokie prawdopodobieństwo (bo aż
1/6) na zwycięstwo, ale...
rozważmy następujący przypadek:
A nie trafia celowo w żadnego cyborga (pr=1)
B nie trafia w C (pr=1/2)
C trafia w B (pr=1)
A nie trafia w C (pr=2/3)
C trafia w A (pr=1)
Tak więc prawdopodobieństwo tego że A zginie wynosi tyle ile iloczyn
prawdopodobieństw pojedynczych zdarzeń czyli aż 1/3

Tak na prawdę najlepsze co może zrobić A to celować do B w celu trafienia ale
spudłować (nie celowo), wówczas prawdopodobieństwo zwycięstwa wynosi 1/6
natomiast prawdopodobieństwo tego, że zgonie 1/9

[Gość: Krzys]

chyba należałoby jeszcze uwzględnić, że może być więcej rund

Uzupełnienie

[kihooj]

Jak się okazało zadanko wymaga doprecyzowania, co niniejszym czynię.

1. Cyborgi B i C wybierają swój cel losowo.
2. W odróżnieniu od pozostałych cyborgów masz prawo świadomie chybić.

W związku z tym przy pierwszym strzale masz trzy możliwości:

a) strzelić w powietrze
b) celować w B
c) celować w C

Co wybierzesz?

[bigda]

kihooj napisał:

> Jak się okazało zadanko wymaga doprecyzowania, co niniejszym czynię.
>
> 1. Cyborgi B i C wybierają swój cel losowo.
> 2. W odróżnieniu od pozostałych cyborgów masz prawo świadomie chybić.
>
> W związku z tym przy pierwszym strzale masz trzy możliwości:
>
> a) strzelić w powietrze
> b) celować w B
> c) celować w C
>
> Co wybierzesz?


Czy strzelając w powietrze też ma 2/3 szansy, że w nie nie trafię (czyli trafię
a B lub C)?

[kihooj]

bigda napisał:

> Czy strzelając w powietrze też ma 2/3 szansy, że w nie nie trafię (czyli trafię
> a B lub C)

Nie.

[jacekstu]

nadal uważam, że najkorzystniej jest celować w B

[bigda]

jacekstu napisał:

> nadal uważam, że najkorzystniej jest celować w B


Czyja wiem. Jeśli spróbujesz strzelić w C i ci się uda, masz szansę, że B cię
nie trafi - w przypadku celnego strzału w B, C na pewno potem trafi.
Masz 33% skuteczności. Masz 1/3 szansy, że zginiesz w następnej rundzie.
Celujac w C masz 1/3 (szansa trafienia) * 1/2 (szansa trafienia przez B w
ciebie) = 1/6 szansy, że zginiesz w następnej rundzie (jeśli) LUB jeśli nie
trafisz w C 1/2 (szansa, ze B wybierze ciebie jako cel) * 1/2 (szansa, że trafi,
jeśli już wybierze) = 1/4 szansy, żeb zginąć.

[smiechowiec]

Przy takich możliwościach to dopóki jest 2 cyborgów strzelam w powietrze bo to
daje mi największą szansę przeżycia.
Udany strzał w B to pewny grób.
Udany strzał w C to pojedynek z B, który zaczyna B.
Po ewentualnej eliminacji jednego z cyborgów staje z nim do pojedynku i strzelam
jako pierwszy więc mam jakieś szanse.
Z cyborgiem B mógłbym nawet tak strzelać aż do wyczerpania magazynku.

[Gość: Krzys]

też myślę, że w powietrze daje największe szanse

[bigda]

C zmiecie i mnie, i B. Pierwsza sprawa o jakiej myślę, to wyeliminować C. Szanse
na to są większe, jeśli spróbuję. A jak się nie uda trafić, to B strzela tak
samo, jak po moim strzale w powietrze.

[kihooj]

Poniżej rozwiązanie, trochę długie, ale krócej nie potrafię.

Najpierw zauważmy, że tylko przy pierwszym strzale masz jakiś wybór. W drugiej rundzie uczestniczy zawsze dwóch cyborgów, jeżeli masz szczęście być jednym z nich, to nie pozostaje ci nic innego jak strzelać w przeciwnika.

Rozważmy więc pierwszy strzał. Są dwie możliwości: trafisz albo nie trafisz.

1) Jeżeli nie trafisz to nie ma znaczenia do kogo celowałeś.

2) Jeżeli trafisz, to lepiej, żeby to był C (zabicie B to twój koniec).

W związku z powyższym pozostają do sprawdzenia dwie możliwości: czy lepiej C trafić, czy nie trafić.

Przyjmijmy następującą notację:
ACx - A strzela do C i trafia
AC - A strzela do C i nie trafia

Załóżmy, ze zabiłeś C (ACx). Przeżyjesz, jeśli nastąpi następujący ciąg wydarzeń:
BA -> ABx
Prawdopodobieństwo, że to nastąpi wynosi:
1/2 * 1/3 = 1/6 = 0,17

Jest jeszcze szansa na:
BA -> AB -> BA -> ABx
1/2 * 2/3 * 1/2 * 1/3 = 1/36 = 0,056

i dalej
BA -> AB -> BA -> AB -> BA -> ABx

itd.

Ogólnie jest to suma szeregu 1/6 * 1/3^n , która wynosi 0,25.

A jakie masz szanse, jeśli C przeżyje?

1) BCx -> ABx i pochodne = 0,125 przy czym prawdopodobieństwo BCx wynosi tutaj 1/2 * 1/2 , gdyż B może wybrać cel.

2) BC -> CBx -> ACx = 0,125

To już jest razem 0,25 a dochodzi jeszcze:

3) BA -> CBx -> ACx = 1/24

czyli szanse przeżycia wzrastają o ponad 4 punkty procentowe, z 25 do około 29,2%

A skoro lepiej jest NIE trafić w pierwszym strzale, to strzelamy w powietrze.
Tak typowali Krzyś i Śmiechowiec, gratuluję i pozdrawiam wszystkich.
A teraz wracajmy do sporu o pogodę.

[bigda]

kihooj napisał:
> A jakie masz szanse, jeśli C przeżyje?
>
> 1) BCx -> ABx i pochodne = 0,125 przy czym prawdopodobieństwo BCx wynosi tu
> taj 1/2 * 1/2 , gdyż B może wybrać cel.
>
> 2) BC -> CBx -> ACx = 0,125
>
> To już jest razem 0,25 a dochodzi jeszcze:
>
> 3) BA -> CBx -> ACx = 1/24

Pewnie się pogubiłem, ale czy nie powinno tu być jeszcze opcji

CAx i game over?

Po moim strzale w powietrze B pudłuje, a jeśli tak C nie musi strzelać do B.
Może do mnie.

[kihooj]

bigda napisała:

> Pewnie się pogubiłem, ale czy nie powinno tu być jeszcze opcji
>
> CAx i game over?
>
> Po moim strzale w powietrze B pudłuje, a jeśli tak C nie musi strzelać do B.
> Może do mnie.

Pokazuję szanse na przeżycie A, więc bez BAx i CAx.

[marchewa4]

kihooj napisał:

> A jakie masz szanse, jeśli C przeżyje?
>
> 1) BCx -> ABx i pochodne = 0,125 przy czym prawdopodobieństwo BCx
wynosi tu
> taj 1/2 * 1/2 , gdyż B może wybrać cel.

Tu zgoda.

> 2) BC -> CBx -> ACx = 0,125

Ale tu juz nie. BC nastepuje z prawd. 1/4 gdyz B musi wybrac C (1/2)
i spudlowac (1/2), CBx z prawd. 1/2, bo C musi wybrac B i wreszcie
ACx z prawd. 1/3, bo A musi trafic, czyli razem w punkcie 2) wychodzi
1/4 * 1/2 * 1/3 = 1/24 = 0,0416666...

> To już jest razem 0,25 a dochodzi jeszcze:

Na razie jeszcze daleko do 0,25 ;-)

> 3) BA -> CBx -> ACx = 1/24

Tu zgoda, ale w sumie daje to:
1/8 + 1/24 + 1/24, czyli 5/24, a zatem 0,208333...

Pozdrowienia
M.

[marchewa4]

kihooj napisał:

> Załóżmy, ze zabiłeś C (ACx).

Ale nie zapominajmy, ze strzelajac do C mamy 1/3 szansy trafic!

> Przeżyjesz, jeśli nastąpi następujący ciąg wydarzeń:
> BA -> ABx
> Prawdopodobieństwo, że to nastąpi wynosi:
> 1/2 * 1/3 = 1/6 = 0,17
>
> Jest jeszcze szansa na:
> BA -> AB -> BA -> ABx
> 1/2 * 2/3 * 1/2 * 1/3 = 1/36 = 0,056
>
> i dalej
> BA -> AB -> BA -> AB -> BA -> ABx
>
> itd.
>
> Ogólnie jest to suma szeregu 1/6 * 1/3^n , która wynosi 0,25.

Ciagle pod warunkiem, ze trafilismy!!!
Jesli nie trafilismy, szansa jest taka jakbysmy nie strzelali w
ogole, w poprzednim poscie wyliczona na 5/24.
Czyli ogolnie szansa na przezycie przty celowaniu na poczatku w C
wynosi
1/3*1/4 + 2/3*5/24 = 8/36 = 2/9 = 0,22222...

Pozdrowienia
M.

PS. Wyniki te dosc dobrze zgadzaja sie z wynikami symulacyjnymi,
ktore uzyskaliscie...

>
> A jakie masz szanse, jeśli C przeżyje?
>
> 1) BCx -> ABx i pochodne = 0,125 przy czym prawdopodobieństwo BCx
wynosi tu
> taj 1/2 * 1/2 , gdyż B może wybrać cel.
>
> 2) BC -> CBx -> ACx = 0,125
>
> To już jest razem 0,25 a dochodzi jeszcze:
>
> 3) BA -> CBx -> ACx = 1/24
>
> czyli szanse przeżycia wzrastają o ponad 4 punkty procentowe, z 25
do około 29,
> 2%
>
> A skoro lepiej jest NIE trafić w pierwszym strzale, to strzelamy w
powietrze.
> Tak typowali Krzyś i Śmiechowiec, gratuluję i pozdrawiam
wszystkich.
> A teraz wracajmy do sporu o pogodę.

[kornel-1]

Na wstępie chciałbym się wytłumaczyć z moich uwag zawartych w dwóch postach a
dotyczących celowego chybiania.
Sześć lat temu podobną zagadkę rozwiązywaliśmy na forum:
forum.gazeta.pl/forum/72,2.html?f=514&w=4118966&a=4118966
Jednakże , żadem ze strzelców nie miał 100-procentowej skuteczności jak w
zagadce kihooja. W tamtej - ważną rolę odegrał pomysł, czy też możliwość
celowego spudłowania. Dlatego wtrąciłem żartobliwie swą uwagę o strzelaniu na
wiwat, nie wiedząc, czy to będzie właściwe rozwiązanie.
Podczas dyskusji odrzuciliśmy strategię strzelania A do B. Pozostało pytanie czy
lepie strzelać A -> O czy A -> C.

Jako człowiek słabo myślący i mający nikłe pojęcie o rachunku
prawdopodobieństwa, wolałem pobawić się w symulację pojedynku cyborgów, każąc im
uczestniczyć w tysiącach pojedynków.
Program w Fortranie znajduje się tutaj: kornel-2.webpark.pl/pojedynek.htm
Ponieważ miałem problem z obsługą funkcji random, skorzystałem z wartości
wygenerowanych funkcją los() w Excelu (liczby znajdują się w osobnym pliku
random.txt i są pobierane przez program pojedynek.exe).
Starałem się wyplenić ewentualne błędy. Ale... głowy nie dam ;-)

A oto wyniki dla 100.000 pojedynków:
A->0 przeżył: A - 20157 razy, B - 25901 razy, C - 53942 razy
A->B przeżył: A - 14289 razy, B - 16559 razy, C - 69152 razy
A->C przeżył: A - 21999 razy, B - 41773 razy, C - 36228 razy

Z grubsza rzecz biorąc, gdy A strzela w powietrze ma szansę 20%, gdy strzela w C
- szansa wzrasta do 22%.

A teraz możecie na mnie pokrzyczeć ;-)

Kornel

[bigda]

No właśnie tak mi cos mowilo, ze lepiej jednak do C.

[smiechowiec]

>Z grubsza rzecz biorąc, gdy A strzela w powietrze ma szansę 20%,
> gdy strzela w C
> - szansa wzrasta do 22%.

Potwierdza to rozwiązanie analityczne zaproponowane przez Fenixa
I strzelam w B:
Wygrywamy z pstwem 13.8%

II strzelam w C:
Wygrywamy z pstwem: 22.2%

III strzelam w powietrze:
Wygrywamy z pstwem 20.8%

[horpyna4]

Czyli pierwsze intuicyjne skojarzenie (wyeliminować tego, który
zawsze trafia) okazało się słuszne.
Skojarzyło mi się to trochę z Mrożkiem (Na pełnym morzu), gdzie
Średni podjął błędną decyzję. Bo trzeba było wspólnie z Małym
zadźgać Grubego. Więcej by zeżarli, a gdyby nie dotarli szybko do
lądu, to właśnie Średni miałby większą szansę przeżycia.

Tytułem uzupełnienia

[kornel-1]

W tamtej zagadce sprzed sześciu lat zasady były nieco inne - przeciwnicy
strzelali nie losowo lecz obierając najlepsze strategie (przy okazji poprawiam
się: najskuteczniejszy strzelec również miał 100% trafień).
Przeprowadziłem symulację modyfikując tak działanie programiku, by cyborg B i C
wybierał zawsze najsilniejszego przeciwnika, czyli B-C, C->Bx; A bez zmian (ma
wybór, no niby rozum ;-)).

Dla 100.000 pojedynków otrzymałem:

A->0 pozostanie A - 42048 razy; B - 25144 razy; C - 32800 razy
A->B pozostanie A - 27458 razy; B - 16048 razy; C - 56494 razy
A->C pozostanie A - 36141 razy; B - 42122 razy; C - 21737 razy

Jak widać, teraz bardziej "opłaca" się strzelać w powietrze za pierwszym razem:
42% szans na przeżycie A zamiast 36% przy celowaniu w C. Przy tych zasadach
szanse A ogólnie rosną w myśl zasady "gdzie dwóch się bije tam trzeci korzysta".
Zwróćmy uwagę, że z punktu widzenia B, zmiana zasad pojedynku nie ma znaczenia -
i tak ma najgorzej (o ile rozumek A nie będzie zbyt mały).

Kornel

[kihooj]

Przepraszam, że odgrzebuję stary wątek ale myślę, że mam coś istotnego do zakomunikowania. Otóż bardzo mi się spodobała metoda "brute force", zastosowana przez Kornela. Postanowiłem dokonać sprawdzenia jego wyników, a był na to tylko jeden sposób - napisać niezależny program robiący to samo.
Listing programiku, który popełniłem jest tu: kihooj.webpark.pl/pojedynek.html . Język to Object Pascal z Delphi, a właściwie z jego linuksowego odpowiednika - Lazarusa.

A oto porównanie wyników działania naszych programów dla 100 000 pojedynków:

A->0
A - 20157 razy, B - 25901 razy, C - 53942 razy (kornel)
A - 20632 razy, B - 24995 razy, C - 54373 razy (kihooj)

A->B
A - 14289 razy, B - 16559 razy, C - 69152 razy (kornel)
A - 13958 razy, B - 16680 razy, C - 69362 razy (kihooj)

A->C
A - 21999 razy, B - 41773 razy, C - 36228 razy (kornel)
A - 21955 razy, B - 41651 razy, C - 36394 razy (kihooj)

Jak widać zbieżność wyników jest ogromna, co świadczy chyba o tym, że są one prawidłowe. Dla miliona i więcej pojedynków wychodzi podobnie. Raczej nie jest możliwe, żebyśmy się w ten sam sposób pomylili, a to znaczy, że moje wcześniejsze rozwiązanie można o kant tyłka potłuc.

Pozdrawiam i dziękuję za zmotywowanie mnie do przypomnienia sobie programowania, może mi się jeszcze przyda.

[marchewa4]

Zerknij na moje posty pod Twoim rozwiazaniem.

Pozdrowienia
M.