In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.
The New Hacker’s Dictionary
“What are you doing?”, asked Minsky.
“I am training a randomly wired neural net to play Tic-Tac-Toe” Sussman replied.
“Why is the net wired randomly?”, asked Minsky.
“I do not want it to have any preconceptions of how to play”, Sussman said.
Minsky then shut his eyes.
“Why do you close your eyes?”, Sussman asked his teacher.
“So that the room will be empty.”
At that moment, Sussman was enlightened.
Note: I wrote this essay many years ago (2006, according to the date on it) and just dug it up recently. It’s much more technical than most of the stuff I post on here, but it’s a fun look into the past so I decided to go with it.
When I was just entering college as a Freshman, the only real programming I had done was in environments that do a lot of hand-holding (specifically Visual Basic 6 and Delphi 5). I liked Visual Basic especially because it was very simple and instead of doing actual programming I could drag buttons and stuff around on the screen to make pretty forms. But as a college student, I was given my very own copy of Visual Studio .NET (which Microsoft practically gives away to universities so that students will all come out knowing how to use their IDE and no-one else’s). I hadn’t learned enough C++ yet to get much beyond ‘hello, world’, but here was this spiffy new version of Visual Basic sitting on my computer.
I decided to try something new. For reasons that escape me now, I decided that my very first project in the land of .NET would be a tic-tac-toe game.
My goal was to create an unbeatable opponent. This is, as I know now, entirely possible. Tic-tac-toe is such a simple game that every possible move has been mapped out. The most naive possible opponent could simply remember every possible board configuration — made much easier by the fact that many configurations are simply rotations of other ones — and what the optimal move is when that configuration is encountered. There’s also an algorithm for perfect play.
I knew none of this, nor did I research any of this. Instead, I was going to build my own electronic opponent.
I had a great plan: I would score each row with a floating-point number. The number of computer symbols in the row would be the ones digit, and the number of player symbols in the row would be the tenths digit. Then I would devise a clever algorithm to determine the best place for the computer to go. I suspect I did a lot of this design work in my calculus class, because neither my calculus grade nor my design was particularly stellar.
I designed the windows form, a task which has not changed much between VB5 (the first version I used) and VB.NET. I made the necessary doodads and widgets that were necessary for a tic-tac-toe game. I was somewhat dismayed at the lack of support for control arrays in the form designer (I still don’t really know why this was removed, since it was a great feature), and rather than doing it by making an array of controls (which is close to the same thing, though without explicit form designer support) I had nine textbox controls labeled UR (upper right) through LL (lower left). A maintenance nightmare, but since there was only nine of then it wasn’t like I was dealing with thousands of things one at a time. I even knew at the time, CS first-semester freshman though I was, that this was a suboptimal design, but since my grasp of programming was rudimentary at best then there was little I could do. But after a short amount of time I was ready to actually write the code.
With the documentation open at all times for a quick reference, I began coding up the logic. I started with prosaic stuff like making the right symbol appear when you clicked the textbox and making the program figure out when someone had won (a massive wad of select case statements, which would be a continual theme throughout the program). But finally it came time to write the AnalyzeMove() function, the function that previously just picked a random free square for testing purposes. This function would be the brain of the computerized opponent.
After writing a few support functions to do things like calculate the value of a row, determine which cell in a row was the best one to move to, etc., I finished up the function. I started the program, graciously let the computer go first, and began a game. After a few games I realized that there was a critical flaw in my ‘unbeatable’ AI: it could be beaten by a small child, a particularly intelligent monkey, or even a University of Virginia graduate.
I tightened up the algorithm some, but there was always some sequence of moves that would beat the AI. It also had the slight problem that sometimes it would give up and decide that none of the moves were all that appealing, instead doing nothing. The AnalyzeMove function ended up with a lot of ‘failsafes’ that it could fall back on if it couldn’t find a move, and also a lot of special case code designed to handle one possible sequence of moves that would result in a player win. By the time the AI was done, it may have been less effort to approach it on a case-by-case basis, dealing with every possible board configuration based on the best possible move. But there we had it: my unbeatable AI was complete.
Fast forward to 2005. An older (and much better at programming) me was rummaging through my old programs when I found the TicTac executable. “Ha!” thought I, “I remember this. Let’s have a few rounds against the unbeatable AI.” So I fired it up and started clicking. After a few games, I ended up being selected to go first so I did. A few moves later, much to my surprise, I won. I wasn’t really expecting it, so I had been paying about halfhearted attention. But I managed to reproduce the sequence of moves which resulted in victory and even vary them up without the computer being able to defend against it. The fundamental problem was, in order to counter this particular tactic the opponent must make a move which, considered in a vacuum, seems like a sub-optimal move. It’s only when taken in the context of the game as a whole that the move makes the most sense. But my goal of an unbeatable opponent was still intact and I still had the code kicking around somewhere, so I figured “hey, why not re-visit that code and see if I can block this move?”
As any programmer knows, looking at one’s own old code is basically like looking at someone else’s completely unfamiliar code. My first inclination was to just re-write the thing in C# or maybe use it as an opportunity to learn Java better. But I figured that it would be a good exercise in code maintenance, so I dutifully fired up Visual Studio .NET and opened the project.
I had known that it was a mass of special cases and select case statements, but I had forgotten how abysmal it really was. For example, I had a problem with text selection: when the user clicked on one of the text boxes that represented the cells, the player’s symbol would appear. But if the user moved the mouse while clicking, the symbol would be highlighted (in the canonical method of text box controls). In 2002, I had no idea how to fix this, so I wrote a function called Unselect which would iterate through each control and remove the selection. I then threw calls to this subroutine throughout the code. I think it was actually called twice in the AnalyzeMove() function, which is silly. What I did not realize was that the highlighting was occurring in the MouseMove event, so the logical thing to do would be to put a call to Unselect() in there. I did that and removed the other unnecessary calls to Unselect(), which made the code immensely easier to read.
As a second modification, I created a class for a cell and for a row. This allowed me to encapsulate in their own class all the data pertaining to cells and rows. Many programmers at this point would have used aggregation or association to create an object with three row objects, with each row object having three cell objects. This memory model would allow the table itself to be completely represented in memory, and then the visible grid would just reflect the state of the table. However, this would essentially be wasteful because the data would be duplicated in memory. In addition, I wanted this to be an exercise in maintaining code without significantly changing the underlying architecture. So instead I created row and cell objects as I needed them and then abandoned them to the garbage collector when they were no longer actively being used.
Readers who have been paying attention will realize that I have not yet addressed the issue of the computer opponent, which was the original reason why I wanted to modify the code. However, experienced programmers no doubt realize that by making these changes I in essence paved the way, making my job easier by allowing me to visualize better what’s going on, giving me a better way to map my mental model to the program model (using these college terms makes me feel so smart), and in the first case helping me remove calls to a function that has no relation to the task at hand. With these things accomplished, I moved on to the AI section.
The code was very poorly done and actually existed in two stages. My initial plan was just to insert (another) special case into the logic where it would detect when the tactic I had found was used and then defend against it. However, this was a problem for two reasons: first, the detection would occur in stage one but the defense would be in stage two, and second, the defense requires two moves to be fully successful so that would actually be two special cases, which actually would be four special cases for the first move (because it can be rotated 90, 180, or 270 degrees and still work) plus detection and correction for each of the possible counter-moves to then create a counter-counter move. This way lies madness. So I decided to radically clean up the code.
At this point, a career in horticulture begins to look more and more appealing, but I resolutely pressed on. After a few rounds of testing and tweaking, the program was essentially complete. The AnalyzeMove() function determined exactly which cell to play in, and it made fairly intelligent decisions about where to move. At least it would play a good game of tic-tac-toe. Except for one problem: it was still beatable.
I cannot yet give this story a proper ending, as the program still exists in the state described above. Other projects have become more interesting and TicTac must return to its slumber on my hard disk, at least for the moment. Maybe some day this narrative will finally become complete and I will have written a truly unbeatable opponent.
14 years later (this is 2020 Nathan writing this bit), I haven’t touched that program again. I can’t really even claim to know the programming language it’s written in anymore, and I have more interesting and (hopefully) useful projects to work on.
As I mention in the essay above, tic-tac-toe is a solved game, and it was a solved game back when I originally started this project. However, the point of this project wasn’t to add useful and novel research to the field of game theory or artificial intelligence. The point was that I wanted to write a tic-tac-toe game, so I did. It stretched my programming abilities and it was interesting enough for me to finish it until it was playable. Thus, it served its intended purpose admirably!
I could write a much better tic-tac-toe game today. But why would I? There are already a number of excellent tic-tac-toe implementations out there (if you Google tic-tac-toe, you can play a game right in your browser!). I would be unlikely to learn very much, and while I might find some enjoyment in it, I don’t think I would find very much.
To aspiring programmers: there’s way more information available now then there was when I was starting out. It’s easy to feel like all the problems at your level have already been solved. My advice to you is to ignore all that and build something you want to build, for its own sake. Don’t look at how anyone else did it. Do it your way. There will be plenty of time to see how other people have solved the same problems once you’ve found your own solution, because then you will be in a position to truly understand the other solutions you encounter.
And never, ever, stop playing and having fun.
Strange Tales for Strange Times 
I love your advice at the end. (The technical stuff went right over my head.)
LikeLike