Posted by Dusty

Proof?

Don't know about Graal's PRNG, but plenty of PRNGs are predictable. That's why there is a P (for pseudo, not predictable). Even with truly random selection, there is a potential for certain people to be selected more often over a limited period of time. Since you brought up that there's a repeating loop, I'm not entirely confident that the queue is truly random.  

It wouldn't be random. Folks closer to the start of the list searched by the 'loop' would have a slightly greater chance at getting in. Slightly.

I have gotten into and won 2 events in the same day before. Non-queue ones only, though. The queue is a harsh mistress... and often the hats she provides are already ones that I have.

Speaking of which, I have gotten into events run by queue while already having the hat that is on offer.

And btw, thanks for cliff climber, Dusty. Realized how well it is designed and randomized the other day, unlike bush race (for example).  

Posted by 4-Lom

It wouldn't be random. Folks closer to the start of the list searched by the 'loop' would have a slightly greater chance at getting in. Slightly.

Nah, it plucks a random player from all entrants. It doesn't start at the beginning of any list.

PHP Code:

  while (temp.getqueue.size() < temp.plyrcount) {
    temp.p = randomstring(this.("event_" @ eventid));
    temp.plyr = findplayer(temp.p);
    // other stuff
  } 


Posted by 4-Lom

I have gotten into and won 2 events in the same day before. Non-queue ones only, though. The queue is a harsh mistress... and often the hats she provides are already ones that I have.

You are lucky, and maybe a good example of why perhaps time from last event should be considered.

Posted by 4-Lom

Speaking of which, I have gotten into events run by queue while already having the hat that is on offer.

It relies on the person hosting to actually specify the prize in the system. They may not be doing that.

Posted by 4-Lom

And btw, thanks for cliff climber, Dusty. Realized how well it is designed and randomized the other day, unlike bush race (for example).

I'm glad you enjoyed it, it was quite fun to make It's not really randomized, save for the falling of the rocks and such. Would be really cool to have actual random layouts and such but sadly that would be very difficult to pull off.  

Posted by Dusty

Nah, it plucks a random player from all entrants. It doesn't start at the beginning of any list.

PHP Code:

  while (temp.getqueue.size() < temp.plyrcount) {
    temp.p = randomstring(this.("event_" @ eventid));
    temp.plyr = findplayer(temp.p);
    // other stuff
  } 


You are lucky, and maybe a good example of why perhaps time from last event should be considered.


It relies on the person hosting to actually specify the prize in the system. They may not be doing that.


I'm glad you enjoyed it, it was quite fun to make It's not really randomized, save for the falling of the rocks and such. Would be really cool to have actual random layouts and such but sadly that would be very difficult to pull off.

cliff climber is probably 1 of 3-4 events that actually require skill  

Posted by Dusty

I'm glad you enjoyed it, it was quite fun to make It's not really randomized, save for the falling of the rocks and such. Would be really cool to have actual random layouts and such but sadly that would be very difficult to pull off.

Yes, the layout is not random, but the falling of the rocks is. It leads to difficulty winning even if you have won before or know the route.  

Posted by Dusty

Why shouldn't they get into the events? Are they not allowed to enjoy them? This is the problem I have... it's always the same people bitching that they never get into events anymore because they always did before. What makes you more privileged to experience an event over the other players? Because you have more hours?


I was interested in allowing staff to host events with other prerequisites like that but I don't think I'd have the time to do it.


Players who already own the prize are already omitted.


Players in forts and spars and the such are skipped over.


I feel like it'd be more fair to have events hosted towards specific groups of players, rather than just ignoring a huge chunk of the playerbase. But see my first response. 500 hours is a lot of time to invest in a game, and it's not fair that you'd have to basically just AFK like everyone else to get a chance in events.

Anyways, players on tutorial island and some number of hours are skipped over anyways.


Possible, but I highly doubt this will have a noticeable outcome. The chances of getting into an event and then in another in the same week is pretty slim.

I didn't get into events much before at all. Chances are I would be inactive or offline, in the rare event they hosted at all. The only events I really like (or ever have a chance to participate in are hide and seek and trivia. IMO those events should be hosted WAY more often)

warpers were honestly so much better, aside from
the lag.  

Posted by Shadowfox

(or ever have a chance to participate in are hide and seek and trivia. IMO those events should be hosted WAY more often)

I also wish trivia was hosted more often. Unfortunately the people hosting would rather dump some chests on the ground or watch people fail at dodge then sort through thousands of pms...  

Once they get the right answer then can just clear pms lol  

Posted by Shadowfox

Once they get the right answer then can just clear pms lol

The people I've talked to have said it's a lot more than just that.  

Posted by Dusty

Nah, it plucks a random player from all entrants. It doesn't start at the beginning of any list.

PHP Code:

while (temp.getqueue.size() < temp.plyrcount) {
    temp.p = randomstring(this.("event_" @ eventid));
    temp.plyr = findplayer(temp.p);
    // other stuff
  } 


Question: Why does it dynamically look up this.("event_" @ eventid) every iteration? I'm assuming that it evaluates to an array of account name strings, and the randomstring function selects one of them. The potential for repeats is also an issue. A single pass method where everyone gets equal probability: http://en.wikipedia.org/wiki/Reservoir_sampling.

My GScript skills are a bit rusty, but here's an attempt instead of doing it in some other language (may not be correct):

PHP Code:


// Reservoir Sampling
// ==============
// **pool**: An array from which to draw samples
// **count**: The desired sample size
// returns a sample array with **count** random elements from **pool**
function sample(pool, count) {
    temp.sample = {};
    for (temp.prospect : pool) {
        if (temp.sample.size() < count) {
            temp.sample.add(temp.prospect);
        } else {
            temp.n = random(0, pool.size() - 1);
            if (temp.n < count) {
                temp.sample[temp.n] = temp.prospect;
            }
        }
    }
    return temp.sample;
} 


A weighted version of this algorithm is described by this journal article: http://www.sciencedirect.com/science...2001900500298X. Oddly, Graal is older than the algorithms described by the paper.


My Javascript interpretation of that:

PHP Code:



// Weighted Reservoir Sampling
// ==============
// **population**: A population from which to select a sample
// **weights**: A parallel array to population, to specify weight
// **size**: The desired sample size
// returns a sample array with **size** random elements from **population** influenced by **weights**
function sample(population, weights, size) {
    var reservoir, keys, key, threshold, i, j;
    
    reservoir = [];
    keys = [];
    
    for (i = 0; i < size; i++) {
        reservoir[i] = population[i];
        keys[i] = Math.pow(Math.random(), 1 / weights[i]);
    }
    
    threshold = Math.min.apply(null, keys);
    for (i = size; i < population.length; i++) {
        key = Math.pow(Math.random(), 1 / weights[i]);
        if (key > threshold) {
            j = keys.indexOf(threshold);
            reservoir[j] = population[i];
            keys[j] = key;
            threshold = Math.min.apply(null, keys);
        }
    }
    
    return reservoir;
} 


The weighted one should return a purely random sample if you give every item in the population the same weight. Also, weights can't be 0.

Another javascript version I just wrote of the weighted reservoir sampler that wouldn't require keeping track of all of the players that have entered the queue (which was the point of reservoir samplers, but then even with a known pool they were more efficient than alternatives):

Edit: Added documentation to where things line up with the algorithm description in the journal article. You can see I didn't do things in the same order as described, but you should be able to see where I saved some code and added small efficiencies by reordering it.

PHP Code:


// See http://www.sciencedirect.com/science/article/pii/S002001900500298X#
function WeightedReservoirSampler(length) {
    this.length = length;
    this.sample = [];
    this.keys = [];
    this.threshold = Infinity;
}

// R is the reservoir, or [this.sample], or what's going to be the end result.
// m is the size of the reservoir, or [this.length].
// V is the input stream of items, which is of indeterminate length.
// n is the end size of the input stream, or the number of items passed in before the sample is complete.
// v_i is an incoming [item].
// w_i is an associated [weight] for the incoming item.
// u_i is a random number in the range of 0-1, or [Math.random()] generated in association with v_i.
// k_i is a [key] calculated for each item based on its weight, w_i, and the random number, u_i.
// T is a threshold, or [this.threshold], that represents the smallest key value.
WeightedReservoirSampler.prototype.push = function (item, weight) {
    var key, index;
    if (weight <= 0) return;
    
    // 2. For each item in v_i in R: Calculate a key, k_i = u_i^(1/w_i), where u_i = random(0, 1)
    // 5. For each item v_i: Calculate a key, k_i = u_i^(1/w_i), where u_i = random(0, 1)
    key = Math.pow(Math.random(), 1 / weight);
    
    // 1. The first m items of V are inserted into R
    if (this.sample.length < this.length) {
        this.sample.push(item);
        this.keys.push(key);
        
        // 4. The smallest key in R is the current threshold T
        this.threshold = Math.min(this.threshold, key);
        
    // 3. Repeat steps 4-7 for i = m+1, m+2, ..., n
    // 6. If the key k_i is larger than T, then:
    } else if (key > this.threshold) {
    
        // 7. The item with the minimum key in R is replaced by item v_i
        index = this.keys.indexOf(this.threshold);
        this.sample[index] = item;
        this.keys[index] = key;
        
        // 4. The smallest key in R is the current threshold T
        this.threshold = Math.min.apply(null, this.keys);
    }
}

WeightedReservoirSampler.prototype.flush = function () {
    var result = this.sample;
    this.sample = [];
    this.keys = [];
    this.threshold = Infinity;
    return result;
} 


 

Dusty! Duusty!! DUUuUUUUUUSSSTYyyyYYY!!!! WE HAVE THE TECHNOLOGY!!!! You don't even have to keep track of who opted into the queue if you use this!

So at least with the last piece of code, I've run two tests:

1. A sample of 100 numbers from a set containing the numbers 0-9999 with equal weights (should be about uniformally distributed)

PHP Code:

// should be uniformly distributed between 0-9999
sampler = new WeightedReservoirSampler(100);
for (i = 0; i < 10000; i++) sampler.push(i, 1);
sampler.flush(); 


This is an Excel chart from one of those runs to show the distribution in result array order:


This is an Excel chart from the same run to show the same distribution in sorted order:


2. A sample of 100 numbers from a set containing the numbers 0-9999 where odds have a weight of two and evens have a weight of one (should have around twice as many odds as there are evens).

PHP Code:

//should be approximately 2:1 ratio of odds to evens.
sampler = new WeightedReservoirSampler(100);
for (i = 0; i < 10000; i++) sampler.push(i, 1 + i % 2);
sample = sampler.flush();
sample.filter(function (x) { return x % 2 }).length + ':' + sample.filter(function (i) { return i % 2 - 1 }).length 


Ten sequential results: 65:35, 66:34, 73:27, 67:33, 63:37, 66:34, 70:30, 70:30, 70:30, 63:37  

I still haven't heard any feedback on this particular algorithm.  

uhm why can't we just host trivia?

gives everyone a fair chance  

Not a single soul can go against the work that deadowl puts in for this game, god damn!  

Posted by Fulgore

Not a single soul can go against the work that deadowl puts in for this game, god damn!

I didn't put this into the game, I gave a script prototype written in Javascript, an entirely different language than GScript. I just want to know what the devs opinions are.