Decision Trees In Games 


My lastest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
Decision Trees in Games (Part 1)  2011/05/15A fairly standard exercise in probability is to ask who, under a given scoring system, will win a game given the probability of each move. For example, suppose we toss a coin, and I get a point for every head, and you get a point for every tail. Winner is first to 2. It's easy if the coin is fair, because the game is symmetrical. It's easy if it's a two headed coin, or a two tailed coin, because then the winner is certain.
We now have all the possibilities, and we can see that there are three ways "H" can win: "HH", "HTH", "THH". By tracing their respective paths down the tree we can see the probability of each combination, and so we get our answer of pp+pqp+qpp, which simplifies to p^{2}+2p^{2}q or p^{2}(1+2q). We can check this in three particular cases. If the coin is fair (so p=1/2 and q=1/2) then it should evaluate to 1/2. If it's a double headed coin (so p=1 and q=0) then it should evaluate to 1, and if p=0 (so q=1) then it should evaluate to 0. And it does. That's nice.
For larger cases there are ways to do this algebraically and without the diagrams, but personally, I find that understanding and intuition comes from the diagrams, and the counting arguments are guided by the structure in the diagram, whether I draw the diagram, or simply think of how to draw it.

Contents 
Links on this page 

Quotation from Tim BernersLee 