Mega-R2. Basic Search; Optimal Search Video Lecture - Artificial Intelligence

the following content is provided under
a Creative Commons license your support
will help MIT OpenCourseWare continue to
offer high quality educational resources
for free
to make a donation or view additional
materials from hundreds of MIT courses
visit MIT opencourseware at ocw.mit.edu
this week's problem is from the 2008
quiz 1 on search is motivated by the
search of evil overlord mark Vader who
is shopping for a new evil stronghold he
starts from his current stronghold which
is ask the depth first search star now
depth-first search star has the
following qualities it has a small
thermal exhaust pipe weakness it has the
quality of that's no moon
but it does not have a race of enslaved
minions or a secret escape route or
sharks with laser beams now when I
originally wrote this problem in 2008
there was another quality it was very
important there was a giant laser and it
did have that property as did dr. Evil's
moon base but that was removed to make
it easier to solve so we're going to
solve it without the without the giant
laser that we can just have the sharks
with laser beams
so mark Vader has gone to Akbar Emporium
of eat new evil strongholds which are
listed on the left and he's trying to
figure out the best way to get from his
current stronghold to his goal
stronghold the 6:03 fortress which has
the abnormal qualities of no small
thermal exhaust pipe weakness and it
still has that's no moon it has a race
of enslaved minions and it's a great
escape route and sharks with laser beams
so it's got everything you would want
and no weakness however he can only move
between fortresses that have exactly one
difference fortunately mark remembers
how to perform the start search
techniques he learned in 6.34 from his
mentor Emperor Patrick team so we've got
several fortresses here we've got the
depth first search star we've also got
shallow pool which has the
qualities basically of that's no moon
and none of the other qualities dole
gold or hair has got the exhaust pipe
weakness somehow despite being Sauron
stronghold it's not a moon and it has
those enslaved minions I guess the
origin slave
Moonraker here only has an exhaust pipe
weakness so it's not very good but James
Bond didn't need to deal with stuff
ziyal underwater palace has that's no
moon and a secret escape route zero
misses lunar core has an exhaust pipe
weakness at a race of enslaved minions
whalers of the moon ride has the exhaust
pipe weakness race of enslaved minions
and sharks with laser beams six ugly
fortress we've already been over
Atlantis has all qualities except for a
secret escape route Willy Wonka's
factory has some of everything it is
after all Willy Wonka's factory
highlight the race of enslaved minions
the Oompa Loompas and dr. Evil's moon
base is only missing that's no moon
because it is a moon because it's a moon
base so if you got all the references
that were used in making those
fortresses I'm sorry there's nothing I
can do for you both now mark being a
clever evil overlord realizes that he
can group produce a graph of the
exploration choices with edges joining
strongholds that differ by just one
feature so although this is a graph here
as Patrick often says and you get to
here again right now search is about
choice not just about maps so we're not
moving around anywhere in the real world
but we certainly are going to move
around this graph to pick between these
many stronghold choices how can we
decide where to travel well we're about
to find out
so we've got this lovely graph right
here and now we're going to get to do
depth first search on the graph now
there's a lot of ways to do search and
you've seen Patrick do it you may have
seen some people do it in recitation
and I'm gonna offer you guys a unique
opportunity to see me do search in one
of several ways or possibly more I have
the tried-and-true method you have the
queue or agenda or whatever you want to
call it you keep track of it in every
level you make damn sure that everything
you're doing is right it takes a long
time and you get the answer right or
there's one where you only work with the
goal tree and you draw it really fast
and you might make a mistake but it's
going to solve it more quickly so who
would rather see the reliable with
slower approach who would rather see the
faster but less reliable approach all
right Montecarlo people here rather than
Las Vegas you don't know that is you'll
learn it in algorithms class alright
then there's a third approach that I
probably won't show you unless is
overwhelming favor for it that is the
approach that is manically fast it will
solve depth-first search in no time at
all but is very likely to make mistakes
that is the first that I use when
solving depth-first search and I've used
it enough times that I don't make
mistakes that often but even I still do
so does anyone want to see that one okay
not that many people well it doesn't
take much time but I'm just afraid if I
show to you that you will ooh that's the
only way to do it so we just say that
for later if we have more time it
essentially the people interested in
volved just using your chalk or finger
to trace through the tree really fast
and figure out what it's doing
by drawing little tiny lines it is very
fast but it's not very accurate and you
have shown basically no work if you get
it wrong so shame on you okay well let's
do the somewhat faster way we don't draw
out the entire agenda and then people
who were the almost nobody who raised
their hand for that way can check it out
in tutorial the way that you do it using
the agenda so let's do it using the goal
treat so it's a bit faster that way so
we're going to start starting at s the
start node and going to G the goal node
that's a standard notation but make sure
that when you're taking the test you
check to make sure where the start node
is where the goal node is it's pretty
pretty much a an asshole move to have a
G know that
didn't go alone but sometimes there
won't be an S note that's a pretty good
clue that something else is the start
node now there's a few little white star
ideas that we have or Silver Star ideas
for search
one is lexicography what is lexicography
who cares well the most famous
lexicographer I know of is Samuel
Johnson who wrote a really famous
dictionary and the only reason we care
about it in this class is because you'll
always see the instructions break ties
in lexicographic order and then you
might be like wow that's really rather a
wordy word or a sesquipedalian word or
whatever really long word you want to
use to describe the word lexicographic
what the heck does it mean basically it
means alphabetical order like you would
do in a dictionary so for instance in
alphabetical order a comes from 4b so
you would go to a before B now even
beyond that point there's several ways
to do a lexicographic tie break and it's
not always consistent between algorithms
how you would do a lexicographic tie
rake in the most recent time that
Patrick was kind of randomly talking to
the staff he made it clear that the way
he would like us to do it and therefore
the way we would like you to do it is to
tie break based on the very latest nodes
at the end so you might say that's not
really lexicographic wouldn't si be come
before SGA in the dictionary and my
answer my answer to you is yes it would
yes yes it definitely would however that
is that that is apparently what we're
doing according to the last thing that
patrick said and we will keep you
updated if he decides to go back to
dictionary order so that's less graphic
lexicography you might be wondering what
the picture here is well this is our
friend the orb boris long has it been a
symbol in alchemy of infinity eternity
or maybe you know a sort of infinite
energy engine turning iron into gold but
today unfortunately
the or bars is endangered species
because no biting your own tail in
success before a lot of people mess up
from this it's an honest mistake
I mean we've gotten some emails from
staff members who couldn't solve one of
the problems because they forgot about
this so it's okay if you forget but try
your best to remember no biting your own
tail is the only smart thing our system
does so remember last week when we were
talking about rules and we were saying
that if the rule system is not a smart
creature it doesn't know that there's
different there's difference between or
sorry it doesn't know that not Polly is
dead should be the same as Polly is not
dead or something like that it's too
dumb to figure that out
well this system is also dumb but one
thing it knows is that Patrick really
hates if the same note appears twice
within the same path and it will destroy
that immediately before even adding it
to the queue it's gone it's not
considered it's out of there
so very important sad Ouroboros nobody
in your hotel all right so now I've
gotten to that let's actually solve the
problem with some depth-first search
how will we do that well we're not going
to use the queue at popular demand we're
going to use a goal tree so we'll start
at node s what are our choices at node s
well I'm going to force you guys to help
so it won't be quite as fast but it'll
be fun so what are twisted note s you
not quite and this is something I like
about this problem you got most of them
do you see that there might be another
choice
everyone yeah see this is a big problem
that has happened on a few different
quiz problems where there's a tree that
you could where there's a sort of a grid
that looks like a tree or graph that
looks like a tree where people aren't as
willing to go up as they are to go down
you can see it on some of the other
paths previous problems to make sure
that you check the connectivity and also
note that unless otherwise specified and
I don't think we've really done this
much the little connecting edges in our
graphs are bi-directional you'll see a
big arrow and probably instructions
written at least eight font sizes is
higher than all the rest of them and
bold if if we're going to do something
different for this quiz it happens that
they do it sometimes well as I say a
mega recitation we never do this and
then on the quizzes they do it but it
will be in giant bold letters which also
leads me to another Silver Star idea
that I forgot to tell you guys last week
so I hope people didn't ditch out I mean
like all marks boring we won't come next
week and then miss this one because it
just came to my mind that is read the
instructions there's a very important
thing for the quizzes and I'm Patrick
will in a later lecture tell you guys
ask why five times and he'll explain why
that's a gold star idea my parallel to
this is read the instructions five times
maybe not five maybe three or four but
at least three read the instructions
read them again then read them a third
time only paying attention to whatever
is bold and eight sizes larger than all
the other ones because there's going to
be something there that's that size and
it's going to be one thing that everyone
misses so make sure you're not everyone
and you read the instructions a lot of
times but anyway so yeah we've got it
right s goes to a B and C okay we're
looking at a B and C as possibilities
everyone let help me make the
lexicographic tiebreak where do we go
hey that's right all right actually you
know I'll call on you guys for calling
you guys four other ones the depth per
surface is pretty simple we can have
everyone
together hey everyone a only leads -
that's right
why doesn't lead to ass as well no
biting your own tail everyone's right
good job everyone
all right excellent leads to a s leads
to these three you go to a go to D up
dead-end backtrack okay when we
backtrack we add back track up to a
there's no other children we backtrack
up to s where we go now B it's the next
one alphabetically all right B can't go
to s so it only goes to yes one more at
H we can go to Fri that's right you guys
get at this that first search is easy
all right
so but we choose F that's right one more
F we can go to E and J that's right
we'll choose E when we're even go to we
uh we can go to see it's not on this
particular path people are correct when
they say C when we go to C we can go to
nowhere we're dead backtrack we
backtrack we kept away three we go to F
now I forgot to tell you guys but this
is an important note someone's going to
get this wrong it's going to be one of
you look around you all through the room
at least one of you is going to do this
so now I'm going to tell you not to do
this and then hopefully that will still
be true but for fewer people when I went
to D and then I backtracked and I went
to ask how many times did I backtrack
once I backtracked once this would have
been more obvious if we were doing the
really slow boring agenda way or queue
way because when we got to s ad and we
expanded it and there was nothing left
we throw it off the top of the queue and
go to the next thing on the queue and it
turns out the next thing on the queue is
SB that step was only taken once it will
since we're using the gold tree which is
faster it looked like we did too but we
didn't and if you use the queue you'll
see that because it'll go s and then we
expend that sa SB SC okay we spread sa
sa d SB SC
we spend a CD but instead SBS c1
backtrack we're back at SB so so far
we've done two not four see I mean it's
pretty intuitive to say that you did -
there it turns out you didn't because of
the algorithm the algorithm that's
backing what lets us do this gold tree
search so make a try to make sure you're
not the one who says - when we and I on
the other hand will try to make sure
that we don't take off too many points
if you do question it is always going to
be considered one step it's possible to
backstrap two times in a row like if
asked if B didn't go to anything instead
of going to H then we might backtrack
twice before we got to SC generally any
time you draw a Swizzle if you're like
me and you draw Swizzle i suggested
swizzles they're very nice little things
but if anytime you draw a swizzle on
your graph you've backtracked
once you could even write bt next to the
swizzle and go back and count those or
even just count the swizzles at the end
you've got it you got the answer because
they often ask how many times have you
backtrack all right so good questions
everyone so anyway we backtrack from see
nothing we go back we're at F so we were
s bhf we go to J it's the only choice at
J we can only go to and at I we can only
go to and we win it's not an optimal
search so as soon as we see anything
with the G on the queue boom winner all
right and we're done we did it
that wasn't too bad for those of you who
are vaguely interested in seeing how I
would do it um the really super fast way
it goes something like this
all right ABC a con first only D
backtrack all right becomes first H F
comes first
e see nothing backtrack we came that way
AJ I G so that's the really fast way to
do depth research don't do that kids we
don't like
well maybe you can if you get it right
we're not going to take off we're not
going to take off points usually
generally when we say draw the goal tree
below it's to assign partial credit
however we are pretty strict about that
if anything is wrong except for maybe
like okay you write everything exactly
right you know forget G at the end if
anything that's not completely
understandable is wrong you will
probably lose all of the points and it
will be a lot of points if you don't
draw the goal tree so man I love the
size drawing the goal tree is a good
idea all right so now let's do a
breadth-first search before we do the
breadth-first search on this on this
tree I will tell you guys that there is
a also a faster way to the breadth-first
search which is less risky and it really
depends on how nice they are about what
they ask for in this case the
breadth-first search question asked what
path does mark find using breadth-first
search rather than saying what knows is
he expanding order or anything like that
that is important if that question is
asked you there is a trick that will let
you solve it very very quickly in fact
faster than depth-first search you can
solve it by inspection in about 30
seconds does anyone know what the answer
is what path did you find that's correct
so the answer is on this craft answer is
s be hig that's answer you would have
your five points did people see that and
it doesn't always work so we're going to
actually solve it but does everyone see
that sometimes you can get away with not
doing it because breadth first search is
guaranteed to give you the path as we
heard correctly with the least number of
jumps and if there are more than one
that tie with the least number of jumps
you can just lexicographically figure it
out in this case with actual dictionary
order but SP hid is the only one let's
do an actual breadth-first search though
so we can feel better about ourselves
okay so you've got s and s goes to as we
saw before ABC maybe that doesn't have
to go quite so high
alright as we saw the 4 s goes to ABC
and you already told me that a goes to B
and you told me one big O's to H but
what does C go to e that's right how you
can see we're expanding it level by a
level left to right all right
so s ad where does s ad go to s ad goes
to nowhere it's dead SPH now wait you
might say wait a minute Patrick said
that we're using this weird dictionary
order where E is it the I think comes
before H
that's our type rank order but it turns
out that best for such endeavors search
don't sort in any way the is very
important they don't sort the paths that
are currently on the queue so you're
going to just go left to right left to
right left to right and only at each
node are you're going to break ties
unless you graphic letter all right so
SPH h goes to as we already know f and i
e we think we already know but we don't
quite because this is e coming from the
other direction
a this time goes to F that's right well
actually you guys do already know it all
right
great now we come over here H F goes to
as we already know enj I goes to as we
don't already know H I goes to G and J
that's right and as it turns out by an
implementation detail we're done
question does it not expend Evan all now
this is an implementation detail it's
perfectly sane and reasonable to make
adapt at the best first search that
likes to finish its entire level that
it's working on however in our
implementation and we would have seen
this if we had been pedantic and drawn
out the entire queue it's another reason
why I drawing out the entire queue is as
I said more reliable
um in our implementation since it's not
an optimal search as moment anywhere on
the queue you add something with a G
and you finish and because of the fact
that the way breadth-first search does
is mojo is that it adds everything to
the end of the queue that's how it does
it level by level right it adds it to
the end of the queue instead of the
front well then you at you'll add it to
the end of the queue and then you will
have it on the queue with the G so you
won't have to do as CEF another question
ah that's a good question so the
question was so for the breadth-first
search there was no backtracking g-d
died why didn't we backtrack or
something the answer to that one is but
for breadth-first search backtracking
doesn't really it isn't really a thing
like it is for depth-first search
why well because breadth-first search
we're sending our infinite monkeys down
every path in depth research we're
really focused in now we're like we want
to get there we want to get there over
this way this way this way this way and
we might have gone the wrong way and
then we hit a dead end we're like oh
crap and we go backwards but for for
breadth-first search we really are like
an evil overlord and you know we're like
bach vader saying like stormtroopers go
every direction and then from there go
every other direction and so even though
yes when we got to D some of the
stormtroopers hit a dead end and
probably like it was reflective and they
shot it and hid themselves or something
like that
meanwhile the stormtroopers reset to B
and C are still fine so we don't need to
backtrack yeah there are other troops
going down the tree in every direction
whereas in the depth first search we
only sent we're like there are
definitely no droids on this escape pod
send everyone this straight direction
and we only sent them to a and B and
then so we had to backtrack because we
had a dead end does that make sense
another question
so the plus it is in this breadth-first
search did last if the graphical order
ever come into play the answer is yes in
a very subtle and sneaky way which is i
wrote e before j f before I and G before
J if I was not using lexicographical
order it might have been reasonable to
write for instance at when I was
expending I to write J before G because
J was higher up on the tree or something
like that but the only way it came into
play is that I wrote them left to right
in alphabetic order every time and I
wrote ABC another question and with
others is it I forget that's correct
the question is f is listed twice so if
we hadn't reached the goal node let's
say that down there after I is Z and
after Z is the goal node then will be a
visited F again the answer is yes and I
said this is the approach that throws
your troops to every possible way so
there's stormtroopers going from E to F
and their story was going for H to F and
they're going everywhere now there is a
way to cut down on this you could do
breadth-first search with an extended
list if you did do breadth-first search
with an extended list that would be sort
of equivalent to after as soon as you
expand one node you know soon as storm
you send storm troopers out of AI to
look at G and J one of them stays at AI
and if any other structures come to I
and they're like oh we want to see what
path I is like no no no we've already
sent troops path I we've got this go
back home you're it's okay there are no
rebels here but it might be Han Solo
dressed up as a stormtrooper as we'll
see in the next problem where our Senate
list screws us over
but for this problem do you see what I
mean with an extended list we could
avoid this because the extended list
basically says once I've expanded and
searched past here don't do it again but
if you don't have one yeah you'll do F
twice in fact didn't we do something
twice here oh it turns out we didn't but
we easily could have we almost did eat
twice we almost did we almost did F
twice it turns out we didn't but we
could have another question
Jason stop that's a very good question
that provokes a minor change the
question is when you expend s bhi is SP
h IG added before SP hij because of
lexicographic ordering or they both add
at the same time the answer is
simultaneous when you do the expansion
you instantly receive a say a list baby
or whatever data structure you like
containing all of the children and they
all go get appended to the q at once in
order so you will receive all of them
like I suppose you can create some kind
of search problem where you have like an
adversary node like a Wumpus or you're
hunting a Wampus interview you don't
want to add the exact Wampus to your
search tree or you lose you only want to
add the one next to the Wumpus
I don't know I'm making this up and
unfortunately you would have to add all
that you have to add all the children at
once you our current algorithm does not
add one at a time
alright so we've done a breadth-first
search great now we're going to do some
optimal search that is going to require
me to draw a slightly different graph I
will draw it on what is left of the
bottom here and then we'll solve it on
what is left at the bottom here so all
right mark has his new stronghold and he
wants to invade parallel universes now
he's going to he's programmed his evil
supercomputer to find the shortest path
of jumps from his starting universe to
the goal universe gee he is also it
takes a certain amount of energy to move
from universe to universe based on the
differing factors between those
universes but maybe in one universe a
butterfly didn't flap its wings in China
whereas in the other universe there's a
sentient Reptoids ruled the earth and so
he is a Martian supercomputers tried to
create a heuristic value that determines
how different the unit
versus our two guess sort of how much
energy is going to take to get from his
start universe s to his goal universe G
given that he's out of he's currently
his armies are at a particular universe
in other words okay
it's not a Euclidean search but damn it
we're going to have a heuristic distance
to the goal and we're going to have a
graph with distances so let's see what
it looks like all right and down here is
G so this otherwise this unassuming
heart shape hides an evil invasion force
so let's see the distance here is 100
the distance here is 3/4 the distance
here is 4 distance here is 50/50 14 4 16
16 oh sorry these are connected 30 and
10 the heuristic values are 0 at the
start node 50 at B 60 and a 55 at C
fifty a d-- 56 at E 50 at F
zero at G because it's the goal node 39
at H I'll draw the little H smaller and
zero at I well after all I goes right to
G it can be zero it'll be great okay so
now this time mark is trying to conserve
the energy of his parallel universe
jumper that understandably takes a lot
of energy so he needs to find he needs
to program in the shortest number of
universe jumps that will get him to the
goal he he's not interest and he doesn't
mean the least number of Junction means
the least amount of energy on these
edges he's not interested in conquering
and getting to this new world and not
having enough energy left to blast the
crap out of it so we need to find the
shortest path so first mark programs is
simple branch-and-bound search he adds
dated an extended list to his branch and
bound just to make it a little bit
faster as usual he breaks ties of equal
length in lexicographic order so let's
list the nodes that mark's computer adds
to the extended list in order distances
are shown next to the edges ignore the
number in parentheses for now they are
heuristics and we're not using them so
that brings me to another point that I'd
like to drive home before we go for the
home stretch and solve these problems
what the heck is the difference between
branch and bound at a star okay I like
to liken it to the following I probably
should have
I'll make this is Silver Star idea okay
the Silver Star I get is pizza it
doesn't really look like pizza but
that's it's over started yet
branching bound is a cheese pizza it's
simple if you order it for a large group
event of college students that will eat
it and things will be okay now a star
search is some kind of meat lovers of
supreme pizza maybe a meat lovers Pizza
it's got all these extra toppings a lot
of people are really going to like it it
might be better but then you've got a
vegetarian and everything's screwed up
so basically Branson a star is just
branch-and-bound with some extra
toppings added on in this case one of
the toppings is an extended list
extended list which will see keeps track
of where we where we passed through and
already expand it out and it never goes
back the other topping that we were
going to add is a heuristic heuristic
tells us about how far we think we have
left until we're at the end so we don't
go through really short paths that go
completely in the wrong direction all
right between the two of those we get
our supreme pizza but sometimes as we'll
see they bet they sort of mess each
other up so you know one of the topics
this doesn't go well with the other one
maybe a lot someone doesn't like
Hawaiian they think that the the ham
doesn't go well with the pineapple
anyway so let's do a branching bound
that just has an extended list maybe
we've got some green peppers on this
pizza this is going to be safe all right
so we're going to list the note C as an
extended list and the way we're going to
do that is well you guys said you like
gold tree more than Q so let's do it
with a goal tree so we've got s and as
we already know s goes well as the only
path our current length it s is zero
that's the lowest of all of our lengths
on the tree because it's the only length
so we go to a B and C okay so what is
everyone um it may be hard to see so the
length of Si is 100 the length of SB is
oh you're right it's a different tree I
was doing a B and C from the other tree
Thank You friends for correcting my
foolishness the length of SB is 3 it is
a different tree I was trying to save
work that wound up creating more because
someone's going to be confused by this
so the length of a b e and f are 103 14
and 14 which one do we choose lesson
graphically it's a we choose that one
right F is going to be 14 that's a 1
sorry we owe is 4 I wrote this problem I
should know it you're right f is for my
apologies once more after I get all
right I'm going to stand over here from
now on when I write over there
okay um so which one of these are we
going to choose even with the four we're
going to choose B that's right
lexographic be damned it's only for tie
rigs we want the shortest path our
special thing with branching banners we
take the currently shortest path
whatever it is great so we spent beat
fortunately and I'm pretty sure I've got
this correct this time oh wait I've got
an even better idea
I'll just take this little hand sheet
with me and then I don't have to look at
that at all ok so once we spend B B goes
to D our path length from B to D is 4 so
well do we right next to the little G
here 7 that's right we add them all
together I'm going to ask you guys again
the next time we do this with the
heuristics which is going to be the next
part of the problem and someone's going
to give you the wrong answer next time
so stay tuned for that all right so
we've got SPD we've got all these where
do we go next
F that's right because currently 4 is
the shortest because you guys corrected
me correctly so SF 4 is the shortest F
only goes to H and what do we right next
to the h20 that's right
16 plus 420 all right where's our
current shortage it's the D SPD all
right so s BDD only goes to I and we've
got a 57 oh I want to get wait a minute
57 I think wait a minute I want to get
this problem right so we better actually
write the extended list better at we
because that's the only thing they're
asking us for so first we extend it s
then we extended B then we extend it F
then we extended D all right so far so
good and I have the answer key so I know
we're doing it right okay what are we
doing next
that's right so extend e e goes to H and
when it goes to a so we've got a length
of 30 all right who's our winner now
which H s fh that's right s fh is length
20 oh yeah of course i should write an e
in here i always forget to do that SF h
is length 20 so we extend H and I'm
going to write it here preemptively all
right when we extend H over here eighths
only goes to I with length 50 great
what's the next shortest the next
shortest is the other H however will we
expand it you guessed that because I
asked that question in that way you knew
the answer was no why don't we expand it
it's already on the extended list that's
right so since it's already on the
expanded standard list this one dies a
horrible death I like writing an X
through it instead of writing a Swizzle
at the bottom you can do whatever you
want all right it's gone it's not a
choice what's the next best one s fh i
that's right
that goes to G and the length is 60 and
we've extended I all right
so question is are we done the people
who say no I like you you're smart you
realize that just because the G is on
there that we can't end how are the
people who said yes you're either
oblivious or really really smart and I'm
going to choose to assume you're all
really really smart because the really
really smart people said okay yes we're
not quite done just because we added a G
we still have to check to make sure
there are no going to shorter paths but
look the only one with the shorter path
is i which is already on the extended
list so actually we are done double
check we've got it so these are the
paths we extended in order and our final
path is everyone that's right
sf hig I claim that is the correct path
however mark is frustrated by
branch-and-bound speed I don't know I
wasn't that frustrated it seemed pretty
good but mark is frustrated by Brenton
Brown speed so he pre-programs his
computer to use a star mark counts the
number of subspace anomaly is between
each universe and the goal and uses this
count as the heuristic for a star these
numbers are in parentheses hopefully you
can read them yes oh we've got a
question right here ah that's a very
good question and the answer is very
simple answer you guys tricked me no but
I should have been able to figure out it
does go to C and D the correct tree
which you wouldn't we wouldn't have lost
punch for having the ink right trainer
we did get the correct answer yes the
reason why is that same reason that very
first time I asked someone something he
didn't remember the C it's easy to
forget to go up the tree it does
actually have a CD however they are
horrendous paths they are 100 and 100 on
their on their path length and so it
doesn't matter but you were correct
official answer we add up those wrong
good question where the question is
would the deed get added to the children
after all it's already an extended list
the answer is we search for and remove
and kill all of the attempts to extend
something that's already on the expanded
list at the time we try to expand it the
time we try to expand it is only when
it's on the front of the queue because
it's the currently shortest path so that
means they get added it's just that when
it comes time to expand it it will get
crossed off no matter what turns out it
escaped execution because of the fact
that we never expanded it so it should
go to e as well is the question the
answer is yes H to go to e as well a lot
slip past me this time it should go to e
as well with a length of 36 and it dies
there this one will actually be checked
so it actually does make a difference if
we ask how many times was a node
executed due to not going on the Xterra
t being on the extended list very good
very good notice it should be on there
we'll get it right next time all right
everyone so I'm working together with
you I made the mistake too easy one to
make it can it can mess you up it didn't
this time we're going to get it right
question so the question is do exist do
actually extend G you should you should
we even put G in the extended list the
answer is the answer to that question
is it is a matter of taste and in the
questions where we in my opinion rather
foolishly as how many nodes were
extended rather than asking you to write
them out we generally accept the answer
where you didn't extend or where you did
extend G it's an implementation detail
you can either have a fail-safe that as
soon as it sees G at the beginning of
the list says we're out we're not going
to extend we're done we win or failsafe
that when you're about to extend
something and you do go into the
extension process and it sees that ends
in G that it wins so it is a matter of
taste if you kind of like to watch your
your little guy doing the search win and
have an S energy you can put it on if
you don't you cannot put it on we won't
take off points for whether or not it
has a G at the end because clearly if
you did all the other crazy stuff
correct well you could have written the
energy if you wanted to I think unless
like there's someone who missed solves
the problem right at the end is like oh
who cares about G oh no it's stuck into
data and we lose but that would be
probably pretty rare all right
so let's solve the the a star so I'm not
going to make the same mistake place we
go from s to a BEF and s by the way had
a value of zero all right what is the
value at a well I think it's 160 the
question is how do we calculate this
well it's the path that we traveled so
far plus the heuristic value at the
final node okay this is why something's
going to give me the wrong answer at B D
but let's see so we have 160 here okay
so SB we've got a what is the trysting
value here we've got three for the path
and 50 for the new heuristic so it's 53
i s II
what have we got here we've got 14 for
the path 56 for the heuristic so it's 70
I s
we've got four for the path 50 for the
heuristic 54 okay
who's our winner it's B again barely but
it is the winner extended list up here
SB RB as we saw goes only to D what is
the what is the value like right
here okay I'm happy I heard all the
things that I expected to hear
I heard the correct answer which is 50
57 I also heard someone say 107 so why
is it 57 not 107 someone does it this
way every time do not add up all the
heuristics along the way I'll try to
explain to you why you'd never want to
do that the heuristic value at any given
node says given that I'm here how much
work do I think I have left to get to
the end all right it's sort of like
let's guess the last few nodes in the
path that we haven't done out yet so you
can see why it would be bad to add that
every add that for every node in your
list because then you're at your double
counting all the last nodes so add the
path so far to the very final heuristic
that's 3 plus 4 plus 50 that's with D is
57 so our current winner then is 54 with
F just same as last time f goes to H and
what's our total value at H 20 plus
that's at 3959 so who wins now D with 57
but ah we extended F yes look all right
so D with 57 all right
so D was not one of the ones that I
tricked myself with D only goes to I
what's our value at I I think our value
is 57 because I has a heuristic of zero
yes I has a heuristic of zero our value
at I is 57 okay and I extended D who's
the winner now I okay so I is the winner
with I as a winner we extend on I goes
to C D
haha good call whoever back there
figured out my secret error before C D
and G C H and G oh you're right we
already went to D aha
CH and G you're correct everyone see
that see H and G absolutely right I goes
to see H and G so the path to see H and
G is a hard path we've got to see we got
when we have 57 plus 50 is 127 oh by the
way see G and H we've got to do it
unless you graphic order so 127 - C - G
we have 67 + 2 H we have 87 okay so who
wins now H H was 59 that's right
H 1 59 and as we already know because it
was the winner last time H with 59 goes
to I which has I believe 50 well it
still gets added remember we're only
going to kill it when it gets extended
so who's the shortest so you were a step
ahead whoever asked me the question
who's the shortest H also goes to e
absolutely right all right H also goes
to e I was getting ahead of myself here
H also goes to eat with the length of
extra 16 so we've got a 20 plus 16 is 36
plus 56 is 92 all right that's good so
who's the shortest I am shortest to
extend it no it's on the extended list
all right who's the shortest now it's
hard to read but the shortest is this 67
on the G so we're done we win our path
is SB d IG yay for a star gets the right
answer right no unfortunately not so
what happened here why did we not get
right answer being as specific as
possible what are people saying about
heuristics all right people are saying
the heuristic must be consistent that is
both correct and specific so I applaud
you too easy to say the heuristic was
unmissable it actually was completely
admissible everywhere so that leads us
into our very last point for the day
what the hell are these heuristics
consistency and miscibility things and
why do I care well the reason why you
care is many-fold one of which is that
it's almost guaranteed to be on the quiz
but what are they
admissibility is a check at every point
to make sure your careerist stick at
that point which is supposed to be an
estimate of how much work you have left
to do is always an underestimate or an
accurate estimate it can never be an
overestimate why not well as Patrick
showed you with his mostly correct
example in lecture if it's an
overestimate it's never going to expend
that note because it's going to think
you know if you write 1 million as a
heuristic it's going to think it needs
to do 1 million after it's done going
that way it's not going to want to go
that way all right so it's always got to
be an under estimate or an equal
estimate but let's say that you as at
the quiz and you forget mark told me
this you didn't bring any notes you're
just having a brain freeze oh no is it
to be an overestimate or underestimate I
can't remember which one how can I
figure it out how can I figure it out I
propose you the following calm soothing
mantra / Sutra that will help protect
you think to yourself of the following
question does we know that a star
sometimes messes up with the heuristic
does branch-and-bound always get it
right yes
what heuristic values does
branch-and-bound add everywhere zero
right it has no here's to get
essentially add zero zero an
overestimate or an underestimate an
underestimate therefore since Princeton
bailed always works the one you're
looking for is under estimate I know
from when I was taking the class I
always had a moment where I had to spend
like two minutes convincing myself ok
I'm going for under estimate not over
estimate this will help it will take
fewer than two minutes to do that so
what is consistency consistency is a
little bit stronger of a claim when you
claim that a graph is consistent what
you're saying is between any two nodes
or to do it more simply between any two
adjacent nodes the distance between the
heuristics is less than the distance
between the nodes in other words it's
sort of like admissibility is this sort
of like consistency between every node
and G where's consistency is consistency
between every node and every other node
all right insistence Ilya is a stronger
claim any graph that's consistent is
always admissible any graph that is
inadmissible is always inconsistent
that's the contrapositive question equal
to is still okay equal to is always okay
that's great it's a perfect estimate but
never greater now if a graph is
inconsistent will you lose will you lose
why is it called admissible then if you
can if it's sometimes not admissible the
answer is why do we why do we lose the
answer is the extended list and you see
that here if a graph is admissible you
will always get the right answer and
you'll always get the right answer
unless you use an extended list because
you're checking for every node to the
goal node and you're sure that your
estimates are right but if estimates
within nodes aren't correct you might go
through them out of order and that
violates your assumption that you made
when you decide to use the extended list
that you would always go through the
sort of the sub graphs in order this
graph is very expertly crafted to do
that to you because I might as well be
sort of a bottleneck goal node and I has
an inconsistency there's a few other
inconsistencies in this graph but they
don't do anything to you in fact even in
miscibility sometimes don't mess you up
so you can't just say blindly it's
admissible so it will never work it
might work it turns out the only
inconsistency that matters here is not
inconsistency between say s and F that
doesn't turn out to matter it's the
inconsistency between some of these
nodes including I and H specifically so
have a good weekend comment on Monday
and Tuesday the tutorial asked about the
queue method or other methods ask about
anything that's niggling in your brain
but hopefully you guys have got this
you're going to do fine