Week 5, Weekend

April 26, 2009 at 8:20 pm (Reading, Watching, Week 5) (, , , , , , , )

I’m constantly amazed by the amount of information available online to help people improve and learn. To my wife’s chagrin, I spent several hours watching video lectures by Hal Abelson and Gerald Jay Sussman (from a 1986 course presentation at Hewlett Packard) and by Douglas Crockford (at Yahoo, I believe).

These aren’t directly related to my assignments for the apprenticeship, but I’m learning a lot. The Abelson/Sussman lectures (also on Google Video) are based on their book, The Structure and Interpretation of Computer Programs (SICP), which I understand was the introductory course at MIT for many years. I recommend the 256k mp4 versions if you’re downloading – the 64k are too hard to make out, and the high-res ones are huge! The language, Scheme, has got some pretty cool features, but to be blunt, the parentheses are pretty ugly. The really interesting part of this language, so far, is that functions are first-class objects, which can be saved into variables, passed into other functions, etc. This isn’t a completely foreign concept to me, as Ruby has closures like Procs and lambdas, but I think it’s the area of Ruby where I feel the least comfortable. Another pretty crazy thing is the way control structures like loops must work: recursion (a function might call itself with a modified index). I feel like I’d have had an easier time beginning to understand the minimax algorithm if I’d watched these videos first – the tree structure in particular was clearly explained, in one example, as it related to recursion.

I’d seen Caleb Cornman‘s tweets about the Crockford videos (they’re also available for download from the YUI Theater site), and realized (for the umpteenth time) that even though I’ve written a decent amount of Javascript in my day, I know basically jack about how the language works. I’ve generally just let the Rails helpers, JQuery, or Prototype to do the dirty work for me, hacking in the rest as needed. So that can work, as it does for many others, but trust me when I say that you don’t want to be debugging ugly Javascript. I’m a little weirded out that I just happened to be learning about lambdas and Lisp, and Crockford mentions several times that how Javascript is the first language with lambdas to really hit the mainstream. Javascript has no concept of classes, only objects! I’m surprised, but intrigued to learn a lot more about the subject. Currently debating whether to start with Crockford’s Javascript: The Good Parts (recommended highly by Jim Suchy) and David Flanagan’s Javascript: The Definitive Guide (the only book Crockford recommended other than his own). The local library has the 4th edition of the Flanagan book – I wonder how much has changed in the most recent (5th) edition… Anyone familiar with these and have advice?

I spent some time during and after each of the videos fooling around with practicing Scheme and Javascript, in Emacs and Firebug (a Firefox add-on), respectively. I’m starting to get the hang of Emacs, which is encouraging. I’d need to do a lot more reading and practicing to get as good with it as I am with Vim, but I feel like I should at least have a rudimentary knowledge of how to get around in Emacs, since it’s one of the most-used editors on Unix machines (and has such strong Lisp integration).

I also did a lot of reading, from Refactoring by Martin Fowler et al., and a book I’m reviewing for the Pragmatic Programmers. I won’t say much about the review book, but it’s very good so far, and I think it’ll turn out wonderfully. They were looking for someone who wasn’t an expert, and as I told Micah, that’s me!

Refactoring is so much more readable than I’d imagined. I had always thought of it in the same category as the Gang of Four Design Patterns book, which I flipped through once at a bookstore and found it to be far beyond my understanding. I think at this point it’d be easier, but Refactoring is extremely clear and easy to read. I wish I’d read it sooner, because it describes a lot of the things I’ve done to clean up my Tic-Tac-Toe (and to make changes to it as they came up). The automated tools in IntelliJ made the process easier, of course, but I’m also discovering that some of my bigger changes could have been made much easier by applying the steps in the refactorings catalog.

It’s always a good sign when you’re excited to get back to work and do some coding, but I’m wondering if I should be doing more actual coding at home. I may get into some Limelight Tic-Tac-Toe tonight – I think that things should fall into place more quickly now that at least some of the game logic is hooked up between Java and Ruby.

Advertisements

Permalink 2 Comments

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!

Permalink Leave a Comment

Week 5, Tuesday

April 21, 2009 at 9:26 pm (Java, Week 5) (, , , , , , , , )

Eric and I spent the morning making some styling tweaks to the Rails application, and I moved back to Tic-Tac-Toe in the afternoon. I got the board score caching to work almost immediately, or so I thought. Micah sat down with me to help me with my Ant build, which had been broken since I split the project up into packages. The fix there turned out to be easy (with the right knowledge): I needed to add JUnit to the compile classpath. For some reason I had it in the classpath for the <junit> element for running the actual tests, but not in the compile.

So then we took a look at my caching mechanism, which was taking up the whole heap and throwing errors at 6 levels deep in the game tree. Micah helped me to increase the heap size to 512MB, which got us to 9 or 10 levels deep, but we still eventually took up the whole heap again. We spent some time with a profiler tracking down the objects being created, and of course it was the hashed objects (~ 6 million of them) taking up all the memory. We worked for awhile to decrease the memory we were using, but we didn’t end up making it any more levels deep. At this point, the 4×4 computer player still makes some weird moves near the start of the game, but he gets smarter towards the end and avoids losses.

Micah noticed that my caching didn’t have tests (cringe), so that was my next assignment. Because my minimax method was so big and complicated, I kind of went to town with the Extract Method refactoring and eventually figured out a way to get some tests written on the caching part. Along the way, I discovered that JUnit doesn’t allow you to test private methods, and got some “Extract Class” knowledge dropped on me by Doug, who said that if I had a private method that wasn’t already covered by tests on my public methods, maybe those private methods really belonged somewhere else, as public methods on another class! For now, I’m just changing the method I wanted to test into a public method.

I like the looks of this class a lot better now that it has smaller methods – it’s a lot more readable. I think I picked some decent names, like writeScoreToCache(), getCachedScore(), getValueToOtherPlayer(), finalScore(), calculateBestScore(), etc. There is still a lot to be done for this program to look like something out of one of these books I’ve been reading, but it’s getting closer. And I’m getting a lot better at seeing what the differences are, which I think is really positive.

Permalink 1 Comment

Week 4, Weekend

April 19, 2009 at 6:44 pm (Week 4) (, , , )

I got a lot of reading done over the weekend: finished up Clean Code by Robert Martin (with chapters by other Object Mentors as well), which I’d been working on for a couple months or so now. Great book; I highly recommend it. I ended up finishing it late Saturday night, and then felt a strong urge to do some coding. So I took a look through some open-source project I’d contributed to in the past, mostly just playing around, and finally ended up spending a few hours doing some bug fixes on the Rails app Eric and I are working on. Bug fixes are so much more satisfying when you write tests to accompany them. This way, you feel confident that you’re not going to see that bug again, and you also get a chance to go back into the code and refactor if needed. Refactoring wasn’t much needed in this case, but I looked!

And speaking of Refactoring, I started reading that book (by Martin Fowler) last night as well. I’d been putting it off since I felt better about my abilities “in the small” than with larger-scale design decisions, but the introduction makes me realize that small improvements are going to lead to larger design improvements over time, so I’m excited about that. I certainly have a lot of room for improvement and learning on a small scale as well!

After hearing Eric Smith and Corey Haines tweet back and forth a little bit about SICP, I had to investigate. Turns out “SICP” is Structure and Interpretation of Computer Programs, a computer science textbook using Scheme (a LISP dialect), which I’d looked into when I first started getting interested in programming but which went way over my head at the time. Inspired, I watched the first course lecture (by Hal Abelson) on Google Video, read the first section of SICP, and played around with Scheme on my laptop (re-learning Emacs navigation along the way).

I’ve learned a lot this weekend, and I’m looking forward to getting back into Java a bit this week, along with Rails and whatever else is in store!

Permalink Leave a Comment

Week 2, Thursday

April 2, 2009 at 6:49 pm (Java, Week 2) (, , , , , , , )

Software design was my main focus today – I spent some time creating an updated UML class diagram of my Tic-Tac-Toe game. By creating a Swing-based GUI for the game, I had been forced to make some abstractions in the View/Controller area, and a lot of SOLID principle violations got fixed in that process. However, once I had drawn the UML up on the whiteboard, I saw several things that I knew Micah would point out, so I spent some time cleaning up before I had him look at it.

For instance, my ConsoleView and SwingView classes had dependencies on my PlayerFactory implementation, which was a violation of the Dependency Inversion Principle (DIP). Now, just to be clear, especially for those who haven’t already read Uncle Bob’s (Robert C. Martin’s) books and articles, programmers don’t follow these principles just because they exist – there are clear reasons to adhere in specific situations (and I think by extension, in general wherever possible). My problem here was that if I want to write a new PlayerFactory, which creates Players that have faster algorithms or which pick moves randomly, then I’ll be stuck in the situation of having to go down into all the views and change code there.

I’ll be a bit more specific to make this clearer. My PlayerFactory implementation had an enum full of things like Computer_V_Human, Human_V_Human, etc., to which the views had to have access in order to parse the names and display the game type choices to the console or GUI. So then I couldn’t change a field in PlayerFactory without needing to verify that it’s OK with the view. But PlayerFactory shouldn’t have to worry about that! I refactored PlayerFactory and the Views, adding a method gameTypeToString() on PlayerFactory, so that now the Views are telling the PlayerFactory to do something, rather than pulling out and parsing enum members, which felt kind of magical (in a bad way). At any rate, the final step was to extract an interface out of my implementation of the PlayerFactory, so that now the Views could just refer to the interface and not the implementation. The Dependency Inversion Principle says you depend on abstractions, not implementations or details. Especially when you have an idea that those details are going to change…

Which brings me to my next big assignment: I still have a significant number of DIP violations with dependencies on my Board class, which means that it will be hard to change it (it’s rigid) and I’ll break a lot of stuff when I do change it (it’s fragile). So what part of the application would you guess that Micah wants me to change? Indeed, now I need to create the option and implementation to play 3-dimensional Tic-Tac-Toe. There are 2 things I foresee happening: (1) lots of pain when changing the Board, and (2) lots of changes in other places. I know the minimax algorithm in particular is going to take a lot longer to run – I’m going to be traversing a tree with a LOT more levels: 27 vs. 9. That might not sound like a lot, but the number of nodes grows exponentially. There are 2^9 (512) nodes right now at the start of the game, but now there will be 2^27 (134,217,728) – OUCH! I may be off by one on those exponents, but you can see the problem… And I can see that I’m going to need to use some of the speed strategies that I read about when I was researching the minimax algorithm.

Permalink Leave a Comment

Week 1, Wednesday

March 25, 2009 at 8:03 pm (Java, Week 1) (, , , , , )

We worked from a client site today, where Jim and Eric S. generally work. They had an iteration meeting this morning, so I was there to observe. I’m told this one was really abnormal, as the new feature demo was only a few minutes long and it was around one computer rather than a conference room: one of the customers was on a tight schedule and had actually already signed off on some other stories from the iteration.

Each time Micah sits down with me and I try to explain my way through something, I realize how differently I need to approach my coding. Here’s the conversation that ends up happening (perhaps a bit paraphrased and exaggerated for my point):

Me: So, one of my tests is failing but the others are all passing. Here’s the code…
Micah: OK, so walk me through it.
Me: Well, this thing depends on that one and needs to call on it for later on when it updates the other thing. And before, when I was working on that first thing, I had a weird problem with the other thing so I changed the implementation of that first thing to be the new thing’s gobbledygookandtrailingoff… [you get the idea]
Micah: Wait. Go back to the beginning. Let’s think through each step.

I must slow down and be more methodical, especially when I’m having a problem. And even more especially when I’m having a problem understanding why I’m having the problem. The whiteboard was VERY helpful in solidifying my understanding of the minimax algorithm itself, especially as I applied terms from the implementation to it. Recursion can be really difficult for me to understand when I don’t go step by step (or call by call).

My ComputerPlayer is getting better: it wins when it can win immediately, but it gets much dumber after the first move. I actually thought it was finished at one point, but alas, my tests weren’t extensive enough and I was able to beat it easily. I banged my head against the wall (figuratively, of course) for awhile today trying to get it working – I think I needed to step away for awhile. Jim suggested 25 minutes of continuous coding/debugging, and then a 5-minute break (the Pomodoro technique). I’ll give that a shot tomorrow.

There was a lot of refactoring today. Some of it was to sanitize some nasty stuff I’d written, but some was out of necessity. For instance, I had the Board responsible for deciding the next move possibilities, but it should have been the Player, since the move itself depends on the player’s mark (X or O). This meant I had to bring a method or two up out of my Board class into the Player before I could move on with the algorithm. I also learned a couple more refactorings in IntelliJ that will save a lot of time: Introduce Variable and Extract Method. I had to spend a little time verifying for myself that the Extract Method change wasn’t going to break anything, so I need to crack the cover of the Martin Fowler Refactoring book sometime soon. It’s in my reading queue piling up from Amazon, but there are several others as well.

I spent a little time with Java generics and Lists in the morning – I’m used to Ruby where an array resizes for you automatically, so I figured that a new Java array, even one with space for 9 allocated, would have length 0, as it does in Ruby. But of course int[] possibleMoves = new int[9] is just an array of nine ZEROS. At any rate, I’m certain this is a much better way to learn a language than trying to learn all the syntax cold before hopping into the code, but it’s frustrating sometimes. I have a good friend living in Berlin who knew only a few phrases in German like “Where is the bathroom?” when he moved there a few years back, but of course he was fluent within a year or so. I imagine it’s similar here, except that I don’t have to speak in Java to buy a sandwich. Yet…

Permalink Leave a Comment