wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> A snowball's chance...
        
(Message started by: towr on Sep 23^rd, 2003, 8:42am)

Title: A snowball's chance...
Post by towr on Sep 23^rd, 2003, 8:42am

In one of the virtual worlds on the internet I occasionally frequent there's agame you can play were you throw virtual snowballs at people. The goal is of course to hit people, and in doing so get a good score.
Now there isn't really anything you can do to influence it, since it's purely a chance game, but it is nice to know what you're chances for improvement are.

Here are the rules:
for the first 20 throws there's always a 50% chance it's a hit.
After that the chance of a hit is equal to your hitrate up to that point (so if you have 12 out of 20, there's a 60% chance you'll hit who you're aiming for)

What's asked:
-Find the probability for a certain future score, given some current score.
So for instance I have 20/30 and want to know my chances of getting 30/35 (or higher, which is then easy enough to find).
-The same, but with your chance of a hit being the hitrate rounded down to the nearest percentage (so 20/30 would only give a 66% chance of hitting someone)
(this is the actual implementation of the game, and I still don't have a good solution for it)

And of course try doing it as efficiently as possible, so give the order fo the algorithm.

Title: Re: A snowball's chance...
Post by James Fingas on Sep 25^th, 2003, 9:38am

Interesting problem. Take a look at the outcomes if you start with the following track records:

0/1, 1/1, 1/2, 2/3, 3/4, 4/5, ...

If you start with 20/30, you would need 10 hits in 5 shots to get 30/35.

I think the simplest way to do the calculation would be to just simulate the next N shots. So if you have a record w/x, and you want to find out what your probability of reaching a record y/z is, just do (z-x) rounds of simulation, with performance O((z-x)^2) and O(z-x) memory.

Title: Re: A snowball's chance...
Post by towr on Sep 26^th, 2003, 2:38am

on 09/25/03 at 09:38:12, James Fingas wrote:

Interesting problem. Take a look at the outcomes if you start with the following track records:

0/1, 1/1, 1/2, 2/3, 3/4, 4/5, ...

The first 20 throws are even chance, so this won't happen in the game.
Still, in the second part of the problem you can still get stuck in an infinite loosing streak. and there's a one in a million chance you'll have an infinite winning streak (haven't had that luck so far).
(There's an interesting observation you could make there)

Quote:

If you start with 20/30, you would need 10 hits in 5 shots to get 30/35.

I think the simplest way to do the calculation would be to just simulate the next N shots. So if you have a record w/x, and you want to find out what your probability of reaching a record y/z is, just do (z-x) rounds of simulation, with performance O((z-x)^2) and O(z-x) memory.

The problem with O((z-x)^2) is that it get's very large when you want to make forecasts further into the future. For the first plem you can definately do much better. But I haven't found a better one for the second. Though do I think there's a better one, using more memory but much less time (I only really worked at the first problem, since it's much simpeler, more elegant, and more fair)