Randomization Buffering Performance

[Rinobi]

Just to get our definitions down, by buffering, I mean resistance to change.
While working on an actor generator script I realized that the randomization of certain
stats would be too varied on an actor by actor bases. I did come up with a way to remedy
this problem, but it's way too performance intensive to be a viable solution. Here's what I mean:

Let's say we want the actor's maximum level to be randomized.
actor.max_level = 1 + rand(98)
This is too random. There's an equal chance for the actor to land on any given level.
I want the middle value, 50, to be the most likely level.
We could do something like this:
actor.max_level = 20 + rand(60)
or this:
actor.max_level = Random.new.rand(20..80)
but its all just as random as before with some potential values excluded.
I want an actor's max level to be more likely to land on 50, but still have the potential
to deviate to very low or high values (just a lot less likely. I came up with this:

#==============================================================================
# ** Array
#------------------------------------------------------------------------------
#  This class handles arrays.
#==============================================================================
class Array
  #--------------------------------------------------------------------------
  # * Sum of Array Elements
  #--------------------------------------------------------------------------
  def sum; inject(nil) {|sum, x| sum ? sum + x : x } end
  #--------------------------------------------------------------------------
  # * Mean of Array Elements
  #--------------------------------------------------------------------------
  def mean; sum / size end
end

buffer = 100 # higher values increase resistance to change.
actor.max_level = Array.new(buffer){Random.new.rand(1..99)}.mean.round.to_i
It basically just creates an array of potential outcomes and returns the average value.
The higher the buffer, the less deviation from the average value. (Also lowers performance)
It works, but the performance is terrible. I'm looking for an alternate, performance friendly, solution.

 

[gstv87]

basevalue + rand(+/- margin) = basevalue - (margin-marginlow) + rand((margin - marginhigh))

so, if you want a center of 50 with a random of 20 up and down,
30 + rand(40)

or

basevalue + rand(small_deviation) + high_deviation * rand(1)
40 + rand(20) + 60 * rand(1)

 

[Sarlecc]

You have the right idea with averages. What you are looking for is whats known as a weighted random number algorithm here is a link that describes more working types blackbytes.
Here is one I made that should be very fast as it doesn't do any looping:

def randomWeight(min, max, weight)
  target = rand(min..max)
  return (target + weight) / 2
end

p randomWeight(5, 20, 10)

 

[Another Fen]

Do you need such a high buffer to begin with? After all, your theoretical chances to roll one of the extremes should be in the 1:10^200 range, which is pretty neglectable.

The easiest solution would probably be to reduce the number of rolls and the range of your possible results (for example actor.max_level = 50 + rand(11) - rand(11) ).

Edit2: Forget about the power operator, I'm pretty sure I messed up here... ^^

Spoiler

If you want to keep something like your amount of buffers, you maybe could use the power operator:
actor.max_level = 1 + (rand(99**10)**(1.0 / 10)).floor
This example would highly favor high levels (since the range of x in which floor(x**0.1) equals 98 is much larger than the range in which it would equal 0).

Edit: Nevermind, this is probably quite useless, since you cannot increase the exponent to much more than 100 before the calculation will yield "Infinity".
In this range, your original solution should also be viable.

Edit2: Forget about the power operator, I'm pretty sure I messed up here... ^^

 

[Rinobi]

@gstv87 Sorry, I'm not sure I understand what you're trying to show me.

@Sarlecc I'll check out the link soon, thanks for that. I wasn't sure how to word it; my initial search was futile.
Your code wouldn't work though:
random_weight(1, 99, 50)
max possible: (99 + 50) / 2.0 = 74.5
min possible: (1 + 50) / 2.0 = 25.5

@Another Fen I need control over the buffer. The odds should be astronomical depending on the buffer set.
It's gonna take me some time for me to wrap my head around your latest example, but it looks good.

While considering my options, I ran a test on your code with the highest possible buffer:

    buffer = 182 ; min = 1 ; max = 99
    average = (max - min) / 2.0
    iterations = 1000000
    record = Array.new
    iterations.times do |attempt|
      derivation = average - (rand((average - min + 1)**buffer)**(1.0 / buffer)).floor
      result = average + (rand(2) == 0 ? derivation : -derivation)
      record.push(result)
      print "Attempt #{attempt + 1}: #{result}\n"
    end
    print "Record Low: #{record.min}\n"
    print "Record High: #{record.max}\n"

Record Low: 44.0
Record High: 53.0
It seems to favor the low end. A buffer higher than 182 causes an infinity error.
If anyone is gonna test this themselves, I suggest lowering iterations to something more reasonable.

 

[Sarlecc]

Yea after thinking it over a bit I came to the same conclusion though I believe I found a quick fix for that:

def randomWeight(min, max, weights)
  target = rand(min..max)
  return ((target + weights.sample) / 2).floor
end

100.times do
p randomWeight(1, 99, [1, 99, 50])
end

This should allow for all numbers but generate mostly in the mid range. And you can apply more weight to it if you think that it needs more by just simply adding more numbers to the array.

Edit here is an example out put of what the above can do:

a = [0,0,0]
b = 0
10000.times do
    b = randomWeight(1, 100, [1, 50, 50, 50, 100])
    if b < 33
      a[0] += 1
    elsif b >= 33 && b < 66
      a[1] += 1
    else
      a[2] += 1
    end
end

print a
#[2132, 5380, 2488]

 

[Another Fen]

Uh, I made a typo here I think:
The average between min and max is
(min + max) / 2.0
obviously.

Though as mentioned, if you use a buffer of 181 here you'll have almost no variation, as the rates will drop increasingly fast (assuming Rubys random number generation spreads the numbers evenly):
derivation = 0 : 97.4182%
derivation = 1 : 2.5200%
derivation = 2 : 0.0604%
derivation = 3 : 0.0013%
derivation = 4 : 0.0000%
...
Of course this is still not that impressive, but I'm just wondering what you are using it for.
Edit: However, in the end I'm pretty sure I messed up here... At least when I simulated the chances to get a certain mean value, the numbers were far off these here.

Edit2: Will reply to the topic later, should really go to bed now

 

[MobiusXVI]

I want an actor's max level to be more likely to land on 50, but still have the potential
to deviate to very low or high values

What you're looking for is a controllable, 'normal' distribution. (If you're unfamiliar, see: https://en.wikipedia.org/wiki/Normal_distribution). By default, Ruby - and most programming languages - generate random numbers using a 'uniform' distribution from 0-1. However, you can convert this to a 'normal' distribution using the Box-Muller transform (https://en.wikipedia.org/wiki/Box–Muller_transform). So here's how you do it.

Generate two random numbers using Ruby's built-in functions. Let's call them u1 and u2.

u1 = rand()
u2 = rand()

Now we'll create a new number 'z' that represents a z-score taken from the normal distribution (https://en.wikipedia.org/wiki/Standard_score).

z = Math.sqrt(-2*Math.log(u1))*Math.cos(2*Math: PI*u2)

This value of z will be most weighted towards a value of zero but will vary from approximately -3 to 3 (technically negative infinity to infinity but the probability drops off sharply), so we can use it to generate values within the range that we want. From your example, we'd like to have the level land on 50, so that's going to be our mean (which we'll call 'm'). Now, we need to set our standard deviation (which we'll call 's'). The value of 's' will determine the likelihood of the other possible values. Let's choose a value of 10. This will set the probability of getting a level between 40 and 60 to be approximately 68%, and the probability of getting a level between 30 and 70 will be approximately 95.5%. Setting a larger value of 's' will let it deviate more while setting a smaller value will make it deviate it less. This is your 'buffer' value. Ok, now we need to convert our 'z' value from earlier to a usable level:

level = ( z * s ) + m

and we're done! Hope that helps.

 

[Sarlecc]

10000000.times do
u1 = rand()
u2 = rand()
z = Math.sqrt(-2*Math.log(u1))*Math.cos(2*Math::PI*u2)
m = 50
s = 10
level = ( z * s ) + m
if level > 99
  p level
elsif level < 1
  p level
end
end

#0.9723880535056821
#0.465862905667052
#-1.3430776009174465
#106.52049184542767
#103.0288487224546
#-3.995581328780432
#99.39029667296359
#-0.5322952738899929
#0.3380669167417807
#0.7939412220441397
#99.23847001169602
#-2.912946638535594

Well @MobiusXVI way does work it can have results that you might have to adjust further. For example using Math.abs on negative values or setting it to the max you want if it goes over it. Granted I was only able to get these results when I set the loop to ten million; but it could still happen (think of it as a chance of winning the lottery). You will also want to use a rounding method such as ceil, floor or round to make them whole numbers.

 

[Rinobi]

@Sarlecc It isn't a bad approach. I just need to modify the array until I get the results I want. It's actually a lot more flexible than my initial approach. I'll definitely add it to my core module for other projects and fall back on it if all else fails. Thank you.

@Another Fen It's mostly for a personal project I'm working on, but I intend to add this functionality to an actor generator script to be released soon. I'm using it for genetic deviation where large deviations represent a sort of mutation. These mutations can be beneficial or terrible but always rare. Without going into too much detail, this randomization method will need to run many times throughout the game as it is a part of the gameplay loop.

@MobiusXVI Wow. I'll need to read up the specifics but I get the gist. Here's my setup:

  #--------------------------------------------------------------------------
  # * MobiusXVI Weighted Randomization
  #--------------------------------------------------------------------------
  def mobius(min, max, mean, buffer)
    u1 = rand ; u2 = rand
    z = Math.sqrt(-2*Math.log(u1)) * Math.cos(2 * Math::PI * u2)
    [[(z * buffer) + mean, min].max, max].min
  end

Testing Setup: (I know the attempt printing is slowing it down)

    buffer = 10 ; min = 1 ; max = 99 ; mean = 50
    iterations = 1000000 ; record = Array.new
    iterations.times do |attempt|
      result = mobius(min, max, mean, buffer)
      print "Attempt #{attempt + 1}: #{result}\n"
      record.push(result)
    end
    print "Record Mean: #{record.mean.round(2)}\n"
    print "Record Min: #{record.min.round(2)}\n"
    print "Record Max: #{record.max.round(2)}\n"

Here are the results.
Record Mean: 49.99
Record Min: 4.2
Record Max: 99.0

I'm gonna stress test it some more to find the setting I need, but it seems to work pretty well. I'm sure the minimum value will show up eventually thanks to @Sarlecc's results.

Thank you so much for your help guys. I think I have enough to work with now. I'm gonna do some reading and additional testing. I truly appreciate the assistance!