Stochastic Geometry

October 24, 2009

Why seeding is important for random functions…

Filed under: General — Mark Dennehy @ 01:40

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):

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);

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.

Advertisements

36 Comments »

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

    Comment by stephen — October 24, 2009 @ 06:16 | Reply

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

      Comment by Mark Dennehy — October 25, 2009 @ 00:08

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

    Comment by Evan — October 24, 2009 @ 06:47 | Reply

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

      Comment by Mark Dennehy — October 25, 2009 @ 00:09

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

    Comment by Jouni Osmala — October 24, 2009 @ 10:36 | Reply

    • 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…

      Comment by Mark Dennehy — October 25, 2009 @ 00:10

  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.

    Comment by Travis Phillips — October 24, 2009 @ 15:48 | Reply

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

    Comment by BetInvest — October 24, 2009 @ 16:24 | Reply

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

    Comment by Mark Beadles — October 25, 2009 @ 13:00 | Reply

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

    Pingback by Top Posts « WordPress.com — October 26, 2009 @ 01:03 | Reply

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

    Comment by Scott Lantz — October 26, 2009 @ 18:29 | Reply

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

      Comment by Mark Dennehy — October 27, 2009 @ 01:14

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

      Comment by Scott Lantz — October 27, 2009 @ 16:48

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

      Comment by Akos — November 2, 2009 @ 18:03

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

      Comment by Jen — November 6, 2009 @ 20:07

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

    Pingback by Chain Links #044 | Proc#curry — October 27, 2009 @ 06:08 | Reply

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

    Comment by Pearlsphere — October 27, 2009 @ 15:04 | Reply

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

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

    Comment by Dave — October 29, 2009 @ 01:23 | Reply

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

    Comment by Mark — October 29, 2009 @ 03:49 | Reply

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

    Comment by Chad — November 2, 2009 @ 20:46 | Reply

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

    Comment by Jen — November 6, 2009 @ 18:58 | Reply

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

    Comment by Nicolas — November 7, 2009 @ 20:16 | Reply

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

    Comment by Jen — November 24, 2009 @ 23:05 | Reply

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

    Comment by Mark — December 14, 2009 @ 00:43 | Reply

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

      Comment by Akos — December 17, 2009 @ 01:13

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

    Comment by Scott Lantz — December 17, 2009 @ 03:03 | Reply

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

      Comment by Akos — December 17, 2009 @ 11:44

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

    Comment by Akos — December 17, 2009 @ 11:48 | Reply

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

    Comment by Scott Lantz — December 17, 2009 @ 17:32 | Reply

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

      Comment by Akos — December 17, 2009 @ 18:15

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

    Comment by Scott Lantz — December 17, 2009 @ 19:34 | Reply

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

      Comment by Mark Dennehy — December 17, 2009 @ 19:42

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

    Comment by Scott Lantz — December 17, 2009 @ 19:58 | Reply

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

    Comment by Mark — December 19, 2009 @ 06:25 | Reply

    • 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!

      Comment by Jen — December 22, 2009 @ 22:23

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

    Comment by Jen — December 23, 2009 @ 05:15 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: