Snippet GetChance

[kingkingyyk3]

library GetChance
/*
      Get Chance v1.0.4
        by kingking

  GetRandomInt/Real in warcraft 3 are commonly used to get the chance to trigger something, like effects.
  However, they are not precise.
  They will return close values sometimes.
  This has caused the chance is not so precise.
  This library is aimed to solve that.
  
  Usage :
  Chance.define(real probabilityToProc, integer weightage) -> Chance
  vars.getChance() -> boolean
  vars.reset() = Reset the allocated chance.
  set vars.probability = <probability>
  set vars.weightage = <weightage>
  
  It is a good idea for attaching this to units because allocated chances to return true are different.
  For best precision, probabilityToProc * weightage should be whole number.
  Weightage is the number for checking each loop.
  If you put 10 for it, then each 10 times of .getChance will reset the chance.

*/

    struct Chance
        private integer countdown
        private integer weight
        private integer procCount
        private real probably
        private integer left
        
        static method define takes real probabilityToProc, integer weightage returns thistype
            local thistype this = thistype.allocate()
            
            debug if weightage <= 0 then
                debug call BJDebugMsg("GetChance error! Invalid Weight found!")
                debug return 0
            debug endif
            
            set .probably = probabilityToProc
            set .procCount = R2I(probabilityToProc * weightage)
            set .weight = weightage
            
            return this
        endmethod
        
        method reset takes nothing returns nothing
            set .countdown = .weight
            set .left = .procCount
        endmethod
        
        method operator probability= takes real r returns nothing
            debug if r < 0. and r > 1. then
                debug call BJDebugMsg("GetChance error! Invalid Probability found!")
                debug return
            debug endif
            set .probably = r
            set .procCount = R2I(r * .weight)
        endmethod
        
        method operator weightage= takes integer i returns nothing
            debug if i <= 0 then
                debug call BJDebugMsg("GetChance error! Invalid Weight found!")
                debug return
            debug endif
            set .procCount = R2I(.probably * i)
            set .weight = i
        endmethod
        
        method getChance takes nothing returns boolean
            if .countdown == 0 then
                call .reset()
            endif
            if .probably == 1. then
                return true
            elseif .probably == 0. then
                return false
            endif
            set .countdown = .countdown - 1
            if .left > .countdown then
                return true
            endif
            if .left > 0 and GetRandomReal(0.,1.) <= .probably then
                set .left = .left - 1
                return true
            endif
            return false
        endmethod
    endstruct
    
    
endlibrary

UPDATES :
v1.0.0 : Initial Release.
v1.0.1 : Allow users to change probability and weightage freely.
v1.0.2 : Switched algorithm to array stack.
v1.0.3 : Switched algorithm to linked list.
v1.0.4 : Switched algorithm. Does not require preloading chance now and lot's faster(271% faster than v1.0.0).
v1.0.5 : Polished current algorithm by a small chance detecting, thus the distribution is better.

 

[saw792]

Wait, let me get this straight. You're solving the issue of 'randomness' by making everything pseudorandom?

 

[kingkingyyk3]

Yes, you can say so.

 

[Deaod]

http://www.wc3c.net/showthread.php?t=107967
also:
http://www.wc3c.net/showthread.php?t=105330

Both of these solve the issue better than you do.
Why did you bother?

 

[Accname]

i dont see a point in this, for me random means random. if you use random and you get three times the same value that is the only prove that it really is random because you havent gotten what you were expecting.

if people dont like it they should not use it. if you want your random factors to be less random do some pseudo random if you like but please tell the users so instead of calling it random still because it aint anymore.
(yes i know there is no "random" in a computer, i dont want to start a discussion)

 

[kingkingyyk3]

Both of these solve the issue better than you do.
Why did you bother?
They are working on difference algorithm and interface.
Mine too.
Anyway, how did they solve the issue in better way?

 

[Deaod]

For one, they dont use an algorithm with the possibility of infinite complexity.
Secondly, they can be more random or less random than your implementation.
Thirdly, your allocation algorithm for indices is off (starts at 2).

Yes, GetProc works with a different interface.
ChanceToProc, however, does not (besides the names).

Also, both offer retrieving the current probability, which yours does not (and can not, for technical reasons).

Did you try using a "weight" of 1 and a chance <1?

Edit: I forgot to mention that your library doesnt solve the issue of long streaks.

 

[kingkingyyk3]

For one, they dont use an algorithm with the possibility of infinite complexity.
Does not fail for me.
I have another algorithm, that's using linked list, which does not have this possibility.
But this solution is working well so far.
I shall switch to linked list until someone faced the problem.

Secondly, they can be more random or less random than your implementation.
Because of different algorithm. No randomie at here, because this library is not for random chances, but for the exact numbers to proc.

Did you try using a "weight" of 1 and a chance <1?
It will return 0.0. Why would you put this value? LOL. I mentioned it in demo spell's script, the probability * weightage should be whole number, for best precision.

 

[Deaod]

Does not fail for me.

Try using 0.99 probability, and 100 "weight". If you want more, use 0.99 and 1000 weight. Enjoy your thread crash.

No randomie at here, because this library is not for random chances, [...]

This library is nothing more than caching random numbers. Its still random, only that (EDIT: removed "before") you know the result before you actually need it.

Why would you put this value? LOL.

Because im a dumbass who wants to break your library. If i can break it intentionally, chances are that others will break it unintentionally and wonder why things dont work. You should make sure users cant break your libraries, even intentionally.

I mentioned it in demo spell's script, the probability * weightage should be whole number, for best precision.

Well how about you mention it where it actually matters? Like in the description of your library?

 

[kingkingyyk3]

struct Test
    private static method onInit takes nothing returns nothing
        local Chance c = Chance.define(0.99,100)
        call BJDebugMsg("Ok")
    endmethod
endstruct

Worked well.

 

[Deaod]

Okay, heres a benchmark.

Just a few conclusions: GetProc and GetChance beat the shit out of each other trying to place last in benchmarks. Using GetProc, you get one random bit of information at the cost of 0.045ms.
Using GetChance, you get one random bit of information at the cost of anything between 0.020ms and 0.050ms. Interestingly, using what the demo suggests (chance 1./3 and weight 3) yields the 0.050ms result. What to do against that? Simple, increase the weight. But then whats the fucking point of this library? GetProc ensures the distribution of streaks is not as random as it could be (look at the first post of its thread on wc3c, theres some test data there). GetChance does....nothing? Seriously, if its going to be slower than GetProc, then you could use GetProc, but if you increase the weight, it essentially becomes a slower wrapper around GetRandomInt().
Interestingly, ChanceToProc beats the crap out of both of them with 0.016ms per bit of information. If only it had a better interface.

Also, using a negative probability or a probability greater than 1 makes this library crash the thread its running on. Oh, and rounding errors are going to kill your libraries purpose.

You also failed to properly respond to the infinite (computational) complexity point i brought up (which btw, accounts for most of your speed loss at very high probabilities and weights). Its like throwing all pieces of a puzzle into the air, hoping they will assemble in mid air and drop to the ground as the finished puzzle. Its simply bogus.

Seriously, drop this and use other peoples resources.

 

[kingkingyyk3]

Updated, changed algorithm to array stack.

Just a few conclusions: GetProc and GetChance beat the shit out of each other trying to place last in benchmarks. Using GetProc, you get one random bit of information at the cost of 0.045ms.
Using GetChance, you get one random bit of information at the cost of anything between 0.020ms and 0.050ms. Interestingly, using what the demo suggests (chance 1./3 and weight 3) yields the 0.050ms result.
Have you tried to benchmark the inlined code? Frankly speaking, speed isn't anything. Functionality takes over speed.

 

[Deaod]

New Tests. As the new algorithm included no collision detection, i added it myself (without touching the original code, when not testing for collisions). This also means that whenever you now get a collision, the Data set would have been corrupted (not enough "true"). For example: probability 0.8, data set size 100 yields an average of 6 collisions. That means, the algorithm would insert only 79 to 74 true values instead of the desired 80 (on average).

This can also be replicated using probability 0.8 and data set size 10. Less collisions occur when using 5, but there still are collisions.

If you use a chance of 1 and data set size of 10, the collision detection will cause a crash (that means the data is corrupted beyond repair) about 60% of the time. A data set size of 100 results in 100% crashs (as far as i could tell).

I still think this library is superfluous. We already have two other libraries to make random less random and redistribute chance so that long streaks occur less frequently.

EDIT:
1.0.3 still has collisions (mostly due to chainRemove not working as it should). I can upload a testmap once i get access to my own PC again.

 

[kingkingyyk3]

Ok, updated to v1.0.4. It is super fast(Faster than GetProc) and returns precise value now.

 

[Deaod]

Again, this library shouldnt exist, as there are already two other libraries doing what i assume this library tries to do, but in a better way.

Besides that, the algorithm this version uses is bullcrap. Think about what will happen if you use a probability thats either very high or very low.

 

[Jesus4Lyf]

Your .left member is only set in .reset().
Your .procCount is only used in .reset().
Your documentation doesn't explain weight.
"GetRandomInt/Real in warcraft 3" being "not precise" is not explained.

Fix it.

 

[kingkingyyk3]

Your documentation doesn't explain weight.
"GetRandomInt/Real in warcraft 3" being "not precise" is not explained.
Okay.

 

[Deaod]

Fix it.

Thats IT? Thats all you could find wrong with this library? Are you kidding me?

Alright, since noone else can do the math, heres how this works:

        method getChance takes nothing returns boolean
            if .countdown == 0 then
                call .reset()
            endif
            if .probably == 1. then
                return true
            elseif .probably == 0. then
                return false
            endif
            set .countdown = .countdown - 1
            if .left > .countdown then
                return true
            endif
            if .left > 0 and GetRandomInt(0,1) == 0 then
                set .left = .left - 1
                return true
            endif
            return false
        endmethod

countdown is the data set size (he calls it weight). Its decremented by one every time getChance is called. When it reaches 0 its set to "weight" again.
.left is the number of "true"s getChance has yet to return before .countdown reaches 0.
[ljass]if .left > 0 and GetRandomInt(0,1) == 0 then[/ljass]
This is where the algorithm fails so much. A 50% probability regardless of probability you passed to the Chance instance. That means when you have a 99% probability and a data set size of 100, you are most likely to have the one "false" as one of the first 6 generated values. 50%^7 is already less than the 1% probability youd have, had you simply used GetRandomReal.
Thats a bit of an extreme example, but how about a 25% chance. Again, let data set size be 100. The first 50 values are going to be 50% true and 50% false. But you only have 25 "true"s to distribute. So youre very unlikely to have any "true" in the last 50 values you generate.
Now, lets take a prime, like 29, 23, 19 or 13. If you want to have accurate results (to the extent possible for this library), youre going to have to use a data set size of 100. Same thing happens. Youre going to have most "true"s in the first half of all generated values and almost zero in the second half.
That, in my book, is worse than the default GetRandomReal. Take a chance of 19%, youre going to have a streak of more than 50(!!) "false", before you get another "true" again (while better implementations allow streaks of 10 or so at most, depending on weight).

It can work rather well for all probabilities p=1/n;n is element of {1,2,3,4,...}, but thats about it.
Edit: But its not like its the only library of its kind that can work well with such probabilities. GetProc and ChanceToProc do work well too, PLUS they can handle all probabilities correctly.
Edit, the 2nd: This library can also work well with probabilities p=n-1/n;n is element of {1,2,3,4,...}.

 

[Jesus4Lyf]

Thats IT? Thats all you could find wrong with this library? Are you kidding me?

Alright, since noone else can do the math, heres how this works:

Thank you for your helpful explanation. Actually, my issue was not with understanding the math, it was with wondering why you'd implement something like this in the first place.
The other two points were regarding the code being broken.

I need him to fix those things before I can review the resource at all. It allows me to see whether or not a resource is justified in the first place, and what the interface to it should be if it is. Then we can look at how he implements it... :thup:

(At the moment, this is an incoherent mess to me.)