Tic Tac Toe

Yesterday I had the unusual once-in-a-lifetime experience of getting up before everybody else in the house. Confused, and not quite awake yet, I went to work on the latest version of Intercab. Before noon version 0.22 (documentation) was fully functional and the situation that you simply don't know what else to program emerged. Luckily a friend of mine mentioned a fun thread on the java developer forums where a few people were trying to implement Tic Tac Toe in Java. Their implementation (this was apparently the second thread already) was well over a thousand lines of code, wasn't working, and a perfect example of how not to program applications.

Slightly shocked I amusingly read the topic, and couldn't hold my laughter after I saw that somebody showed them how to program Tic Tac Toe in 99 lines of Java. His implementation however had a mayor flaw; the player was both colors (or X & O to be exact) at the same time. That's not how you play the game! You're supposed to play against somebody, or at least against something! My brain did some quick thinking. The number of possible moves in any particular game of TTT isn't that big, so a brute force artificial intelligence should be able to find the best counter move rather quickly.

I opened up a new tab in my webbrowser and started searching the web. I figured their should be at least one implementation out there which was already bruteforcing it's way through all possibilities. I was expecting something along the lines of a min-max algorithm and after about 5 minutes I had a hit. It was an alpha-beta search to be exact, and had a few very nice optimalisations written in it. Armed with that source, I got to work to implement that algorithm in the 99 lines of TTT Java goodness.

About two hours later (and a full re-implementation of the alpha-beta search, since there where a few fundamental design differences between the two source files) I got the thing to work. The weirdest part was that the original source of Particle had a bug in it causing it to always loose. They probably didn't put online their latest version of the application to prevent people from copying their source blatantly, but it wasn't hard to spot if you understand what's going on. With an end result of 164 lines I was now the proud owner of an unbeatable TTT version! You can try your luck here, and if you're curious about the source you can look at it here. I'll make a commented version later today to explain what's going on in the algorithm (update: Done, and a bug fix too).

Two hours of programming didn't really fill my afternoon, but it sure was fun to do. A friend of mine mentioned (dutch blog, the game's called 'Boter, kaas en eieren') a few days ago that he was planning on writing TTT in Python so if Java isn't your thing (I got to say, it still isn't mine either) you might want to keep an eye on his blog.

In other news, I've updated the Javascript again which makes this website navigate so snappy and you'll be able to open up pages in new tabs and windows again, even though the links loaded don't actually change the page you're looking at. I'll probably spent some time today on the layout of this site, although I'm not exactly sure what I want to add yet. We'll see, it shouldn't be too hard to come up with something idiotic. G'day!

[: wacco :]

Leave a comment