Week 4, Tuesday

April 14, 2009 at 5:54 pm (Java, Week 4) (, , , )

Back into Tic-Tac-Toe today, and things turned out much better than I’d hoped. Jake Scruggs of Obtiva is in the office as part of the 8th Light – Obtiva Craftsman Swap, and he helped me to think through some of my 3-D Tic-Tac-Toe woes. It was good to have another set of eyes on the code, and another voice of reason encouraging me to write my tests first.

As one of my speed strategies, to get this thing to actually run in a reasonable amount of time, I was working on putting board positions in a Hashtable, but we quickly realized that we’re not going to have enough memory for all the possible board positions. Because of the exponential growth of possible boards (with the number of positions), we’re looking at numbers in the trillions, and I was running out of memory around 600,000. So Jake had two insights that helped me focus on what really needed to be done: I could (1) make rules for my computer player that made him move properly for longer-term strategy, and (2) use a disk-based dictionary to cache the values of various board positions (like a flat text file or a full-fledged database). Before we could leap into coding up either of the solutions, however, Micah analyzed the situation and saw that I might be better off working on a 2-dimensional 4×4 board.

His reasoning was that since we had found a flaw in the 3x3x3 game (picking the center of the cube guarantees a win – try it!), it was only really good for learning, and I’d probably learn more with a slightly smaller problem anyway. So, I spent the rest of the afternoon coding up a 4×4 board, which was fairly easy now that I have abstracted the concept of a board away. Then I won some memory savings by having one reusable board (accompanied by a stack of moves that gets pushed and popped as I traverse the game tree), so now the only optimization I have left from Micah’s list is the biggie: caching board positions and scores. This one has me stumped right now, since the score will only be applicable on a per-player basis, but I’m sure a little away time will give me some focus when I come back to it.

I had a couple of people interested in seeing the source code, so I’m happy to direct people to the Git repository for my code. This should give you a good idea of where my Java knowledge is at the moment; I’m sure I’ll shudder about it a few years down the road!

I also got to meet Robert Martin (whose books I’ve read and blogged about) and James Grenning, who were in the office today to work with Doug on a Slim implementation (for Fitnesse). Exciting!

Advertisements

2 Comments

  1. Caleb Cornman said,

    Sounds like you are having a great time there. I recently did a tic-tac-toe game in Ruby and mine is up at github.com/calebcornman/tictactoe/ I haven’t looked at Java in a few years but I’ll check yours out and probably steal a few ideas. 🙂

    • trptcolin said,

      Caleb – very cool. Yeah, Tic-Tac-Toe is a lot of fun – but after working on this, I can see why computers that can win at chess are a big deal!!!

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

%d bloggers like this: