/bj2bot

Bejeweled 2 Bot for Xbox 360 Achievements

http://www.brains-N-brawn.com/bj2bot 6/4/2007 casey chesnut

comment(s) 

NOTE Travis Feirtag has written an article about the custom hardware used for this project : Xdotnet360 - Controlling the Xbox360 with .NET

Introduction

er, um ... hello, my name is casey, and i'm addicted to Xbox 360 achievements. but i also love to write code, so i decided to combine the two ... which has recently become popular :

not a hardware person, so this bot will be mostly software based. the goal was to have it target one of the most difficult games for achievements, and have it actually play the game. achieve360points.com has the games listed by achievement difficulty. at the time, Hexic and Bejeweled 2 were in the most difficult category and looked like the easiest to program against. Top360Tag (recently closed) had Bejeweled 2 ranked as the most difficult Xbox Live Arcade game, so thats the one i picked ... not to mention i had the least amount of points in it. plus the achievements for Bejeweled 2 are ridiculously time consuming. figured it would take less time to write a bot to indirectly get the achievements, than to directly get the achievements. so this article will explain how i wrote a bot to play Bejeweled 2 to earn Xbox 360 achievements. NOTE after starting, i found out that somebody else had already written a Bejeweled 2 Bot for the PC. a PC version would be slightly less tricky, because input/output would be easier. so when Live Anywhere (for Windows) gets rolling ... it'll probably be a little easier to bot those PC versions for achievements.

the following image shows the bot application. the upper-left image is a preview video of the game board (in debug mode). the mid-left image is the current image sampled from the video that is being image processed. the main image to the right shows the game board state, with debug info rendered on top of the game board. the list box to the bottom-left shows the list of moves that are available. the small image to the right of the 'list of moves' shows the result game board if the selected move is made (used for debugging). to have the bot start playing, all you have to do is select the game mode from the drop-down list (e.g. Endless mode), and then press the 'start loop' button.

 

the video below shows the bot playing 'Hyper' mode. the video is real-time (i.e. has not been sped up). Hyper mode redraws the board quicker than other modes.

360 Video Output >> Bot Video Input

 

the pic above shows a high level overview of the hardware setup for the bot to get input and output. the first step was to get the video output from the game into the bot. i used the HD cable that came with the premium 360. the component cable is connected to the TV (for viewing), while the composite cable is connected to the Pinnacle Studio Moviebox Plus (~$125). with the 360 HD cable set to standard-def, it will output video to both cables (composite and component). the Studio Moviebox was then connected to my computer through USB. NOTE my Xbox display settings are set to standard-def normal (not widescreen).

then the bot uses DirectShow .NET to grab screen captures of the game. it creates a filter graph and adds the Studio Moviebox as the 'Video Input Device' filter. it then adds a 'Video Mixing Renderer 9' as the output filter. its bound to a PictureBox on my Windows Forms application so that i can see a preview video of what is happening (if i dont have the TV on too). the VMR9 is real nice, because it has an interface which allows you to grab a screen capture of the currently playing video. once i've got the image, then i can do basic image processing on it to figure out the current board state. NOTE the screen cap grabbed is only 352x240.

Bot Output >> 360 Controller Input

next step was to figure out how the bot could control the 360. wanted to come up with a solution that could be purchased off the shelf. it's kind of ugly, and expensive, but this is what i came up with. first, i bought an XCM XFPS (~$80). this can convert keyboard commands into Xbox 360 controller commands. then i bought the Mule key wedge (~$200). the key wedge has a DLL that i can pInvoke using C# sending string commands that will be converted to keyboard commands. and i used a USB-to-serial cable to connect the computer to the key wedge. so the bot will pInvoke the DLL which sends commands to the key wedge (through the USB-to-serial adapter), then the key wedge will send keyboard commands to the XCM XFPS, and the XCM XFPS will send wired controller commands to the Xbox 360. this ended up working OK, and i used it to earn 8 of the 12 achievements (did not get Action, MultiMode, Hyper, and Finity with the key wedge). the problem is it wasnt real fast or entirely reliable. the problem seemed to be the communication between the key wedge and the XCM XFPS. if i used the XCM XFPS with a real keyboard, then i was able to make fast and reliable moves. as fast as i could click the keyboard. and if i hooked the key wedge up to another computer, then i could send keyboard commands ridiculously fast and reliably. but when i hooked them together, the commands were executed slower than i could physically do, and they weren't 100% reliable. this really hurts when you are trying to beat Action mode. NOTE i tried a bunch of different things to get this to work better : different cables, sending the commands differently, adding pauses, etc... no luck there

but my friend Travis Feirtag at feirtech.com cooked up a hardware solution for me : Xdotnet360 - Controlling the Xbox360 with .NET. basically, he programmed a microcontroller to control an Xbox 360 arcade stick controller. so the bot will send the microcontroller commands over a serial cable, and the microcontroller will trigger the correct button presses on the arcade stick, which will send the commands to the Xbox 360. this ended up allowing me send the commands very quickly and reliably. much quicker than i could physically do. since the button presses are so reliable, it even allows the bot to move diagonally, which is near impossible to do using the D-pad on a 360 controller. didnt get this controller til the very end, so it might be kind of interesting to run it against Endless now, and see how fast it can get through the boards. but for Endless mode, a bot that never sleeps really doesnt care if it moves slow or fast ... it just needs time. NOTE the pic below shows the basic processing loop the bot uses.

 

Game Board State

now that we can get input and send output, its time to make the bot. it starts out by knowing where the game board begins and end. the board is always in the same spot, except for Puzzle/Cognito modes. so i just hardcoded those positions. based on the size of the board and knowing the number of rows/cols, then it knows where each tile is.

first, it figures out which tile is targeted. it does this by only checking the upper-left corner pixels for each tile. if its just the game board background, then the pixels are dark, and if its the target, then the pixels are bright.

next, it tries to figure out the color of each gem for each tile. it does this by checking the pixels for each tile. it ignores the dark background tiles, as well as the edges to ignore the target. it also ignores the center of the gem, which will be white for power gems. the rest of the pixels are added up to find the average color, as well as the size of the gem. the average color is then looked up in a hardcoded color table, to find the closest gem color it maps too. if its too close to tell, then the size of the gem is also used to determine. an alternate technique would be to use shape. the pic below shows all the different gem types.

 

that works ok, but not great. too make it work better, i used a little Bejeweled 2 trick to make the board easier to read. if you press and hold the left and right triggers and the left and right buttons at the same time, and finally press the A button on the 360 controller, then the gems will render differently. this turns off alot of the graphical enhancements and makes the game board much easier to process.

 

the image above shows the normal game board, and the image below shows the alternate version ... which is easier to perform image processing on. NOTE a friend pointed out that the alternate board could have used the black outlines for gem recognition.

that works great for all the gems, except for white and hyper. my logic for that is not perfect, so it sometimes screws up and thinks a white gem is a hyper gem or a hyper gem is a white gem. if i had to improve this, then i would take 2 screen shots and compare them, which would allow me to see that the hyper gem is moving. or i could do some texture checking to tell that the color is not constant for the hyper gem.

for power gems, it just checks to see if the center of the gem is white. this works great for all gems, except for the white ones ... which are already white. so i dont have a way to find white power gems. if i really wanted this badly, then i would also do some sort of motion detection.

there is also some logic in there to mark tiles as being empty, when the tiles have been cleared and gems have not fallen to fill in the tiles yet.

for the advanced modes, there are also rocks and bombs. i dont have any specific logic to find either of these. the bombs are even trickier because they have a # on them which is the # of moves until the bomb blows up. i'd have to do some OCR to figure out that number, but i didnt want to put that much work into this, so i ignored it.

so its not perfect, but at least 90+% correct at figuring out the game board state. this ends up being 'good enough' because if it screws up, it can just try again. the image below shows a board state capture with debug information rendered on top of it. NOTE the 'Purple' text in red, which signifies the gem is a power gem.

 

Finding Moves

now that the game board state is known, the bot finds all the possible moves. first, it goes to each Hyper gem and figures out which move would remove the most gems from the board. then it goes to each tile, and sees what would happen if it were moved Up,Down,Left,Right. it makes the move in memory, and then looks for matches of length 5 (create a Hyper gem), 4 (create a Power gem), or 3. it will also mark these moves as Power moves, meaning the match contains a Power gem, so it will explode and take out surrounding tiles.

then each potential move is executed in memory. e.g. the potential Hyper move will wipe out an entire color, and a Power move will wipe out the surrounding tiles. matches of 5 or 4 will create a Hyper or Power gem as well as clearing some times. matches of 3 will clear those tiles. this is recursive so that combos occur. after the moves are executed, then the remaining tiles are dropped into place. the other tiles are left blank, because i have no way of knowing what gems will fall in. then it counts the # of blank tiles and that records the amount of damage that the potential move will do. finally, the resulting board is also processed to find moves. then this count is added to the potential move so that we know how many moves we might have after executing the move.

Choosing Moves

now that we have all the moves and have an idea of what they might do, we can go about picking which move to execute. this depends on what game mode you are playing.

Endless - this is the easiest because it always gives you a move. i started out and just had it pick moves randomly. then, i had it make Hyper gems first, Power gems second, use Hyper gems, and then do matches of 3. this got me the 8x cascade, 10K power gems, and 1K hyper gem achievements. it started out at just 10 minutes per level, and then that time got closer to an hour as it increased in levels. this was pretty slow, so i wanted to speed things up to beat Action mode, and then apply those speed ups to Endless. regardless, bots don't sleep, so i could just let it run forever. anyway, it took forever to get this achievement. this one alone made it worth my time to write the bot. NOTE there are a bunch of complaints on the boards about people losing their Endless saved games, so i put the Xbox 360 on an UPS and disabled the Xbox 360 auto shut down after 6 hours.

Finity - this is Endless mode with Rocks and Bombs and a timer. plus the timer only increases when an explosion occurs. so it uses the same game loop as Action, but chooses moves that will explode.

Classic - for this mode, i started out making Hyper gems and then save them as backups, and performing the top most moves. this ended up with the dreaded 'no more moves'. so i switched and had it make the moves that would result in the most subsequent moves ... to keep the board 'move rich'. this had the unexpected benefit of making tons of Hyper gems. let this run overnight and it ended up at level 46 before i stopped it. i'm assuming this would just keep running.

Twilight - this mode is like Classic, but it alternates the direction in which tiles fall from (top or bottom). didn't change the Classic logic at all, and the bot was still able to get the achievement. i also assume that the bot would just keep going in this mode.

Action - started out by having this do the lowest moves first. the moves were slow, so i switched to having it execute the nearest move. after that, i had it execute the most damaging moves (e.g. combos). this showed promise, but the moves were still too slow and unreliable. for the time-based modes (Action, Hyper, Finity), i had to wait for Travis's hardware controller, which allows for fast and reliable movements. then the logic was to go after combos, or moves at the bottom of the board to possibly unlock combos falling in above. this uses a different game loop than Classic, Twilight, Original. it will attempt to figure out the next move as soon as it finishes a move. it tries to choose moves that will still be there after its previous move. so sometimes it will not execute a move because a random piece fell in that did an unexpected combo, or the foreshadowing game logic was incorrect, or it will try to make the move before the previous move is done falling into place ... so the move wont be executed, etc...

Hyper - this is similar to Action. it can be beat by going for Combos or the most damaging moves.

Puzzle - got the Puzzle achievement a while ago by manually hinting my way through ... lame

Cognito - Cognito is Puzzle mode without hints. there is a FAQ that you can use to get this achievement. ended up only partially automating this. converted part of the txt based FAQ into XML, so that the bot could parse it. then i've got some logic to have the bot lookup the current puzzle in the list of puzzles. it generally finds the exact puzzle, but sometimes a couple match (e.g. it does not do character recognition for the # of moves on a bomb, so it cant tell those 2 boards apart), so it adds those to a DropDownList and the user can pick the exact puzzle. then the user clicks a button on the bot, and the bot will execute the moves one by one. the user can interact here because there is the occasional 'off by one' bug in the FAQ. where a row or column will be 'off by one'. anyway, it steers the user to the right place, and they can undo the bad move, and execute the proper one if needed. with a little cleanup to the FAQ, and more complete board recognition, this could be fully automated.

the image below shows the app being used to solve puzzles. it has populated the DropDownList with the list of potential game boards. in this instance, it found the exact match, even though the board has been mirrored. a user could then repeatedly press the 'puzzle step' button to execute each move to solve the puzzle.

 

Original - is just like Classic, in that you can get 'no more moves'. also, it doesnt have power or hyper gems. so for picking moves it uses the same logic as Classic to keep the board 'move rich', it just never makes any power or hyper gems. didn't have the bot play this mode because there is no achievement for it.

Limitations

its not perfect. first, it might get the board state wrong. its main problem is confusing hyper gems with white gems, and vice versa. the quick hack to get around this was to put a bit of randomness in there, for choosing which is which. a better solution would be to check the texture of the gem. i.e. the white gem would have a constant texture, while the hyper would have more variability (changing from color to color between pixels). else i could do some motion detection. nor can it determine white power gems. second, explosions, text overlays, and falling gems might cause the board state to be incorrect. in the timed-mode, it tries to figure out what move to make as soon as it executes the last move. so the board might still be redrawing. there is extra crap on the board at that time, and it might guess that a gem is a different color than what it really is. third, falling gems might change the forecasted board state. so it might try to execute a move that is no longer there. fourth, the previous move might still be occurring. so it might try to make the next move, even though the previous move is still not done, so the current move will not occur. fifth, forecasting board state is not exact. there are some combinations in which it is impossible to tell what the next board state will be. i.e. if two gems of the same color fall in to make a power gem, out of those 2 gems, where will the power gem be created? sixth, its not big blue. it does forecast how move-rich the resulting board will be, and how much damage a move will do (e.g. combos), but it doesnt do anything like 'if i make this move, then that will set me up to make a hyper gem' with the following move. seventh, it keeps state when transitioning to the next board. sometimes when a new board is started, it tries to execute a move that would have been on the last board. eighth, there are bugs in my code. sometimes i watch it try and make some bizarre move, or it sits for a while ... and i have no clue what its 'thinking'. the pic below shows a portion of a board that is redrawing and has text overlaid.

 

Achievements

it ended up getting all the achievements ... sort of. Bejeweled has a bug when multi-mode is unlocked. for me, it unlocked Hyper (by beating Action), which also awards the MultiMode achievement. so i was awarded the MultiMode achievement, but the Action achievement did not register. so i really ended up with 190 of 200 points. had it beat Action mode again, but it still did not award it. cant really complain, since my own program has plenty of bugs in it. if i had done this manually though ... that would have really pissed me off.

a quick glance at the forums show some people getting the achievements in 175 to 360+ hours. as far as my own time, i spent substantially less. my coding and debug time was mainly spread out over a month. would estimate that i spent 50 to 60 hours coding and debugging. there were alot of times where it was left unattended running on its own. some of these times it would get stuck, and i'd come back to see an exception had occurred. a good chunk of that time was spent screwing around trying to get the keyboard wedge to work quickly and reliably. i.e. wasted time. then i let it sit for a month while Travis finished the hardware controller. after getting the controller, it took about 4 hours of tweaking to finish it off. the image below shows that it got all the achievements, minus Action mode because of the MultiMode bug

 

Leaderboards

couldnt care less. it would be easy to set the bot up and just have it run non-stop to take over the leaderboards for Endless, Classic, Original, and Twilight. for the time-based ones (Action, Hyper, Finity), i'd actually have to write some more code to improve its board state logic and increase its speed. not sure how to get high scores on Cognito? anyway, i was only after the achievements and not in taking over the leaderboards. regardless, here are the bots standings :

Cheating?

recently, MS started banning people with mod Xbox 360s. i read many of the comments and found this very interesting. first off, my Xbox 360 is not mod'd. i got most of the achievements using off-the-shelf components. only used a modified controller for the last 3 achievements. as far as i know, nobody has been banned for using a modified controller, and they have no way of detecting it other than from reading this article. or possibly seeing that a controller is being pressed faster than humanly possible. which would be tough to do with the third party controllers that have turbo buttons on them.

my expectation was that most of the comments would be about people getting banned for playing pirated games, but it turns out that most of the comments were about cheaters. it seems that people used to be able to cheat at Halo 2 using a mod, and now it looks like there is a different exploit for Gears Of War. the community seemed pretty unanimous that they wanted the cheaters out of their online games.

Bejeweled 2 isnt an online game, but there are online leaderboards. and it's definitely possible to write similar bots to play games which are online. so i'd like to know ...

Video

the following videos show the bot in action. there are clips from different game modes, because the bot plays differently according to the game mode. the main changes are for the game loop (conservative vs aggressive) and the strategy for choosing moves.

Classic [no more moves] (1) (2) conservative loop, keeps the board 'move rich'

Endless aggressive loop, do the most damage

Action [timed] (1-6) (6-9) aggressive loop, go for combos. NOTE these vids are not from the same game ... had problems with the recordings. NOTE that this shows that the bot should have attained the 'Action Mode' achievement for passing level 8

Twilight [no more moves] conservative loop, keep the board 'move rich'

Finity [timed] aggressive loop, go for explosions

Hyper [timed] aggressive loop, go for damage

Conclusion

this article details the making of a Bejeweled 2 bot to beat the most difficult Xbox Live Arcade game for achievements. the time invested in writing the bot ended up being at least a third of the time to manually get the achievements. some things i discovered in the process :

granted, its a bit anti-climatic since a bug in BJ2 awarding achievements limited the bot to 190 points, instead of the full 200. of course i could have just rented Madden or College Hoops 2K6 to get more than 200 points within a couple hours ... but then i wouldn't have learned anything ...

finally, Thanks to Travis for making the hardware so that it could complete the timed-modes.

Source

the code is only useful for developers interested in basic image processing, because some of the hardcoded values might have to be tweaked based on your setup. plus, the code is currently tied to the custom hardware, which isnt publicly available; so the control mechanism would have to be changed. if you want to run it, you probably need to use the same video hardware i used, and change your 360 settings to be the same.

Updates

none planned

Future

probably something 'surface computing'-like. later