We're now going to graduate from black box states to factored states. Remember that in

all our search and adversarial search stuff we could not look, the search algorithm in itself

could not look into the states. These are black boxes. We might know the name but that's all.

We kind of relented on this a little bit. We in chess the evaluation function for instance,

we allowed ourselves to look at the boards but only for heuristics, not for actual research.

We didn't reason about the state of the world. If we look at what our evaluation function was,

we essentially had data of the form rooks, probably not, one, pawns, seven and so on.

We had certain features we called them, which had certain values. Then we made a weighted sum

and came up with 37 or something like that. Then we fed that back into our black box search

algorithm and said, oh I'll go with the 37 because there's only a 25 as an alternative.

We don't want that. Now what we're going to do next is we're going to say, aha, why not always

treat states in this way? We can always transform this into a state, maybe a state 317. But as you

can see, there's a lot of information we lose. It could be that algorithms that take the inner form

of the states into account might actually run better. That's the initial idea. That's an idea

that's very plausible. Namely, the more information I have, the better I can do. It's not always true

though, but on average that is true. Also on average, the algorithms get more complicated.

Iterative deepening search is extremely simple. There's no reason we have to wait until university

to teach somebody iterative deepening search. You can almost do it in elementary school. Very,

very simple. The more complex the objects become, the more interesting the algorithms become.

We go up the next step. We're going to what we call factored representations, which has a finite

number of slots which have values. True-false or high-low-middle or school grades from 1.0 to

4.3 or whatever. The simplest way of thinking about these is what we call constraint satisfaction

problems, which is what we come to now. Let me start with a constraint satisfaction problem, namely

scheduling Bundesliga tournaments. Here is a schedule of a couple of years ago. You have events,

like BVB plays Bayern München in Dortmund on the 12th of December at 6 o'clock. Every one of these

events we can describe by things like, let me just invent something. Home team, what do you call the

other team? Guest. Guest team, date, time. What else do we need? Yeah, let's assume that the home

team always brings the stadium along. I don't even know how realistic that is. Yes? Referee maybe,

yes, you don't want a referee to be in two stadiums at the same time. Maybe a little bit more,

but not much more. Let's assume that this is it. Any one of those has a couple of values. In every

Bundesliga we have 3N plus K teams, so you have team A, team B, and you can already see that these

two aren't independent. You do not want BVB play BVB because then it's clear who wins. You want to

have that A is not equal to B. That's essentially the setup. You have a set of states which you can

describe by partially filled information slots, and you have so-called constraints. Constraints

are just like things like A is not B. Or you want to make sure that every team plays at least one

exactly once in on a weekend. And you want that the dates are Friday, Saturday, Sunday, one of

them, and so on. There's quite a lot of constraints there, and they all have to be satisfied. So you're

looking for a set of states here that, or for a state, so you actually want to have, no I again

don't know how many teams there are, you want to have essentially 12 of those if there's 12 teams,

which I don't know, 20 or so. How many teams are there in Bundesliga? 18? Good, thanks. I'll directly

forget it again, but maybe I can remember until the end of today. So that's really what constraint

satisfaction is about. We have these forms where we can partially fill out values, and we have

constraints on the forms, and we're looking for a state where every one of these slots has been

filled out in a way such that all the constraints have been satisfied. That's why it's called

constraint satisfaction. Okay, so here, so up till now we have black box states, now we have

constraint satisfaction problems, in which we have a state that is given by a set of variables.

Variables think names of the slots, and each variable has a domain, right? You do not want to

say the home team is 12 of December 18, right? It's not going to help much. So you say this

home team is one of the 18 teams of this year, of this season, and you really have these variables

and their domains plus constraints being a formal language, which is still very simple,