Server item drop roll algorithm improvement

Started by ai_enabled, July 28, 2020, 10:42:07 AM

ai_enabled

I've researched and made something interesting regarding the random roll algorithm for rare items (seeds, gold, gems).

First, vanilla version (A27 prior to patch) for an item with 1/1000th drop chance:


As you can see, the problem with it is that it's quite...random. While on average you can obtain an item with 1/1000th drop change with 1000 attempts, it may require any number of attempts from 1 to over 10000. Which is in no way fun especially when you're playing solo or on a local server and cannot trade with other players.
You may find it mildly interesting: with this (old) roll algorithm number of lucky players (those that obtained a gem (1/1000th probability) with less than 50 attempts) was 5%. Same as the number of really unlucky (that obtained a gem only after 3000+ attempts) ΓÇö yes, also 5%. It's really not good! But that's what most games are using...

A new feedback-augmented roll algorithm:

How does it work? Basically, it increases your chance a bit with every failed attempt (for an item with 1/1000th probability the roll formula is 1/(2000-#attemptNumber)).
And the end result is a completely flat distribution chart. The chance to obtain an item that has 1/1000th drop rate is still 1/1000th in average but it will require no more than 1999 attempts in any circumstances, and it's randomΓÇöbut with flat distribution instead of a bell curve! The number of attempts is evenly distributed while the average and a median number of attempts necessary are precisely around 1000 attempts (on a large sampling number) for an item with 1/1000th drop probability.

What does it mean? The new algorithm will ensure that you can obtain even the rarest items in a reasonable time, while on average it will require as many attempts as we intended. It will be much more consistent, with less lucky streaks but also without infinite bad luck that followed every player from time to time!

In the server patch (that is already deployed on all the PvE servers) it applies to various rare items: seeds from grass (1/50th chance), gold nuggets (1/100th chance), and gemstones (1/1000th). The challenge was to elegantly integrate this in the game, and ensure that the number of attempts made is properly stored in the world savegame and restored on the world load after the server restartΓÇöbut we've made it. Enjoy the game!

Regards!

P. S. If you want to play with this simulation model yourself here is the link on the source code of the sample app https://github.com/aienabled/RandomDistributionTest (requires Visual Studio 2019 with desktop development setup for WPF apps).
There is also a sample written in JavaScript https://gist.github.com/Jimbly/9364e1bd50877357c74d8ff5d3631ac1 from the community member @Jimbly that wanted to verify the formula. It doesn't draw a chart but it demonstrates the flat distribution if you run it with a JS editor.

UPD. I've made two JSFiddle samples based on the code from @Jimbly but advanced further to demonstrate the regular random approach (https://jsfiddle.net/ai_enabled/1L5gd02v/) and the described above my feedback-augmented roll aglorithm (https://jsfiddle.net/ai_enabled/z7obhmyq/). There are no graphs but if you open the console you can read the output.

Mars

#1
So when you start mining or after getting a gem, your chance to get one is 1/2000 ?

Is the chance 1/1000 per stone node (as exemple), or is it per loot like +5 stones, or per stone? I mean if you loot 5 stones at once, did you get 5 chances or 1?


MGS

Quote from: Mars on July 28, 2020, 08:05:27 PM
So when you start mining or after getting a gem, your chance to get one is 1/2000 ?

Is the chance 1/1000 per stone node (as exemple), or is it per loot like +5 stones, or per stone? I mean if you loot 5 stones at once, did you get 5 chances or 1?

I would like to know the answer to this also

ai_enabled

The chance is applied once per mineral object/node. When you've finishing mining it, the server rolls your chance to obtain a gold nugget and rolls your chance to obtain a gemstone.
So if you go and mine 5 stone nodes you will take 5 chances to obtain a nugget and 5 chances to obtain a gemstone.

QuoteSo when you start mining or after getting a gem, your chance to get one is 1/2000?
Correct. But that's a good question that requires some understanding of statistics and probability theory.
With the new algorithm, the more failed attempts you've made, the larger your chance is for the next attempt. The average number of attempts you will need to do to obtain an item with 1/1000 probability is 1000. But it's still random, and it could be any number of attempts in the range from 1 to 1999. The beauty here is that unlike the previous roll function that featured a bell curve (that often results in both lucky streaks and also infinite bad luck), the new function has a completely flat distribution. You have an equal chance to obtain an item with 1/1000th probability in every number of attempts from 1 to 1999.
So, while it may sound very odd that you start with basically 1/2000 probability, it's rising up quickly with every failed attempt and it ensures that you have an equal chance to obtain an item in a reasonable timeΓÇöunlike the bell curve that resulted in 5% of server population being able to obtain a gem only after 3000 (!) attempts (and in some rare cases much more) while other 5% of server population was able to obtain a gem in less than 50 attempts.
Now every number of attempts is equal, it will never go above 1999 attempts, while it still has the same average number of attempts (1000).

I hope it makes sense. Alas, English is not my native language and it's very hard for me to provide a concise response but I did my best to provide the data so you can look up the charts and see the distribution bucket of the number of attempts to make your own conclusions.

Regards!

MGS

Have i understood this correctly:

Each hit on a node (sand,clay,copper, iron, etc)
Counts towards the increased probability of gaining a gem?

Or is it each completed node ?


ai_enabled

@MGS, no. The gem is rolled randomly when you or your drone finishing mining a node. The chance is 1/1000th. No change with this. The only change is how the roll algorithm works to make it more predictable and ensure that no players will have bad luck forever.

Caninicus

I like this.

Is there any way that something similar could be implemented for seeds? I haven't managed to find all the seed types, since I will only accept seeds that I find 'naturally.' I.e., I won't buy them or accept them from other players.


ai_enabled

@Caninicus, that's a good suggestion to consider. Technically, it's already done to some degreeΓÇöyou will always find a seed from green grass in a reasonable time (the algorithm described above applies there so you get a random seed once in a while). However, it doesn't ensure that you will find a particular seed, only a random one from the set. So getting all the seeds available through grass gathering might take considerable time (though, not much, I believe).
However, some seeds could be obtained only in radtowns/ruins (from brown "Supply crates"). We will analyze how it works and consider changes there for future updates.

Regards!

betocorp

Quote from: ai_enabled on August 28, 2020, 03:13:32 AM
We will analyze how it works and consider changes there for future updates.

I did this some time ago regarding loot table ans as can see it isnt just an algorithm issue but a balance issue, it is my post:

betocorp08/11/2020
I have looked into code about drops in ruins and filtered about good drops. Simplified a little on cumulative probability but the error is  small. You can go to anywhere, the loot is only linked to crate and tier gate.
mili > 1 piece T4 armor 0.12% / 1 piece T3 armor 0.31% / extra loot in skill is just 10mm trash
food > rice 8% /  wheat 8%
med > stim 3.2% / medk 3.2% / extra loot in skill is trash
ht > drones ~5%, but all loot is already good / extra loot gives more components
ind > ~30% chance to get components /  extra loot gives more components
supply > any specific seed has a chance of 1.5 rolls of 1.3% /  extra loot gives more components
So statistically you must open 240 supply crates to get tobacco with 99% chance to get it

ai_enabled

@betocorp, we've found some irregularities in how the nested droplists operate and applied the necessary changes.
We've also reviewed the seed drop rates from the crates.
Thanks for reporting!

ai_enabled

Q: Is this roll algorithm per player or server-wide for all players?
A: It is per player. Actually, it is per resource type per player. This way the system will ensure that, for example, gemstones are dropping for each player with 1/1000 chance on average when mining any mineral (of any type), and each player will not need to mine more than 2000 minerals in the worst case to obtain a gem.

Q: Does it work with drones?
A: Yes! Just keep in mind that you need to have Prospecting skill at least at level 15 in order to be able to find any gemstones. Upon reaching level 15, the system will ensure that you can obtain a gemstone in a reasonable time as described above. Operating several Tier 4 drones is the best way to mine minerals in a large number quickly.