Thursday, September 8, 2011

Skyd + Nerdy Challenge

If you haven't seen already, I have moved over to Skyd. I am going to keep this space open for little odds and ends and things that don't quite fit or are a bit less formal than I intend the Skyd writing to be.

Here is the nerdy challenge: I am looking for a function where the input is the chance of a possession ending in a score (p). Obviously, 1 - p is the chance that a possession ends in a turnover. Then output is the probability of each of the six possible endings to a game of mini. The three 'wins' being: 3~1, 3~0, 3~-1 and the three 'losses': 1~-2, 0~-2 and -1~-2. Please ignore the Golden Goal variation for right now.

I brute forced it for p=0.5. This had the nice property that 1-p=0.5 as well, so the outcome tree was essentially symmetric and the probabilities easier to manage because I just used negative powers of 2. I quit after 5 generations and then estimated the remaining 20% of the probability based on the observed trends. Here is what I got:
3~1: 4.4%
3~0: 23.6%
3~-1: 18.2%
Winning: 46.2%
1~-2: 9.2%
0~-2: 18.6%
-1~-2: 25.6%
Losing: 53.4%
This was a bit surprising. I expected the chance of losing to be much higher. My intuition told me that it was two steps to lose and three steps to win, so it should divide out on a two-thirds, one-third ratio. But it turns out that you always have a chance to win, but you don't always have a chance to lose.

Help? Ideas? There has to be an easier way.

11 comments:

  1. I don't have time to do the math but this is a Markov Chain and modeling it as such should provide the information you want.

    http://en.wikipedia.org/wiki/Markov_chain

    ReplyDelete
  2. Wrote a quick monte carlo simulation for this, and here's what I got:

    [3, 1] : 0.02213
    [3, 0] : 0.1683
    [3, -1] : 0.0746
    [1, 3] : 0.03003
    [1, -2] : 0.03729
    [0, 3] : 0.06142
    [0, -2] : 0.07304
    [-1, 3] : 0.1031
    [-1, -2]: 0.09828
    [-2, 1] : 0.05189
    [-2, 0] : 0.10238
    [-2, -1]: 0.17754

    Winning %: 0.47364

    Code available here: https://gist.github.com/1203643

    ReplyDelete
  3. Alright, hopefully I didn't screw anything up...

    Google Spreadsheet with details and information here:

    https://docs.google.com/spreadsheet/ccc?key=0AuspDfJO_tIedGxRTFVoRi1MVDFpd3g1OUhDNDJkcGc&hl=en_US


    Assume that the team receiving first point has probability of scoring of p and of turning over of q (1-p), and pulling team for first point has probability of scoring of a and turning over of b (1-a).

    We can letter all the states that are possible from A to X and use that to represent possible game scores, and designate probability of moving from one state to another with variables p, q, a and b.

    If we reorder the states so that all the ending states (A, B, G, H, Q, R, W, X) are at the end, we have the Markov Chain with absorption states in canonical form, giving us the matrices Q and R (in the upper left and right, respectively).

    If we define B = (I - Q)^-1 * R, then B is the matrix of Bij that represents the probability that we'll end in any given absorption state j given a specific starting state i.

    Since we start in state N, we'd just need to find the corresponding row in matrix B to starting in state N, and that would give us long run probabilities of each possible game result.


    I still need to plug the matrices into something that can compute symbolic matrix inverses, and then we can calculate the results in a way that accepts parameters p and a at the start to generate expected winning percentage in absolute terms...assuming I didn't goof anything up. :-)

    ReplyDelete
  4. @Ben: Thanks! That is some cool and interesting math and (obviously) just what I needed.

    @Bill Mill: http://www.ultipedia.org/wiki/Mini_Ultimate

    @Alpha Chen: My dad told me to Monte Carlo it, but being really old school, he wanted me to use Basic. Will yours allow you to adjust p to any possible value?

    ReplyDelete
  5. @Ben: You have state G (in H5) at a score of 2-3. Shouldn't it be pushed down a cell (into H6)? I also think you are missing a few end states. There should be 12 (31,30,3-1, 1-2,0-2, -1-2 each twice). Or am I miss reading it?

    ReplyDelete
  6. So I went through it in my head over and over and I couldn't come up with a way that the game could end, say, with the receiving team with 3 and the pulling team with 1. I drew it out on a piece of paper to make sure I wasn't going crazy, and I still might have messed up, but I think since you score or lose a point with every possession, there is no way to get into some score situations.

    In other words, I said to myself, if it starts 0;0, what are all possible scenarios for the receiving team? Score or turn. So then it's either 1;0 or -1;0. Then I did that for 1;0 and -1;0, and so on. I never got to 3;1 that way (or 0;3, etc.).

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. Although looking at these probabilities, I'm pretty tempted to keep track of turnovers at our morning mini games!

    ReplyDelete
  9. For kicks, I put it up here: http://mini-probability-calculator.heroku.com/ You can change the probability of each team individually.

    So people can check my work, here's the source: https://github.com/kejadlen/Mini-Probability-Calculator

    ReplyDelete
  10. Fun question! I also wrote a little Java program to model the scenario, pretty interesting that at a p of .75 there's a 93-94% chance of the game being won (and of course we all hope it's more likely to score on a given possession than to cause a turn). To answer your question about your initial intuition, at the beginning of the game you are actually exactly 3 steps from winning or losing, because to lose the current team has to turn the disc, then the other team has to turn it, then the current team again, so still 3 steps down the tree, same as to win!

    ReplyDelete