Subscribe!

• Colins Blog

• Decision Trees In Games
• A Matter Of Convention
• Do You Nourish Or Tarnish
• Binary Search Reconsidered
• Two Equals Four
• The Lost Property Office
• The Forgiving User Interface
• Setting Up RSS
• Withdrawing From Hacker News

• Random Writings.
• Colins Blog 2010
• Colins Blog 2009
• Colins Blog 2008
• Colins Blog 2007
• Colins Blog Before 2007

Decision Trees in Games (Part 2) - 2011/05/18

Decision tree for tennis Decision tree starting at Deuce

In the last post we analysed a simple "First to Two" (or "Best of Three") game of probability. More interesting, and more difficult, is something like tennis, which adds the complication of "Deuce." In tennis, the winner of a game is the person who not only has at least 4 points, but is also at least 2 ahead of their opponent. When you each have 3 points the next winner of a point doesn't win the game - they need to get two in front.

So we start drawing our tree of possibilities, then we realise it will be too big and we collapse it into a DAG, and then we get the situation shown at right. I've marked each node with the score at that node and the number of ways of getting there. In case you're wondering, the number of ways of getting to a node is simply the sum of all the ways of getting to its parents. Some people find that obvious, others don't.

So we can see that "H" wins with loads of possible combinations, and we can add them all up. Using D for the probability of winning from Deuce we get:

But just what is the probability of winning from Deuce? We can compute the probability of getting to Deuce. Now we just need to compute the chances of winning once we're there.

Starting from being Deuce (which is 3 all), let's draw our DAG. We could get two heads, and then we've won, or we could get two tails, and then we've lost. Or we could get one of each (and there are two ways to do that) and we get to 4 all.

And here's the clever bit. Our chances of winning from 4 all are the same as winning from 3 all. We must again pull ahead by two, just as we had to do from 3 all. So our chances of winning from 4 all are again D.

So our chance of winning from 3:3 is the chance of getting HH, plus twice the chance of winning from 4:4. Thus our chances of winning from 3:3 are p²+2pqD. And that's D. So we have the equation: D=p²+2pqD.

We can rearrange that, and we get D-2pqD=p², and then D(1-2pq)=p², and so finally we have D=p²/(1-2pq). It's worth checking what happens when p=0, p=1/2 and p=1. That lets us check our answer.

So now we get our final expression for the probability of winning a game of tennis. It's this:

It looks complex, but we can see where all the terms come from, and we've been able to sneak up on it. It's not that bad.

In my next post, however, we'll find that this hides within it a rather surprising and slightly disturbing result.

<<<< Prev <<<< Decision Trees In Games

:

>>>> Next >>>> An Oddity In Tennis ...

---

You should follow me on twitter

Comments