更好的随机算法?

5
我正在使用C++制作游戏,其中涉及用随机布尔值(是或否)填充图块,该值是通过 rand() % 1 来决定的。但它感觉不太随机。
我在启动时使用了srandctime,但似乎出现了相同的模式。
是否有任何算法可以创建非常随机的数?或者有任何建议可以改进rand()

只是出于好奇,您的数组有多“大”?如果它很小,您可能看不到太多的随机性。 - GrayWizardx
你能展示一下代码吗?可能是因为你设置种子的方式有问题,所以出现了连续的模式。 - Jim Wallace
16
"rand() % 2"会产生更好的结果。 - Drew Dormann
12
当1的值足够小时,rand() % 1通常为零。 - Michael Foukarakis
人类在检测随机性方面的表现往往不佳。如果这很重要,那就不要猜测:一旦你修复了%1 / %2的错误,就要捕获大量结果(1000个以上,而不是10个),将它们放入Excel中,并让它计算平均值。 - AAT
14个回答

23

真正的随机性通常看起来并不那么随机。但至少你可以立即采取一些措施,避免仅使用最低位比特。引用C语言数值计算方法:

如果您想生成1到10之间的随机整数,应始终使用高位比特,例如
j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
而且从不使用任何类似的东西进行
j = 1 + (rand() % 10);
(使用较低位)。

此外,您可能考虑使用具有更好性能的不同 RNG。 Xorshift 算法是很好的选择。它速度快、代码简洁,只需几行 C 代码就足够了,并且在统计方面应该对于任何游戏都足够好。


12
避免低位比特非常依赖于生成器。一些伪随机数生成器却会生成弱的高位比特。 - Joey

8
低位不够随机。 使用 %2 只检查随机数的最后一位。
假定您不需要密码强度的随机性。 那么以下应该没问题。
bool  tile = rand() > (RAND_MAX / 2);

实际上,他们甚至没有使用底位(bottom bit),而是使用了 %1。 :) - Drew Dormann
4
你的解决方案和原始版本存在相同的问题:只使用了rand()返回值的一位。原始版本只使用最低位,你的解决方案只使用最高位。更好的解决方案应该使用所有位。 - sbk
@sbk:如果我认真考虑,是的,你是正确的。我只是简化了“rand()/(RAND_MAX + 1.0) * RANGE”,其中范围为2。 - Martin York

4
除了编写另一个伪随机数生成器或使用库之外,您可以做的最简单的事情就是使用单个调用rand()给您的所有位。大多数随机数生成器可以分解为具有某些随机性和统计特性的位流。该流上均匀间隔的各个位不必具有相同的特性。在这里,您实际上正在丢弃14到31位伪随机性。

您可以仅缓存由调用rand()生成的数字,并使用其每个位(当然,这将取决于RAND_MAX),因此如果您的RAND_MAX是32768,则可以使用该数字的最低阶15位按顺序。特别是如果RAND_MAX很小,则您不会处理生成器的低阶位,因此从高位获取位不会获得太多好处。例如,Microsoft CRT使用以下方程式生成随机数:

xn + 1 = xn · 214013 + 2531011

然后移除该结果的最低16位并将其限制为15位。因此,在那里没有来自生成器的低位。尽管对于RAND_MAX高达231的生成器,这在很大程度上仍然成立,但有时您不能指望它(因此,在那里可能只限制自己使用来自高位的16或24位)。

因此,通常情况下,只需缓存对rand()的调用结果,并按顺序使用该数字的位于您的应用程序中,而不是使用rand()%2


3

C++11实现Mersenne旋转算法的方式如下。来自cppreference.com

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 6);

    for (int n=0; n<10; ++n)
        std::cout << dis(gen) << ' ';
    std::cout << '\n';
}

这个产生的随机数适用于模拟,没有其他随机数生成器的缺点。但它不适用于密码学;而密码学随机数生成器需要更多的计算资源。
还有Well equidistributed long-period linear算法;有许多实现示例。

3
许多伪随机数生成器在周期性较低的位上存在问题,特别是线性同余算法,这通常是最常见的实现方式。有些人建议通过移位最不重要的位来解决这个问题。


2

我多年来一直成功地使用 Mersenne Twister 随机数生成器。它的源代码可以从广岛大学数学系这里获取。(直接链接,省去了阅读日文的麻烦!)

这个算法的优点在于:

  1. 其“随机性”非常好
  2. 其状态向量是一组无符号整数和一个索引,因此非常容易保存其状态、重新加载其状态,并从留下的伪随机过程处恢复。

对于你的游戏,我建议你看看它。


给我展示一个没有第二个引用优势的伪随机数生成器(PRNG)。事实上,这几乎是PRNG的一个标准特性。 - Joey

1

随机的“是”或“否”的完美方式是切换它们。您可能不需要随机函数。


这并不是,而且原帖作者说他需要随机值。 - David R Tribble
+1,@LorenVS- 在一个完全确定的宇宙中,任何其他事物可能是多么随机。 - Tom Neyland
好的,我可以删除这个,但是我想到了,“OP感觉不太随机。”我认为他得到了类似于“是 是 是 是 否”的东西,他/她可能认为它不太随机。 - YOU
2
几乎像 int random() { return 4; } // 完全随机选择的数字 - Cecil Has a Name
通过公正的D6掷骰子,我从我的D%骰子集合中获得更多的随机性,它们有一个奇怪的技巧,可以掷出相当一致的88%。 - greyfade

1

标准随机数生成器的最低位不太随机,这是一个众所周知的问题。

我建议研究一下boost随机数库


0

让你的数字看起来更随机的一种简便方法是每次条件if(rand() % 50==0)为真时重新生成。


2
那个条件确切地告诉你需要重新播种的情况是什么? - Joey
根据生成的数字范围和数字生成器,它将在每生成50个(或其他数量)数字后自动重新设定生成器种子。 - Tom Neyland
请注意,“感觉更随机”并不等同于更好的统计随机属性。伪随机数生成器是非常棘手的东西,特别是当被不当地使用或缺乏非常精确的知识时(即使有了这些知识,它们也可能会爆炸性反弹)。 - Joey

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接