We shall begin our study of ARTIFICIAL INTELLIGENCE, AI, by considering a number of alternative definitions of this topic

DEFINITIONS

A I is the study of how to make computers do things which at the moment people do better. This is ephemeral as it refers to the current state of computer science and it excludes a major area ; problems that cannot be solved well either by computers or by people at the moment.

Alternative

A I is the branch of computer science that is concerned with the automation of intelligent behaviour. A I is based upon the principles of computer science namely data structures used in knowledge representation, the algorithms needed to apply that knowledge and the languages and programming techniques used in their implementation.

These definitions avoid philosophic discussions as to what is meant by artificial or intelligence.

Alternative

A I is a field of study that encompasses computational techniques for performing tasks that apparently require intelligence when performed by humans.

Alternative

A I is the field of study that seeks to explain and emulate intelligent behaviour in terms of computational processes.

Alternative

A I is about generating representations and procedures that automatically or autonomously solve problems heretofore solved by humans.

Alternative

A I is the part of computer science concerned with designing intelligent computer systems, that is, computer systems that exhibit the characteristics we associate with intelligence in human behaviour -- understanding language, learning, reasoning and solving problems.

A I Problems

Let us consider some of the problems that AI is used to solve. Early examples include game playing, which will be discussed in subsequent lectures and theorem proving, which involves resolution and is considered elsewhere, if at all. Common sense reasoning formed the basis of GPS a general problem solver; vision and image processing problems are covered by other lecture courses. Natural language processing met with early success then the power of the computers foiled progress but nowadays this topic is experiencing a surge, simpler approaches are considered later. The question of expert systems is interesting but it represents one of the best examples of an application of AI which appears useful to non AI people. Actually the expert system solves particular subsets of problems using knowledge and rules about a particular topic, see for example the other Dr Jones course.

The following four questions need to be considered before we can progress further:

1 what are the underlying assumptions about intelligence?

2 what kinds of techniques will be useful for solving A I problems?

3 at what level if at all can human intelligence be modelled?

4 when will it be realised when an intelligent program has been built?

The Underlying assumption

A physical system consists of a set of entities called symbols which are patterns that can occur as components of another entitiy called an expression. At an instant the system will contain a collection of these symbol structures. In addition the system also contains a collection of processes that operate on expressions to produce other expressions; processes of creation, modification,reproduction and destruction.

A physical symbol system is a machine that goes on producing an evolving collection of symbol structures.

The physical symbol system hypothesis

A physical symbol system has the necessary and sufficient means for general intelligent action. It is only a hypothesis and there is no way to prove it other than on empirical grounds. Thus experimentation is in order using computers. Evidence in favour of this hypothesis has come from game playing Chinook gave the current world champion in draughts or checkers a tight game 2-3 recently; and from visual perception.

An AI technique.

Intelligence requires knowledge but knowledge possesses less desirable properties such as

a it is voluminous

b it is difficult to characterise accurately

c it is constantly changing

d it differs from data by being organised in a way that corresponds to its application

An AI technique is a method that exploits knowledge that is represented so that

a The knowledge captures generalisations ; situations that share properties, are grouped together, rather than being allowed separate representation.

b It can be understood by people who must provide it; although for many programs the bulk of the data may come automatically, such as from readings.

In many AI domains people must supply the knowledge to programs in a form the people understand and in a form that is acceptable to the program.

c It can be easily modified to correct errors and reflect changes in real conditions.

d It can be widely used even if it is incomplete or inaccurate.

e It can be used to help overcome its own sheer bulk by helping to narrow the range of possibilities that must be usually considered.

In order to characterise an AI technique let us consider initially OXO or tictactoe

and use a series of different approaches to play the game.

The three program increase in complexity, in their use of generalisations, the clarity of their knowledge and the extensibility of their approach. In this way they move toward being representations of AI techniques.

1 The first simple approach.

The data structure consists of a nine element vector, BOARD, representing the board numbered 1 to 9 in three rows. An element contains the value 0 for blank, 1 for X and 2 for O. A huge vector, MOVETABLE, of 19683 elements-- three to the power nine-- is needed where each element is a nine element vector. The contents of the vector are specially chosen to help the algorithm.The algorithm makes moves by pursuing the following

1 View the vector as a ternary number. Convert it to decimal.

2 Use the decimal number as an index in MOVETABLE & access the vector there.

3 Set BOARD to this vector indicating how the board looks after the move.This approach is efficient in time but it has several disadvantages. It takes up too much space; it requires stupendous effort to calculate the decimal numbers and errors are likely; the method is specific to this game and cannot be extended.

2 The second approach.

The data structure is as before but we use 2 for a blank 3 for a X and 5 for a O. A variable called TURN indicates 1 for the first move and 9 for the last. The algorithm consists of three procedures

MAKE2 which returns 5 if centre square blank otherwise it returns any blank noncorner square ie 2, 4, 6 or 8.

POSSWIN(p) returns 0 if player p cannot win on the next move and otherwise returns the number of the square that gives a winning move. It checks each line in turn using products 3*3*2 = 18 gives a win for X, 5*5*2=50 gives a win for O, the winning move is the holder of the blank.

GO(n) makes a move to square n setting BOARD[n] to 3 or 5

The algorithm is a gigantic case statement see insert.

This algorithm is more involved and so takes longer but it is more efficient in storage which compensates for its longer time. It depends on programmer's skill and cannot be generalised.The final approach

The data structure consists of BOARDPOSITION which is a structure containing a nine element vector representing the board, a list of board positions that could result from the next move and a number representing an estimate of how likely the board position is to lead to an ultimate win for the player to move.

The algorithm use lookahead to decide on the next move. By deciding which is the most promising move the appropriate move at any stage is selected.

If a win can occur make this move. Consider all possible moves that the program can make and then consider all possible replies. Continue this process for as long as time permits until a winner emerges and then choose the move that leads to the computer program winning if possible in the shortest time.

This is actually the most difficult to program by a good margin but it is far superior in that the technique can be extended to any game. The method makes relatively fewer demands on the programmer in terms of game technique but the overall game strategy must be known to the adviser.

This is a good example of an AI technique.

Further topics that will be considered in our introductory phase:

simple question and answering problems

the water jug problem

constraint satisfaction, such as cryptarithmetic

systematic searching problems.Algorithm Breadth-First Search

1. Create a variable called NODE-LIST and set it to the initial state.

2. UNTIL a goal state is found OR NODE-LIST is empty DO

(a) Remove the first element from NODE_LIST and call it E.

IF NODE-LIST was empty quit.

(b) FOR each way that each rule can match the state described in E DO

(i) Apply the rule to generate a new state

(ii) IF the new state is a goal state quit and return this state.

(iii) Otherwise add the new state to the end of NODE-LIST.

Algorithm Depth-First Search

1. IF the initial state is a goal state, quit and return success.

2. Otherwise DO the following until success or failure is signalled

(a) Generate a successor,E, of the initial state. If there are no more successors signal failure.

(b) Call Depth-First Search with E as the initial state.

(c) If success is returned signal success otherwise continue in the loop.

Problem Characteristics.

1. Is the problem decomposable into a set of nearly independent smaller or easier subproblems?

2. Can solution steps be ignored or at least undone if they prove unwise?

3. Is the problem's universe predictable?

4. Is a good solution to the problem obvious without comparison to all other possible solutions?

5. Is the desired solution a state of the world or a path to a state?

6. Is a large amount of knowledge absolutely required to solve this problem or is knowledge important only to constrain the search?

7. Can a computer that is simply given the problem return the solution or will the solution of the problem require interaction between the computer and a person?