If you shop at Amazon anyway, consider using this
link. We receive a few cents from each purchase. Thanks.
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
Send an e-mail with your
comments about this program (or anything else).
Three men who are mutual enemies decide to
settle things with a shootout. Al is a poor shot only hitting his target 1/3
of the time. Bob hits his target 2/3 of the time and Charlie hits what he
aims at 100% of the time. To even the odds a bit, Al is given first
shot. Bob is next, if he's still alive. He's followed by Charlie, if he's
still alive. They will continue shooting like this, in this order, until two
of them are dead.
The question is: At whom should Al aim his first shot to maximize his
chances of surviving?
Background & Techniques
This problem was borrowed from a recent Puzzler on the Car Talk radio
here. When math skills fail, programming skills can (sometimes)
save the day. That was the case here. I decided to
simulate lots of shootouts under various strategies and empirically find the
best one. The most obvious plan would be to shoot at the guy
most likely to kill you. The only other two plans I could think of
were to shoot at the fellow least apt to kill you, and to choose your target
randomly, as if you did not know the accuracy statistics of each
shooter. It turns out that there is a fourth, the winning,
strategy, as I found when I checked Car Talk's solution. So I
added that choice a well, but I won't describe it here (in case you
want to work on the problem on your own first).
The program allows you to select a strategy, then click a button to
conduct 1,000,000 shootouts and display the results. The
shot-by-shot results are displayed for the first 100 contests.
Each contest has each shooter in turn apply the chosen strategy to
select a target, then record a "hit" based on that shooters
probability of hitting his target. (For example, for Al's
accuracy score of 1/3, we generate a random real number between
0 and 1 and record a hit if the number is less than 0.3333. This
technique is called a "Monte Carlo" simulation.)
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.
The program defines a shooter record,
TShooterRec, for each participant. The record contains the
constant information about the shooter (name and accuracy score),
information about his current status within a game (whether alive or not),
and his total statistics for this set of shootouts (number of wins and
number of hits).
And array of these records, Recs, is
initialized for each "SolveBtn" click. A loop then runs the
1,000,000 shootouts. "Alive" status is set to true for all
participants before each shootout. The "TakeAShot" procedure is
a recursive routine which takes a shooter array index, Shooter,
and the Shotnbr as parameters. It performs these
|Determine the target|
|Take the shot and record whether or not target
was hit if one is found. A hit is determined by comparing a random
real number between 0 and 1 to the shooters accuracy rating.
"Less than" counts as a hit. If hit, the shooter's hit count is
incremented and the target's "alive" status is changed from true
to false. |
|Identify next shooter, NextShooter,.
Since shooters take turns in "round robin" fashion, we search up
through the Recs array from the current shooter's index number
looking for a living participant. (Round robin" means that the
first shooter follows last shooter in shooting order.) |
|If the global ShowDetail variable is
true( in the first 100 games), we display the result s for this shot.|
|Finally, if no next shooter was found, the
game is over and we can update total statistics and display winner
information if ShowDetail is true. If a next shooter
was found, we call ourselves again passing NextShooter and ShotNbr+1 as
That's about it. After the 1,000,000 shootouts, final stats are
Addendum February 21, 2012: Version 2 posted today adds a
second version of the Car Talk puzzle with different accuracy probabilities
for the three shooters. This version is from a book
Fifty Challenging Problems in Probability
Frederick Mosteller, Dover
Publications which I am currently working my way through. I had
previously posted several other problems from the book in our math section
Probability Problems. For each of those I included an analytical
as well as an experimental solution but I have yet to solve this one
analytically. I decided to add the experimental result here to provide
some clues to the correct theoretical solution.
Running/Exploring the Program
Suggestions for Further Explorations
Number of shootouts and number of detailed results
per trial could be user inputs, although 1,000,000 and 100 seem
to be good enough numbers to verify the strategy chosen and to get
consistent results taking only a few seconds to run..
Original Date: February 13, 2007
February 21, 2012