a story lives forever
Sign in
Form submission failed!

Stay signed in

Recover your password?
Form submission failed!

Web of Stories Ltd would like to keep you informed about our products and services.

Please tick here if you would like us to keep you informed about our products and services.

I have read and accepted the Terms & Conditions.

Please note: Your email and any private information provided at registration will not be passed on to other individuals or organisations without your specific approval.

Video URL

You must be registered to use this feature. Sign in or register.


Learning about Symbolic Optimum Assembly programs


Writing a tic-tac-toe program
Donald Knuth Scientist
Comments (0) Please sign in or register to add comments

So I got my summer job at… in the Computing Center.  And, so I didn't come home to Milwaukee, except for a short trip that summer. And this was before I had met these girls I was… I was telling you about, in my sophomore year. So I had only the computer to be… to be with, and my… my second program was to… was to change numbers from decimal to other… other bases, but my… but that was a… a fairly quick. My third program is the one that I… I spent the most time on at that time, was to play tic-tac-toe.
Now… now I found out later that a lot of computer scientists have… have worked on tic-tac-toe. Charles Babbage, the famous guy who, you know, was… was planning a machine that could do tic-tac-toe in England in the… in the 1800s. Danny Hillis built a… built a tic-tac-toe playing machine out of Tinker toys, that went into the computer museum at Boston. But anyway, I and… I… decided I'd write a computer program to play this children's game, and it was a bit of a challenge. I wasn't using Tinker toys, but… but this IBM 650 had another interesting feature; not only was it decimal, with 10-digit numbers, but it only had 2000 altogether. So the total memory of that computer was, oh well, let me see, 2000 times, well what have we got? Five bytes or so? So that's 10… 10K bytes of memory. Now, right now, if you don't have 10 gigabytes, oh well, 10…10 megabytes, you know, you're… you’re dead. You can't load Microsoft Windows unless you have hundreds of megabytes, but here we had 10,000 bytes, total. And so I… but I… but I was wanting it to play tic-tac-toe against me. And… the… I wrote three versions of tic-tac-toe. One was an expert version, which you know, I… I pre-planned a… a strategy that… that would… that I knew was going to be right. What's the second version? I can't remember. But the third version was the most interesting. This was the learning version, where the machine starts out knowing nothing. And… and it learns by experience. So it… so it remembers all the possible positions on the tic-tac-toe board, just barely enough to fit inside of 10K bytes, and… and every time it plays a game, if it lost a game, it said, oh, these… these moves that I made were… were bad. The moves that the other guy made were good. If it won the game, it said, oh, my moves were good; the other guy's were not. So it would adjust; it… it kept… it had one digit for every position, so it would start out like at four, and if you'd… if you’d win a game it might go five. If you'd lose, it'd go to three. And so then if you had different moves, you'd… you’d… it would try the ones that looked… looked good in its ranking.

And… and that took me… that took me a month to write the program, and I learned a lot playing around with that. And afterwards I… I… then I tried the… the learning program against the expert program, so I would use the expert program to play and… and train the learning program.  So how many times… how many times would the expert play against, you know, like I think it was like 120 games or something, then the… then the learning program learned not to lose against the expert.
Tic-tac-toe is a kind of boring game, because if you really know… know how to play it, every game comes out as a cat's game; it's a tie. Nobody wins. But before that it's interesting. When you… when you make bad moves, it gets really exciting. So… so then I… then I said, okay, now I'm going to have two learning... I'm going to have the learning play… game play against the learning game, so both of them start out knowing nothing about the game, and each of… so originally all their moves are completely blindfolded, and… and you know, they're… they’re blundering along, but then at the end somebody happens to win the game, or somebody happens to lose the game, so then their strategy changes a little bit. Well now it turned out that after about 350 games, they would learn how to play conservatively, to… to draw against each other. It was a very dull game that they finally wound up doing… doing; they would… they played safe moves instead of brilliant moves, but it was anyway, a good learning experience for me, writing this tic-tac-toe program.

Born in 1938, American computing pioneer Donald Knuth is known for his greatly influential multi-volume work, 'The Art of Computer Programming', his novel 'Surreal Numbers', his invention of TeX and METAFONT electronic publishing tools and his quirky sense of humor.

Listeners: Dikran Karagueuzian

Trained as a journalist, Dikran Karagueuzian is the director of CSLI Publications, publisher of seven books by Donald Knuth. He has known Knuth since the late seventies when Knuth was developing TeX and Metafont, the typesetting and type designing computer programs, respectively.

Tags: Milwaukee, Computing Center, Case Institute of Technology, England, Boston, IBM Model 650, Microsoft Windows, Charles Babbage, Danny Hillis

Duration: 5 minutes, 13 seconds

Date story recorded: April 2006

Date story went live: 24 January 2008