Alice’s Random Rewards

Perhaps you have heard a story like this one before:

In a far away land lives a strange, kindhearted, and almost entirely harmless creature named Alice.

Every day, Alice slowly and awkwardly clambers and skitters her way to an old tree stump at the edge of the woods to leave an offering of shiny baubles for The Crows.

Every day, The Crows collect Alice’s offering and leave her a Reward.

Alice has heard that there is a chance- however small- that barter with The Crows might result in a Reward which could change her life forever: a Tome of Knowledge.

So far Alice’s Rewards have mostly been twigs, leaves, or the occasional scrap of paper. She longs for the Tome of Knowledge, or even a tasty apple from the highest branches of the gnarled deep-woods apple trees.

Unfortunately for poor Alice, she lives in a computer game. Perhaps the foundations of her world look something like this:

const rewards=[
	{name:'twig',  type:'common'},
	{name:'leaf',  type:'common'},
	{name:'paper', type:'common'},
	{name:'apple', type:'food'  },
	{name:'tome',  type:'unique'},
]
function stump_reward(){ return rewards[Math.random()*rewards.length] }

In principle, every stump_reward() has the same random chance of appearing. If she knew about the contents of the rewards table, Alice could expect to obtain her Tome of Knowledge within 5 Rewards or so- maybe a few more tries, maybe a few less, and maybe she’d even get it on her first try!

On the other appendage, there’s no guarantee that this algorithm will ever yield a tome: she could leave The Crows payment a dozen times or even a hundred times and there would still be a chance- however small- of never being rewarded with a Tome of Knowledge.

Dear reader: poor Alice is not a lucky creature.


This world simply won’t do.

Consider a different approach: Instead of picking each Reward independently, we randomly shuffle a list of indices of Rewards. Each time a Reward is selected, we advance along this list of shuffled outcomes, and when the list is exhausted we generate a new shuffled sequence:

let p=[]
function stump_reward(){ if(!p.length)p=shuffle(range(rewards.length)) return rewards[p.shift()] }

With our revised approach, the best-case scenario for Alice is the same: she might get The Tome of Knowledge on her first try.

The worse-case scenario- which tends to be Alice’s lot in life- is much kinder: no matter how the list is shuffled, it cannot take Alice more than five attempts to win the Tome.

The cost of this kindness is additional state: we must remember the permutation vector p between transactions with The Crows. In practice, this information will usually contribute only a tiny fraction of the maintenance of Alice’s clockwork universe. If the Random Number Generator which drives shuffle() is “seedable”, you could shrink the storage requirements of this approach by remembering only a snapshot of the seed before each shuffle and an index into the current shuffle, regenerating the permutation vector as needed.


If you want a deliberately skewed range of outcomes, you could augment this approach by repeating the indices of more common items before the shuffle:

const rewards=[
	{name:'twig',  type:'common', weight:3},
	{name:'leaf',  type:'common', weight:3},
	{name:'paper', type:'common', weight:2},
	{name:'apple', type:'food',   weight:2},
	{name:'tome',  type:'unique', weight:1},
]
function range(x){ return x.flatMap((item,idx)=>Array(item.weight).fill(idx)) }
range(rewards) // [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

The basic version of this approach prevents repeated Rewards unless they appear as the last element of one shuffle and the first element of the next shuffle. The “weighted” version of this approach allows more repetitions, but they will always be bounded: Alice will never be rewarded with an infinite stream of twigs.


The coveted Tome of Knowledge is a unique item: it should only ever be dispensed once. If a Tome-carrying Alice extends her gratitude to The Crows, she can still look forward to the possibility of the occasional apple. Of course, there might be other conditions which influence which Rewards are possible at various times, like whether apples are in season!

Since we know our shuffle-based approach will select every possible reward fairly, it is safe to generate a series of Rewards in sequence and return the first result which is valid (assuming there is always at least one valid Reward):

function valid_stump_reward(){
	while(1){
		const r=stump_reward()
		if(is_valid(r))return r
	}
}

With the simpler random-selection approach, valid_stump_reward() could take an arbitrarily long time to complete- especially for a creature as unlucky as Alice.

I have seen some practitioners of virtual world construction account for that problem by bailing out after a limited number of failed draws:

function valid_stump_reward(){
	for(let z=0;z<10;z++){
		const r=stump_reward()
		if(is_valid(r))return r
	}
	return {name:'nothing',type:'disappointment'}
}

Alas, a brittle hack.


Perhaps the ideas in this little story are already obvious to you, dear reader, and perhaps the worlds you have crafted are already kind. But perhaps there is a chance- however small- that the seed of a new idea has been planted which can spare as-of-yet undreamed Alices from countless days of unlucky toil.

It’s worth a try, no?

back