AUT CEIT AI Class - Spring 2009:

News:

  • Jun 6: Game map protocols are released. The map will follow this template. Here is an example and the meaning of it.
  • Feb 8: Page refreshed for new semester. Your assignment (game) will be World War (risk) and can be found here. The server will be released ASAP.

Guides:

  • Learn how to play World Wars(Attacks). Try to find the winning issues of the game such as strategic points, number of countries owned and ... . The rules of the game will be exactly the same of what is written in game help.

Assignments:

Game Definition:

  • The target of World Wars is gaining control over all territories on the map.
  • Game starts with a pre-created map on which all units are located. Your units will have role of each color once to complete the level.

  • Pay attention when a role assigned to you. You can alter your strategy or fitness function regarding the initial arrangements. For example you can have some playing moods to switch between: Greedy, Aggressive, Strategic, Freak, Conservative, Stable, Bloodthirsty, ...

  • You receive reinforcement at end of your turn (when you choose to end it). Received reinforcements are only from the biggest area of connected countries you have. If your units are next to each other on the map, it is easier to win.

  • Choose a territory of yours with two or more units on it to attack a neighboring enemy territory. The game compares results of dice rolling (number of rolls is equal to number of units). If the attacker result is better, (s)he obtains the attacked territory and all his(her) units apart from one are moved from the attacking to the attacked territory. There is no limit of attacks [er turn.

  • Each territory can have maximum of eight units within.
  • Reinforcements are placed in random spots occupied by your units, in the number equal to biggest number of combined territories you control.

Server:

Agent:

Human Judge:

League:

Bonuses:

Deadlines:

Information:

Game Scoring Policy:

Solution Methods:

  • Ant Colony Optimization
  • Particle Swarm Optimization
  • Genetic Algorithm
  • Simulated Annealing

Related Links:

Scores:

Will be filled gradually...


AUT CEIT AI Class - Fall 2008:

News:

  • May 16: See this brief explanation of how to develop a checkers player agent (Thanks to Eng. Majidfar for sharing hi handouts)
  • Jan 27: The league was held. View results and final scores.
  • January 18: The deadline for your reports and  agent code hand over is Saturday 25 Jan (5 Bahman). The league will be held on Monday 27 Jan (7 Bahman). Please gather in computer site before 9 o'clock.
  • January 3: If you feel you need another extra class, arrange it with your classmates and tell me to attend when and where.
  • December 28: An extra class were held.
  • December 22: Hey guys, start the project. It's kinda late...
  • December 3: New server patch available. Stay tuned with Server v1.1 and New Test Client. You should use graphics from old server pack.
  • November 30: Server v1.0 is released. This pack contains graphics required, server (.jar file), readme, and test client. For further assistant contact Eng. Hamekasi. Here You can find a time line for your project.
  • November 17: Guide page was launched for the semester.
  • November 17: The project was discussed in the classroom, along with scoring policy. The server for the game is still to be released and will be available soon. 

 

Guides:

  • Learn Checkers! Play it for yourself here.
  • Learn how to implement your desired solution framework (PSO, ACO, EA, SA) independent from your problem.
  • Test your framework with some sample fitness fuctions:
    • f(x) = (x-3)^2 , 0<x<6 (correctness of your code)
    • f(x) = x.sin(x) , 0<x<6 (local optima tolerance)
    • f(x) = 2 , 0<x<6 (plateau status)
  • Study current solutions for the game and extract criteria focused on, along with your innovative criteria.
  • Combining extracted criteria, form fitness function.
  • Write a generic agent with some methods implemented such as socket programming, world model(board) change track system,  interpret server commands, illegal move check routine, etc. Check this agent to work with server correctly with your own given moves (provide very simple user interface to test it manually).
  • Write a simple agent using search mechanisms (Greedy, Minimax, ...). Test your agent by connect it to both sides of board and debug it.
  • Eventually, embed your AI routine into your agent, debug it and test it with your friends.

Assignments:

Games Definitions:

  • Checkers is played on the dark squares of a 8x8 chess board only. A piece may move one square at a time, diagonally. If one of your pieces is next to one of your opponent’s pieces and the square beyond it is free, you are required to jump over the opponent’s piece. The opponent’s piece is then removed from the board. It is possible to jump many times in a row with the same piece, capturing several of your opponent’s pieces.
  • The black pieces always move first in Checkers.
  • In the beginning, pieces can only move and jump forward. However, if a piece reaches the far end of the board (in the case of the person playing black, the top), then it becomes a king. (In checkers, a king is usually signified by stacking two checkers one on top of the other.) A king is allowed to move and jump diagonally backwards and forwards. Kings can be captured like any other piece. 
  • You win by capturing all of your opponent’s pieces, or by blocking them so that they cannot move.
  • This is straight, American checkers. No long jumps. 
  • Checkers strategy is built around the idea that you force your opponent to jump in order to get them into a bad position, For example making a jump.

Server:

  • Server socket: IP:6060
  • First player who joins plays first(FCFS!) as black player.
  • Each player will be informed about turns by server using a Boolean variable. True means that it's your turn.
  • The move command format is 4 integers: First two are the X & Y of the selected piece, and the latter ones are for destination square.
  • You must specify only one jump in a move, if you can have another jump, the server gives you another turn and you should do it, i.e. it sends you another Boolean variable with true value. 
  • Each player get the confirmed move each turn, no matter that you played it or not. So both players know what is the last move (not the entire board). So if you made a move but didn't receive confirmation for about one time cycle (currently 0.5 second) so your move was illegal and you must try a new one.
  •  The game will be terminated, if no player wins before a certain number of moves (currently set as total 120 moves). In this case the game is considered as a Draw.
  • Addressing of the squares...Read the ReadMe in the server pack...
  • Server History:

Agent:

  • Your agent should be able to connect to server, giving it's Ip address.
  • The agent should play in both sides, black and white.
  • The agent should work correctly with server, no manual triggers is allowed during the test.
  • You can update your code once during the competitions. It's recommended that you keep this chance to repair unexpected bugs in your code.
  • In the case of a crash in the agent-side, no matter what it is, the agent loses the game, thus the points.
  •  Tricky moves are awarded as stated in Bonus section.
  • Erroneous moves take away one of bonuses, and will lead to a lost if continued.
  • Agents should not do incorrect moves repeatedly or the game is terminated by human judge, costing agent in charge 3 points.
  • Agent must be handed out in a stand-alone form (usually .exe or .jar) and in the source code form.
  • Agent source code should be documented inline for your own good.
  • Your agent can offer a draw at the moment, but it's wise to implement in your code. That can bring you a bonus.

Human Judge:

  •  Human judge tells you when to connect your agen and what is the IP.
  • He can give and take back bonuses to a player based on what is observed in agent behavior.
  • He decide where to terminate a game manually, punishing one agent. The main reasons to cut the game are:
    • Repeated erroneous moves of an agent (lose)
    • Time up for a move (lose)
    • Moves count of more than 120 moves (draw)
    • Server crash (rematch)
    • Agent crash (lose)
    • Network failure (rematch / lose)

League:

  • Each student have one team in the league. You can name it and that will add more taste to league. The league itself is called "Shahid Meshgi Cup"!
  • Each two teams, plays twice in the league; one as black player(host) and one as white player(guest).
  • Winner team gets 3 points, while no point is assigned to loser of the game. In the case of draw, both players achieve 1 point.
  • Agents run on your own platforms. Server IP is given to you and when you are told, connect it to server and stand beside human judge optimistically to get Bonuses.
  • There is no re-match for a game except for server problems. No objection is accepted as it's announced before competitions. In the case of network problems, the judge decides about the problem individually.
  • League results and Team score table will be available online during the league.
  • A setup round will be held before the real league starts. You can test your client during it, regarding how good it is and compatibility. It is recommended to join this event and it's not mandatory, but it makes no excuses for later problems during real league even if server is bugged. The date will be announced in the news section.
  • There's no Israeli teams in the league, you should play with all! But if you want you can resign a game and giving away its points.

Bonuses:

  • Bonuses are awarded by an individual in the final score sheet, not during the league.
  • Tricky moves by the agent is awarded by human judge. Moves such as forcing opponent to place 4 pieces in a row, Capturing a king by a gambee (sacrificed piece), long term plan to breach into a structured defense, ...
  • Offer a draw in the strategic points of game. If smart enough, it can brings you a bonus. Your agent should not stop working in that event because it's not implemented in server yet, but should show it's will to offer a draw with a notification such as console output or message box.
  • Phenomenal teams, that have very high scores relative to other teams get bonuses. This bonus can be granted to a team or two.
  • Extrea methods that results in extra agents gives bonuses. Judge will test it with your own main team.
  • Hand-Coded agents have bonuses too. They should win the worst team of the league. Hand coded algorithms are usually some win strategies that one can solve the puzzle. You usually know some general tactics to win the game, you can challenge your own play style to machine's style and try to improve both. This type of writing an agent is called "Reflective Agent" that reacts to special cases with some predefined actions. This algorithms are good for long comparisons that upgrades the modern intelligent algorithm against that play style. So it's advisable to put your play style into code and compare them with AI one and write the results into the report.

Deadlines:

  • Ask Dr. Ebadzadeh about your exact deadline.
  • It's 25 Jan for Reports and the league will be held on 27 January.

Information:

Game Scoring Policy:

  • Your agents must play in league. Write the network part at any cost.
  • If your agent can't play for any reason, network part, intelligent part, late hand over, etc. you lose half of your score (-50%)
  • Late teams will join in matches from that time, assumed lost in previous games.
  • Your primitive scores are based on rank of your agent in the league. Winner of the league gets 130% and worst team will give 70%. Phenomenal teams get bonuses. (70% ~ 130%)
  • You will explain your methodology and your program and algorithm components. Be prepared to change a part of your agent upon request to show you master your code. You will lose score from your primitive score if you can't justify the code or if the TA noticed a sort of cheat.
  • If you don't hand over your agent or don't participate in league at all, you will lose the scor of the report too.

Solution Methods:

  • Ant Colony Optimization
  • Particle Swarm Optimization
  • Genetic Algorithm
  • Simulated Annealing

Related Links:

Scores:

Here is the list of scores: January 27 (checkers league results included)8 teams qualified to final league challenges.

Memorial Photo!

 

AUT CEIT AI Class - Spring 2008:

Guides:

  • I personally suggest you to implement the algorithms of your choice(ACO, PSO, SA,and GA) and test them with these functions to avoid confusions about semantics of your code at the time of evaluating you heuristics and fitness functions:
    • f(x) = (x-3)^2 , 0<x<6 (correctness of your code)
    • f(x) = x.sin(x) , 0<x<6 (local optima tolerance)
    • f(x) = 2 , 0<x<6 (shoulders status)

News:

  • June 23: Code Test is now over. Reports are now available. ( See SCORES section)
  • June 21: Deadline is extended for the last time. The last time for handing out projects is  Monday, Jun 23 till 14:30 (3 tir). Also all reports must be handed out within work ours of this day.
  • June 15: The deadline is extended. Final day to hand over projects and related reports is Saturday, June 21 (1 tir). 
  • May 25: Games Are Discussed in the classroom. 
  • Apr 22: Game Scoring Policy defined. 
  • Apr 10: Games are set, score policy will be announced later. Game list is as suggested before: Magic Square, Hearts Card Game, Holdem Poker, Blobs, Connect Four, Tower of Hanoi, Knapsack, Traveling Salesman, Sudoku, Checkers, Backgammon, Rotation, Missioners & Cannibals. See some of games here.

  • Apr 1: The games are not arranged for this term yet, but there are some possible ones in mind:  Magic Square, Hearts Card Game, Holdem Poker, Blobs, Connect Four, Tower of Hanoi, Knapsack, Traveling Salesman, Sudoku, Checkers, Backgammon, Rotation, Missioners & Cannibals

Information:

Game Scoring Policy:

  • Final project will be half of your final scores: 10 out of 20
  • From the 10 points, 4 points goes to your implementation.
    • Code of two categories ( 1 Point, 0.5 each )
    • Interface ( 1 Point )
    • Correctness + Completeness if required ( 2 Pints )
    • User Friendliness ( Bonus )
    • Third category implementation code ( Bonus )
    • Self-Evaluating Agent ( Bonus )
    • Hand-code including algorithm design ( Bonus )
    • Games of class A has bonus scores due to complexity of implementation.
  • Categories: There are several solution methods that are defined in next section of this page, each called a category. Two of them must be implemented in order to achieve full mark of section, the more the better. Note that using methods to configure fitness function parameters and the search that use that function are counted as one category. For example if you define a numeric fitness function and using genetic algorithm to adjust them, then using this fitness function in minimax algorithm belongs to search category and counted as one. 
  • Interface: Each student must have his/her own interface implemented, using partner's interface faces a penalty in scoring. Interface is an stand alone game server that can accept a few commands from clients and show the game, manage turns, check invalid actions, and have proper user messaging system. Each client can join the game and send the command to server to play the game. Clients are AI agents or human agents. For example in Reversi game, when GA and PSO agents are implemented, these plays must be available: PSO-PSO, PSO-GA, PSO-Human, GA-GA, GA-Human, Human-Human(To check invalid moves and correct implementation of game)
  • Correctness: Local optimum is the case that must be handled well. Full mark of this section belongs to correct answers on most cases.
  • Completeness: Some methods promise completeness, and full mark of this section depends of this. Some others methods don't guarantee complete answer and their score totally depends on correctness section.
  • User Friendliness: Ambiguous interfaces are those which one can't operate the program without the assist of programmer. These GUIs have negative effect on interface section. Well-designed, professional interfaces with good graphics are those eligible of getting the bonus.
  • Self-Evaluation: Showing reports of games, drawing charts, showing the evolution of parameters, and other automatic report generating widgets embedded in your interface, if works properly and seems useful.
  • Hand-code: Hand coded algorithms are usually some win strategies that one can solve the puzzle. You usually know some general tactics to win the game, you can challenge your own play style to machine's style and try to improve both. This type of writing an agent is called "Reflective Agent" that reacts to special cases with some predefined actions. This algorithms are good for long comparisons that upgrades the modern intelligent algorithm against that play style. So it's advisable to put your play style into code and compare them with AI one and write the results into the report.
  • Games are in two class: A and B. Class B are ordinary ones that is in the scales or score limits. Class A has some implicit bonus in the scoring sections. Random factor, Fuzzy environment, and Creative approaches are meant in this part. Maximum bonuses are defined in the "Score Of Games" section.

Solution Methods:

  • Search Methods ( A* - Greedy - ... )
  • Ant Colony Optimization
  • Particle Swarm Optimization
  • Genetic Algorithm
  • Simulated Annealing

Related Links:

Assignments:

Games Definitions:

Announced in the classroom...

Score of Games:

  • Magic Square (B)
  • Hearts Card Game (A) - Randomness, Creativity
  • Holdem Poker (A) - Randomness, Creativity, Fuzzy, Bluffing
  • Blobs (B)
  • Connect Four (B)
  • Tower of Hanoi (B)
  • Knapsack (B)
  • Traveling Salesman (B)
  • Sudoku (B)
  • Checkers (A) - Creativity
  • Backgammon (A) - Randomness, Creativity
  • Rotation (B)
  • Missioners & Cannibals (B)
  • If you want to choose games other than this games note that it will be considered as class B and you must have my confirmation for it.

Deadlines:

  • Reports & Projects must be handed to Dr. Ebadzadeh on a single CD with the hard copy of the report. (July 21)
  • Programs must be presented to assistants on July 21.

Scores:

Here is the list of scores: Code Scores (June 23)

 

AUT CEIT AI Class - Fall 2007:

News:

  • Feb 2: Code Test is now over. Reports are now available. ( See SCORES section)
  • Jan 15: Deadline for Projects is Extended to February 2nd ( Saturday 13th of Bahman ). 
  • Jan 3: Deadline For The Projects is Jan 13th. Handing project completely in exam session (Jan 13) has a bonus score.
  • Jan 2: Some Guides Are Uploaded in Resources Section.
  • Jan 1: Second Make Up Class: 8:00am to 9:30 am. 
  • Dec 30: First Make Up Class: 12:30 pm to 1:30 pm. 
  • Dec 18: Scoring Policy is Announced.
  • Dec 12: Report Template is uploaded.
  • Dec 09: Games Definitions is up now.

Information:

Game Scoring Policy:

  • 30% of score: Abstract + Introduction + Literature Review + Implementation + References
  • 70% of score: Results + Discussion
  • Template of REPORTis here. Read it carefully, formatting weaknesses are regarded as a harm to total score.
  • Each game has it's own value: A, B, or C.
  • Games ranked B scores normally. Score of games in class A is doubled, while class C games have one half of original score.
  • Normal score for this project is 6 from the whole 20 score.
  • User-friendly interfaces has bonus scores.
  • Each game must be solved by two of five methods followed in next section. Implementation the 3rd solution has a bonus score.
  • Results provided in you reports will be treated in three classes individually:
    • Class C (Dumb Results): Results without support of evidence, or suffering from illegal reasoning, or not discussed properly, or inferred only by a single experiment.
    • Class B (Normal Results): Results supported by figures, evidence, and experiments, providing enough reasoning to be proven.
    • Class A (Brilliant Results): Results provided by a comprehensive study on a particular subject and are well-discussed, relevant, highly-supported, and strongly-reasoned. Innovative results are placed in this category if there are enough support for them.
  • Overall score of report depends on number of results, value of each, and the quality of discussion. Sure it is built upon several good experiments, precise figures, comparative diagrams, and relevant studies.

Solution Methods:

  • Search Methods ( A* - Greedy - ... )
  • Ant Colony Optimization
  • Particle Swarm Optimization
  • Genetic Algorithm
  • Simulated Annealing

Related Links:

Assignments:

Games Definitions:

You can download it HERE ...

Score of Games:

Scores of games is relatively:

  1. Draughts (A)
  2. Chinese Checkers (A)
  3. Riversi (A)
  4. Gomoku (A)
  5. Connect Four (B)
  6. Peg Solitaire (B)
  7. Sudoku (B)
  8. Fifteen Puzzle (C)
  9. N-Queens (C)
  10. Tower of Hanoi (C)

Deadlines:

  • Reports must be handed to Dr. Ebadzadeh at the final exam session. (13 Jan)
  • Programs must be presented to assistants by the first week after the exam date. (23 Jan)

Guides:

  • A sample of some of these games can be found HERE...
  • The most important part of this project is the HEURISTIC or FITNESS function that you will provide.
  • To have several experiments and thus several results, manipulate free parameters of each algorithms and compare the results. For example inertia in PSO, mutation probability in GA, pheromone vaporization rate in ACO, temperature schedule in SA, and ...
  • Comparative diagrams are indeed one of most useful tools to interpret results. Use Excel or similar softwares to draw such diagrams. You can embed Matlab module in C#.Net environment. Databases such as Access can be of great help too.
  • If you have ideas about several strategies that can be used to improve playing the games, you can mix them linearly, exponentially and etc to form you heuristic.
  • Comparison of several heuristics to find cons and pros of each is strongly advised. You can share ideas about each game with others to improve your solutions.
  • It will be shameful to find same implementations, same results, or etc in the project of two or more students. Share ideas, develop yours.
  • I personally suggest you to implement the algorithms of your choice and test them with these functions to avoid confusions about semantics of your code at the time of evaluating you heuristics and fitness functions:
    • f(x) = (x-3)^2 , 0<x<6 (correctness of your code)
    • f(x) = x.sin(x) , 0<x<6 (local optima tolerance)

Scores:

Here is the list of scores: Code Scores (Feb 2nd)


 

Study Resources:

General Guides: 

GA:

 ACO:

A good definition of Ant Colony Optimization. 

Simulation of an ACO sytem to find shortest path, red lne is the best path so far. 

PSO: 

 

 

Useful Links:

Areas of Interest In AI:

This is a Hangman game to illustrate your familiarity with AI keywords...


Artificial Intelligence At A Glance:

Branches of AI:

Here's a list, but some branches are surely missing, because no-one has identified them yet. Some of these may be regarded as concepts or topics rather than full branches.

Also there is a good BIBLIOGRAPHY of AI available HERE.


logical AI


What a program knows about the world in general the facts of the specific situation in which it must act, and its goals are all represented by sentences of some mathematical logical language. The program decides what to do by inferring that certain actions are appropriate for achieving its goals. The first article proposing this was [McC59]. [McC89] is a more recent summary. [McC96b] lists some of the concepts involved in logical aI. [Sha97] is an important text.


search


AI programs often examine large numbers of possibilities, e.g. moves in a chess game or inferences by a theorem proving program. Discoveries are continually made about how to do this more efficiently in various domains.


pattern recognition


When a program makes observations of some kind, it is often programmed to compare what it sees with a pattern. For example, a vision program may try to match a pattern of eyes and a nose in a scene in order to find a face. More complex patterns, e.g. in a natural language text, in a chess position, or in the history of some event are also studied. These more complex patterns require quite different methods than do the simple patterns that have been studied the most.


representation


Facts about the world have to be represented in some way. Usually languages of mathematical logic are used.


inference


From some facts, others can be inferred. Mathematical logical deduction is adequate for some purposes, but new methods of non-monotonic inference have been added to logic since the 1970s. The simplest kind of non-monotonic reasoning is default reasoning in which a conclusion is to be inferred by default, but the conclusion can be withdrawn if there is evidence to the contrary. For example, when we hear of a bird, we man infer that it can fly, but this conclusion can be reversed when we hear that it is a penguin. It is the possibility that a conclusion may have to be withdrawn that constitutes the non-monotonic character of the reasoning. Ordinary logical reasoning is monotonic in that the set of conclusions that can the drawn from a set of premises is a monotonic increasing function of the premises. Circumscription is another form of non-monotonic reasoning.


common sense knowledge and reasoning


This is the area in which AI is farthest from human-level, in spite of the fact that it has been an active research area since the 1950s. While there has been considerable progress, e.g. in developing systems of non-monotonic reasoning and theories of action, yet more new ideas are needed. The Cyc system contains a large but spotty collection of common sense facts.


learning from experience


Programs do that. The approaches to AI based on connectionism and neural nets specialize in that. There is also learning of laws expressed in logic. [Mit97] is a comprehensive undergraduate text on machine learning. Programs can only learn what facts or behaviors their formalisms can represent, and unfortunately learning systems are almost all based on very limited abilities to represent information.


planning


Planning programs start with general facts about the world (especially facts about the effects of actions), facts about the particular situation and a statement of a goal. From these, they generate a strategy for achieving the goal. In the most common cases, the strategy is just a sequence of actions.


epistemology


This is a study of the kinds of knowledge that are required for solving problems in the world.


ontology


Ontology is the study of the kinds of things that exist. In AI, the programs and sentences deal with various kinds of objects, and we study what these kinds are and what their basic properties are. Emphasis on ontology begins in the 1990s.


heuristics


A heuristic is a way of trying to discover something or an idea imbedded in a program. The term is used variously in AI. Heuristic functions are used in some approaches to search to measure how far a node in a search tree seems to be from a goal. Heuristic predicates that compare two nodes in a search tree to see if one is better than the other, i.e. constitutes an advance toward the goal, may be more useful. [My opinion].


genetic programming


Genetic programming is a technique for getting programs to solve a task by mating random Lisp programs and selecting fittest in millions of generations. It is being developed by John Koza's group and here's a tutorial.

Applications of AI:


game playing


You can buy machines that can play master level chess for a few hundred dollars. There is some AI in them, but they play well against people mainly through brute force computation--looking at hundreds of thousands of positions. To beat a world champion by brute force and known reliable heuristics requires being able to look at 200 million positions per second.


speech recognition


In the 1990s, computer speech recognition reached a practical level for limited purposes. Thus United Airlines has replaced its keyboard tree for flight information by a system using speech recognition of flight numbers and city names. It is quite convenient. On the the other hand, while it is possible to instruct some computers using speech, most users have gone back to the keyboard and the mouse as still more convenient.


understanding natural language


Just getting a sequence of words into a computer is not enough. Parsing sentences is not enough either. The computer has to be provided with an understanding of the domain the text is about, and this is presently possible only for very limited domains.


computer vision


The world is composed of three-dimensional objects, but the inputs to the human eye and computers' TV cameras are two dimensional. Some useful programs can work solely in two dimensions, but full computer vision requires partial three-dimensional information that is not just a set of two-dimensional views. At present there are only limited ways of representing three-dimensional information directly, and they are not as good as what humans evidently use.


expert systems


A ``knowledge engineer'' interviews experts in a certain domain and tries to embody their knowledge in a computer program for carrying out some task. How well this works depends on whether the intellectual mechanisms required for the task are within the present state of AI. When this turned out not to be so, there were many disappointing results. One of the first expert systems was MYCIN in 1974, which diagnosed bacterial infections of the blood and suggested treatments. It did better than medical students or practicing doctors, provided its limitations were observed. Namely, its ontology included bacteria, symptoms, and treatments and did not include patients, doctors, hospitals, death, recovery, and events occurring in time. Its interactions depended on a single patient being considered. Since the experts consulted by the knowledge engineers knew about patients, doctors, death, recovery, etc., it is clear that the knowledge engineers forced what the experts told them into a predetermined framework. In the present state of AI, this has to be true. The usefulness of current expert systems depends on their users having common sense.


heuristic classification


One of the most feasible kinds of expert system given the present knowledge of AI is to put some information in one of a fixed set of categories using several sources of information. An example is advising whether to accept a proposed credit card purchase. Information is available about the owner of the credit card, his record of payment and also about the item he is buying and about the establishment from which he is buying it (e.g., about whether there have been previous credit card frauds at this establishment).

Basic Questions About AI:

Q. What is artificial intelligence?

A. It is the science and engineering of making intelligent machines, especially intelligent computer programs. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable.

Q. Yes, but what is intelligence?

A. Intelligence is the computational part of the ability to achieve goals in the world. Varying kinds and degrees of intelligence occur in people, many animals and some machines.

Q. Isn't there a solid definition of intelligence that doesn't depend on relating it to human intelligence?

A. Not yet. The problem is that we cannot yet characterize in general what kinds of computational procedures we want to call intelligent. We understand some of the mechanisms of intelligence and not others.

Q. Is intelligence a single thing so that one can ask a yes or no question ``Is this machine intelligent or not?''?

A. No. Intelligence involves mechanisms, and AI research has discovered how to make computers carry out some of them and not others. If doing a task requires only mechanisms that are well understood today, computer programs can give very impressive performances on these tasks. Such programs should be considered ``somewhat intelligent''.

Q. Isn't AI about simulating human intelligence?

A. Sometimes but not always or even usually. On the one hand, we can learn something about how to make machines solve problems by observing other people or just by observing our own methods. On the other hand, most work in AI involves studying the problems the world presents to intelligence rather than studying people or animals. AI researchers are free to use methods that are not observed in people or that involve much more computing than people can do.

Q. What about IQ? Do computer programs have IQs?

A. No. IQ is based on the rates at which intelligence develops in children. It is the ratio of the age at which a child normally makes a certain score to the child's age. The scale is extended to adults in a suitable way. IQ correlates well with various measures of success or failure in life, but making computers that can score high on IQ tests would be weakly correlated with their usefulness. For example, the ability of a child to repeat back a long sequence of digits correlates well with other intellectual abilities, perhaps because it measures how much information the child can compute with at once. However, ``digit span'' is trivial for even extremely limited computers.

However, some of the problems on IQ tests are useful challenges for AI.

Q. What about other comparisons between human and computer intelligence?

Arthur R. Jensen [Jen98], a leading researcher in human intelligence, suggests ``as a heuristic hypothesis'' that all normal humans have the same intellectual mechanisms and that differences in intelligence are related to ``quantitative biochemical and physiological conditions''. I see them as speed, short term memory, and the ability to form accurate and retrievable long term memories.

Whether or not Jensen is right about human intelligence, the situation in AI today is the reverse.

Computer programs have plenty of speed and memory but their abilities correspond to the intellectual mechanisms that program designers understand well enough to put in programs. Some abilities that children normally don't develop till they are teenagers may be in, and some abilities possessed by two year olds are still out. The matter is further complicated by the fact that the cognitive sciences still have not succeeded in determining exactly what the human abilities are. Very likely the organization of the intellectual mechanisms for AI can usefully be different from that in people.

Whenever people do better than computers on some task or computers use a lot of computation to do as well as people, this demonstrates that the program designers lack understanding of the intellectual mechanisms required to do the task efficiently.

Q. When did AI research start?

A. After WWII, a number of people independently started to work on intelligent machines. The English mathematician Alan Turing may have been the first. He gave a lecture on it in 1947. He also may have been the first to decide that AI was best researched by programming computers rather than by building machines. By the late 1950s, there were many researchers on AI, and most of them were basing their work on programming computers.

Q. Does AI aim to put the human mind into the computer?

A. Some researchers say they have that objective, but maybe they are using the phrase metaphorically. The human mind has a lot of peculiarities, and I'm not sure anyone is serious about imitating all of them.

Q. What is the Turing test?

A. Alan Turing's 1950 article Computing Machinery and Intelligence [Tur50] discussed conditions for considering a machine to be intelligent. He argued that if the machine could successfully pretend to be human to a knowledgeable observer then you certainly should consider it intelligent. This test would satisfy most people but not all philosophers. The observer could interact with the machine and a human by teletype (to avoid requiring that the machine imitate the appearance or voice of the person), and the human would try to persuade the observer that it was human and the machine would try to fool the observer.

The Turing test is a one-sided test. A machine that passes the test should certainly be considered intelligent, but a machine could still be considered intelligent without knowing enough about humans to imitate a human.

Daniel Dennett's book Brainchildren [Den98] has an excellent discussion of the Turing test and the various partial Turing tests that have been implemented, i.e. with restrictions on the observer's knowledge of AI and the subject matter of questioning. It turns out that some people are easily led into believing that a rather dumb program is intelligent.

Q. Does AI aim at human-level intelligence?

A. Yes. The ultimate effort is to make computer programs that can solve problems and achieve goals in the world as well as humans. However, many people involved in particular research areas are much less ambitious.

Q. How far is AI from reaching human-level intelligence? When will it happen?

A. A few people think that human-level intelligence can be achieved by writing large numbers of programs of the kind people are now writing and assembling vast knowledge bases of facts in the languages now used for expressing knowledge.

However, most AI researchers believe that new fundamental ideas are required, and therefore it cannot be predicted when human-level intelligence will be achieved.

Q. Are computers the right kind of machine to be made intelligent?

A. Computers can be programmed to simulate any kind of machine.

Many researchers invented non-computer machines, hoping that they would be intelligent in different ways than the computer programs could be. However, they usually simulate their invented machines on a computer and come to doubt that the new machine is worth building. Because many billions of dollars that have been spent in making computers faster and faster, another kind of machine would have to be very fast to perform better than a program on a computer simulating the machine.

Q. Are computers fast enough to be intelligent?

A. Some people think much faster computers are required as well as new ideas. My own opinion is that the computers of 30 years ago were fast enough if only we knew how to program them. Of course, quite apart from the ambitions of AI researchers, computers will keep getting faster.

Q. What about parallel machines?

A. Machines with many processors are much faster than single processors can be. Parallelism itself presents no advantages, and parallel machines are somewhat awkward to program. When extreme speed is required, it is necessary to face this awkwardness.

Q. What about making a "child machine" that could improve by reading and by learning from experience?

A. This idea has been proposed many times, starting in the 1940s. Eventually, it will be made to work. However, AI programs haven't yet reached the level of being able to learn much of what a child learns from physical experience. Nor do present programs understand language well enough to learn much by reading.

Q. Might an AI system be able to bootstrap itself to higher and higher level intelligence by thinking about AI?

A. I think yes, but we aren't yet at a level of AI at which this process can begin.

Q. What about chess?

A. Alexander Kronrod, a Russian AI researcher, said ``Chess is the Drosophila of AI.'' He was making an analogy with geneticists' use of that fruit fly to study inheritance. Playing chess requires certain intellectual mechanisms and not others. Chess programs now play at grandmaster level, but they do it with limited intellectual mechanisms compared to those used by a human chess player, substituting large amounts of computation for understanding. Once we understand these mechanisms better, we can build human-level chess programs that do far less computation than do present programs.

Unfortunately, the competitive and commercial aspects of making computers play chess have taken precedence over using chess as a scientific domain. It is as if the geneticists after 1910 had organized fruit fly races and concentrated their efforts on breeding fruit flies that could win these races.

Q. What about Go?

A. The Chinese and Japanese game of Go is also a board game in which the players take turns moving. Go exposes the weakness of our present understanding of the intellectual mechanisms involved in human game playing. Go programs are very bad players, in spite of considerable effort (not as much as for chess). The problem seems to be that a position in Go has to be divided mentally into a collection of subpositions which are first analyzed separately followed by an analysis of their interaction. Humans use this in chess also, but chess programs consider the position as a whole. Chess programs compensate for the lack of this intellectual mechanism by doing thousands or, in the case of Deep Blue, many millions of times as much computation.

Sooner or later, AI research will overcome this scandalous weakness.

Q. Don't some people say that AI is a bad idea?

A. The philosopher John Searle says that the idea of a non-biological machine being intelligent is incoherent. He proposes the Chinese room argument www-formal.stanford.edu/jmc/chinese.html The philosopher Hubert Dreyfus says that AI is impossible. The computer scientist Joseph Weizenbaum says the idea is obscene, anti-human and immoral. Various people have said that since artificial intelligence hasn't reached human level by now, it must be impossible. Still other people are disappointed that companies they invested in went bankrupt.

Q. Aren't computability theory and computational complexity the keys to AI? [Note to the layman and beginners in computer science: These are quite technical branches of mathematical logic and computer science, and the answer to the question has to be somewhat technical.]

A. No. These theories are relevant but don't address the fundamental problems of AI.

In the 1930s mathematical logicians, especially Kurt Gödel and Alan Turing, established that there did not exist algorithms that were guaranteed to solve all problems in certain important mathematical domains. Whether a sentence of first order logic is a theorem is one example, and whether a polynomial equations in several variables has integer solutions is another. Humans solve problems in these domains all the time, and this has been offered as an argument (usually with some decorations) that computers are intrinsically incapable of doing what people do. Roger Penrose claims this. However, people can't guarantee to solve arbitrary problems in these domains either. See my Review of The Emperor's New Mind by Roger Penrose. More essays and reviews defending AI research are in [McC96a].

In the 1960s computer scientists, especially Steve Cook and Richard Karp developed the theory of NP-complete problem domains. Problems in these domains are solvable, but seem to take time exponential in the size of the problem. Which sentences of propositional calculus are satisfiable is a basic example of an NP-complete problem domain. Humans often solve problems in NP-complete domains in times much shorter than is guaranteed by the general algorithms, but can't solve them quickly in general.

What is important for AI is to have algorithms as capable as people at solving problems. The identification of subdomains for which good algorithms exist is important, but a lot of AI problem solvers are not associated with readily identified subdomains.

The theory of the difficulty of general classes of problems is called computational complexity. So far this theory hasn't interacted with AI as much as might have been hoped. Success in problem solving by humans and by AI programs seems to rely on properties of problems and problem solving methods that the neither the complexity researchers nor the AI community have been able to identify precisely.

Algorithmic complexity theory as developed by Solomonoff, Kolmogorov and Chaitin (independently of one another) is also relevant. It defines the complexity of a symbolic object as the length of the shortest program that will generate it. Proving that a candidate program is the shortest or close to the shortest is an unsolvable problem, but representing objects by short programs that generate them should sometimes be illuminating even when you can't prove that the program is the shortest.

Q. How is AI research done?

A. AI research has both theoretical and experimental sides. The experimental side has both basic and applied aspects.

There are two main lines of research. One is biological, based on the idea that since humans are intelligent, AI should study humans and imitate their psychology or physiology. The other is phenomenal, based on studying and formalizing common sense facts about the world and the problems that the world presents to the achievement of goals. The two approaches interact to some extent, and both should eventually succeed. It is a race, but both racers seem to be walking.

Q. What are the relations between AI and philosophy?

A. AI has many relations with philosophy, especially modern analytic philosophy. Both study mind, and both study common sense. The best reference is [Tho03].

Q. How are AI and logic programming related?

A. At the very least, logic programming provides useful programming languages (mainly Prolog).

Beyond that, sometimes a theory useful in AI can be expressed as a collection of Horn clauses, and goal to be achieved can be expressed as that of finding values of variables satisfying an expression . The problem can sometimes be solved by running the Prolog program consisting of and .

There are two possible obstacles to regarding AI as logic programming. First, Horn theories do not exhaust first order logic. Second, the Prolog program expressing the theory may be extremely inefficient. More elaborate control than just executing the program that expresses the theory is often needed. Map coloring provides examples.

Q. What should I study before or while learning AI?

A. Study mathematics, especially mathematical logic. The more you learn about sciences, e.g. physics or biology, the better. For the biological approaches to AI, study psychology and the physiology of the nervous system. Learn some programming languages--at least C, Lisp and Prolog. It is also a good idea to learn one basic machine language. Jobs are likely to depend on knowing the languages currently in fashion. In the late 1990s, these include C++ and Java.

Q. What is a good textbook on AI?

A. Artificial Intelligence by Stuart Russell and Peter Norvig, Prentice Hall is the most commonly used textbbook in 1997. The general views expressed there do not exactly correspond to those of this essay. Artificial Intelligence: A New Synthesis by Nils Nilsson, Morgan Kaufman, may be easier to read. Some people prefer Computational Intelligence by David Poole, Alan Mackworth and Randy Goebel, Oxford, 1998.

Q. What organizations and publications are concerned with AI?

A. The American Association for Artificial Intelligence (AAAI), the European Coordinating Committee for Artificial Intelligence (ECCAI) and the Society for Artificial Intelligence and Simulation of Behavior (AISB) are scientific societies concerned with AI research. The Association for Computing Machinery (ACM) has a special interest group on artificial intelligence SIGART.

The International Joint Conference on AI (IJCAI) is the main international conference. The AAAI runs a US National Conference on AI. Electronic Transactions on Artificial Intelligence, Artificial Intelligence, and Journal of Artificial Intelligence Research, and IEEE Transactions on Pattern Analysis and Machine Intelligence are four of the main journals publishing AI research papers. I have not yet found everything that should be in this paragraph.

Interesting Novel Ideas:

Acknowledgments: