I cheat at Bejeweled Blitz

August 19, 2009 § 28 Comments

bejeweled_blitz_25KSo, there’s this great game called Bejeweled Blitz. It’s basically the most evil game I’ve ever played. It sucks you in with the promise of glories and riches in return for only one minute of your time, and you find yourself wandering away from the computer in a stupor hours later wondering what happened and why you still haven’t gotten better than that 25K medal.

The problem, really, is that I suck at this game. The rules are deceptively easy, but it requires a quick pattern matching ability that I simply do not seem to possess. Oh, I do alright; I’ve managed to get 125K occasionally, but often it’s more in the 15K range. My wife (the temptress who started me on the journey into despair that I call Bejeweled Blitz) is fabulous at the game, and rarely scores less than 50K on any given game.

So, despite the fact that I suck at this game, and really, there’s no hope that I’ll ever really be good at it, I couldn’t stop playing it. It was taking away time from more productive pursuits, and I decided I needed to slay this evil dragon. While I might suck at playing Bejeweled Blitz, I’m pretty darn good at writing software. I thought that maybe, just maybe, if I spent my time writing a program to play Bejeweled Blitz, I might be able to beat my addiction and in the process, maybe learn a little something.

I’m happy to say that I was successful – I’ve beaten my addiction. Oh, I play it once in a while, but it’s largely lost its hypnotic power over my mind. It wasn’t easy, but the effort has paid off, and I’m a better person for it now. Here’s how I did it.

bejeweled_blitz_5I set up a windows forms project in Visual Studio, brought up the browser on my screen with Bejeweled Blitz already loaded in it, and started up the application.

Step one is getting the board off of the browser and into a program so that I can work with it. That’s just basic screen scraping, and is actually pretty simple. I set up textboxes on the form so that I can adjust the top, left, height, and width at runtime, depending on the position of the browser window and whatever variable information is loaded in the browser. Then, some code like this, and I’ve got a bitmap image of the screen.

    Rectangle r = new Rectangle(
        Convert.ToInt32(tbxX.Text),
        Convert.ToInt32(tbxY.Text),
        Convert.ToInt32(tbxWidth.Text),
        Convert.ToInt32(tbxHeight.Text));
    Bitmap bitmap = new Bitmap(r.Width, r.Height);

    using (Graphics g = Graphics.FromImage(bitmap))
    {
        g.CopyFromScreen(
            new Point(r.X, r.Y),
            new Point(0, 0),
            r.Size);
    }

bejeweled_blitz_4I can then display the bitmap on my form, so I can keep track of the difference (if any) between what’s displayed in the browser, and what my program has to work with.

Of course, just having a bitmap doesn’t do much for me, I have to translate that bitmap into a game board that I can work with in memory. I set up a class to represent a piece on the board like the following. The reason I track the color of the piece, as well as the “whiteness” of the piece, is because there are certain pieces in the game that *sparkle*, and using them scores more points. Tracking this part of the piece allows the program to make better decisions about which piece to move.

    public class Piece
    {
        public Color PieceColor { get; set; }
        public int PieceWhiteness { get; set; }

        public Piece()
        {
            PieceColor = Color.White;
            PieceWhiteness = 0;
        }
    }

I then create an 8×8 array of “Pieces”. Populating it is tricky, and actually gave me a lot of problems. I tried several different methods, but the one I finally settled on looks something like the following. I think the comments in the code explain most of what’s going on there.

    Random random = new Random();
    Bitmap bitmap = (Bitmap)pbBoard.Image;

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            board[i, j] = new Piece();

            // build up a whole array of colors for this piece
            // this is done to correct for minor errors/variations
            // when reading the different pieces
            // we use a random factor so that the same error isn't
            // repeated over and over when the color analysis/matching
            // is not completely correct
            List<Color> colors = new List<Color>();
            for (int k = 0; k < 5 + random.Next(15); k++)
            {
                for (int m = 0; m < 5 + random.Next(15); m++)
                {
                    int x = toX(i);
                    int y = toY(j);
                    colors.Add(bitmap.GetPixel(x - k, y - m));
                    colors.Add(bitmap.GetPixel(x - k, y + m));
                    colors.Add(bitmap.GetPixel(x + k, y - m));
                    colors.Add(bitmap.GetPixel(x + k, y + m));
                }
            }

            for (int colorCount = colors.Count - 1; colorCount >= 0; colorCount--)
            {
                // if the color is more or less white,
                // this adds to the whiteness, not the color
                int colorDiff = diff(colors[colorCount], Color.White);
                if (colorDiff < 100)
                {
                    board[i, j].PieceWhiteness++;
                    colors.RemoveAt(colorCount);
                }
            }

            // the only pieces with this much whiteness are
            // actually just white pieces
            if (board[i, j].PieceWhiteness > 100)
            {
                board[i, j].PieceWhiteness = 0;
            }

            // the color of the piece is the average of all the non-white(ish) pixels
            board[i, j].PieceColor = avg(colors.ToArray());
        }
    }

The “avg” and “diff” functions aren’t all that complicated, but it took me a few minutes to figure out how to diff and average colors. The code for that is as follows.

    private int diff(Color c1, Color c2)
    {
        double red = Math.Pow(Convert.ToDouble(c1.R) - c2.R, 2.0);
        double green = Math.Pow(Convert.ToDouble(c1.G) - c2.G, 2.0);
        double blue = Math.Pow(Convert.ToDouble(c1.B) - c2.B, 2.0);

        return (int)Math.Sqrt(blue + green + red);
    }

    private Color avg(Color[] colors)
    {
        int aTotal = 0;
        int rTotal = 0;
        int gTotal = 0;
        int bTotal = 0;

        foreach (Color c in colors)
        {
            aTotal += c.A;
            rTotal += c.R;
            gTotal += c.G;
            bTotal += c.B;
        }

        if (colors.Length == 0)
        {
            return Color.White;
        }
        else
        {
            return Color.FromArgb(
                (int)(aTotal / colors.Length),
                (int)(rTotal / colors.Length),
                (int)(gTotal / colors.Length),
                (int)(bTotal / colors.Length));
        }
    }

bejeweled_blitz_3So anyway, once I have the board built, I can also display that on the form so that I can debug errors and inconsistencies in that whole board translation process above. This isn’t exactly a flashy presentation, but it does the job that I needed.

Now, that’s the easy part – the hard part of this application was figuring out the best moves to make. There’s lots of different options – do you go from the top to the bottom, or the bottom to the top? Do you preferentially get 4 in a row to make more power gems, or do you blow up the power gems you already have? Do you try to think ahead and analyze the chain of events that will occur following each move? Can you do all of that fast enough that your program isn’t wasting time thinking about which move to make instead of just actually making the move? I’m not posting my code for this. If you want to cheat, you can do the work yourself. Suffice it to say, I figure out which move I want to make, but then I need to actually make it.

So, we’re just going to make the program play the game the same way you or I would play the game – it’s going to click on it. Here’s a handy little class to send mouse clicks. You can just pass the x and y coordinates that you want to click on, and it’ll take care of it.

    public class SendInputClass
    {
        //C# signature for "SendInput()"
        [DllImport("user32.dll", EntryPoint = "SendInput", SetLastError = true)]
        static extern uint SendInput(
            uint nInputs,
            INPUT[] pInputs,
            int cbSize);

        //C# signature for "GetMessageExtraInfo()"
        [DllImport("user32.dll", EntryPoint = "GetMessageExtraInfo", SetLastError = true)]
        static extern IntPtr GetMessageExtraInfo();

        private enum InputType
        {
            INPUT_MOUSE = 0,
            INPUT_KEYBOARD = 1,
            INPUT_HARDWARE = 2,
        }

        [Flags()]
        private enum MOUSEEVENTF
        {
            MOVE = 0x0001,  // mouse move 
            LEFTDOWN = 0x0002,  // left button down
            LEFTUP = 0x0004,  // left button up
            RIGHTDOWN = 0x0008,  // right button down
            RIGHTUP = 0x0010,  // right button up
            MIDDLEDOWN = 0x0020,  // middle button down
            MIDDLEUP = 0x0040,  // middle button up
            XDOWN = 0x0080,  // x button down 
            XUP = 0x0100,  // x button down
            WHEEL = 0x0800,  // wheel button rolled
            VIRTUALDESK = 0x4000,  // map to entire virtual desktop
            ABSOLUTE = 0x8000,  // absolute move
        }

        [Flags()]
        private enum KEYEVENTF
        {
            EXTENDEDKEY = 0x0001,
            KEYUP = 0x0002,
            UNICODE = 0x0004,
            SCANCODE = 0x0008,
        }

        [StructLayout(LayoutKind.Sequential)]
        private struct MOUSEINPUT
        {
            public int dx;
            public int dy;
            public int mouseData;
            public int dwFlags;
            public int time;
            public IntPtr dwExtraInfo;
        }

        [StructLayout(LayoutKind.Sequential)]
        private struct KEYBDINPUT
        {
            public short wVk;
            public short wScan;
            public int dwFlags;
            public int time;
            public IntPtr dwExtraInfo;
        }

        [StructLayout(LayoutKind.Sequential)]
        private struct HARDWAREINPUT
        {
            public int uMsg;
            public short wParamL;
            public short wParamH;
        }

        [StructLayout(LayoutKind.Explicit)]
        private struct INPUT
        {
            [FieldOffset(0)]
            public int type;
            [FieldOffset(4)]
            public MOUSEINPUT mi;
            [FieldOffset(4)]
            public KEYBDINPUT ki;
            [FieldOffset(4)]
            public HARDWAREINPUT hi;
        }


        // This function simulates a simple mouseclick at the current cursor position.
        public static uint Click(int x, int y)
        {
            int vscreenWidth = System.Windows.Forms.Screen.PrimaryScreen.Bounds.Width;
            int vscreenHeight = System.Windows.Forms.Screen.PrimaryScreen.Bounds.Height;
            int vscreenLeft = System.Windows.Forms.Screen.PrimaryScreen.Bounds.X;
            int vscreenTop = System.Windows.Forms.Screen.PrimaryScreen.Bounds.Y;

            // Absolute input requires that input is in 'normalized' coords - with the entire
            // desktop being (0,0)...(65535,65536). Need to convert input x,y coords to this
            // first.
            //
            // In this normalized world, any pixel on the screen corresponds to a block of values
            // of normalized coords - eg. on a 1024x768 screen,
            // y pixel 0 corresponds to range 0 to 85.333,
            // y pixel 1 corresponds to range 85.333 to 170.666,
            // y pixel 2 correpsonds to range 170.666 to 256 - and so on.
            // Doing basic scaling math - (x-top)*65536/Width - gets us the start of the range.
            // However, because int math is used, this can end up being rounded into the wrong
            // pixel. For example, if we wanted pixel 1, we'd get 85.333, but that comes out as
            // 85 as an int, which falls into pixel 0's range - and that's where the pointer goes.
            // To avoid this, we add on half-a-"screen pixel"'s worth of normalized coords - to
            // push us into the middle of any given pixel's range - that's the 65536/(Width*2)
            // part of the formula. So now pixel 1 maps to 85+42 = 127 - which is comfortably
            // in the middle of that pixel's block.
            // The key ting here is that unlike points in coordinate geometry, pixels take up
            // space, so are often better treated like rectangles - and if you want to target
            // a particular pixel, target its rectangle's midpoint, not its edge.
            x = ((x - vscreenLeft) * 65536) / vscreenWidth + 65536 / (vscreenWidth * 2);
            y = ((y - vscreenTop) * 65536) / vscreenHeight + 65536 / (vscreenHeight * 2);

            INPUT input_set = new INPUT();
            input_set.mi.dx = x;
            input_set.mi.dy = y;
            input_set.mi.mouseData = 0;
            input_set.mi.dwFlags = (int)(MOUSEEVENTF.ABSOLUTE | MOUSEEVENTF.MOVE);

            INPUT input_down = new INPUT();
            input_down.mi.dx = 0;
            input_down.mi.dy = 0;
            input_down.mi.mouseData = 0;
            input_down.mi.dwFlags = (int)MOUSEEVENTF.LEFTDOWN;

            INPUT input_up = input_down;
            input_up.mi.dwFlags = (int)MOUSEEVENTF.LEFTUP;

            INPUT[] input = { input_set, input_down, input_up };

            return SendInput(3, input, Marshal.SizeOf(input_set));
        }
    }

bejeweled_blitz_2So how does it work? It works fine – the program averages about 100K, I think it’s top score is 212,900, which is just a ridiculous score that I could never hope to get with my slow, pitiful human fingers.

It’s pretty fun to watch – the program just goes nuts, clicking away as quickly as possible – mouse pointer flying all about the screen, colors flashing and changing constantly.

I learned quite a bit from this little exercises, but mostly, I’m just happy I’ve exorcised my Bejeweled Blitz demon.

One Minute . . . GO!

Advertisements

Tagged: , , , , , , , , ,

§ 28 Responses to I cheat at Bejeweled Blitz

  • Secret Squirrel says:

    What would be cool is if you released a zip of the code for us all to try – while Ive got a top score of earer 350, Im kinda interested to try and work out some way to get the computer to work out better options for me..

    Anyone know a free c# source version of bejeweled?

    • mikevallotton says:

      While I thought about posting the source code, I didn’t for two reasons.

      1) The point of the post (and the project in general) had a lot more to do with finding creative ways to solve a problem than to beat Bejeweled. Screenscraping images, reading them into a usable structure, applying fairly intelligent algorithms, and sending the mouse clicks back to the game was the challenge for me. The fact that it was Bejeweled was somewhat incidental. I could have done this for any game – this is just the one that caught my eye.

      2) I’m happy to teach and help people learn. I’m not particularly interested in helping anyone cheat, however. There’s enough information there for you to write your own – check out what Charles Cook did – http://www.charlesrcook.com/archive/2010/09/05/creating-a-bejeweled-blitz-bot-in-c.aspx.

  • charles says:

    Interesting post. I created another c# bot for the game, thanks for the ideas and tips.

    http://www.charlesrcook.com/archive/2010/09/05/creating-a-bejeweled-blitz-bot-in-c.aspx

  • Mark Lindell says:

    Yeah, I made one also and it’s selling like pancakes! People love to cheat!

  • Thomas says:

    It’s amazing how many people wrote bots for Bejeweled Blitz.

    My bot gets over 700K and averages 200K to 300K.

    The key differences are:
    – to identify the gems, I don’t use any averaging. I just look at the center 9 pixels of the gem. Those center pixels are not altered by the background. So, a direct comparison of colors works.

    – the code thinks 4 moves ahead to build the most valuable formations.

    – The code automatically starts a new game. That way I can walk away from the computer and do something else, while it plays.

    You are totally ride exorcising the Bejeweled demon is a good thing. It’s such a time waster.

    • mikevallotton says:

      700K is really impressive – you must have spent a decent amount of time on it.

      Yeah, looking back at it now, I wouldn’t have identified the gems the same way. Sometimes you start down a path, and you stick with it just because it will get you there, even if it isn’t the most direct.

      I didn’t post any of my logic. I played around with solving from the top to the bottom, bottom to the top, left to right, multiple moves ahead, going for speed, going for 5 gems or 4 gems first, etc. I really just wanted to make it better than me (which wasn’t hard), and once I did that, I didn’t go much further.

      Mine automatically started a new game, too. I think it would be way to annoying otherwise.

      Either way, it was a fun exercise. I learned a bit about things that I don’t normally get to do in my day-to-day work.

      • Thomas says:

        For me, it was only a fun hack as well. I wondered, if it worked. Once it worked, I spent hours watching the game play itself like a mesmerized rabbit.

        The one thing that keeps making me wonder, if there is a possibility to get six in a row. The game officially only rewards for up to three in a row. Though, six should be possible with a very strategic robot:

        x2x
        x21
        11x
        x2x
        x23
        33xx4
        x244x
        x2x

        x – any kind of gem

        a) Complete the 4 series.
        b) Step (a) should shift the 1 and 3 series in place to explode
        c) Step (c) should complete series 2 with 6 gems.

  • Gary says:

    Hey Mike,

    what is board? a 2 dimensional array?
    and toX toY what are they?

    thanks,
    Gary

    • mikevallotton says:

      Hi Gary,

      Yes, board is just a two-dimensional array made up of the “Piece” class.

      toX(int) and toY(int) lets me translate a board position to a screen position. So the square that is in the 0,0 position on the board may be at 400px across and 180px down (just as an example).

      • Russell says:

        Ok, I don’t think I have ever had to write a 2 dimentional array that references like the way you have it. Closest thing I can think of is Piece[,] or board[,]. Can you send me a good example of that kind of array amd how it is referenced. I am learning a lot from this.

      • mikevallotton says:

        Here is a pretty straightforward multi-dimensional array overview, Russell. I learned a lot when I did it, too. Let me know if you need any help.

      • Russell says:

        Actually I could not understand what this kind of 2-dimensional array declare a array to a new contructor:
        Example: board[i, j] = new Piece();

        I would assume the board is actually a class on it’s own and has some sort of public board[,] board = new board[8,8]; I can’t seem to find any examples on how to do it the way you do it. Not even my C# reference book shows how to do that. Plus I have a few other things I don’t understand, but I got the rest of it though.

      • mikevallotton says:

        I see. That line of code creates a new Piece class and sets a reference to it in the Board array. So the Board array will actually contain references to 64 different Piece instances.

        The Board array is actually declared like this:
        Piece[,] Board = new Piece[8,8];

        However, all of the individual items within the array will be set to null until you do something like this:
        Board[0,0] = new Piece();

      • Russell says:

        Thanks for clearing that up! I usually declare the array with initializers such as { {1,1}, {1,2}, {1,3}, etc }; Not used to seeing the new type intializer being used, but it makes complete sense. Wish I would have realized that sooner. Learned another thing today thanks again!

  • Gary says:

    Hi Mike, thanks for that. I have created the toX and toY sucessfully and have been able to draw the board like you. However my colors have variations. Say its a green gem, then 1 green gem on my board may be a light green but the next green gem may be a darker green. I know that an average color is returned using the avg function. Should these colors be the same, what am I missing? or does it make any difference?

    Thanks,
    Gary.

    • mikevallotton says:

      I found that there was a lot of variation in the color that I picked up using the method I posted. This is why I had to average the colors, compare them to known values, use the random(ish) sampling, etc.

      I don’t think that I would necessarily do it the same way again. Someone had posted that if you just pick up the 9 pixels in the center of each piece, they will always be consistent. I don’t know if that’s accurate, but you may want to explore that as a simpler option for identifying the pieces.

  • Gary says:

    Thanks Mike.

  • Gary says:

    yes the 9 pixel idea works 🙂

  • needhelp says:

    i don’t understand your concept since i don’t know VBA. Mind if you explain further how to identify both normal and special gems?

    my bot can only identify color gems by matching the centre pixels so i’m having troubles. thanks

    • mikevallotton says:

      I don’t know VBA, either. 🙂

      The game has changed a bit since I wrote the bot, which would obviously change how to identify the gems.

      When I did it, I kind of averaged the color of the whole gem to make a guess as to which gem it was. I used a pseudo random function so that each time I tried to identify the gem, I would get a slightly different result. That way, if I misidentified one, I could guess again on a subsequent play.

      If you’re just matching the center pixel, you will probably have problems. I’d suggest trying to match the center 9 or 25 pixels, which will give you more fidelity to work with.

  • JACKSON GETRAD BUHCK says:

    Let me tell you now, Its a lot more satisfying to be averaging around 800K every week WITHOUT BOTS OR CHEATS then it is using them. Practice makes perfect, don’t be a sore loser!

  • Lyrcisit says:

    Maybe a bit late here but im just learning coding and thought this was a fun way (most of the things I will be doing revolve around botting boring daily tasks at work) Only bit im stuck on getting this to work is toX toY. not sure what these are or hos to go about creating them? read above its to do with translating board position to screen position but bit confused as to what you mean. Can ya help me out as I would really like to see this working now ive spent the time getting the rest of it compiled and working!.

    • mikevallotton says:

      Most of everything I do revolves around boring daily tasks at work, too.

      The idea is to translate the board position to the screen position so that you can make the mouse click the correct pixel. So if the left of the board is at 100px, and you want to click on the 4th column, and the columns are each 20px wide, then toX() should return 180px.

      Does that help?

Leave a Reply

Fill in your details below or click an icon to log in:

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

What’s this?

You are currently reading I cheat at Bejeweled Blitz at Mike Vallotton's Blog.

meta

%d bloggers like this: