需要可预测的随机生成器

我是一个networking游戏开发者,我遇到了一个随机数的问题。 假设一名玩家有20%的几率用他的剑命中。 这意味着,五分之一的命中应该是至关重要的。 问题是我得到了非常糟糕的现实生活中的结果 – 有时玩家会在5次命中中得到3次暴击,有时候15次都没有。 战斗时间相当短(3-10次),所以获得良好的随机分配很重要。

目前我使用PHP mt_rand() ,但是我们只是把我们的代码移到C ++中,所以我想在我们游戏的新引擎中解决这个问题。

我不知道解决scheme是一些统一的随机生成器,或者也许记住以前的随机状态来强制适当的分配。

我同意早些时候的回答:在某些游戏的小游戏中,真正的随机性是不可取的 – 对于某些用例来说这似乎太不公平了。

我写了一个简单的Shuffle Bag就像在Ruby中的实现,并做了一些testing。 执行过程如下:

  • 如果它仍然看起来公平,或者我们还没有达到最低限额,那么它会以正常概率返回一个公平的命中。
  • 如果从过去的观察到的可能性看起来不公平,那么它将返回一个“公平的”命中。

基于边界概率被认为是不公平的。 例如,对于20%的概率,可以将10%设定为下限,将40%设定为上限。

使用这些边界,我发现在10次命中的情况下, 14.2%的真实伪随机实现产生的结果超出了这些界限 。 大约有11%的时间,10次重要的命中得分。 3.3%的时间,5个或更多的关键命中落在了10分之外。当然,使用这种algorithm(最小卷数为5),“Fairish”运行的数量(0.03%)超出界限。 即使下面的实现是不合适的(当然也可以做更聪明的事情),值得注意的是,通常你的用户会觉得这对一个真正的伪随机解决scheme是不公平的。

这是我用Ruby写的FairishBag的肉。 整个实施和快速蒙特卡洛模拟可在这里(要点) 。

 def fire! hit = if @rolls >= @min_rolls && observed_probability > @unfair_high false elsif @rolls >= @min_rolls && observed_probability < @unfair_low true else rand <= @probability end @hits += 1 if hit @rolls += 1 return hit end def observed_probability @hits.to_f / @rolls end 

更新:使用这种方法确实增加了获得致命一击的总体概率,使用上面的界限增加到22%左右。 您可以通过将其“真实”概率设置得稍低来抵消这一点。 如果修正得当,概率为17.5%,则观察到的长期概率约为20%,并保持短期运行的公平性。

这意味着,五分之一的命中应该是至关重要的。 问题是我得到了非常糟糕的现实生活中的结果 – 有时玩家会在5次命中中得到3次暴击,有时候15次都没有。

你需要的是一个洗牌袋 。 它解决了游戏中真随机过于随机的问题。

algorithm是这样的:你把一个关键的和四个非关键的命中放在一个袋子里。 然后你随机把他们的订单放在包里,然后一个一个挑出来。 当袋子是空的,你用相同的值再次填充并随机化。 这样,每5次命中就会平均得到1次重击,最多连续2次重击和8次非重击。 增加袋子中物品的数量以获得更多的随机性。

下面是一个实现 (在Java中)和我之前写的testing用例的例子 。

你有什么随意的误解。

哪一个更随机?

替代文字http://norvig.com/plot1.png 替代文字http://norvig.com/plot3.png

而第二个阴谋看起来更均匀分布,实际上第一个阴谋越多。 人的头脑经常看到随机性的模式,所以我们把第一块情节中的块看作是模式,但是它们不是 – 它们只是随机select的样本的一部分。

鉴于你所要求的行为,我认为你是随机错误的variables。

而不是随机化这个命中是否至关重要,尝试随机化回合的次数,直到发生下一次重击。 例如,每当玩家获得一个关键时刻,就select一个2到9之间的数字,然后在多轮结束后给他们下一个关键。 你也可以使用骰子方法来接近正态分布 – 例如,你将在2D4回合中获得下一个关键。

我相信这个技术也可以用在那些在地狱中随机遭遇的angular色扮演游戏中 – 你随机化了一个步伐计数器,然后在这个步骤之后,你再次被击中。 感觉更加公平,因为你几乎从来没有被连续两次遭遇击中 – 如果这种情况发生,甚至一次,球员变得烦躁。

首先,定义“适当”的分配。 随机数是随机的 – 你看到的结果完全符合(伪)随机性。

在此基础上,我假定你想要的是一些“公平”的感觉,所以用户不能没有成功就走100圈。 如果是这样,我会logging自上次成功以来的失败次数,并对生成的结果进行加权。 假设你想要五分之一的“成功”。 所以你随机产生一个从1到5的数字,如果是5,那么很好。

如果没有,logging失败,下一次,产生一个从1到5的数字,但是加上说,floor(numFailures / 2)。 所以这一次,他们又有一个五分之一的机会。 如果失败,下次获胜的时间间隔是4 5; 一个2的5成功的机会。 有了这些select,八次失败后,一定会成功。

如何用这样的东西replacemt_rand()?

XKCD漫画(RFC 1149.5指定4作为标准的IEEE审查随机数)。

(RFC 1149.5规定4作为标准的IEEE审查随机数。)

从XKCD 。

希望这篇文章能帮助你: http : //web.archive.org/web/20090103063439/http : //www.gamedev.net :80/reference/design/features/randomness /

这种产生“随机数字”的方法在rpg / mmorpg游戏中很常见。

它解决的问题是(提取):

刀片蜘蛛在你的喉咙。 它击中,你想念。 它再次击中,你又想念。 一次又一次,直到你没有什么可以打的。 你死了,你的尸体上有一个两吨的蜘蛛。 不可能? 不可能的 是。 但是给了足够的玩家足够的时间,这个不大可能性就变得几乎可以肯定。 这不是那个刀片蜘蛛很辛苦,只是运气不好而已。 多么令人沮丧。 这足以让一个球员想要退出。

你想要的不是随机数字,而是对人类来说是随机的数字。 其他已经build议单独的algorithm,可以帮助你,像Shuffle坏。

有关这个领域的详细和广泛的分析,请参阅AI游戏编程智慧2 。 对于任何游戏开发者来说,整本书都值得一读,“看似随机数”

AI决策和游戏逻辑的过滤随机性

摘要:传统观点认为,随机数发生器越好,游戏越不可预测。 然而,根据心理学的研究,短期内的真实随机性往往看起来对人类来说是绝无可能的。 本文展示了如何使随机AI决策和游戏逻辑看起来对玩家更随机,同时仍然保持强大的统计随机性。

你也可以find另一个有趣的章节:

随机数统计

摘要:人工智能和游戏一般使用随机数。 忽视他们的潜力是让游戏变得可预测和无聊。 不正确地使用它们可能和直接忽略它们一样糟糕。 了解如何生成随机数字,他们的限制和他们的能力,可以消除在你的游戏中使用它们的许多困难。 本文提供了对随机数,它们的生成以及将好的和坏的分开的方法的深入见解。

当然,随机数字生成有可能产生这样的运行? 你不会在3-10卷中获得足够多的样本集,以查看适当的百分比。

也许你想要的是一个仁慈的门槛…记得最后10卷,如果他们没有一个关键的打击,给他们一个免费赠品。 平滑随机的吊索和箭头。

你最好的解决scheme可能是用多种不同的随机scheme进行游戏testing,并select一个让玩家最快乐的scheme。

你也可以在给定的遭遇中尝试一个相同数字的回退策略,例如,如果玩家在第一回合掷出1接受它。 要获得另一个1他们需要连续滚动2 1秒。 要获得第三个1他们需要连续3个,无限的。

不幸的是,你所要求的实际上是一个非随机数字发生器 – 因为你想要在确定下一个数字时考虑到以前的结果。 这恐怕不是随机数发生器的工作原理。

如果你想每5次命中就有1次是一个关键,那么只需select一个1到5之间的数字,并说这个命中将是一个关键。

mt_rand()是基于Mersenne Twister的实现,这意味着它会产生一个最好的随机分布,你可以得到。

显然你想要的不是随意性,所以你应该开始明确指定你想要的。 你可能会意识到你的预期是相互矛盾的 – 结果应该是真正的随机性而不是可预测的,但同时它们不应该performance出所述概率的局部变化 – 但是这种变化是可以预测的。 如果你连续设置最多10个非暴击,那么你刚才告诉玩家“如果你连续有9次非暴击,下一次将是100%的确定性的关键” – 你可能会以及根本不打扰随机性。

在如此less量的testing中,您应该可以期待这样的结果:

真正的随机性只能在一个庞大的规模上才能预测到,因此很有可能第一次连续3次投掷硬币,然而超过几百万次的翻转,最终大概会达到50-50。

我看到很多答案build议跟踪以前生成的数字或洗牌所有可能的值。

就我个人而言,我不同意,连续3次爆击是不好的。 我也不同意,连续15次非暴击是不好的。

我会解决这个问题,通过修改每个数字后面的自我暴击机会。 示例(来演示这个想法):

 int base_chance = 20; int current_chance = base_chance; int hit = generate_random_number(0, 100) + 1; // anything from 1 to 100 if(hit < current_chance)//Or whatever method you use to check { //crit! if(current_chance > base_chance) current_chance = base_chance; // reset the chance. else current_chance *= 0.8; // decrease the crit chance for the NEXT hit. } else { //no crit. if(current_chance < base_chance) current_chance = base_chance; // reset the chance. else current_chance *= 1.1; // increase the crit chance for the NEXT hit. //raise the current_chance } 

你没有得到暴击的时间越长 – 你的下一个暴击行动的机会就越高。 我包括的重置是完全可选的,它需要testing来判断是否需要。 在长时间的非暴击行动链之后,对连续多个行动给出更高的爆击概率可能是也可能不是理想的。

只是扔我2美分…

前几个答案是很好的解释,所以我只专注于一个algorithm,可以控制“坏条纹”的概率,而不会成为确定性的。 以下是我认为你应该做的事情:

伯努利分布的参数不是指定p ,而是伯努利分布的参数,它是一个关键命中的概率,它指定ab ,β分布的参数,伯努利分布的“共轭先验”。 您需要跟踪AB ,到目前为止的关键和非关键点击次数。

现在,要指定ab ,确保a /(a + b)= p,这是重击的几率。 (a + b)量化了你希望A /(A + B)离p有多近。

你做这样的抽样:

p(x)是β分布的概率密度函数。 它在许多地方都可用,但是您可以在GSL中find它作为gsl_ran_beta_pdf。

 S = A+B+1 p_1 = p((A+1)/S) p_2 = p(A/S) 

从概率为p_1 /(p_1 + p_2)的bernoulli分布中选取重要的命中

如果你发现随机数有太多的“坏条纹”,按比例放大ab ,但是在极限情况下,当ab达到无穷大时,你将采用前面描述的shuffle bag方法。

如果你执行这个,请让我知道它是怎么回事!

如果你想要一个阻止重复值的分布,你可以使用一个简单的重复排斥algorithm。

例如

 int GetRand(int nSize) { return 1 + (::rand() % nSize); } int GetDice() { static int nPrevious=-1; while (1) { int nValue = GetRand(6); // only allow repeat 5% of the time if (nValue==nPrevious && GetRand(100)<95) continue; nPrevious = nValue; return nValue; } } 

这段代码在95%的时间内拒绝重复值,使重复不太可能,但不是不可能的。 统计上它有点难看,但它可能会产生你想要的结果。 当然,它不会阻止像“5 4 5 4 5”这样的分配。 你可能会更有兴趣,倒数第二(比如说)60%的时间,倒数第三(比如说)30%。

我不推荐这是好的游戏devise。 简单地build议如何实现你想要的。

这不是很清楚你想要什么。 可以创build一个函数,使得前5次调用它,它将以随机顺序返回数字1-5。

但是,这不是真的随机。 玩家将知道他将在接下来的5次攻击中获得一个5。 这可能是你想要的,在这种情况下,你只需要自己编码。 (创build一个包含数字的数组,然后洗牌)

或者,您可以继续使用您当前的方法,并假定您当前的结果是由于一个糟糕的随机生成器。 请注意,目前的数字没有任何问题。 随机值是随机的。 有时你会连续得到2,3或8个相同的值。 因为他们是随机的。 一个好的随机发生器只是保证平均而言,所有的数字将经常返回。

当然,如果你使用的是一个坏的随机生成器,那么结果可能会有偏差,如果是这样的话,只要改用一个更好的随机生成器就可以解决这个问题。 (查看Boost.Random库以获得更好的生成器)

或者,你可以记住你的随机函数返回的最后N个值,并用这些值来衡量结果。 (一个简单的例子就是,“对于每一次新的结果,我们都有50%的机会丢弃价值并得到新的结果”

如果我不得不猜测,我会说坚持“实际”的随机性是你最好的select。 确保你使用了一个好的随机生成器,然后继续按照现在的方式进行。

你可以创build一个包含从1到5的数字的列表,并按随机顺序进行sorting。 然后只是通过你创build的列表。 你至less有一次跑到每一个数字的保证…当你通过前5,只是创build另外5个号码…

我推荐一个像暴雪一样的渐进式百分比系统: http : //www.shacknews.com/onearticle.x/57886

一般来说,你滚动一个RNG,然后将它与一个值进行比较,以确定是否成功。 这可能看起来像:

 if ( randNumber <= .2 ) { //Critical } else { //Normal } 

所有你需要做的是增加一个渐进的增加基础的机会…

 if (randNumber <= .2 + progressiveChance ) { progressiveChance = 0; //Critical } else { progressiveChance += CHANCE_MODIFIER; //Normal hit } 

如果你需要它更加奇特,那么添加更多内容是非常简单的。 您可以限制progressivechance可以获得的数额,以避免100%重要的机会或在某些事件上重置。 您也可以通过ProgressChance + =(1 – progressiveChance)* SCALE(其中SCALE <1)来使progressivechance每次增加较less的数量。

那么,如果你有一点math,你可以试试指数分布

例如,如果lambda = 0.5,期望值是2(阅读这篇文章!),意味着你最有可能在每次第二回合中击中/暴击/无论如何(如50%,呵呵?)。 但是有了这样的概率分布,在第0回合(即事件已经发生并且turn_counter已经被重置的那一回合)中,你将定义为完全错过(或者与之相反),有40%的几率命中下一回合,大约65%第2次(接下来的下一个)转,大约80%打到第3次等等。

这个分配的全部目的是如果一个人有50%的命中机会,并且他连续三次失误,他会安然无恙(好吧,超过80%的几率,下一个回合就会增加)。 这会带来更“公平”的结果,保持50%的机会不变。

拿你20%的几率爆击,你有

  • 第一回合的暴击率为17%
  • 32%暴击第2回合,如果没有暴击发生在所有以前的。
  • 45%暴击第3回合,如果没有暴击发生在所有以前的。
  • 如果没有暴击发生在第四回合的话,54%。
  • 如果没有暴击发生在所有以前的80%,暴击第8回合。

在5个随后的轮次中,它仍然约为0.2%(相对于那些5%)的3次爆击+2次非爆击。 4次随机非暴击的概率为14%,5次为5%,6次为1.5%,7次为0.3%,其余8次为非暴击为0.07%。 我敢打赌它比“41%,32%,26%,21%和16%”更“公平”。

希望你还是不要无聊至死。

如何使得关键的机会取决于最近的N次袭击。 一个简单的scheme是某种马尔可夫链: http : //en.wikipedia.org/wiki/Markov_chain,但代码非常简单。

 IF turns_since_last_critical < M THEN critial = false turns_since_last_critical++; ELSE critial = IsCritical(chance); IF Critial THEN turns_since_last_critica = 0; ELSE turns_since_last_critica++; END IF; END IF; 

当然,你必须做出自己的math,因为一旦你知道自从上一次以来已经有足够多的回合了,那么一个关键的机会就低于一个关键的机会

OP,

如果你想要公平的话,那么它就不会是随机的。

你的游戏的问题是实际的比赛长度。 比赛时间越长,你将看到的随机性越低(暴击率往往是20%),并且会接近你的预期值。

你有两个select,根据之前的滚动预先计算攻击。 每5次攻击你会得到一个暴击(基于你的20%),但是你可以随机发出命令。

listOfFollowingAttacks = {Hit,Hit,Hit,Miss,Crit};

That's the pattern you want. So make it choose randomly from that list, until its empty, them re-create it.

That's a pattern I created for my game, it works quite well, for what I want it to do.

your second option, would be, increase the chance to crit, you are probably going to see a more even number in the end of all attacks(presuming that your matches ends rather quickly). The less % chance, the more RNG'd you get.

You are looking at a linear distribution, when you probably want a normal distribution.

If you remember back in your youth playing D&D, you were asked to roll multiple n-sided die, then sum the results.

For instance, rolling 4 x 6-sided die is different than rolling 1 x 24-sided dice.

City of Heroes actually has a mechanic called the "streakbreaker" that solves exactly this problem. The way it works is that after a string of misses of a length related to the lowest to-hit probability in the string, the next attack is guaranteed to be a hit. For example if you miss an attack with over 90% to hit chance then your next attack will auto hit, but if your hit chance is lower like 60% then you'll need to have several consecutive misses to trigger the "streakbreaker" (I don't know the exact numbers)

替代文字

this one is really predictable… but you can never be sure.

How about weighting the value?

For example, if you have a 20% chance to critical hit, generate a number between 1 and 5 with one number representing a critical hit, or a number between 1 and 100 with 20 numbers being a critical hit.

But as long as you are working with random or pseudorandom numbers, there's no way to potentially avoid the results you are currently seeing. It's the nature of randomness.

Reaction on: "The problem is I got very bad real life results — sometimes players get 3 crits in 5 hits, sometimes none in 15 hits."

You have a chance of somewhere between 3 and 4 % of getting nothing in 15 hits…

I would propose the following "randomly delayed putback die":

  • Maintain two arrays, one ( in-array ) initially filled with the values from 0 to n-1, the other ( out-array ) empty
  • When a result is requested:
    • return a random value from all defined values in in-array
    • move this value from in-array to out-array
    • move one random (over all elements, including the undefined!) element from out-array back into in-array

This has the property that it will "react" more slowly the bigger n is. For example, if you want a 20% chance, setting n to 5 and hitting on a 0 is "less random" than setting n to 10 and hitting on a 0 or 1, and making it 0 to 199 out of 1000 will be almost indistinguishable from true randomness over a small sample. You will have to adjust n to your sample size.

Pre-calculate a random critical hit for each player.

 // OBJECT //... // OnAttack() //... c_h = c_h -1; if ( c_h == 0 ) { // Yes, critical hit! c_h = random(5) + 1 // for the next time // ... } 

I think perhaps you are using the wrong random distribution function. You probably don't want an even distribution over the numbers. Try a normal distribution instead so that the critical hits become more uncommon than the 'regular' hits.

I work with Java so I'm not sure where you can find something for C++ that gives you random numbers with a normal distribution but there has to be something out there.