8
$\begingroup$

Alice, Bob and Charles are involved in a deadly three way duel game.

Before the game starts, the referee prepares three guns for the players to choose from. She randomly picks three guns from a very large collection of guns whose hit probabilities are randomly distributed between $0$ and $1$. She then examines the hit probabilities of her picks, and honestly labels them "the best", "the mediocre" and "the worst" accordingly.

The players know how the referee picked and labeled the guns. But the guns' exact hit probabilities are only revealed to them AFTER they've made their choices. The game then begins with the following rules:

  1. Each player takes turns to shoot. In your turn, you can either shoot at another player, or pass your turn.
  2. To be fair, the player with the worst gun will go first, followed by the mediocre gun, and the best gun is the final one to shoot. This cycle is repeated until only one player survives.
  3. Each player is intelligent, selfish and malicious. This means they calculate how to shoot to maximize their own surviving probabilities, but if shooting and passing give the same surviving probability, they would choose to shoot.

Given Alice is the only lady, she is allowed to choose her gun first.

Question: Which gun is her best choice? The best, the mediocre or the worst?

Hint:

It is never optimal for the mediocre or the best guns to pass turns.


Update: Without further constraints, the hint is not necessarily true. The "malicious" requirement in rule 3 seems insufficient. I didn't expect or intend that. I've provide a "bug version" (or lateral-thinking, depending on your perspective) solution in my answer. It seems the only way to avoid this is to change the rules and allow only the worst gun the right to pass.

$\endgroup$
  • 1
    $\begingroup$ Does this answer your question? Help understanding the solution to a "shooting puzzle" $\endgroup$ – Kate Gregory May 1 at 14:18
  • $\begingroup$ @KateGregory It does not. That answer applies only when you know exact hit probabilities. But here you must choose your gun based on the information "best, mediocre and worst" only, before you know the exact hit probabilities. $\endgroup$ – Eric May 1 at 14:26
  • 2
    $\begingroup$ ok, then take a look at puzzling.stackexchange.com/questions/2153/… for the general case, not only of unspecified accuracies, but of more than 3 shooters $\endgroup$ – Kate Gregory May 1 at 15:09
  • 3
    $\begingroup$ Are you sure this question has an elegant solution? There probably exists a complicated but straightforward solution using game theory, but is that what you're expecting? It would help if you can prove the claim in the hint, so we're confident that an elegant solution does indeed exist $\endgroup$ – ghosts_in_the_code May 1 at 15:12
  • 1
    $\begingroup$ What is the purpose of passing? In which scenario would that ever increase the probability of survival in a game with lethal weapons? $\endgroup$ – Ian MacDonald May 1 at 19:26
3
$\begingroup$

Update: found the bug in my pass code that was skewing statistics. It didn't change my final answer, but the probabilities come in much, much closer. This also makes me think if I can work out an optimization for worst passing, it could catch that last percent difference and make it the best choice.

The answer is

The Mediocre!

I may or may not have written a simulation to test this several million times in different variations to help me...

If the worst passes every time, then mediocre still has a roughly 34% chance to win, compared to 32% and 33%.

Run 1:
The best's win count: 321451
The mediocre's win count: 344495
The worst's win count: 334054

Run 2:
The best's win count: 321761
The mediocre's win count: 343515
The worst's win count: 334724

Run 3:
The best's win count: 322009
The mediocre's win count: 343636
The worst's win count: 334355

and,

If the worst doesn't ever pass, mediocre has a roughly 48% chance to win, with the difference split between the other two options. This option should be eliminated as a possibility given the players ability to pick the optimal strategy (worst passing).

Run 1:
The best's win count: 260989
The mediocre's win count: 479366
The worst's win count: 259645

Run 2:
The best's win count: 261143
The mediocre's win count: 479403
The worst's win count: 259454

Run 3:
The best's win count: 260462
The mediocre's win count: 479958
The worst's win count: 259580

Code below for those who are curious/might have some input to improve.

<?php

    $o1_win_count = 0;
    $o2_win_count = 0;
    $o3_win_count = 0;
    $i=0;
    //$check1 = 0;
    //$check2 = 0;
    while($i < 1000000){
        $o1 = array('hc'=>0, 'status'=>"");
        $o2 = array('hc'=>0, 'status'=>"");
        $o3 = array('hc'=>0, 'status'=>"");
        $i++;
        $v1 = rand(0,10000)/10000;
        $v2 = rand(0,10000)/10000;
        $v3 = rand(0,10000)/10000;
        if($v1 > $v2 && $v1 > $v3 && $v2 != $v3){
            $o1['hc'] = $v1;
            if($v2 > $v3){
                $o2['hc'] = $v2;
                $o3['hc'] = $v3;
            }
            else{
                $o2['hc'] = $v3;
                $o3['hc'] = $v2;
            }
        }
        elseif($v2 > $v1 && $v2 > $v3 && $v1 != $v3){
            $o1['hc'] = $v2;
            if($v1 > $v3){
                $o2['hc'] = $v1;
                $o3['hc'] = $v3;
            }
            else{
                $o2['hc'] = $v3;
                $o3['hc'] = $v1;
            }
        }
        elseif($v3 > $v1 && $v3 > $v2 && $v1 != $v2){
            $o1['hc'] = $v3;
            if($v1 > $v2){
                $o2['hc'] = $v1;
                $o3['hc'] = $v2;
            }
            else{
                $o2['hc'] = $v2;
                $o3['hc'] = $v1;
            }
        }
        else{
            $i--;
            continue; //duplicate random values, restart this attempt
        }
        // o1 is "the best", o2 is "the mediocre", o3 is "the worst"
        while($o1['status'] == "" || $o2['status'] == "" || $o3['status'] == ""){
            $hit = rand(0,10000)/10000;
            //option 3 goes first, aims at option 1 if alive, 2 if 1 is dead, unless passing
            $pass = 0;
            //$diff1 = $o2['hc'] - $o3['hc'];
            //$diff2 = $o1['hc'] - $o2['hc'];
            /*if($o3['hc'] >= .32){ //change these out as desired, I was just doing guess and check to watch win count change for reference - could've missed possibilties in my guess and check
                $pass = 1;
            }*/
            $pass = 1;
            if($pass == 1){
                if($o2['status'] == "dead" || $o1['status'] == "dead"){ //skip as worst if all players in the game
                    if($o3['status'] != "dead" && $o3['hc'] >= $hit){
                        if($o1['status'] != "dead"){
                            $o1['status'] = "dead";
                            if($o2['status'] == "dead"){
                                $o3['status'] = "alive";
                                $o3_win_count++;
                            }
                        }
                        elseif($o2['status'] != "dead"){
                            $o2['status'] = "dead";
                            $o3['status'] = "alive";
                            $o3_win_count++;
                        }
                        else{
                            //shouldn't get here
                            $o3['status'] = "alive";
                            $o3_win_count++;
                        }
                    }
                }
            }
            else{
                if($o3['status'] != "dead" && $o3['hc'] >= $hit){
                    if($o1['status'] != "dead"){
                        $o1['status'] = "dead";
                        if($o2['status'] == "dead"){
                            $o3['status'] = "alive";
                            $o3_win_count++;
                        }
                    }
                    elseif($o2['status'] != "dead"){
                        $o2['status'] = "dead";
                        $o3['status'] = "alive";
                        $o3_win_count++;
                    }
                    else{
                        //shouldn't get here
                        $o3['status'] = "alive";
                        $o3_win_count++;
                    }
                }
            }
            $hit = rand(0,10000)/10000;
            //option 2 goes second, aims at 1 if alive, 3 if 1 is dead
            if($o2['status'] != "dead" && $o2['hc'] >= $hit){
                if($o1['status'] != "dead"){
                    $o1['status'] = "dead";
                    if($o3['status'] == "dead"){
                        $o2['status'] = "alive";
                        $o2_win_count++;
                    }
                }
                elseif($o3['status'] != "dead"){
                    $o3['status'] = "dead";
                    $o2['status'] = "alive";
                    $o2_win_count++;
                }
                else{
                    //shouldn't get here
                    $o2['status'] = "alive";
                    $o2_win_count++;
                }
            }
            $hit = rand(0,10000)/10000;
            //option 1 goes last, aims at 2 if alive, 3 if 2 is dead
            if($o1['status'] != "dead" && $o1['hc'] >= $hit){
                if($o2['status'] != "dead"){
                    $o2['status'] = "dead";
                    if($o3['status'] == "dead"){
                        $o1['status'] = "alive";
                        $o1_win_count++;
                    }
                }
                elseif($o3['status'] != "dead"){
                    $o3['status'] = "dead";
                    $o1['status'] = "alive";
                    $o1_win_count++;
                }
                else{
                    //shouldn't get here
                    $o1['status'] = "alive";
                    $o1_win_count++;
                }
            }

        }
    }

    echo "The best's win count: ".$o1_win_count."<br>";
    echo "The mediocre's win count: ".$o2_win_count."<br>";
    echo "The worst's win count: ".$o3_win_count."<br>";
?>
| improve this answer | |
$\endgroup$
  • $\begingroup$ What do you mean by "chance to win" in the sentence "If the worst doesn't ever pass, mediocre has a roughly 48% chance to win". Did you mean that the mediocre's surviving probability is 48%? $\endgroup$ – Eric May 2 at 2:46
  • $\begingroup$ Somewhere something must be wrong with this simulation. The mediocre's chance to win will strictly decrease if the worst passes every time than if he doesn't ever pass. Think of it this way: if the worst doesn't pass, he will shoot the best. If he misses, it is equivalent as passing his turn to the mediocre. But if he succeeds, mediocre will duel with a weaker opponent and will have a first shoot advantage. This is the best possible outcome for the mediocre. So if the the worst misses, the mediocre is as good as if the worst had choose to pass, but if the worst hits, the mediocre has - $\endgroup$ – Eric May 2 at 3:38
  • $\begingroup$ [continued] a better chance to survive. So by conditional probability, the worst choosing not to pass is strictly better for the mediocre. $\endgroup$ – Eric May 2 at 3:40
  • 1
    $\begingroup$ @Eric Irrelevant really, but it's php, not python. Probably also hard to read because it was written as I thought it out, so no planning in the construction of the script.. but you're very close, it generates a random triple, assigns worst, mediocre, best, and simulates shooting process using random probabilitie until one is alive, adds count, and repeats entire process 1000000 times. the 10000 in rand is just because php rand gives an integer, so I get one between 1-10000 and divide by 10000 to get a (very specific) hit probability. $\endgroup$ – TCooper May 5 at 16:44
  • 1
    $\begingroup$ They are infinitely intelligent of course :p I've worked out the exact analytical constraint for whether the worst will pass or not, and also precise formulas for each players surviving probabilities based on that, for any given hit probabilities $g_b, g_m, g_w$. Then triple integrations of the surviving probabilities over $g_b\gt g_m\gt g_w$ yields precise result for their overall surviving probabilities. The result is 33.6%, 35.4%, 31.0% from worst to best. So the mediocre is still the best choice. The computations are very involved. I'll post an answer if I have time. $\endgroup$ – Eric May 9 at 1:34
1
$\begingroup$

The answer is:

The Worst

Because:

Each player is intelligent and so they are likely to play tactically. This means that the worst and mediocre are likely to attack the best first, giving Alice (not knowing the hit probability) a 50% possibility of killing the mediocre. This does not guarantee Alice's survival but does decrease her chance of death by about 17.6%

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Okay, but you have no idea what the probabilities are. One of the combinations is: 100%, 0.000000000001%, 0.00000000000000000001%. Choosing either the mediocre or the worst is effectively a death sentence. $\endgroup$ – Ian MacDonald May 1 at 19:24
  • 1
    $\begingroup$ Yes, but the likelihood is that the numbers are a lot less radical. My calculations are based of possible averages. Yes it is possible that the guns have a difference of up to 100% but it is also possible that it is infintesimal. $\endgroup$ – William Pennanti May 1 at 20:35
  • 1
    $\begingroup$ Would this change if after they selected they found out the hit probabilities are .500001, .500002, and .500003? Again unlikely for a random selection, just curious from a theoretical viewpoint. I would assume with my life on the line I'd still play the .000001-.000002 advantage - but maybe I'm missing something? $\endgroup$ – TCooper May 1 at 22:29
  • $\begingroup$ Another question- Going first seems to be a huge advantage, but if you know the worst will aim at the best, then couldn't moderate be safer? They aim for best, either kill or don't, but if they do, you only have one target with a lower chance than yourself, and are shooting before they do again. If they don't hit best, you haven't 'missed any turns' and take aim at best, hopefully hitting and only leaving one target below yourself. Don't know, just hypothesizing there may be more than meets the eye. $\endgroup$ – TCooper May 1 at 23:33
  • 1
    $\begingroup$ @WilliamPennanti No. Every possible combination of hit probabilities are equally likely. The question explicitly states that the guns are randomly picked from "a very large collection of guns whose hit probabilities are randomly distributed between 0 and 1" . $\endgroup$ – Eric May 2 at 0:52
1
$\begingroup$

The answer is

the Mediocre!

Because

A threeway-duel with turns, such as this, always ends up in a duel with turns. The worst gun is always in that duel as a bigger threat for the other two always exists. In most cases, the worst gun passes and ends up starting the duel. But sometimes the odds of facing the mediocre gun in the duel, even when the mediocre gun starts, are better than facing the best gun with the worst gun starting. Sometimes hitting the best gives better probabilities overall than missing/passing. This yields a set of probabilities for each gun picking. Iterating those pickings and adding the probabilities together gives the best educated guess of the gun that makes surviving (winning) most probable.

Results

Worst: 5151798.6976851 - 33.4%
Mediocre: 5481543.8630309 - 35.5%
Best: 4804657.4392835 - 31.1%
Worst shoots in 2756406 out of 15438000

Worst doesn't shoot
Worst: 5127133.1895262 - 33.2%
Mediocre: 5324462.4832485 - 34.5%
Best: 4986404.3272247 - 32.3%
Worst shoots in 0 out of 15438000

Worst shoots always
Worst: 3985277.060324 - 25.8%
Mediocre: 7396272.7532691 - 47.9%
Best: 4056450.1864092 - 26.3%
Worst shoots in 15438000 out of 15438000

first post (assuming naively that only comparison is against worst-best and mediocre-worst duels for the worst)
Worst: 5143589.5619746 - 33.3%
Mediocre: 5598586.3788909 - 36.3%
Best: 4695824.0591346 - 30.4%
Worst shoots in 4218360 out of 15438000

Proof

<?php

$inc=0.004;

/**
 * The worst gun can either wait for the two better guns to battle it
 * out and take the first shot at the winner in the duel that follows,
 *
 * or
 *
 * decide to shoot at the best and introduce a fork where when hitting
 * he will face the mediocre in a duel with the mediocre starting and
 * when missing have the same outcome as passing (ie get the first
 * shot). If the odds in the hits-best scenario are worse than in the
 * misses scenario he should pass, because
 *
 * Pworst * Pduel-vs-mediocre + (1 - Pworst) * Ppassing <= Ppassing
 * 
 * with all values of Pworst when Pduel-vs-mediocre <= Ppassing
 **/
function shouldWorstShoot($w,$m,$b){
 // probability of winning the whole battle after missing/passing
 $prob_missing = ($m/($m+(1-$m)*$b))*($w/($m+$w-$m*$w))+($b*(1-$m)/($m+(1-$m)*$b))*($w/($w+(1-$w)*$b));

 // probability of winning the battle after hitting the best
 // (i.e. duel against mediocre with mediocre starting)
 $prob_against_mediocre = ((1-$m)*$w)/($m+((1-$m)*$w));
 return $prob_against_mediocre>=$prob_missing;
}

/**
 * Duel: Worst fires first against mediocre
 *
 * updates the global win stats
 **/
function duelWorstMediocre($w,$m,$prob){
 global $worst_wins,$mediocre_wins;
 $tot = $w+((1-$w)*$m);
 $worst_wins+=($w/$tot)*$prob;
 $mediocre_wins+=(((1-$w)*$m)/$tot)*$prob;
}

/**
 * Duel: Worst fires first against best
 *
 * updates the global win stats
 **/
function duelWorstbest($w,$b,$prob){
 global $worst_wins,$best_wins;
 $tot=$w+((1-$w)*$b);
 $worst_wins+=($w/$tot)*$prob;
 $best_wins+=(((1-$w)*$b)/$tot)*$prob;
}

/**
 * Duel: Mediocre fires first against worst
 *
 * updates the global win stats
 **/
function duelMediocreWorst($m,$w,$prob){
 global $worst_wins,$mediocre_wins;
 $tot=$m+((1-$m)*$w);
 $mediocre_wins+=($m/($tot))*$prob;
 $worst_wins+=(((1-$m)*$w)/$tot)*$prob;
}


// these represent the combined odds of each of the gun position
// winning in every situation. They add up to number of pickings
$worst_wins=0;
$mediocre_wins=0;
$best_wins=0;

$worstShootsCount=0;
$n=0;
$a=[];
for($i=0.001;$i<=1;$i+=$inc){
 for($j=0.001;$j<=1;$j+=$inc){
  if($j===$i){
   continue;
  }
  for($k=0.001;$k<=1;$k+=$inc){
   if($k===$j||$k===$i){
    continue;
   }
   $n++;
   $a=[$i,$j,$k];
   sort($a);

   // only need to account for the first lap of 3way as others repeat
   $w_m_prob=0; // probablity of ending in worst-mediocre duel
   $m_w_prob=0; // mediocre-worst duel prob
   $w_b_prob=0; // worst-best duel prob

   $worst_shoots = shouldWorstShoot($a[0],$a[1],$a[2]);

   if($worst_shoots){
    $worstShootsCount++;
    $m_w_prob = $a[0]; // worst manages to hit -> m-w duel
    $w_m_prob=(1-$a[0])*$a[1]; // worst misses, mediocre hits -> w-m duel
    $w_b_prob=(1-$a[0])*(1-$a[1])*$a[2]; // worst misses, mediocre misses, best hits  -> w-b duel
   }
   else{
    $w_m_prob=$a[1]; // mediocre hits -> w-m duel
    $w_b_prob=(1-$a[1])*$a[2]; // mediocre misses, best hits -> w-b duel
   }
   $tot_prob = $m_w_prob + $w_m_prob + $w_b_prob; // normalize the odds
   duelWorstMediocre($a[0],$a[1],$w_m_prob/$tot_prob);
   duelMediocreWorst($a[1],$a[0],$m_w_prob/$tot_prob);
   duelWorstBest($a[0],$a[2],$w_b_prob/$tot_prob);
  }
 }
}
$tot = $worst_wins+$mediocre_wins+$best_wins;
echo str_pad("Worst:",14).str_pad($worst_wins,20)." - ".(round(1000*$worst_wins/$tot)/10)."%\n";
echo str_pad("Mediocre:",14).str_pad($mediocre_wins,20)." - ".(round(1000*$mediocre_wins/$tot)/10)."%\n";
echo str_pad("Best:",14).str_pad($best_wins,20)." - ".(round(1000*$best_wins/$tot)/10)."%\n";
echo "Worst shoots in ".$worstShootsCount." out of ".$n."\n";
| improve this answer | |
$\endgroup$
  • $\begingroup$ "Worst shoots in 4218360 out of 15438000" I think this is overestimating. In your "shouldWorstShoot" function, you should compare the worst's overall survival probabilities in whether shooting or not, not those in the duels. For example if he passes, there's some probability that he'll face the best and some probability that he'll face the mediocre, you need to condition on those probabilities to get his survival probability if he pass. Then compare it to his survival probability if he shoots, which is calculated similarly based on conditional probabilities. $\endgroup$ – Eric May 5 at 15:27
  • $\begingroup$ That is the result of the simulation, not an estimation. Overall survival probabilities boil down to surviving the forthcoming duel. If he passes, he will always start the duel and has an advantage. The only reason he would give up that advantage is when the Best has an overwhelming accuracy (like the function calculates). $\endgroup$ – ovikoomikko May 5 at 16:02
  • $\begingroup$ Of course I know it's simulation. What I was saying is the formula you used is wrong. There's no boil down here. The only reason he would give up passing is when his survival probability when passing is smaller than that when shoot, and the former is given by $\frac{m}{m+b-mb}\frac{w}{m+w-mw}+\frac{b(1-m)}{m+b-mb}\frac{w}{b+w-bw} $, not $\frac{w}{b+w-bw}$ as you suggested. these 2 are not equal so you can't "boil down”. Similarly for the latter. $\endgroup$ – Eric May 6 at 0:50
  • $\begingroup$ Yeah, you were right. His odds got better (barely) when comparing those of missing/passing odds against the odds of winning when hitting the Best. Up to 33.4% from 33.3%. He shoots a lot less though. I'll update my answer. $\endgroup$ – ovikoomikko May 6 at 9:05
  • 1
    $\begingroup$ Decreasing the inc variable (ie increasing the resolution) to 0.001 (one quart of above) yields Pw=33.63%,Pm=35.44%,Pb=30.93%, with better confidency $\endgroup$ – ovikoomikko May 9 at 9:04
0
$\begingroup$

I found a "bug" in this problem, not what I intended though. It seems with a very weak assumption, this problem (and by extension all similar three way duel problems), will admit a surprising solution. The assumption is

The players can see and remember who shot who.

Then the answer is

Alice can pick any gun and have a surviving probability of 100%!

Why? Because

Alice simply adopts a tit for tat strategy. She announces her strategy at the beginning of the game: Gentlemen, I'm vindictively dovish. I'll always pass my turns if nobody shoots me. But I'll keep shooting at whoever first shoot me until he or I am dead.

Why does this work?

When there're 2 players alive, {Alice, Bob} or {Alice, Charles}, if Bob and Charles have not shot Alice before, they'll just choose to pass every turn because unless they're 100% accurate, their shooting will make Alice fire back in case they miss, and decrease their survival rate to less than 100%. When all 3 players are alive, if Bob and Charles must shoot, they will want to shoot the person whose death gives them higher surviving probabilities. It is obvious that person can't be Alice. So they shoot each other, and when one of them dies, the survivor enters the blissful situation described above, surviving indefinitely. But wait! Who says they must shoot? They'll be fools if they do! As soon as Alice announced her strategy, the cunning Bob and Charles follow suit and announce the same strategy. A precarious balance by mutual threats is thus established in which nobody will venture to shoot.

| improve this answer | |
$\endgroup$
  • $\begingroup$ A "nobody shoots anyone" scenario isn't a survival probability of 100%. "This cycle is repeated until only one player survives." - the game NEVER ends, so nobody "survives" to live any life outside the game. The "bug" requires another assumption, which is that the 3 players can choose to end the game before only one player survives. The end-game could be enforced by the organiser of the game vowing to kill all 3 of them if (say) an entire round goes by without anyone shooting... $\endgroup$ – Steve May 5 at 9:50
  • $\begingroup$ @Steve Getting stuck in the game forever may or may not be to "survive" depending on what you define as "survive". The point is what additional rule to add to break this infinite loop. Your rule is in effect equivalent to forbidding the mediocre and the best to pass turns. I don't know if there're more reasonable rules that can also rule out this "nobody shoots" scenario. $\endgroup$ – Eric May 5 at 10:54
  • $\begingroup$ thematically, the existence of some sadistic tyrant controlling the whole thing would explain why Alice, Bob and Charles are even considering playing this "game" in the first place - e.g. they were all due to be killed, but one of them will be spared if they win this "game". $\endgroup$ – Steve May 5 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.