Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Self-balancing random number generation


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
36 replies to this topic

#1 Kylotan   Moderators   -  Reputation: 3338

Like
Likes
Like

Posted 09 August 2001 - 06:50 PM

Ok, although I am ok at mathematics, I''m no expert, so excuse any apparent ignorance or misuse of terminology. Imagine you are about to flip a coin 10 times. You expect 5 heads. So you flip it coin 9 times, and get 5 heads and 4 tails. Given a proper coin, the 10th flip has a 50% (p = 0.5) chance of being heads. This means that, once you''ve had 9 flips, you have a 50% chance of scoring 6 heads. However at the start, it was a 50% chance of scoring 5. I am looking for a way to ''counterbalance'' this, so that by the time that 10th flip comes about, the system is biased so that it tends towards rectifying any imbalances in the probability sequence. In other words, the chance of flipping the coin and getting tails would be greater than 50%. Ideally, the chance in this case of getting tails on the final flip would be 100%. However, this requires that the system knows that we are working with a sample size of 10. This will not always be possible. Therefore any system that can guarantee a tails chance of greater than 50% will be better than nothing. And for every subsequent flip that results in heads, this chance should grow somewhat. Another constraint is that the system will be called many times. Therefore it''s not viable to store all the past scores. However, it would be viable to store the average of the past scores plus the number of scores in the sample that made up that average, which I guess should be just as useful in the circumstances. Finally, this random number generator wouldn''t just be generating true/false or heads/tails values based on a 50% probability. (I used the coin-flipping as a simple example.) It would be generating true/false values based on a supplied variable that represents a percentage, or other continuous value (between 0.0 and 0.1, perhaps). For example, via a function call such as "RandPercent(60)", which has a 60% chance of returning true, given no prior calls to the function. This makes a solution based on formulating a ratio from the nominal data (ie. count the heads, count the tails, and weight the new result based on the proportion) insufficient. However, since the random number generator knows what the ''threshold'' for each test is, it can see whether it returned the ''expected'' result or not, and can also see how likely/unlikely its result was. I have seen the term ''stochastic'' used in some contexts similar to this, but have yet to find an explanation of the term that is both precise and yet not overly complex. Perhaps this is the solution to my problem, but I don''t know. (For those who are interested, basically I just want this so that I can have a random number system in a game that allows for freak events, but takes corrective action to reduce the chance of an unlucky streak damaging a player''s chances.)

Sponsor:

#2 mmelson   Members   -  Reputation: 232

Like
Likes
Like

Posted 09 August 2001 - 08:50 PM

Hello. I think this is the sort of thing you are looking for...

First, let me describe some terms:

SUM: This term is equal to the sum of all the previous return values from the function. "True" is counted as +1, "False" is counted as -1. Ex: If the fn had returned 10 trues and 8 falses, then SUM would be -2.

C: C is a constant which will need to be tweaked in order to get it to fit perfectly. C is the cap for the difference in the number of true and false responses. For example, if C = 5, then there can be no greater than 5 more true responses than false responses (and vise versa) before the fn forces a response of the opposite type.

The function below will return a weighted probability that can be used as as usual for determining a true or false. It needs to be given a probability (called x below) between 0 and 1 (inclusive). Here is the actual (simple) fn in psuedocode:

if (sum >=0)
p = x - (SUM / C)*x
else
p = x - (SUM / C)*(1-x)

I hope this helps. If it''s not what you are looking for, let me know and I''ll see what I can do.

Mike Melson

#3 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 10 August 2001 - 03:34 AM

What application do you have in mind for this?

If you really care about this kind of binary coin flipping example, you will be much better off by randomly sorting or permuting an equal number of true and false values.

#4 Grudzio   Members   -  Reputation: 122

Like
Likes
Like

Posted 10 August 2001 - 09:23 AM

quote:
Original post by Kylotan

Imagine you are about to flip a coin 10 times. You expect 5 heads. So you flip it coin 9 times, and get 5 heads and 4 tails. Given a proper coin, the 10th flip has a 50% (p = 0.5) chance of being heads. This means that, once you''ve had 9 flips, you have a 50% chance of scoring 6 heads. However at the start, it was a 50% chance of scoring 5.


A small correction. Probability that in 10 flips you get 5 heads
is not 0.5 but smaller. To solve such problems (k succeses in N trials) you must use Bernoulli schema:
P(N,k)= N!/(k!*(N-k)!)*pk*(1-p)N-k
N - number of trials, k - number of succeses
p - probability of success, P(N,k) - probability that in
N trials you have k succeses.
So P(10,5) = (10!/5!*5!)*1/1024 = 252/1024
quote:

I have seen the term ''stochastic'' used in some contexts similar to this, but have yet to find an explanation of the term that is both precise and yet not overly complex. Perhaps this is the solution to my problem, but I don''t know.


The only meaning of "stochastic" I know about are stochastic processes. In such case stochastic means random as opposite to deterministic. I dont think they can help you,but I can be wrong.
quote:

(For those who are interested, basically I just want this so that I can have a random number system in a game that allows for freak events, but takes corrective action to reduce the chance of an unlucky streak damaging a player''s chances.)


Maybe you can try something like this, each time the "bad" event
happens decrease its basic probability by some amount. After that
let it slowly grow, so after some time it reaches its base probability.

K.

#5 Kylotan   Moderators   -  Reputation: 3338

Like
Likes
Like

Posted 10 August 2001 - 09:26 AM

mmelson... that system seems close to what I am getting at. I was hoping there wouldn''t be a magic constant that I would have to pick on trial and error, though And I couldn''t just add +1 or -1 to ''sum'', rather it would be fractional parts of 1 indicating how far from the expected result the actual result was. If that makes sense. Ideally, I would have liked to eliminate any ''hard upper bound'' on the function, which is what is represented by the constant. I know that if I remove the hard upper bound, then there is always a chance that the correction method I use will not kick in, but I guess I would just prefer the corrective element itself to be based on a probability than a certainty.

Anonymous... I thought I made myself clear in the original post... it would be working on a percentage system, where I say "ok, this action has a 37% chance of success" and I want the system to return true about 37 times when called 100 times. The only difference between what I want, and a standard pseudo random number generator, is that when I''ve called it 99 times and had 36 true results, I want a better than average chance of getting a 37th true result on that 100th call. Whereas a normal PRNG is stateless (as far as probabilities are concerned... I know they have internal state for their own purposes) and would just have a 37% chance of returning true on that 100th call, regardless of what had gone before.

#6 Kylotan   Moderators   -  Reputation: 3338

Like
Likes
Like

Posted 10 August 2001 - 09:35 AM

quote:
Original post by Grudzio
A small correction. Probability that in 10 flips you get 5 heads
is not 0.5 but smaller. To solve such problems (k succeses in N trials) you must use Bernoulli schema:
P(N,k)= N!/(k!*(N-k)!)*pk*(1-p)N-k
N - number of trials, k - number of succeses
p - probability of success, P(N,k) - probability that in
N trials you have k succeses.
So P(10,5) = (10!/5!*5!)*1/1024 = 252/1024

Yes, of course. I only understood 1% of what you just said but I do know that what I said was wrong What I should have said was more like "However at the start, you had a higher chance of getting 5 heads than 6."

quote:
The only meaning of "stochastic" I know about are stochastic processes. In such case stochastic means random as opposite to deterministic. I dont think they can help you,but I can be wrong.

I read that stochastic processes were (sometimes) to do with some sort of probabilistic compensation for events that take a random amount of time and can only be measured once they complete. I figured this had a relevance to my system since you can''t know how many heads or tails you will have got until you flip it 9 times, however you know how many you want after 10 flips. But I know I''m largely stumbling in the dark here

#7 mmelson   Members   -  Reputation: 232

Like
Likes
Like

Posted 10 August 2001 - 06:24 PM

Well, how about replacing C with the term (NUM_TIMES + 1), where NUM_TIMES is (obviously) the total number of time that the function has been called. That way, there is always a positive probability that any given option will be selected (unless, of course, the given probabilites are 0 or 1, which still work correctly).

Also, I''m not sure why you would have to add a fractional value to SUM instead of +1 or -1. Maybe you could explain what sorts of return values the function would be spitting out. If they are just true/false values, then this system would work (I may just not be explaining what I mean well enough...).

Hope this helps.

Mike Melson

#8 Kylotan   Moderators   -  Reputation: 3338

Like
Likes
Like

Posted 10 August 2001 - 10:17 PM

The reason for the fractional values is because I don''t want it ''overreacting''.

Scenario: I call RandPercent(99) 5 times. It returns true 5 times. If C was 5, then the next call to RandPercent(99) will return false. This is obviously erroneous behaviour. Scoring 5 trues in a row for a 99% query is less ''unbalanced'' than 5 trues in a row for a 50% (coin flipping) query. Therefore it should be ''tipping the scales'' far less. With me?

#9 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 13 August 2001 - 03:30 AM

I''m not ready to stop pushing permutation yet.

You''re chance is 37%. You generate a list of true/false values, and you set 37% of them to ''true.'' Then you permute the list randomly. (Fairly easy and cheap to do) Each call to get random returns the next value in the queue. When you hit the end, you have a choice of looping back to start or re-permuting the list and starting over.

This also has the advantage of cutting down the number of potentially expensive calls to your system rand function, by essentially generating a look up table of random values.

Want more general percentages? Permute the numbers from 0 to 99, then treat chance < randvalue as a true. You''ll be true exactly chance out of 100 times.



#10 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 13 August 2001 - 03:30 AM

I''m not ready to stop pushing permutation yet.

You''re chance is 37%. You generate a list of true/false values, and you set 37% of them to ''true.'' Then you permute the list randomly. (Fairly easy and cheap to do) Each call to get random returns the next value in the queue. When you hit the end, you have a choice of looping back to start or re-permuting the list and starting over.

This also has the advantage of cutting down the number of potentially expensive calls to your system rand function, by essentially generating a look up table of random values.

Want more general percentages? Permute the numbers from 0 to 99, then treat chance < randvalue as a true. You''ll be true exactly chance out of 100 times.



#11 Kylotan   Moderators   -  Reputation: 3338

Like
Likes
Like

Posted 13 August 2001 - 07:11 AM

This would involve having a state of about 100 bytes for every player (since each player would have his or her own PRNG state to keep the game balanced for them) and this could get unwieldy in a multiplayer game...

#12 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 13 August 2001 - 08:00 AM


Nah. With a little extra book keeping work, you can just keep one state list, and all you need per player is a one or two byte index into the list describing their current position. You''re going to need that much state info per player no matter which scheme you use.

I''d probably set up a state list a few hundred bytes long and randomly scatter the players starting points on the list as they join the game, and never recalculate. I doubt they''d notice that there''s a pattern a few hundred positions long if they endlessly repeat the same action.

Actually, /I/ would probably just use rand, because I don''t care about the observed probablity matching to the expected one under any sort of time bound.

#13 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 13 August 2001 - 08:04 AM

Hmm. It also occurs to me that rolling a rand function in this manner will produce a deterministic game, which is good for the ever cool instant replay or demo recording function.

#14 Kylotan   Moderators   -  Reputation: 3338

Like
Likes
Like

Posted 13 August 2001 - 10:07 AM

The problem with this system is that although it ensures you have a perfect spread of probabilities over the 100-call period, it still doesn''t actually do any balancing. If the pattern of the calls (eg. a sequence of: RandPercent(20); RandPercent(80) is a low-high repeating sequence) happens to closely correlate (or negatively correlate) with the shuffled sequence of numbers from 1 to 100, then the results can be erroneous and the system does nothing to balance this. In this sort of situation, it''s little better than just using rand(). You can guarantee a good and even distribution ''behind the scenes'', but it''s not guaranteeing a ''fair'' deal for the game entity in question, which is what I''m aiming for.

#15 Dragonus   Members   -  Reputation: 122

Like
Likes
Like

Posted 17 August 2001 - 09:50 AM

I'm not sure if this will give you the probability distribution you're looking for. I don't even know if it'll even guarantee that it'll come close. But it's a random thought I came up with, so it was worth a shot.

    
void RandomChance ( int percentage )
{
static int difference = 0;
// This will be an integer that remembers our bias.

// difference will equal the # of true returns minus the

// # of false returns.


if (difference == 0) // If there's no bias

{
// Test the percentage directly to the random number.

// Then increment or decrement difference based on outcome

}
else if ( difference < 0 ) // If more false returns...

{
// Boost your probability score

percentage = 100 + (percentage / (difference - 1));
// (NOTE: Difference < 0, so division above will be < 0)

// (ALSO NOTE: The -1 is to correct for the case when

// difference == -1)

// Pretend you're repeatedly calling RandomChance(50%).

// Fore each successive false, your probability rises.

// First 50%, then 75%, then 83.3%, then 87.5%, and

// upwards to 100.


// Test new percentage & update the difference variable

}
else // If more true returns...

{
// Lower the odds

percentage = percentage / (difference + 1);
// (NOTE: The +1 is to correct for the case when

// difference == 1)

// Pretend you're repeatedly calling RandomChance(50%).

// For each successive true, your probability falls.

// First 50%, then 25%, then 16.7%, then 12.5%, and

// downards to 0.


// Test new percentage & update the difference variable

}


Will this work?

~ Dragonus
If F = ma, and Work = Fd, does that mean that Work = mad?

Edited by - Dragonus on August 17, 2001 4:54:11 PM

#16 Torn Space   Members   -  Reputation: 122

Like
Likes
Like

Posted 17 August 2001 - 09:54 AM

If you "balance" out your random number, is it still random?

#17 Kylotan   Moderators   -  Reputation: 3338

Like
Likes
Like

Posted 17 August 2001 - 11:11 AM

Dragonus: that is very similar to mmelson''s first reply, except that instead of a linear change in probability you have a gradually decreasing change in probability.

What all these solutions are missing out, is the point I made in the post beginning "The reason for the fractional values..." If you are only counting the difference between true and false returns, you are considering them to be equally weighted, which they are not. They can be weighted arbitrarily, depending on what kind of calls I am making to the generator. If I call RandPercent(90) and get 5 true answers, your system will make the 6th call have a (90 / (5 + 1)) == 15% chance of returning true. This is wrong: there should still be a >50% chance of returning true.

I figure that the algorithm is on the right lines, however. Instead of adding 1 to ''difference'' for every ''true'' and subtracting 1 for every false, I think I need to add different values that reflect the likeliness of the past calls. For example, when I call RandPercent(90) and get true, that other 10% needs carrying over. Basically, I add less than 1 each time. Perhaps I add 0.2, or something, since the ratio of 0.2 to 10% is the same as 1 to 50%. But I''m not sure. Nor would I know how to prove its ''correctness'' if I tried it.

Torn Space - no, it''s not random any more. But then, they were only pseudo random in the first place. I''m not really interested in how random they are, just that I get a stream of varying numbers which are biased towards ''proving the statistic'' (eg. 10% chance of success at a given activity) rather than each call being independent.

#18 Diodor   Members   -  Reputation: 517

Like
Likes
Like

Posted 18 August 2001 - 07:58 PM

This thread reminds me of a "Married with children" show when Al Bundy had blind luck throughout the episode. But all this luck made him terribly unhappy because he knew he was only so lucky because something awfull was gonna happen to correct the odds. The show ended of course with every lucky thing that happened turning around (just like in your algorithm ) and Al finally happy and relieved of all the presure saying "I''M FREE !!" to the officer arresting him (for owning a stolen car he won at a card game).

#19 liquiddark   Members   -  Reputation: 331

Like
Likes
Like

Posted 19 August 2001 - 09:26 AM

Kylotan, I don''t see how you expect any system to perform much better than a standard PNRG if you don''t provide a "cap" to its behaviour. If you''ve got an open-ended system, any sufficiently dimensionally independent PNRG (and there are lots) is in fact pretty close to the definition of proving the statistic.

You''ve got to give a cap if you want the statistic proved to a much better degree. Perhaps a system size indicator would help, wherein small = 10 (the minimum for an integer percentage to be proven to the nearest 10th), medium = 100 (the minimum for an integer percentage proving), and large > 100 (can be proved to within one range level).

I have no idea what you would need this for, but I would suggest taking a long hard look at the design you''re using if the events you wish to bias are severe enough to undermine the average random number generator.

ld

#20 liquiddark   Members   -  Reputation: 331

Like
Likes
Like

Posted 19 August 2001 - 11:06 AM

Ok. Here is an attempt at a solution despite my trepidation as to its tractability. Basically, for each call to the function you add or subtract directly from the percentage.


int NewRand(int pctg)
{
static int trues = 0; //total #trues
static int totalcalls = 0; // total # function calls
int newChance; // adjusted value of percent chance
int result;

// adjust the percentage to compensate for the difference
// between actual and desired. As the difference approaches
// the order of the percentage itself, the system approaches
// 0% chance of returning a true.
// Might as well increase the # fnc calls here, as well
newChance = pctg - ((int)((float)trues/(float)(++totalcalls)) - pctg))

// constrain the chance to 0 thru 100, obviously
if (newChance < 0) newChance = 0;
else if (newChance > 100) newChance = 100;

// GenRand is a generic PNRG on a percentage system
result = GenRand(newChance);

// If we got a true record it
if (result) ++trues;

return result;
}


This is pretty close to what Mike Melson wrote earlier, but I came up with it independently and figured I'd put it down to make sure we're on the same page.

ld

Edited by - liquiddark on August 19, 2001 6:09:16 PM




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS