• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

This topic is now archived and is closed to further replies.

Kylotan

Self-balancing random number generation

36 posts in this topic

Just a little suggestion....say for instance you only store a certain number of past values. Say 50, for example. First you start with your basic algorithm for generating a random number, then store the result in a linked list, queue, whatever. Then build the first 50 numbers by taking the number of past values that are opposite to what you want (In your case this would involve numbers less than .5, greater then .5), and using that number as the probability of generating the value you need on this one. Makes Sense? Then, when you reach 51, 11, etc., you simply discard the first value and add the new value. A linked list would be great for this.
0

Share this post


Link to post
Share on other sites
Sorry if my wading into this thread so late causes a rehash of old stuff...

Kylotan: You have a problem in your requirements for the system that makes a solution not possible.

By biasing the coin flip (or roulette wheel for continuous variables) so that in the limit as the number of trials approaches a given number N, the apparent bias of the coin approaches the actual bias (i.e., k/n -> p(success,t=0); k= number of successes, n = number of trials held so far) means that you no longer have a random process of independant trials. You''re coin flips will be correlated and what you will be producing is the equivalent of a coloured noise process.

However, you state that you desire a system that does not maintain information about prior flips. I don''t see this as being possible. You will need to maintain some information regarding the sequence generated so far. In particular, the coloured noise will be a time varying function (time is the number of trials conducted so far).

quote:
Original post by Kylotan
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.



Stochastic is best defined as ''containing an element of unpredictability''. More formally, if a variable X can be explained as a (possibly non-linear) function of a set of other variables, Y, then X is a random (or stochastic) variable if there exists a residual variance in the values of X when Y is held constant.

quote:
Original post by Kylotan
(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.)


You would be far better off just to stick with random numbers and maintain a moving window of behaviour that broke streaks of good luck or bad luck by inserting a failure or success respectively.

The easiest way to do this is to reject any coin flip if the sequence of previous flips (over a window of length k) are identical. Simply resample from the distribution (which, if it is binary, means return the desired result). In the limit as the number of trials is large, this insertion will not appreciably harm the statistics of your sequence.

Cheers,

Timkin
0

Share this post


Link to post
Share on other sites
quote:
Original post by Timkin
However, you state that you desire a system that does not maintain information about prior flips. I don''t see this as being possible. You will need to maintain some information regarding the sequence generated so far. In particular, the coloured noise will be a time varying function (time is the number of trials conducted so far).

The system will not be able to store the previous sequence in its entirety due to implementational limitations. (Finite RAM and all that.) But it could happily store the number of samples, plus the mean of the returned values. Or any other measure of central tendency, or any other value that needs recording. It just can''t record the whole sequence because that will grow infinitely, and is thus impractical.

quote:
You would be far better off just to stick with random numbers and maintain a moving window of behaviour that broke streaks of good luck or bad luck by inserting a failure or success respectively.

The easiest way to do this is to reject any coin flip if the sequence of previous flips (over a window of length k) are identical. Simply resample from the distribution (which, if it is binary, means return the desired result). In the limit as the number of trials is large, this insertion will not appreciably harm the statistics of your sequence.

This is all very well for coin flips. Coin flips are trivial to deal with. However, I am not using coin flips. How do I do something like this if I get 2 true results from 10 calls, when in fact I only expected 1 true result (ie. a 10% chance)?
0

Share this post


Link to post
Share on other sites
Kylotan, did you see my last post? I think that''s what you''re looking for...

~ Dragonus
0

Share this post


Link to post
Share on other sites
quote:
Original post by Dragonus
Kylotan, did you see my last post?

Well, I don''t quite see how to get around the ''max calls'' problem, for starters. But the other issue is that it assumes the same percentage being passed to it each time. I don''t want to limit the procedure to only working on a given probability: I just want it to know whether it''s been scoring true more than it ''should'' or false more than it ''should'', on input values which can vary.


0

Share this post


Link to post
Share on other sites
It''s early, I''m tired, so maybe this has already been suggested. Why not generate a number between 0 and 1. A value greater than the number of successes divided by the number of roles would be needed for a success. So if you had ten roles already and six successes you would only have a 40% chance of a success. With a bit of thought this could be expanded out to more than a true/false outcome, but as I said it is too early to think clearly.
0

Share this post


Link to post
Share on other sites
Sigh.

I don''t think that you have fixed your design requirements firmly enough in your own head. First you complain that a standard PRNG won''t get enough samples, then you state that storing values will ''grow to infinity.''

I think you need to figure out how many calls you really expect this system to get, and when resets will or will not be noticable by the user. Then you''ll really know if you can cap the number of calls or not... and make no mistake, you will either have to cap the number of calls, or stick with one percentage per instance of your generator object.
0

Share this post


Link to post
Share on other sites
Oops, I goofed a bit on the equation. Here's what it should be...

    
original * (maxCalls / 100) - trueReturns
tweaked = -----------------------------------------
maxCalls - totalCalls


That's done so that the numerator will be with the same order of magnitude (roughly) as the denominator. (Also assumes original is between 0 and 100. If original is between 0 and 1, i.e., a fraction, replace the 100 with 1.)

~*~*~*~

Actually, Kylotan, it doesn't assume that it will get the same probability every time -- I was just using the same probability case as an example:

If you assume maxCalls == 100, your first call to the function (let's say original == 90 the first time), trueReturns == totalCalls == 0, so you get 90%.

Assume you get a true next time you call it 50% being the original percent. trueReturns == totalCalls == 1, so the real probability is (50-1)/(100-1) = 49/99 = 49.5%.

Assume you then get a false and call it at 30%. TrueCalls == 1 and totalCalls == 2. So your chance now is (30-1)/(100-2) = 29.6%. A similar call to 70% would give (70-1)/(100-2) = 70.4%. It will keep the odds you want.


As far as "getting rid of" the maxCalls number, I still think setting it "high enough" would work. All you have to do is make sure you don't call it that many times. If you set it to exactly the number of calls you'll be making, this equation will be exact. However, if you increase the maxCalls number, it won't be perfectly exact, BUT the probabilities will follow the distribution you're looking for.

Given your explanation of the problem (when you specified a number of calls), this is exactly the equation you're looking for. But if you want to make any number of calls to the function, all you have to make sure is that maxCalls is significantly bigger than the actual number of times you intend on calling the function; if you set it "high enough", you'll never run into that problem.

~ Dragonus

Edited by - Dragonus on August 22, 2001 9:56:57 AM
0

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Sigh.

I don't think that you have fixed your design requirements firmly enough in your own head. First you complain that a standard PRNG won't get enough samples, then you state that storing values will 'grow to infinity.'

Where did I say anything about a standard PRNG not getting enough samples? *looks very confused*

EDIT: Oh, I see: you misunderstood what I was referring to. Any random sampling is subject to higher rates of error given smaller samples. A normal PRNG is going to have almost zero error, eventually, but 'eventually' is too late. All I want is a system that can calculate the error (which is theoretically possible since we always know what the 'expected' outcome is, and just how likely it is), and take action to reduce that error by biasing subsequent calls.

quote:
I think you need to figure out how many calls you really expect this system to get.

As many as it needs. There is no fixed amount, nor can there be.

Edited by - Kylotan on August 22, 2001 12:02:04 PM
0

Share this post


Link to post
Share on other sites
quote:
Original post by Dragonus
But if you want to make any number of calls to the function, all you have to make sure is that maxCalls is significantly bigger than the actual number of times you intend on calling the function; if you set it "high enough", you''ll never run into that problem.

Ok, I''m with you, and this is certainly along the right lines, but: if you make ''maxCalls'' too high, then the balancing effects become minimal.

I feel sure there must be some way of doing this that doesn''t have some fixed bound, because given enough ''error-correction'', what has gone previously can be considered to have been adequately compensated for. Am I making sense?

0

Share this post


Link to post
Share on other sites
The method I (accidentally) double-posted earlier is guaranteed to work "correctly" from the get-go, has no fixed upper bound, and I''m even surer now than I was at the time that it is extensible to any vector of weighted probabilities. I believe there are a number of ways to address its deficiencies, as well.

ld
0

Share this post


Link to post
Share on other sites