1

I have a game program that is played by a robot. For simplicity's sake, the game has 2 buttons - "win" and "try again". To win, the robot must simply push the "win" button.

The game involves a countdown timer that starts at 10 and runs to 0, ticking once per second. During each tick of the timer, the robot picks one of the two buttons. When the timer is at 10, the chance of the robot clicking win is very small. As the timer gets closer to 0, the chance of the robot clicking the "win" button increases. And of course, the robot may never click the win button at all.

What I'm looking for in the end is that the robot click "win" about 90% of the time with those win clicks being weighted closer to the timer being 0.

I did some research on probability (absolute novice) and my understanding is that the sum of the probabilities at each tick of the time should total up to .90 in order to get my desired result. Example:

countdownTimerTickNumber | probabilityOfClickingWin
====================================================
10 | 0
9 | 0.0001
8 | 0.005
7 | 0.01
6 | 0.02
5 | 0.04
4 | 0.08
3 | 0.1
2 | 0.15
1 | 0.2
0 | 0.294
----------------------------------
Total probabilityOfClickingWin over all ticks: .9

Here is some pseudo code to show how I use the probabilities from the table above to actually determine which button the robot clicks. It is called during each tick:

function bool doClickWin(probabilityOfClickingWin)
{
     if (probabilityOfClickingWin >= new Random().NextDouble())
          return true;

     return false;
}

However, if I run my program many times, I'm finding that the actual percentage of the time that the robot clicks "win" is much lower than 90% (approx 60%).

Can anyone tell me what I'm doing wrong? Thanks in advance.

Don
  • 531
  • 6
  • 13
  • I've removed my comment because it had inaccurate but idea was correct. What screws up your logic is `probabilityOfClickingWin` and the way it's calculated. To get desired probability it needs to be `probability * maxRandomNumberThatCanBeReturned`. Since `Random.NextDouble` returns max value `1.0d`, you need to pass `0.9d` to get 90% of return `true`. Here's sample: http://ideone.com/a8wxw6 Higher gets tries more accurate becomes result. Also keep `Random` object statically ([_reason_](http://stackoverflow.com/a/10598041/1283847)) – Leri Oct 18 '13 at 07:04
  • Leri - it looks like CompareWithRandom() in your sample will return true ~90% of the time for each iteration of "tries". That's actually not what I need. I need it so that for all iterations of "tries" combined, there is a ~90% chance that CompareWithRandom() will return true only once. Thanks for taking the time, though. – Don Oct 18 '13 at 07:37

1 Answers1

4

The probability calculation is more complicated than you think. The probability of winning is

P(win on 0th tick) + P(win on 1st tick) + ... + P(win on 10th tick)

Let's call the probabilities p(0) ... p(11). Then

P(win on 0th tick) = p(0)
P(win on 1st tick) = (1-p(0)) * p(1)
P(win on 2nd tick) = (1-p(0)) * (1-p(1)) * p(2)

etc. At each tick, the probability that you win on that tick is the probability that you didn't already win on any of the previous ticks, multiplied by the probability of winning right now.

With the numbers you gave in your post, I think that your robot should win about 63.17% of the time (I am not sure why you are seeing about 30% - could this be a bug somewhere else in your program?)

With the following numbers you should observe about a 90% success rate overall

 0       0
 1  0.0068
 2  0.0113
 3  0.0188
 4  0.0314
 5  0.0524
 6  0.0875
 7  0.1459
 8  0.2433
 9  0.4059
10  0.6771

EDIT

How did I come up with these numbers? Trial and error. But we could invent a procedure that given any win probability, generates a suitable set of probabilities for each tick.

Let's say that the total win probability is Q, so you want

P(Win on 0th tick) + ... + P(Win on 10th tick) = Q

Let's say we want there to be no chance of winning on the 1st tick, and a linearly increasing chance of winning on any tick after that. So the probabilities have to add up to Q, and the probability of the win coming at tick i is proportional to i. Therefore

P(Win on ith tick) = const * i

hence

   c * 0 + c * 1 + c * 2 + ... + c * 10 = Q

=> 55 * c = Q

=> c = Q/55

That gives us

P(Win on 0th tick) = 0
P(Win on 1st tick) = Q/55
P(Win on 2nd tick) = 2*Q/55

etc. Now you use these to determine each of the p(i) using the formula at the top of the post. We have

p(0) = P(win on 0th tick) = 0
p(1) = P(win on 1st tick) / (1-p(0)) = Q/55
p(2) = P(win on 2nd tick) / (1-p(0)) / (1-p(1)) = 2*(Q/55) / (1-Q/55)

etc. Here's a Matlab routine that calculates the probabilities; it shouldn't be hard to translate it into C# or whatever you're using.

N = 10;
Q = 0.9;
p = zeros(N+1,1);

for i = 1:N
  p(i+1) = i * Q/(0.5*N*(N+1)) / prod(1-p(1:i));
end

which gives this result

 0         0
 1    0.0164
 2    0.0333
 3    0.0516
 4    0.0726
 5    0.0978
 6    0.1301
 7    0.1745
 8    0.2416
 9    0.3584
10    0.6207
Chris Taylor
  • 46,912
  • 15
  • 110
  • 154
  • You're right in that I was getting ~60%. It looks like you see my problem but can you explain to me or give me an exact formula for how you got your set of probabilities for each tick? There are actually many robots and they have varying probabilies (not just 90%) so I need to be able to work backwards from a robot's total probability to determine the probability at each tick for each robot. I tried to figure it out using your snippet, but I'm stuck (e.g. `P(win on 1st tick) = (1-p(0)) * p(1)` - but aren't `P(win on 1st tick)` and `p(1)` the same in this line?). Thx again. – Don Oct 18 '13 at 08:18
  • 1
    The probabilities `p(i)` are the probability that you win on this tick, *if we have reached it*. But you don't always reach that tick, because you might win on an earlier tick. The probabilities `P(Win on ith tick)` are the total probabilities that your robot win on the i'th tick. These are mutually exclusive, so they can be added to get the total win probability. – Chris Taylor Oct 18 '13 at 08:24
  • The way that I arrived at the numbers in my post was simply trial and error. I'll make an edit to give you a more concrete procedure for determining the probabilities at each tick. – Chris Taylor Oct 18 '13 at 08:27
  • Thx for working on that. As your working on it, let me just clarify the two pieces of data that are available for the formula: 1) the total probability for all ticks (e.g. 90%, 85%, 70%, etc) and 2) the formula for the curve that sets the probabilty at each tick: `y = x^2.25` (x is the tick number and y is the tick's relative probability. In other words, as x increases, so does the probability that it is a "winning tick". Hope that isn't too confusing). – Don Oct 18 '13 at 08:33
  • Sorry, I forgot one other piece of data: 3) the total number of ticks. I said it was always 10 for simplicity in the original question but it can actually vary from game to game. I went ahead and already marked your answer as correct because these are additional parameters, but I hope you can still come up with a formula for all of this. Thx. – Don Oct 18 '13 at 08:41
  • Thanks for the formula and the added explanations. Works nicely now. – Don Oct 18 '13 at 10:53