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
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.
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!