AI Expert Newsletter

2002 November

• From the Editor
• News
• 2002 Person vs. Program Chess Championship
• 1738 Artificial Duck
• Articles
• Computer Chess: the Drosophila of AI
• Links
• General AI
• Computer Chess

Welcome to the Premier Issue

Welcome to Dr. Dobb's AI Expert Newsletter. Before you begin to talk about Artificial Intelligence (AI), you have to deal with the name itself. It leads to impassioned philosophical debates, like those raging right now on the AI Forum, and inspires some great science fiction. (The Hyperion Trilogy by Dan Simmons is my favorite, based on Tom Ray's fascinating Tierra project, but that's for a later newsletter.)

Debates on machine vs. human intelligence are fun, but this newsletter needs a working definition of AI that more realistically encompasses the wide variety of fascinating software and hardware usually classified as AI. So we'll define it in terms of computer nature rather than human nature:

Artificial Intelligence (AI) is the art and science of making computers do interesting things that are not in their nature.

What is a computer's nature? Well it has memory that's good for storing data and a CPU that processes sequences of instructions. If you have a problem that requires automating data storage, procedures or both i.e. data processing, then computers are perfect. Other types of problems are trickier.

Consider Mycin, one of the earliest AI programs. The developers were posed with the problem of trying to automate medical diagnostic knowledge that was best expressed as rules.

The rules were neither data or procedures. Trying to force them as either was untenable for any significant body of knowledge. So what could they do?

The answer lies in the words of some long forgotten hardware engineer:

"Software is a kludge for getting around design flaws in the hardware."

What the Mycin developers really needed was a new kind of computer: one that processed rules. So they created a virtual machine, they called it an inference engine, whose nature was ideal for processing knowledge expressed as diagnostic rules.

People in the AI field have been doing the same thing ever since, creating virtual machines that are programmed in non-conventional ways, and using those machines to perform previously untenable programming tasks.

Which leads to the problem with an AI newsletter. There isn't a common language, like Java or C++ that is used for AI applications, nor are there standards like SQL for database access, or HTML for Web browsers.

Nor are these virtual machines similar. The classic ones deal with a wide variety of rule languages and reasoning algorithms, while others deal with semantic networks, neural networks, ontological knowledgebases, genetic algorithms, artificial life, robot brains, cellular automata and, of course, games.

And then, given a specific area of AI one can write about how to build the tool, or write about applications of the tool. The former is solid programmer stuff; the latter requires some knowledge of the specific tool, which is often a commercial product.

So I'm asking for your input. There is a wealth of fascinating subject matter that this newsletter can cover, and I'd like to know what your interests and experiences are. Send me e-mail. Tell me what you're currently doing with AI and what you'd like to see covered in the AI Expert Newsletter. I want the newsletter to meet your interests.

dennis@ddj.com

News

It's a Tie!

Brains in Bahrain was the latest man-machine chess showdown of champions, pitting Kramik (a human) against Deep Fritz (a software program). Kramik won the early matches in what was called a triumph of anti-computer strategy. Deep Fritz won the later matches in what was called a triumph of anti-human strategy.

Chess playing has often been considered an ultimate test of machine intelligence because it is too complex to be mastered using straight-forward search algorithms. That is, the search space of possible moves is too great to be explored by a machine.

Early researchers worked on encoding the essence of grandmaster reasoning to improve performance. They learned, for example, that grandmasters had greater "pattern vocabularies" than weaker players. They didn't reason faster than weaker players, but more efficiently because they were reasoning using larger chunks of knowledge.

With the speed of today's machines, the value of the brute-force search in chess had become more important. Its ironic that in this classic test of machine intelligence, computers are playing on a par with the best humans more by exploiting the natural strengths of computers, and less by the application of human-like intelligence. Intelligent or not, today's top chess programs are masterpieces of software engineering.

It is interesting to note that Deep Fritz is not Deep Blue, which was dismantled after defeating Kasparov in the last man-machine chess championship. Deep Blue was an amazing mix of specialized parallel processing hardware and software capable of searching 200 million moves per second. Deep Fritz is a souped up commercial product from ChessBase running on stock hardware capable of only 3 million moves per second. They claim it's smarter though.

As for humans, with their feeble CPUs, they still provide stiff competition for millions-of-moves-per-second machines. It all appears to revolve around superior recognition and processing of patterns. And when you take a heavily pattern-oriented game like go, well computers aren't even close, yet.

1738 Artificial Duck

Dr. Jessica Risken of Standord University has done a study of a mechanical duck built in 1738 that created the same interest and excitement as current experiments in artificial life. The parallels between their desire to use mechanized models to understand real life, and ours, are fascinating.

Among other things, the duck was realistic in that it ate and pooped. But if you looked inside, it sort of cheated. Food went in, and time passed, and poop came out, but the input food was still there, and the poop had been pre-loaded. So the duck didn't really digest, it just looked like it did.

That is not dissimilar from the chess programs that look like they understand the patterns on the board, but instead are processing millions of individual moves.

But also like the chess programs, the duck was an amazing bit of engineering and probably a lot of fun to build.

Articles

AI Expert Magazine, this newsletter's namesake and inspiration, was one of the premier magazines covering AI in the early 1990s. Considering the quality of the magazine, it probably comes as no surprise that we can still learn from many of the articles published a decade or more ago. To that end, every month we'll be publishing an article or two from AI Expert on Dr. Dobb's Journal's AI Expert Web site. If you recall a favorite AI Expert article you'd like to see, let us know.

Computer Chess: the Drosophila of AI by L. Stephen Coles. Chess has been called the fruit fly of AI research. This in depth article covers the history of chess playing machines from a 1770 mechanical automaton (like the duck!) to Deep Blue.

Links

General AI

The American Association of Artificial Intelligence (AAAI) is a non-profit scientific organization devoted to supporting AI research and development. They have conferences and journals and an excellent Web site that introduces AI research and topics.

John McCarthy of Standord University has one of the great minds of AI and is one of AI's founders. See his views on what AI is at his What is AI Web site. He's got some ideas in there on computer chess as well.

Carnegie Mellon AI Repository has a large collection of AI software, resources and links, although some are out of date. Included in the resources is a directory of major AI resources.

The MIT Media Lab's Web site list describes a large number of fascinating research projects.

Kurzweil's AI site has numerous papers, books and discussions of the deepest issues with intelligent machines.

Dr. Dobb's Journal's AI Topics Web site has a number of interesting links to sites, papers, books and FAQs, as well as a discussion forum.

PCAI magazine has a wealth of information about AI technologies and products on their Web site.

Chess

The alpha-beta search algorithm is the core technology for two player games. It finds the best move for each player by examining a tree of possible future moves. The link is to some excellent course materials at McGill University.

The International Computer Games Association (ICGA) Web site has a tremendous amount of information on computer chess and other games. In particular, check out the excellent article anatomy of a chess program with its in depth description of the design of chess programs.

The Enpassant Chess Club has a long list of free chess programs and related tools, with short descriptions of each. Some are available with source code.

Chessopolis has a longer list of free chess programs as well as a directory and reviews of commercial chess programs.

Beowulf is a full open source chess program with the admirable goals of 1) being a competitive program, and 2) having clearly commented and written code ideal for learning about and tinkering with a chess program.