A coding conundrum - weighted randoms?
BlitzMax Forums/BlitzMax Programming/A coding conundrum - weighted randoms?
| ||
| I'm having a brain fart. What I want to do, is have a call to Rand() that will return a result, either 0, 1, or 2. Let's call them Bronze, Silver, and Gold for the sake of coherence. I have a 'bias' parameter, which can be any value from 1 to 10. 1 will be mostly bronze, 10 will be mostly gold. A bias of 5 would be a fairly even mix of all three. What's the best way of generating a random result while taking the bias value into account? |
| ||
| I was googling this yesterday but didn't find a suitable solution that suited my purpose. Normal weighted randoms have a table representing probabilty, where; prob[] = [0,0,0,0,0,1,1,1,2,2] result = prob[ rand( 0, 9 ) ] You could do it with a set of tables; weight1[] = [0,0,0,0,0,1,1,1,2,2] weight2[] = [0,0,0,1,1,1,1,2,2,2] weight = rand( 0, 1 ) if ( weight = 1 ) return weight1[ rand(0,9) ] else return weight2[ rand(0,9) ] end if It's a quick and easy way, simple to test run. I don't know enough about probability math to describe a better solution :) Cheers Matt ( first post! w00t!) |
| ||
| I've spent unhealthy amounts of time on google over this too, and that's the best solution I could come up with as well. But I can't help feeling there has to be a better way? Oh, and welcome. :D |
| ||
| Thanks for the welcome :) Food for thought; The weight tables can also be parabolic curves. Think of the X axis going left to right, Y is the height (or value); [0,0,0,1,1,1,1,2,2,3,2,2,1,1,1,1,0,0,0] The form of the curve can give more weight to higher or lower values so there's no need to precalculate the probabilities. |
| ||
| Surely it's as simple as this? maxbias=10 bias=rand(1,maxbias) value=rand(0,2) result=((value*maxbias)+bias)/maxbias)-1 |
| ||
| didn't we have a biiiig discussion about this a few months ago? My method is to have an array of probabilities, and I think that would be clearer than matibee's method if you want the weighting to depend on a parameter. Strict Function weightedrand(probs#[]) Local p#=Rnd(0,1) 'generate a uniform random variable P, which we will transform into a weighted variable X Local i=0 Local tot#=probs[0] While p>tot i:+1 tot:+probs[i] Wend Return i End Function 'test - draw a bar graph of 1000 runs Graphics 600,600,0 SeedRnd MilliSecs() Local probs#[] Local results[3] Local ox=-1,mx Local i,c Local bias# While Not (KeyHit(KEY_ESCAPE) Or AppTerminate()) mx=MouseX() If mx<>ox bias#=.1+.8*(mx/600.0) 'bias is 0.1 when mouse is on left of screen, 0.9 when mouse is on right of screen probs=[bias*2/3,1.0/3,(1-bias)*2/3] 'remember, probabilities have to add up to 1 'I've made the probability of getting 1 to be halfway between that of 0 and 2 'which effectively means the probability of getting 1 is always 1/3 For i=0 To 2 results[i]=0 Next For c=1 To 1000 i=weightedrand(probs) results[i]:+1 Next ox=mx EndIf DrawText "Bias: "+bias,250,0 Local width=600/Len(results) For i=0 To 2 Local x#=i*width Local y#=600-results[i]*600/1000.0 DrawRect x,y,width,600-y DrawText results[i]+"/1000 (P = 0."+Int(probs[i]*100)+")",x,y-13 Next Flip Cls Wend markcw - your code can generate a result of -1 when bias=1 and value=0. |
| ||
probs=[bias*2/3,1.0/3,(1-bias)*2/3] That's it, right there in a nutshell :) |
| ||
| There is a nice article about never-ending shuffled sequences (when random is not random enough) over here. Although the source code is in Java the introduction explains it all. |
| ||
| Someone asked about this a while ago I think. What springs to mind is simple to make an array which represents the frequency of occurance of each value, so maybe you'll have 3 x 1's, 10 x 2's and 25 x 3's. Then just pick a random index. I think this is an integer version of the above formula ;-D |
| ||
Here's what I understood TommyH's article to mean:Function shuffler:tshuffler(numbers[]) s:tshuffler=New tshuffler s.numbers=numbers Return s End Function Type tshuffler Field i Field numbers[] Method nxt() c=Rand(i,Len(numbers)-1) b=numbers[c] numbers[c]=numbers[i] numbers[i]=b i:+1 If i=Len(numbers) i=0 Return b End Method End Type s:tshuffler=shuffler([1,2,3,4,5]) For c=1 To 25 Print s.nxt() Next It's like a knuth shuffle that loops back round when it's done. ImaginaryHuman - your method is what matibee suggested in the second post. GreyAlien made the good point in the old thread that it involves only one array lookup, but I don't like it just from an aesthetic standpoint. This all just depends on how comfortable you are with the mathematics of probability, though. Maybe that's an idea for my next warpy code maths blog? |
| ||
| We have the usual difficulty here. The problem would be easy if it were well defined. But we don't know what bias really means. For example, bias = 1 means "mostly bronze". What number is that? For a given bias we must determine the probability of bronze. Call it pB. Then we generate a random float in the range 0 to 1 with Rnd(0,1). If this number is less than pB then we have chosen Bronze. Otherwise we must choose Silver or Gold, according to some weighting. To do this we need probabilities for Silver and Gold, call them pS and pG. Once we know these we generate Rnd( 0, pS+pG). If the value is less than pS then we choose Silver, otherwise we choose gold. The only remaining task to define bias. i.e. for a given bias just what are pB, pS, and pG. They must be non-negative and add up to 1. |
| ||
| Actually, following what you say, the probability of getting a silver is (1-pB)*pS, not just pS, since you need to not get a bronze first. |
| ||
| You could also just use RndFloat() and then if the value is <0.1 choose bronze, if it's >0.6 choose gold, otherwise choose silver ?? |
| ||
| http://www.blitzmax.com/Community/posts.php?topic=76412#854464 |
| ||
| Actually, following what you say, the probability of getting a silver is (1-pB)*pS... The probability of Silver is (1-pB) * ( pS / (pS+pG) ). pS+pG equals 1-pB, so this simplifies to pS as desired. This is all standard technique when dealing with conditional probability. |
| ||
| I went with matibee's original suggestion. It suits my needs, doesn't need to be especially fast (not that its slow) as I'm not doing it in realtime, and was easy to implement. All the other suggestions are a bit overkill for my requirements. Feel free to discuss further though, in case somebody is asking the same question later. |
| ||
| That's fine as long as it represents what you want. His scheme is: bias must be in the range 0 to 1. Silver alway has probability 1/3. Bronze and Gold split the remaining 2/3, based on bias, e.g. bias = 0.4 means bronze gets 40% of the non-silver leftovers. Using these probabilities the method I outlined becomes: If Rnd( 0, 1 ) <= 1.0/3.0 then result is Silver. Else if Rnd( 0, 1 ) <= bias result is Bronze. Else result is Gold |
| ||
| I had issues with that method when it came to my own needs. The article TommyH pointed out would have suited me more, but I didn't find that method and ending up rolling my own variation for when 'random is too random'. Rand averages out nicely over very large samples and it's too easy to type 'for t = 0 to 10000000' in test code and get a false impression that this will suit your purpose. In smaller test runs (say, 20 or 50) it's easy to see that your 'weights' can often have very little bearing. I had 8 powerups with the probability array [0.2,0.2,0.15,0.05,0.05,0.2,0.1,0.05] but wanted to make sure they all came out over small runs. Again the shuffle method would have been perfect, but here's what I came up with... Keep a dynamic probability array to choose from When an item is chosen, half it's current probability (or experiment with other ratios) Spread the other half of it's probability over the other 7 items according to their initial probabilites It worked out well enough to live with but next time I'll test out the never ending shuffle method. |
   |