Streaky PRNG

From WarfishWiki

Jump to: navigation, search

I've taken engineering statistics classes before. This has kind of annoyed me fairly often, but I've been quiet, but then I had other people making similar comments.

It seems the PRNG (Pseudo-Random Number Generator, for those not aware of the acronym) is far too streaky. You might say, "well that just means it's really random." I'd agree if it was a rare occurrence, but it happens quite often. You might say, "but everything seems fairly even on the stats page," but the streakiness just seems to level out between hot and cold. That's why you can somehow lose a 20-3 continuous attack (and taking out only 1 defender of the 3 in the process), and then have a bunch of wins without incident. I believe, statistically, losing 20-3 under normal conditions should not happen very often, yet I see it quite a bit.

What I, and other people have noticed, is that you'll go on a hot streak of 6's and 5's but the defender will seem to match it every time. It's strange enough that it makes people think about it.

So, while I haven't done the actual math on the statistical odds of any of this (because really, who wants to do that?) it may be good to revisit the PRNG code. Perhaps a better, more dynamic seed is needed. I know that with continuous attacks it is likely that the PRNG is using the same current division of time for each roll, which could definitely affect the randomness.

It's also entirely possible that myself and the folks that have complained about it are completely wrong, so feel free to offer a dissenting opinion. --FadeToOne

Thank you for framing this so well. Indeed, much of the feedback on this issue involves sending me one or two examples of a streak and stating that the mere existence of a streak as an indication that something is is "obviously" wrong. I appreciate that you describe the issues so thoroughly. The randomness of the dice have definitely been one of the more controversial issues on the site and can mostly likely use more refinement.
-
Over the years, I have been sending the Warfish code to anyone who has sent in feedback about the dice and has been interested in looking at it, so it has been reviewed and modified by quite a number of people. I'll include it here for further code reviewing:
def versusAttack(fromunits, tounits, adie = None, ddie = None):
   # seeding moved to once per http request because this
   # function is called in a tight loop for continuous attacks 
   # and seeding here would result in the same results returning most
   # of the time.
   # random.seed()
   if tounits >= 2: numdefend = 2
   elif tounits < 0: numdefend = 0
   else: numdefend = tounits
   if fromunits > 3: numattack = 3
   else: numattack = fromunits
   defenddice = [random.randint(1,ddie) for i in range(numdefend)]
   defenddice.sort()
   defenddice.reverse()
   attackdice = [random.randint(1,adie) for i in range(numattack)]
   attackdice.sort()
   attackdice.reverse()
   defenderlosses = 0
   attackerlosses = 0
   for i in range(min(numdefend,numattack)):
       if attackdice[i] > defenddice[i]: defenderlosses += 1
       else: attackerlosses += 1
   return (attackerlosses, attackdice, defenderlosses, defenddice)
In addition to reviewing the code, even though it is a lot of work... another strategy which you mention above for doing analysis of the randomness would be to look at the dice rolls for prior games to gather statistical evidence that there are too many streaks. This I think maybe the next step in getting deeping into this issue. But then the question is what is an effective way if detecting "too many streaks"? Btw, all the die rolls are available for each game via the XML apis. --Steven 19:58, 21 April 2008 (UTC)
I'm assuming that is python code? I did some reading on python's PRNG and it seems fairly robust (unless the version of python is older than 2.3). I even tested a small script and it doesn't seem to be out of the ordinary. My guess is when we are hitting streaks we are encountering true randomness, yet it strikes us as wrong because it appears to not be random. With true random, anything can happen and eventually will, so we just may not expect streaks as much as we should? Who knows... --FadeToOne 22:17, 23 April 2008 (UTC)
Yes that is python code >=v2.3 and actually someone brought up that in some cases (like for Java) built in PRNGs are known to be faulty. So we looked up which particular PRNG python used and found it to be pretty robust.
-
With regards to it appearing wrong.. i agree it at times feels wrong, but I have to say for me it would be difficult to factor out selective memory when evaluating it that way. For example, I'm sure I get favorable streaks as well.. but even though every once in a while I'm able to plow through someone attacking them 20 vs 20.. it doesn't stick in my mind as well... so I still feel that the dice are out to get me. In fact, some folks have sent in feedback before asking if there was anything in the code that depended on the userid itself since they were convinced there was something in the code that specifically targetted their user id. Haha.. besides the code that checks for my userid and throws in some extra sixes.. this isn't that case (j/k btw).
-
At one point another concern was the time of day (which perhaps was plausible). That attacking certain times of the day would result in always ending up in the same areas of the PRNG. That, btw, was when the seeding was moved from server initialization to once per request. When it was initialized at server startup it was possible that there were times of the day when servers more likely to be started (like really late at night) which had a small probability of causing seeding to happen more at a certain time of day. Btw... seeding once per requeset apparently also has its flaws since I guess the higher order bits are not as signficant when seeding the PRNG so it is possible that requests that come in too quickly one after another will be given the same seed. But that seemed like a minor point of concern. In practice that would just mean that if you two attacks in different games where players happened to be attacking almost at the same time would get the same die rolls... or if you saw a die roll you liked and attacked immediately (perhaps within microseconds) from the time you placed your first attack you might get similar numbers again, but with network latency and webserver/browser interaction it is unlikely anyone would be able to do it that quickly anyhow.. and after all that one is not even guaranteed to get the same roll.
-
Here is another way to look at it. Lets assume that the PRNG is completely screwed up in some way, I hope it isn't, but assume for the sake of argument it is doing something very wrong. Then it seems that everyone is suffering from using the same PRNG and even if it was streaking too much would that necessarily make it unfair? Seems like in that case it would have a broken PRNG but the game would technically still be fair since everyone is having to deal with it.
-
Finally, other folks have in the past have also written test harnesses after I've provided them the code. If you wouldn't mind posting yours here perhaps you could save future folks the trouble (and then we could also inspect it for flaws as well).
-
Thanks for taking the time to investigate this... definitely a complicated issue.
--Steven 23:12, 23 April 2008 (UTC)
Oh, I didn't code up anything special... just took the respective random calls to see what I got and if anything suddenly occurred to me for some reason. I will say though, being that the python PRNG is deterministic, every dice roll would be depend on the dice before it (and as such, the attacking dice would depend on the defending dice in your code), but this falls back to the PRNG being good enough that it shouldn't be much of an issue. I definitely agree on the selective memory, but I think another aspect of the problem is that people don't know the actual dice odds well enough to believe that a long streak could happen fairly often (winning outright using 3 dice vs 2 dice only has a 37% chance of happening, which I learned today) so you have a 63% chance of losing at least 1, which could enable fairly long streaks. --FadeToOne 04:50, 24 April 2008 (UTC)
Personal tools