Follow US:

Practice English Speaking&Listening with: Lecture - 6 Problem Reduction Search: AND/OR Graphs

Difficulty: 0

Okay. In the last couple of lectures, we were discussing state space search, and if you

remember, in the initial introduction that I gave on search, we said that there are 3

different paradigms for problem solving, using search, broadly.

One was state space search, of which there are few topics which are left; we will cover


up later. The second topic is problem reduction search, and under problem reduction search,


will look at 2 kinds of graph search, namely, and/or graphs and game trees. And/or graphs


a kind of structure which we will study, and it has several different applications, though

people do not always refer to them as and/or graph search. But the underlying philosophy


the same. And then, we will look at game trees, which is the backbone of game playing programs

and for programs which optimize in the presence of an adversary. So, game are situations where

you have adversaries, and there is some criterion that you may have to optimize, and in the

presence of the adversary, you have to do that optimization.

So, problem reduction search can be broadly defined as planning how best to solve a problem

that can be recursively decomposed into sub-problems in multiple ways. So, we can solve the

same problem by decomposition. There are more than one decompositions of the same problem,


we have to decide which is the best way to decompose the problem, so that the total solution-

cost quality of solution or the effort of searching- is minimized. To start with, let


consider the matrix multiplication problem, where you are given a set of matrices A1 till


and we have to find out the product of them. So, we have to find out A1, A2 to An, right?

Now, we can do it in several ways. For example, we can first multiply A1, A2; with that

product, we can multiply A3, right; with that product, we can multiply A4, this is one way


doing. Another way could be, that we first multiply A1, A2, then we multiply A3, A4,


then we multiply A5, A6, then A7, A8, in this way. And then, we multiply these 2, multiply


product of A1, A2, with the product of A3, A4, and the product of these 2; and then,


in the final step, we multiply the product of this, right? So, it means, that if you

look at

it bottom up, then here are our matrices A1, and so on. And one way of multiplying is by

taking these 2, and these 2, and these 2, right? So, this, if we look at it from the


direction; so, the problem of multiplying it A1, A2, A3, A4, can be thought of, as multiplying

A1, A2 and then A3, A4, and then this, right? An alternative way of doing this, would be


have, right. And A1, A2, A3 can be done with the A1, A2, A2. This is another decomposition,


So, this way is one decomposition, this way is another decomposition. These arcs that

I draw

here, indicate that both of these has to be done, right, so you cannot do one of them.


example, when I have an and here, it means that you have to solve this sub-problem of


out A1, A2, and this sub-problem of multiplying A3, A4, and then you can solve this. Once


have solved this one, and once we have solved this one, then you can solve this, right?


as you can see, that there is cost associated with each of these multiplications. If I have


A1 is n cross m, if A1 is n cross m, and A2 is m cross k, then the complexity of finding


product A1A2 is what? n into m into k, right? And what is the size of this matrix? It becomes

n cross k.

So, when I take this n cross k matrix and then I multiply it with another k cross z


then the cost will become n cross k cross z, right? Now, you can easily see that these

products which all have, will all have different cause. So, depending on the decomposition,

the total number of operations that you have to do for the matrix multiplication will vary.

So, one problem is to determine, what is the best way to multiply a given set of matrices.


there are different kinds of solutions to this problem. For example, you may have studied

dynamic programming solutions to this problem. It is not difficult to create a dynamic

programming formulation for this problem. We will see how to cost this general problems


an and/or graph search framework, and we will study one algorithm for solving them. Coming


other examples of problem reduction search, there are several planning problems which


decomposed into sub-problems, and there are many ways of decomposition. Are you familiar


the tower of Hanoi problem? Okay.

The problem is like this, that you have 3 pegs, and one of them contains a set of disks.


are disks which have been put in from the top. So, these are round disks, which have


inserted, so they have a hole in between, so you can put them on this disk A. Now, what


have to do is to transfer all of these pegs- all of these disks- from a to c, using b as


intermediate. But, the constraint is that I cannot, at any point of time, put a larger

disk on

top of a smaller one. So, during the entire transfer, I can move one disk at a time; I

am not

allowed to move more than one disk at a time.

So, the constraints are one disk at a time, right? And the second constraint is that small

disk- smaller disk- can never sit on a- rather, it is the other way around: a larger disk

cannot sit on a can never sit on a smaller one, right? So, with that restriction- with

these 2

restrictions- we have to transfer the set of disks from a to c. There is very neat recursive

solution to this, that say, that- use the algorithm; suppose we have an algorithm, say

p. Use

the algorithm p to transfer the top n minus one disks; the top n minus one disks, from

a to b,


When you are moving this top n minus one disks, the largest disk is here; it remains here,


it is a sub-problem of shifting the smaller n minus one, to the second disk. Once you


solved this sub-problem, then you transfer the largest disk from a to c; there is no


in doing this, because at that time, c is empty. And then, recursively, again, transfer

the n

minus one disks, that were in b to c, right? So, what we have here is, suppose we say that

initial problem was, to transfer n disks from a to c; then, we are basically decomposing


into 3 sub-problems- that transfer the top n minus one disks from a to b, then, transfer


largest disk from a to c, and then, transfer the n minus one disks that we are moved to

b, so

they are now moved to b to c.

We have to solve all this problems in order to solve the tower of Hanoi. This is one kind


decomposition of the problem. There can be many other ways of decomposing the problem,


Once we have chosen a decomposition, the solving procedure is standard, but the objective

here, is to determine that which of these methodologies of decomposing the problem works


for a given problem? Then, there are blocks world problems in planning; we will discuss


later, when we talked about planning problems, and also theorem proving, where, in order


prove something, we will see that there are different premises and different ¬¬¬__

and the way

in which we combine these to arrive at the shortest proof, is also a problem reduction.

Let us see how we create a formulation of the problem reduction search problem. So,

we will

have an AND/OR graph, where an OR node represents a choice between possible decompositions.

There can be more than one decomposition, and we will use an or node to choose between

possible decompositions. I will give you an example- complete example, of what I mean

by that.

And we will have and nodes, which represents a given decomposition, right? It means that


you have an all node, then you have to solve any one of its successors; if you have an

node, we have to solve all its successors. So, and nodes are actually the decompositions.

And/or nodes will represent the choice between different decomposition. We will come to

examples which will clarify this, and later on, we will study game trees, where we will-

instead of and and or, we will have max and min nodes, where max nodes will represent


choice of my opponent, and min nodes will represent my choice.

When we come to game trees, I will elaborate up on this, but these 2 formulations have


similarity, in the sense that both have 2 different kinds of nodes; each node has a

kind of

optimization criterion- like max nodes will maximize, min will minimize, and nodes will


the sum of the cost, or node will take again the minimum of the cost, if you are looking

in a

minimization problem.

So, this is the AND/OR graph search problem. We are given implicitly specified AND/OR graph,

where the start node of the AND/OR graph, s is the start node of the AND/OR graph, t

is a set

of terminal nodes and h is a heuristic function that estimates the cost of solving the sub-

problem at n. And we are to find the minimum cost solution tree. Let me give an example


and then we will go into the actual algorithm for doing this. So, while I give this example,


will also give you an outline of how we plan to solve such problems. So, first let us

understand what is what do we mean by an AND node and an OR node.

So, suppose we start with a problem that we have to solve. Let us say this is something


the matrix multiplication problem. I have to multiply matrices A1, A2, A3, right? Initially,

let us say that I have an or node, which will say that I want to solve this as A1, A2, A3,


this one says, I will solve it as A1, A2 and A3. Now, clear, that these are the 2 ways


solving the problem? In order to solve it with this way, I have an AND node, which says


you have to solve A1, and you have to solve A2, A3. So, this is an AND node. And, here

also, I

will have a decomposition A1, A2 and A3. So this is an AND node, right? Okay. Now, the

way I

am going to evaluate it, is that I will find out- so, in order to solve this, again, I

have to

take the product of A2 and A3, right?

What is the cost of taking this product? Let us put some- put the dimensions of these,

so let

us say that the dimension of A is 3 cross 4, dimension of A2 is 4 cross 10, and A3 is

10 cross

1, right? If that is the case, what is the cost of this A2, A3? 4 into 10 into 1, so

that is

40. So I associate a cost of 40 with this. And what is the cost of this? 0 is- nothing


multiply here, so this is 0, right? What is the dimension of this A2, A3? 4 cross 1, and


dimension of this is 3 cross 4, right? So, since I have to solve both of these, so therefore,

what do I have as the cost of this operation?

This particular operation will have a cost of 3 into 4 into 1, so 12, plus the cost of

what I

have from this, so plus 40, so this comes to 52, right? Likewise, if you look at this-

what is

the cost of this? 3 into 4 into 10, so 120, right, and this has a cost of this has a dimension

of 3 cross 10, right, and what is the cost of this? 0? Okay. What is the cost of taking


product? 3 into 10 into 1, so 30, plus this 120, so this comes to 150. In all nodes, I

will be

choosing; because this is a minimization problem, I will be choosing the least cost successor,

so I will be choosing this one, right? Therefore, finally, what is my solution? It is the

sub-tree that is rooted along the solution, if I take the arcs along- the selected arcs


the OR node. So, it means that this is the way to solve the problem.

First, take the product of A2 and A3, and then you take with product, with A1, that

is going

to give you a total cost of 52 which is the best that you can do for this particular problem.

Let us consider, right? If you have many more matrices, then this tree would go deeper,


you will have more or nodes and more and nodes. But in and nodes, the cost of taking this

product and this product will add up, plus the cost of taking the product of this and


will be added to that, right? So, that is the cost of the and nodes. In the or node,

I will

select only the best among the successors, and the cost of that best successor will be


up as the cost of the or node, right? Now all this step we have said so far, is in the


of heuristic functions. in the absence of heuristic function

Just like we had in state space search, we can also have heuristic functions, that given


particular sub --problem, gives us an estimate of the best way to solve that problem. It


us the least cost by which we are to be we can solve that problem. Again, we can have

overestimates; again, we can have underestimates. So, at this point of time, we will assume

that we have only underestimates, right? So, if we take heuristics into account, let us


let us see what happens. So, let us say that we start again, with another example, where


the top node, we have h is equal to 7. And let us say that this is an and node. this

is an AND


So, the way in which we will solve this problem is that, we will- just like we were

maintaining open for state space search, we will maintain a marked and/or graph, indicating

which is the best way of solving the problem up to now. So, if we have a and node, in order


solve it, we will have to solve both of its successors. So, we simply expand the and node


we get its successors. In this case, let us say that we have 2 successors, and then again,


evaluate the heuristic function in the child nodes. So, let us say that this gives us h


to 4, and this gives us h equal to 3, right, and in general, we can associate some costs


the edges also.

These costs will be the costs of merging these sub-problems back into the original problem,

like, for example, in that case, this was the cost of the multiplying of the sub-products,

right? In general, we can have separate costs for the separate edges, right? So, now, you


what do we have here? We have 2 successors; this one has an estimate of 4- it means that


order to solve this sub-problem, we are estimating that at least 4 units of costs will have to

be incurred to solve this; at least 3 units of cost has to be incurred. And because this

is an

AND node, we have to mark both the successors, because both have to be solved.

The marked ones are the ones that we will eventually we want to solve. the once we eventually

want to solve. So, now, we can revise this cost- we can revise this cost, because now,


cost has grown, because we know to solve this, we require 4 plus 2, 6, and from this side,


have 3 plus one, 4, so, the total of 10 is the new cost that I associate with this AND


right? This 10 is also an underestimate, because this one will require at least 4, this one

will require at least 3, and if I add up this cost, then the total is at least 10. Is it


how I arrived at this figure-10- 4 plus 2 plus 3 plus 1? Then, let us say I expand.

Now, see,

when I have this marked sub-tree, it does not matter whether I expand this first or


first, because for the and node, I will have to solve both, right?

So, let us say, I pick up this one, and I expand that, and this, let us say, is an or

node. We

discover that it is an or node, and now it has 2 successors, right, and as we keep on

expanding this, we will go to sub-problems and sub-problems and sub-problems, and finally,


will arrive at an leaf level, where those sub-problems are unit level problems, which

we can

solve, right? That is the end of the decomposition- the basic units of problems that we will

solve. Let us say here, that these 2 that we have arrived at, are the basic sub-problems,

right, and let us say, that solving this requires 9, solving this requires 7, and let us say

that these 2 are zero, right?

So, I have 9 here and 7 here, okay? Now, because this is an or node, I can solve either this

or this, right? I will choose the one which has lesser cost, right? So, I will choose

this and

mark this successor, right? Now, this cost is going to get updated. What happens is,

I am

performing a cost revision bottom up, so I update this one to what? 7, right? And then,


update this one, because this cost has changed, so this will also change. So, now, this is

going to be 6 plus 8, so 14. So, this one gets updated to 14. As of now, I can see that


is the best way of solving the problem, and up to so up to this part, that this is the


way of solving it- where I have still not solved this one.

I will expand this I will expand this node and let us say, that this is also a or node.

So, I

will expand that. And let us say that I get 2 nodes- this one has h equal to 5. This one

has h

equal to 2, right? h equal to 5, h equal to 2. So, you can use pathmax, if you want, into


where is heuristic less than that of - yes yes, so you can update it, if you want, right,


if- you can update it, if you want, using pathmax, as we have done previously, right?

So, let

us go on with this example and those optimizations, that you can update this; we can do it

later. Let us say that this one has a cost of 1; this also has a cost of 1, right?

Now, see heuristic of this- suppose this has cost of 2, then you have nothing to worry


because this is 2 plus 2, 4, which agrees with this, right? It is because 2 plus one

is 3, and

that is less than this, so if you want, we can make this 12, let us make it 2. Now, if


compare this, this has a cost of 4 and this has a cost of 6. Therefore, we will mark this


as the base successor. In an OR node, we will always mark the best successor, the current


successor. Now, if you mark this, then this cost has not changed anymore, this cost has


changed, so therefore, we do not have to do any cost revision beyond this point, because


cost has not changed. So, there is no need to go further up; this cost will still remain


14, right?

And now, let us see- what is the best solution that we have? We solve this here, and this

here, right? Now again, we want to expand another node now, which node we will select?


one. We are not selecting this node for expansion, because currently, this is not good; this

is better- the OR node has picked this as a successor. So, we are always going to pick

a leaf

node of the marked sub-tree. In this case, the marked sub-tree, so far, is this.

We will pick up, always, a leaf node of the mark sub-tree and expand that. In the marked


tree, we have this one, so we expand this, and this gives us again: let us say we have


successor, one has h equal to 3, and the other successor is a solved node, which is 10, this

is 0, this is 1, let us say, and this is an AND node.

So, now, what is the cost? This cost is going to get updated; it is going to be how much?


plus 0 and 3 plus 1, 4, so 14. This cost has changed, by the way, because this is the and

node; both of it successors will be marked. Now, we take this node and again, because


cost has changed, this whole cost revision step will have to be done. Now, this one will


replaced by 16- 14 plus 2, 16. Wait, wait. Now, now now at this point of time, we have

to see

which is the best for successor of this or node. If you look from this side, what you


getting up, what is being backed up is 16, but from this side, we now have a better one-



So, we are going to choose the less of the 2, and take 6 as the heuristic cost of this


Now, does that change this- it does, because it has changed from 4 to 6. This is now going


become 16, is this clear? And now, the marked successor is this- this mark is not there

anymore; this mark has shifted in this direction, right? So, the mark shifts when I find the

better successor of the OR node, so the mark has shifted here, right? Then, I expand this,


let us say I get the let say that this is an AND node and I have this with a cost of

3, and

this has a cost of 4, and they are solved node- terminal nodes. Now, what is going to


This is going to get updated to 7. This is going to get updated to 8, but this is still


best successor; this is still the best successor, because we are comparing between 7 plus 1

and 14 plus 2, so between 16 and 8, so, we will select this one, still.

This is going to get updated to 8, and this is going to get updated to 18, right? And

now, we

use- we are in a point where all the leaf nodes of the marked tree are solved. The best

way to

solve this problem, is by following the marked tree, and solving those problem. What we are

going to do is, we are going to solve this problem- we are going to solve this problem,


we are going to solve this, then we are going to solve this, then we will solve this, that

will solve this, and then we will solve this one, and the best cost of solving this, is


to be 18. Is it clear? Is that alright? Yes. Coming back to here, you are saying that we


not yet solved this one. Our heuristic are underestimates, right?

This one is going to cost at least 16, if not more. If you go further down, your cost

can only

increase, because the heuristic cost are underestimates, whereas on this side, we have

actually got a solution of cost 8, right? A complete solution of cost 8for this one,

and in

this side it says it is at least 16. Between at least 16, and exactly 8, we know that exactly

8 is always going to be better, right? So, we do not actually go to solve these things


further. The full and/or graph is not going to be explicitly generated; this is progressively

expanding its best first, only up to the point where we have got the minimum cost solution,

right? Now, if you think that we could have solved A* also in the same way, we could have

taken the initial problem, except that in A*, we do not have and nodes; we only have

or nodes.

To solve a start problem, there are several different choices in a star- the set of successors

and then take the successors of those successors, and in this way, you could expand it out

into an or graph, right? A graph which has only or nodes, right, and we could use the


marking strategy- always maintain the best cost successor at every or node, right? Now,

if we

did that, then we will still arrive at the same solution as A* does. At every point of


the node that you are selecting for expansion will be the node that is along the best cost

path from the start state, that is, the minimum cost node that we are always expanding. That

will be the only node which is along the marked path, because we do not have and nodes, there

will be only one marked path from the start state. So, try to think of a star in the context

of and/or graph search.

It actually is doing the same thing as well, but there we were maintaining open as a separate

list, but if you think of open and close together, it is nothing but this tree. Let us look at

the algorithm that we just now worked out. Initially, we will define a thing called g*.


here, is the marked sub-tree, rooted at the start state. At every point of time, it will

denote the sub-graph, which is which has so far being generated out and rooted at the


space. Initially, the estimate of the cost at the start state is equal to hs, because

we do

not have any other cost at that point of time. Now, if we find that the start state itself


a state belonging to t; t is the set of terminal states- terminal states represents those

sub-problems which are unit level sub-problems, which we do not further decompose, but solve

directly. So, t is the set of sub-problems, which are directly solvable.

If we find that s belongs to t, then we will label s as solved; whichever is a terminal


can be labeled as solved. Then, if a if at any point of time, the start state is labeled


solved, then we terminate. Let, now, when we are in or node, right, and the best cost

successor is marked solved; then we labeled the or node as solved. In a and node, when

all its

successors are labeled solved, then we label it as solved; so we are coming to that. The


step is the select step- so, what we do is, we select a non-terminal leaf node from the


sub-tree, as we were doing previously. At every point of time, we just look at marked


and select the non-terminal leaf node, then expand that node to generate the successors


this state n.

For each new successor, we set fm equal to hm; for each new successor mind you, we set


equal to hm. If m is terminal-if any of the successors is a terminal node- then we label

it as

solved. And then, after we have done this, we will call cost revise, which is the bottom


cost revision step, and finally, we will return to step 2, right? Now, let us recall the

example that we had done just now, where, well, it is all cluttered up here.

But if you remember, that we had initially started with the and node, generated it successors,

right? Expanded the node, generate it successors, then marked for an n node. We marked both


its successors, right? And then, for an or node, we mark only the best cost successor,

and we

label a node as solved only when the best cost successor is labeled solved. When this


solved, and at this node, we find that the best successor is this- and the best successor


solved, so we can label this as solved. Then, we expanded this node, and initially, first

time, we went this way- when we backed up this cost; when this was the best cost successor,


was not solved, that is why we never labeled as solved, at that point of time.

But when we went this way, and found that this was solved, this was solved and then


this is an and node, both of its successors are solved, so, we labeled this as solved.


when we went back to this or node and found that the best successor is solved, that is

when we

label this as solved, right? When the best successor is labeled solved, we label it as


Why? Yes, because the other along the other directions, we will only have more costs,


they are all underestimates. And if this is the better, then those underestimates, and

this is

the best that we can get, so we label it as solved. And then, when this AND node has both


its successor were solved, then we label this as solved.

And, if you look at the algorithm, whenever s is solved, that is when we terminate. Let


look at in details at this step, what do we do in cost revise? what do we do in cost revise.

That is where we will compute the costs of the parents from the successors, and in and


we will decide to shift the marking if necessary.

What we are going to do is, we are going to start with the node from where we want to

do the

cost revision. Let us say that in this, when we came up here and updated this cost, right,

then, from here, we will do the cost revision backward. Initially, which- the node that


generate at the bottom, is the one from where we will start the cost revision. So, we found

out these 3, plus one- 4, and 10 plus zero- 10, so 14. So, we start cost revision from


right? Now, what we do here is, we create z equal to n, so we start with z equal to

this state

n, right? Then, coming to the slides, slides slides- when z is empty, that is, where we


done. Otherwise, select a node m from z, such that m has no descendants in z, right? Why

do we

do that? Because we want to go bottom up; we want to go bottom up, so we will always


first, the state which has no descendants in z.

Then, if m is a and node with successors r1 to rk, then we set fm to the sum of the child

nodes, plus the cost on the edges, right? So, this is fri plus cmri, which is the cost

of the

successor ri plus the cost of the transition from m to ri, cost of the edge from m to ri.

Then, we submit over all the edges, that that is because this is AND node, so we have to

submit over all the edges, and then mark the edge to each successor of m. Because it is

an and

node, we mark the edge to every successor. And if each successor is labeled solved, then

m as solved, right? Okay.

After this, what we need to do is, we have to check whether, after this exercise, the

cost of

m has changed. If cost of m has changed, we will put it back into z- we will put it into

z, so

that in the next iteration or subsequent iterations, we also examine whether the parent of m

is also going to change, right? What happens if m is a OR node?

If m is a OR node with successors r1 to rk, then similarly, we compute the cost of solving

every child as fri plus cmri, but because this is a or node, we will find out the minimum

among this. We will find out the minimum among this, and that is going to be the new cost


m. So, cost of the or node is the minimum of the cost of solving its successors. And

then, we

mark the edge to the best successor of m, and if the marked successor is label solved,

then we

label the or node as solved, okay?

And then, finally, if the cost of m has changed- regardless of whether m was a or node or and

node, if the cost or label of m has changed- then, insert the parents of m into z for which


is a marked successor. Now, you might find something interesting here. We are talking

insert those parents of m into z. Now, when we are talking about and/or trees, as we have


here so far, there can be only one parent, right? But, in case you have a graph- and/or


then, you can have more than one___ . At this point of time, we are not talking about graph,

right? If you are further interested in this area, you can read up what happens in the

case of

and/or graphs, okay?

In any case, any graph can be unfolded into a tree, so if you do not want to remember


you are visiting the same node from 2 different paths, you can keep that as a and/or tree,


that alright? Okay. So, the question is, why do not we just climb up the tree and update


of them along that path, right? Now, that is essentially what we are doing; also what

we are

doing is, in the case of a tree- because there is only one parent- we can just what will

happen is, it is you will have always z will n will have a single parent.

So, if the cost of n changes, then the cost- the parent of z will be put in z, and then

in the

next iteration, the parent will be picked up, right? And if the parent of that parent


changed, then that is one which is going to get inserted. So, if it is the same thing

that is

happening; but in the case of a graph, suppose you have the state n, and this state n could

have been the or successor of some node, and could have been the and successor of some


right? Or could have been the or successors of 2 nodes also.

So, in that case, you see, when the cost of n changes, the cost of this node can also


the cost of this node can also change, right? Okay. So, as a result, we will put this also

into z; we will put this into z, and we will also put this into z, right, so that both

of them

are again updated, with respect to their respective parents, right? So, because this algorithm

that I have talked about, is for and/or graphs in general, those are examples that I have

given this for and/or trees. But this algorithm itself is applicable to and/or graphs as well.

So, therefore, the cost revision steps that we have mentioned here, are actually made


graphs. Yes. Yes. No no no, it can be, see- look at this examples in this or node. The


way to solve this or node could be this, and in this and node, both of these are marked.


it is also the marked successor of this, and as well marked successor of this. No, see,

if it

is not marked, suppose this or node is actually pointing in this direction. So, it is not-


is not selecting this. So, this option for this or node- this option is still better,


Therefore, this cost is going to come up from this side; it is not going to come up from


side, right?

So, if there is if the the the parent node is still marked the other way, then you need

not do

cost revision beyond that point, right? If this fellow's cost changes, and this the mark

shifts from here to here, then we need to put this back into z, so that this fellow's


also gets a chance to see, whether, now, this becomes the better path, understood? Is that

clear? Any other any questions regarding this algorithm? No, right? What I would suggest


you take a few more examples by AND by gr graph and/or graph, right, and try to see

how best

to how you can apply this algorithm by and, to solve it. Yes. If a node is marked as solved,

it means that you have already found out the best way to solve that sub-problem. So, for

example, if an and node recursively- if an and node- all of you are successor solved,

then you

have solved that and node, because you know exactly how to solve everything from below


and node.

In an or node, if the currently selected successor is labeled as solved, then you know that

you need not worry about the other successor, because those other successor are going to


you more. So, the marked successor- if that is labeled as solved, then you know that if


follow along this mark, then I have already solved everything below that. So, I can label


node as solved. What are the initial set of solved nodes? The terminal nodes. The basic


problems, which cannot be further decomposed, are the initial set of solved node. There

is a

fixed cost associated with each of those terminal nodes.

So, that is the cost that you have to incur, that unit sub-problem which cannot be further

decomposed, okay? So, a class- so, how does AO star fare? So, the this algorithm that

we had

so far, is called AO star; it is a and/or graph search algorithm, so we call it AO star


star. How does it fare when the graph has only OR nodes? Well, it fares exactly like

we having

a*, right?

So, the next topic that we will look at is searching of game tree. I will not start this


today, because we are nearly towards the end of this lecture. We are not starting this


what we are going to see in game tree is, we will have 2 types of nodes- just like we

have and

nodes and or nodes, we will have max nodes, min nodes. And we will see how we can model

a game

playing problem, as a problem of solving game trees, with max nodes and min nodes, right?

So, the next lecture- we will talk about game trees and how we solve game trees, right?

And, I

also intend to wrap up a little of the previous things that we left on search, so that from

the next to next lecture, we can get started with knowledge and deduction, okay? Thank


In today's class, we will start on game trees, and we will see how we can model different


playing situations in terms of game trees. We will study some very classical algorithms


searching in game trees, and finding out when we are in a better position, and when we are


a worst position.

So, in this, on searching game trees, what essentially game trees are?

They are OR trees, namely. We have already studied what AND/OR graphs are, and AND/OR


are. Game trees are a special type of OR tree, but there are 2 types of OR nodes. By OR tree,

we mean that at a time, we will be selecting only one of the successors of the OR node,


which one will be selected will depend on whether it is a min node or a max node. I


shortly explain why we need this kind of a representation. And briefly in min nodes,

we will

select the minimum cost successor, and in max nodes, we will select the maximum cost

successor. Terminal nodes can be winning or losing states, but it is often infeasible


search up to the terminal nodes. So, we will use heuristic costs to compare non-terminal

nodes. So, let me start by showing a simple formulation of a game tree search problem.

Let us

say we take that example of tic-tac-toe.

In tic-tac-toe, what we have is something like this, right? And the players alternate


putting either a circle or a cross, in any of these positions. Let us say, that we start


a configuration, where we put x here, right? Then, from here, so this is where the one


this is the starting configuration. Let us say now, it is the move of player b; so, when

it is

the move of player b, then there are various different moves that player b can take. Say,


out of which, this is one, or this is one, and so on. Then, for each of these cases,

player a

has a move. Here, let us say player b has a move. From this point, in each of these


player a has a move.

Suppose player a makes a move here, then player a can, again, take one of many different

moves. Suppose, if this is the step, and player b can give something like this, or player


can give something like this, and so on, right? Then, you know that suppose this is the move,

that player b has given, then, again, player a will have turns, but if you look further


this, then you will see that all- there is a way of playing, by which this fellow always


Because, if now, the only possible option of this player is to put a dot here, and if


happens, then the other player can put a cross here, and then there is no way of saving the

game, right?

If you look below this sub-tree, then you will see that that for every move that this


makes, the other player has a winning strategy, right? Now, so, this is the structure of the

game tree. The game tree is a tree where every node of the tree, represents a state of the

game, and nodes can be either max node or a min node. I have not yet defined what I

mean by a

max node or a min node, but let us say that one of these type of nodes is for player a,


the other is for player b. So, depending on who has the move, we will distinguish between


types of nodes, right?

The Description of Lecture - 6 Problem Reduction Search: AND/OR Graphs