Monday, March 05, 2007


Noughts and crosses

[Corrected spelling of “noughts”; thanks, Ray, for pointing it out, and thanks to the Ridger for pointing out that I can change the title without changing the permalink.]

Here's another in my college days series. This one's about some recreational computer programming.

One day in 1975, I decided, on a lark, to write a program to play tic-tac-toe (UK: noughts and crosses). You know the game, surely; it's a simple game, and computers have been playing it since the earliest days of computers. There wasn't any particular reason for me to write one, except that I had some free time — and perhaps more time than sense — and felt like writing it in APL.

As I recall, the program didn't lend itself particularly well to APL, so it wasn't the most concise APL program on Earth. Still it was fun to write. And just as you know it's a simple game, you probably also know that if neither player makes a mistake it will always end in a draw, which we used to call a “cat's game” (for reasons I never knew). Of course, the program never made a mistake — not hard to program for such a simple game, and so it couldn't possibly lose.

Write it. Test it by playing it a bit. Put it away forever.

Well, almost. First I showed it to a friend who was a journalism major (so, not a computer guy... so not a computer guy). He thought it was cool, despite the rudimentary user interface (well, to be fair to the programmer, pretty much all user interfaces were rudimentary in those days): it typed the grid out for you, you gave it your play by entering the number (1 to 9) of the square you wanted to play in, it made its move, and it typed the next iteration of the grid.

My friend liked it, and played it for quite a while. He kept playing it. He kept playing it long after I was sure he'd have tired of it, certainly long after I'd have tired of it. “OK,” I said, “Come on... let's go get some beer.” No, no, he replied... he wanted to play it more. He hadn't won a game yet. “But you can't win. You'll never win.” But surely it'll make a mistake eventually! “No... it won't. It's a computer. It's not going to get tired and ‘slip up’, or anything like that.” But don't computers make mistakes? “Well, there could be a bug in the program, yes. But I assure you, there isn't. It's a simple program, and I've tested it.” Aha! There could be a bug![1] And he kept playing, playing, looking for that bug. I left him in the computer center, and found others to “drink a pizza” with.

I'd like to say that he remains there, to this day, trying to defeat my program, like something out of a Twilight Zone episode. No, he did eventually show up at Leonardo's, and I think he even caught up with us with his beer count. He never did score a career in journalism, though, at least not as far as I know. And no one ever played my program again.

[1] On a side note, we often measure the “bugginess” of a program as a ratio, in errors per thousand lines of code. The highest bug rate in history, at least by lore, was in a “trivial” IBM program called IEFBR14. I was going to describe it here, but I see that my colleague John Pershing's description is on Wikipedia, so I'll link to that instead (look at the "history" section).


Maggie said...

When I was an undergrad, I got a Mac. It was before any of my friends had a Mac, and before there was a Mac lab on campus (by a semester, I think). My friends came over my house and they stayed all night, mostly playing with MacPaint. I remember them, drawing things and then selecting them with the lasso and cutting them apart, laughing like it was the funniest thing ever.

Is there anything like that now? I feel so numb to new technology. My children are accustomed to computer and cell phone technology, and my husband and I sound like old-timers, explaining how you needed to find a pay phone when we were young.

I wonder what the next great leap will be, the next technology that's so cool, people will find it amazing and won't be able to tear themselves away.

Ray said...

Since you point out that the name of the game is British, I thought that I, in turn, should point out that we spell it "noughts", not "naughts".

In my very first job, when our department acquired a PDP-8 computer, our manager wrote a noughts and crosses program, too, which I thought was exceedingly clever. Better still, this was a program that learned from its mistakes so that, even if you succeeded in beating it once, you would never beat it the same way again. This would have been a really interesting feature to add to your program before inviting your friend to play it! "I've beaten it before. I know I can beat it again."

Barry Leiba said...

"Dang!", as they would say in The Far Side. I actually looked up the spelling to be sure, and I still messed it up. Ah, well. Nothing for it now; if I change it, the permalink will go wrong.

In order for "learning" to be of any value, the program would have to be imperfect to start with. It was so easy to write it to play perfectly the first time that no sort of machine learning was useful.

We did try to write a machine-learning program to play Stratego, but we hadn't studied machine learning at all, and it was a huge flop.

Maggie, the cell-phone vs pay-phone thing is particularly amusing when I think of all the movies now whose plots require cell phones. In The Departed, for instance, the whole thing centers around using cell phones for communication.

Ray said...

Barry: In order for "learning" to be of any value, the program would have to be imperfect to start with.

That depends on what you mean by imperfect. Since this particular program was written so as to learn by its mistakes, and would eventually (quite quickly, really) become unbeatable, I would say it was a perfect program that did precisely what it was designed to do.

Barry Leiba said...

Right, but in this case "perfect" modified "play", not "program".

Maggie said...

Staying out of the "perfect" conversation... :-) (It depends on your goal, but tic-tac-toe does seem an awfully easy game to practice with machine learning on. Okay, I didn't quite stay out.)

It's also interesting to read/see stories with plots that rely on technology *not* being there, like the Leaphorn/Chee novels by Hillerman. I think we were explaining it to our girls when we were watching an old Columbo episode or something.

It opens up an interesting sort of character (and probably some clever author has written a character like this) -- one who refuses to use technology. The old-timer who won't have a cell phone, e.g. I have a friend who refused to have an answering machine for years (she just got one this year), and it was so annoying to call her and have the phone ring and ring! You get used to being able to communicate with people that way.

The Ridger, FCD said...

Actually, you can change the name of a post without the permalink messing up. I've done it; the permalink stays the same even if the title changes completely.

Barry Leiba said...

Well, looky there — so you can. I've fixed the spelling, with acknowledgments to the both of you.