Tic Tac Toe: A game for Kindle

The Amazon Kindle isn't much of a gaming platform. In fact, it's just a static HTML viewer. The Kindle e-book format, which is the same as the Mobi e-book format, is basically just a subset of HTML with a few extensions. Published e-books are produced by converting HTML into the e-book format (if you convert from a .doc or .pdf file, they are converted to HTML first).

This doesn't mean that interactive games can't be developed in an e-book format. I developed a Tic Tac Toe (aka Noughts and Crosses) game for the Kindle by writing code that pumps out an HTML file containing every playable board. The board exists as a set of 9 images - the empty squares are links to a page with a board that contains the current player's mark on that square. The version I made first (Two Player Tic Tac Toe at the Kindle Store) is a two player game - the first player makes a move and then hands it off to the 2nd player. The e-book is over 5000 pages long and allows every possible move in a Tic Tac Toe game. It was easy to develop, and the code is explained below.


There is at least one other e-book game available in the Kindle store, The Towers of Hanoi Puzzle. This puzzle works on a similar principle - each page contains links that take you to a page containing the next game state.

The code

The source code for an early version of the Two Player Tic Tac Toe (TPTTT) HTML generator is available here. It's C#, which isn't quite as sexy as Haskell or Clojure or whatever is popular on proggit nowadays, but it worked for me.

Board State Representation

A game board is represented by a Board class that has one instance member - a 9 element array of ints that holds the state for each square on the board. A zero means the square is empty, -1 means an X, -2 means an O, and any positive integer is the index into an array of Boards that contains the board state for that move.

The board array is just that - an array. Many people will use a tree structure for doing things like this, but I chose a flat array with each board indexed by an integer representing its state. Every possible game state can be represented by a ternary (base-3) integer - each digit is a 0, 1, or 2. In my code an empty square zero, X is 1, and O is 2. The most significant trit of the ternary number is in the top-left square. Here's a graphic to explain how it works:



The 9 digit numbers in each of the squares are the ternary representation of what the board will look like if the current player chooses that square. That number is also the index of that board in the array of boards. In the picture, the first board has an index of zero and each of the empty spaces are links to new boards where X places his mark there. If X chooses the middle square, the 2nd board is 000010000 in ternary, 81 decimal, or 0x51 hex. Now each empty square has a link to the board where O chooses that spot. If O picks the lower right corner, that board is index 000010002 ternary (83 decimal, 0x53 hex).

The maximum possible board states is 3⁹, or 19683, but there are many fewer possible boards in a game of Tic Tac Toe. For example, the highest index possible here - with a board full of O's - just won't happen in a game. Each board will always have a number of X's that is either equal to the number of O's or one more than that. A game will never continue once it's been won. The total number of possible individual boards for the two player game is 5474. This number of boards is able to represent all 255,168 possible playable games. It's possible to further trim the number of boards needed by not continuing game states that will always end in a tie, but the code posted here doesn't do that.

Generating the HTML

There are two phases to the execution of the code - first all of the board states are created, then the HTML representation is printed.

Each game board is generated in the NextTurn method which calls itself recursively. It's simply a loop that goes through each of the 9 spaces on the board looking for an empty space. If it finds one (not containing an X, a O, or an address) it makes a move there. When a move is made, the resulting board state is stored in the boards array based on its index. There is a bit of an optimization in the code where it won't re-create a board state that already exists. It's kind of pointless to optimize code like this that's designed to run once and finishes in under a second, but I couldn't handle the fact that it was so inefficient and my willpower is weak.

When NextTurn determines that there's a tie or a winner on a given board, it returns. Once all of the game boards have been calculated, the next phase of the program loops through the entire array of boards looking for non-null entries at each index. When it finds one, the board is printed as HTML that looks like this:

<a name="0"></a>
<table border=1><tr><td><a href="#1">_</a></td><td><a href="#3">_</a></td><td><a href="#9">_</a></td></tr><br/>
<tr><td><a href="#1b">_</a></td><td><a href="#51">_</a></td><td><a href="#f3">_</a></td></tr><br/>
<tr><td><a href="#2d9">_</a></td><td><a href="#88b">_</a></td><td><a href="#19a1">_</a></td></tr><br/>
</table><br>

Every board has an anchor tag who's name is the index of the board (it's not actually legal for a name token to start with a digit, but the Kindle and most browsers don't seem to mind). Each empty entry contains a link to the board that contains that move. A board that contains a winner has no links and displays a helpful message indicating that someone one.

The code posted here prints the results as HTML tables, and empty spaces are underlines. The 'production' code that generates the 'real' e-book uses a set of square images to represent the X's, O's, and empty spaces.

You can check out the full HTML here. It's about 1.3mb. It works best in a web browser if you shrink the window down so you can only see the immediate board you're on and the space below it.

The e-book

Once the HTML was generating properly, a lot of time was spent making it look good on the Kindle. I replaced the HTML tables with sets of images. I inserted pagebreaks using a special HTML tag that exists for this purpose. It took a while to tweak the images to get them to line up properly and to allow for easy movement with the Kindle's controller. The size was pretty huge (550KB) but I managed to shrink it down to around 480KB (still huge) with some creativity - mostly by removing unneeded HTML tags.

Single Player Tic Tac Toe

I also developed a single player version of Tic Tac Toe that allows you to play against "the computer". This version of the e-book contains 16 random starting games. The player picks one of the games which takes them to a page where either they can make the first move or the computer has already made the first move. The computer moves are picked using the NegaMax algorithm, with a random element added to let the player win occasionally.

Because the number of boards doesn't need to account all possible moves of two players - just one, the number of boards required to represent a game is much smaller than the two player game. If the computer goes first, there are an average of around 200 boards needed. When the player goes first, around 400 are needed. The code that generates the single player TTT e-book produces 16 different games where either the user goes first or the computer goes first. The first player is split up 50/50, and the computer's starting point is always random (instead of the best spot - the middle square).

If you want to try out a single player version of e-book Tic Tac Toe, download this demo. I tested it on Kindle and Mobipocket Reader, but it may work on other readers. The full version is available from the Kindle Store here.

Update: This concept was also explored by Thomas Jansen at http://blog.beef.de/2008/01/16/html-game/

Amazon DTP preview on Kindle

If you've written an e-book and uploaded to Amazon's DTP site, you might have noticed that there's no way to download a file to preview on your Kindle before publishing. There is a preview button that shows a simulation, but this isn't good enough in most cases. It is possible to download your converted e-book in AZW format using this trick (this works with Firefox, directions might be slightly different with IE or Safari):

1. First, go to the Upload & Preview page for the title you're publishing
2. Right click the “Download HTML” link and copy the link location
3. Paste the link into another browser window
4. Replace the “zip” with “azw” in the “file_type” part of the URL, then hit Enter
5. Firefox will tell you to save a .zip file – go ahead and save it
6. Rename this file so it has a .azw ending, then copy it to your Kindle
7. You should now see your title on your Kindle!

Hothead Archive format (Part 1)

For those of you who only come here to read about Android stuff, don't worry. I'm sure Jon will be posting about his new game soon.

On the Greenhouse forums, someone brought up the topic of making mods for the Penny Arcade game. At that point, someone had already used some FMOD tools to extract and re-package the sound files for the game, but the rest of the game data was packed into ".hha" files. Since they didn't seem to be any known format, I started trying to decode the .HHA ("Hothead Archive", I'm assuming) format, with some help from Jon. I got distracted before I finished (weddings are so time-consuming), and by the time I got back from vacation, someone else had released source code to extract all files. I lost interest pretty quickly after that.

On a whim, I decided to pick up my little project and do something useful with it. Part 1 (this article) is about my first round of research. Part 2 will be about adding support to PhysicsFS (I have a few bugs to work out before I release that part). I might write a part 3 about actually doing something with the "Rain-slick Precipice of Darkness" files, or creating an archive, or something.

Info/header

Blocks represent DWORDs (aka 32-bit integers):

0                1               2               3
+----------------+---------------+---------------+--------------+
|    MAGIC       |    VERSION    | FILENAMES SZ  | FILE ENTRIES |
+----------------+---------------+---------------+--------------+

Like most file formats, HHA starts with a "magic" number. This is 0xAC2FF34F, when read as little-endian, like all the numbers in the format. I'm just assuming the next DWORD is a version number, which is 0x00010000 in all the files I've seen. It probably represents something like "0.1.0.0", but I'm not sure. The next number is the size of the filenames list that follows (again, in LE). The last number in the header is the number of files contained in the archive.

Filename list

After the header is a null-delimited list of file and directory names. It's meant to be referenced by an offset that is stored with the file's other metadata (better explanation in the next section).

File metadata

Following the list of filenames is an array of 6-integer groups of file metadata, best represented by this structure:

//file metadata structure
struct hha_file_info {
 int dir;       //directory name (offset into filename list)
 int name;      //file (offset into filename list)
 int compress;  //compression level (0-2)
 int offset;    //offset from start of file
 int full_len;  //uncompressed file size
 int len;       //file size in archive
};

(some day, this blog will have syntax highlighting)

To get the directory name, add the first number to the starting address of the filenames list. Read from there until you get to a null, like any C string. Do the same for the file name.

The compression level can be 0 (no compression), 1 (deflate/zlib), or 2 (LZMA). The offset determines where the file data begins. The next two numbers are the uncompressed and compressed sizes of the file (these numbers will, of course, be identical for uncompressed files).

Before the above-mentioned vacation and loss of interest, I had yet to actually try to figure out compression types 1 & 2. Credit goes to Maks Verver [ maksverver (at) geocities.com ] for figuring that out.

Source code or it didn't happen

I've posted my original code on our Google code project, though I don't recommend actually using it. It will only extract uncompressed files from the archive. Maks Verver posted a better version that supports the two compression types and can also create archives. For now, I would use his version instead, if you just want to play with your Penny Arcade game files.

Credits/disclaimer

Just to be clear, the author (me) does NOT work for Hothead Games, Greenhouse Interactive, Penny Arcade, etc. Any/all trademarks mentioned in this article belong to one of them, and the author is not associated or endorsed in any way.

Also, buy their games. If you're a Linux geek/gamer like me, you know there are few games that are released with native Linux clients (and OS X, if you're in to that sort of thing). Of course, they're a lot of fun, too.

CellFinder released!

CellFinder has been posted to the Android Market, so if you have a T-Mobile G1, check it out in the Applications/Tools section. The source code is available at the Codetastrophe Google Code project page. There's also some documentation. Some of the new features since the initial post:

• Improved format for data display at top of screen
• Friendler direction/distance display with configurable units
• Configurable location refresh time
• Full-screen map option ("Show cell" data in the Settings menu)
• A few bug fixes

There are a few features I'm planning on adding in the near future:

• Auto update notification
• Keep database of cell tower locations and display those on the map
• GPS satellite locations (see this post)
• Signal strength is some unit other than "asu"
• Redirect user to settings page if GPS or Network location service is disabled
• Help page to show full documentation for all features

So anyways, I was pretty surprised how fast CellFinder showed up on the Marketplace and how soon people starting e-mailing me. I got a lot of positive comments and a few negative ones too. I uploaded it to the Marketplace around 10pm last night, and as of 8:43AM, my stats are:

• 110 reviews, 4/5 stars
• 2235 total installs
• 1823 active installs (81%)

Writing a cross-platform ELF binary

Just for fun (actually, I was bored at work) I came up with the crazy idea of writing a cross-platform ELF binary that I could run on Linux, FreeBSD (without the Linux compatibility module), and potentially other Unix. I'm sure at the time I justified it by thinking that it would somehow be easier than writing portable C that I just compiled on different platforms, though in retrospect I was just looking for an excuse to do something a bit weird.

My early experiments with making portable ELF files weren't going so well. Trying to run a Linux executable on FreeBSD (without Linux compat) was harder than I thought. The first problem is the ABI version in the ELF header. The first byte of the padding in the ELF header is interpreted as an ABI version under FreeBSD. Linux just sets it to 0 (and ignores any other value you set it to), but FreeBSD recognizes:

> brandelf -l
known ELF types are: FreeBSD(9) Linux(3) Solaris(6) SVR4(0)

...and refuses to run an ELF type of 0. Supposedly, setting to 3 works if you have the Linux compat library installed, but I was avoiding that.

Before I gave up, I got the idea that if I could strip the program down to the basics, I'd have a better chance of making it work. I found a great article on making tiny ELF files, which reduced the problem down to:

• Define _start instead of main
• Make the exit system call (without calling _exit)

It turns out that an even bigger problem than the ELF header is making system calls cross-platform. FreeBSD system calls use a different calling convention: arguments are passed in the stack instead of registers like on Linux. Fortunately, I'm only making one system call (exit). Setting the registers AND pushing values on to the stack will work on both platforms! Doing something complicated that requires more system calls could get messy rather quickly, though.

The final piece is just doing something useful. I found an article describing using the SLDT instruction on x86 to detect virtualization. In summary, if both the high and low bytes returned by the SLDT instruction are nonzero, there's a high probability you're running in a VM. There are lots of other ways to detect virtualization, but SLDT is easy.

The code I wrote is probably non-optimal (I haven't written much x86 assembly), but at least is easy enough to read. Anyway, the "main" assembly part (not including ELF headers, etc) of the program is as follows:

_start:
    mov     eax, 1      ; system call 1 (exit)
    mov     ebx, 0      ; default return value of 0
    sldt    edx         ; SLDT to detect VMWare
    cmp     dl, 0       ; if first byte is 0
    je      .L2         ; jump to end (return 0)
    cmp     dh, 0       ; if second byte is 0
    je      .L2         ; jump to end (return 0)
    mov     ebx, 2      ; otherwise, set return value of 2
.L2:
    push    ebx         ; push return value arg onto stack
    push    eax         ; push syscall number onto stack
    int     0x80        ; syscall interrupt

This gives a return value of 2 if the machine is running in a VM, otherwise 0 (not using 1 because that might be the return value if it doesn't execute properly). It should run on any UNIX platform if the ABI in the ELF header is set correctly, though I've only tested on Linux and FreeBSD. Full assembly on our Google Code project (direct download link here). Since I was following the tiny ELF file article, the assembly includes the ELF header and is 116 bytes when assembled. Build with nasm -f bin -o vmware_small vmware_small.asm. It runs on Linux as-is, but you need to run brandelf -t FreeBSD vmware_small on FreeBSD to set the ABI byte to 9 and make it run there (afterwords, it can still run on Linux!).