roll_chance mechanism

[PeterJust]

Bad news again (sorry...). I analysed the roll_chance mechanism, to understand how and when a base likely gets discovered. And it's broken. Or actually it sort of works, but it surely doesn't do what it's supposed to do. TL;DR: somehow replace g.roll_chance in player.py with g.roll_percent. I tried to simply replace it, and it didn't work. I'm guessing there is another place where chances are modified, that's incompatible to the roll_percent function (because of the 10000 factor stuff or some addition). Or maybe you would need to divide the percent_per_day defined in data.dat by the seconds_per_day, to get the percent_per_tick value to pass to roll_percent.

So here is the deal: the roll_chance function calculates the current value of the cumulative probability distribution function (CDF) of the geometric distribution (yeah, I know... statistics sucks.. I'll explain further down). And that's bullshit, as this distribution is supposed to be the model of what happens. You're not supposed to roll against the values of this function. It's just a model of the likely population change over time. So "changing the population by rolling against the current probable population level" is a bit curious to say the least. Short explanation of this stuff:

• The discovery of a base is a probability experiment with only two possible outcomes (alive, dead). So it's a (discrete) bernoulli process.
• The likelyhood of discovery is constant. That is, the chance of a base being discovered per unit time (=seconds, I assume?) is a constant number per group. For example if News=100 then the chance of discovery every time a tick goes by is 0.01, e.g. 1%.
• This would be easy to implement: once per tick, roll against the chances of the base.
• To understand, when your base will LIKELY be discovered, you can create a model of this process. If you care to do the math, you will realise, that the remaining amount of bases with discovery chance p after a certain amount of time k is: CDF = 1 - (1 - p)^k
• check out roll_chance. It's exactly this, even though k is a value between 0 and 1, which doesn't make sense. So if you would map the value of chance over the day, you would get some kind of steadily rising function, reaching chance_per_day at the end of the day. Interesting but useless?
• What roll_chance proceeds to do with this value of how many bases will probably be left at time k is: it rolls against it. I'm guessing because the author didn't understand the meaning of the value.
• The consequence: it's VERY unlikely for a base to be discovered in the morning. Only at the end of the day, the base uses it's assigned chances. I noticed this behaviour before, but couldn't explain it/thought it was just a coincidence.

Upshot: roll_chance is not doing what it's supposed to do for the bases. Somehow replace the function with roll_percent(remembering to remove or add any potential factors of 10000 in there). And I will head on to use the geometric distribution to finally get some grips on the balancing. Should be easy now to calculate "half times", and run that against the base cost and build times.

Edit: I haven't considered time warp. This seems to influence the "amount of experiments per day". It might be a reason for the way it's done. But I still think it's solved wrong.

[Xenega]

If k is a number between 0 and 1, it's because the unit of time is a day and not a second. So, what it compute is the portion of day : seconds passed / seconds by day.

It's not a correct model but works well for small probability.

The explication why unlikely for a base to be discovered in the morning, is the tick function always stop at midnight. So you will have more discoveries at midnight.

[PeterJust]

Hmm, this is weird stuff. It seems, you can actually do this test on the CDF to check, if something has happend up till now (sorry for my first reaction). But the formula is still flawed as I understand it:

• k in this formula is "the number of the test". So if the process would usually test every second but you only test the CDF after one hour, you need to set k to 3600. Of course p has to be in the form of "probability per test"="probability per second" then. I recommend this piece of text.
• if you test (for instance) every hour on the CDF, you need to modify the formula. Because testing on the value of the CDF always tests if something has happened UP TILL NOW. If the result is negative, you shouldn't test the "tested timeframe" again. Upshot: you have to subtract the CDF value of the last test, from the CDF value of the current test, to get your chance for the current test (see second formula here)
• Another implication: say you are in time warp 4. It skips whole hours then (I guess?). So if you test positive, and a base gets discovered at this point: you don't know when in the 3600s the base was actually discovered. If it would have been in the first second of the hour, you wouldn't have earned cash with this base for almost an hour. So you can actually cheat a bit with time warp. With normal time, the base would have died much earlier. Suggestion: get a random second of the hour and correct production accordingly.

I hope this is somehow understandable.

[Xenega]

1/ In fact, having a number of test or a fraction of test is the same.

Let me demonstrate it.

We have 1% per day. With the current formula, we have: 1 second => 1 - (1 - 0.01) ^ (1 /(24*60*60)) = 1.16323325e-7

Now if we use the same formula than you : 24 hour => 1 - (1 - 1.16323325e-7) ^ (24*60*60) = 0.01

So using n or n/N is the same.

2/ As I said the formula is not completely correct. Give me the correct formula and I will try to implement it.

3/ Yes you right. It's a problem already know but I have difficult to solve because it's need big change in the tick function.

[PeterJust]

1) you're right. An interesting observation. 2) As stated above, the correct Formula should be: chance = CDF(k) - CDF(k-1). I suggest saving the secs_passed from the last tick, and passing it to roll_chance as well. In there, you have to calculate chance twice: once for the current secs_passed and once for the old secs_passed, after that you subtract old from current, and then roll against the result: random.random() < diff_chance 3) The glitch only occurs, in the tick where a base gets discovered. I would assume, you would just have to correct the resources of one tick. But I don't really understand "the tick function" (i.e. when on_tick is called), yet. And I guess it's not an important problem right now.

[Xenega]

2/ We already use secs_passed 3/ We must stop the tick to the moment the base discovered. It's a little complicated to implement.

[PeterJust]

At 2): so it works well enough, because the CDF is almost linear for these small chances, and therefore testing on the interval [0 t] is almost equal to testing [t1 t2]? Cunning...

But it seems I'm still missing something. I did a quick survey of 9 games and found a "mean half life" of 9.8 days for 10 "server access" and the university computer. An estimation of the supposed half life is about 28 days (1/(p * 1.2), where p=0.0297. I neglected the lower discovery chance of the university computer, but used the modifier for "previous discovery at this location"). Is there some large modifier I missed? The product of all modifiers would need to be about 2.8 to get a half life of 9.8 days.

[Xenega]

I think I discovered a problem that may explain some of your discoveries. The Expected Value of CDF do not change when you change the interval, but the variance do. The variance decrease when the number of experience increase (inversely proportional with the interval chosen).

Therefore, small interval => small variance big interval => high variance

Conclusion, in high speed you will have more exceptional experience. This is bad. Very bad.

We need a distribution that is independent of period chosen. The solution is easy: we need to use a poisson distribution. It's independent of the interval chosen since λ is constant.

So, we could just calculate for each interval: P(X>=1)=1-P(X=0)=1-e^(-λT)

And use it instead. But I have thought about a better method, confirmed in this article: https://preshing.com/20111007/how-to-generate-random-timings-for-a-poisson-process/

t(Death) = - ln X / λ

Therefore, we can just calculate one time the moment of death of the base (for example, after build) and check it each tick.

This would resolve 3/ and all problems we have with CDF.

[PeterJust]

Hmm, well spotted! There might just be one issue: what if the detection rate changes after the moment of death was calculated? I guess you would need to recalculate the time of death every time something happens. Is it actually possible to ignore the past when recalculating (following from the memorylessness of the distribution)? What's the distribution of the recalculated values?

[nthykier]

Poisson would be awesome if we had completely constant detection rates. Unfortunately, I am with @PeterJust on this; I am not sure we can use them given our detection rates are not constant and it is not clear how we would change the time of death when the detection rates change.

[osjc]

it is not clear how we would change the time of death when the detection rates change.

If the base is detected before the detection rates change, then the base is dead and you don't need to change anything.

If the base's projected death is after the detection rates change, then you need to calculate new time of death for the base using the new detection rates and start measuring that time of death from the point of time when the detection rates changed. In other words check whether the new "time to live" is less than the current time minus the time of the detection change and if yes, bang, base is no more.

To see why this is the correct answer consider the situation when the base with the old detection rate is destroyed by the player at the time when the detection rates changed and a completely new base with the new detection rates is created at exactly the time of the detection rate change. The statistics of "did humans find a base?" will behave exactly the same as in the situation when there is only 1 base with the detection rate changed at that time point but in the case with two independent bases you don't have any confusing "detection rate changed, how do I update the time of death" problems.

[nthykier]

Jozef Behran:

it is not clear how we would change the time of death when the detection rates change.

If the base is detected before the detection rates change, then the base is dead and you don't need to change anything.

If the base's projected death is after the detection rates change, then you need to calculate new time of death for the base using the new detection rates and start measuring that time of death from the point of time when the detection rates changed. In other words check whether the new time of death is less than the current time and if yes, bang, base is no more.

To see why this is the correct answer consider the situation when the base with the old detection rate is destroyed by the player at the time when the detection rates changed and a completely new base with the new detection rates is created at exactly the time of the detection rate change. This will behave exactly the same as the situation when there is only 1 base with the detection rate changed but this time you don't have any confusing "detection rate changed, how do I update the time of death" problems here.

The problem is the bit about "you need to calculate new time of death". The Poisson trick only works if the rate is constant. The moment the detection rate can change (as it does here), the Poisson trick is no longer applicable.

In theory, I suppose we could roll once per base and recompute the death time by recomputing the Poisson curve with the new rate. While this would work technically (not sure about the accuracy) consider the case where humans finds one base immediately triggers all of your bases to be discovered. This is mechanic is "not-fun" as it will just feel like "the game decided you should lose now for no apparent reason". For me, that would be a deal breaker in a game.

I am interested in a way where we can compute the time of death efficiently without ending up "steam rolling" the player. This could be the above mechanic (assuming it is "accurate enough") with a fail-safe where we do not instant kill multiple bases but instead give them a final (random) grace time.

(Side note/clarification: I am fine with humans finding multiple bases at approximated the same time, so you need more than one backup base. This can be explained by a "raid" like police against organized crime etc. plus we can add a story event that warns the player about this being a possibility. I am against base discovery causing an immediate avalanche effect that kills all of your bases in one feel swoop).

[PeterJust]

Hmm, if you fast forward, it's not uncommon nor unlogical, that two bases get discovered with the same tick. I don't think you would get an avalanche effect, as the detection probabilities are very low. Any time you reroll the time of death, you DON'T roll on "does this base die now". That would kill a base quickly. Instead you roll on the CDF. The more often you roll, the more likely the time of death lies around the expected value (right??). Which is the "half-life" Lambda, in case of Poisson.

But what i'm not too sure about is this: Imagine an old base close to its time of death. Then the discovery rate changes. So the base gets rerolled and probably gets another half-life. Amiright? So the question remains: what is the distribution of the rerolled values?

@nthykier: i'm not sure how you imagine the process. Would you remember the age of the base, and compare it with the newly calculated time of death? Because that would truly create an avalanche.

Here is an idea: don't remember the age of the base at a recalculation event, but the fraction of lifetime left. When the detection rate changes, recalculate the lifetime using the CDF/Poisson Distribution. The new time of death is the previously remaining fraction of the new lifetime. Exempli gratia: At a detection rate change, a base has 1/3 of it's lifetime left (say 3 days of a nine day life). With the new detection rate, its life should now only be 6 days long. Therefore, its remaining lifetime is: 2 days (1/3 of 6). Not too sure about the distribution of this beast, though... :D

[nthykier]

Having googled around, I think singularity is using a Poisson binomial distribution. Just to save an hour or two googling around until I find again next time I need to look at this issue.