Artificial Intelligence FAQ

Table of contents

1) What is AI? 2) What's the difference between strong AI and weak AI? 3) I'm a programmer interested in AI. I'm writing a game that needs AI. Where do I start? 4) What's an agent? 5) What has AI accomplished? 6) What are the branches of AI? 7) What are good programming languages for AI? 8) What's the difference between "classical" AI and "statistical" AI? 9) What do the following terms mean? 10) I'm a student considering further study AI. What information is there for me? 11) What are best graduate schools for AI? 12) Where can I find conference information? 13) How can I get the email address for Joe or Jill Researcher? 14) What does it mean to say a 2-player game is 'solved'? Is tic-tac-toe solved? How about game z?

What is AI?

Artificial intelligence ("AI") can mean many things to many people. Much confusion arises that the word 'intelligence' is ill-defined. The phrase is so broad that people have found it useful to divide AI into two classes: strong AI and weak AI.

What's the difference between strong AI and weak AI?

Strong AI makes the bold claim that computers can be made to think on a level (at least) equal to humans. Weak AI simply states that some "thinking-like" features can be added to computers to make them more useful tools... and this has already started to happen (witness expert systems, drive-by-wire cars and speech recognition software). What does 'think' and 'thinking-like' mean? That's a matter of much debate.

I'm a programmer interested in AI. I'm writing a game that needs AI. Where do I start?

It depends what the game does. If it's a two-player board game,look into the "Mini-max" search algorithm for games (see [4-1]). In most commercial games, the AI is is a combination of high-level scripts and low-level efficiently-coded, real-time, rule-based systems. Often, commercial games tend to use finite state machines for computer players. Recently, discrete Markov models have been used to simulate unpredictible human players (the buzzword compliant name being "fuzzy" finite state machines).

A recent popular game, "Black and White", used machine learning techniques for the non-human controlled characters. Basic reinforcement learning, perceptrons and decision trees were all parts of the learning system. Is this the begining of academic AI in video games?

What's an agent?

A very misused term. Today, an agent seems to mean a stand-alone piece of AI-ish software that scours across the internet doing something "intelligent." Russell and Norvig define it as "anything that can can be viewed a perceiving its environment through sensors and acting upon that environment through effectors." Several papers I've read treat it as 'any program that operates on behalf of a human,' similar to its use in the phrase 'travel agent'. Marvin Minsky has yet another definition in the book "Society of Mind." Minsky's hypothesis is that a large number of seemingly-mindless agents can work together in a society to create an intelligent society of mind. Minsky theorizes that not only will this be the basis of computer intelligence, but it is also an explaination of how human intelligence works. Andrew Moore at Carnegie Mellon University once remarked that "The only proper use of the word 'agent' is when preceded by the words 'travel', 'secret', or 'double'."

What has AI accomplished?

Quite a bit, actually. In 'Computing machinery and intelligence.', Alan Turing, one of the founders of computer science, made the claim that by the year 2000, computers would be able to pass the Turing test at a reasonably sophisticated level, in particular, that the average interrogator would not be able to identify the computer correctly more than 70 per cent of the time after a five minute conversation. AI hasn't quite lived upto Turing's claims, but quite a bit of progress has been made, including:

- Deployed speech dialog systems by firms like IBM, Dragon and Lernout&Hauspie

- Financial software, which is used by banks to scan credit card transactions for unusual patterns that might signal fraud. One piece of software is estimated to save banks $500 million annually.

- Applications of expert systems/case-based reasoning: a computerized Leukemia diagnosis system did a better job checking for blood disorders than human experts.

- Machine translation for Environment Canada: software developed in the 1970s translated natural language weather forcasts between English and French. Purportedly stil in use.

- Deep Blue, the first computer to beat the human chess Grandmaster

- Physical design analysis programs,such as for buildings and highways.

- Fuzzy controllers in dishwashers, etc.

One persistent 'problem' is that as soon as an AI technique trully succeeds, in the minds of many it ceases to be AI, becoming something else entirely. For example, when Deep Blue defeated Kasparov, there were many who said Deep Blue wasn't AI, since after all it was just a brute force parallel minimax search (!)

What are the branches of AI?

There are many, some are 'problems' and some are 'techniques'.

Automatic Programming - The task of describing what a program should do and having the AI system 'write' the program.

Bayesian Networks - A technique of structuring and inferencing with probabilistic information. (Part of the "machine learning" problem).

Constraint Statisfaction - solving NP-complete problems, using a variety of techniques.

Knowledge Engineering/Representation - turning what we know about particular domain into a form in which a computer can understand it.

Machine Learning - Programs that learn from experience or data.

Natural Language Processing(NLP) - Processing and (perhaps) understanding human ("natural") language. Also known as computational linguistics.

Neural Networks(NN) - The study of programs that function in a manner similar to how animal brains do.

Planning - given a set of actions, a goal state, and a present state, decide which actions must be taken so that the present state is turned into the goal state

Robotics - The intersection of AI and robotics, this field tries to get (usually mobile) robots to act intelligently.

Speech Recogntion - Conversion of speech into text.

Search - The finding of a path from a start state to a goal state. Similar to planning, yet different...

Visual Pattern Recognition - The ability to reproduce the human sense of sight on a machine.

AI problems (speech recognition, NLP, vision, automatic programming, knowledge representation, etc.) can be paired with techniques (NN, search, Bayesian nets, production systems, etc.) to make distinctions such as search-based NLP vs. NN NLP vs. Statistical/Probabilistic NLP. Then you can combine techniques, such as using neural networks to guide search. And you can combine problems, such as posing that knowledge representation and language are equivalent. (Or you can combine AI with problems from other domains.)

What are good programming languages for AI?

This topic can be somewhat sensitive, so I'll probably tread on a few toes, please forgive me. There is no authoritative answer for this question, as it really depends on what languages you like programming in. AI programs have been written in just about every language ever created. The most common seem to be Lisp, Prolog, C/C++, recently Java, and even more recently, Python.

LISP- For many years, AI was done as research in universities and laboratories, thus fast prototyping was favored over fast execution. This is one reason why AI has favored high-level langauges such as Lisp. This tradition means that current AI Lisp programmers can draw on many resources from the community. Features of the language that are good for AI programming include: garbage collection, dynamic typing, functions as data, uniform syntax, interactive environment, and extensibility. Read Paul Graham's essay, "Beating the Averages" for a discussion of some serious advantages: http://www.paulgraham.com/avg.html

PROLOG- This language wins 'cool idea' competition. It wasn't until the 70s that people began to realize that a set of logical statements plus a general theorem prover could make up a program. Prolog combines the high-level and traditional advantages of Lisp with a built-in unifier, which is particularly useful in AI. Prolog seems to be good for problems in which logic is intimately involved, or whose solutions have a succinct logical characterization. Its major drawback (IMHO) is that it's hard to learn.

C/C++- The speed demon of the bunch, C/C++ is mostly used when the program is simple, and excecution speed is the most important. Statistical AI techniques such as neural networks are common examples of this. Backpropagation is only a couple of pages of C/C++ code, and needs every ounce of speed that the programmer can muster.

Java- The newcomer, Java uses several ideas from Lisp, most notably garbage collection. Its portability makes it desirable for just about any application, and it has a decent set of built in types. Java is still not as high-level as Lisp or Prolog, and not as fast as C, making it best when portability is paramount.

Python- This language does not have widespread acceptance yet, but several people have suggested to me that it might end up passing Java soon. Apparently the new edition of the Russell-Norovig textbook will include Python source as well as Lisp. According to Peter Norvig, "Python can be seen as either a practical (better libraries) version of Scheme, or as a cleaned-up (no $@&%) version of Perl." For more information, especially on how Python compares to Lisp, go to http://norvig.com/python-lisp.html

Also see section [6-1] for implementations of new languages that might be pertainant to AI practitioners and researchers.

(some of the above material is due to the comp.lang.prolog FAQ, and Norvig's "Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp")

What's the difference between "classical" AI and "statistical" AI?

Statistical AI, arising from machine learning, tends to be more concerned with "inductive" thought: given a set of patterns, induce the trend. Classical AI, on the other hand, is more concerned with "deductive" thought: given a set of constraints, deduce a conclusion. Another difference, as mentioned in the previous question, is that C++ tends to be a favourite language for statistical AI while LISP dominates in classical AI.

A system can't be truely intelligent without displaying properties of both inductive and deductive thought. This lends many to beleive that in the end, there will be some kind of synthesis of statistical and classical AI.

What do the following terms mean?

This is the start of a simple glossary of short definitions for AI terminology. The purpose is not to present the gorey details, but give ageneral idea.

• A*:

A search algorithm to find the shortest path through a search space to a goal state using a heuristic. See 'search', 'problem space', 'Admissibility', and 'heuristic'.

Admissibility: An admissible search algorithm is one that is guaranteed to find an optimal path from the start node to a goal node, if one exists. In A* search, an admissible heuristic is one that never overestimates the distance remaining from the current node to the goal.

• Agent:

"Anything that can can be viewed a perceiving its environment through sensors and acting upon that environment through effectors." [Russel, Norvig 1995]

• ai:

A three-toed sloth of genus Bradypus. This forest-dwelling animal eats the leaves of the trumpet-tree and sounds a high-pitched squeal when disturbed. (Based on the Random House dictionary definition.)

• Alpha-Beta Pruning:

A method of limiting search in the MiniMax algorithm. The coolest thing you learn in an undergraduate course. If done optimally, it reduces the branching factor from B to the square root of B.

• Animat Approach:

The design and study of simulated animals or adaptive real robots inspired by animals. (From www-poleia.lip6.fr/ANIMATLAB - click on "English page")

• Backward Chaining:

In a logic system, reasoning from a query to the data. See Forward chaining.

• Belief Network (also Bayesian Network):

A mechanism for representing probabilistic knowledge. Inference algorithms in belief networks use the structure of the network to generate inferences effeciently (compared to joint probability distributions over all the variables).

• Breadth-first Search:

An uninformed search algorithm where the shallowest node in the search tree is expanded first.

• Case-based Reasoning:

Technique whereby "cases" similar to the current problem are retrieved and their "solutions" modified to work on the current problem.

• Closed World Assumption:

The assumption that if a system has no knowledge about a query, it is false.

• Computational Linguistics:

The branch of AI that deals with understanding human language. Also called natural language processing.

• Data Mining:

Also known as Knowledge Discovery in Databases (KDD) was been defined as "The nontrivial extraction of implicit, previously unknown, and potentially useful information from data" in Frawley and Piatetsky-Shapiro's overview. It uses machine learning, statistical and visualization techniques to discover and present knowledge in a form which is easily comprehensible to humans.

• Depth-first Search:

An uninformed search algorithm, where the deepest non-terminal node is expanded first.

• Embodiment:

An approach to Artificial Intelligence that maintains that the only way to create general intelligence is to use programs with 'bodies' in the real world (i.e. robots). It is an extreme form of Situatedness, first and most strongly put forth by Rod Brooks at MIT.

• Evaluation Function:

A function applied to a game state to generate a guess as to who is winning. Used by Minimax when the game tree is too large to be searched exhaustively.

• Forward Chaining:

In a logic system, reasoning from facts to conclusions. See Backward Chaining

• Fuzzy Logic:

 In Fuzzy Logic, truth values are real values in the closed interval [0..1]. The definitions of the boolean operators are extended to fit this continuous domain. By avoiding discrete truth-values, Fuzzy Logic avoids some of the problems inherent in either-or judgments and yields natural interpretations of utterances like "very hot". Fuzzy Logic has applications in control theory.

• Generate and Test:

The basic model for performing search in any search space.

"The purest form of `generate and test' is: 1. generate all the possible [options] that I would even remotely consider taking next, 2. test each [option] in the generated set to filter out bad ones, and possibly to prioritize the rest. How much you move away from this "pure" form depends on how much of the testing you try to move into the generation stage. What we often strive for in intelligent systems is: 1. generate only the most appropriate action 2. no testing is needed But what we usually end up with is: 1. generate only the best candidates (moving some of the testing conditions into the generator), 2. perform a more strenuous test on the small set of generated actions, for a final selection" -Randolph_M._Jones <rjones@colby.edu>

• Heuristic:

The dictionary defines it as a method that serves as an aid to problem solving. It is sometimes defined as any 'rule of thumb'. Technically, a heuristic is a function that takes a state as input and outputs a value for that state- often as a guess of how far away that state is from the goal state. See also: Admissibility, Search.

• Information Extraction:

Getting computer-understandable information from human-readable (ie natural language) documents.

• Iterative Deepening:

An uninformed search that combines good properties of Depth-fisrt and Breadth-first search.

• Iterative Deepening A*:

The ideas of iterative deepening applied to A*.

• Language Acquisition:

A relatively new sub-branch of AI; traditionally computational linguists tried to make computers understand human language by giving the computer grammar rules. Language acquisition is a technique for the computer to generate the grammar rules itself.

• Machine Learning:

A field of AI concerned with programs that learn. It includes Reinforcement Learning and Neural Networks among many other fields.

• MiniMax:

An algorithm for game playing in games with perfect information. See alpha-beta pruning.

• Modus Ponens:

An inference rule that says: if you know x and you know that 'If x is true then y is true' then you can conclude y.

• Nonlinear Planning:

A planning paradigm which does not enforce a total (linear) ordering on the components of a plan.

• Natural Language (NL):

Evolved languages that humans use to communicate with one another.

• Natural Language Queries:

Using human language to get information from a database.

• Partial Order Planner:

A planner that only orders steps that need to be ordered, and leaves unordered any steps that can be done in any order.

• Planning:

A field of AI concerned with systems that constuct sequences of actions to acheive goals in real-world-like environments.

• Problem Space (also State Space):

The formulation of an AI problem into states and operators. There is usually a start state and a goal state. The problem space is searched to find a solution.

• Search:

The finding of a path from a start state to a goal state. See 'Admissibility', 'Problem Space', and 'Heuristic'.

• Situatedness:

The property of an AI program being located in an environment that it senses. Via its actions, the program can select its sensation input, as well as change its environment. Situatedness is often considered necessary in the Animat approach. Some researchers claim that situatedness is key to understanding general intelligence. (see Embodiment)

• Strong AI:

Claim that computers can be made to actually think, just like human beings do. More precisely, the claim that there exists a class of computer programs, such that any implementation of such a program is really thinking.

• Unification:

The process of finding a substitution (an assignment of constants and variables to variables) that makes two logical statements look the same.

• Validation:

The process of confirming that one's model uses measureable inputs and produces output that can be used to make decisions about the real world.

• Verification:

The process of confirming that an implemented model works as intended.

• Weak AI:

Claim that computers are important tools in the modeling and simulation of human activity.

I'm a student considering further study AI. What information is there for me?

Aaron Sloman has written an essay addressing this question, aimed at people who know little about it. Please see http://www.cs.bham.ac.uk/~axs/misc/aiforschools.html

What are best graduate schools for AI?

The short answer is: MIT, CMU, and Stanford are historically the powerhouses of AI and still are the top 3 today.

There are however, hundreds of schools all over the world with at least one or two active researchers doing interesting work in AI. What is most important in graduate school is finding an advisor who is doing something YOU are interested in. Read about what's going on in the field and then identify the the people in the field that are doing that research you find most interesting. If a professor and his students are publishing frequently, then that should be a place to consider.

Where can I find conference information?

Georg Thimm maintains a webpage that lets you search for upcoming or past conferences in a variety of AI disciplines. Check out: http://www.drc.ntu.edu.sg/users/mgeorg/enter.epl

How can I get the email address for Joe or Jill Researcher?

The AAAI membership directory is updated annually and contains addresses, phone numbers, and email addresses for many members of AAAI and other AI societies. Contact info@aaai.org for information on getting a copy of the directory (you should get a free copy if you are a member of one of the listed societies).

See also the Email Address FAQ posting to the newsgroups soc.college and soc.net-people.

The Artificial Intelligence and Molecular Biology Researchers database contains names, institutions, addresses, phone, fax, email, research interests and other related information about more than 200 researchers worldwide. The database is available via anonymous ftp from the lhc.nlm.nih.gov:/pub/aimb-db/ There are computer- and human-readable versions available. Get the README file for more information or send email to Larry Hunter, <hunter@nlm.nih.gov>.

E-mail addresses for members of the Linguistics Society of America (LSA) are available by anonymous ftp as linguistics.archive.umich.edu:/linguistics/LSA.email.list or by sending a message to listserv@tamvm1.tamu.edu with "get lsa lst linguist" in the message body.

A list of "Who's Who in Fuzzy Logic" may be obtained by sending a message to listserver@vexpert.dbai.tuwien.ac.at with GET LISTSERVER WHOISWHOINFUZZY in the message body. New entries and corrections should be sent to Robert Fuller <rfuller@finabo.abo.fi>.

WHO's On-Line is a WWW biographical database of folks on the internet. http://www.ictp.trieste.it/Canessa/ENTRIES/entries.html For more information, contact E. Canessa <canessae@ictp.trieste.it>.

The Association for Logic Program (ALP) membership list was published in the February 1994 issue of the newsletter (Volume 7/1). It will be made available by anonymous ftp from Imperial College in October 1994.

What does it mean to say a 2-player game is 'solved'? Is tic-tac-toe solved? How about game z?

We say a game is solved when we know for sure the result when both players play optimally. The result is either a guaranteed win for the first player, a guaranteed win for the second player, or a draw. We find this out by searching the mini-max game tree to the game ending positions. If you do this for 3x3 tic-tac-toe, it is easy to see that it is a forced draw.

other games:

• 3x3x3 tic-tac-toe: win for the first player.
• 4x4x4 tic-tac-toe: win for the first player.
• Connect-4: win for the first player.
• Go-Moku: win for the first player.