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.

Advertisements

Permalink Leave a Comment

Week 1, Thursday

March 26, 2009 at 7:05 pm (Java, Week 1) (, , , , , , , )

I FINALLY got my head wrapped around the minimax algorithm today. I went more slowly and stepped away more often, and I finally have an unbeatable computer in Java. This took me a heck of a lot longer than it did in Ruby, but I think it was reasonable considering my limited Java knowledge, a new algorithm, and new knowledge about things to avoid.

My last step was kind of an interesting one: I rewrote (not refactored) part of the algorithm in a way that was easy for me to understand, very slowly and deliberately, and it came out right! Imagine that…

// before:
bestScore = Math.max(bestScore, -minimax(child, depth - 1, otherPlayer);

// after:
otherPlayerScore = minimax(child, depth - 1, otherPlayer);
maxOtherPlayerScore = Math.max(otherPlayerScore, maxOtherPlayerScore);
bestScore = -maxOtherPlayerScore;

If you take a minute or two to look through this, you’ll see that the two versions are not equivalent. Although I could break the second version down into one line, I don’t trust myself to be able to understand it as well later on, so I’m leaving it explicitly spelled out this way.

I demoed the game for Micah and indeed, it seemed to work correctly. Micah had me draw up a UML diagram of the code in its current state, with all the methods and dependencies that I knew about, and Micah pointed out violations of the SOLID principles for object-oriented class design. I’d read about them but needed a refresher and deeper understanding, so he walked me through each of the principles, asking me what they were and where I saw problems. I didn’t catch them all of, course, but I was glad I at least had a cursory introduction already. I made sure that I understood the kinds of situations in which a principle violation would bite me.

For those unfamilar with these, you can learn more on Ward Cunningham’s wiki (he’s the inventor of the wiki, among other distinctions):

I just read about these for the first time a few months ago (they’re detailed in Agile Software Development: Principles, Practices, and Patterns by Robert C. Martin (Micah’s dad, incidentally). I had more Dependency Inversion violations than anything (though certainly not as many as my Ruby version had), but there were some Open-Closed problems as well.

My next step, which seems realistic for an Agile/XP project, is to put a GUI on top of my Java code. I haven’t done anything to speak of with Swing, so I spent a couple of hours this afternoon investigating the API and figuring out sizing, colors, and other things I’m going to need to draw the board.

I have an Open-Closed violation or two around my GameDisplay class, which means that my design is going to have to change around that point in order to substitute the GUI for my command-line output. The good news is that I HAVE a display class in the first place; my Ruby display code was coupled to the rest of the game in several places.

Permalink Leave a Comment

Week 1, Tuesday

March 24, 2009 at 8:05 pm (Java, Week 1) (, , , , , , )

Okay, so today was harder. I had a flurry of discoveries this morning as I got my questions answered from some work I did last night on the Tic-Tac-Toe game, and then I hit a big roadblock this afternoon. Lesson learned: interrupt when necessary and get questions answered rather than stalling on my own if I’m really stuck.

My problem this afternoon was the Minimax algorithm. I’d looked at it briefly before, after I had finished the Ruby version of the game, but didn’t understand it and gave up. Since the algorithm is part of this assignment, I buckled down and read several descriptions of the algorithm that I found on Google. I thought I understood the mechanics of the algorithm, decision tree and all, but two things were eluding me: the implementation of the decision tree and the computation of the value of a given board position. Eventually I got close (basically translating the pseudocode to Java and Tic-Tac-Toe), but I really did need Micah to help me think through my implementation line by line in order to see a big mistake I was making with recursion. It’s not there yet, but I think it’s close.

Which leads me to the other (maybe bigger) afternoon problem: in my efforts to understand and implement the algorithm, I had neglected TDD and avoided writing tests. Because it was hard => because I’m not good enough at it yet. Well, Micah’s given me some ideas to begin with: sending in board positions where there is a definite best move, and testing that the algorithm spits out the right one, along with some other lower-level things. He did say it’s hard to test, so that makes me feel a little better, but I have to get to the point where I’m not intimidated by TDD. I caught myself jumping ahead to the implementation several times today (and once in front of Micah IN THE TEST CODE – whoops!).

On to the more complete wins of the day, from the morning: I came in with a couple of questions about how to test specific points in the project. Let’s say I have Game, Player, and Board classes. Now, I needed to test that when I told a Player to make a move, the Player would pick a move, and then populate the Board with that move. I was struggling to find a way to verify that the Player had told the Board to populate. It turned out that I just needed a mock Board object. I had an inkling that this is something mocks would be good for, because I remembered a bit of RSpec (ONLY a bit) where an object might have “should_receive(:populate)” to do something similar. I was really glad to come across this problem, because nearly every time I’d read about mocks and stubs in the past I’d come away feeling dumb and defeated. This was simple, though: I just derived a MockBoard class from Board, added a field on the class (private boolean populateCalled = false;), and overrode the populate() method, setting populateCalled = true inside it (and calling super.populate() when I needed the real behavior later).

I’m still incredibly slow in IntelliJ, so I was happy to pick up a few IDEAs about it today. Get it? Get it? I know, I’m incorrigible… Shift-F6 is the Rename refactoring. Wow, is that going to save a lot of time! I think you have to be hovering on the declaration, but the program goes through and changes the name of that method/field/variable/class, in a pretty smart way.

The biggest IntelliJ thing I’m excited to know about is Live Templates, which right now seems exactly like TextMate snippets. Micah wrote me a quick one that does the skeleton of a JUnit test on a tab-complete of “test”, and I can see how this is going to come in handy. I always liked scripting up and using snippets to blast out often-used ERB template things for Rails, and I’m definitely going to start paying more attention to the things that I end up typing over and over so that I can give those to IntelliJ to do.

Permalink 3 Comments