London Clojure Dojo, August 2011

Posted on 08 September 2011

Prologue: I’m going to start blogging every month’s London clojure dojo here. For more details, see epilogue.

August’s dojo, like most of them, was a bit of an experiment. The wonderful Dale Thatcher had prepared a tournament environment for all of our clojure programs to compete in.

The format was this: every ten minutes, we had to upload a working clojure program to a tournament server. The server would then play each team’s program against every other program and determine the winner each time. Points would be scored and added to a running leaderboard.

After settling in with a few rounds of rock, paper, scissors, we started the main feature: noughts and crosses! Your program is given a command line argument of the form

xx0-0----

representing a noughts and crosses grid. You have to output a number from the range 0-8 indicating your next move. One snag is that you are not told whether you are noughts or crosses, and have to determine this fact with the knowledge that noughts go first.

So for example, in the above board layout, you would instantly win if you output 6, because you are noughts, and you would have formed a line top-right-to-bottom-left.

I was on team 4 — you can grab the code and follow on from github.

Lesson 1 — automate common tasks

Since we were to be uploading a new contender every 10 minutes, the first thing we did was write a script called gen-zip which did just that. This script bundled our app into a zip file and uploaded our entry to the tournament server in one step. Hey presto, continuous delivery! Furthermore, this script also automatically committed to git, keeping a history of every single program we uploaded to the tournament server (from the second round onwards, at least).

Lesson 2 — start simple and evolve

Our first entry for noughts and crosses was simply (println 5). It was basically the fastest thing we could write which wasn’t simply guaranteed to lose. Since deployment is cheap, we uploaded it, although it wasn’t captured in the git history. Our second entry (aed257) simply searched for the first free space and went there:

(defn choice [board]
  (inc (.indexOf board "-")))

The simplicity of this is astonishing:

no need to parse the board string into an actual board object
no need to determine which player we are

Instead, we just use Java’s native String.indexOf() method to find the first free space and output the index corresponding to that space.

Our next contender (2db1fc1) was only slightly more complex:

(defn choice [board]
  (cond (= \- (nth board 4)) 5
    (= \- (nth board 0)) 0
    (= \- (nth board 6)) 6
    (= \- (nth board 2)) 2
    (= \- (nth board 8)) 8
    :else (inc (.indexOf board "-"))))

Here we use the fact that clojure strings are sequences and can have nth called on them just like anything else. Once more, we don’t need to parse the string into a board; we work only with the flattened string, and we add a bunch of special cases to make a brute-force strategy of getting the middle and then each corner in turn. If all are taken, we revert to our original strategy of the first available space.

Lesson 3a — understand the problem before rushing to a solution

Lesson 3b — get frequent, rapid feedback

You may have noticed some oddities in the above code. What is that inc doing there before .indexOf? Why do we say (cond (= \- (nth board 4)) 5 ...) not (cond (= \- (nth board 4)) 4 ...)? This is because we made the faulty assumption that the grid indexing was 1-based, not 0-based. As a result, we were often going one square to the right of where we actually had intended to go!

We only discovered this because one member of our team was checking each tournament result to see which other teams we lost to and why. He noticed that we were making invalid moves — something we thought we had avoided by always aiming for an empty space.

Our next version (d83b9a6c) fixed this problem. It also started work on a significant new effort — parsing the board and detecting if it was possible to win outright from the current position.

Lesson 4 — doing something simple correctly is better than doing something sophisticated but wrong

By this time our work on instant-win to determine if there was an instant winner was the most significant part of our efforts. The next step was a function to determine which player we were. This was deemed a challenging enough task that we wrote a test for the function. Next we wrote a test for our instant win function, and aimed towards putting together the pieces which could make that function pass. However, all of this was a waste, because we simply didn’t have the time or phenomenal brains required to solve the problem in the half hour we had remaining.

By contrast, the only significant refinements we made to our program in these rounds were based on feedback from tournament results:

in 8e4e524, grabbing square 2 earlier, to stop us losing to those enemy programs who just filled the grid in order (as our example in aed257 had done).
in 244c97c, changing from 4-2-0-6-8 to 4-2-6-0-8 to fill the 2-4-6 line one move faster.

Our final version had reams of abortive attempts at sophistication, all commented out using the #_ reader macro. But the real reward had come from those old tactics, rapid feedback and gradual evolution.

Epilogue : the London clojure dojo happens on the last Tuesday of every month. During the dojo, we split into groups of four or five around a single computer, and each person takes a turn at the keyboard. This ensures that even if you have zero clojure experience, you will get the opportunity to write some code at the event.