Why seeding is important for random functions…

Like many people these days, I use facebook to track what’s going on with friends and family I don’t get to see as often as I would have done in years past. Long work days, large numbers of balls in the air and general “stuff” prevents actual face time far too often, but while it’s not the same as a night spent laughing over a beer, it’s better to note that a friend has a new job or that there’s a new baby en route or whatever over facebook than not at all.

And of course, facebook has games. Which is handy sometimes, for those moments when you have literally six or seven minutes to fill – too much time to sit still and be bored, too little to get anything real started. Personally, I play bejewelled on facebook for those moments. It’s been set up rather nicely there – blitz games of one minute, with scores being tracked so that friends compete in weekly rankings and little medals at various scores and scores being classed as being in the top X% globally and so on. The thing about this is that now you have a large community of people (over five million within six months of its launch according to Popcap, who wrote the game), all competing against one another – so now it’s important that it be fair or it feels like it’s not worth playing. Unfortunately tonight I noticed that someone’s been too clever.

The game’s written in actionscript. I obviously don’t know the source code, but I have a pretty good guess as to what mistake’s been made here. I’m guessing that to set up the initial game board, they used the noise() function to generate a bitmap with the six pieces represented by the values in one channel of the bitmap like so (adopted from the Adobe documentation):
[cc escaped=”true” lang=”actionscript”]var myBitmap:BitmapData = new BitmapData(8, 8,false, 0xff000000);
myBitmap.noise(<RANDOM NUMBER HERE>, 0, 5, BitmapDataChannel.BLUE,true);
var image:Bitmap = new Bitmap(myBitmap);[/cc]
So now you just read the bitmap, and for each of the 8×8 pixels, if the value is 0 display a blue diamond, if it’s 1 display a red square, etc, etc. It’s a clean enough way to do it, but it has a flaw, highlighted in light blue there. If the <RANDOM NUMBER HERE> number isn’t actually random, the noise looks the same every single time. And if they’ve used another method that calls Math.random(), I’m guessing they’re not seeding it correctly there either because what I’m seeing in the game is a fairly classic case of a random() function being repeatedly called without reseeding and giving the same sequence each time. In my case, I played three games before noticing that they all opened up like so:

Screenshot1

If I drag a yellow piece up to create a three-in-a-row in the top left corner there, it disappears and three blue pieces fall down from the top to replace them, creating a five-in-a-row (a hypercube in the game’s parlance) like so:

Screenshot2

If I use that hypercube to delete all the blue pieces on the board, a multiplier bonus falls in attached to a red piece in the upper left quadrant of the board like so:

Screenshot3

(You’ll note the timer at the bottom of the game is running out fast here, this is because I’m taking screenshots at leisure). If I now move the white piece in the top left quadrant to create a vertical three-in-a-row, it disappears, the multiplier (X2) piece falls down and a red piece falls behind it, creating a three-in-a-row of red pieces which vanish leaving this:

Screenshot4

And the game progresses on from there. But the point is that this is the same sequence, every time I’ve played. So far I’ve repeated the same board in something like fifteen games (mostly while grabbing screenshots and mucking about). So it’d be perfectly possible for me to spend hours exploring this board’s possible permutations to find the optimum set of moves, or in simpler words, to cheat.

And suddenly the game isn’t fun anymore. Did person X beat my high score because they spent time playing the same game over and over honing their procedure? Is my own high score really valid anymore as a result of this? And yes, there are indeed cheating methods already available to those who are willing to install software to their browser to crack the game, but this is somehow different from that, there’s less effort required to cheat using this bug and less malicious intent as well. So it’s a nice game ruined by someone missing one single step in the setup of the game board – namely, they forgot to seed the random function with an appropriate seed value which changes between sessions.

36 thoughts on “Why seeding is important for random functions…

  • Oct 24, 2009 at 0616
    Permalink

    Flash’s seeding of its random number generator is handled internally.

  • Oct 24, 2009 at 0647
    Permalink

    I just tried to reproduce this problem with no luck. Could it possibly be your version of flash?

  • Oct 24, 2009 at 1036
    Permalink

    Sometimes this is done INTENTIONALLY in different style games.
    The purpose of the replay value isn’t in trying to find best random seed, but to have a competition who gets best result when EVERYTHING is same between tries except what results change by gamers actions.

  • Oct 24, 2009 at 1548
    Permalink

    Interesting…I have not noticed that myself. I love playing games on facebook. Sometimes I think I spend way too much time on there. Nice post.

  • Oct 24, 2009 at 1624
    Permalink

    We are spending much time on facebook all of us ! Don t worry, Travis Phillips! 🙂

  • Oct 25, 2009 at 0008
    Permalink

    In Math.random() it’s meant to be, in Bitmap.noise() it’s not.
    Whether it actually really is or not is down to the actual platform from what I can see.

  • Oct 25, 2009 at 0009
    Permalink

    It’s possible, but there’ve been reports of the same thing from others who’ve then noticed it being fixed in the game. Popcap may have noticed the problem and solved it.

  • Oct 25, 2009 at 0010
    Permalink

    If this is done intentionally, then (a) why has it not been seen before, and (b) it’s a really stupid design choice. If I want the same starting conditions always, I’ll play chess…

  • Oct 25, 2009 at 1300
    Permalink

    The game starts differently every time for me, which is a pretty good counterexample. It’s possible that you have a library from either Flash or from your OS that has a randomness flaw. If so, the implications there are worse than making a game no fun. If any crypto functions use that same library, you’d be losing randomness for encryption.

  • Pingback: Top Posts « WordPress.com

  • Oct 26, 2009 at 1829
    Permalink

    Hey there — Scott Lantz from PopCap here. Just wanted to let you know that we saw this and are looking into the problem. We definitely do seed the random number generator with the current timer, but for some reason in some cases, it appears the timer value reported by Flash is 0. That appears to be the case in the screenshot of your initial board state (given that a seed of 0 always looks the same.)

    Also, if people are seeing this issue intermittently or are seeing it fix itself, that’s odd given that we haven’t touched the code since we launched the new Blitz 3 weeks ago or so.

    We’ve haven’t ever seen this internally and haven’t been able to reproduce it, but we have received one other comment recently about this. Would you mind sharing your OS and browser information with us? The one other case we know of is happening on a Firefox alpha build on Linux. Also, I would be curious if the problem would somehow fix itself if you were to try a different browser.

    Anyway, of course we’re delighted to see people playing Blitz, and we’re sorry you’ve been having these issues. We are looking into it, and hopefully we can figure out an alternate method that isn’t subject to whatever is causing this problem.

    Cheers,
    Scott Lantz
    Associate Producer – Online and Social
    PopCap Games

  • Oct 27, 2009 at 0114
    Permalink

    Thanks Scott. I’m still seeing the same error here at the moment, so if the code has been unchanged for weeks, that strongly points towards the flash platform itself (which is Adobe Flash 10.0.32.18 for Linux running in Firefox 3.0.14 here on my Debian Squeeze system).

  • Pingback: Chain Links #044 | Proc#curry

  • Oct 27, 2009 at 1504
    Permalink

    Being a Bejeweled Blitz addict, I played that game zillions of times but didn’t even notice that the gems on the board wasn’t reshuffled. Oh well…my score is still the highest among my friends so it doesn’t relly matter if someone was cheating at Blitz. 😛

  • Oct 27, 2009 at 1648
    Permalink

    Ah, so you’re using Linux as well. I can only assume this is a problem specifically with the Flash Player on Linux+Firefox. We’ve only seen 2 reports of the problem so far (yours and one other), but both were on an OS/browser pair that is quite rare when it comes to Blitz players. That seems too specific and too statistically unlikely to be coincidence.

  • Oct 29, 2009 at 0123
    Permalink

    I get the same board on my Bejeweled ….. Every time……

    Firefox Browser, with Flash 10 on 64-bit Linux. Maybe a Flash bug?

  • Oct 29, 2009 at 0349
    Permalink

    I am also using 64 bit flash 10 64 bit linux(Fedora 11). I am encountering it on two machines that are running the 64 bit flash. I don’t think it was happening after the initial release of the new version of Bejeweled, but I can’t prove that.

  • Nov 2, 2009 at 1803
    Permalink

    It only seems to be happening on 64-bit Linux (Flash version 10.0.32.18, Firefox 3.0.14 on Gentoo Linux). On 32-bit Gentoo Linux, with the exact same versions, everything is OK. 64-bit Vista is also OK.

    Also, for me this started around 23-24 October (I’d guess 23rd), definitely had no problem before.

  • Nov 2, 2009 at 2046
    Permalink

    I was affected on Ubuntu 9.04 64-bit, Firefox 3.5.4. After updating Flash Player to 10.0.32.18. I now get random boards as expected.

  • Nov 6, 2009 at 1858
    Permalink

    I recently updated flash [the 64 bit alpha] from 10.0.22 to 10.0.32.18 on Debian lenny Linux 64bit with firefox 3.5, but alas, I still get the exact same board you posted above, every time.

    I figured it must have had to do with me being on ilnux [also the reason the bejeweled folk haven’t answered my problem report, I assumed], but my old 32-bit ubuntu hardy laptop generated new boards just fine.

    Thanks for this post, Mark! It was more information than I had hoped to find out there! :]

  • Nov 6, 2009 at 2007
    Permalink

    Just to chime in; I was still running the older 10.0.22 version of the 64-bit flash alpha release, and still started experiencing the “same board” problem at around the same date Mark’s post mentioned, so it doesn’t have to do with any recent updates to the flash platform at least…

    So, nothing on my end changed at all [no OS updates, no ff updates, no flash updates] when the game started to show me the same board.

  • Nov 7, 2009 at 2016
    Permalink

    My board looks exactly like the one on your screenshot.

    Using Debian squeeze, 64-bit; Flash 10.0 r32, I don’t know if it’s 32-bit or 64-bit; happens in both Iceweasel (rebranded Firefox) and Konqueror.

  • Nov 24, 2009 at 2305
    Permalink

    Bejeweled changed something on their end within the past 2 weeks and it is now fixed for the same 10.0.32.18 64bit flash on linux….
    Hooray!

  • Dec 14, 2009 at 0043
    Permalink

    Something happened today and it’s back to the same board.

  • Dec 17, 2009 at 0113
    Permalink

    Yes, for a few days now. I hate that board.

  • Dec 17, 2009 at 0303
    Permalink

    Honestly guys, we aren’t changing code back and forth. We have not touched the randomization logic since the new version launched quite a while ago.

    If the board is sometimes working and sometimes not, maybe that’s somehow related to the nature of the bug in the version of the Flash player with the problem?

  • Dec 17, 2009 at 1144
    Permalink

    Hi Scott,

    thanks for following these comments. Please note that I am trying to help here, not trying to bash PopCap, or anything like that. Of course, I would love it if BB worked.

    Anyway, I looked at my emerge history. I had the same flash version (10.0.32.18) from Aug 4 to Dec 14. During this time, you launched the new version, which worked for a while, then stopped working near the end of October, then started to work again sometime in the middle of November. I am 100% certain nobody touched the adobe flash player on my computers during this time. The problem manifested on all 64-bit Linux computers, and there was no problem at all on 32-bit Linux machines and on Windows (which I don’t use unless I have to). So it is entirely possible that the flash player is at fault here, especially since the 64-bit Linux version is a bigger pile of junk than usual. But then please tell me what might be the reason for it continuously working for a month, then continuously not working for another?

    If there is any way I can help you guys debug this problem, please tell me. (Also, if you don’t want to bother with 64-bit Linux users, that’s OK, too. Tell me, and I won’t bother either.)

  • Dec 17, 2009 at 1148
    Permalink

    I forgot to add, that since Monday, I tried both 10.0.32.18 and 10.0.42.34. Bejeweled is working with neither (besides that board from hell 🙂 ).

  • Dec 17, 2009 at 1732
    Permalink

    Hi Akos,

    I can’t tell you why it would juggle between working and not working, other than the reason does *not* lie with us. We did not update the code to the game in the specific timeframes mentioned, and we have certainly not touched the randomization code in any way since we launched the new Blitz.

    My best guess: Since the randomization seed inside of Flash is tied to the timer, it seems plausable to me that something about the time values could be conditionially triggering the bug. That could explain why it works at some times and not others. But that’s purely speculation, of course.

    It’s overwhelmingly clear from the feedback in this thread that this problem is isolated to 64-bit Linux. We have yet to have a single report from any of our millions of players that they suffer this problem on another OS.

    And I hate to say it, but we both can’t provide a fix (because the problem isn’t in our code) and we can’t justify spending any more time investigating this issue on this platform. I hope you understand it’s hard enough to find the time to make the improvements we want for our millions of players that we can’t afford to get bogged down in any such tiny slice of our user base.

    Sorry I don’t have anything better to tell you…

  • Dec 17, 2009 at 1815
    Permalink

    Hi Scott,

    thanks for the honest reply, I do appreciate it. I definitely agree with you on the technical part. Waving off a “tiny slice of your user base” is PopCap’s decision to make, and I see your reasons. My decision is whether to ever buy anything from PopCap, or recommend to any friends either on Facebook or outside of it. This way the answer is an easy and obvious no.

  • Dec 17, 2009 at 1934
    Permalink

    Hi there Akos,

    I’m sorry to hear that. Though I have to admit I don’t understand why you would discourage people you care about from playing games they would most likely like, all because one of our free web games doesn’t run on a corner-case environment because of a bug in Adobe’s Flash implementation on that platform.

    But I guess that’s your choice to make. I wish you the best.

    -Scott

  • Dec 17, 2009 at 1942
    Permalink

    I wonder Scott, if PopCap would consider it worth it to issue a “bug bounty” for this particular bug?

  • Dec 17, 2009 at 1958
    Permalink

    I’m sorry to have to say it, but this is going to have to be my last post on this subject. It’s starting to seem like a mistake that I responded in the first place, even though I was only trying to help.

    We are absolutely slammed trying to make this game better for millions of people. I don’t know if you guys realize how truly tiny a slice 64-bit Linux is for our product. It’s way less than a tenth of one percent. To give a sense of perspective, we generally don’t support browsers with less than 3% usage because we need to focus on moving the game forward for the extreme majority.

    I totally understand you guys wanting this problem fixed. I do too. But again, this is not a problem with our codebase. This is a problem with the Adobe Flash player on 64-bit Linux. If you guys have an investment in seeing this bug fixed, Adobe seems like the right place to lean on.

    I’m sorry I’m not able to help further. I wish you all the best.

  • Dec 19, 2009 at 0625
    Permalink

    Scott, Thanks for your help. If I change my system date to 11/24/2009, I get random boards.

  • Dec 22, 2009 at 2223
    Permalink

    Mark, how brilliant! lol. I thought perhaps any date before 11/24 would also work, but no go with 11/1/2009, either…. What an odd bug.
    Thanks again for your post and bringing even a popcap developer into the discussion. This has been great!

  • Dec 23, 2009 at 0515
    Permalink

    PS: My bad; I thought Nov 24 was the day we first encountered the problems… maybe before ~Oct 20th then…

Leave a Reply

Your email address will not be published. Required fields are marked *

Stochastic Geometry is Stephen Fry proof thanks to caching by WP Super Cache

%d bloggers like this: