1) Create OpenList

2) Push the initial state (start) on to OpenList, set its cost to 0 and set its parent to 0.

3) Until a goal state is found or OpenList is empty do:

(a) Pop the first (best) element from OpenList and call it 'current'.

(b) If OpenList was empty, return failure and quit.

(c) If 'current' is the goal state, return success, construct the path and quit.

(d) For each rule that can match 'current' do:

i) Apply the rule to generate a new state and call it 'n'

ii) The cost of the new state is the cost of 'current' added to the cost of moving from 'current' to 'n': newcost = current.cost + cost(current, n)

iii) If 'n' is on OpenList and newcost >= existing_n.cost then skip the rest of the loop and go back to (d)

iv) If 'n' is on OpenList then let 'n' now refer to existing_n.

v) Set the parent of 'n' to 'current'. Set the cost of 'n' to newcost.

vi) If 'n' was not on OpenList then push 'n' on to OpenList.

vii) Reorder OpenList by cost (since either the cost of 'n' has been updated or 'n' has been pushed onto OpenList).