Hampshire Student Uses J.K. Rowling's Quidditch as Basis for Artificial Intelligence Experiment
Although enrolled in Hampshire College, not Hogwarts Academy, Raphael Crawford-Marks has spent the past year fine-tuning his Quidditch skills. Crawford-Marks - set to graduate on May 22 - has created a computerized version of the rapid-fire game played by young witches and warlocks in J.K. Rowling's series of Harry Potter novels. But Crawford-Marks is doing far more than playing a video game: he's running an artificial intelligence experiment that involves computerized generation of teams that either proceed in competition or fall by the wayside according to their ability to adapt to the Quidditch environment.
Put simply, teams evolve rather than being hand coded into the computer. Players are never directly told what to do. In Darwinian terms, teams learn what behavior is desirable by surviving and their desirable traits get passed along in the evolutionary process.
In Crawford-Marks' project, titled "Virtual Witches and Warlocks: Computational Evolution of Teamwork and Strategy in a Dynamic, Heterogeneous and Noisy 3-D Environment," two separate computer programs talk to one another. One is a Quidditch simulator with a built-in fitness function that evaluates each team's performance and likelihood to produce sought-after results, such as scoring a goal. A smaller program generates teams one by one - setting up players in roles as chasers, beaters and seekers - and passes them into the game. Those who perform well survive to play another day and their desirable traits pass on to following generations.
In order to graduate, every Hampshire College student must complete a yearlong independent project and thesis, called the Division III. Crawford-Marks picked his Quidditch project after a classroom comment by computer science professor Lee Spector, who suggested during a seminar on evolutionary computation that Quidditch could pose an interesting artificial intelligence problem. Spector and two of his former students had presented a paper on the pedagogical possibilities of virtual Quidditch as a "challenge problem" at the 2001 Genetic and Evolutionary Computation Conference. For Crawford-Marks, who had taken two years off from college to work as a computer programmer in his hometown of San Francisco and whose other academic interests are film and creative writing, it sounded like the perfect problem and he ran with the idea.
Crawford-Marks became a fan of the Harry Potter books after he got interested in the challenge Spector posed. He read them for the first time last year, in Spanish while studying in Spain.
Rowling need fear no encroachment on her copyrighted territory: Crawford-Marks is using Quidditch only as an academic project and is being scrupulous in his documentation.
He is similarly careful in documenting the work of others. He is indebted to RoboCup soccer, which uses soccer as a model for the evolution of teams of cooperating agents and is considered a benchmark in artificial intelligence. "Virtual Witches and Warlocks" pushes past some limitations in RoboCup, which runs at real time, with one second in the game equivalent to one second in real life. Fittingly for Quidditch, Crawford-Marks' project must run much faster than real time in order for the programs to evaluate the hundreds to possibly thousands of players necessary for successful evolution.
"Virtual Witches and Warlocks" is built on a simulation environment called Breve, the Division III creation of another former Spector student named Jon Klein. And, the Quidditch-playing programs are constructed in a computer language called Push, invented by Spector, and developed further by Spector, Klein and another Hampshire professor, Chris Perry, who works in computer animation.
Crawford-Marks now calls his earliest work "kiddy Quidditch," as it evolved teams that played like he thinks six-year-olds might. But, now well past the 50th generation it starts to look a little more like Rowling's game, with a practically uncatchable Snitch.
He hopes to present a paper about his project at the next Genetic and Evolutionary Computation Conference, along with his mentor Spector. Spector chairs the Hampshire faculty committee overseeing Crawford-Marks' academic work, and the Quidditch project is running on a big "Beowulf-style" cluster computer funded through a National Science Foundation grant to Spector, who was one of six professors nationwide recognized last year by the NSF as Distinguished Teaching Scholars. Computer science professor Jaime Davila is also on Crawford-Marks' faculty committee.
In addition to being a lot of fun, the Quidditch project enabled Crawford-Marks to master a range of computer science skills - development, design, programming, data analysis - and integrate them into a coherent research program. At the same time, he explored processes of co-evolution, genetic representation and evolution of teamwork.
Now that he's become an artificial intelligence wizard, Crawford-Marks plans to attend graduate school in computer science in a couple of years, but in the meantime will pursue creation of life in a slightly different form by working on his creative writing.
Virtual Quidditch Challenge Problem
"Virtual Quidditch: A Challenge Problem for Automatically Programmed Software Agents," by Lee Spector, Ryan Moore and Alan Robinson in Late-Breaking Papers of GECCO-2001, the Genetic and Evolutionary Computation Conference.