report | 代写Data structure | Algorithm | aws代写 | 作业Artificial | java | scheme | oop | Objective | 代写Asp | unity | 代做AI | Haskell作业 | Operating Systems – COM1005: Experiments with AI Techniques

COM1005: Experiments with AI Techniques

report | 代写Data structure | Algorithm | aws代写 | 作业Artificial | java | scheme | oop | Objective | 代写Asp | unity | 代做AI | Haskell作业 | Operating Systems – 这是一个Asp面向对象设计的practice, 考察Asp的理解, 涵盖了report/Data structure/Algorithm/aws/Artificial/java/scheme/oop/Objective/Asp/unity/AI/Haskell/Operating Systems等方面

aws代写 代做aws bigdata代做 大数据代写

1 of 90
University of Sheffield
Department of Computer Science

COM1005: Experiments with AI Techniques

Semester 2 of COM1005 covers a number of computer-based problem solving
methods developed for  Artificial Intelligence.
It also gives you experience in research programming.
We will implement these techniques in  java and experiment with them
We are looking at techniques for symbolic rather than connectionist AI.
1.1 References
There are many AI textbooks covering this material, for example:

Russell & Norvig, Artificial Intelligence: a modern approach Winston, Artificial Intelligence, Addison Wesley. Cawsey, The Essence of Artificial Intelligence, Prentice Hall

There is no requirement to buy any of these to follow the course, but you might find
it useful to look at them.
Course Materials are on Mole
Java code used in this module is on the MOLE site. Download it as & when you
need it.
1.2 About AI Programming
In AI, programmes are scientific apparatus, written

in order to make ideas concrete, to make it possible evaluate ideas experimentally, to enable comparative evaluation against alternatives, to ensure that results can be reproduced.

The following principles are important:

2 of 90 COM1005: AI Techniques

Solve the general problem, not a particular variant (abstraction), e.g Avoid repeated work (i.e. repeated computation). Vital in order to make best use of limited resources.

AI researchers have traditionally used unconventional programming languages,
primarily LISP (functional) and PROLOG (logic). Well point out differences
between Java programming and these styles as we go along.
We look first at problem-solving by search. In the early days of AI it was thought
that this paradigm might prove sufficient to produce generally intelligent behaviour.
While the modern view is that there is more to it than that, it is still necessary to be
able to conduct a search sensibly.
A search-based problem-solver makes decisions based on the likely consequences
of potential actions. The only knowledge used is what actions are available in a
given problem state, how these actions will change the state and, in the general case,
costs associated with these actions.
From an initial problem state, the search engine generates the states which can be
reached by a single action. It then selects one of these states and (if the new state is
not a goal), generates all its successors and so on.
2.1 Examples:
Well use three simple search problems as exemplars:
2.1.1 Jugs Problems
A typical jugs problem is:
Suppose you have a 7-pint jug, a 4-pint jug, a water tap and a sink.
You are allowed to fill either jug from the tap, empty either jug into the sink, or pour
from one jug into the other until either the first jug is full or the second jug is empty.
Show that by a sequence of such moves it is possible to measure any number of pints
between 0 and 7.
We always want to generalise our solutions, so we will consider that our jugs can be
any capacity (not just 7 & 4 pints), and the target amount can be anything we like.
Contains common code for game
Common code
& Specialise
This is one of the foundations ofObject Oriented Programming, e.g. as in Java
Weavoid solving the same problem twice.
Abstraction forces us to understand the general principles of our technique
COM1005: AI Techniques 3 of 90
Note that there may be no solution to some given problem.

2.1.2 8 – Puzzle

Rearrange the tiles to the desired pattern by sliding adjacent tiles into the hole.

2.1.3 Map Traversal

Think of A,B etc. as cities The numbers are distances between cities. Find the shortest route from Start to Goal.

Later on we will look at how search techniques are adapted for game-playing and
how they are used in speech recognition.
All problem-solvers search to some extent. Effective use of knowledge can make
the search trivial or at least manageable.

2.2 Definitions

We consider that the problem involves moving between a number of problem states.
State Space contains all allowed problem states. Consists of a graph in which states
are connected by arcs (legal moves from one state to another).

Jugs: all possible configurations that can be reached from the initial state where both jugs are empty:

5 4
7 8
1 2 3
4 5 6
7 8

4 of 90 COM1005: AI Techniques

8 – puzzle: all possible arrangements of tiles. Map Traversal: the map.

The expand function takes a given state and returns a list of all the states that can be
reached by a single move from that state.

Jugs – all possible configurations by one move from a given state 8 – puzzle – all possible tile configurations from a given one Map-Traversal: All cities that can be reached from a given city.

Sometimes it is natural to think of the expand function as invoking operators. An
operator is a function which embodies a 'legal move' from one state to another.

Jugs: empty j1 to sink, empty j2 to sink, fill j1 from tap, fill j2 from tap, pour from j1 to j2, pour from j2 to j1. 8 – puzzle: Move-Up, Move-Down, Move-Left, Move-Right

Not all operators will be applicable to a given state.
The operators/expand-function represent the 'rules of the game'. The process of
considering all the successors of a given state is called developing the state.
A problem is seen as finding a path through state space from a given initial state to
some goal state.
The solution can be expressed either as the sequence of states traversed, the
sequence of operators used or the goal state, as appropriate.
There may be one or many goal states. In general, we need a goal test that, given a
state, tells us whether it is a goal or not.
It may be sufficient to find any solution, or we may be required to find the 'best'

Jugs/8-puzzle: minimum number of moves. Map traversal: least costly path.

2.3 Search Trees and the Dynamic Programming Principle
We need to distinguish between the state space and the search tree that is grown
when we explore it.
State-space is generally a graph (i.e. there may be >1 way of reaching a state), but in
the search tree each Search Node will have 1 parent.

####### (0 0)

####### (7 0) (0 4)

####### (7 4) (3 4)

####### (3 0)

####### (0 3)

####### (4 0)

####### (4 4)

####### (7 1)

Incomplete state space for jugs with capacities 7 & 4
COM1005: AI Techniques 5 of 90
This is because we only need to remember one way (the best way so far found) of
reaching any state.
This is called the  dynamic programming principle and is fundamental to search
algorithms. In simple cases, it means that if, in the course of a search, we come
across a node we have already seen, we need do nothing.
States and Nodes
Each node in the search tree will be associated with a different state in state space,
but may also contain other information (for instance, a pointer to the parent node):

2.4 AI and the Combinatorial Explosion

The problem of relying on search is the combinatorial explosion. The potential
search tree grows explosively with increasing depth:
If there is a uniform branching factor b and we search the tree to depth n, there will
be bn tip nodes.

b averages around 30 for a complete game, n will be around 100 So exploring the whole tree will produce 30^100 or around 10145 nodes. This is considerably more than the number of atoms in the universe

We therefore have to arrange to stop the search before resources run out, and to
search selectively.
If the state space is large, we may have to trade-off the quality of the solution against
the amount of effort required to find it.
It is important to choose our problem representation so that the search space is not
too large.

####### (0 0)

####### (7 0) (0 4)

####### (7 4) (3 4)

Incomplete state space for jugs with capacities 7 & 4
Jugs search for target 3. Solution path in bold

6 of 90 COM1005: AI Techniques

We can try to do this by deploying more knowledge (e.g. not all legal chess moves
are useful). We return to this later.
'The more knowledge, the less search'.
Many problem-solving programs can be seen as conducting a state-space search.
Later on we will relate forward-chaining and backward-chaining (rule-based
systems) and structure-matching (frame-based systems) to search.
2.5 Search Strategies
We must have a way of deciding which leaf node in our search tree to explore next,
i.e. which state to expand. The  Algorithm to do this embodies the search strategy.
Assessing Search Strategies: Criteria

Is the strategy Guaranteed to find a solution if one exists? Is the strategy Admissible, i.e. guaranteed to find the best solution?, or a solution of sufficient quality? How Efficient is the strategy: i.e. how much effort does it expend in finding a solution?

The optimal strategy would visit only those nodes which turn out to be on the
solution path.
For an individual search, Efficiency = (Number of nodes on solution path)/
(Number of nodes visited)
Note that admissibility is a property of the algorithm, but efficiency is different for
each different search we perform. To assess the efficiency of a search algorithm in
a particular problem domain we would run the algorithm for a representative set of
problems from that domain & average the efficiency over these trials.
2.6 Programming a State Space Search
We will need

A way of representing the states, An expand method, perhaps calling operators. A method acting as a goal predicate, A method implementing a strategy for navigating the State Space.

2.7 A Skeleton Algorithm for State Space Searching
Expressed imperatively:
We maintain

a list of nodes awaiting development. This is called the open list or agenda. a list of nodes already developed. This is called the closed list.


we put the start node on open.

COM1005: AI Techniques 7 of 90

closed is empty

We repeatedly
  1. Check if open is empty. If so, exit with failure
  2. Use the search strategy to select some node (the currentNode) from open for development.
  3. Remove currentNode from open. Add it to closed.
  4. Check if currentNode is a goal – if so, exit with success.
  5. use expand to find currentNode s successors,
  6. add all successors which are not already on open or closed to open.

2.8 Java Implementation

We will develop a generalised search engine in Java, which we can then use in any
search problem domain. The user has to set up what is necessary for her domain: we
specify below how to do this.
This policy of abstracting the problem-solver is typical of AI (and CS in general). It
saves repeated work & forces us to understand what were doing.
The baseline version of the search engine is in the folder java/search1 from the
MOLE site

2.8.1 Classes and Methods

We need a class which contains a method runSearch implementing the algorithm above. Well call this class Search. runSearch uses open and closed, so these will be variables in Search. runSearch deals with search nodes, so well have another class SearchNode. Well need to keep track of the currentNode, so this will be another variable in Search. To programme a search in a particular problem domain (e.g. Jugs problems), our user needs to create a subclass of Search for this domain e.g. Jugs_Search. This subclass will have variables carrying the information needed to define a search problem in this domain for jugs, the jug capacities and the target amount. These are the problem parameters. To run a search, we create an instance of the subclass, giving it the defining information, and call runSearch. So we will never make an instance of Search itself it will be an abstract class. The class SearchNode makes the distinction between a node in a search and a problem state clear: the user is concerned with states. The search engine sees only nodes. SearchNode will have a variable state which contains the state associated with this node. Later on, well add more variables, e.g. the parent node and the cost of getting to this node. SearchNode will have methods which express what runSearch needs to know:

is a node a goal (goalP)?,
what are its successor nodes (getSuccessors)?,
is its state the same as that of another node (sameState)?.. this is needed for
dynamic programming.

8 of 90 COM1005: AI Techniques

state will be of type SearchState. This will be another abstract class which we specialise for a particular problem domain (e.g. Jugs_State). The class for a state in a particular domain (e.g. Jugs_State) will define a state using a state representation scheme chosen by the user (e.g. the contents of the jugs). SearchState specifies what the user needs to implement for her domain goalP, getSuccessors and sameState. The corresponding methods in SearchNode will in turn use these user-defined methods

So the (partial) design looks like this:
2.8.2 Data Structures
runSearch relies on the lists open and closed. How are we going to implement these
in Java? Notice

We cant pre-specify how many items (nodes) are going to be stored, For open we will need to remove items as well as add them.

This behaviour means that arrays are inappropriate here. We need more
flexibility. This flexibility is provided by linked lists (the standard  Data structure in
The Java Collection Framework provides a rich range of data structures covering
the spectrum between arrays and linked lists.

####### SYSTEM

####### USER

jug capacities
0 1 2 3 4 5 6
a b c d
block of
Linked List
follow the pointer
to find the next item
Move everything to make room
Create a new element and link it in
COM1005: AI Techniques 9 of 90
We will use ArrayLists, which support methods

add(Object) addition at right hand end or tail add(Object, index) adds item at specified position remove(Object, index) removes item at specified position

If all the elements in an ArrayList are of the same type, we can indicate this thus
This kind of declaration uses the generics mechanism.
For-each and Iterators
For all classes in the collections framework Java provides an easy way of stepping
through each element of the collection in turn (i.e. following the pointers in the case
of a linked list). This is done with a for-each statement or by creating an Iterator for
the collection. Examples soon..

2.8.3 Heres the code for SearchState: an abstract class which specifies what sub-classes must provide: /**

  • State in a state-space search
  • abstract class
  • must implement goalP, getSuccessors, sameState, toString / import java.util.; public abstract class SearchState { /**
  • goalP takes a SearchNode & returns a boolean if it’s a goal */ abstract boolean goalP(Search searcher);
/** getSuccessors returns an ArrayList of states which are successors to
* the current state in a given search
abstract ArrayList<SearchState> getSuccessors(Search searcher);
* sameState: is this state identical to a given one?
abstract boolean sameState(SearchState n2)
Note that

10 of 90 COM1005: AI Techniques

To decide whether a given state is a goal, we will generally need information which is defined for the current search problem – e.g. the target amount for Jugs. This is why goalP is given the current instance of Search. getSuccessors also needs the Search instance, for instance in Jugs we need to know what the capacities are for the current problem.

Now we can specialise SearchState for the Jugs domain: We have to choose the
internal representation of a state (2 ints j1 & j2) and provide, a constructor,
accessors and the methods required by SearchState:
* State in a jugs problem
import java.util.*;
public class Jugs_State extends SearchState{
private int j1; //content of jug
private int j2; //content of jug
The constructor is given the contents of the jugs..
public Jugs_State(int j1c, int j2c){
We provide accessors..
public int get_j1() {return j1;};
public int get_j2() {return j2;};
goalP picks up the target amount for the current search & checks against the jug
contents. Note that we have to cast the Search passed in to its concrete class
public boolean goalP(Search searcher) {
Jugs_Search jsearcher = (Jugs_Search) searcher; //cast as Jugs_Search
int tar=jsearcher.getTarget(); // get target amount
return ((j1 == tar) || (j2 == tar));
getSuccessors is a bit complicated for Jugs...
public ArrayList<SearchState> getSuccessors (Search searcher) {
Jugs_Search jsearcher = (Jugs_Search) searcher;
int cap1=jsearcher.getCap1();
int cap2=jsearcher.getCap2();
int j1Space=cap1-j1;
int j2Space=cap2-j2;
ArrayList<Jugs_State> jslis=new ArrayList<Jugs_State>(); // the list of
jugs states
COM1005: AI Techniques 11 of 90
ArrayList<SearchState> slis=new ArrayList<SearchState>(); //
corresponding SearchStates
if (j1Space > 0) jslis.add(new Jugs_State(cap1,j2)); //fill jug
if (j2Space > 0) jslis.add(new Jugs_State(j1,cap2)); //fill jug
if (j1 != 0) jslis.add(new Jugs_State(0,j2)); //empty j
if (j2 != 0) jslis.add(new Jugs_State(j1,0)); //empty j
if ((j1 != 0) && (j2Space != 0)) { //pour from j1 into j
if (j1 > j2Space)
{jslis.add(new Jugs_State(j1-j2Space, cap2));}
{jslis.add(new Jugs_State(0, j1+j2));};
if ((j2 != 0) && (j1Space != 0)) { //pour from j2 into j
if (j2 > j1Space)
{jslis.add(new Jugs_State(cap1, j2-j1Space));}
{jslis.add(new Jugs_State(j1+j2,0));};
// cast the jugs states as search states in slis
// this is a for-each
for (Jugs_State js:jslis)slis.add((SearchState)js);
return slis;
sameState compares the jug contents for this state with those of another..
public boolean sameState (SearchState s2) {
Jugs_State js2= (Jugs_State) s2;
return ((j1==js2.get_j1())&& (j2==js2.get_j2()));
Finally we provide a toString method..
public String toString () {
return "Jug State: Jug1-> "+j1+" Jug2-> "+j2;


Next we look at the SearchNode class.
import java.util.*;
public class SearchNode {
Any instance of a SearchNode will have a corresponding SearchState:

12 of 90 COM1005: AI Techniques

private SearchState state;
public SearchState get_State(){ //accessor for state
return state;
The SearchState will be provided when the node is created:
public SearchNode(SearchState s){
state= (SearchState) s;
SearchNode has methods goalP, getSuccessors & sameState which are used by
Search. goalP just calls the corresponding method for the nodes state:
public boolean goalP(Search searcher){
return state.goalP(searcher);
getSuccessors gets the list of successor states, then makes a corresponding list of
public ArrayList<SearchNode> getSuccessors(Search searcher){
ArrayList<SearchState>slis = state.getSuccessors(searcher);
ArrayList<SearchNode>nlis= new ArrayList<SearchNode>();
for (SearchState suc_state:slis){
SearchNode n = new SearchNode(suc_state);
return nlis;
sameState compares the states in two nodes:
public boolean sameState(SearchNode n2){
return state.sameState(n2.get_State());
Finally, toString adds more text to toString for the state:
public String toString(){
return "Node with state " + state.toString();
Now for the search engine...
* - abstract class specialising to Jugs_Search etc
import java.util.*;

COM1005: AI Techniques 13 of 90

import SearchNode;

import SearchState;

import sheffield.*; //for i/o

public abstract class Search {

We need to set up variables for open, closed, the current node etc. These will be protected – available only in instances of Search and its sub-classes:

protected SearchNode initNode; //initial node

protected SearchNode currentNode; // current node

protected ArrayList open; //open – list of SearchNodes

protected ArrayList closed; //closed – …….

protected ArrayList successorNodes; //used in expand & vetSuccessors

protected EasyWriter scr; //output to console window

The search algorithm is implemented by the runSearch method. This takes an initial SearchState from the user and (for the moment) returns a string indicating success or failure. The first thing to do is create an initial SearchNode for the initial state:

public String runSearch (SearchState initState) {

initNode= new SearchNode(initState); // create initial node

runSearch will generate a commentary as the search proceeds:

scr=new EasyWriter();

scr.println(“Starting Search”);

The initial conditions are that open contains the initial node and closed is empty :

open=new ArrayList(); // initial open, closed


closed=new ArrayList();

Well also count how many nodes have been expanded:

int cnum = 1; // counts the iterations

Now were ready to start the search. Each iteration of the while l oop expands 1 node. We stop either when the search succeeds (within the while) or open is empty.

while (!open.isEmpty()) {

// print contents of open


scr.println(“iteration no “+cnum);

scr.println(“open is”);

for (SearchNode nn: open) {

String nodestr=nn.toString();



14 of 90 COM1005: AI Techniques

selectNode(); // selectNode selects next node,
// makes it currentNode & removes it from open
scr.println("Current node "+currentNode.toString());
//- is current node a goal? - must pass current search to goalP
if (currentNode.goalP(this)) return "Search Succeeds"; //success,
//currentNode not a goal
expand(); // find successors of currentNode and add to open
closed.add(currentNode); // put current node on closed
}; //end of the while controlling the search
return "Search Fails"; // out of the while loop - failure
Expand has to find the current nodes successors and put them on open, unless
theyve been seen before. A method vetSuccessors checks that:
private void expand () {
// get all successor nodes - as ArrayList of Objects
// pass search instance to get_Successor of currentNode
successorNodes = currentNode.getSuccessors(this);
vetSuccessors(); //filter out unwanted - DP check
//add surviving nodes to open
for (SearchNode i : successorNodes){open.add(i);}
vetSuccessors removes any node if its state is the same as that of a node already on
open or closed: (the DP check):
private void vetSuccessors() {
ArrayList<SearchNode> vslis = new ArrayList();
for (SearchNode snode: successorNodes){
if (!(onClosed(snode)) &&
!(onOpen(snode))) vslis.add(snode);
vetSuccessors uses the following:
//onClosed - is the state for a node the same as one on closed?
private boolean onClosed(SearchNode newNode){
boolean ans = false;
for (SearchNode closedNode: closed){
if (newNode.sameState(closedNode)) ans=true;
COM1005: AI Techniques 15 of 90
return ans;
//onOpen - is the state for a node the same as one on open?
private boolean onOpen(SearchNode newNode){
boolean ans = false;
for (SearchNode openNode : open){
if (newNode.sameState(openNode )) ans=true;
return ans;
selectNode embodies the search strategy. For the moment, we take the last node
added to open. This becomes the currentNode & is removed from open:
private void selectNode() {
int osize=open.size();
currentNode= (SearchNode) open.get(osize-1); // last node
added to open
open.remove(osize-1); //remove it


Now we can specialise Search for Jugs problems. This just sets up the search
parameters (jug capacities and target) and provides a constructor and accessors for
the parameters.
* search for jugs problems
import Search;
import SearchNode;
import java.util.*;
public class Jugs_Search extends Search {
private int cap1; //capacity of jug
private int cap2; //........... jug
private int target; //target
public Jugs_Search (int c1, int c2, int tar) {

16 of 90 COM1005: AI Techniques

public int getCap1(){
return cap1;
public int getCap2(){
return cap2;
public int getTarget(){
return target;
Heres a top-level programme to try all this out:
import sheffield.*;
import java.util.*;
public class Run_Jugs_Search {
public static void main(String[] arg) {
// create an EasyWriter
EasyWriter screen = new EasyWriter();
// create the searcher
Jugs_Search searcher = new Jugs_Search(7,4,2);
// create the initial state, cast it as SearchState
SearchState initState = (SearchState) new Jugs_State(0,0);
String res = searcher.runSearch(initState);
2.8.9 Some Results
A: Capacities 7,4: Target 2
java Run_Jugs_Search
Starting Search

COM1005: AI Techniques 17 of 90

iteration no 1

open is

Node with State Jug State: Jug1-> 0 Jug2-> 0

Current node Node with State Jug State: Jug1-> 0 Jug2-> 0

iteration no 2

open is

Node with State Jug State: Jug1-> 7 Jug2-> 0

Node with State Jug State: Jug1-> 0 Jug2-> 4

Current node Node with State Jug State: Jug1-> 0 Jug2-> 4

iteration no 3

open is

Node with State Jug State: Jug1-> 7 Jug2-> 0

Node with State Jug State: Jug1-> 7 Jug2-> 4

Node with State Jug State: Jug1-> 4 Jug2-> 0

Current node Node with State Jug State: Jug1-> 4 Jug2-> 0

iteration no 4

open is

Node with State Jug State: Jug1-> 7 Jug2-> 0

Node with State Jug State: Jug1-> 7 Jug2-> 4

Node with State Jug State: Jug1-> 4 Jug2-> 4

Current node Node with State Jug State: Jug1-> 4 Jug2-> 4

iteration no 5

open is

Node with State Jug State: Jug1-> 7 Jug2-> 0

Node with State Jug State: Jug1-> 7 Jug2-> 4

Node with State Jug State: Jug1-> 7 Jug2-> 1

Current node Node with State Jug State: Jug1-> 7 Jug2-> 1

iteration no 6

open is

Node with State Jug State: Jug1-> 7 Jug2-> 0

Node with State Jug State: Jug1-> 7 Jug2-> 4

Node with State Jug State: Jug1-> 0 Jug2-> 1

Current node Node with State Jug State: Jug1-> 0 Jug2-> 1

18 of 90 COM1005: AI Techniques

iteration no 7
open is
Node with State Jug State: Jug1-> 7 Jug2-> 0
Node with State Jug State: Jug1-> 7 Jug2-> 4
Node with State Jug State: Jug1-> 1 Jug2-> 0
Current node Node with State Jug State: Jug1-> 1 Jug2-> 0
iteration no 8
open is
Node with State Jug State: Jug1-> 7 Jug2-> 0
Node with State Jug State: Jug1-> 7 Jug2-> 4
Node with State Jug State: Jug1-> 1 Jug2-> 4
Current node Node with State Jug State: Jug1-> 1 Jug2-> 4
iteration no 9
open is
Node with State Jug State: Jug1-> 7 Jug2-> 0
Node with State Jug State: Jug1-> 7 Jug2-> 4
Node with State Jug State: Jug1-> 5 Jug2-> 0
Current node Node with State Jug State: Jug1-> 5 Jug2-> 0
iteration no 10
open is
Node with State Jug State: Jug1-> 7 Jug2-> 0
Node with State Jug State: Jug1-> 7 Jug2-> 4
Node with State Jug State: Jug1-> 5 Jug2-> 4
Current node Node with State Jug State: Jug1-> 5 Jug2-> 4
iteration no 11
open is
Node with State Jug State: Jug1-> 7 Jug2-> 0
Node with State Jug State: Jug1-> 7 Jug2-> 4
Node with State Jug State: Jug1-> 7 Jug2-> 2
Current node Node with State Jug State: Jug1-> 7 Jug2-> 2
Search Succeeds
Process Run_Jugs_Search finished
B: Capacities 4,3: Target 2
java Run_Jugs_Search

COM1005: AI Techniques 19 of 90

Starting Search

iteration no 1

open is

Node with State Jug State: Jug1-> 0 Jug2-> 0

Current node Node with State Jug State: Jug1-> 0 Jug2-> 0

iteration no 2

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 0 Jug2-> 3

Current node Node with State Jug State: Jug1-> 0 Jug2-> 3

iteration no 3

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 4 Jug2-> 3

Node with State Jug State: Jug1-> 3 Jug2-> 0

Current node Node with State Jug State: Jug1-> 3 Jug2-> 0

iteration no 4

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 4 Jug2-> 3

Node with State Jug State: Jug1-> 3 Jug2-> 3

Current node Node with State Jug State: Jug1-> 3 Jug2-> 3

iteration no 5

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 4 Jug2-> 3

Node with State Jug State: Jug1-> 4 Jug2-> 2

Current node Node with State Jug State: Jug1-> 4 Jug2-> 2

Search Succeeds

Process Run_Jugs_Search finished

C: Capacities 4,3: Target 5

java Run_Jugs_Search

20 of 90 COM1005: AI Techniques

Starting Search
iteration no 1
open is
Node with State Jug State: Jug1-> 0 Jug2-> 0
Current node Node with State Jug State: Jug1-> 0 Jug2-> 0
iteration no 2
open is
Node with State Jug State: Jug1-> 4 Jug2-> 0
Node with State Jug State: Jug1-> 0 Jug2-> 3
Current node Node with State Jug State: Jug1-> 0 Jug2-> 3
iteration no 3
open is
Node with State Jug State: Jug1-> 4 Jug2-> 0
Node with State Jug State: Jug1-> 4 Jug2-> 3
Node with State Jug State: Jug1-> 3 Jug2-> 0
Current node Node with State Jug State: Jug1-> 3 Jug2-> 0
iteration no 4
open is
Node with State Jug State: Jug1-> 4 Jug2-> 0
Node with State Jug State: Jug1-> 4 Jug2-> 3
Node with State Jug State: Jug1-> 3 Jug2-> 3
Current node Node with State Jug State: Jug1-> 3 Jug2-> 3
iteration no 5
open is
Node with State Jug State: Jug1-> 4 Jug2-> 0
Node with State Jug State: Jug1-> 4 Jug2-> 3
Node with State Jug State: Jug1-> 4 Jug2-> 2
Current node Node with State Jug State: Jug1-> 4 Jug2-> 2
iteration no 6
open is
Node with State Jug State: Jug1-> 4 Jug2-> 0
Node with State Jug State: Jug1-> 4 Jug2-> 3
Node with State Jug State: Jug1-> 0 Jug2-> 2

COM1005: AI Techniques 21 of 90

Current node Node with State Jug State: Jug1-> 0 Jug2-> 2

iteration no 7

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 4 Jug2-> 3

Node with State Jug State: Jug1-> 2 Jug2-> 0

Current node Node with State Jug State: Jug1-> 2 Jug2-> 0

iteration no 8

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 4 Jug2-> 3

Node with State Jug State: Jug1-> 2 Jug2-> 3

Current node Node with State Jug State: Jug1-> 2 Jug2-> 3

iteration no 9

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 4 Jug2-> 3

Node with State Jug State: Jug1-> 4 Jug2-> 1

Current node Node with State Jug State: Jug1-> 4 Jug2-> 1

iteration no 10

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 4 Jug2-> 3

Node with State Jug State: Jug1-> 0 Jug2-> 1

Current node Node with State Jug State: Jug1-> 0 Jug2-> 1

iteration no 11

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

Node with State Jug State: Jug1-> 4 Jug2-> 3

Node with State Jug State: Jug1-> 1 Jug2-> 0

Current node Node with State Jug State: Jug1-> 1 Jug2-> 0

iteration no 12

open is

Node with State Jug State: Jug1-> 4 Jug2-> 0

22 of 90 COM1005: AI Techniques

Node with State Jug State: Jug1-> 4 Jug2-> 3
Node with State Jug State: Jug1-> 1 Jug2-> 3
Current node Node with State Jug State: Jug1-> 1 Jug2-> 3
iteration no 13
open is
Node with State Jug State: Jug1-> 4 Jug2-> 0
Node with State Jug State: Jug1-> 4 Jug2-> 3
Current node Node with State Jug State: Jug1-> 4 Jug2-> 3
iteration no 14
open is
Node with State Jug State: Jug1-> 4 Jug2-> 0
Current node Node with State Jug State: Jug1-> 4 Jug2-> 0
Search Fails
Process Run_Jugs_Search finished
2.9 Implementing State-Space Search for a new Problem Domain
This is a summary of what we have to do for a new domain:

Define a subclass of SearchState which

Represents a problem state in whatever way we choose.
Provides a constructor
Provides accessors for the state representation
Implements goalP, getSuccessors and sameState as specified.

Define a subclass of Search with variables for the search parameters and a constructor.

We then initiate a search by
Creating an instance of our search class
Calling runSearch for this instance, giving it the initial state.
Note that
 The algorithm terminates as soon as the first goal node is selected from
 It doesn't (yet) return a solution path, just an indication of success or
2.10 Reconstructing the Solution path
If it is necessary to reconstruct the solution path (as in the map-traversal problem, for
instance), we must keep a record of how we reached each node that we close:
together with each node we remember its parent node. To do this:

A parent variable is added to the Search-Node class. For the start node, there will be no parent: in Java, its parent will have value null (i.e. not initialised).

COM1005: AI Techniques 23 of 90

The expand method in Search is modified so that when new nodes are added to open their parent is set to currentNode.

When a search succeeds we need to reconstruct the solution path. Starting with the currentNode and working with closed, we follow the chain of parents until we come to a node with parent null. We need to print out or return the states on the solution path in order from the start node. Here is a method of Search to do this: it is called when the search succeeds and returns the solution path as a string. It also reports the efficiency of the search:

private String reportSuccess(){

SearchNode n = currentNode;

StringBuffer buf = new StringBuffer(n.toString());

int plen=1;

while (n.getParent() != null){






scr.println(“=========================== \n”);

scr.println(“Search Succeeds”);

scr.println(“Efficiency “+ ((float) plen/(closed.size()+1)));

scr.println(“Solution Path\n”);

return buf.toString();


For example, with capacities 7 & 4 and target 2 we get:

Search Succeeds

Efficiency 1.0

Solution Path

node with state Jug State: Jug1-> 0 Jug2-> 0

node with state Jug State: Jug1-> 0 Jug2-> 4

node with state Jug State: Jug1-> 4 Jug2-> 0

node with state Jug State: Jug1-> 4 Jug2-> 4

node with state Jug State: Jug1-> 7 Jug2-> 1

node with state Jug State: Jug1-> 0 Jug2-> 1

node with state Jug State: Jug1-> 1 Jug2-> 0

node with state Jug State: Jug1-> 1 Jug2-> 4

node with state Jug State: Jug1-> 5 Jug2-> 0

node with state Jug State: Jug1-> 5 Jug2-> 4

24 of 90 COM1005: AI Techniques

node with state Jug State: Jug1-> 7 Jug2-> 2
2.11 Elementary Search Strategies
How do we choose which node on open to expand next?
2.11.1 Depth-First Search
The selectNode method of Search which weve been using up to now:
private void selectNode() {
int osize=open.size();
currentNode= (SearchNode) open.get(osize-1); // last node added to open
open.remove(osize-1); //remove it
Implements depth-first search:
Each iteration expands one of the successors of the node expanded on the previous
iteration, until a goal is reached or a dead end (node with no successors) is found. In
this case, search will resume at the last level in the search tree where there is an
alternative. This is sometimes called Backing Up.
open behaves as a stack.. last in, first out.
Depth-first is guaranteed to find a solution, but not admissible.
2.11.2 Breadth-First Search
Expands all nodes at level l before moving to level l+1.
selectNode selects that node which has been on open the longest.
If nodes are added to the head of open, then selectNode should take the last node.

####### (0 0)

####### (7 0) (0 4)

####### (7 4) (3 4)

####### (3 0)

####### (0 3)

####### (7 3)

####### (6 4)

####### (6 0)

####### (2 4)

backing up
Depth-first search for jugs
with capacities 7 & 4
Target 2
COM1005: AI Techniques 25 of 90
open behaves as a Queue..first in, first out.
Guaranteed to find a solution.
Admissible in case of uniform costs.
The following implements breadth-first search:
private void breadthFirst(){
currentNode= (SearchNode) open.get(0); //first node on open

2.11.3 Compromises

Depth-Bounds: Search depth-first to some depth-limit N. Enforce backup from this level, but keep a list l of the nodes found at level N. If open becomes empty (i.e. searched completely to depth N without finding a solution), increase N, set open to l, and resume. Beam Search: Like breadth-first, but only expand from the best few nodes at each level. Assumes we have some way of deciding which they are.

Generally, we want to allow our user to choose which search strategy to use, by
naming the selectNode function to use in the call of runSearch: this is the next part
of the project.

2.11.4 Adding these improvements

The code in java\search2 reconstructs the solution path, returning it as a string, and
allows the user to choose either a breadth-first or a depth-first search. The strategy is
specified as an additional argument in the call to runSearch:
Jugs_Search searcher = new Jugs_Search(7,4,2);
SearchState initState = (SearchState) new Jugs_State(0,0);
String resb = searcher.runSearch(initState, "breadthFirst");
String resd = searcher.runSearch(initState, "depthFirst");

####### (0 0)

####### (0 3) (4 0)

####### (3 0) (4 3) (1 3)

####### (3 3) (1 0)

####### (4 2) (0 1)

Breadth-first jugs search
Capacities 3 and 4
Target 2
Nodes closed in numerical

####### 1

(^23) (^456)

####### 7 8

####### 9

26 of 90 COM1005: AI Techniques

Now selectNode chooses which of depthFirst and breadthFirst to call by
comparing with the given string. The default is breath_first. The old selectNode is
renamed depthFirst.
2.12 Branch-and-Bound search^1
We now turn to the more general case of search, where each move has a variable
cost associated with it. Our exemplar is map-traversal:
Branch-and-Bound is a generalisation of breadth-first.
Whereas breadth-fist chooses the node at minimum depth into the search tree from
Start, branch-and-bound chooses the node with minimum accumulated cost from
Branch-and-Bound explores on contours of increasing cost from Start:
select-node chooses that node from open with minimum cost from start.
Reduces to Breadth-First when costs are uniform.
Branch-and-Bound is admissible. Since it explores on contours of increasing cost,
the goal node chosen from open must be that one at minimum cost from Start.
This is why we dont stop the search as soon as a goal node appears during expand.
2.12.1 Implementing Branch-and-Bound Search
Code implementing map search is in java\search3.

(^1) Called Uniform Cost Search in Russell & Norvig A B C D E F G H I J Start Goal 8 12 10 7 20 20 12 10 15 20 12 15 25 15 18 15 10 20 18 4

Circles represent cost contours at 5, 10,15..(approx)

COM1005: AI Techniques 27 of 90

The user can choose breadth-first, depth-first or branch-and-bound search.

In search3,

The class Carta implements a map^2. A map is represented by a HashSet of city names and an ArrayList of MapLinks. An instance of the class MapLink represents an individual link between 2 cities, and its cost. Carta has methods to read a map from a file (mapFromFile^3 ), find all the cities in a given map (findcities), get the cost between 2 cities connected by a link (costBetween) and find all the links to a given city (getLinks). For variable-cost problems, SearchState needs a variable localCost for the cost of reaching a state from its parent in the search tree (the state in the currentNode). The subclass of SearchState for map-traversal problems is MapState. The getSuccessors method of MapState now has to fill in these localCosts for each successor. SearchNode needs variables localCost (copied from its state) and globalCost (the total cost from the start – 0 for the node representing the initial state) globalCost can be set either in getSuccessors for SearchNode or in expand in Search^4. It is the sum of the nodes localCost and currentNodes globalCost. It is necessary to implement the dynamic programming principle: that we only need to remember the best (i.e. minimum cost) route to a given state, e.g. When we find a successor which has the same state as one weve already seen, but not yet closed (i.e. there is a SearchNode N with this state on open) , we need to compare the globalCost of this SearchNode (cost of the old route, c) with c. This can be done within vetSuccessors: For any successor SearchNode N with globalCostt c, If x is not on open or closed, add a SearchNode for it to open. If x is on closed, ignore it (exercise: why is this safe?). If x is on open, then if c <= c , ignore x (old route cheaper) if c > c , (new route cheaper) change the globalCost of N to c change the parent of N to the currentNode

(^2) Its not called Map to avoid confusion with the Map interface (^3) The map were using as an example is in map1.txt (^4) The latter is coded in search3.

####### P

####### Q

####### R

####### S

####### 10

####### 15

####### 20

getSuccessors P
should returnMapStates with
city Q localCost 10
city R localCost 15
city S localCost 20

####### X

####### K

####### L

total cost 50 15
total cost 55

####### 8

Heretherearetwo routes to X
The route through K will be opened first
When the route through L is found,
we should forget about the one through K

28 of 90 COM1005: AI Techniques

The branchAndBound select-method then chooses that node on open with minimum cost. The class RunMapSearch tries all this out on the example map.

2.12.2 Performance of Branch-and-Bound
A branch-and-bound search for the best path from St to Gl in map1 should give
something like:
state parent cost
st nil 0
expanding st
state parent cost
c st 10
b st 12
a st 8
expanding a
state parent cost
d a 28
c st 10
b st 12
expanding c
state parent cost
g c 30
b st 12
d a 28
expanding b
found better route to g
state parent cost
f b 22
e b 32
d a 28
g b 27
expanding f

COM1005: AI Techniques 29 of 90


state parent cost

h f 26

g b 27

d a 28

e b 32

expanding h


state parent cost

gl h 44

j h 46

g b 27

d a 28

e b 32

expanding g


state parent cost

d a 28

e b 32

gl h 44

j h 46

expanding d


state parent cost

e b 32

gl h 44

j h 46

expanding e


state parent cost

i e 47

gl h 44

j h 46

expanding gl

30 of 90 COM1005: AI Techniques

Solution is (st b f h gl)
Cost 44
Effficiency 0.5
The efficiency of 0.5 exemplifies the problem with branch-and-bound: it is
undirected and so will waste effort on paths which are getting no nearer to the goal.
Here half the states expanded arent on the eventual solution path...and were using
an unrealistic map which only has links going roughly in the St-->Gl direction.
If we have no more knowledge to deploy, Branch-and Bound is the best algorithm to
use if we want to preserve admissibility.
However, there may be other knowledge to use...
2.13 Best-First Search
To improve on the efficiency of Branch-and-Bound, we need some knowledge about
the topology of the state space...are we going in the right direction?
Suppose we have available estimates of the remaining cost from any node n to a
goal node, i.e. a SearchState has a variable est_rem_cost which the user fills in in
her getSuccessors.
This is reasonable in many search problems e.g. in map traversal, if the map is a road
map, the estimates could be as the crow flies distances between cities.
Exercise: Its difficult to think of a way of getting estimates for jugs problems, but
what about the 8-puzzle? or equaliser?
Best-first search selects from open that node with minimum estRemCost, i.e. the
node that seems closest to the goal.
This is great when the estimates are good, but dangerous when they are not: it is not
2.14 The A* Algorithm
A combination of Branch-and-Bound and Best-First.
Suppose we have estimates of remaining costs as above.
A* selects that node n from open with minimum estimated total cost of a path
from start to goal through n.
This estimate is obtained by adding the globalCost (branch-and-bound) and the
estRemCost (best-first).
A* is admissible provided all the estRemCosts are guaranteed to be underestimates.
Informal Proof: The known distance along a complete, non-optimal path cannot be
less than an underestimate of the distance along the incomplete, optimal path. Hence
the wrong path cannot be selected from open.
Limiting cases:

If all the estimates are accurate, A* is optimal. If all the estimates are 0 (or identical), A* reduces to Branch-and-Bound. The better the estimates are, the more efficient A* is.

COM1005: AI Techniques 31 of 90

2.14.1 Converting branch-and-bound to A*

Changes to the search engine:

The user supplies estRemCosts for each SearchState SearchNode also has an estRemCost variable, copied from the state, and an estTotalCost which is globalCost+estRemCost. The A* selectNode function chooses from open using this field. vetSuccessors has to change because its now possible (if we have a serious underestimate of remaining cost) to find a better route to a node which is already on closed. When this happens (which should be rarely if the estimates are good), the node (X in the example above) should have its parent, globalCost and estRemCost changed, then it should be taken off closed and put back on open.

Code for the A* algorithm is in java\search4
A Larger Example
In java\search_usa is a map of the USA you can use to get a better feel for more
realistic search problems. Using the search4 code, explore the behaviour of the
different search strategies in this map. How much gain in efficiency for A* versus

2.15 Variants on the Search Problem

Hill Climbing
We have been assuming that it is possible to identify a goal state and test for it with
In some problems we cant do this. Instead we can measure the merit of a state but
we dont know what its best value will be. We have an  Objective function f(s) which
returns the merit for a given state s. The problem is to find the state which maximises
the objective function.
In hill climbing the search strategy is to select the successor state u of s state s which
maximises f(u)-f(s) and to stop when there is no successor which shows an

####### X

####### A

####### B

cost-sofar 10
cost-sofar 30
cost-sofar 35

####### 25

est-remaining-cost 10
est-remaining-cost 30

####### 5

X will be placed on open with parent A and estimated total cost 45.
This will be preferred to B, (estimated total cost 60).
X will thereforebe closed.
Later on, the better route through to X through B will emerge.

32 of 90 COM1005: AI Techniques

improvement, i.e. f(u)-f(s) <0 for all u. The problem is that this isnt admissible: it
will be fooled by local maxima:
There are a number of techniques for overcoming this problem, for instance
simulated annealing and genetic algorithms they all involve introducing some
randomness in the search.
Sequence Matching
Suppose you have the acoustic data for a spoken sentence. Your task is to find the
sequence of words which were spoken. You have some kind of model for each word.
You must search for the model sequence most likely to have generated the data. This
connected speech recognition problem is an example of sequence matching.
Other domains which involve sequence matching are in decoding convolutional
codes and in bioinformatics, a sequence alignment is a way of arranging the
sequences of DNA, RNA, or protein to identify regions of similarity that may be a
consequence of functional, structural, or evolutionary relationships between the
In speech recognition, the Viterbi Algorithm is commonly used for sequence
matching. We outline this at the end of the next section.
2.16 Search in Automatic Speech Recognition
An example of state-space searching in a larger scale application.
Automatic Speech Recognition (ASR) aims to provide voice input to computers.
Consider the simplified ASR problem of isolated word recognition, with a small
vocabulary (e.g. voice telephone dialling). Given a new word, which of the words
we know about is it most likely to be? We outline the Dynamic Time Warping
(DTW) method.

Information in speech is represented by the distribution of energy through time and frequency. Conventionally, this is portrayed in a spectrogram:

Spectro gram for a spoken eight
State returned

COM1005: AI Techniques 33 of 90

Think of the spectrogram as an image in which each pixel codes the energy at that frequency at that time. We might typically have around 100 time frames & 64 frequency channels. In DTW, we store an example of the spectrogram for each word in the vocabulary. These are called templates. We thus have a template library. Along comes a new word – the pattern. Heres another eight: We need a way of comparing the pattern with each template and picking the closest match. The problem is that two different utterances of the same word will vary in length, and the time-scale distortions will not be linear. We can compute a local distance measure for the similarity of a single time-frame of data in the pattern with a frame in the template. These distance measures are plotted in a time-time plane below: What we need is the minimum-cost path from bottom-left to top-right in the time-time plane – the total cost is the sum of the local costs of the cells on the path. We can impose constraints on path movements:

(i, j)

34 of 90 COM1005: AI Techniques

If we have the total cost to each of the predecessors, we can select the minimum, to find the best route to (i,j) and add the local cost at (i,j) to get its total cost. This is just the Dynamic Programming Principle again. We do this for each template and select that one with minimum total cost. DTW only works well only for small vocabularies of isolated words by a single speaker. For more difficult recognition problems we need to compare the incoming data with statistical models rather than templates, but the search principle is the same.

The Viterbi Algorithm
DTW can be extended to the connected word recognition problem: what is the best
sequence of templates to match the data?
In outline, the Viterbi algorithm
 Considers all the temples together,
 Moves forward in time using DTW, remembering the best way of matching
each template to time t, and its score,
 When a template completes, considers restarting each template at the next
time frame but adding to the score and remembering the path,
 At the end, delivers the answer: the best path through a template sequence
that finishes with a complete template match.
The technique can be extended to allow for a grammar which specifies what words
can follow what other words, or the probabilities of possible next words.
2.17 Constraint Satisfaction Problems
The states in a state space may have a structure which we can exploit to find a goal, rather
than blindly searching for one.
We consider a factored representation for a state:
 a state consists of a set of Variables X={X 1 ,X 2 , ..Xn} each of which has a value.
 The possible values a variable can take is called its Domain and in general each
variable has a different Domain D={D 1 ,D 2 , ..Dn}.
COM1005: AI Techniques 35 of 90
 In addition we have a set of constraints C which specify allowable combinations
of values. Applying the constraints changes the domains.

A solution is a set of values for the variables which satisfies all the constraints (i.e. the domain for each variable has cardinality 1).

Many everyday problems can be expressed in this way, for instance in Logistics:

Job Scheduling (e.g. building a house). The variables are tasks (dig foundations, erect scaffolding, ground floor brickwork, fix roof timbers…) and their domains are start times and end times. The constraints specify the order in which tasks must be done and their prerequisites (cant commence brickwork before bricks are on site). This is more complicated if you factor in how many workers you have, how many workers each task requires, the target completion date and so on.

Constraint Satisfaction problems can be solved by a mixture of constraint propagation and search.

 If a constraint is activated it will cause changes in the domains of the variables
involved, and these changes will lead to more changes and so on.
 If this activity does not yield a complete solution (i.e. some variables still have a
Domain with more than 1 value) then we have a search problem: the different
values correspond to different successor states. This is illustrated below:

Example: Sudoku

Problem (^) Solution Each row and column must contain each digit once only. Each 3×3 square must contain each digit once only.

36 of 90 COM1005: AI Techniques

In Sudoku,
 The variables are the 81 squares
 Their domains are {1,2..9} for an empty puzzle
 The problem start point reduces some of the domains to length 1 (e.g. to {5} in the
top left
This is the initial problem state
The constraints are that
 Each row and column must contain each digit once only.
 Each 3x3 square must contain each digit once only.
Note that it would be very inefficient to solve a Sudoku puzzle by search alone. We can,
however, use constraint satisfaction within a search:
Sudoku Search Algorithm (see java/search2_sudoku)
Using the search2 code,
  1. Put the initial node (built from the initial state) on open
  2. If open is empty, failure
  3. Select the first node from open (depth first say, strategy not important)
  4. Test for a goal state.. every cell has a domain of length 1
  5. If not a goal, apply constraint propagation:
Constraint Propagation takes the current state and applies the constraints to each cell
which still has a domain of cardinality >1.
If this leaves any cell with an empty domain there is no solution from this state (i.e. no
successor states).
If it produces at least 1 new cell with domain cardinality = 1, then make a single
successor state and add to open
If there is no new cell with domain cardinality = 1 then select the cell with minimum
cardinality & construct a successor state for each possibility. Add these to open.
  1. Repeat from 5
It seems that newspaper puzzles classed as easy can be solved by constraint satisfaction
alone, those classes as moderate require search
COM1005: AI Techniques 37 of 90
3 Game Playing
3.1 Why Program Computers to Play Games?

Skilled game-playing seems to involve important problem-solving abilities: look-ahead, planning, strategy, judgement. Games are well-defined, providing a tractable micro-world. Games provide an opport unity to test programs against each other, and against humans. There’s money in it (in recent years). It’s fun.

3.2 What kind of Games?
We will only consider

2 – opponent games with no chance element where both players have complete-knowledge of the state of the game

e.g. tic-tac-toe (noughts & crosses), drafts, chess, go, reversi....
There is also a body of work on other types of game, e.g. bridge, poker and
backgammon. In the latter, the world champion was beaten by a machine in about
3.3 Formulating Game Playing as State-Space Search
As before, our problem will be completely expressed by an internal structure called a
state, e.g. the positions of the pieces on the board & a note of who is to move. A state
completely defines the game position.
From a given state S 1 , the rules of the game will allow us to move to one of a
number of successor states S 11 , S 12 ...
We begin in some initial state Si. We have to find a route through state space that
leads us to a goal state. In game-playing a goal state represents a win (e.g.
row/column of 3 Xs, checkmate...).
3.4 Game Trees
In game playing by state-space search, we consider our moves from a given state, the
opponent's possible replies to each of these moves, our possible replies to his/her
replies etc. The resulting exploration of state-space is called a game tree. The
exploration process is called look-ahead.
Terminal nodes (leaves) in the game tree represent board positions where the result
of the game is known for certain, i.e. win, lose or (if allowed) draw.
The fundamental components of a game-playing program will be

A way of representing board positions (states),

38 of 90 COM1005: AI Techniques

A ‘legal move generator’ which embodies the l aws of the game; given a board, return a list of new boards – like getSuccessors in the search code. A means of detecting terminal board positions; given a board, return win/lose/draw/unknown. A program which explores the game tree.

3.5 MiniMaxing
Suppose we take a game which is simple enough for us to grow the complete game
tree (complete look-ahead), for instance
The Game of Piles (ako Grund ys game).
Start with 1 pile of tokens. A move consists of taking a pile and dividing it into 2
unequal piles. The last player who is able to move wins
Here is the state space if we start with 7 tokens:
We can decide on the move to make as follows:

Label the terminal nodes as win if the player to move next will win, loss if the player to move next will lose. In piles they will all be labelled loss.

Backtrack up the tree starting from the level above the terminals:

If all the successors of a node are labelled win then label this node loss. Otherwise label it win. Terminate when the root has been labelled. If it has been labelled win then find a successor of the root labelled loss and play that.

####### (7)

####### (6 1) (5 2) (4 3)

####### (5 1 1) (4 2 1) (3 2 2) (3 3 1)

####### (4 1 1 1) (3 2 1 1) (2 2 2 1)

####### (3 1 1 1 1) (2 2 1 1 1)

####### (2 1 1 1 1 1)

COM1005: AI Techniques 39 of 90
So in this case (see over) the original board position is a losing position - the second
player can force a win.

3.6 Java Implementation

Growing a game tree is similar to the search processes we have already seen. At the
end we have to do the backtracking rather than  report success.
Again we can write a domain-independent engine which can be specialised for
particular games. This can be based on the search2 code - we dont need variable
costs. The major changes will be
Abstract class GameSearch can be adapted from the Search class:
method run_GameSearch, derived from runSearch, grows a tree of
GameSearchNodes, either breadth-first or depth-first.
Instead of goalP we have resultP, which tells us whether a node is a
terminal. If it is, we dont look to expand it, but put it on closed and select the
next node.
On expanding a node, we can no longer ignore successor nodes with the
same state, because the same state at different points in the tree can lead to
different outcomes.

3.6.1 Naive Version

The search terminates when open is empty – we search the whole tree.
When this happens run_GameSearch calls a method minimax – see below.
Class GameSearchNode is adapted from SearchNode:
It now has additional variables children (the successor nodes), level (the
depth of this node in the tree) and a String outcome (whether this node
represents a win or loss for the player to move, or whether the outcome is
It has a resultP method rather than a goalP method, which calls the result
method of the subclass of GameSearchState. This returns win , loss or
unknown. resultP returns true for win or loss.

####### (7)

####### (6 1) (5 2) (4 3)

####### (5 1 1) (4 2 1) (3 2 2) (3 3 1)

####### (4 1 1 1) (3 2 1 1) (2 2 2 1)

####### (3 1 1 1 1) (2 2 1 1 1)

####### (2 1 1 1 1 1)


####### 2

####### 3

####### 4

####### 5

loss 6
win loss
loss win loss
win loss
win win win

####### 1

####### 1

40 of 90 COM1005: AI Techniques

Abstract class GameSearchState is adapted from SearchState & just specifies that
its subclasses must have methods result, getSuccessors and sameState.
The minimax method of GameSearch works as follows:
  1. Work through the tree -i.e. through closed – filling up the children slots, i.e. for each node n (except the root) with parent p, add n to ps children (alternatively you can do this within expand).
  2. Work back up the tree through the levels, starting at the maximum depth – 1.
  3. For each node at the current level that hasnt already been labelled, label it win unless all its children are win.
  4. When the root (the single node at level 1) has been labelled, return its label and, if its a win , the first node in its children labelled loss – this is the move to make.
3.6.2 Better Version
Avoids repeated work and backtracks as soon as possible rather than waiting until
the end of the search.
Keep 2 lists of nodes wins_found and losses_found which keep track of nodes for
which we have already discovered the outcome in the course of the search.
If a successor s of the current node n is a loss (either because result says so or
because its in losses_found, we know its parent can be labelled win.
Backtracking from a win
Any nodes already in the tree with the same state can also be labelled win.
Their successors can be removed from open, and so can their successors etc,
If any of the nodes labelled win now has all its children labelled win it can be
labelled loss, added to losses_found backtracking can proceed as below.
If all the successors of n are labelled win than n can be labelled loss and
backtracking takes place as follows:
Backtracking from a loss
Find all other nodes with the same state in the tree & label them loss.
Remove their successors (& their successors etc etc) from open.
Label their parents win, add them to wins_found and backtrack from these
wins as above.
The search terminates either when open is empty or when the initial state has been
labelled win or loss.
3.7 Evaluation Functions.
Because of the combinatorial explosion, in practice we can only afford to
explore a small part of the complete game tree, and we can't expect to reach the
terminal nodes.
If we can't search to terminal positions, we have to have a way of assessing the
positions we can reach.
COM1005: AI Techniques 41 of 90
If we call the 2 players MAX and MIN.
An evaluation function E(b) takes a board position b and returns a number which
expresses the merit of the position: the larger E(b), the more the position is judged as
favouring the player MAX, the smaller it is the better for MIN.
A popular form for E(b) is a weighted polynomial:
E(b) = w 1 f 1 (b) + w 2 f 2 (b) + ....
f 1 , f 2 ... are functions which measure features of the board position which seem to
be important, e.g. piece advantage, control of centre, mobility...
w 1 , w 2 ... are 'weights' which express the relative importance of the fi.
  1. It is arguable whether it is really legitimate to reduce a board position to a single number.
  2. E(b) is a static evaluation function. It does not try to take account of the dynamics of a game, e.g. a threat building up.
  3. E(b) is likely to be more accurate for simpler positions, e.g. when there are few pieces around. Its unlikely that E(b) will say much about the first move in chess, for instance.
  4. A polynomial form assumes that f 1 , f 2 … are essentially independent pieces of evidence. This may be unjustified.
  5. There will be a trade-off between how far we can search and how complex E(b) is, because it must be computed for each leaf node.

3.8 Partial Look-ahead

Given an evaluation function we can proceed as illustrated below:

Grow the tree as far as we can (typically to a fixed depth or ply). Compute v = E(b) for each leaf node. ‘Traceback’ or ‘back-up’ or ‘backtrack’ through the tree as follows: A node at a maximising level is given a backed-up value v’ which is the maximum value of its children.




(^2718) V

42 of 90 COM1005: AI Techniques

A node at a minimising level is given a backed-up value v’ which is the minimum value of its children. Eventually the root node will have backed-up values for all its children. If we are MAX, we make the move with maximum v’, vice-versa if we are MIN.

  1. We could have applied E(b) to the original children of the given board position and used these immediate estimates to decide our move. The argument for look-ahead and backtrack is that E(b) should be able to produce more accurate estimates later on, when board positions are ‘simpler’.
  2. There is an implicit assumption that the opponent is ‘thinking in a similar way to us’, i.e. has a similar evaluation function, and always chooses on this basis.
3.9 ALPHA-BETA Pruning.
There is a way of conducting a minimax backtrack without backing up all the
For each MAX node we keep a ‘provisional-backed-up-value’, , whose value
may rise but will never decrease.
i.e. we may find another child which is better for max, but any worse case can be
For each MIN node we keep a provisional-backed-up-value, , whose value may
fall but will never increase.
The pbvs become vs when all children have been explored.
This is another version of the dynamic programming principle: forget everything
except the best (or worst) path so far found.
The procedure is illustrated below:

Work from left to right, starting by diving down to the depth limit. Discontinue work below any node which won’t be chosen by its parent.





2 1






2 <=1


COM1005: AI Techniques 43 of 90

Well try a larger example on this..

####### NOTE:

  1. Alpha-beta is guaranteed to return the same value as a full minimax.
  2. Alpha-beta is an example of the ‘dynamic programming principle’ – in a state-space search you only need to remember the best route to a given node so far found.
  3. Alpha-beta may postpone the combinatorial explosion, but it doesn’t remove it: in the best case the number of static evaluations, s, needed to find the best move is given by s = 2b(d/2) 1 if d is even

= b(d+1)/2 + b(d-1)/2 – 1 if d is odd.

Where d is the search depth and the tree has uniform branching factor b.

This is illustrated below for d=3 and b=3.

44 of 90 COM1005: AI Techniques

The following compares full minimax with best-case alpha-beta
3.10 Adaptations of Brute-Force Search
3.10.1 Heuristic Pruning
Compared to skilled human play, a brute-force search spends most of its time
considering 'rubbish' - positions a good player would never bother with. In
heuristic pruning, moves from each node are ordered by their plausibility, and
search effort is expended according to that ranking. Low plausibility moves are
never considered. The tree takes on a 'tapered' look (see below).
Note that we may make a mistake - this is a heuristic method, not guaranteed.
COM1005: AI Techniques 45 of 90
The general name for this sort of technique is 'beam search'.

3.10.2 Book Moves

Serious computer game-playing programs make much use of libraries of standard
positions, with sometimes millions of entries. If a node represents a board position
which is in the library, we have effectively already done the search below that
A more powerful version of this would suggest whole sequences of moves to follow
until play diverts from a standard pattern - e.g. classic chess openings.
The difficult problem is to recognise not when a situation is identical to one
previously met, but which has a similar pattern , differing only in unimportant
respects. Skilled human players are very good at this intelligent pattern matching.
This ability is (in my opinion) closely-linked to human powers of perception. It has
been shown that expert chess players can memorise and recall board positions more
readily than novices.

3.10.3 Combating the Horizon Effect.

If we search to a fixed depth, we can wind up choosing moves which delay but do
not prevent disasters, e.g.
The disaster is 'beyond the horizon'. The program can seem to be throwing material
away, only postponing the inevitable.
One way of reducing the horizon effect is to continue search past situations which
are considered to be dynamic, e.g. check, imminent loss of a piece, pawn about to
Another idea is to back-up and chose a prospective move m, then grow a small,
secondary tree below the position p which m is expected to lead too. If the
backed- up value for p is much worse than E(p), think again.
pawn lost
queen lost
queen lost

46 of 90 COM1005: AI Techniques

3.10.4 Learning
In his classic work on Checkers or draughts (1959-67), Samuels attempted to get a
program to learn to play better by adjusting both the features fi(b) and their weights
wi in E(b).
The idea was to reward a win by increasing the wi for those fi which contributed
to the good moves, and punish a defeat in a similar way. If some wi became very
low, the corresponding fi was removed from E(b) and replaced by a new feature
chosen from a pool.
The learning regime was to have 2 computer players A and B play each other. A
used a fixed E(b), the best found so far. B starts with this polynomial, perhaps with
some random adjustments. B's polynomial is modified by
punishment-and-reward, as above. If B consistently beats A, B's polynomial is
moved to A.
Samuels achieved some success with this learning technique. His program
eventually reached world-class performance (but most games are drawn).
In general the problem is to devise a learning technique which will converge - which
is guaranteed to find an optimum solution. I don't know of any such 'training
theorems' for game-playing.
3.11 Comparison of Human and Machine Play
3.11.1 Strategy
A program using search techniques as described above would consider the
situation afresh on each move. It has no long-term plan or strategy. This is initially
disconcerting to a human opponent - the machine 'jumps around' rather than
pursuing some logical line of play.
3.11.2 Adaptability
Good game players vary their play according to who (or what) the opponent is. They
know the opponents strengths and weaknesses. The dumb machine would make
exactly the same response every time it was in a particular position.
Commonly the human struggles when first playing a particular program, but soon
learns to beat it. David Levy (who issued a challenge in 1968 that no computer
would beat him for 10 years) advocates making unusual opening moves so that the
program can't 'use its book'.
3.11.3 Search in Human Play
Overt search does play a part in expert-level play, but it often has the secondary role
of checking out a promising move that has been identified in some other way. The
search is very selective - very depth-first.
COM1005: AI Techniques 47 of 90

3.11.4 Expert Systems for Game Playing

Search-based techniques don't 'understand' the problem in any human sense.
They cannot, for instance, provide explanations. The only knowledge is in the legal
move generator and the evaluation function, where its implicit rather than explicit.
Can human knowledge about how to play a game be captured in a program?
Michie (1980) reported work on an expert system for chess end-games in which he
was able to demonstrate theoretically-correct play for some classic problems.
Knowledge-based systems are coming later...

3.11.5 Really Brute Force

Computer Chess has developed into a world of its own, and is no longer seen as
central to AI. Modern programs, still search-based but with specialist hardware and
massive libraries, now play at international master level. Programmes are widely
available which can beat all but the best few hundred humans. Kasparov was beaten
by IBMs deep blue in 1996. The following (from the San Francisco Chronicle)
summarises the match..
Speed, Not Artificial Intelligence, Is How IBM Won
1997 San Francisco Chronicle
For all its historic significance, Deep Blue's victory over world chess champion Garry Kasparov
wasn't really much of a scientific breakthrough, computer experts said Monday. In fact, the
consensus was that the 6-foot-5, 1.4-ton IBM computer depended less on artificial intelligence
than on raw computing power to dispatch Kasparov in their six-game series that finished
``The Deep Blue team used heavy computing to make up for a lack of cleverness in the
algorithms themselves,'' said John McCarthy, professor of computer science at Stanford
It may not have been quite that simple. IBM worked hard to improve Deep Blue's chances this
year, giving it a better gr Asp of chess openings and end games than it had in 1996, when
Kasparov won the first meeting.
IBM also hired chess grandmaster Joel Benjamin as a consultant this year. ``They sat down with
the grandmaster and fine-tuned the knowledge of how the computer judged some of the
positions,'' said David Wilkins, a senior computer scientist (and chess expert) at SRI in Menlo
Park. ``So it did have more and better chess knowledge this time.''
In the end, however, he said the real difference probably was Deep Blue's calculating speed,
which was doubled this year. It could analyze 200 million possible moves a second -- 50 billion
board positions in the three minutes given for each move. That kind of power, said Wilkins,
``will get you to human champion performance.'' Deep Blue employed searching and logic
techniques based in early artificial intelligence theory. But research into A.I. has now gone far
beyond chess-playing computers. Today, to have true artificial intelligence, a machine must be
able to respond to outside stimulus such as light, sound and movement.
If Deep Blue were able to actually ``look'' at the chessboard and decide how to play, it might
qualify. Right now, though, it's just a powerful computer whose real talent is to wear out its
opponent. Kasparov proved to be a case in point. After winning the first game of the match, the
champ surrendered in game two, even though experts said he could have gained a draw. The
next three games ended in draws, and in the finale on Sunday, Kasparov was practically a
basket case, botching his opening and losing in just 19 moves.
History will record this as the first time man was beaten by a machine, but that's not quite right.
``I don't think this is a story about mano a silicio,'' James Bailey, author of ``After Thought: The
Computer Challenge to Human Intelligence,'' wrote in Harper's magazine recently. ``It's about a
bunch of guys at IBM who by themselves had no chance of ever getting into an international
chess tournament, and therefore chose to collaborate with a computer.

48 of 90 COM1005: AI Techniques

``The computer by itself also didn't have a chance of making it into an international chess game.
But together they were able to go where neither of them could go alone.''
The real winner in the match, of course, was IBM itself, which owns and operates Deep Blue the
way George C. Scott managed Paul Newman in ``The Hustler.''
IBM gave the rematch a lot of hype, which entailed a risk, because if Deep Blue had lost badly --
worse than last year -- all the buildup would have been for nothing. With Deep Blue's triumph,
however, IBM has polished its image as a maker of fabulously fast computers.
COM1005: AI Techniques 49 of 90
4 Pattern Matching and Knowledge-based
Problem solving techniques in symbolic AI which go beyond blind searching
depend on the use of knowledge about the problem domain.
This knowledge must somehow be matched with the current problem-state: What
do we know which applies to the situation we are in?
Internally, we will be comparing data structures representing the problem state with
data structures which represent the knowledge. We need a knowledge
representation scheme (sometimes called an ontology).
There are various knowledge representation schemes but they all involve patterns
and their use is based on pattern matching.
This is the methodology of expert systems. The knowledge is confined to some
restricted problem domain.
In an expert system shell, the idea is to provide a general mechanism for this kind of
problem-solving, which the user can then adapt to her domain (like our search
4.1 Programming a pattern matcher
Fundamental to pattern matching is the idea of wild cards. You may be familiar
with this from the  Operating Systems MS-DOS and/or Unix:
chortle{pdg}41: cd /home/pdg/public/com1005/java/search1/simplejava
chortle{pdg}42: ls
Coordinates.class SimpleReader2.class SimpleCanvas.class
SimpleReaderException.class SimpleGraphicsWindow.class
SimpleWriter.class SimpleReader.class
chortle{pdg}43: ls Simp?eCan?as.class
chortle{pdg}44: ls Simple*.class
SimpleCanvas.class SimpleReader2.class
SimpleGraphicsWindow.class SimpleReaderException.class
SimpleReader.class SimpleWriter.class
chortle{pdg}45: ls C*.*
engine solution

50 of 90 COM1005: AI Techniques

So the wild cards are ?, which is allowed to match with any single character and *,
which matches against zero or more characters. They can be used alone or in
combination. We only need to think about the equivalent of ?.
In general, we can think of the wild cards as matching variables, and pattern
matching means find a suitable set of substitutions for matching variables which
makes one pattern identical to another. Another name for pattern matching is
The Java API doesnt supply this style of pattern matching^5 as part of the language,
so we need to provide our own facilities. The languages youll learn at level 2,
 Haskell and Prolog, have pattern matching as a central feature. In Lisp, pattern
matching is not part of the language itself, but there are packages for it. Lisp data
structures (lists) are well-suited to pattern matching.
Code for the matching classes we need is available in java\pmatch
Which can be imported as a package pmatch.
Well represent our patterns by Strings, using single spaces as delimiters between
elements in the pattern, so for instance if we are matching against colour apple
red we should get
Pattern to match Result
colour apple red true
colour apple green false
colour apple red size small false
colour apple ? true
colour orange ? false
? apple ? true
4.1.1 Bindings for pattern variables
When a match is successful, it is useful to remember what the wild cards matched
against. Well do this by giving the wild cards names that start with a ?, e.g. ?col. A
successful match establishes bindings for the pattern variables. The set of bindings
thus created is called a context:
Pattern to match Result Context
colour apple red true null

(^5) Java does have patterns in the form of Regular Expressions, regexps, which well make use of

COM1005: AI Techniques 51 of 90
colour apple green false null
colour apple ?col true ?col <= red
colour orange ?col false null
?prop apple ?val true ?prop <= colour
?val <=red
Where <= means is bound to.

4.1.2 The MString class

We need a class MString to implement pattern matching between Strings. We cant
implement this in the obvious way, as a subclass of String, because String is a
final class - it cant be subclassed. Instead we make it a subclass of Object whose
constructor takes a String as argument.
We need to split this string, and the string we are matching against, into words
separated by delimiters - single spaces in this case. This is sometimes called
tokenising^6. We can then iterate over the words - the tokens. There is a split method
of String to do this, e.g
String[] tokens = this is a test.split(" \\s");
for (String w: tokens){
The "\\s" is an example of a regular expression - it means a single space. split splits
the string its given using the regexp its given as the delimiter.
We also need to decide on how we are going to represent contexts. A context is a
table whose items associate variables (keys) with values (data). Java provides a
HashMap class which allows us to create tables, add items to them (method put),
retrieve items (get) etc.
Well allow pattern variables to appear in either (or both) patterns p1 and p2 we are
matching. To simplify things,

Each pattern variable can only appear once, We cant have variables in the same position in p1 and p2 (e.g. p1 = size apple ?s , p2 = size apple ?t ).

(^6) There are legacy tokeniser classes in Java.

52 of 90 COM1005: AI Techniques

We should really check that these conditions hold, but to save time we wont.
Heres the start of
public class MString extends Object {
private String str; //the string to be matched against
public String getStr() {return str;}; //accessor
private HashMap context; //the matching context
public HashMap getContext() {return context;} //accessor
public MString(String s){ str=s;}
public boolean match(String d){
String[] pTok = str.split("\\s"); //tokenise the MString - separate into words
String[] dTok= d.split("\\s"); //& the string it will match against
boolean result;
if (pTok.length != dTok.length)//unequal number of words
else {
context=new HashMap();
int j=0;
while (j<pTok.length && result){
String nextP=pTok[j];
String nextD=dTok[j];
if (!nextP.equals(nextD)){
if (pVar(nextP))
else {
if (pVar(nextD))
else result=false;
COM1005: AI Techniques 53 of 90
return result;
pVar here is a predicate telling us whether a string is a pattern variable:
private boolean pVar(String v){return(v.startsWith("?"));}
We can now use MString like so:
MString n1=new MString("one two three four");
boolean n1res=n1.match("one ?too ?free" four);
will return true and
Will print
{?too=two, ?free=three}

4.1.3 Additions to MString

Matching with an existing context
Often we want to do matches in sequence, using contexts from earlier matches:
MString m1 = new MString(I want to go from ?start to ?dest);
m1res=m1.match(I want to go from Sheffield to London);
MString m2=new MString(The train from Sheffield to London leaves at 0930);
m2res=m2.match(The train from ?start to ?dest leaves at ?time,
... will match & set the context of m2 to
{?start=Sheffield, ?dest=London, ?time =0930}
This is done by

Defining a second constructor for MString which takes an additional argument, the initial context. Whenever a pattern variable appears in the match, we look in the context to see if it has a binding. If so, we use this binding in the match.

Substituting back
The method mSubst is the inverse of matching: given an MString and a context,
return the MString with pattern variables in the context replaced by their bindings:
MString m3=new MString(Return from ?dest to ?start);
String sres=m3.mSubst(m1.getContext());
Return from London to Sheffield
Forward and Backward Contexts

54 of 90 COM1005: AI Techniques

It is sometimes important to be able to distinguish between matches for variables in
the given MString instance and matches for variables in the String we are matching
against. The method match2Way performs a match as before but returns two
contexts, one for the mvars in the mString instance which is called (pCon) and one
for the mvars in the String its matched against (dCon). e.g.
MString m4=new MString(?x weight heavy)
m4.match2Way(feather weight ?y)
m4.getpCon ==>{?x,feather}
m4.getdCon ==>{?y,heavy}
Well use this in backward-chaining later on. In this case we are allowed to have
mvars in the same place, and pCon takes precedence, e.g.
MString m5=new MString(?x parent of Fred)
m5.match2Way(?z parent of ?y)
m5.getpCon ==>{?x,?z}
m5.getdCon ==>{?y,Fred}
4.1.4 matching against a Vector of Strings
In the train example above wed want to try matching our pattern
The train from ?start to ?dest leaves at ?time,
in the context
{?start=Sheffield, ?dest=London}
against a whole train timetable, searching through the timetable until we find
something that matches. Rather than a single pattern we need to match against each
pattern in a Vector of patterns, until we find one that matches (well stop at the first
match found) or the Vector runs out. This facility is provided by the
MStringVector class.
MStringVector extends Object. The vector of patterns is a private variable v
which is an ArrayList of MStrings:
private ArrayList<MString> v;
Like MString, MStringVector has

a match method (two versions, with and without an initial context), an mSubst method, a variable context which is updated by a successful match.

Their behaviour is illustrated below:
MStringVector p = new MStringVector(PDG phone 21828| MPC phone 21822
|GJB phone 21817); //in the constructor, | separates MStrings
boolean res=p.match("MPC phone ?m");
returns true & v.getContext() returns {m=21822}
MStringVector w = new MStringVect or(Robbie at ?x|Suzie at ?y);
boolean res = w.match(Suzie at home)
COM1005: AI Techniques 55 of 90
returns true & w.getContext() returns {?y home}
HashMap con=new HashMap();
con.put(?x work);
con.put(?y play);
Vector res=w.mSubst(con);
returns a vector with elements Robbie at work , Suzie at play.

4.1.5 Additions to MStringVector Sometimes we want to find all the matches for a given String against a given MStringVector, not just one. The matchAll method does this. As usual, there are 2 versions, with & without an initial context. If it succeeds, matchAll sets up an ArrayList of the details of individual matches, which is accessed with getMatchDetails. Each item in this list is an instance of the MatchDetails class, and contains the pattern which matched, the rest of the MStringVector and the matching context.

4.2 Other Matching Facilities

We wont need the following in our programming but its worth discussing them

4.2.1 Restricting the match

We may wish to put restrictions on what is allowed to match against a variable, for
instance by specifying a predicate that must return true if the binding is allowed.
e.g. we may want arriving at ?x to match against arriving at Sheffield but
not against arriving at 0930. We need to define a predicate which must hold if the
match is to succeed. This is natural in a functional language because you can pass
functions as arguments. In Haskell youd say something like
match [arriving, at, (?x, townP)]
[arriving, at, Sheffield]
where townP is a predicate returning True if its argument is a member of a list of
town names.

4.2.2 Matching sequences We may want variables which are allowed to match against sequences of forms, rather than a single form. These are conventionally introduced with a *:

e.g. matching *pre arrives at *post against the train arrives at Sheffield at
1100 would succed & bind
{*pre=the train,*post=Sheffield at 1100}
* is allowed to match against 1 or more tokens, not 0 or more as in unix
Duplicating matching variables
We may want variables which occur more than once in the same pattern. In that case,
the first appearance establishes the binding, the remainder have to bind to the same:
e.g. matching go from ?x to ?y and back to ?x
would succeed against go from Sheffield to London and back to Sheffield

56 of 90 COM1005: AI Techniques

but not against go from Sheffield to London and back to York.
COM1005: AI Techniques 57 of 90
5 Rule-based systems
Here the knowledge is expressed in rules. This is the most common type of expert
A rule looks if
If a 1 and a 2 and a 3 .... then c 1 and c 2 and....

The ai are the antecedents. The cj are the consequents. If all the ai are met we can deduce all the cj. We can restrict ourselves to rules with a single consequent, without loss of generality (if there are n consequents we can have n rules, each with the same antecedents).

Rule-based systems create new knowledge from old by performing deduction
rather than induction or abduction (the other modes of inference).
Deductive systems are related to formal logic, and generally implement parts of
first-order predicate calculus. They usually do not have all of PC's expressive
power. More about this in year 2.
The antecedents and consequents are patterns containing pattern variables, for
instance we might have a rule
Grandfather rule
Antecedents: (?x is a grandparent of ?y)
(?x is male)
Consequent: (?x is a grandfather of ?y)
In LISP the lists would be written as above. In Java we are going to use strings, but
for simplicity we can drop that for now.

Note that a fact is a special case of a rule – one with no antecedents. The pattern variables play much the same role as quantifiers (for all, there exists) in logic. This kind of formalism is the basis of the programming language Prolog.

5.1 Forward and Backward Chaining
The inference engine can do its deduction in two ways. Suppose in addition to the
grandfather rule we have
Father-is-parent rule
Antecedent: (?x is the father of ?y)
Consequent: (?x is a parent of ?y)
Father-is-male rule
Antecedent: (?x is the father of ?y)
Consequent (?x is male)
Grandparent rule

58 of 90 COM1005: AI Techniques

Antecedents: (?x is the parent of ?y)
(?y is the parent of ?z)
Consequent: (?x is a grandparent of ?z)
5.1.1 Forward Chaining
Moves from antecedents to consequents:
If we are given the fact
(henry7 is the father of henry8)
The antecedents of the father-is-parent rule are triggered and the rule fires,
(henry7 is a parent of henry8)
and the father-is-male rule adds the deduction
(henry7 is male)
now if we are given
(henry8 is the father of Elizabeth)
The parent rule adds
(henry8 is a parent of Elizabeth)
and the antecedents of the grandparent rule are matched giving
(henry7 is a grandparent of Elizabeth)
finally the grandfather rule fires giving
(henry7 is a grandfather of Elizabeth)

Forward chaining is data-driven. Rules used in this way are sometimes called demons.

5.1.2 Backward Chaining
Moves from consequents to antecedents. Look for a rule that will allow us to make
the deduction we want, then try to prove its antecedents.
Suppose we want to find a grandfather of Elizabeth & we are given the same facts to
begin with.
We look for a rule whose consequent matches the pattern (our hypothesis).
(?x is a grandfather of Elizabeth)
& come up with the grandfather rule. We therefore try to prove its antecedents, given
what we know already:
(?x is a grandparent of Elizabeth)
(?x is male)
We check to see if any antecedents match directly with a fact. If not, we look for
rules whose consequents match. The grandparent rule leads us to look for
(?x is the parent of ?y)
(?y is the parent of Elizabeth)
COM1005: AI Techniques 59 of 90
Taking the second of these first, and using the father-is-parent rule we find that we
can satisfy this using the fact
(henry8 is the father of Elizabeth)
This gives us a value for ?y. We now look for
(?x is the parent of henry8)
and find a match through ?x -->henry7.
Were now back in the grandfather rule having deduced
(henry7 is a grandparent of Elizabeth)
Finally we prove, using the father-is-male rule that
(henry7 is male)

Backward chaining is hypothesis-driven. We are performing a blind search of the space of possible deductions. We may get a combinatorial explosion. We may have to backtrack. The deduction process is inherently recursive: forward chaining stops when no more deductions can be made. Backward chaining stops when we can match against a known fact, or when there are no rules whose consequents match what we are trying to prove. Substitutions must be correctly retained through the stages of a proof. Both forward and backward chaining are forms of monatonic reasoning. A fact always remains true: once asserted, it is never withdrawn.

5.2 Rule-based systems in Java

For both forward and backward chaining we need a class Rule to represent
individual rules and RuleSet to represent a collection of Rules. Rule has variables
private String[] antes; //no point in this being an ArrayList - it wont change
private String conseq;
and corresponding accessors. RuleSet has
private ArrayList<Rule> rules; //ArrayList because we may want to add rules
the following (in TestFChain) creates a small RuleSet:
String[]gfantes={"?gf father of ?p","?p parent of ?c"};
String[]fpantes={"?f father of ?c"};
Rule gfrule = new Rule (gfantes, "?gf grandfather of ?c");
Rule fprule = new Rule (fpantes, "?f parent of ?c");
//make the ruleset
ArrayList<Rule> rset = new ArrayList<Rule>();

60 of 90 COM1005: AI Techniques

RuleSet rs = new RuleSet(rset);
5.2.1 Forward Chaining in Java
The class FChain implements forward chaining through a method runFC. When
we create an instance of FChain (in TestFChain) we give it the RuleSet to use
FChain fc=new FChain(rset);
and the initial facts:
ArrayList<String> facts = new ArrayList<String>();
facts.add("H7 father of H8");
facts.add("H8 father of E");
and invoke forward chaining like so:
ArrayList<String> res=fc.runFC(facts);
runFC makes all the deductions it can & returns an ArrayList of the given facts and
the deduced facts.
runFC works as follows:
Keep a record of all the knownFacts and the ones which have not yet been pursued
i.e. we havent yet tried to make further deductions on the basis of them. Initially
knownFacts and toPursue are both set to the given facts.
Iterate the following until toPursue is empty:
Remove the first fact f from toPursue and make all
possible deductions from it:
Iterate the following over all the rules in the RuleSet
For each rule r, find all the matches for f against its antecedants (using
Each success constitues a partial match, in which there will be a matching
context and (in general) more antecedants to be satisfied. matchAll supplies
this information by returning a list of MatchDetails instances.
Iterate the following until the list of partial matches is empty:
Remove the first partial match p and develop it:
If p has no more antecedants, we have a deduction:
Substitute ps context in rs consequent (using mSubst) and add this new
fact to knownFacts and toPursue.
Take the first of ps antecedants and use matchAll to find all the matches
for it against knownFacts, given ps context.
Each successful match forms a new partial.

COM1005: AI Techniques 61 of 90


kf= [H7 father of H8, H8 father of E]

tp= [H7 father of H8, H8 father of E]

pursuing H7 father of H8

match for rule with antes [?f father of ?c]

Deduced H7 parent of H8

match for rule with antes [?gf father of ?p, ?p parent of ?c]

matching ?p parent of ?c

in context {?p=H8, ?gf=H7}

result = false

kf= [H7 father of H8, H8 father of E, H7 parent of H8]

tp= [H8 father of E, H7 parent of H8]

pursuing H8 father of E

match for rule with antes [?f father of ?c]

Deduced H8 parent of E

match for rule with antes [?gf father of ?p, ?p parent of ?c]

matching ?p parent of ?c

in context {?p=E, ?gf=H8}

result = false

kf= [H7 father of H8, H8 father of E, H7 parent of H8, H8 parent of E]

tp= [H7 parent of H8, H8 parent of E]

pursuing H7 parent of H8

match for rule with antes [?gf father of ?p, ?p parent of ?c]

matching ?gf father of ?p

in context {?p=H7, ?c=H8}

result = false

kf= [H7 father of H8, H8 father of E, H7 parent of H8, H8 parent of E]

tp= [H8 parent of E]

pursuing H8 parent of E

match for rule with antes [?gf father of ?p, ?p parent of ?c]

matching ?gf father of ?p

in context {?p=H8, ?c=E}

result = true

Deduced H7 grandfather of E

kf= [H7 father of H8, H8 father of E, H7 parent of H8, H8 parent of E, H7 grandfather of E]

tp= [H7 grandfather of E]

62 of 90 COM1005: AI Techniques

pursuing H7 grandfather of E
Result: [H7 father of H8, H8 father of E, H7 parent of H8, H8 parent of E, H7
grandfather of E]
5.2.2 Backward Chaining in Java
Well implement backward chaining as a search technique: we are searching the
space defined by all the links between the antecedants of one rule and the
consequents of another rule.
We could have done this for forward chaining too, rather than implementing it
Since we have uniform costs well make use of the Search2 code.
We need a subclass of Search for backward chaining - BChain _Search. This class
has a variable rules containing the ruleset (using the same classes as forward
chaining). TestBChain sets this up for the usual problem...
BChainSearch bc=new BChainSearch(rs);
We need to define a subclass of SearchStateinitState representing a state in the
backward chaining search:
A state will contain an ArrayList of goals gl. A goal will be a String which may
have. matching variables.
In addition we will keep an answer-variable-list (avl) in each state. This is used to
record values found for the variables in the original goal. The search succeeds when
a state is found with values for all the answer-variables, and no remaining goals.
For instance, this code (in TestBChain) creates the initial state in the search for
Elizabeths grandfather:
ArrayList<String> goals = new ArrayList<String>();
goals.add("?X grandfather of E");
HashMap avl = new HashMap(); avl.put("?X",null);
BChainState bstate = new BChainState(goals, avl);
BChainState must implement goalP, getSuccessors and sameState
goalP returns true if there are no more goals to satisfy & we have values for all the
answer variables:
public boolean goalP(Search searcher) {
if (gl.isEmpty()&&!avl.containsValue(null)) {return true;}
else {return false;}
sameState returns true if the two states have the same gl & avl. The action is in
Create an empty successsor list
COM1005: AI Techniques 63 of 90
Iterate the following for goal g in gl:
Iterate the following for each rule r:
Match the conseq of r against g, using match2Way
If there is a match, we are going to create a successor s..
Create the goal-list for s from the antecedants of r plus the other goals in gl
Use mSubst to substitute in this goal-list for mvars in the pCon and dCon
returned by match2Way.
Create the avl for s from the avl for this state by substituting any values for
answer vars that have emerged in dCon.
add s to the successor list
This is the depth-first search tree for the Elizabeths grandfather problem:

5.2.3 Things to try Add some more family tree rules (there are some in 5.4 below). Compare forward and backward chaining for the same problem. How much repeated work is there?

Goals [?X grandfather of E]
AVL {?X=null}
Goals [?X father of ?p, ?p parent of E]
AVL {?X=null}
Goals [H8 parent of E]
AVL {?X=H7}
Goals [E parent of E]
AVL {?X=H8}
Goals [?X father of ?p, ?p father of E]
AVL {?X=null}
Goals [H8 father of E]
AVL {?X=H7}
Goals [E father of E]
AVL {?X=H8}
Goals [?X father of H8]
AVL {?X=null}
Goals []
AVL {?X=H7}
matches [H7 father of H8]
matches [H8 father of E] matches [?p parent of E]
matches [H7 father of H8]
matches [H8 father of E]
matches [H8 father of E]

64 of 90 COM1005: AI Techniques

5.3 Rule Networks and Token-Passing
Implementing forward (and backward) chaining as above is hopelessly inefficient
because it duplicates work. There are two reasons for this:
  1. Within cycle repetition
In large rule sets it is common to find rules which share some antecedents, e.g.
Rule 1: if A and B and C and D then X
Rule 2: if A and B and C and E then Y
If we are matching antecedents independently for these 2 rules we repeat the work of
checking A,B and C.
We need to make use of the relationships between the rules by creating a rule
network. Then we can (automatically) create an intermediate node which captures
what these rules have in common: A and B and C.
  1. Between cycle iteration
Consider these 2 rules again. At a given time we might be able to match A,B and C
but go no further. Later on D is added to our facts. We dont want to go back through
the work of matching A,B & C again.
What we need to do is remember partial matches. These are called tokens. A token
holds the remaining antecedents and the context formed from those that have
5.3.1 Rule Networks
Lets add a few more family rules to our rule-set:
Rule Name Antecedents Consequent
father-is-parent (?f is the father of ?c) (?f is a parent of ?c)
father-is-male (?f is the father of ?c) (?f is male)
mother-is-parent (?m is the mother of ?c) (?m is a parent of ?c)
mother-is-female (?m is the mother of ?c) (?m is female)
grandparent (?gp is a parent of ?p)
(?p is a parent of ?c)
(?gp is a grandparent of ?c)
grandfather (?gp is a grandparent of ?c)
(?gp is male)
(?gp is a grandfather of ?c)
grandson (?gp is a grandparent of ?c)
(?c is male)
(?c is a grandson of ?gp)
grandmother (?gp is a grandparent of ?c)
(?gp is female)
(?gp is a grandmother of ?c)
granddaughter (?gp is a grandparent of ?c)
(?c is female)
(?c is a granddaughter of ?gp)
COM1005: AI Techniques 65 of 90
The rules are related like so: a link means that the consequent of one rule might
match with an antecedent of another rule (a successor rule)

####### .

We can create such a net automatically, given the rules. Each rule will have a
successor slot containing a list of successor rules

5.3.2 Tokens and forward-chaining We are going to implement forward chaining: we supply facts, one at a time, to the net. Every time a fact is supplied we make all the deductions we can.

Associated with each rule we maintain a list of tokens. Each token represents a
partial match for the antecedents of the rule we can make on the basis of what we
already know. Each token is a pair: the remaining antecedents and the context
formed by those antecedents that have already matched. Initially, each rule has a
single token, with all the antecedents and an empty context.
Whenever a fact becomes known that completes the match for a token, i.e. there are
no remaining antes, we can make a deduction. We report it (and maybe add it to a list
of known facts) and propagate it to all the successors of the rule (which may in turn
lead to other deductions....). This is called token-passing. Note that it ensures that a
deduction is only passed on to rules which might be able to make use of it.
Initially, the token-list for each node is set to contain a single token, with all the
rules antecedents and an empty context. So for the father-is-parent rule we have a
remaining-antecedents ((?p is the father of ?c))
context: ()
Whenever a new fact is supplied from the outside world, we propagate it to all the
rules. The fact is checked against all the tokens for each rule.
For instance, if we supply
(henry7 is the father of henry8)
This will match against the token in the father-is-parent token-list, producing a new
remaining-antecedents ()
context: (?p henry7 ?c henry8)
The token which matched remains on the token list - we want to pick up later facts or
deductions which match it, e.g. (henry8 is the father of Elizabeth).

66 of 90 COM1005: AI Techniques

Whenever a token has no remaining antecedents, we

remove it from the token-list use the context to substitute in the consequent and make a deduction (e.g print it out or add it to a list of deduced facts) propagate the deduction to all the rules successors.

So in this case (henry7 is a parent of henry8) is propagated to the grandparent
rule. There it creates 2 new tokens, because it will match with either antecedent
remaining-antecedents (?p is a parent of ?c)
context (?gp henry7 ?p henry8)
remaining-antecedents (?gp is a parent of ?p)
context (?p henry7 ?c henry8)
Similarly, the father-is-male rule will fire, deducing (henry7 is male) and
propagating to the grandfather-rule and the grandson rule.
Now if we add the fact (henry8 is the father of elizabeth)

The father-is-parent rule will deduce (henry8 is a parent of elizabeth) and propagate this to the grandparent-rule. This will match with the first of the 2 tokens created above for that rule, deducing (henry7 is a grandparent of elizabeth) and so on: this printout is from my lisp implementation: propagating to grandfather-rule deduction: (henry7 is a grandfather of elizabeth) propagating to grandson-rule propagating to grandmother-rule propagating to granddaughter-rule deduction: (henry8 is male) propagating to grandfather-rule propagating to grandson-rule

finally, if we add (Elizabeth is female), the granddaughter-rule will deduce
(elizabeth is a granddaughter of henry7)
This kind of algorithm is common in applications which involve deductive rule-sets,
for instance parsing in natural language processing and speech recognition. It was
originally developed in the context of the expert system R1, where it was called the
RETE match algorithm.
5.3.3 Java implementation of Rule Networks
see java\RuleNets
Object-oriented languages like Java are well-suited to implementing rule nets,
because each node in the   network becomes an instance of a class which represents

COM1005: AI Techniques 67 of 90

The class RuleNet represents a rule network consisting of a set of RuleNodes. RuleNet keeps track of the facts still to be propagated and, for each such fact, the list of RuleNodes to propagate it to. Its methods are

initialise - calls initialise for each rule in the network
addFact - receives a fact from the outside world, puts it on factsToPropagate,
puts rulenodes on targetNodeLists (so the fact will be given to each rule) and
calls propagate
propagate - pops the first fact from factsToPursue and the first node list from
targetNodeLists. Calls RuleNode.propagate to propagate the fact to each
node in the list. Gets back deduced facts, prints them out (or records them) and
adds them to factsToPursue. Adds the successors of the rule which deduced
each fact to targetNodeLists.

The class RuleNode represents individual rules in a rule network. Each rule has a name, a list of antecedants, a consequent, a list of successor RuleNodes and a list of Tokens. Its methods are

initialise sets the token list to contain the single initial token.
propagate matches an incoming fact against each Token by calling
Token.matchFact. If matches are found, adds the new Tokens to the token
list. Builds a list of deductions, each obtained by substituting (using mSubst
from the pmatch module) in the consequent for the context which completed
the match.

The class Token represents individual tokens attached to RuleNodes. Each Token has a list of remaining antecedants and a context so far established. The single method of Token is

matchFact which uses matchAll from the pmatch module to find all the
matches for a given fact. Each such match creates a matchdetails instance
from which matchFact builds a list of new Tokens and a list of contexts for
each completed deduction. matchFact returns true if any matches were found.
RunRuleNet RuleNet RuleNode Token
antes (remaining)
create the nodes
create the net
add facts 1 by 1

68 of 90 COM1005: AI Techniques

5.4 Production Systems
Unrestricted forward and backward chaining are prone to the combinatorial
explosion: they thrash around in the search space without progressing towards a
Production Systems implement forward chaining but provide a way in which the
behaviour of the deduction process can be controlled. Many expert system shells
resemble production systems. They have also been used to model human learning.
We keep a data structure called the short-term memory (STM). This consists of a
list of facts, like the initial facts and deductions in forward chaining. The difference
is that we are allowed to delete items from the STM, to keep things under control^7
Instead of rules we have productions. A production contains

a name a number of antecedents, which will contain pattern variables, as before a predicate on the pattern variable bindings, i.e. a function which is given the context resulting from a successful match of the antecedents and returns true or false. The production can only fire if the predicate returns true. a modifyContext function which takes the context after a successful match and modifies it, for instance to compute the value of a new matching variable. Examples below.

In some productions the predicate &/or modifyContext may not be needed.

a number of actions which are carried out if the production fires, in the context returned by modifyContext. There are three kinds of actions:

additions are patterns to be added to the STM (after substituting from the
deletions are patterns to be deleted from the STM (after substituting from
the context).
remarks are patterns to be printed out (after substituting from the
context).They are used to supply commentary and results.
A production system interpreter repeatedly

Scans through the productions in order until one is found whose antecedents match the STM, Checks the predicate for this prodn in the resulting context and, if this returns true, Runs the productions modifyContext fn, Fires the production, i.e. performs its actions in the resulting context.

This continues until no production fires.
5.4.1 Example: bagging
Robbie the robot has a job in a supermarket. As shopping items are passed through
the checkout, Robbie must put them into bags. A good bagging system will make
sensible decisions about what goes where, based on factors such as

How much space there is left in each unfilled bag,

(^7) In work modelling human learning, the maximum size of the STM is limited, to reflect the characteristics of human memory.

COM1005: AI Techniques 69 of 90

The size of the items, The weight of the items, How fragile each item is.

Bagging is an everyday example of the kind of problem solved by one of the most successful expert systems, R1, which configured DEC mainframe computers.

Here is a very simple production system for bagging, called bagger1. It makes the following simplifications:

all bags are 100 units high items are stacked one on top of the other we dont care about item fragility, weight etc.

Bagger1 simply takes each item in turn & tries to fit it in the current bag. If it wont go, a new bag is started.

The initial STM will tell us what is in the trolley, how much space each item needs and a note that will trigger the production which starts things off:

step is start bagging

trolley contains bread space 30

trolley contains spuds space 50

trolley contains cornflakes space 40

The step trick is commonly used to restrict the productions which are active at a given time.


Prodn No 1 Name: START_BAGGING

Antecedants: step is start bagging

Predicate: none modifyContext: none


deletions: step is start bagging
additions: step is get next item
current bag no 1 space 100
remarks: starting to bag

####### ——————————————————————

Prodn No 2 Name: GET_NEXT_ITEM

Antecedants: step is get next item

trolley contains ?I space ?S”

Predicate: none modifyContext: none


deletions: step is get next item
trolley contains ?I space ?S
additions: step is bag item

70 of 90 COM1005: AI Techniques

item to bag ?I space ?S
remarks: bagging ?I

####### ———————————————————-

Prodn No 3 Name: BAG_IN_CURRENT
Antecedants: step is bag item
item to bag ?I space ?S
current bag no ?N space ?BS
Predicate: ?BS>=?S
modifyContext: add ?RS <== ?BS-?S
deletions: step is bag item
item to bag ?I space ?S
current bag no ?N space ?BS
additions: step is get next item
?N contains ?I
current bag no ?N space ?RS
remarks: ?I in bag no ?N

####### ———————————————————–

Prodn No 4
Antecedants: step is bag item
current bag no ?N space ?BS
Predicate: none
modifyContext: add ?NB <== ?N+1
deletions: current bag no ?N space ?BS
additions: current bag no ?NB space 100
remarks: Starting bag ?NB

####### ————————————————————-

Notice that the order of the productions is important: START_NEW_BAG only fires
if BAG_IN_CURRENT doesnt: i.e. there isnt enough space in the current bag.
In general this isnt good enough, and attention has to be paid to the problem of
conflict resolution: if more than one rule has its antecedents and predicate satisfied,
which should fire?
5.4.2 Java Implementation

COM1005: AI Techniques 71 of 90

Java makes life difficult in this case, for reasons which expose its limitations for AI programming:

The natural thing is to have each production as an instance of a Prodn class, as we did with rules. But we need to specify different predicates and modifyContexts for different productions, i.e. different code. The only way we can do this is to write them as methods (as far as I know). But we cant have different methods for different instances of the same class. Therefore each production has to be coded as a different class. Prodn becomes an abstract class which individual productions are subclasses of.

Heres the code for the Prodn class:

public abstract class Prodn {

String name; //production name

String[] antes; //antecedants

String[] adds; //additions to stm

String[] dels; //deletions from stm

String[] remarks; //printouts on firing

//can’t give the accessor code here, otherwise don’t get val from concrete class

abstract String getName();

abstract String[] getAntes();

abstract String[] getAdds();

abstract String[] getDels();

abstract String[] getRemarks();

abstract boolean pred(HashMap context);

abstract HashMap modifyContext(HashMap context);


and heres the code for BAG_IN_CURRENT

public class b1BagInCurrent extends Prodn {

final static String name = “BAG-IN-CURRENT”;

final static String[] antes = {“step is bag item”,

“item to bag ?I space ?S”,

“current bag no ?N space ?BS”};

final static String[] adds = {“step is get next item”,

“bag ?N contains ?I”,

“current bag no ?N space ?RS”};

final static String[] dels = {“step is bag item”,

72 of 90 COM1005: AI Techniques

"item to bag ?I space ?S",
"current bag no ?N space ?BS"};
final static String[] remarks = {"?I in bag no ?N"};
//must define accessors here
public String getName(){return name;}
public String[] getAntes() {return antes;}
public String[] getAdds() {return adds;}
public String[] getDels() {return dels;}
public String[] getRemarks(){return remarks;}
public boolean pred(HashMap c){
Integer space_left = Integer.valueOf((String) c.get("?BS"));
Integer spaceNeeded = Integer.valueOf((String) c.get("?S"));
return (space_left.intValue()>=
public HashMap modifyContext(HashMap c){
Integer space_left = Integer.valueOf((String) c.get("?BS"));
Integer spaceNeeded = Integer.valueOf((String) c.get("?S"));
return c;}
The problem is that part of the knowledge that we wish to put into a production -
simply by writing it down - is in fact code that we want to execute at the appropriate
time. Java isnt set up for this.
In functional languages like Haskell (which youll learn in COM2010) life is easier
because we can create objects which represent functions and use them just like other
objects. For the pred fn in BAG_IN_CURRENT youd write something like
pred :: HashMap -> Boolean // pred is a fn that takes a HashMap
// & returns a Boolean
pred c = (get c ?BS)>=(get c ?S) // the code
In lisp its even easily because there is no distinction between code and data & you
dont have to mess around with type declarations. In your data structure for
BAG_IN_CURRENT youd say that the pred is
(>= ?BS ?S)^8
and the code for checking any predicate would be
(eval (mSubst pred context))

(^8) To perform a computation in lisp you form up a list of the function name followed by its arguments, & then evaluated it, e.g. (+ 1 2) evaluates to 3.

COM1005: AI Techniques 73 of 90

… where the worlds most useful function eval takes its textual argument as code and evaluates it. is the class for running production systems. It contains a method runPS which implements a production system interpreter as described above. runs bagger1 for the trolley contents above, producing


STM= [step is start bagging, trolley contains bread space 30, trolley contains spuds space 50, trolley contains cornflakes space 40]


in context {}


starting to bag

STM= [trolley contains bread space 30, trolley contains spuds space 50, trolley contains cornflakes space 40, step is get next item, current bag no 1 space 100]


in context {?I=bread, ?S=30}

GET-NEXT-ITEM remarks:

bagging bread

STM= [trolley contains spuds space 50, trolley contains cornflakes space 40, current bag no 1 space 100, step is bag item, item to bag bread space 30]


in context {?N=1, ?RS=70, ?BS=100, ?I=bread, ?S=30}


bread in bag no 1

STM= [trolley contains spuds space 50, trolley contains cornflakes space 40, step is get next item, bag 1 contains bread, current bag no 1 space 70]


in context {?I=spuds, ?S=50}

GET-NEXT-ITEM remarks:

bagging spuds

STM= [trolley contains cornflakes space 40, bag 1 contains bread, current bag no 1 space 70, step is bag item, item to bag spuds space 50]


in context {?N=1, ?RS=20, ?BS=70, ?I=spuds, ?S=50}

74 of 90 COM1005: AI Techniques

spuds in bag no 1
STM= [trolley contains cornflakes space 40, bag 1 contains bread, step is get
next item, bag 1 contains spuds, current bag no 1 space 20]
in context {?I=cornflakes, ?S=40}
GET-NEXT-ITEM remarks:
bagging cornflakes
STM= [bag 1 contains bread, bag 1 contains spuds, current bag no 1 space 20,
step is bag item, item to bag cornflakes space 40]
in context {?NB=2, ?N=1, ?BS=20}
START-NEW-BAG remarks:
Starting bag 2
STM= [bag 1 contains bread, bag 1 contains spuds, step is bag item, item to
bag cornflakes space 40, current bag no 2 space 100]
in context {?N=2, ?RS=60, ?BS=100, ?I=cornflakes, ?S=40}
cornflakes in bag no 2
STM= [bag 1 contains bread, bag 1 contains spuds, step is get next item, bag 2
contains cornflakes, current bag no 2 space 60]
final STM
[bag 1 contains bread, bag 1 contains spuds, step is get next item, bag 2
contains cornflakes, current bag no 2 space 60]
5.4.3 Things to try
Write a better bagger
COM1005: AI Techniques 75 of 90
6.1 Planning v. Search
In state-space search we find a sequence of actions which will transform an initial
state into a goal state. We do this by exploring state space starting from the initial
state and moving gradually away from it. If the information is available, we control
and guide the search using costs from the initial state and estimates of remaining
In planning, the problem is the same but the approach to finding the solution path is
different. Planning systems make use of knowledge about the potential actions (or
operators) that might be used, how each operator will change the problem state and
what preconditions each operator has, i.e. what is requires before the operator can
be used.
For instance, suppose Im planning a journey from home to a workshop in Patras,

I know about various operators to do with transport: walk, drive, take-taxi, take-train, take-plane, ….. I know that walk is good for short distances, take-plane for long distance and so on. I know that take-plane requires that Im at an airport and have a ticket, take-taxi requires that Im at a taxi rank and I have local currency etc.

To plan the solution to a problem

Compare the current state with the goal state, to find what it is that must be changed. e.g. a difference in location of around 2000 miles. Examine the potential actions, looking for something which is capable of making the change. take-plane fits the bill Having found a promising action, try to apply it. This means meeting its preconditions: I need to be at the airport with a ticket. Each unfulfilled precondition leads to a new problem: plan a way of meeting it. How am I going to get to the airport? These new problems are handled (recursively) in the same way.

Notice that we may find that some plan doesnt work out - I might try fly-to
Thessaloniki but then discover that theres no train or coach service from there to
Patras. I have to backtrack and consider fly-to Athens instead.
So planning involves looking ahead to consider what we might be able to do in
some future state. In search, we only look at what is possible from the current state.
6.2 Planning with STRIPS
The classic work on planning was done by Newell et al. and led to a scheme called
GPS (General Problem Solver). GPS introduced the planning scheme above, which
the authors called means-end analysis.
STRIPS (Fikes, Hart & Nilsson 72) is essentially an implementation of GPS with a
particular representation scheme for knowledge about operators. This is what well
look at.

76 of 90 COM1005: AI Techniques

As with search, we separate the planning mechanism from problem-specific
knowledge, so that we can solve planning problems in different problem domains. A
fallible Java implementation is available in
This directory also contains the pmatch package.
6.2.1 Representing Operators
The example well take is
Im in my living room and I want my friendly robot to get me a beer. The beer is in
the kitchen. To go from living room to kitchen the door has to be open.
Code for this problem is in in the strips directory.
The operators involved are carry, move, open-door and close-door. In STRIPS each
operator has

an actList, specifying what will be added to the plan if the operator is used (or applied) – the action to take. an addList, specifying what will be added to the current state if the operator is applied. a delList, specifying what will be removed from the current-state on operator application a list preconds of preconditions which must be satisfied (by changing the current state) before the operator can be applied.

Well have a class StripsOp to represent operators. It will have private variables
actList, addList, delList and preconds, together with their accessors. For the beer
problem the operators are
ator actList addList delList preconds
open open door from ?r1 to ?r2 door open ?r1 ?r2 door closed ?r1 ?r2 Robbie in ?r1
door closed ?r1 ?r2
close close door from ?r1 to ?r2 door closed ?r1 ?r2 door open ?r1 ?r2 Robbie in ?r1
door open ?r1 ?r2
move move from ?r1 to ?r2 Robbie in ?r2 Robbie in ?r1 Robbie in ?r1
door open ?r1 ?r2
carry carry ?obj from ?r1 to ?r2 Robbie at ?r2
?obj in ?r2
?obj in ?r1
Robbie in ?r1
?obj in ?r1
Robbie in ?r1
door open ?r2 ?r1
Each of these variables will be an MStringVector. There is a constructor which
takes them as Strings, using the character | to separate the list items.
COM1005: AI Techniques 77 of 90
The actList is the pattern for the action which will (with the appropriate
substitutions) go into the plan which is our final result. A plan is a list of actions. So
for the beer problem strips will return the plan
open door from living room to kitchen
move from living room to kitchen
carry beer from kitchen to living room
For the beer example the initial state is another MStringVector
"Robbie in living_room|beer in kitchen|door closed living_room kitchen"
and the goal list is an MStringVector with one element
"beer in living_room"

6.2.2 An OOP design for STRIPS see java\strips

The STRIPS planner can be coded as three mutually-recursive functions Strips1,
Strips2 and Strips3. All the functions are able to access the list of available
operators opLis (a list of instances of StripsOp) and are given an initState to work
on. We start the system by calling Strips1:

Strips1 is given a goal_lis and has the job of finding a plan to reach a state in which all the goals in goal_lis are met. It does this by finding differences between the goal_lis and the initState and calling Strips2 to deal with them. Strips2 is given the a difference and looks for an operator which can do something about it (reduce it). Having found an operator, it calls Strips3 to try to apply it. Strips3 is given an operator and a context in which to apply it (see below). It tries to meet the operators preconditions. If a precondition is not met in the current_state, Strips1 is called with the goal of finding a plan to satisfy it. When the preconditions have been met, the operator is applied, producing a plan and a new_state which will result if the plan is applied.

When they succeed, Strips1, Strips2 and Strips3 all produce a plan and a
new_state which results from applying the plan. They may fail, however..
In Java, Strips1, Strips2 and Strips3 are separate classes. Since they have many
variables in common well make them subclasses of an abstract class StripsFn:
public abstract class StripsFn{
goal diff
goal new-state
new-state new-state
plan plan

78 of 90 COM1005: AI Techniques

protected ArrayList<StripsOp> opLis; //operators
protected MStringVector goalState; //goal state
protected MStringVector initState; //initial state
protected MStringVector newState; //state after carrying out plan
protected ArrayList<String> plan; //final plan
protected boolean result; //success or failure
public ArrayList<StripsOp> getOpLis(){return opLis;}
public MStringVector getGoalState(){return goalState;}
public MStringVector getInitState(){return initState;}
public MStringVector getNewState(){return newState;}
public ArrayList<String> getPlan(){return plan;}
The Strips functions become methods called run in the classes Strips1, Strips2 and
Strips3. The run methods return a boolean, representing success or failure. If they
succeed, they set their variables newState and plan appropriately.
Whenever we need to call Strips1, Strips2 or Strips3 on a new problem, we create a
new instance. This is necessary because of the way they present their results, by
setting newState and plan. In a functional implementation we wouldnt do this,
wed just call the function..which would return its results in a suitable data structure.
To run Strips, we start (in by creating the operators:
StripsOp open = new StripsOp("open door from ?r1 to ?r2",
"door open ?r1 ?r2",
"door closed ?r1 ?r2",
"Robbie in ?r1|door closed ?r1 ?r2");
StripsOp closed = new StripsOp("close door from ?r1 to ?r2",
"door closed ?r1 ?r2",
"door open ?r1 ?r2",
"Robbie in ?r1|door open ?r1 ?r2");
StripsOp move = new StripsOp("move from ?r1 to ?r2",
"Robbie in ?r2",
"Robbie in ?r1",
"Robbie in ?r1|door open ?r1 ?r2");
StripsOp carry = new StripsOp("carry ?obj from ?r1 to ?r2",
"Robbie in ?r2|?obj in ?r2",
"?obj in ?r1|Robbie in ?r1",
"?obj in ?r1|Robbie in ?r1|door open ?r2
& then form them into an ArrayList:
ArrayList<StripsOp> beerOps = new ArrayList<StripsOp>();

COM1005: AI Techniques 79 of 90





Then we create an instance of Strips1, giving it the operators, initial state and goal list.

Strips1 str=new Strips1(beerOps,

new MStringVector(“Robbie in living_room|beer in kitchen|door closed living_room kitchen”),

new MStringVector(“beer in living_room”));

Then we start the planning by


Heres Strips1:

import java.util.*;

import StripsFn;

public class Strips1 extends StripsFn{

//constructor given opLis, initState, goal state

public Strips1 (ArrayList opl,

MStringVector is,

MStringVector gs)






//run problem solver

public boolean run(){






//look for a difference

boolean diffound=false; //set to true when diff found

String g=new String(); //where the diff found will go

Iterator git=goalState.iterator();

while(git.hasNext()&& !diffound){ //iterate over goals

80 of 90 COM1005: AI Techniques

//try to match goal g within state - initState is an MStringVector
diffound=!initState.match(g); //becomes true if goal not matched
//end of the while...was a difference found?
if (!diffound){
result=true; //no difference found - trivial success
newState=initState; //end state same as initState
plan=new Vector(); //empty plan
return result;
else{ //found a diff, use Strips2
Strips2 strips2=new Strips2(opLis,initState, goalState,g); //make instance
//Strips2 needs opLis, initState, goalState and difference - the goal not met
boolean; //run it
if (!s2res){ //did Strips2 succeed?
result=false; //no, failure
return result;
else { //strips2 succeeded - call Strips1 again with state returned
//must be a new instance - state will have changed
Strips1 nstrips1=new Strips1(opLis, strips2.getNewState(),goalState);
boolean; //run the new Strips1
if (!nstrips1res){ //did it succeed?
result=false; //no, failure
return result;
else { //success
//complete plan is strips2 plan + strips1 plan
newState=nstrips1.getNewState();//final state is that returned by
return result;
COM1005: AI Techniques 81 of 90


import java.util.*;
import StripsFn;
public class Strips2 extends StripsFn{
String diff; //difference to reduce
public Strips2 (ArrayList<StripsOp> opl,
MStringVector is,
MStringVector gs, String d)
//run problem solver
public boolean run(){
System.out.println(working on +diff);
result=false; //set to true when diff dealt with
Iterator opit=opLis.iterator();
//search for an operator to reduce the diff, then call strips3 to apply it
while (opit.hasNext()&& !result){ //try ops till one succeeds or none left
StripsOp op= (StripsOp);
boolean matchres=op.getAddList().match(diff); //match diff against addlist
if (matchres){ //op can deal with diff
HashMap con=op.getAddList().getContext(); //in this context
System.out.println("calling Strips3 to apply operator
//call strips3 to attempt to apply op
//Strips3 needs the context
Strips3 strips3 = new Strips3(opLis, initState, goalState,op,con);

82 of 90 COM1005: AI Techniques

boolean; //run Strips3
if (strips3res){ //strips3 succeeded
plan=strips3.getPlan(); //Strips2 plan is Strips3 plan
newState=strips3.getNewState(); //new state is Strips3 new state
return result; //will be false if no op succeeded
6.2.5 Strips3

The run method of Strips3 has the task of applying an operator. Strips3s constructor looks like public Strips3 (ArrayList opl, MStringVector is, MStringVector gs, StripsOp o, HashMap con) { opLis=opl; //operators initState=is; //initial state op=o; //operator to apply context=con; //incoming context } The first job is to meet ops preconditions. Well have a separate method meetPreconditions to do this. It will return a boolean, true if the preconds have been met. If meetPreconditions returns false, Strips3 returns false if meet-preconditions succeeds it will produce a plan, prePlan which will result in a new state, preState. It will also establish a new context, pCon. These will be private variables of Strips3. For example, if we are trying to apply move in the context {?r2= kitchen} and current_state contains Robbie in living_room well satisfy the precondition Robbie in ?r1 in the context {?r1=living_room, ?r2= kitchen} we can now at last apply the operator. A separate method applyOp is called to do this, given op, pre_state and pre_con. to apply an operator to a state given a context, we use the ops delList to find what needs to be deleted from the state, the addList to find what must be added and the actList to work out the 1-action plan (aPlan) for applying the operator. For all these, we use the mSubst method (they are MStringVectors) to replace ?vars with their matching values in the context after meeting the preconditions, precon. There are addAll and removeAll methods of Vector which will do the job of establishing the state after applying the operator, newState – the state after Strips3 has done its job.

COM1005: AI Techniques 83 of 90

The final plan after applying the op is the concatenation of the plan returned by meetPreconditions, prePlan, and the plan returned by applyOp, aPlan.

6.2.6 Meet-preconditions

meetPreconditions iterates through ops preconds trying to meet each one. Stopping conditions are when no preconds remain (success) or we fail to meet one (failure). Before starting this iteration, we need to set up the following: preState=initState; //state having met some preconds pCon=context; //context after having matched some preconds prePlan=new ArrayList(); //plan for preconds, initially empty For a given precond p, we call the match method of initState, giving it the current context: boolean matchres=initState.match(p,pCon) If matchres is true, we update pCon & move on to the next precondition. If matchres is false, we need to invoke a new instance of Strips1 and use it to solve the new problem of meeting this precondition. To specify what the goal is for this new Strips1, we need to substitute for the context in p (e.g. we are trying to apply carry in the context {?r2=kitchen}. Well need to satisfy the precondition Robbie in ?r2. For the new call of Strips1 we need to make the goal Robbie in kitchen. The new Strips1 will either succeed or fail. If it fails then Strips3 fails. If it succeeds, its plan is added to prePlan and its newState becomes preState.

6.3 The beer example

Here we go... printouts from my lisp version...
goal-list ((BEER IN LIVING-ROOM))
current-state ((ROBOT in LIVING-ROOM)
--> calling STRIPS2 to deal with (BEER IN LIVING-ROOM)
current-state ((ROBOT in LIVING-ROOM)
--> calling strips3 to try op (CARRY ?OBJ FROM ?R1 TO ?R2)

84 of 90 COM1005: AI Techniques

current-state ((ROBOT in LIVING-ROOM)
calling STRIPS1 to meet precondition (ROBOT in KITCHEN)
goal-list ((ROBOT in KITCHEN))
current-state ((ROBOT in LIVING-ROOM)
--> calling STRIPS2 to deal with (ROBOT in KITCHEN)
current-state ((ROBOT in LIVING-ROOM)
--> calling strips3 to try op (MOVE FROM ?R1 TO ?R2)
op (MOVE FROM ?R1 TO ?R2)
context (?R2 KITCHEN)
current-state ((ROBOT in LIVING-ROOM)
calling STRIPS1 to meet precondition (DOOR-OPEN LIVING-ROOM KITCHEN)
current-state ((ROBOT in LIVING-ROOM)
--> calling STRIPS2 to deal with (DOOR-OPEN LIVING-ROOM KITCHEN)
current-state ((ROBOT in LIVING-ROOM)

COM1005: AI Techniques 85 of 90



–> calling strips3 to try op (OPEN DOOR FROM ?R1 TO ?R2)




current-state ((ROBOT in LIVING-ROOM)



op applied with plan ((OPEN DOOR FROM LIVING-ROOM TO KITCHEN))




–> dealt with (DOOR-OPEN LIVING-ROOM KITCHEN) – try STRIPS1 again




op applied with plan ((MOVE FROM LIVING-ROOM TO KITCHEN))

giving state ((ROBOT in KITCHEN)



–> dealt with (ROBOT in KITCHEN) – try STRIPS1 again


goal-list ((ROBOT in KITCHEN))



giving state ((ROBOT in LIVING-ROOM)



–> dealt with (BEER IN LIVING-ROOM) – try STRIPS1 again


goal-list ((BEER IN LIVING-ROOM))



86 of 90 COM1005: AI Techniques

6.4 Limitations
Strips as implemented above is pretty crude: you should try to break it.

The operators have to come in the right order Its possible to satisfy goal A, then work on goal B and in doing so undo goal A – goal conflict. Its thus possible to get into an endless recursion. Theres no attempt to decide which goal its best to work on next. The representation scheme is pretty unwieldy.

Later work on planning has attempted to address these limitations.
6.5 Things to try
Devise stacking problems which exemplify the limitations above.
7 AI and Perception

R.L. Gregory, Eye and Brain R.L. Gregory, The Intelligent Eye J.P. Frisby, Seeing.

In this course weve studied AI systems that look like so:

The knowledge base available to the problem-solver is expressed in data structures that make use of some knowledge-representation scheme. The problem is expressed in a compatible data structure. The problem-solver applies the knowledge to the problem by doing symbolic manipulation using these data structures. The result is another data structure.

problem-solver result

COM1005: AI Techniques 87 of 90

The data structures representing the knowledge and the problem are provided by the user.

But real intelligent systems have to function without this help:

Perceptual systems have to make sense of data reaching the system from the outside world, The system acquires knowledge by learning (in a variety of ways), Motor systems have to convert decisions made by the system into actions.

88 of 90 COM1005: AI Techniques

7.1 The problem of perception
Perception in living systems works so well that the difficulty of the task isnt
obvious. We can get a feel for what is happening by driving the system to its limits:

Here, there are few cues to indicate object boundaries and depth. The processing which perceives the object must be active & knowledge-based, not passive transduction. Perception imposes an organisation on the sensory data: it makes features explicit.. This example is not so atypical of what happens all the time, and in other modalities besides vision, e.g. we hear pauses between words which arent physically there. It is often easier to write the problem-solving part of an AI system than it is to provide the system with adequate perception.

7.2 Gregorys Perceptions as Hypotheses Metaphor
We can think of perceptions as being like hypotheses in science:

perceptions explain the data in terms of arrangements of known objects (in vision), perceptions are used to predict – to hidden parts of objects, to the future..

Perception works so well that its difficult to study without devising ways of making
it malfunction. Psychologists have therefore studied perception through illusions. If
the system can be confused, or fooled, what does that reveal about its properties?
7.2.1 Ambiguous figures
COM1005: AI Techniques 89 of 90

7.2.2 Paradoxical Pictures

7.2.3 System error!

Two viable hypotheses.
Perception alternates
Many effects are due to
depth perception
The figures suggest familiar objects.
Though the evidence isntconsistent,
the system continues to believe the
In these cases, there is a correct but unusual hypothesis, but the system prefers the
more normal one:
Fraser Spiral
Ames Room

90 of 90 COM1005: AI Techniques

7.2.4 Distortion Illusions
7.2.5 Gestalt Grouping Principles
7.2.6 Perceptual Invention
7.3 Conclusions

Perception is an intelligent problem-solving activity, involving much of the cortex. Perception and reasoning have a rich interaction. There is a similar argument for motor activity.

Muller-Lyer Ponzo
Figures are interpreted as 3D scenes. Size constancy operates where it shouldnt.
similarity,continuity,proximity,common fate..
Kanitsasfigure: why is the illusory triangle perceived as brighter?