Week 5, Wednesday

April 22, 2009 at 10:37 pm (Java, Week 5) (, , , , , , )

From yesterday morning to this afternoon I improved my understanding of the Hashtable a lot. Micah found a flaw in my hashing yesterday, but when I started to blog about it last night, I found I didn’t really understand my problem, so I held off until tonight.

I was doing this sort of thing:

private Board board;
private static Hashtable boardScores = new Hashtable();
// ... (calculating the score for a particular board position)
boardScores.put(board, calculatedBoardScore);

I had hashCode() and equals() defined on my Board class according to the squares filled on the board, but I wasn’t REALLY following the way that hashing works in Java (actually, in any language). My big flaw was in not realizing that while a given board position would always resolve to a given hashCode(), there’s no guarantee that it will be distinct from the hashCodes for other positions! So “XOX XOO X” (for a 3×3 board) might go in the same “bucket” as “OOXX OO X”, for all I know. Well, that’s not necessarily a problem when I store the positions in the Hashtable; the problem is getting them back out.

From Hashtable’s get() method:

if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}

And the key WAS a Board, which has equals() defined as having every square equal. So a hash lookup with Boards as keys really should work? No, actually! (This is where I got lost trying to work things out in my head last night) It’s true that the board is the key and 2 boards with different square configurations will not compare as true with equals(), but the keys are not really different boards. In fact, they were all references to the same board, which means that when if I get a hashCode() collision (which will most likely happen with the millions of boards that I’m hashing), there will be confusion, because the second part of the conditional in the Hashtable code above will always be true.

So anyway, Micah helped me to refactor to use new String objects as the Hashtable keys instead, which fixed the logic flaw, but took up even more memory and crashed the program at a lower depth search (running out of room in the heap). This all took place yesterday. Today I came in with the idea that I’d refactor things, write some more tests, and clean up some dependencies. I think I accomplished those goals, starting with a lot of refactoring (using IntelliJ’s built-in refactoring tools). I tried out a new-to-me tool called JDepend to check out problems with my packages, and I tracked down a few dependency cycles (that’s a BAD Java programmer. No dependency cycles. Nnnoo!). JDepend is an open source project by Mike Clark of Advanced Rails Recipes fame. It was pretty easy to use, and while class-level detail could’ve been nice, it was easy enough to do a “Find in Path” to track down the naughty dependencies. Here’s how it went:

  1. downloaded from Github (http://github.com/clarkware/jdepend)
  2. ran ant task to build it
  3. $ java jdepend.swingui.JDepend ~/IdeaProjects/TicTacToe/ (there’s also a textui and xmlui version)
  4. too many packages shown for me to process well, so I added jdepend.properties in home directory to ignore junit, hamcrest, java
  5. ran again, started doing searches for dependencies in my packages and breaking them where necessary to avoid the cycles

Now my package dependencies were as follows:

  • main => depends on baseGame, boards, players, and ui
  • ui => depends on baseGame, boards, and players
  • players => depends on baseGame and boards
  • boards => depends on baseGame
  • baseGame => no other project dependencies

Before my refactorings, every single one had a dependency cycle (icky).

And then we came to the afternoon, when I finally got fed up enough with the memory constraints of the Hashtable to open a JDBC connection and write the millions of positions and scores to a database. This was new to me, but the MySQL website was helpful enough that it wasn’t a big deal to do. One false start (only 8 levels deep), ~10 million database records, 16 levels deep, and ~6 hours of writes and indexing later, my computer player can play a 4×4 board more quickly, but in exactly the same way as he did at 6 levels deep with the (corrected) Hashtable. Which was not that badly, except at the opening. He makes smart moves to avoid a loss (on both sides) at the end, but at the beginning he thinks all the positions are equivalent. My impression in thinking as deeply as I can about this for a week or so is that on a 4×4 board, it is extremely easy to force a tie. So easy that a player would need to make at least two bad moves in order to lose. There’s no forcing a win after one misstep like on a 3×3 board. I think in order to get the computer to play like a human, I’d have to use an evaluation function that added value for 2-in-a-rows and 3-in-a-rows, which I’d have to do anyway in a more complicated game like chess, since there are so many more possibilities to consider there.

At any rate, Micah decreed that today was my last day on Java Tic-Tac-Toe, and so I’m moving on to Limelight tomorrow. Micah’s actually the author of Limelight; it’s a framework based on Java and JRuby that allows you to write rich GUI applications in Ruby. Pretty cool stuff; I’ve looked at some here and there since arriving in Illinois, and Eric and I looked at some this afternoon. I don’t know yet whether I’ll be doing some more Tic-Tac-Toe or something else, but I’m looking forward to digging into the new technology.

Whew, how’s that for an epic send-off for Java Tic-Tac-Toe? Apparently that’s what happens when you write 10 millions records to a database!

Advertisements

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: