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 comments

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

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

  3. Jouni OsmalaNo Gravatar

    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.

  4. 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.

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

  6. 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.

  7. 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.

  8. 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…

  9. Mark BeadlesNo Gravatar

    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.

  10. […] 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 […] […]

  11. 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

  12. 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).

  13. […] Why seeding is important for random functions… or, How to Cheat at Bejeweled. […]

  14. PearlsphereNo Gravatar

    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. 😛

  15. 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.

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

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

  17. 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.

  18. 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.

  19. 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.

  20. 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! :]

  21. 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.

  22. 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.

  23. 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!

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

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

  26. Scott LantzNo Gravatar

    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?

  27. 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.)

  28. 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 🙂 ).

  29. 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…

  30. 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.

  31. Scott LantzNo Gravatar

    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

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

  33. Scott LantzNo Gravatar

    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.

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

  35. 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!

  36. 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