Bejeweled autopilot

The idea behind the Bejeweled game is as following:
An average game status looks like this:

The player is allowed to switch between any two neighboring gems in order to create a series of three or more gems of the same color. If the player does so, the gems are destroyed, points are given, gems are falling down to fill the empty spaces, and new gems are coming from the top to fill the vacuum. The problem is that the player has just about one minute to destroy as many gems as possible, and it’s hard to find series of gems that quick.
What I did to solve this problem was to write a small Python script to capture the screen, find the best next move and simulate mouse clicks to execute it. One of the problems I faced while writing the script was identifying the kinds of gems, while the bustards kept on moving, rotating n’ glowing in different kinds of effects that usually inform the player about special bonuses. I tried to scan a 4x4 pixels square in the middle of any square, to get a color value out of this small square, and to compare it against a table I made manually in order to decide which gem it is.
I found out, that in many cases bots scripts alter the game to change all the graphics to something more OCR friendly. But I didn’t want to do that, as I’m trying to perfect the technique of writing a bot, and not to mix the two game cheating vectors. Therefore, I didn’t want to put any patches on the game, just writing a bot.
The next problem I faced was Python itself, as I found out that it’s quite slow to scan an image or to compare two images with the Python Image Library (PIL). Though, it is possible that I’m miss-using the library. Please, I would like to hear any ideas on how this part could be done better from Python, without extending Python with a custom C library.
One lessen I learnt the hard way during writing of this very script, was that it’s very important to find the time to write a code for finding the location of the game on the screen, so in case I scroll the page down a little, or just open the bookmarks tools bar, it won’t be using the hard coded position of the game and miss figure where the gems are.
Even thought, I successfully set myself on the top score among all of my friends, but not world wide best just yet. I found out that many fine tunings on the scripts, such as what strategy to prefer, weather to aim for bonuses first, try to destroy a longest chain of gems at once, or save bonuses for later, have immense effects on scoring. Please, I would love to hear from the readers of this blog about any ideas on how to improve the script, or how you would write one in case you had to.

The script is aviable on my SVN at https://xp-dev.com/svn/Cheats

Cheers,
Assaf

Wonder Cheat 3

Recently I had a major nostalgic emotional burst which took me all the way to the Sega Master System ™ I had in my childhood. One of the games I remember the most from this 22 years old console is the Wonder Boy III, the Dragon’s Curse. So I fired up the Meka emulator and downloaded the ROM, and sat down for few hours of unlimited fun.

During the search for the ROM I found out that there was another version of the game with slightly better graphics for the TurboGrafx-16 console (AKA PC-Engine) which is called the Dragon’s Curse.

For the readers who never heard of WB3 or the Sega Master System, I shall explain, in short, the game’s look n’ feel. The game is some kind of a combination of RPG with a platforming action game. You need to get different kinds of swords, shields and armors by either finding them in treasure chests throughout the game, or buying them in shops found in the city. Besides the gear, the player has to collect gold, potions, magics and power ups. The game has about 6 levels that the player has to finish, while at the end of each one there is a boss that has to be destroyed. When a boss is beaten, the character in the game transforms into some kind of a new animal-human creature that possesses a special ability that helps him get to the next level. The characters are Hu-man, Lizard-man (Can shoot fire), Mouse-man (Very short, and able to climb some walls), Piranha-man (Can swim), Lion-man (Can punch up), Hawk-man (Can fly).

Bosses:

The part that I find interesting about this game is the way save games were implemented in time before Flash memory. During the game there was a place in town where the player could get a 14 characters long code that if entered in the main menu, would take him back to the same status as he was in the time of getting the code.

Meaning these 14 characters encode the full status of the game, including amount of Gold, Lives, Potions, Gear and more. The characters are either numbers 0 to 9, or capital ABC, excluding few characters such as I, O & Q, for the reason that they look too much like 1 and O, which could be quite confusing. Besides that, not every combination of characters is valid, meaning there must be some kind of a checksum. I remember that many years ago, every time I got bored playing the game I was trying to brute-force codes, with very little success. I was always very curious about this mechanism, and I had a belief that somewhere, there is some kind of a very special code that would turn the game upside down.
During the last week I decided to finally cope with this old craving, and finally reverse engineer the secret behind this coding system. First I had to find out which CPU is used by the Sega Master System to know how to load the game in IDA. Wikipedia mentioned, rightfully, that the Z80 is the main CPU of the console, and loading the ROM file into address zero seemed to work just fine. Second, I had to find the relevant code, so I searched the Internet for some special codes that might lead me to the right place. I found out that there is one very special code that is WE5T 0NE 0000 000, which is the name of the company who made the game. This special code could not possible encode a game status, so it must get a special treatment in the code. Searching for the string (without the spaces) through the entire file took me to the following code:

Xrefs took me to:

From reversing I found that every character tributes exactly five bits to the data, that comes to be total of 70 bits (5 * 14) which turn into total of 9 bytes of data. Two bits of the 9 bytes are index to a xoring table that is then xored to the 9 bytes. After the xoring, all the bytes are added together to form a checksum that is compared to the first 7 bits (which are not used in the addition). If the first 7 bits match, the code is valid and is passed to another function that sets the game state.
I’ve written a full functional code decoder / encoder in Python, and is available for download from the following link:
http://xp-dev.com/svn/Cheats/


Links:
For more information about Wonder Boy III and The Draogon’s Curse follow the links below.
http://www.geocities.jp/monsterworld2/Wonderboy_Land.htm
http://hg101.kontek.net/wonderboy/wonderboy.htm
http://retro.ign.com/articles/930/930245p3.html
I would like to thank them for the pictures I took from these sites without asking for permission, hope it’s ok.

Cheers,
Assaf.

P.S.
The Dragon’s Curse has something different in the coding system, I would have to reverse it too. Does anyone know how to reverse the PC-Engine’s ROMs?