Monthly Archives: February 2012

Tic-Tac-Toe

Tic-Tac-ToeAt 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…

Matthew Learns to Type

Matthew’s handwriting leaves something to be desired. So does mine for that matter but it was becoming a problem at school. It was slowing him down and keeping him from getting his work done. The school suggested that he could have access to a laptop so he could type some of his work instead of writing it if only he could type quickly. Matthew needed to learn to type.

My first stop was the Mac App store. I searched for a good typing tutor and started with “UltraKey”. It seemed to be well reviewed so we tried that. He worked with that for a bit but he quickly got bored. UltraKey was definitely targeting an older user and Matthew wanted something more dynamic.

So, I picked up “Typing Tournament”. This was highly graphical with little games you play by being able to press the right key in time. It was definitely a good program for him and he started improving when using it.

But after a while, it seemed like his biggest problem was the keyboard. We have a wired Apple keyboard hooked up to our iMac. The keyboard actually is very much like a laptop keyboard. The keys are very shallow and one false move and you will type the wrong key. I figured Matthew might need to practice on an easier keyboard.

I have no shortage of computers and keyboard handy and the first one I thought of was the Apple //e I have. I have an old typing tutor on a 5 1/4″ disk and I pulled it out and booted up the machine. Matthew tried typing on the Apple //e for a short time and he did seem better. But then he moved to the machine to his left and just tried that keyboard. He said he really liked that keyboard and would like to use a typing tutor on that one.

Well, that was my Replica One which is a reproduction of an Apple 1 from the mid 1970’s. As far as I knew, there never was a typing tutor written for the Apple 1. But Matthew insisted that he liked that keyboard best. What should I do?

What I did is I wrote a typing tutor for the Apple 1. I had a C compiler working for that computer so I quickly coded something in C. It starts with a menu. One item on the menu allows you to select the set of keys you want to work with. You can focus on the home row, all letters, letters and numbers or all keys. Then you can either do a typing drill or the typing game.

The drill gives you eight characters randomly from the set of keys you are working with for you to type back. You type them and it tells you how many you got right and then gives you eight more until you decide to quit and press escape.

The game just prints a random character from the set you have selected over and over again until you press it. Once you press it, it prints a new random character. The goal is to press the key as quickly as you can and get as few characters printed as possible.

Matthew used the program a few times but he gravitated back to the Typing Tournament on the Mac. I guess the simple text based output couldn’t compete with the colourful graphics in that program. But Samantha liked using my typing tutor and probably used it more than Matthew.

I posted my program online for other people with a Replica One or maybe even a real Apple 1. According to the forums, my program has been downloaded 38 times which is pretty good I think.