UCSD Jacobs School of Engineering University of California San Diego
Pulse Subscribe | Archive | Survey
 
Playing at the Edge of A.I.

Meet Blondie24, a 24-year-old UCSD co-ed who learned to play checkers while she was laid up from a skiing accident. She became a popular player on Microsoft's Zone.com, and quickly earned expert-level status as she logged one win after another. When the New York Times reported on her success in July 2000, Blondie24 gained overnight notoriety as one of the first computer programs that literally taught itself how to play checkers better than most humans through the application of evolutionary computation.

Blondie24 is the creation of Jacobs School alumni David Fogel (M.S. '90, Ph.D., '92 engineering sciences) and Kumar Chellapilla, (Ph.D., electrical engineering '02).

"We did this project on our own time, weekend after weekend, with one computer and no funding. Our real impetus was to demonstrate that the evolutionary computation approach, which is a simple concept of capturing Darwin's random variation and selection on a computer, can generate incredible solutions to problems we don't have the answers to already," says Fogel. Blondie24 started out as 30 random neural network models, each of which was programmed to follow the rules of checkers, but was not instructed on strategy or even the object of the game. The models were pitted against each other, and in a survival of the fittest scenario, the 15 that played the best games of checkers survived and were cloned with slight mutations to form the next generation, while the less successful nets were killed off.

"After 10 generations, Kumar and I both played the best nets we had, and we both lost two games in a row. Then we looked at each other and admitted that we stink at checkers," says Fogel. After 800 generations, Fogel began playing the neural nets against stiffer human competition on the Zone.com website. Interestingly, he quickly realized that persona matters, and switched from the handle David1101 (who nobody wanted to play) to Obi_WanTheJedi (who drew interest, but was the target of bad sports) and finally settled on Blondie24, a character that was popular with both men and women. Blondie24 went on to win several competitive tournaments.

The evolutionary computation ideas behind Blondie24 have been the driving inspiration for Fogel's work since his days as a UCSD graduate student. He has written more than 200 scientific articles and six books on the subject, and received the 2004 IEEE Kiyo Tomiyasu Award for his contributions to the field. Computational intelligence is also the core of Fogel's family business, Natural Selection, Inc., which has developed programs to speed the drug discovery process, optimize scheduling for corporations such as Levi Strauss and Chevron, and even train military personnel in war game scenarios.

"A.I. work has primarily been pursued through universities and national laboratories, but it has a very broad commercial potential to help solve any problem where a solution can be optimized and a process can be improved," says Fogel.

He cites work his company did in collaboration with Pfizer Inc.'s La Jolla Laboratories (formerly Agouron Pharmaceuticals, Inc.). Pfizer seeks to identify molecules that bind, or "dock" to, the active site of a target protein. Finding potential drug candidates is difficult because there are millions of molecules to choose from, and each molecule can take on diverse conformations. It is impossible to computationally enumerate all of the possible solutions. Fogel worked with Pfizer to develop an evolutionary algorithm to optimize the conformation for each tested molecule within the binding site of the target protein, through an iterative process of random variation and selection. The program allows Pfizer to quickly screen through candidate molecules and focus on the most promising leads for further research.

"The screening program we developed has become part and parcel of Pfizer's drug discovery tools," says Fogel.

Today Natural Selection, Inc. is a fairly small firm with 14 employees and $2 million in annual revenues. Fogel says the company's future business model will revolve around spin-off software products for financial forecasting, bioinformatics, and homeland security.

As for Blondie24, she's retired from competitive checkers play and has moved on to chess. Fogel chronicles her exploits in his book "Blondie24: Playing at the Edge of AI" (2002, Morgan Kaufmann Publishers). It was the publicity raised by Blondie24 that brought Fogel to the attention of video game veterans Doug Johnson and Tom Lang, formerly with Quadra Interactive. Johnson and Lang had been searching for technology to create games with intelligent, life-like beings that could act and learn on their own.

"Doug found me through his research on the Web. It turns out that I was just two blocks up the road from where he lives in La Jolla," says Fogel.

In 1999, the three teamed up to start Digenetics, Inc. as a sister company to Natural Selection. Digenetics has two games on the market, Chess with an Attitude and Checkers with an Attitude, both of which feature computer personas who look, act, and play like real people. For those who don't like the idea of being beaten mercilessly by a cheeky 14-year-old, there are several levels of play from novice to senior master. For now, the games are only available on the Digenetics website www.digenetics.com and in other limited venues. Fogel says Natural Selection has already received support from the National Science Foundation's Small Business Innovation Research (SBIR) program to create a third-party software developer's kit to support creating evolutionary characters. So video game enthusiasts can watch for Fogel's technology to be incorporated into a variety of games in the future.