Search in AI
and “hope for the best,” or else develop
Chapters 3,4,&6 in your Text
vicinity. If you follow this later course,
Now What Do I do?
How Can an agent decide what to do?
In our initial discussion, I’m going to use the term AGENT
Think back to our water-jugs problem
Likely a term you’ve heard before, e.g. a secret agent or real-estate agent. Something performing tasks on another’s behalf
An agent can consider possibilities systematically until it comes up with a sequence that lets it do what is needed to achieve its goal
systems metaphor: an agent is a system that perceives its environment and acts on those perceptions
• and use knowledge to reduce what it has to consider
This doesn’t imply much sophistication: the clock in my PC that adjusts for daylight savings time is an agent
This is called planning – we’re using a search process to construct a plan to achieve our desire
An intelligent agent is one that acts intelligently (see our discussion on intelligence)
We do this all the time
Doing the Right Thing
“In order to cope, an organism must
either armor itself (like a tree or a clam)
methods for getting out of harm’s way
and into better neighborhoods of the
you are confronted with the primordial
problem that every agent must
continually solve: Now what do I do?”
• D.Dennett, Consciousness Explained, in Luger, p. 75
Does every agent have to plan?
34 © 2020 J.E. Anderson © 2020 J.E. Anderson
2 © 2020 J.E. Anderson
Crickets don’t plan. Neither do most animals.
Biologically, these are creatures like crickets (for example) whose responses to the world are selected over many generations through evolution
NO
Reactive Agents
Plenty of simple agents don’t do anything this complex
It depends on the richness of the agent’s domain and
Very simple agents react to their environment purely – they have no ability to remember previous situations or do any learning (at least what we’d call learning)
what it takes to be successful in it
They don’t operate in our world, but they DO find food, avoid enemies, and reproduce – boundaries of their life
We generally want more than this (though you’d never know it from watching the people on reality TV), which is why we DO plan
have a built-in mapping (a function!) of perception to action
But it IS possible to deal with simple situations without it 5
Pure reaction good enough for many environments
But not for those that require significant sequences
Reactive Agents with State
Agents that can Search
Adding the ability to remember a state makes an agent much more interesting
Assuming we have reaction too (we’ll get to combining these later!) we have the best of both worlds
We can do some learning, in that the agent can recall what it has seen before and use that as input to its choice
Still largely insect-level intelligence
Agents that can search can solve problems like the water-jugs and other puzzles, as well as putting together sophisticated sequences of physical actions (e.g. a driving route plan).
There are behaviourists that argue that even human level intelligence arises out of this (see Brooks), but it isn’t demonstrable and it’s complex enough to be hard to envision
Exploring issues and working out details before trying to do anything (searching a hypothetical space)
Certainly SOME of our behaviour does
This may be a physical search as well 78
© 2020 J.E. Anderson
of actions 6 © 2020 J.E. Anderson
© 2020 J.E. Anderson © 2020 J.E. Anderson
0,0
2,3 0,3
0,5 2,3 •
• • •
e5
e2
p52
•
a few issues are different (e.g. backing up is hard to do physically for emptying water)
e5
0,5 0,5
p25
Path planning is itself a vital part of robotics, and in virtual areas like gaming as well
2,0
0,5
e2
p52
However the search we use here is equally applicable to searching through a problem space as opposed to searching a physical space
Problem States
Problem Space
A problem state is a problem’s configuration at a specific point in time (i.e. after a particular set of rules/operators has been applied)
From the concept of a state we can talk about the problem space
We have some representation for this, or construct one when confronted with the problem (e.g. 2 integers for the water-jugs)
The problem space is the set of all valid problem states
The initial state (or initial context) is the problem state before any operators have been applied
We can generate all the possible states in a problem using some sequence of operations
A goal state is a desired problem state
a Plan is a sequence of operations that takes us
So, the problem space can be represented by a graph (often a tree) in which each node represents a problem state and each edge/arc represents an operator to move to another state
from the initial state to a goal state
9 10
Problem Space: Water Jugs
Aside: Physical vs. Graph Searches
• • •
Many issues are the same
1,0
our branching factor is 4 because there are 4 possible states emanating from each existing node
• e.g. guaranteed state transitions: you never know for sure that pouring water will work as you expect. Leads to multiple state problems, where you can’t predict what precise state you will be in after an action
© 2020 J.E. Anderson
© 2020 J.E. Anderson
11 © 2020 J.E. Anderson
12 © 2020 J.E. Anderson
Problem Space
Problem Space
The problem space is an abstract representation of the states associated with a particular problem
i.e. a tree such as the following is generated as we search – we’re NOT traversing an existing structure (nor could we in most cases!)
Search in these situations differs from that you have experienced in 2140: The problem space does not physically exist when a problem is presented to the system
This is a diagram of what the search space will ultimately look like as we uncover it
We must generate the portions of the problem space we explore, and store or maintain state so that we can search it as we generate it
Problem Space
State Space Problem Solving
The problem space is searched by the search process
state space problem solving involves creating complete problem states and searching for a solution within the space of all possible problem states (i.e. the problem space)
The dark lines indicate paths that have been examined, the dotted lines paths that have not been examined (parts of the graph that do not exist yet!)
Each of the states is a complete description of the problem (e.g. the level of water in 2 jugs) at a specific point in time (after some specific set of rules/operators has been applied)
13 © 2020 J.E. Anderson
14 © 2020 J.E. Anderson
15 © 2020 J.E. Anderson
16 © 2020 J.E. Anderson
There are many approaches to search in state- space problem solving – you know some of these already
2 3
Bad:
4
backtrack and try 5 if 4 isn’t a goal
17 © 2020 J.E. Anderson
Need mechanics for backtracking if a dead end is encountered 18
2
5
3 6
• all nodes must be stored – time and space O(bd)
Depth-First Search
Depth-First Search
Depth-first search involves examining the descendants of a node before examining the siblings of a node
“Good”:
• Uses a minimal amount of storage space : O(bd)
Apply the first possible rule to the initial state, and proceed downward from that using the first available rule – we only try alternatives if we cannot move down further1
where b=branching factor, d=depth • store path and the nodes on it
Breadth-First Search
Breadth-First Search
Breadth-first search involves examining all siblings of a node before examining the descendants of a node
Good
14
• No, it’s just physically the shortest # steps!
• No need to backtrack
• Good if there are few paths to a goal state
19 © 2020 J.E. Anderson
20 © 2020 J.E. Anderson
• “Good” if the tree is relatively uniform and there are several paths to a goal state (time O(bd) )
• • •
Can get lost in a deep subtree
Need to worry about infinite loops from cycles
• Does not get lost in deep subtrees
• will find shallowest solution 1st (is this the best solution?)
Bad
• If several paths lead to a goal state, time is wasted by examining them all
© 2020 J.E. Anderson
BFS Performance
Uninformed Searches
e.g. say branching factor of 10, 1000 nodes checked/second, 100 bytes of storage/node:
These are called uninformed searches because they require no knowledge whatsoever of the domain
depth nodes
time
memory
They’re weak methods – they work for anything we can define in a graph-like structure with transitions based on operations (water-jugs to path planning!)
0 1
2 111
4 11,111 6 10^6
8 10^8 10 10^10 12 10^12 14 10^14
1 millisec .1sec
11 sec 18 min 31 hrs 128 days 35 years 3500 yrs
100b 11k
1 meg 111 meg 11 gig
There are ways of adding very general knowledge for ordering choices in each of these without going into knowledge of the domain (e.g. which operators do we pick first?). These are similarly weak because they’re so general, there’s a ton of exceptions to them
time complexity is the same for basic bfs too…
21 © 2020 J.E. Anderson
we’re reasoning about? 22 © 2020 J.E. Anderson
Uninformed Resolution
Improving Uninformed Searches
unit preference strategy – if one of the clauses is a single item, that will always disappear and give us a shorter simpler result (since what we’re trying to get is nil, shorter clauses are closer to that)
There are also general ways of improving the general search strategies we have seen (BF/DF) to minimize their particular weaknesses – they don’t change the crappy worst-case complexity results though!
set-of-support strategy: always use a clause that is either ~h or derived from it (because that’s where our contradiction should be)
linear strategy – always use a clause from the previous resolution if you can. Follows a single line of reasoning, giving a more normal appearance to somebody watching the system work
• See p. 595-599
23 © 2020 J.E. Anderson
24 © 2020 J.E. Anderson
1 terabyte 111 ter 11,111 ter
e.g. in resolution refutation, what could we do to
choose what clauses to resolve, without caring what
Improving DFS
Improving DFS
The main problem with DFS is getting lost in a deeeeeeeeeeep subtree
What can we do in that case?
We can impose a depth limit to stop that: specify some number K to backtrack after going that deep, rather than continuing
If goal state can’t be found within the depth bound, depth bound must be increased and search restarted from the beginning
What does it mean when we chop the space like this?
This sounds incredibly wasteful
Our search is no longer complete – we don’t search everything, so we’re not guaranteed to find the answer
It actually ISN’T for many problems – think of how the problem space grows with the # of operators – retracing the first few levels is trivial compared to the work in adding a level
Here we know when we won’t find it: when it lies below our cutoff depth 25
We’re usually working with very BIG problems
26
Iterative Deepening Overhead
Making This Concrete
Say the depth of the tree is d, and each node has b branches coming off of it
Suppose we had a tree of depth 5 with a branching factor of 10:
The number of nodes in a full tree is: • 1+b+b2 +b3+…+b(d-1)+bd
Plugging these numbers in, we get:
And the repeated parts? Well, the deepest stuff is generated once, with one repeat for the level above, and one more (repeatedly) for each level above that. Total nodes are:
• as opposed to 111,111 for the full tree with no repeats
• (d+1)1+(d)b+(d-1)(b2)+ … +(2)(b(d-1)) + 1(bd)
• The bigger the size of the level, the fewer repeats
• so the repeated portions comprise only about 11% more nodes when b=10
© 2020 J.E. Anderson
© 2020 J.E. Anderson
27 © 2020 J.E. Anderson
Sothisisn’tsobad! Infact- 28 © 2020 J.E. Anderson
Depth First Iterative Deepening
• 6+50+400+3000+20000+100000 = 123,456
• even if b is only 2, still only 2x as long with repeats
Iterative Deepening
Iterative Broadening
time O(bd), space O(bd), guaranteed to find the optimal solution eventually
Breadth-first search can also be performed iteratively
• and no getting lost in subtrees
Instead of examining every node under the current node, only the first n nodes under each node we look at are examined – still using a BFS but only looking at and storing some of the nodes
• the bd space is because we’re storing the path to a node and the unexpanded nodes/unused operators for each node on the path
Iterative deepening is actually the preferred method when there is a large search space and the solution depth isn’t known
• assuming we’re stuck with an uninformed method
30 © 2020 J.E. Anderson
Iterative Broadening
Another Approach
Usually, the search begins with n=2
If a goal state is not found, the search is repeated with
Problem Reduction Problem Solving
n=3, 4, etc., continuing until a goal state is found
When you have a big problem, break it up and solve the pieces. Keep doing that and the pieces will eventually be trivial!
rarely used because advantages of iterative deepening aren’t usually there – rarer that eliminating some of the breadth, given we know nothing about each branch, is as useful as eliminating some of the depth
a Divide and Conquer technique
It’s possible to do this in a forward direction (break
29 © 2020 J.E. Anderson
31 © 2020 J.E. Anderson
Before we get to PRPS, let’s talk about why 32 backward reasoning is useful in general © 2020 J.E. Anderson
down our problem description)
But it is more natural do do this in a backward direction (start with our goal and break achieving it down into pieces)
Search Direction
Backward Search
Until now, we have assumed that search always proceeds in a forward direction, from the initial state towards the goal state
Backward search can be used if the description of the goal state is explicit (e.g. not just to find a solution to a crossword puzzle)
However, the number of choices may be significantly smaller if the search proceeds backwards, from the goal state towards the initial state
• there’s another restriction too, that’s coming up…
• not always, but often – and often quite dramatically
e.g. if goal is in(me,berlin). I can hypothesize I’m in berlin, and say ok, how did I get here?
Backward Search
Resolution Refutation
Backward search is often much more efficient than forward search because it constrains the search process to working with relevant operations (i.e. focuses the attention on the goal)
…can be a backward search, if we use the goal or a resolution from it each time (set of support strategy)
e.g. if I’m trying to get a robot to the doorway, I start visualizing there and say what would precisely get me here, rather than starting at the beginning and asking “what can I do?”
Recall if we attempt to generate a contradiction from a positive hypothesis, we have to go through the whole space to show that there isn’t one
everything I consider is directly relevant to being at the door, rather than looking at anything I could do at any point
with RR, every step we take can involve our goal if we so choose
33 © 2020 J.E. Anderson
34 © 2020 J.E. Anderson
35 © 2020 J.E. Anderson
Attempting to generate our H from initial facts would be forward reasoning, with much potential for doing useless deductions! 36
Backward search is often used when solving planning problems, putting together a sequence of actions that achieve a specific goal
The reason we use a negated hypothesis is to have a specific goal to generate a contradiction from, rather than having to look everywhere
© 2020 J.E. Anderson
Backward Search
Problem-Reduction Search
Not every problem can be tackled this way!
The water-jugs problem cannot be solved using
State-space search involves applying rules/operators to problem states to create new, complete problem states
backward search
because the operators aren’t reversible – e.g. if I empty a jug, I can’t guess how much water was in it before I emptied – I can’t reason about the previous state
Problem reduction problem solving involves breaking a problem down into smaller subproblems that can be solved individually
You can do backward search in a state-space manner, provided you can reverse the operators
However, backward search is most often carried
out with problem-reduction search
37 © 2020 J.E. Anderson
38 © 2020 J.E. Anderson
Problem-Reduction Search
Problem-Reduction Search
For example, problem solving in integral calculus frequently uses a problem reduction approach
Like state-space search, PR search can be easily represented by a graph
e.g. (x2 + 3x + sin(x))dx
This problem can be reduced to the
the nature of the graph is different though. Consider our calculus problem
subproblems
x2dx + 3xdx + sin(x)dx
((x^2)+3x+sin(x))dx
The solution to the problem is the sum of the solutions to the three subproblems
((x^2) dx (x^3)/3
(3x)dx 3(x^2)/2
(sin(x))dx -cos(x)
39 © 2020 J.E. Anderson
40 © 2020 J.E. Anderson
Problem-Reduction Search
Problem Reduction Search
What’s different about this graph compared to our usual state space graph?
State-space problem-solving involved an OR graph – we could take any path at any point, and we backtrack if we get to a dead end
• A path to a leaf isn’t our solution- in places we have to do ALL of the parts of the problem
In a Problem-reduction search is represented by and AND/OR graph
((x^2) dx (x3)/3
(3x)dx 3(x2)/2
(sin(x))dx -cos(x)
Not every node has an arc – that is, we still have alternatives we can explore
((x^2)+3x+sin(x))dx
This is an AND-OR graph rather than an OR graph
The arcs indicate subproblems that must all be solved
Problem-Reduction Problem Solving
Direction vs. Problem Solving Type
Run
go airport
Hop
get from airport
• See Polya, How to Solve It for many more The direction you operate in is independent of
run
winnipeg -> toronto Fly
State Space Search and Problem Reduction are two types of problem solving strategies
flight 101 taxi
the strategy
41 © 2020 J.E. Anderson
Each node is not necessarily a complete description of the problem anymore! 42
43 © 2020 J.E. Anderson
44 © 2020 J.E. Anderson
You can have backward state space search, forward problem reduction search
© 2020 J.E. Anderson
Other Techniques
Summary
Bidirectional search
It may be possible to start from the goal and from
Choice of forward/backward search
the initial state, and meet in the middle
These choices are independent
Still uninformed, but it helps us try to eliminate some of the huge bottom areas in a search tree!
The correct choice depends on the characteristics of the domain
Requires operators that can work backwards (that have inverses), just as regular backward search
All of these are weak techniques: they’re very broadly applicable, but not particularly powerful, because they don’t take the domain into account
This STILL only gets us so far – weak techniques are…weak!
Uninformed Search
Combinatorial Explosion
Depth-first search and breadth-first search are uninformed search strategies
e.g, Chess, after 40 moves
• 10120 ways that board state could have been
The strategy has no knowledge of how to solve problems efficiently
generated
Uninformed search is acceptable only if the problem space is relatively small
• The observable universe is estimated to contain on the order of 1080 atoms
This will obviously not be the case in most interesting problems!
e.g. Go
• an average game has 10800 possible outcomes
Problems for which the number of possibilities increases exponentially (or worse) suffer from a combinatorial explosion: the branching factor causes an enormous
And these are finite games with rigid rules
• How many outcomes in a 10 minute trip driving, or
number of potential states after a few levels 47 © 2020 J.E. Anderson
from attempting to cook breakfast?
• and more importantly, how many outcomes do you
45 © 2020 J.E. Anderson
46 © 2020 J.E. Anderson
Choice of state-space/problem reduction
expect from each of these? 48 © 2020 J.E. Anderson
Exponential Problems
Travelling Salesman Problem
It actually doesn’t even take much to get an exponential (or worse!) problem… e.g. the Traveling Salesman Problem
The problem space is proportional to N! 10! = 3,628,800
Given a list of cities and the distance between each pair of cities, find the shortest path that visits each city exactly once and then returns to the starting city
For even small values of N, the problem space is too large to be able to search it completely
Combinatorial Explosion
Informed Search
time for growth rates vs. problems size at 1 microsecond per operation n
How do we deal with these numbers?
10 20 30 40 50 60
• Literally: because most of the problems we deal with daily are of this kind of complexity!
n .00001s
n2 .0001s
n3 .001s
n5 .1s
.00002s .00003s .00004s .0004s .0009s .0016s .008s .027s .064s 3.2s 24.3s 1.7min 1.0s 17.9m 12.7days 58 6.5 3,855
.00005s .00006s .0025s .0036s
.125s .216s
5.2min 13.0min 35.7yrs 366 centuries 2×108 1.3×1013 centuries centuries
We use knowledge of the problem to not bother expanding parts of the search space
2n .001s 3n .059
• e.g. hopping to Toronto!
sec. min. years centuries
In general trying to decide whether to expand a node or not can be a significant problem itself
Here, The minimal tour is
a, b, d, c, a with a path length of 27
78.5 ?? ??
• GareyandJohnson,ComputersandIntractability
n! 3.6
sec. centuries
?? ??
But our experiences teach us situations to be wary of, or ignore, that work most of the time
49 © 2020 J.E. Anderson
50 © 2020 J.E. Anderson
51 © 2020 J.E. Anderson
52 © 2020 J.E. Anderson
Thinking Computationally
Deciding Based on Heuristics
The search process needs to identify the states that appear to be more plausible and examine these states first
If we’re using heuristics to exclude some states,what does that say about our search process?
We have pieces of knowledge that let us know – not perfectly, but MOST of the time – whether a state is worth pursuing or not
Like when using a depth bound in a DFS, it’s no longer complete: we don’t know that we’re searching everything!
The formal term for this:
we might not find the optimal path – but in most problems we don’t care about optimality – we care that our solution is good enough given the resources expended to find it and the consequences of using our solution
A heuristic is a technique (usually consisting of domain-specific knowledge) that identifies plausible from implausible problem states
There’s a word for this: Satisficing it’s what we do most of the time
Heuristic Search
Satisficing
Heuristic solutions are not guaranteed to be correct
Of course the decision that is optimal in the simplified model will seldom be optimal in the real world. The decision maker has a choice between optimal decisions for an imagined simplified world or decisions that are good enough, that satisfice, for a world approximating the complex real one more closely.
Sounds useless…
But what in life is guaranteed to be correct?
The only things that are guaranteed are concrete answers to simple problems – problems where we can search the entire space (or have a known algorithm!). Anything much more complex likely requires universe-lifetimes to guarantee
We use heuristic solutions to hard problems not because we prefer less to more but because we have no choice
So we live our lives without guarantees!
• H. Simon, The Sciences of the Artificial, p 35
© 2020 J.E. Anderson
53 © 2020 J.E. Anderson
54 © 2020 J.E. Anderson
55 © 2020 J.E. Anderson
56
Search and Intelligence
Travelling Salesman Problem
“The amount of intelligence in a search strategy is measured not by the amount of search actually performed, but by the amount that would have been necessary had an intelligent method not been used (i.e. by the amount of search avoided).”
In order to reduce the number of states in the problem space that must be examined, the search process requires some domain knowledge (a heuristic) What’s a good heuristic for the TSP?
• Newell and Simon
The nearest neighbour heuristic performs a local minimization at each step
Travelling Salesman Problem Heuristic
Distance/Cost Functions
This heuristic returns a path of a, c, d, b, a with a path length of 27
Heuristics are often described as functions h(n) that take a state and return a measure of its quality
Turns out the minimal tour has a path length of 27 – so this just happens to be optimal too (remember we aren’t guaranteed to do this well at all!)
e.g. distance to a goal – decreases as we get closer
This heuristic search would execute in time proportional to N2 instead of N!
e.g. Cost to get to goal – should decrease as we get closer
Remember we want to balance the cost of the heuristic against the work it saves us and the quality of the solution
e.g. be a general goodness measure/score – should get higher as we get closer to a goal (warm/cold)
i.e. if we care even less about quality, maybe
We will note in any given domain whether we are using an h where increasing values are better, or where decreasing values are better
there’s something even cheaper..?
59 © 2020 J.E. Anderson
60 © 2020 J.E. Anderson
57 © 2020 J.E. Anderson
58 © 2020 J.E. Anderson
• select the closest city that has not yet been visited
Accurate H
Hill-Climbing Search
How can we make heuristics more accurate?
e.g. distance to some city
walk and measure!
Any state can be evaluated for goodness
Not likely – the issue in heuristics is trying to find something that lets us get an estimate of the closeness to our goal with only a minimum of calculation
Suppose we plot that – we end up with a three dimensional landscape with height based on goodness
Satisficing again: we don’t just satisfice when applying heuristics, but also when calculating them
The goal will obviously be the highest point
Assuming we have such a measure, we can now
62 © 2020 J.E. Anderson
define some INFORMED searches
61 © 2020 J.E. Anderson
Hill Climbing Algorithm
From the point of view of a search tree
Example of a class of algorithms called Iterative Improvement Algorithms
Expand state’s children to determine the goodness of each successor state (i.e. call heuristic fn) – we have to generate (visit) these nodes to plug them into the heuristic function
In these algorithms, we always have a solution – it’s just not a very good one to begin with (we start off far from our goal)
(visited 5 states at this point!)
At each step we move closer – climbing the hill
We begin at the initial state (remember, dashed
Select the successor with the best h value (higher is good here) and continue, always taking the best of the successors as the next move up the hill (i.e. all children visited, one chosen to keep following)
& white = doesn’t exist yet):
To move from here, what do I have to do?
What’s the obvious problem with hill-climbing search (really
63 © 2020 J.E. Anderson
iterative improvement alg’s in general)? 64 © 2020 J.E. Anderson
Local Maxima / Mimima
Local Maxima / Minima
Its possible to get to a point in the search space where every successor state is worse, but we are not yet at the best point in the domain:
Curing local Maxima?
Beam Search
Option 1: Try elsewhere!
Expand (generate/visit) all successor nodes of the nodes at the current level
Random Restart Hill Climbing: Start again from somewhere else in the search space (the idea being if we start someplace else and don’t get to the same place, we’ve found a different (possibly better maximum)
Calculate h(N) for each of the successor nodes
Option 2: step downward occasionally to see if it gets you restarted up again quickly or not!
Create a list with the best m nodes (i.e. the m nodes with the best h(N) values) at the current level, and ignore the remaining nodes. we can increase m if there’s no solution found
e.g. Simulated Annealing – gradually cooling off over time (from metallurgy). We have some likelihood of choosing a downward move at each point (also considering how bad that move would be), and that likelihood decreases over time (the cooling)
Similar to iterative broadening, but we’re not being arbitrary, we’re actually working with what we think are the best!
You Are Here
We think this is our goal because it’s the best point within a step in any direction, but it’s not globally the best: we’re stuck on a Local Maximum and can’t get off
65 © 2020 J.E. Anderson
66 © 2020 J.E. Anderson
67 © 2020 J.E. Anderson
68 © 2020 J.E. Anderson
Minima occur if we’re talking about minimizing h(n) values rather than maximizing
Beam Search
Beam Search
For example assume >h is good, expand (generate/visit) children to get h value, then select the m=2 best nodes for processing
Continue selecting the m best nodes at each level and generating and evaluating their successors, until a goal state is generated
Generate the successors of these nodes and evaluate them using the heuristic function
NB: We MUST visit a node to get its heuristic value! 69 © 2020 J.E. Anderson
If the extra nodes are discarded, the search process may not find a goal state: restart with
> m value 70
Best-First Search
Best-First Search
Expand (generate/visit) all nodes under the current node
Generate (visit in the graph) the successors of the initial state (>h = good again here)
Calculate the h(N) value for each of the new nodes
Select the node with the best h(N) value in the entire tree (as opposed to best successor)
Select the most promising state and continue
This technique follows the most promising path until it becomes less promising than some other path
Doing this with just an h value is also called:
Greedy search
72 © 2020 J.E. Anderson
71 © 2020 J.E. Anderson
© 2020 J.E. Anderson
Best-First Search
Best-First Search
At each stage, select the most promising state in the entire tree and generate its successors, plugging each into the heuristic function
If there is a dead end, select the next most promising state in the entire tree
Best-First Search
Getting Better?
Stop when a goal node has been reached
There are lots of variations on best first search. For example, my heuristic is measuring goodness or closeness to the goal – I’m choosing the best node based on that, hoping to reduce my workload
© 2020 J.E. Anderson
© 2020 J.E. Anderson
75 © 2020 J.E. Anderson
76 © 2020 J.E. Anderson
73 74
Remember though, this is an estimate… It’s all based on how far I think I am from a goal
Thinking of an improvement, which of two nodes would you choose if there was a tie?
Thinking Further
A Two-Part Heuristic
When performing a best-first search, it would be nice if when we have a choice between two nodes, we chose the shallower node
f(n) = g(n) + h(n)
The shallowest is not necessarily the best, but it’s less work to get to the shallower one in the first place (a heuristic in itself!)
cost to get to node n
(this is an ACTUAL
hard value, not an estimate)
estimate of getting from here to the goal
(value DECREASES as we get closer to the goal)
Even better, we could keep track of the actual work (terrain, resources, whatever, instead of using shallowness) – note that this is not hard to do, and it’s exact – not a guess!
Applying best first search with this formula is called algorithm A – inherently better than heuristic alone, because we consider the (real!) cost so far too
This means that our overall heuristic could be made
up of two parts:
77 78
Admissible Heuristics
A* Search
We say an heuristic is admissible if it never overestimates the cost to a goal
Algorithm A (f(n)=g(n)+h(n)) + admissible H =
admissible heuristics are optimistic! They’ll tell you something is easier or cheaper than it really will be (at worst, exactly what it will be), but never that it’s harder or more expensive!
i.e. best first search counting cost and assuming an admissible heuristic
• Estimated car mileage is like this
this is a VERY special algorithm – this isn’t algorithm analysis so I won’t prove it for you formally but you can look the proof up if you are interested
straight-line distance to a city on a map is an admissible heuristic – may be 50 miles on a straight line, but it’s always longer to drive because the road is never perfectly straight
A* is complete (will find a solution if it exists)
and it will also find the OPTIMAL solution (that’s what makes it special) 80
© 2020 J.E. Anderson
© 2020 J.E. Anderson
79 © 2020 J.E. Anderson
© 2020 J.E. Anderson
Algorithm A*!
Sketch of Proof
Example: Travelling in Romania
As we go further down the search tree, a greater portion of the f(n)=g(n)+h(n) comes from g rather than h
From the book “AI: A Modern Approach”, by Russell & Norvig (typical 4th year text) which is in the library. This book also has a pretty approachable formal proof of A*’s optimality if you’re interested
Thus our estimates become more accurate as we go along – we rely on heuristic less as we go
if we’re doing best first search, we’re only getting BETTER as we go along this way
We see a map of Romania, which is not a flat country. Straight line distance between cities is our heuristic, and we want to plot routes from place to place
Provided we have an admissible heuristic
If it’s not admissible, we might suddenly get worse, which means we’d never be sure any of the decisions we made so far were right
82 © 2020 J.E. Anderson
Travelling in Romania
Greedy (best first) search
actual distances
h = straight-line-distance to Bucharest (direct from table by map!)
81 © 2020 J.E. Anderson
83 © 2020 J.E. Anderson
84 © 2020 J.E. Anderson
actual cost = all legs from start to current, e.g. 239 = 140+99 here
This is what also lets us know there are not better solutions on alternative paths, which is why we find the optimal solution with no backtracking (remember this is a best-first variant – the next choice to explore may not always be on the same branch, but that’s not backtracking!) 86
A* Search
A* Search
f =291+380 =671
It’s getting longer as we go because of our admissible heuristic – it’s always optimistic, so it’s being substituted for a (worse) accurate value as we include the actual cost for each step
The last step from Pitesti is not shown – but you can see Pitesti is the
choice at that level, and where to go from there
f=g+h (cost+straight-line-distance)
Look what happened: initial f value was 366, one step later (Sibiu) it was 393, then 413, then 415
Note we are considering the actual cost from the start to the current node
as our g, not just the latest leg! 85 © 2020 J.E. Anderson
© 2020 J.E. Anderson
Control Knowledge
Control Knowledge
In many applications, it is not possible to define a function that evaluates the goodness of each state
If (number_of_moves <= 10) Then try opening_moves If (number_of_moves > 10) Then try middle_moves
If (number_of_pieces < 10) Then try closing_moves
However, it may be possible to define symbolic knowledge that guide the search process
This type of knowledge is control knowledge – knowledge that helps us control a search. It's one type of meta-knowledge: knowledge about knowledge, in this case when types of moves are better than others
For example, consider a board game – we may not have a quantitative estimate of the distance to a winning position, but we could have something like:
Used in most large expert systems: often no obvious H, but we can identify situations where some knowledge is more useful than others 88
87 © 2020 J.E. Anderson
© 2020 J.E. Anderson
The final optimal cost to the goal is 418
END OF CLASS TEST MATERIAL
But happens any time our agent is not the only one affecting the environment
Search in 2-Player Games
Searching in 2-player Games
We take turns making moves, mine depends not only on what I did but what you might do
If this were a "normal" search problem, all max would have to do is find a sequence leading to a goal state
With >2 players what I have to consider is even more complicated
• like solving a maze
We’ll just talk about 2-player games here
We give our players names, for convenience: max
But Min’s choice-making ability leads to uncertainty
and min
• We don’t know what choices min will make, so it’s hard to decide what to do
A game consists of an initial state and operators, conditions for a goal (termination test – what it takes to win!), and some concept of the utility of a goal (binary win/lose, or points, $…)
• What DO we know about min?
© 2020 J.E. Anderson
90 © 2020 J.E. Anderson
91 © 2020 J.E. Anderson
92 © 2020 J.E. Anderson
Adversarial Search
Most often thought of in games
Realistically, we’re never the only ones affecting the environment: others move things, the wind blows things over,…
But we’ll start with the idea that someone else’s decisions are involved too
Searching in 2-player Games
Simple Example: TicTacToe
Min’s object is to win the game
• therefore, their goal is to make the best
From an initial state, Max has 9 possible moves
choices from their perspective
• i.e. MINimize Max’s likelihood of winning
Min responds with a move from each of these and so on (9! board states)
Given this, what is our (Max’s) goal?
To search and find a path to a winning
If we are considering all possible moves on both sides, the tree becomes too large to draw very quickly
terminal state NO MATTER WHAT min does
To consider the details of this search process, we’ll make up a trivial game
The Trivial Game
The Trivial Game
There are only two moves: Max moves, Min responds, and the game is over
A1
A3 A2
• Wow, fun game, let’s get Regis to host
Draw states where it’s Max’s turn with upward-pointing triangles
A11 A12
A13 A21
A23
A33
• Max’s Choices: A1-A3
A31
Min’s with downward-pointing triangles
A
A32
The depth of the entire search space is one move, consisting of two half-moves or two ply
22
Any terminal score results in some point
12
8 2
4
6
14
5 2
score for Max 95 © 2020 J.E. Anderson
Max want is some way to decide which move to take. 96 © 2020 J.E. Anderson
93 © 2020 J.E. Anderson
94 © 2020 J.E. Anderson
3
Any 2 player game is like this: the tree is just bigger. What we as
Minimax
The Trivial Game
An algorithm to determine the optimal strategy for Max and thus the best first move:
A1
A2
A3
• Generate the entire tree down to all terminal states, and find the utilities of each
• Apply the utilities of terminal states to determine
A11 A
A13 A
A
A
the utility of nodes (decisions) one level higher
21
23
A31
33
• How do we do this? We don’t know the moves min will chose?
12
A22
A32
• But by knowing Min’s motivations, we can assume the move Min will choose!
3
12
8 2
4
6
14
5
2
• i.e. we can assume min will move to maximize his or her chances of winning – and if they don’t, we should be doing even better! 97
For example, from Min’s moves, we know that
Minimax
The Trivial Game
i.e., Max MIGHT do better, if Min doesn’t play very well
A1
3
A3
but knowing Min’s motivations, Min will likely confine us to the worst outcome from out point of view (if Min doesn’t though, who cares – things are even better then!!)
A2
We can do this to all branches one level up from the bottom and get the worst Max could do from each…
A
3 12 8 2 4 6 14 5 2
© 2020 J.E. Anderson
98 © 2020 J.E. Anderson
99 © 2020 J.E. Anderson
What’s Max’s move???? 100 © 2020 J.E. Anderson
A11 A
A13
A21
A23
A31 A33 A32
the WORST max could do using A1 is 3
12
221
3
2
2
>2 ply?
Minimax
We picked the best move by choosing the best of the options that max had available.
If depth of the tree is M, and there are B legal moves at each point, time complexity is O(bM)
If we have >2 ply, we repeat in this fashion: assuming scores are from Max’s standpoint, we MINimize on each of Min’s turns, and MAXimize on each of Max’s.
• Bad, but that’s because it’s a hard problem!
We keep repeating this as many times as necessary until we hit the top of the tree
Alternatives?
Minimax maximizes utility based on the assumption Min will play perfectly to minimize it – again, if Min
We’re looking at the interesting stuff, so we’ll assume a depth bound
doesn’t, so what, we do even better!
•
As soon as we have one, we don’t know the utility… 102
Depth Bounded Minimax
Heuristics in Games
Instead of going to the bottom and using a termination test to decide if a state is a goal, we instead use a cutoff test to decide if we’ve gone far enough (easiest = constant function = depth limit)
Obviously highly domain specific • # pieces left
• Giveaways of known strategies • Aspects of board position
We don’t know the utility of the outcome anymore, so instead of a utility function we have a heuristic evaluation function of the states where we cut off
• Strength of pieces left •…
i.e. how likely is the state to lead us to our goal?
© 2020 J.E. Anderson
We’re relying heavily on the computability and decency of these heuristics – they will be computed very often!
101 © 2020 J.E. Anderson
© 2020 J.E. Anderson
103
104 © 2020 J.E. Anderson
Assumes we can search to the bottom, which we clearly can’t do in real time (or even at all, often!).
• what BAD thing does this process so far assume?
• •
Depth bound; precomputation (see Chinook)
Cutting off Search
Variable Cutoffs
We could use a fixed depth
Or time, with some variations on this algorithm Both these strict bounds are a problem
It would be nice to have something more sophisticated
• e.g. in chess, may be white’s move, and white may be ahead by a piece – sounds good
• i.e. don’t stop at a specific point, stop when it looks like we’ve gone far enough – i.e. a heuristic for stopping!
• but may lose a queen in the next turn – suddenly much poorer
• Quiescent state: unlikely to vary much
We expand non-quiescent states until quiescence is
• but only if we look one ply ahead
A problem no matter how far we look ahead –
reached
Horizon Problem
May consider only certain types of moves (captures, check, etc.)
Improving Minimax
Improving Minimax
suppose we’re playing chess: even a mediocre implementation of minimax will allow 1000 moves/second to be considered
We’d like to avoid looking at nodes that won’t help us
at around 150 seconds/move, we get to look at ~150,000 board positions
• Prune the search tree
A common technique in minimax search is
at ~35 branches/node, this means we have 3- 4 ply
alpha-beta pruning, which ends up giving the same results as standard minimax, but does not look at any nodes that couldn’t possibly influence the decision
Pretty bad – a decent human player can look at least 6-8 ply ahead
Consider our original “trivial game” game tree
© 2020 J.E. Anderson
105 © 2020 J.E. Anderson
106 © 2020 J.E. Anderson
107 © 2020 J.E. Anderson
108
We want to stop and evaluate at moves where further lookahead wouldn’t mean much
A11 A12
A13 A
21
atMOSTavalueof2
3 12 8 2
• IfwehaveabetterchoiceMattheparentofNor anywhere further up in the tree, N will never be chosen
3
Here we have utility 2
This means that A2 has
The Trivial Game
Alpha-Beta Pruning
A1
A2
Search starts with A1, then A11-13 (DFS), then A2 and A21
M
…
Alpha-Beta Pruning
Results
If we’re doing DFS, we are maintaining only one path at a time
The effectiveness depends a lot on the ordering in the tree
• Alpha is the best choice we have found so far for max
• It’s a good idea to examine descendents in their worst possible order if we can
• Beta is the best choice for min (the lowest value – worst for max)
If we can do this, we end up needing to examine O(b^(d/2)) nodes rather than O(b^(d))
• We update the values of alpha and beta as we go
our effective branching factor becomes root-b rather than b – pretty darned good heuristic!
• And we can prune any subtree worse than the current alpha or beta value
for chess, 6 rather than 35 branches
So what does this actually give us in practice?
© 2020 J.E. Anderson
we effectively double the number of nodes we can look at given the same processing power
But we already have a value better than that
General Principle:
N
So why bother with the rest of branch A2?
• Consider a node N
109 © 2020 J.E. Anderson
Where does the alpha-beta part come in?
110 © 2020 J.E. Anderson
111
112 © 2020 J.E. Anderson
• look at the third sub-branch in our example – worst last!
Summary
Summary
General-purpose techniques are referred to as “weak” techniques because they lack detailed domain knowledge
The current view of AI researchers is that an intelligent system requires a large amount of knowledge and a smaller amount of search
Weak techniques may be adequate for solving problems when the problem domain has been significantly simplified; however, these techniques will not be adequate when the simplifying assumptions are removed
Techniques that rely on extensive knowledge of a domain (“strong” techniques) must be used to solve hard problems
Summary
Summary
For example, in chess, there are only a few dozen possible moves; these moves can be defined in a knowledge base and an inference engine (search process) can then search for the best move
The amount of this specialized knowledge grows very quickly and soon additional (meta-) knowledge is required to locate the knowledge that is relevant to each board position
However, there are approximately 10120 states that must be considered so a chess program can not be based solely on a brute-force search of the problem space
Thus, adding additional knowledge may not reduce the amount of search that is required in a complex domain
Additional specialized knowledge that is specific to particular situations can be added (e.g. book openings)
We need to develop specialized mechanisms for representation and search in different types of problems, rather than just adding heuristics!
113 © 2020 J.E. Anderson
114 © 2020 J.E. Anderson
115 © 2020 J.E. Anderson
116 © 2020 J.E. Anderson
Unfortunately, adding more knowledge does not always solve the problem
AI Methodologies
There are many such specialized mechanisms – many for special areas
Still there are many more specialized mechanisms that are still useful in many domains
One of the best examples of these are production systems, more commonly known as rule-based systems
These focus on the limitations of FOL computationally, and attempt to build a more practical and extendible formalism
117 © 2020 J.E. Anderson