NetHack's functions Rne, Rn2 and Rnz in Python 3¶
I liked this blog post by Eevee.
He wrote about interesting things regarding random distributions, and linked to this page which describes a weird distribution implemented as Rnz in the NetHack game.
Note: I never heard of any of those before today.
I wanted to implement and experiment with the Rnz distribution myself.
Its code (see here) uses two other distributions, Rne and Rn2.
%load_ext watermark
%watermark -v -m -p numpy,matplotlib
import random
import numpy as np
import matplotlib.pyplot as plt
Rn2 distribution¶
The Rn2 distribution is simply an integer uniform distribution, between $0$ and $x-1$.
def rn2(x):
return random.randint(0, x-1)
np.asarray([rn2(10) for _ in range(100)])
Testing for rn2(x) == 0 gives a $1/x$ probability :
from collections import Counter
Counter([rn2(10) == 0 for _ in range(100)])
Counter([rn2(10) == 0 for _ in range(1000)])
Counter([rn2(10) == 0 for _ in range(10000)])
Rne distribution¶
The Rne distribution is a truncated geometric distribution.
def rne(x, truncation=5):
truncation = max(truncation, 1)
tmp = 1
while tmp < truncation and rn2(x) == 0:
tmp += 1
return tmp
In the NetHack game, the player's experience is used as default value of the
truncationparameter...
np.asarray([rne(3) for _ in range(50)])
plt.hist(np.asarray([rne(3) for _ in range(10000)]), bins=5)
np.asarray([rne(4, truncation=10) for _ in range(50)])
plt.hist(np.asarray([rne(4, truncation=10) for _ in range(10000)]), bins=10)
Let's check what this page says about rne(4):
The rne(4) call returns an integer from 1 to 5, with the following probabilities:
Number Probability 1 3/4 2 3/16 3 3/64 4 3/256 5 1/256
ref_table = {1: 3/4, 2: 3/16, 3: 3/64, 4: 3/256, 5: 1/256}
ref_table
N = 100000
table = Counter([rne(4, truncation=5) for _ in range(N)])
for k in table:
table[k] /= N
table = dict(table)
table
rel_diff = lambda x, y: abs(x - y) / x
for k in ref_table:
x, y = ref_table[k], table[k]
r = rel_diff(x, y)
print(f"For k={k}: relative difference is {r:.3g} between {x:.3g} (expectation) and {y:.3g} (with N={N} samples).")
Seems true !
Rnz distribution¶
It's not too hard to write.
def rnz(i, truncation=10):
x = i
tmp = 1000
tmp += rn2(1000)
tmp *= rne(4, truncation=truncation)
flip = rn2(2)
if flip:
x *= tmp
x /= 1000
else:
x *= 1000
x /= tmp
return int(x)
Examples¶
np.asarray([rnz(3) for _ in range(100)])
np.asarray([rnz(3, truncation=10) for _ in range(100)])
For x=350¶
np.asarray([rnz(350) for _ in range(100)])
_ = plt.hist(np.asarray([rnz(350) for _ in range(100000)]), bins=200)
np.asarray([rnz(350, truncation=10) for _ in range(100)])
_ = plt.hist(np.asarray([rnz(350, truncation=10) for _ in range(10000)]), bins=200)
Conclusion¶
That's it, not so interesting but I wanted to write this.