Author |
Topic: A snowball's chance... (Read 1428 times) |
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
A snowball's chance...
« on: Sep 23rd, 2003, 8:42am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: A snowball's chance...
« Reply #1 on: Sep 25th, 2003, 9:38am » |
Quote Modify
|
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A snowball's chance...
« Reply #2 on: Sep 26th, 2003, 2:38am » |
Quote Modify
|
on Sep 25th, 2003, 9:38am, 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)
|
« Last Edit: Sep 26th, 2003, 2:42am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|