Close
Glad You're Ready. Let's Get Started!

Let us know how we can contact you.

Thank you!

We'll respond shortly.

LABS
The simplest thing that could possibly work in Tetris

At Pivotal we practice a form of Agile software development descended from the original Extreme Programming (XP) created by Kent Beck et al. XP codifies many of our core practices including pair programming, test-driven development, iteration planning, and stand-up. XP also has a very strong emphasis on flat hierarchies and frequent communication. Because of its values and engineering guidelines, XP allows for high-quality software to be produced and shipped extremely quickly. XP values working software over extensive specifications or documentation, so-called “big design up front.” This is so the product can be iterated on quickly, both in the business and the technical sense.

Opinions differ as to which of XP’s practices is the most valuable in accomplishing this. One of my personal favorites is simplicity and clarity in code and design. Simplicity is a difficult thing to pin down. Occam’s Razor, one of the earliest and most popular statements of the parsimony principle, suggests we form a hypothesis with the least “plurality,” or the fewest assumptions or entities possible. Since then people have rephrased this idea as “keep it simple, stupid” (KISS) or probably the most elegant, “less is more.” My favorite statement is St. Exupéry’s:

“It seems that perfection is reached not when there is nothing left to add, but when there is nothing left to take away.”

XP offers us its own guidance on simplicity and writing simple code. It has two simply stated tenets on simplicity: “do the simplest thing which can possibly work,” and the related “you ain’t gonna need it” (YAGNI). Ward Cunningham, another father of XP, explains the first concept as:

“What’s possible? What is the simplest thing we could say in code, so that we’ll be talking about something that’s on the screen, instead of something that’s ill-formed in our mind. Once we get something on the screen, we can look at it. If it needs to be more, we can make it more.”

YAGNI is an answer to the temptation to prematurely optimize: “Always implement things when you actually need them, never when you just foresee that you need them.” Yet, XP also tells us we should “refactor mercilessly,” and Cunningham has long been a proponent of object-oriented design patterns. There is some tension there and it depends on the project and situation.

Clojure creator Rich Hickey tells us in his 2011 talk that the easiest thing isn’t always the most simple, and the simplest design isn’t always immediately apparent. This is a veiled jab at object-oriented programming in favor of functional languages. Obviously object orientation leads to many more “entities” than functional design, assuming entities are objects. Yet most programmers will tell you that objected-oriented design is “easier” than functional design. Perhaps this is merely because they are more familiar with OOP from past experience. However, many would also argue that functional code is quite complex. Code is communication, so a good design is easily parsed (by humans) and understood. That might mean favoring OOP conventions over a more functional style. In Ruby we have a number of functional-inspired techniques that allow for some middle ground to follow the principle of least astonishment.

Let’s look at a case study. Some months ago, I worked on a Ruby implementation of Tetris in my spare time. My goal was to have a working implementation in the shortest time possible, to win a bet that a working game of Tetris would take more than a few days. I settled on Gosu, a C++ 2D game development library that provides graphics, sound, and many other features in a pure Ruby wrapper. The game is on Github. After bundling, you should be able to run it with ‘ruby game_window.rb,’ and try prefacing that with bundle exec if it doesn’t work right away. You will need to have a number of dependencies installed, see the Gosu documentation for more.

I assume the reader is familiar with the rules of Tetris. One of the first things I did was create the shapes for the pieces. Tetris has 7 pieces. All somewhat resemble letters: I the 4×1 stick, J and its mirror L, S and its mirror Z, O the square box, and T. I knew in my head what these pieces looked like, and could easily draw them. So, I created a relative X,Y coordinate system and a draw method. For example, the I piece was [[0,0],[1,0],[2,0],[3,0]].

Now that I had pieces, I needed rotation. I knew what the rotation should look like, but I was not entirely sure how to implement the concept in code. Without researching the question much, I decided to hard-code my values. This seems “dirty” or “ugly,” but it is in keeping with Cunningham’s urging to put something on the screen now and iterate on it later. It was the simplest thing that could possibly provide a working implementation of the game. I also knew that there was a bounded number of possible pieces and rotations in the game, and no need to generalize further. Furthermore, I wasn’t working with a team, didn’t need to maintain the code going forward, and had to win a bet. So I created a large case statement of hashes that looked like this:

def shape
   case @type
   when :I
      {0 => [[1,0],[2,0],[3,0]],
       1 => [[0,-1],[0,-2],[0,-3]],
       2 => [[-1,0],[-2,0],[-3,0]],
       3 => [[0,1],[0,2],[0,3]] }

The pieces, when generated, would randomly assign themselves a type from the list, and a rotation starting at 0. The current_shape method would call to the shape hash method with the current rotation to get the current shape. When the player pressed up, the game would increment the rotation by 1 or reset it back to 0 if it had reached 3. This is not a bad “simplest thing” solution because it is fairly easy to understand what it is doing, and hopefully easy to refactor it into something a bit more elegant. You can see this early commit here. Feel free to checkout that version of the code and run it as well (git checkout 04d590d114cdd564f54491b77339c6ac24bb1693). It will generate a random Tetris piece and then crash. The next commit, ebfcc34e461d30321edf7293f8dc3de95fa2af2b, has semi-functional rotation using the hash method.

I was able to finish the Tetris game with this hard-coded implementation and left it alone for some months. However, in the back of my head, the hard-coded solution was bothering me, and I wanted to implement it using a rotation matrix, a concept I dimly recalled from math class.

Good tests are the most important requirement for refactoring confidently, since they provide a known basis that your refactor preserved the correct behavior and did not break anything. I had been sloppy the first time around and hadn’t written a test for the method that contained the massive case statement, which later became a class method with a type parameter. So here it is:

it "I" do
   Piece.shape(:I)[0].should == [[1,0],[2,0],[3,0]]
   Piece.shape(:I)[1].should == [[0,-1],[0,-2],[0,-3]]
   Piece.shape(:I)[2].should == [[-1,0],[-2,0],[-3,0]]
   Piece.shape(:I)[3].should == [[0,1],[0,2],[0,3]]
end

This was green, as you’ll note it is quite similar to the implementation above. For my refactor I wanted to change the interface of the shape method to have 2 parameters instead of returning a hash, so my test would look like

Piece.shape(:I,0).should == [[1,0],[2,0],[3,0]]

but would otherwise remain the same. The case statement would remain, but would only return the 0 rotation, after which I would perform some sort of matrix transformation.

Wikipedia tells us that the rotation matrix for 90 degrees counterclockwise is:

rotation matrix

After some Googling I settled on an implementation like this:

rotation.times do
   shape = shape.map{|arr|(Matrix[arr] * Matrix[[0,-1],[1,0]]).to_a.flatten}
end

Although the tests passed for the I, J, and L shapes, the other piece tests did not. The O shape actually moved around its axis of rotation even though in my hard-coded version, I had it remain stationary. I had also previously suspected a bug in the implementation of the S or Z shapes, since they seemed to be roughly the same, even though they should have been mirror images. More than likely my known “true” values were simply off. Playing the game confirmed that the rotation was functional and acted as intended. You can see the commit at GitHub.

I was further able to refactor away the rotation variable, generate the shape at object initialize time, and apply the rotation upon receiving player input (commit). This optimizes the number of rotations. Previously, each rotation would start at 0 and progress to a maximum of 3. So if I rotated from 2 to 3, the old code would actually calculate the interim steps 0 to 1 and 1 to 2 as well. The new stateful version will only perform one matrix transformation per rotation.

This change also allowed me to rewrite the test in a much more object-oriented and end-to-end way, as follows:

let(:piece) { Piece.new(window, grid, type) }
describe "I" do
   let(:type) { :I }
      it "rotates" do
         piece.shape.should == [[1,0],[2,0],[3,0]]
         piece.rotate
         piece.shape.should == [[0,-1],[0,-2],[0,-3]]
         piece.rotate
         piece.shape.should == [[-1,0],[-2,0],[-3,0]]
         piece.rotate
         piece.shape.should == [[0,1],[0,2],[0,3]]
       end
   end
end

I think this is a reasonable showcase of a balance between refactoring and simplicity. My initial implementation was pretty ugly, but it allowed me to continue making progress. After getting the simplest thing out the door and hitting my deadline, I went back to refactor the technological debt I had accrued.

Also, I am not going to need it, but the solution is now generalized enough that I could add additional pieces. For example:

   [[1,0],[2,0],[2,1],[2,2],[2,3],[3,0],[4,0],[5,0],[5,1],[5,2],[5,3]]


Additional Tetris piece

Some would argue that the new design is actually simpler. It's fewer lines of code, fewer branches in logic, it uses a well-established algorithm, it's more elegant. Sure, the refactored version is a vastly improved design, but "simple" isn't about lines of code or branches in logic. "Simple" is about complexity of implementation. For example, XP tells us about the "rule of three": refactor out duplication only on the third occurrence of duplicate logic, not the second. The implication is that duplication is more lines, but "simpler" to write.

What "simple" definitely is not about is elegance. The hard-coded solution was simpler because it had fewer levels of abstraction and required less of a cognitive load to understand than the matrix manipulation: the difference between basic Cartesian coordinates versus a result obtained using linear algebra. Math, even pre-calculus, is often quite elegant but quite abstract and therefore more complex than a simple table of values. Why does the rotation matrix work? Well, to understand that, you'll need to understand its generalized form, and quickly this solution becomes quite slow and complicated to implement, especially if it's late at night and you're having trouble remembering trigonometry.
rotation matrix general

It's clear that according to XP's philosophy, the hard-coded solution is the preferred first step. Kent Beck outlines the benefit of doing the easiest simple thing first:

  • You get done sooner
  • Your work is easier to communicate
  • Duplication is obvious, so the needs and means for refactoring are clearer
  • Tests are easier to write
  • The code is easier to performance tune (Or, at least, there will be more scope for tuning performance)
  • You feel less stress, which enhances all of the above

The key benefit of a simple solution is that you get it done faster so you can iterate on it. It's a first pass used to enable continued progress. Perhaps this principle should be called "do the easiest thing to make the tests pass," "do the ugliest, dirtiest thing first," "do what comes to mind first and stop thinking so hard," or maybe just "be as agile as possible." Agile, of course, primarily means "quick."

Comments
  1. Andrew Fader says:

    Here is a beautiful coincidence: http://c2.com/cgi/wiki?TetrisAnalogy

  2. John Barker says:

    I think using Rich Hickey’s “Simple made easy” talk as a counterpoint is a little misleading. Rich Hickey is advocating simple as an end goal. Kent Beck is suggesting simple as a means to an end. Though the difference may appear subtle it is an important one. The reason you write the Simplest Thing That Could Possibly Work is because it focuses you on writing code that meets the expectations first. Then once you’ve met those expectations you have a test harness that allows for easier refactoring opportunities. If you attempt to write a more elegant solution before meeting the full set of expectations you often have to throw away work as new complications arrise. This is what is meant by Pre-factoring.

    You correctly state that simplicity as advocated by Beck and Cunningham is the first step but suggest that their appreciation of refactoring and OO design patterns produces tension. It does not. The next step of the XP approach is to refactor, refactor, refactor. This step is so important in fact that many XP advocates cite its absence as a primary reason for XP failing. It is at this point where Rich Hickey’s definition of simple should be applied.

  3. Andrew Fader says:

    Rich also described any stateful system as being more complex than a non-stateful one. I think XP also advocates merciless refactoring and continuous refactoring to an end result “simple” state in the way Rich means. The difference is when you refactor and the scale of the project flow. XP suggests you start “simple” and then become “simple” later.

  4. Peter Jaros says:

    This is a problem of definitions. In Hickey’s terms, Cunningham’s admonition is to do the *easiest* thing that will work, to get to working implementation as quickly as possible. Then we should, in the spirit of Saint-Exupéry, remove what is not necessary and thus achieve simplicity.

  5. Andrew Fader says:

    It is tempting to say that there are only two meanings for the word “simple,” but actually there are many nuances and shades of meaning depending on the context. Hickey claims that “simple” is an objective measurement of the number of flows or paths in a program. Really, it is still being judged in a subjective way, but from the viewpoint of our dumb compiler or interpreter with the metric being defined as such. Actually what Hickey is doing is setting up the idea that functional programming is “simpler” than object-oriented programming, which I would challenge. He asserts that although less easy, it is nonetheless less complex.

    I would argue that complexity is best understood not only as the measurable path that the computer follows, but to the difficulty in communicating the conceptual underpinnings of the code, i.e. the subjective “simple” as perceived by a developer reading and “parsing” the code. Hickey tries to lump this under “easy” (to code), but I do not think it is strictly related to difficulty of implementation, but difficulty of understanding, or abstractness.

  6. John Barker says:

    The definition of simple is less important in this context compared to when you apply it. My concern here is that you seem to advocate that XP says refactor later, where your definition appears to be “never”. Where as this contradicts everything Beck, Fowler etc have every said about technical debt, refactoring and its importance in a normal XP workflow. Red, Green, Refactor. Not Red, Green, put refactoring off to another day (when it may be too late).

  7. Andrew Fader says:

    Neither XP nor I advocate never refactoring. There is probably some easy and simple refactoring you can do right away, but when it is significant in scope or expensive to do (relative to the project, so for my Tetris game revisiting linear algebra was expensive), it is better put off until later. The earlier you are in the project, the less you understand about the problems you are trying to solve. So undertaking major, project-wide refactoring later in the project is preferred. See http://c2.com/cgi/wiki?WardExplainsDebtMetaphor for what is probably the first use of the technical debt metaphor for this concept. Here are some quotes from Sandi Metz on the subject from earlier this year, see https://twitter.com/sandimetz/status/273110526706462721:

    “The wrong abstraction is far more damaging than no abstraction at all. Waiting trumps guessing every time.”

    “By wait I mean semi-duplicate code if you have too rather then jump to the wrong abstraction. Get it done, cheaply.”

    “I think of this as doing ALL yagni. When I abstract before I really, really need it, I’m always wrong.”

    “I would say YAGNI=good, meaning don’t do it too soon, wait on better data.”

Post a Comment

Your Information (Name required. Email address will not be displayed with comment.)

* Copy This Password *

* Type Or Paste Password Here *