Duels are a classic staple of westerns, but it took Sergio Leone's 1966 film “The Good, The Bad and The Ugly” to immortalize the truel (neologism for a three-way duel) in the popular mind!

Back in 1975, a high school teacher named Walter Koetke took the truel into outer space in a puzzle from the May/June 1975 issue of Creative Computing. I first ran across it in the 1980s, in The Best of Creative Computing.

This puzzle concerned 3 planets, Mutab, Neda and Sogal, who have agreed to an unusually rational war. Each planet would fire planet-destroying missiles at one another in turns, with the order of the truns being determined by random drawing. The rocket launching continues in order until only 1 planet remains. However, each planet has different capabilities. Mutab is the most advanced, and when fired at a target, have a 100% chance of destroying that target. Neda is the next most advanced, but their missiles only have an 80% chance of destroying their target. Sogal is the least advanced of the three, with missiles that only have a 50% chance of destroying their target. The puzzle is this: What are each planet's chances of surviving a war?

Even when I first ran across the problem as a teen, I remember thinking how difficult this problem must be. I realized that any calculations between the less-than=100% chances of battles between Neda and Sogal would be difficult to deal with, as they could go on for several turns, much like encountering long heads-only or tails-only runs in coin-flipping. The problem did stick in the back of my mind, though, as I thought it would be interesting to analyze when I knew more about math.

That day arrived when I first learned about Markov chains. If you're already familiar with Markov chains, you're ready for my solution. I've set up a site that takes you through the solution step-by-step here. Start by clicking the “Click to work out 2-world battles” button, and then read through the logic and tables until you get to the next button. Keep proceeding that way all the way to the end. It's written using Bootstrap, so it should be viewable using any size screen (the larger tables can be swiped left and right on smaller screens). There are lots of labeled tables, explanations of what they mean, and even several links to calculations via Wolfram|Alpha. All the math is being worked out by your browser as the program runs, so you may need to be patient with slower computers.

If you're still reading because you're unsure what Markov chains are, they're not that difficult a concept, as long as they're explained clearly. The rest of this post will deal with the basic concepts. Below is an excellent and clear (and short!) introduction to the concept.



What I realized is that I could represent the targeting of one planet by another as one state, and each of the possible outcomes as individual states. From this, I could build a transition probability matrix, as explained in the video and this visual explanation of Markov chains.

Now, the video discusses the idea of a starting probability vector as a starting point. In the Mutab/Neda/Sogal puzzle, however, we're really only interested in the long term probabilities themselves, the effects over the long term, and not so much a particular starting point, referred to as a stability distribution matrix.

As an example, imagine a 2-planet battle between Mutab (100% deadly) and Neda (80% deadly). If we list starting states from top to bottom (yes, I know this is opposite of how Markov chains are usually done) as, “Mutab fires against Neda”, “Mutab wins”, “Neda fires against Mutab”, and “Neda wins”, and label the resulting states the same way from left to right, then we can assign corresponding probabilities. The probability of going from “Mutab fires against Neda” to “Mutab fires against Neda” is 0, the probability of going from “Mutab fires against Neda” to “Mutab wins” is 1, and the probabilities of going from “Mutab fires against Neda” to “Neda fires against Mutab”, or “Neda wins” are both 0, so our first row would read (0 1 0 0). Continuing through all the probabilities between just Mutab and Neda, we get the following matrix:



Notice the 1s in the 2nd and 4th rows. Those are absorbing states. The 1 in the 2nd row basically says, the probability of going from “Mutab wins” to “Mutab wins” is 1 (100%). The 1 in the 4th row says that the probability of going from “Neda wins” to “Neda wins” is 1. They serve as an endpoint.

Where does this all wind up? Well, if we run these probabilities over 1,000 generations to get the long-term outlook (the stability distribution matrix mentioned earlier) by raising the above matrix to the 1,000th power, we get the following results:



Read with the original labels, this tells us that, over the long term, if Mutab is the first one to fire, then it's probability of survival is 1, and Neda's is 0. Conversely, if Neda is the first one to fire in that two-world battle scenario, then it's probability of survival is 80%, while Mutab's is only 20%. Yes, we figured that much out early on, but when it comes to tougher probabilities, such as the long-term probabilities between Neda and Sogal, this is a very helpful tool.

Once you've understood all that, you're ready to go through the step-by-step explanation I developed!