At work one day, I walked past my director’s desk and noticed he had an editor open and was typing some C code. That was strange (not as strange as it might be in other companies – our director definitely is capable of coding but generally doesn’t). So I asked him what he was up to.

We were looking to grow the team and he was considering asking candidates to code up an implementation of tic-tac-toe as a test. That way, we can see how they approach problems and their coding style. But he wanted to see how difficult the task was before asking anyone to do it so he was trying it out.

Intrigued, I went home that night planning to write my own. I decided to do my implementation in Perl. I didn’t want to write any code for data structures so I just wanted to use a language which had basic arrays and hashes built in. After a short time, I had an implementation which worked and would never lose. It computed all possible moves and scored them. If you weren’t careful, it would beat you. But it was pretty slow. The first move took a couple of minutes on my iMac which is a pretty fast machine.

The other feature of my implementation was that the size of the board was configurable. I decided to try a 4×4 game and it was unplayable. After a couple hours, it still hadn’t made a move.

But, that was enough of a proof of concept. At work though, others started talking about writing their own implementations. People were going to try Python, or C++ or raw C. People said they were going to make an implementation which was faster than mine and still search all possible moves. I needed to do better before I was beaten.

So, I tried again. I ported my implementation to C. And I started adding more smarts. I noticed that I could skip several board configurations. Perhaps the board is a mirror image of one I have already looked at. Or maybe a rotation of one already investigated. So, I added a cache to keep the best move given a board configuration and added code to recognize that one board state is symmetrical with another. That significantly shrunk the space of moves to search.

Then, I added “Grand Central Dispatch” support. On the Mac, this allows you to schedule tasks to multiple cores on the processor. That way, I could investigate multiple board configurations concurrently. With these changes, a 4×4 game became playable. It took my Mac a couple of minutes to make the first move but once it had pre-calculated everything, it was fast.

And as a challenge, I decided I would see if I could get the 3×3 game working well enough on some of my older machines. I have a C cross compiler for my Apple //e and my Replica One. I ripped out the “Grand Central Dispatch” code because that would never work on these old machines. I shrunk the data structures and did a bit of math in my head to see if they would fit. I needed to store enough state for all possible games on my Replica One which had 32K of memory. After a bit of optimization, I decided it would fit.

I compiled the program for the //e and the Replica One and they worked. Again, it took a couple of minutes to make the first move as it investigated all possible games but after that it was fast. And this was on a 8-bit processor running at 1MHz with as little as 32K of memory. I figured I had done enough to defend my reputation since I had a usable version working on nearly 40 year old hardware. More than that, I had a version of tic tac toe running on hardware nearly 40 years old which I assembled myself with a soldering iron. I win the title of “king of the geeks” and none shall challenge me.

And to this day, I don’t think anyone has even attempted their own implementations. If anyone does come to challenge me, I think I will learn OpenCL which will let me put the game search on the GPU in my iMac and then I can get a huge amount of parallelism. Maybe 5×5 becomes playable that way. Maybe…