November 7, 2007

The Context of Minstrel‘s Creation

by Noah Wardrip-Fruin · , 7:24 am

Last month, when I got in touch with Scott Turner (author of Minstrel) I asked if he would be willing to share some memories of the context in which his landmark story generation project was created. I also hoped he would let me publish his thoughts on Grand Text Auto — as James Meehan had last year let us publish some of his memories of the creation of Tale-Spin. This came to fruition yesterday, when Scott sent me the thoughts below and agreed to let us publish them. I enjoyed the stories (as will most who’ve gone through the grad school process) and I think they offer an interesting perspective, especially when combined with Scott’s contributions to our ongoing discussion of Minstrel and the future potential of its approach.

I came to UCLA for my graduate work in the Fall of 1982. I was actually recruited to UCLA — they paid to fly me out to visit the campus, meet with professors and graduate students, and even offered me a “bonus” to enroll during my recruiting trip. The bonus turned out to be book money, but they could have saved themselves the trouble — I was already committed to attend before the trip.

As a senior I had spent part of the year trying to construct an equivalence between token networks and finite state automata. I wasn’t successful, but I thought it was pretty fun, and I was interested in UCLA primarily because Sheila Greibach (of “Greibach Normal Form” fame) taught there. So I arrived in the Fall of 1982 excited to start graduate school and plumb the mysteries of formal machines. Somewhat to my dismay, I discovered fairly quickly that Prof. Greibach wasn’t very accessible or very interested in taking on any new graduate students. It also became apparent that the students working in theory and formal machines were quite a bit smarter than I was.

Fortunately for me, UCLA was trying hard to expand and upgrade the Computer Science Department. Over the course of the next few years, they brought in a number of enthusiastic young professors, amongst them Michael Dyer (and his wife, Margot Flowers). Mike Dyer was from Yale and had worked with Schank there, doing “scruffy” AI and tackling all sorts of interesting problems. Mike ran a graduate seminar on AI as his first class at UCLA and recruited a dozen students, myself included, to form the nucleus of an AI research group. Mike was still half a graduate student himself at this point, so the group was very collegial. We’d go out to dinners and socialize together and there was a great sense of camaraderie. We called ourselves the “Airheads.”

There were some outstanding students in the Airheads. Almost everyone in the initial dozen eventually finished their Ph.D.s and about half went on to tenured positions around the country. Mike got a “genius” grant from the MacArthur Foundation and used the money to build an AI Lab equipped with powerful Apollo workstation computers. The Airheads moved into the Lab en masse and began hacking away in Scheme on an amazing variety of topics — everything from mechanical reasoning to irony.

Not everything was entirely happy in those early days in the AI Lab. Mike came from a research group at Yale that was very competitive and he brought that same model to UCLA. Mike believed that the academic world was cut-throat, and the best preparation was experience. He wanted his students to face tougher criticism in private than they would ever experience in public. He had the Airheads meet weekly for research reviews, and the critiques were vicious. Mike was brilliant and had insight borne of years at Yale — his analysis of our fledgling work was pointed, demanding and unforgiving. The Airheads were only too happy to emulate his model and be as blistering as they could manage in their dissection of each other’s work. If your work was going well, you were generally safe, but if Mike found your work lacking he’d ask you to present your “progress” at the next research meeting. It was a gut-wrenching week waiting for your turn to roll around. More than one presenter fled in the face of the criticism, and at least one left in tears.

Some good did come out of those meetings. The trial by fire generally worked. As a group the Airheads were as sanguine a group of presenters as I’ve ever seen. I saw Airheads at conferences take cruel, envious barbs from the audience and blithely defuse them. Also, the criticism (or the fear of it) did greatly improve the level of our work. For myself, I’ve never since feared public speaking or presenting and defending my work. The real lesson I took from those reviews was to do good, solid work and to have confidence in my own efforts. And Mike was not by nature a cruel person. I think in part he initiated the research meetings because he didn’t have the heart himself to be as critical as he felt was necessary. In those days he was mostly characterized by his enthusiasm. He took a great delight in the work being done and would bubble over with ideas and exuberance. Eventually he came to believe that the research meetings were doing more harm than good, and by the time I left UCLA they had long since stopped.

At the time the AI Lab was created I rode a motorcycle (thanks to one of the other Airheads, Jack Hodges, who also taught me to hang glide) and lived in what would soon become the city of West Hollywood. Initially I supported myself as a teaching assistant, but around this time I received a three year scholarship from HP, which I thought of as my “volleyball” scholarship. I would get out of bed around 10 AM every morning and ride down to the beach at Ocean Park, where I would play beach volleyball for most of the afternoon. I would then ride up to UCLA and work in the AI Lab until 1 or 2 AM before heading back to West Hollywood to repeat the cycle.

There was a core of Airheads who haunted the AI Lab in those evening hours, including the aforementioned Jack Hodges, Alex Quilici (who would later become a VP at AOL), Seth Goldman, John Reeves, and myself. The four of us collaborated to build a package of tools called Rhapsody upon which we built our programs.

UCLA had a Computer Club, which was graced with a room on the fourth floor of Boelter Hall where the Computer Science Department was located. The Computer Club was haunted primarily by undergraduate social misfits, many of whom I and my fellow graduate students had TAed at one point or another. There was a long-standing friendly rivalry between these undergrad geeks and their graduate school counterparts. For example, one year there was a basketball game between the graduate students and the best of the undergrads that drew thirty or forty spectators. (The grad students won, of course.)

In 1989, David Smallberg came to me and some of the other graduate students and suggested that we form a team to compete against the undergraduates in the ACM Programming Contest. (David Smallberg had been on UCLA teams that had finished second in the nation in 1983 and 1985.) I was vaguely aware of the Contest — my undergraduate institution, Washington University in St. Louis had won in 1979 when I was a sophomore — but didn’t really have any great interest in competing. David kept prodding me and I finally agreed that if he could get other people on board, I’d compete. He did, and eventually we ended up with a team consisting of Alex Quilici, Seth Goldman (both from the AI Lab), Matthew Merzbacher, and myself.

The undergraduate team had their core members back from the previous year and were pretty cocky about their chances, but we demolished them in our practice matches, and when both teams got to the Regional competition, we won handily. That sent us on to the Finals, which were being held that year in conjunction with the annual ACM conference in Louisville, KY.

At that time, the Contest consisted of a series of programming problems (usually 8) and each team was given one PC upon which to solve the problems. Candidate solutions were submitted to a judging team, and the only feedback the team received was that the solution worked or it didn’t. The team which solved the most problems won; in case of a tie the team that solved the problems most quickly won. Successful teams usually had a mix of talents: good programmers, good algorithm folks, good debuggers, etc. We were lucky in that everybody on the team was pretty good at every software skill, so we could be flexible and back each other up as necessary.

The Contest ran all day. Intermediate results were posted occasionally, and at first it did not appear we were going to be very competitive. Teams from RPI and CMU posted solutions to several problems very early — before we’d solved any of our problems. As the afternoon wore on we closed the gap somewhat. By the end it was neck-and-neck-and-neck, with our team, RPI, and Texas Tech having solved more problems than the rest of the field, although we trailed badly in time-to-solution. It only mattered what had happened in the last flurry of submissions. We knew that we’d managed to solve one last problem in the final submission, but no results were posted so we didn’t know how the other teams had done.

At the banquet the next evening the results were announced. Third place went to Texas Tech, and second place to RPI. We sat stunned for a moment and then began high-fiving as we realized that we’d manage to sneak into first place by solving more problems than the other teams.

We had our pictures taken for the ACM Magazine and then learned, much to our disappointment, that there were no prizes for the Contest that year. In the past, the ACM had managed to get laptops and PCs and similar gear donated for prizes, but somehow this year it had gotten overlooked. The ACM did make a $500 scholarship contribution to the Department, but the team members got nothing.

The next year at the Regional we were completely stymied. The Regional was much the same format as the previous year, although this year we were submitting our solutions on floppy disks. Partway through the competition, our programs started coming back “failed,” even though we couldn’t find any faults in them. With just minutes to go in the competition, we discovered an extraneous file on our submission floppy. The automated testing routine being used was apparently pulling that file off the floppy instead of our submission. We hurriedly deleted the file from our floppy and re-submitted, but the judge ruled that we were too late — judging by his wristwatch rather than the prominent clock in the classroom that showed several minutes still to go. We protested to no avail. The following year the ACM changed the Contest rules to prevent graduate students from competing.

In that second year of competition, we replaced Seth Goldman with a brilliant new graduate student named Chris Ferguson. Chris had been a math undergraduate at UCLA and his parents both have doctoral degrees in mathematics. He wasn’t a top-notch programmer, but he had one of the most amazing mathematical minds I’ve encountered. At the Regional, Chris looked at one problem and offered to solve it analytically instead of programatically. He went off by himself for about 45 minutes and came back with the answer. We put together a short program to print out the answer and submitted it. This wasn’t the usual approach for a programming contest, but nothing in the rules prevented it. It came back correct.

Although Chris wasn’t part of the AI Lab I saw him quite often around the Department, and late at night he’d often wander through the Lab. However, he sometimes disappeared for a week or more at a time, and he seemed to change his appearance every time I saw him. Eventually I learned that Chris was a major card-counter and blackjack player. He was playing high-stakes blackjack nearly every weekend in Las Vegas, and having to change his appearance to keep from being blacklisted or worse. Chris got John Reeves and I interested in card counting, which we picked up fairly quickly. Eventually we were all making trips to Las Vegas to play blackjack, although John & I were playing low stakes and very casual about it.

Chris was fascinated by all the casino games and the math behind them. One night very late I was working in the AI Lab and there was a pounding at the door. It was Chris. The previous weekend he’d noticed that a new Asian card game had been introduced at a Vegas casino, and he was in the middle of writing a program to simulate the game and determine if there was a positive strategy. He was hung up on some details of the programming, so after he explained the situation, I helped him for a few hours to get the program running. He rushed off to finish his analysis and I didn’t see him again for several weeks. I assumed that the game was beatable and he’d rushed off to take advantage of it while he could, but when I next saw him and asked about it, he barely recalled his analysis.

Chris eventually shifted his focus from blackjack to poker and won the World Series Main Event in 2000, as detailed in “Positively Fifth Street” by James McManus. He finished his Ph.D. and continues to be one of the top poker players in the world today.

Around this time, David Jefferson (who would later be on my committee) came to Seth Goldman and I to talk about a collaboration he was doing with a professor of Biology. The idea was to look at issues in evolutionary biology by simulating an environment and individual animals in the environment, letting them interact, reproduce, pass down genetics, change their behavior and so on. It sounded pretty interesting, so Seth and I spent part of our time the next two years working with David Jefferson to create this simulation. The whole notion of simulating not only intelligence, but all aspects of living creatures became known as “Artificial Life” and the work that Seth and I did was eventually presented at the first Artificial Life conference.

While I was at UCLA I often worked during the summers, including stints at the Rand Corporation (whwere I applied some of what I’d done in Artificial Life to simulating clashes between NATO and Soviet forces) and in the AI Lab at Texas Instruments in Dallas. After my volleyball scholarship ran out I took a part-time position at the Aerospace Corporation (where I’m still employed today). The Aerospace Corporation is a non-profit, Federally Funded Research and Development Center (FFRDC). About 35% of the workforce has Ph.D.s, and most of the rest have and/or long technical experience. The atmosphere there was like the best of graduate school, and I was soon spending most of my time at Aerospace, splitting my efforts between work and finishing my degree. (It helped that the computers at Aerospace outclassed the now-aging Apollos that still populated the AI Lab at UCLA.) Although the first major project I worked on at Aerospace was seminal work in applying AI to the diagnosis of satellite faults, I soon started drifting away from AI.

By this point Minstrel was a fairly mature program, and my work was focused mainly on looking at different issues in the general areas of storytelling and creativity, tweaking Minstrel to try out different approaches, and capturing those results for my thesis. I had also gotten tired of being a perpetual graduate student, so I hammered out an outline for my thesis with Mike and agreed on a writing timetable. I began churning out chapters for the thesis, usually finishing about a chapter a month, and then submitting them to Mike for review.

Unfortunately, I got no feedback from Mike. At this point, I was rarely on campus, and when I was, Mike was usually nowhere to be found. And he was completely gone — out of the country — for the entire summer. Through other faculty and his remaining students I heard that he was having a difficult time and seemed depressed. There was little I could do except submit my chapters and hope that he would eventually review them. Another difficulty was that when I did manage to find Mike we usually ended up talking about humor. I had a quick funny wit, and Mike was fascinated with how to build a model of computer humor. I always enjoyed these conversations — Mike at his brilliant best — but they didn’t help advance my thesis.

I wrote my thesis using LaTeX and a set of macros that David Smallberg had written to meet the UCLA filing requirements. As my thesis grew it got cumbersome to keep it as a monolithic file, so I split it into chapters and worked each chapter separately, figuring that I could stitch it all together with the appropriate page numbers when I finished. So I was focused on each piece as I wrote it and never really looked at in the whole.

After more than a year of writing I was nearing the end of what I planned to include in the thesis. When I was able to talk with Mike about problems in the thesis, he would always suggest ways to extend the thesis to address the problems. For example, when I worried about whether the Minstrel model of creativity would be seen as only applicable in storytelling, he suggested applying Minstrel’s creativity algorithms to mechanical invention (an area the Jack Hodges was also touching upon in his work). Sometimes it seemed that meeting with Mike resulted in backwards progress on my thesis. Finally I convinced Mike to have a serious sit-down to talk about my thesis and how to finish up.

We met in his office and I mentioned that I hadn’t received any feedback on the chapters I’d submitted. Was there some problem?

“No, no problem,” he said. “I’ve got them here somewhere.” He dug around in a corner of the office and came up with a dusty pile of my printed chapters. “I’ve read them,” he said. “They seem pretty good to me. Here…” He handed me the pile. “I’ve made some comments.”

I took the pile. It was four or five chapters. I flipped through a few of the chapters. The introduction chapter was fairly marked up. There were few comments on the other chapters.

“Okay,” I said. “I’ll incorporate these comments. What about the rest of the chapters?”

“There’s more?” he said. He looked a little surprised.

“Yes,” I said. “This is only about a third of the thesis.”

“Oh. Well, send me the rest and I’ll read them.”

“So,” I asked, “how much more do you think I need to do to complete the thesis?”

“Oh,” Mike said, waving at the chapters in front of me, “I think that’s plenty right there. Just add a Conclusions chapter.”

I stared at him in disbelief. “Mike,” I said, “I finished these chapters nine months ago. Why didn’t you tell me then that was enough?”

“Oh,” he said, “I thought you were just enjoying the research.”

By the end of the meeting we’d managed to hammer out a schedule for submitting the thesis and scheduling the final oral exam.

Mike’s obsession with computer humor nearly derailed my oral defense. It was the tradition in the defense for the student’s advisor to open the exam by giving the student some softball questions to start the exam on the proper note and give the student some time to relax. For my exam, Mike decided to ask me questions about computer humor. (Never mind that the topic had little to do with my thesis; Mike didn’t believe in such petty limits for oral exams.) However well-intentioned this was, Mike became engrossed in my answers and we were soon having a very detailed and technical discussion of some of the issues and approaches for computer humor. More than once Mike got up to draw on the whiteboard where I was working. This went on for about an hour, with the other members of my committee looking on at first with amusement (most of them well aware of Mike’s proclivities) and then with growing impatience. Finally, David Jefferson turned to Mike and said “Mike, it’s time for you to shut up and let the committee do its job.” Mike blinked once or twice and sat back with a bit of sheepish smile. Maybe because of that start, the rest of the committee was also very aggressive, asking tough questions with tenacious follow-ups.

As soon as the exam ended I cornered Mike and said, “I thought you were going to piss off my committee so much they would fail me!” Mike handed me my signature sheet — pre-signed. “Oh, everyone signed before you came in,” he replied. “In fact they didn’t want to bother with the oral exam. But I asked them to stay and give you a real grilling to see how you would do.”

All told, my exam ended up lasting two and a half hours instead of the scheduled 45 minutes. By the time I came out the rest of the AI Lab students were milling around in a near panic. They had no idea what had happened, but they feared the worst. Since it was well-known that Mike was happy with my work, it didn’t bode well for them, and they had visions of their own exams being indefinitely postponed until they were “better prepared” than I had been. They were probably more relieved than I to find out the true story.

After the exam I printed out my entire thesis for the first time. (I’d only given my committee members selected chapters and an offer to provide the entire thesis — which no one accepted.) I was shocked to discover that it was over 800 pages long. It was the longest Ph.D. thesis in the history of the UCLA CS Department.

The Department did not provide copying for thesis submittal, so I lugged the entire 800+ pages over to the local Kinkos and had the requisite six copies made, for about $500 (which I could ill afford at the time). Then I tramped the entire load up to the UCLA library for filing. Behind me in the filing line was a young woman from the Sociology Department holding a slim thesis. “You might be here a while,” I warned her.

A fastidious librarian examined every page of my thesis for problems. Halfway through she suddenly stopped and circled the page number at the beginning of a chapter. “You’ve duplicated a page number here,” she announced. “Is that a problem?” I asked. “Yes,” she said, “you’ll have to renumber the pages.”

That was the only problem she found in the entire thesis, but it required re-printing and re-copying about 400 pages of the thesis, to the tune of another $300.

I submitted my thesis to a couple of book companies and LEA expressed interest. They asked me to reduce the thesis to under 300 pages, which I managed, and “The Creative Process” was published in 1994.

All in all, I spent about ten years working on creativity, storytelling and Minstrel. I was lucky enough to be able to work on a fascinating topic with some brilliant people, and I certainly count it amongst the highlights of my life.

3 Responses to “The Context of Minstrel‘s Creation”

  1. andrew Says:

    Wow, thanks for this Scott, it’s a fun and fascinating read.

  2. Matthew Merzbacher Says:

    Scott’s memory of the programming contest overlaps, but is not quite the same with mine. The thing I most remember was that we placed THIRD in our region before going to the (inter)nationals (at that time, there were only a couple of non-US teams, so I’ll call them “finals” from now on instead of the inaccurate “nationals” or misleading “internationals”). Normally, a region sent two teams to the finals. We had hoped to place second behind a very strong CalTech team and were packing up to go home when they told us that we’d be going because we had come third to TWO CalTech teams, and a school could only send one team to the finals. Thus, it took some rules luck to even go to the finals.

    We fully expected to place only moderately well at the finals (maybe top 10), so we spent the day before the finals in Mammoth Caves (Kentucky) and goofing off, instead of getting nervous. When we got the problems for the finals, we divided them up. Seth Goldman took one problem, “It’s just I/O hacking” he said, while Alex, Scott, and I took others (and we left a couple to sit). I finished my problem pretty quickly (after coding in “C” for years, dropping back to Pascal was a bit challenging – do YOU remember how Pascal functions return values?). I saw that another problem had been solved by several teams, so I picked that one up – it turned out to LOOK hard, but easily be solved by a greedy solution. That’s a common characteristic of contest problems.

    Anyhow, Alex got his problem and I picked up another. Meanwhile, Seth had switched problems. He kept saying, “That damned I/O problem *should* be solvable, but it looks like it’ll take hours.” Little did he know – we never even tried to solve that problem (beyond Seth reading through it).

    One of the most surprising things about the contest was how poorly the (remaining) CalTech team (and several other ‘heavyweights’ – e.g., MIT) had fared. After all, CalTech had wiped us out in the regionals. I later asked their coach (a friend of mine) what had happened – they solved only one or two problems.

    He said, “Well, the good teams know that it’s all about who can solve the problems FASTEST and not just who can solve the most, since the top teams always get ALL the problems. They saw the I/O problem and realized that it was going to take a long time, so they spent all but the last hour of the contest working on it. Only then did they realize that they wouldn’t finish it, or (as a result), any others.”

    There’s a great lesson in project management therein, I think. By identifying a problem as essentially insoluble given our constraints, we did the best alternative and ended up “winning”.

  3. Grand Text Auto » Fa├žade, Petz, and The Expressivator Says:

    […] fiction systems, including James Meehan’s Tale-Spin (1 2), Scott Turner’s Minstrel (1 2), and Michael Lebowitz’s Universe (1). Now I’m pleased to continue the series with some […]

Powered by WordPress