Enigmatic Code

Programming Enigma Puzzles

Enigma 1190: Triple duel

From New Scientist #2346, 8th June 2002 [link]

In an earlier incarnation, George fought a “duel” with Ernest and Fred. Ernest was a crack shot, 100 per cent certain to hit his target. Fred had a 75 per cent chance and George only 60 per cent. They agreed to fire one shot at a time in rotation, George (the weakest shot) first, then Fred, then Ernest, until two were dead. Each could aim where he pleased.

If each adopted his best strategy, who was most likely to survive and what was his percentage chance of survival?

[enigma1190]

Advertisements

2 responses to “Enigma 1190: Triple duel

  1. Jim Randell 7 December 2015 at 8:59 am

    I choose to think of this a duel (or “truel”) with paintball guns, so that once a participant is hit they are eliminated non-fatally.

    We then consider the probabilities of winning the truel (i.e. to be the only participant that hasn’t received a “hit”), rather than the probability of “surviving”. If each participant refused to shoot (or deliberately missed), then all three participants would “survive” at the point when they give up (or run out of ammunition), but no-one would win.

    The approach I used is similar to the one I used in Enigma 287.

    To work out the best strategy, we determine the function target(X, [Y, Z]) where:

    target(X, [Y, Z]) is the choice from [Y, Z] when X is to shoot and [Y, Z] are the other participants.

    Using: A = George (60%), B = Fred (75%), C = Ernest (100%).

    If any participant is faced with a single opponent, (so a normal duel), then his best strategy is to target that opponent. In the case of C this gives him a 100% chance of winning.

    target(A, [B]) = B
    target(A, [C]) = C
    target(B, [A]) = A
    target(B, [C]) = C
    target(C, [A]) = A
    target(C, [B]) = B

    So, we need to determine the best strategies when faced with two opponents.

    If C is faced with two opponents (A and B) he can eliminate one of them. If the remaining opponent misses then C subsequently eliminates him. So, faced with two opponents C should eliminate the opponent with the greatest chance of hitting him. i.e. C should target B.

    target(C, [A, B]) = B

    If B is faced with two opponents (A and C). If he targets A and hits, then A is eliminated, and C goes on to eliminate B and win. If he targets A and misses, then C has a choice of two opponents and targets B, eliminating him. So it ends badly for B if he chooses to target A instead of C. If he targets C, then there is a 75% chance he will eliminate C, and a chance that A will miss, giving him at least a chance to eliminate A and survive:

    target(B, [A, C]) = C

    Now we can use the targeting function to work out the following probabilities of winning, where:

    P(X, [Y, Z]) represents the probabilities (X, Y, Z) of winning the duel when X is to shoot an the remaining opponents are Y and Z.

    P(C, [A]) = (0, 0, 1)
    P(C, [B]) = (0, 0, 1)
    P(C, [A, B]) = P(A, [C])

    P(B, [A]) = (3/4) (0, 1, 0) + (1/4) P(A, [B])
    P(B, [C]) = (3/4) (0, 1, 0) + (1/4) P(C, [B]) = (0, 3/4, 1/4)
    P(B, [A, C]) = (3/4) P(A, [B]) + (1/4) P(C, [A, B]) = (3/4) P(A, [B]) + (1/4) P(A, [C])

    P(A, [C]) = (3/5) (1, 0, 0) + (2/5) P(C, [A]) = (3/5, 0, 2/5)
    P(A, [B]) = (3/5) (1, 0, 0) + (2/5) P(B, [A]) = (3/5, 3/10, 0) + (1/10) P(A, [B])

    solving this last equation gives:

    P(A, [B]) = (2/3, 1/3, 0)

    so:

    P(C, [A]) = (0, 0, 1)
    P(C, [B]) = (0, 0, 1)
    P(C, [A, B]) = (3/5, 0, 2/5)

    P(B, [A]) = (1/6, 5/6, 0)
    P(B, [C]) = (0, 3/4, 1/4)
    P(B, [A, C]) = (13/20, 1/4, 1/10)

    P(A, [B]) = (2/3, 1/3, 0)
    P(A, [C]) = (3/5, 0, 2/5)

    Finally if A is faced with two opponents (B and C), we have the following possibilities:

    If A targets B:

    P(A, [B, C]) = (3/5) P(C, [A]) + (2/5) P(B, [A, C]) = (3/5) (0, 0, 1) + (2/5) (13/20, 1/4, 1/10) = (13/50, 1/10, 16/25) = (26%, 10%, 64%)

    If A targets C:

    P(A, [B, C]) = (3/5) P(B, [A]) + (2/5) P(B, [A, C]) = (3/5) (1/6, 5/6, 0) + (2/5) (13/20, 1/4, 1/10) = (9/25, 3/5, 1/25) = (36%, 60%, 4%)

    So, if A has to target one of his opponents then his best chance of winning is 36% by targeting C.

    However, if A can deliberately miss both B and C, we get:

    P(A, [B, C]) = P(B, [A, C]) = (13/20, 1/4, 1/10) = (65%, 25%, 10%)

    So A can increase his chance of winning to 65% by deliberately missing (or forfeiting) his turn.

    B doesn’t have that option, if he forfeits his turn, then he will be targeted by C and eliminated.

    Solution: George is the most likely to win. He has a 65% chance of winning.

    Fred, the middling shot, has a 25% chance of winning.

    Ernest, the best shot, only has a 10% chance of winning.

    So, this “truel” is an example of “survival of the weakest”, as the weakest shot has the best chance of winning and the best shot has the lowest chance of winning.

    Here is a simulation of the above strategies in Python. It runs 1,000,000 trials in 1.4s and produces results that agree with the above analysis.

    from random import randint
    from enigma import irange, printf
    
    # labels for the participants
    (A, B, C) = (0, 1, 2)
    
    # percentage probability of a hit
    hit = [ 60, 75, 100 ]
    
    # run N trials
    import sys
    N = (1000000 if len(sys.argv) < 2 else int(sys.argv[1]))
    
    # run one trial of the duel
    # p - next to shoot
    # ps - participants
    # target - targeting strategy
    def run(p, ps, target):
      while len(ps) > 1:
        # target one of the other participants
        t = target(p, tuple(x for x in ps if x != p))
        # is it a hit or not?
        h = (randint(0, 99) < hit[p])
        if h and t is not None:
          # it's a hit, eliminate the target
          ps.remove(t)
        # move on to the next participant
        while True:
          p = [B, C, A][p]
          if p in ps: break
      # when there's only one participant left, we have a winner
      return p
    
    # target function for player p against opponents ps
    def target(p, ps):
      # single opponent
      if len(ps) == 1: return ps[0]
      # multiple opponents (A, B, C)
      return [None, C, B][p]
    
    # run the trials
    printf("running {N} trials ...")
    r = [ 0, 0, 0 ]
    for i in irange(1, N):
      w = run(A, [A, B, C], target)
      r[w] += 1
    
    t = sum(r)
    for (i, n) in zip('ABC', r):
      f = 100.0 * n / t
      printf("{i} wins {n}/{t} = {f:.2f}%")
    

    Here’s the output of a typical run:

    % time pypy enigma1190d.py
    running 1000000 trials ...
    A wins 650158/1000000 = 65.02%
    B wins 249914/1000000 = 24.99%
    C wins 99928/1000000 = 9.99%
    pypy enigma1190d.py  1.29s user 0.04s system 98% cpu 1.348 total
    

    You can play around with alternate targeting strategies by changing the target() function.

    The number of trials to run (default: 1,000,000) can be specified as a command-line argument.

  2. Hugh Casement 7 December 2015 at 2:55 pm

    This is very reminiscent of one put forward many years ago by Martin Gardner in his column in Scientific American: see also More Mathematical Puzzles and Diversions (Pelican, 1966) for an analysis.  The difference there was that Smith is 100% accurate, Brown 80%, and Jones only 50%; they draw lots to determine the cyclic order of shooting (until one is hors de combat).  The problem apparently dates from 1938 or even earlier.

    Gardner concluded that under those conditions Jones’ best strategy is to shoot into the air until one of his opponents is dead (for they are likely to see each other as much the greater risk and leave him alone).  Then he gets first shot at the survivor.

    Incidentally, according to the dictionary the Latin word duellum was a poetic variant of bellum and had nothing to do with duo.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: