R22. Dynamic Programming: Dance Dance Revolution

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. PROFESSOR: So we’re going
to do a problem that looks like the guitar problem. But it’s a bit cooler. At the same time,
there are fewer states, so I think it’s
easier to manage. How many people know
how to play DDR? AUDIENCE: Well. PROFESSOR: Yeah. OK. How many people know the
rules of playing DDR? Because otherwise I won’t
be able to lift my hand up. OK. OK, so let’s go through
an algorithmic model. So, you have a board that
basically looks like this. And you have four
touch sensitive pads. Up, down, left, right. And then you have
a center position. You also have a sheet of notes
that looks something like this. Say, up, up down, down, up
down, up, up down, left right, left, left right, right. So on and so forth. So when you see an
arrow of up, that’s a constraint that
says one of your feet has to be on the up arrow. Has to tap the up
arrow, actually. There’s no constraint
for the other foot. So your other foot can be
anywhere else on the board. It doesn’t matter. You are also allowed to tap
the board some extra times. So if you don’t have
a note showing up, you can still hit the board. And there’s no penalty. So you can hop around as
many times as you want, or as many times as you can,
until you run out of breath. So up basically means, it’s
actually one foot has to be up. The other one center. Also, of course, because
of the design of the board, it doesn’t matter
what foot is where. So what are possible
goals for this game? AUDIENCE: Not to get an F. PROFESSOR: OK. AUDIENCE: Hit all
the arrows when they line up with the top row. PROFESSOR: OK. So there are two different
ways of doing it. One, you said,
“not to get an F.” So I would say, given some
limited set of skills. So given a set of skills,
or your skill level maximizes your score. right? AUDIENCE: Yeah. PROFESSOR: This is
dynamic programming, so we always want to
maximize something. Now, if you’re really good,
then another possible goal is hit all the notes with
a minimum amount of effort. If you’re going to
be in a competition, and you’re going to
be doing 10 songs, you don’t want to die after
the first song, right? So, assuming you can do
everything reasonably well, this is another possible goal. Any other goals? So we’re brainstorming here. This isn’t set in stone. We’ve already seen the formal
solution for this problem. So I want to play with it
for a little bit, right? We brought a DDR pad, so
I want to play with it. What else could you hope
to maximize or minimize for with dynamic programming? AUDIENCE: Not look ridiculous. PROFESSOR: OK. AUDIENCE: I guess we’re looking
at the cost of each move, right? PROFESSOR: So,
hit all the notes. Minimum effort, or otherwise
say best appearance. So every move looks somewhat
good or somewhat bad. And you want to do the moves
that look as good as possible. So this maximizes
entertainment, right? if you’re on TV, you
probably want this. Now suppose you are
in a competition and you only have
one track to play. AUDIENCE: Well, you know
where all the notes are. PROFESSOR: Sure. Like, we assume that we
know this ahead of time. So you’ve memorized this. And you’re trying to
compute the best strategy, so you can memorize that. Then when you go and
play, you dominate. AUDIENCE: Yeah. PROFESSOR: So, if
you have one track, then I would say that
what you’d want to do is minimize your
probability of failure. Right? So given the probability of
failure for each possible move. You want to minimize the
overall probability of failure so your teammates
won’t hate you. So, hit all the
notes and minimize. So this one’s a little bit
different from the other ones because all the other
ones are already set up as a nice problem
where you add up things. So you can solve
them with graphs or with dynamic programming. If you want to minimize
the probability of failure, then you want to maximize
the probability of success. The probability of
succeeding on all your moves is the product of
the probability of succeeding on each move. All right? So if you have five
moves, then you have five individual
probabilities. You multiply them up. And that’s the probability that
you execute the whole sequence correctly, and not stumble. So we have products
instead of sums. Yes? AUDIENCE: Isn’t it related
to the maximizing score goal? PROFESSOR: You can. Well, not necessarily
because this one says that you only have
some possible moves. I think in the end, all of
them, except for this last one, can be solved using the
recursion depth we have for it. The last one, you have
to do a bit of massaging. And we’re going
over that right now. So, you have products
instead of sums. How do you turn
products into sums? AUDIENCE: Logs? PROFESSOR: Yep. So, for this one, I
would want to use logs, so that I can say that
I want to maximize the log probability of success. Which is just the sum of the
log probabilities for each move. And then it looks like
dynamic programming, as usual. Now, if I wouldn’t
want to use logs, if I’m using the DP formulation,
where I’m doing recursion, I can incorporate
products there. But it turns out,
I didn’t practice. If you have a lot of
numbers that are close to 1, or that are close to 0,
so all the easy moves are going to be really
close to 1, for example. If you have a lot of numbers
that are close to 1 or close to 0, if you
multiply them up, you get numerical instabilities. So we get the number
that’s really close to 1. So for example, if I’m choosing
whether to do, say I’m here, and I’m thinking, do I
want to move like this? Or do I want to move like
this, and then like this? These are both
pretty easy moves. So, in both cases, we’re
looking at probabilities of success of 99.991%. And maybe 99.992%. So if you have numbers
with probabilities that are really close to 1,
and if you have a lot of them and you try to
multiply them, you’re going to get a bad result. So all the products are going
to start looking the same. So we’re going to get
a random solution, instead of what you want. This is a practical thing. It’s called numerical
instability. And it’s a practical
reason why you’d want to use logs, instead
of multiplying things up. So it’s not just a
theoretical thing. It also makes life
nice in practice. OK. So we have a goal
that looks like this. Say, let’s go for this one. Hit all the notes,
minimize the effort. And all the other ones can
be reduced to this one. We need to define effort, right? Let’s say that we have a
function called delta, that takes two foot locations–
so, where both of my feet are– from and to. And it gives me a number from
0 to 1, where 0 is really easy. And 1 is really hard. So from would look something
like, my left foot is up. My right foot is centered. To would look something like,
my left foot is centered and my right foot is up. So basically going
from here to here. So from left foot up. Right foot center. To here. So there is some
difficulty there, right? We have to jump, so it’s not 0. I’m burning some calories here. So any move that I make
has some difficulty. And I want to solve the
game so that overall I have a reasonably
small total difficulty. OK, are we understanding
the problem? So we have three
possible avenues here. We can start solving it
using dynamic programming. We can start solving
it using graphs. Or we can have someone else
play the DDR again so that we can get more hands
on experience, and look at what a good strategy
or a bad strategy looks like. So you guys get to vote. Who wants to solve this using
the dynamic programming? Who wants to solve
this using graphs? Who wants to get more
hands on experience? Damn. I was hoping that DDR would win. You guys are boring. So, graphs, right? We’re going to have notes. Notes represent states, right? So a state is where you are
at some point in the game. And we’ll have to define
what where you are means. And then, when you
jump, you make a move. So moves go between states. So in any game, you
have states and moves. A state is very
hard to put in time. And then you make a move. Like in chess. Your state is your
board position. And whether you’re
moving, or your opponent is the next to move. And the move is when you take a
piece and put it from one place to another. So your vertices are states. And your edges are moves. So what’s in a state? This is our problem. Whether we’re solving
it with graphs or with dynamic
programming, this is what everything
comes down to. What’s in the state? AUDIENCE: So your current
state is how much difficulty have you– what is the problem? Are those representing
the probabilities, the difficulties? Or. PROFESSOR: So this is the
difficulty for one move. Does it depend on
previous moves? AUDIENCE: No, but. PROFESSOR: No. So it’s a nice thing to
note that the difficulties for each move are independent. AUDIENCE: Would it be
dependent in real life? You’ll get tired at the end. And he’s able to
have less energy. PROFESSOR: Yep. So, in real life, we might
want to say that this actually depends on how much energy
you’ve expended so far. And if we have time,
let’s solve that problem. So the nice thing
about this problem is there are many directions
in which we can take it. This is one of them. I’m fine. And I think we’ll learn
a lot by doing that. So back to the original problem. Suppose that it doesn’t
matter how tired you are. You’re pretty
good, so you’re not going to be tired
enough to go [GASP]. So, mostly independent
difficulties for each move. What’s in a state? AUDIENCE: The sum of the
difficulties up to that point. PROFESSOR: OK. So. AUDIENCE: Your
appearance factor, if we’re including that. Or are we only doing– PROFESSOR: So we’re doing this. AUDIENCE: Oh, I was just. Oh, effort. OK, we’re minimizing effort. PROFESSOR: So the way
I like to think of this is, what is does a
solution look like? It’s made up of
decisions, right? What are the decisions? AUDIENCE: To make that move
or don’t make that move? PROFESSOR: We’ll see. But once you know what
the decisions are, then you have to think, what
do I need to make a decision? AUDIENCE: The note. PROFESSOR: So, a
note is one of these. For some reason,
they’re called notes. AUDIENCE: So you
know that somehow you have to hit all of them? Like, you can have
steps in between. PROFESSOR: Yep. AUDIENCE: Moves in between. You have to hit all of them. PROFESSOR: OK, so I like this. So, every one of these is going
to have to generate a move. And there might be
some moves in between. Well, each move is going
to map to some edge. And I’m going to need vertices. So, as an algorithms program
where when I hear that, oh. I can have some moves in
between, I get really uneasy. Like, what is this? How many moves am
I going to have? Is this going to
become really huge? And am I not going to be able
to run any algorithm on it? So let’s think about that. How many moves would
I have in between? And, what would I
achieve with them? AUDIENCE: I guess you’d have
a max of, like, four, right? I mean, you can put your
right leg someplace, and you can put your
left leg someplace. That’s like a max of two. Right? Or no? PROFESSOR: So, let’s
think of an example. You want to go, say,
I want to go, what? From here to here, right? AUDIENCE: Um-hmm. PROFESSOR: And
you’re thinking what? They can do this, oh sorry. So I can do this as one move. And this is one move. AUDIENCE: Yeah. Or you can just do
one jump, right? So it’s– oh, yeah. I guess that’s more than one. PROFESSOR: OK. So looking at this,
if I’m considering whether to go from here to here. If I want to go either this way,
or if I want to go this way. So let’s write this
down on the board. So I’m going from up
down to left right. And I’m considering, do
I want to go directly or do I want to
go up right first. And then left right. Let’s not do these arrows
because they’re confusing. So, do I want to
transition like this? Or do I want to
transition like this? Well, I claim that, since
my moves are independent, going from here to here,
if it’s beneficial to go this way instead of
this way, I would want to go this
way all the time. So I would just say that, look. Inside my delta here, I
would say that, actually, if you know what you’re
doing, whenever you have to go from here to here,
you’re going to go like this. And the delta is going to report
to the total delta for this. So, if the problem is
that they have one note, and then I have my next note
like this, between these two notes, I can always
go in one move. AUDIENCE: So you’re
saying 1 would like, including in our
difficulty function, it’ll also tell
us, like, what move we should make to get there? PROFESSOR: How to get there. The best way to get from
one state to another. Well, like when
you’re learning DDR, these are the
basic steps, right? Like, you practice until you
know how to get from one place to another. There is something else where
you need intermediate steps. AUDIENCE: Or if
you’re holding one and then you’ve got
to move to another. Right? PROFESSOR: So, let’s
not worry about holds. Let’s say that we
would just represent holds as– so if you have
a hold in a game, then we’re just going to
represent it like this. We’re going to cheat. So we don’t have
to deal with it. In real life, you would
have to deal with it. Like if you’re actually writing
a program that trains people. AUDIENCE: What happens if you
have, like, right, left, up or something. So let’s say you start off
hitting your right foot on the top, and then you have
to hit the right one again. And then you have
to hit up again and then you have to transfer. So I guess anytime you
have to through the middle. You have move your foot. PROFESSOR: So I like the idea
of going through the middle. Why or how do you, why would
you go through the middle? AUDIENCE: To avoid crossing
your leg over or something. PROFESSOR: Well, what if I
have something like this? If there are DDR experts, I
know this isn’t the right way to do it. But one way of doing it is
left, right, left, right, left, right. So then, I have some states
that account for the fact that I’m centering. So, some people like
to do this, right? Some people like to go to the
center as much as possible, if they have time
between the moves. So then, I would need
at least one state in between where I’m
allowed to center, right? In order to represent
what I just did there, I need one move. So, one way I could meet
this is I have left center. And then left right. And then left right,
left right, left right. So on and so forth. But this would mean that
instead of doing this, which is reasonably easy, I
would have to do this. This. And then jump, jump,
jump, jump every time. Harder. Not good. Not good for my knees. Not good for my score. So I don’t want to do this. I want to have an intermediate
state so I can say, I start here and
then I get back here. Then I do this. Then I get back here. Then I go here. And then I go back here. And then go back. Do guys see how this works? AUDIENCE: You could
also rock back and forth to because they don’t require
both feet to be on the ground the entire time. PROFESSOR: Rock back and forth. Hold that thought. That might come in handy. Assuming we have enough time. So, if we only do one move
every time we see a note, we’re stuck with this. In our to allow
re-centering, we have to add states between the notes. We need to add an
intermediary state. And you can either think about
it, or take my word for it, but if you represent the notes
using the trick that I said above, and you want to represent
centering, then all you need is one extra state. So one extra move
between every two states. Between two notes. And that’s enough. Because that one extra
state allows you to center. And it allows you to do pretty
much everything a beginner like me would know how to do. AUDIENCE: So you only need one
extra state between each note? PROFESSOR: Yep. That is the inside. That is where I’m
thinking, right? So I have to do both
this trick, to see that I don’t need an
infinite number of steps. And come up with the
need for centering to see why I need one
intermediate step. By the way, does
anyone know what’s the right way of doing that? What’s the right way
of doing this move? You said, rock back and forth. So I wouldn’t rock back and
forth in this case, right? Because that
wouldn’t be helpful. How would I rock? AUDIENCE: Well,
you hold down one and then you go
to the other one. PROFESSOR: Yeah, so
rock left and right. OK. AUDIENCE: I said back and
forth, I meant rocking– PROFESSOR: Sorry. I thought back, forth. So, the optimal
way of doing this is left, right, left,
right, left, right. So what am I doing? AUDIENCE: You have another move. You have, like, one
state for your foot where it’s not touching the ground. PROFESSOR: OK. It’s an interesting, and
important, distinction. So if I wanted to hit
both of them, if I’m here, and I need to hit both of
them, I need to hit them. If I only need to hit
one of them, if I’m here, I can hit it like this. If I’m here, though,
and I want to hit it, I have to lift myself up. So the difference is
whether I’m like this. Or like this. Where is my weight? So if I want to allow
for these moves, if I want to go past the
stage of very beginner, aside from keeping track
of where my feet are, I have to keep track of whether
my weight is on my left foot or on my right foot. So, I would actually
have l, r, and W, where W is either l or r. AUDIENCE: So your state now
has what you’re currently putting more weight on. PROFESSOR: And where
each of the feet are. AUDIENCE: Yeah. Where your two feet are. And then also, the
song difficulty. So it’s everything
in your state, right? PROFESSOR: Ah, yes. I didn’t think about it. I was just talking
about foot position. But we need to get back
to the state thing. So that’s a good point. So before we get to that, how
many feet positions do we have? If we don’t include where
do I have my weight, how many possible positions
for both of my feet do I have? So I have two feet. Each of them can be in any
of these five squares, right? So how many total positions? AUDIENCE: 5 choose 2. Using 2. PROFESSOR: So I can do this. AUDIENCE: Sure. Why not? PROFESSOR: Well, if I have
5 choose 2, then you– AUDIENCE: Oh, then that
doesn’t quite work. PROFESSOR: Yeah. AUDIENCE: Yeah, no. PROFESSOR: So flip. AUDIENCE: Times 2. PROFESSOR: Yeah. So you have two feet. Each foot, five possibilities. Now, what if we have weight? If we are tracking on
where I keep my weight. How many possible positions? AUDIENCE: [INAUDIBLE]? Oh no, because there’s only two. PROFESSOR: So,
for each of these, there’s two possibilities now. So 50. AUDIENCE: You also have to be
so your weight is like this. PROFESSOR: In the middle? AUDIENCE: Yeah. PROFESSOR: You can. Based on that what I’ve been
reading, you never want to. Because if you’re
weight is in the middle, then you’re extending a lot
of effort to move either foot. So you always want to have
your weight somewhere. So that, at least
for one of your feet, it’s easy to move it. AUDIENCE: Could it be the back? PROFESSOR: If that’s
not true, then yeah. We’d need to have a center. Oh, so, like, whether I’m
like this or like this? AUDIENCE: Yeah. If you were, like,
doing the same thing. Rocking back and forth. PROFESSOR: So, if
I have two feet, then this says my weight
is on my left foot. My weight is on my right foot. So l and r is which foot,
not where on the board. AUDIENCE: So, did you not do
center because it was optimal? PROFESSOR: Because I claim
that, in an optimal strategy, you wouldn’t have it. But you don’t have to
take my word for it. If you don’t believe
me, then you add center. And you just have
more possibilities. And if it happens to
not be an optimal thing, then the dynamic
programming will ignore it. So how many positions do
I have if I add center? So if I have left, center,
right for each position. AUDIENCE: 75. PROFESSOR: Cool. Yes. AUDIENCE: So why is it 25? You wouldn’t actually have
both of your feet on the right. PROFESSOR: Why? Maybe, well especially, for
maximizing this one actually. Especially for
maximizing entertainment. Then it’s way cooler
to do this, right? [LAUGHTER] You get the point. AUDIENCE: –possible weight. Like combinations
for like, where is you should have your
feet at one time. Like, not necessarily what
the game is asking you to do. PROFESSOR: Yeah. So this is where my feet are. The game will always
ask something like this. So the game won’t always
care about both of my feet. Sometimes it’ll only
care about one foot. So, yeah. There are two different
concepts, right? There’s the position of my feet. And then there’s the
note on the screen. And my feet have to match
the note on the screen. And we’ll have to
capture that somehow. So what’s in a state? What are my decisions? Come on, now. We should be in a good shape
to know what my decisions are. What do I decide every time? AUDIENCE: What move to make? PROFESSOR: Yeah. How am I going to jump, right? Where my feet are going
to be in the new position. So every time, I’m deciding
what’s the new foot position. AUDIENCE: Aren’t you also
deciding weight position, where you’re going
to hold to, right? PROFESSOR: OK. So when I say foot position,
it’s a cheat for everything. So yeah. Good observation. OK. What do I need to know, in
order to make this decision? OK. I would need to know
where I was before if I want to compute
the difficulties. But aside from that– what? AUDIENCE: Sir, it came
up with this polynomial. PROFESSOR: All right. AUDIENCE: Is that a hint to what
the run time of this will be? PROFESSOR: It’s not on purpose. But yes. So, yeah. That makes sense. Probably not good. I should probably not have
my screen up without me looking at it. OK, so. Back to decisions. I think I want to know what’s
going to be on the screen when I land, right? Because if the screen says,
yo, you need to go up and down. Then maybe I shouldn’t
do this, right? That would not be good. So I need to know what the note
is going to be when I land. Note. AUDIENCE: Is that
the same as the next? PROFESSOR: Yep. Next note. Yes. So the next note
here on the screen. So, my position in
this list, basically. AUDIENCE: So it’s kind of like
the knapsack problem, where it’s like which thing we’re
considering picking up. But in this case, it’s
coming [INAUDIBLE]. PROFESSOR: So it’s
close to knapsack. But the difference
is, in knapsack, I have to decide, do I choose
this or do I ignore it. So, if I’d be like, if I
can only do a few things and I want to maximize
my score, then maybe I would choose, all right. This is easy. I’m going to do it. This is hard. Screw it. This is easy. I’m going to do it. So then my decisions are 0, 1. Pick or not pick. In this case, every
time my decision is a new state of my feet. So it’s not 0, 1. AUDIENCE: OK. PROFESSOR: That’s
the difference. And then, because
of that, the state is going to look different. And the recursion’s will
look a bit different. OK. So I want to know the
note that I’m landing at. I want to know
the sum of– well, we’ll see if I want to know
the sum of difficulties up to this point. And I want to know
one more thing, so. If this is going
to be my new state, and I know what note I’m landing
at, I’m making a decision. The decision tells me where
my feet are going to be. Right? The move decides where
my feet are going to be. What do I need to do? What else do I need to
know for my total solution? So what do I need to know to
consider between decisions? So say I’m considering the
state of– I’m at note two. Note two says, left right. And I’m considering
of coming here from note one, where my
foot position was up down. Or come here from
note one, where my foot position was left right. I need to know where
my foot position was, to choose between these, right? If I don’t know that,
then I can’t choose. AUDIENCE: That’s not
from your state, though? PROFESSOR: Not yet. It’s not here, so it’s
not part of my state. We’ve been talking about it a
lot, but we didn’t put it here. So let’s say that
the state is going to have the note
that I’m landing at. And my foot position
after landing. So, if I know that I’m
going to land like this, then I know where
I was here. l r. Say, l r. I can compute the
costs here, right? This is delta of going
from this to this. And this is the delta for
going from this to this. Can you see? Is that too small? Delta wants to know where
my feet were before. And where they’re
going to be now. So when I call it, I need
to know where I was before. And I need to know where
I’m going to be now. So this should be
part of my state. So our decision says, what’s
my new position going to be? So when I make a move, I
influence my new foot position. They’re going to
be in someplace. And independently of that,
the note– the position here– the position of the note,
increases all the time, right? Because time can
only go forwards. How are we going to account
for these extra moves? AUDIENCE: [INAUDIBLE]. PROFESSOR: So, we said that
between every two notes, we might want to
make one extra move. AUDIENCE: Like, a
potential new note in between your
destination note? PROFESSOR: Yep. AUDIENCE: And then just fill
in the difficulties for that and see which ones– PROFESSOR: So, if I want to use
the algorithm that I already have, that compares my
landing position to my note, to see whether I can go
there or not, what note would I want to put in that
intermediate note? So, you’re basically saying
that between every two notes, I’m going to have one more note. And my feet can
be wherever here. AUDIENCE: Oh. I mean, you’ll also
have the edge originally connecting them. So, you’d have it going
to the intermediate note, but also from the destination. Yeah, like that. You’d have to– PROFESSOR: So, what
note would I have here? AUDIENCE: It makes
you go to the center. PROFESSOR: Do I have
to be at the center? AUDIENCE: Well, you
can be anywhere. PROFESSOR: Yeah. So I’m going to
invent the blank note. That’s a big O. That means
you can do whatever you want. There are no constraints. So that is just an
intermediary state. So then I’m going
to take this input, and I’m going to add
these blank notes here. And these map to adding
notes in the graph. AUDIENCE: Well,
then, when you just run through your difficulty
function between each two notes and see if, for all the
potential moves, which one minimizes that path. PROFESSOR: Yep. So basically, I’m assuming
I don’t need this. I’m assuming that. This is going to
be where there’s at least one choice
where this is going to have the same cost
as a direct note. And then I’m going
to say that instead of having more complex
shapes in the graph, I’m going to insert
extra moves here. AUDIENCE: OK. I would think that, if you
have an intermediate move that might be less expensive,
you should, like, just hop to that new
position than to have an intermediate move, right? PROFESSOR: Yeah. And I’m going to assume that
either that’s not the case, or that I can always find
an intermediate move that makes my life better. AUDIENCE: Every case? PROFESSOR: Yeah. PROFESSOR: These
results do work. You’ll have to take my word
for it that this works. And this makes your
dynamic programming easy. And it makes your
graph building easy. So the advantage of this is
you’re changing the input. And then, when you’re
building your graph or when you’re doing
the DP, you only worry about an input
that looks like this. You don’t care about
any intermediate stuff. You have notes, and you have to
transition between the notes. Period. So we reduce the
complexity of the problem. So whenever you can get away
with that, it’s really nice. We can do that for centering. We might not be able to do
it for other more complicated stuff. OK. So, we sort of know
what we want in a state. Now we want to build a
graph, so that the path from some source
to some destination has a cost that’s equivalent to
the sum of these difficulties. Right? Because then I can
run the shortest path. And my solution
will be right there. I know. You guys seem awfully sad. Do you want to take a break
and play for a little bit more? Yes? How many people want
to play, instead of. You don’t have to play yourself. You can just rest for
these two or three minutes. And you can watch
someone else play. And get more intuition about
how you’re supposed to play. OK. So one person wants
to take a break. Everyone else wants
to keep going? Or are you guys
passed out already? AUDIENCE: Can we get out early? PROFESSOR: Sort of. Yeah. You’ll get out
three minutes early, if we don’t do another round. So who wants to keep going? AUDIENCE: No. Let’s play. PROFESSOR: OK. So who wants to keep going? You can only vote on one thing. Who wants to play? AUDIENCE: OK. AUDIENCE: Five. AUDIENCE: Four. AUDIENCE: Victor, go. PROFESSOR: OK. Who wants to go? So we decided what we’re
going to have in notes. And we’re going to
build a graph, where the notes are the states. And the edges are the moves. Right? So a note tells me, just
like there, what note I’m at. Say I’m at note two. And where my feet are on. So, left foot left. Right foot right. So, given a state, what
outgoing edges do I build? Where can I go to? So let’s say I have a state
that says I’m at note n and my left foot is
in some position. My right foot is
in some position. What are my outgoing
edges from here? AUDIENCE: Is there an
outgoing edge to every move? Because there’s a point. PROFESSOR: OK. Well, actually, the
blank is a note, right? So if the next note, if
note three’s a blank, then the note is a blank. And then I can have. AUDIENCE: I guess,
isn’t the difficulty of the move dependent on what
note that blank actually is? PROFESSOR: So, it doesn’t
depend on what the screen says. It depends on where my feet are. AUDIENCE: Oh, OK. I see. PROFESSOR: So I
have a number that tells me what’s on my screen. This number is
enough for me to know what’s going to be on my screen
from now on until forever. Because I have the
list ahead of time. And then I have the
position of my feet. So these are both
part of the state. So I have notes
for all the notes. And all the positions
of the feet. AUDIENCE: Right. But the blank note is
just one position of feet? PROFESSOR: No. AUDIENCE: Or, it’s
all positions. PROFESSOR: Yeah. AUDIENCE: Isn’t the
difficulty dependent on what position
your feet end up? PROFESSOR: Yeah. So it’s from where I
start to where I land. So, if I decide to start
from here, and go here, the difficulty of this move
is– so it doesn’t depend on whether I have a blank there. And this was OK. Or, if I had an up down,
then I just missed the note. But the difficulty, the effort
I’m expending, is the same. AUDIENCE: OK. But if you start from that
other move and go to a different position, that’s– PROFESSOR: If I go
from this to this, then that’s a
different difficulty. AUDIENCE: But it still
could be a blank note? PROFESSOR: Yeah. So, a blank note will let
me go wherever I want. AUDIENCE: I see. But there are different kinds
of blank notes, with different– I guess I’m confused
as to what– PROFESSOR: OK. So let’s go through them again. AUDIENCE: Is it kind of
like it’s, like, spreading, so really when you
have your source note, it’s actually connecting
to every possible move. And every possible move is
connecting to your next– so it’s kind of like a
diamond shaped thing? PROFESSOR: Not quite. Not quite. So, let’s go through
the notes again. And then let’s go through that. So the source move will be
connected to some notes. And then those notes will
be connected to other notes. And it looks more like you
have a big, outgoing degree. Then you have a big network. Then the big, incoming degree. It looks like a messed
up sorting network. So, notes are constraints. This accepts any possible
feet combination, right? So this accepts this. AUDIENCE: Is the
first combination contained in that note? In that blank note? PROFESSOR: No. The blank is a constraint. So, if I have a note that
looks like this, then if one of my feet is here and
the other one is in the center, then that’s fine. The constraint is met. If one of my feet is up
and the other one is down, then the constraint is met. AUDIENCE: But the edge
running into that blank note, depending on how your feet
land, is different difficulty. Is that right? PROFESSOR: Yep. But when I compute
the edge width, I need to know where
I’m landing exactly. Not just where the note
is because the note might admit multiple positions. AUDIENCE: I see. PROFESSOR: So this guy
admits all positions. AUDIENCE: OK. PROFESSOR: This guy admits
some positions, right? These are l r, l r. If I have up down, how many
feet positions does it admit? AUDIENCE: Just one. PROFESSOR: Not great. AUDIENCE: No. PROFESSOR: How many? AUDIENCE: As an intermediate? PROFESSOR: If it’s up down,
then it’s on the screen. My intermediates are all blank. AUDIENCE: Oh, oh. I thought you were
saying start with that. PROFESSOR: So up down. If you see up down
on the screen, how many feet positions? AUDIENCE: Left to right
what it could have. PROFESSOR: Yep. So, if the screen says up
down, the only two ways I can do that is this. Or this. Right? So, two positions. AUDIENCE: I see. AUDIENCE: Well, I mean, but
you could have intermediate where you step in the
first one, then back. PROFESSOR: But I don’t
care because I’ve added these blank notes. And they take care of
my intermediates for me. AUDIENCE: But so,
we’re saying where the feet land aren’t
part of the note. PROFESSOR: Nope. They’re just states. So they’re a
decision I’m making. AUDIENCE: So, do we
have the multiple– no, we don’t because they’re
not part of the– PROFESSOR: For each
note position here, for every position
in the screen thing, I have multiple feet
positions that I could be in. AUDIENCE: Right. Right. But then, are there multiple
moves to get to those? PROFESSOR: Yep. AUDIENCE: OK. So there’s multiple
moves connecting each. PROFESSOR: Yeah. So for example, if I want
to get to l r, up down here, I can go from l r,
up down in the blank. Or, I could have
l r be like this. And then transition. So I can have a lot of
possible foot positions that I’m transitioning
from in order to get here. AUDIENCE: But those
aren’t actually separate notes on the graph. PROFESSOR: They are. They have to be. So these all have to
be separate notes. Because the edges are going
to have separate weights. Right? This edge is going
to have one weight. This edge is going to
have another weight. AUDIENCE: OK. That’s what I thought. But then you said there
was only one blank. Don’t there have to be multiple
blank notes for every foot thing. If you’re approaching
a note from different– PROFESSOR: So, I’m not
sure what you’re asking. So, if you want to
care about centering, if you want to have
intermediate moves, you need one blank note
between every real note. So that you’re allowed to make
one intermediate move between. AUDIENCE: Right. I get that that’s talking
about the on the screen. PROFESSOR: Yeah. That’s the screen. AUDIENCE: That’s the screen. PROFESSOR: Yep. AUDIENCE: OK. So, that’s not
the graph, though. Here, we’re talking about
the screen on the graph. PROFESSOR: Here, we’re
talking about the graph. So two tells me that the
screen is at note two. Whatever that happens to be. And my feet are
in this position. OK. So that’s very important. Thanks for asking because
that’s very important. So, a state has the note
that I’m landing at. So, where the screen is. And where my feet are. AUDIENCE: OK. PROFESSOR: OK. AUDIENCE: The state corresponds
to the nodes that you’re on. PROFESSOR: A note. A note is a state. So, a note is a state. And a move goes
between two states. This is how we represent
all the graph problems. OK. AUDIENCE: So, you
need multiple blank. PROFESSOR: Yeah. So here, I’m just
drawing one example. Yeah. Yeah. So for example, here
I would need– sorry. Oh, OK. I get your confusion now. So, yeah. This would be one move. This would be another move. AUDIENCE: That’s all for a
single thing on the screen. PROFESSOR: Yep. AUDIENCE: OK. OK. That makes sense. AUDIENCE: So the next note
would have a really large end degree, right? I guess they always have– AUDIENCE: Well, no. It’d have lots of– PROFESSOR: So, this note
has a huge out degree. AUDIENCE: Yeah. But I’m saying the ones that all
those intermediates connect to. PROFESSOR: Yeah. AUDIENCE: So, then,
they would connect with some note that have,
like, really large degree. PROFESSOR: Yep. AUDIENCE: But there’s two
of them after that, right? Because there would
be two different– PROFESSOR: So, what’s next? Next, is position, hmm. How did U number them? I guess, crap. No. It’s not going to
match that, so. Whatever we do, it’s
not going to match that. Say the next note,
4, is just an up. 4 is up down. And then I have two
notes for it, right? Wild One note, l r. So this is note 4. That happens to be up down. And then I have this. And every one of these
connects to every one of these. AUDIENCE: If the
next move is up down, how can notes have down up? Oh, because you can
switch the feet. PROFESSOR: Yep. AUDIENCE: Oh. PROFESSOR: Yeah. So, I aimed to ask you guys, how
am I going to draw the edges? But you guys made me
do it with questions. So, suppose I met note n, l, r. What edges do I draw
going out of it? So, note n, left foot
at some position. Right foot at some position. What are my outgoing edges? AUDIENCE: This is a
note on the screen. Or– PROFESSOR: In the graph. AUDIENCE: –the new one
or intermediate one? PROFESSOR: Doesn’t matter. So, intermediate notes
have a note blank. AUDIENCE: That’s
just everything. PROFESSOR: It doesn’t matter. Yeah, we’re looking at all
of them at the same time. AUDIENCE: Wait, so
you’re asking what are– PROFESSOR: So, given this note,
who am I connecting it to? Let’s draw the outgoing edges. So, if you’re solving
this as a graph problem, you build the notes. You draw the edges. You’re on some algorithm. So let’s draw the edges. AUDIENCE: I think it depends
if you’re an intermediate note or not. PROFESSOR: Nope. So the note tells you
what your constraints are. And that covers
intermediate notes. If you’re note is a blank, then,
well, there’s no constraints. If the note is not a blank,
then there are constraints. AUDIENCE: Oh, note. I thought that was referring
to the note, not the– PROFESSOR: No. So this is a note. Maybe n is not good. Let’s use i, instead, then. If n is hard. So, i is the position
here, in this guy. Right? Say for example,
i equals 1 here. I equals 2 here. I equals 3 here. So and so forth. And that doesn’t match this, so. AUDIENCE: We’re
talking about note– PROFESSOR: Yep. AUDIENCE: –not– PROFESSOR: If one
note is represented by these three numbers, right? Each note has this tuple in it. AUDIENCE: Then i is the note. PROFESSOR: Yep. AUDIENCE: So i
connects to i plus 1. And then all
possibilities known. PROFESSOR: OK. So this connects to i plus 1. And then all possible
destinations, right? So I’m going to say left. This is after the jump. So, left after the jump,
and right after the jump. And this is for all
possible left after a jump, right after the jump. And lost a weight on this edge. AUDIENCE: The way
that it’s from– AUDIENCE: l r to AUDIENCE: –l r to l r. AUDIENCE: l j– l sub j r. AUDIENCE: l r. PROFESSOR: So you want to
say from l r to l j, r j. But what? AUDIENCE: Difficulty level? PROFESSOR: Yeah. Where is that? AUDIENCE: Your
difficulty function. PROFESSOR: Which is? AUDIENCE: Delta. PROFESSOR: Delta. So, yeah. The weight is delta. I drew d. Delta of these two
foot positions. Almost. If I want to minimize the
difficulty, then this is right. If I want to maximize
a score, then I would have to add a minus sign. But if you’re minimizing
the difficulty, this is exactly the way because
it maps the shortest path. Usually, in dynamic programming,
things are maximized. AUDIENCE: Wait, why would
you add a minus if it’s– PROFESSOR: So, if we’re
maximizing something, we have to flip– we have to
add a minus to the edge costs because– AUDIENCE: Right. PROFESSOR: Yeah. But this time we’re
minimizing something. AUDIENCE: Oh. Right, right, right. PROFESSOR: I promised you
that we’ll maximize something all the time. Well, I guess I lied. AUDIENCE: OK. Right, right, right. AUDIENCE: You don’t
want to maximize d. Then you’re dead. PROFESSOR: No. You want to maximize show offs. So if we have the
entertainment thing, then that would be maximized. And then you’d have minus. AUDIENCE: Then you’d
have everything you need. PROFESSOR: Yep. AUDIENCE: OK. PROFESSOR: OK, so
we’re almost good. Source notes and
destination notes. AUDIENCE: Well, I
guess source, we know that means
start in the middle. Right? Like, you would start off with– PROFESSOR: What’s the source? You want to start at
the first note, right? AUDIENCE: Yeah. PROFESSOR: But in
which position? AUDIENCE: Well, in
the center, right? I mean, the [INAUDIBLE] start. Or, I guess you could start– AUDIENCE: Wherever you want. AUDIENCE: Could you
add a source note going to a bunch of
intermediate notes? PROFESSOR: Yeah. Yeah. So what I’m going to do is I’m
going to say there is a note 0. That let’s me choose
how I’m going to start. AUDIENCE: Oh, it
could be any position. It’s like an
intermediate note itself. PROFESSOR: Yep. So I’m going to have a note
0, with all possible foot positions. And then this is going to
be connected to a source, by edges of weight 0. So the intuition is that I get
to choose my starting position, right? Starting position. I see the first note. I make a move. So I want to be able to
choose the starting position. That’s why I have
all those notes. And then make a move to
touch the first note. AUDIENCE: The starting
position is also a note. PROFESSOR: Yep. Because, if the
first note is here, I don’t necessarily
want to start like this because maybe this
is harder than this. All right. What’s the destination? AUDIENCE: The last note. PROFESSOR: OK. So, all the notes that are at
note n, and have any position, would be connected to
a destination note, using an edge of weight 0. Or I can consider
them as destinations. And then choose the destination
that has the shortest path. AUDIENCE: Oh, I see. The final destination is
going to be, like, two notes. Right? It’s going to be that
last position, and then– PROFESSOR: Or it
might be more than two if the note is
just a simple note. Because that wouldn’t
constrain my feet too much. OK. And last, last question. Dijkstra or Bellman-Ford? AUDIENCE: Bellman-Ford,
because you have negative edges,
negative weight, as if you were going
to maximize to death. PROFESSOR: So, this is always
going to be from 0 to 1. So I could possibly
use Dijkstra. The answer is neither. The answer is, we’re
building a DAG, so. AUDIENCE: Dijkstra. AUDIENCE: We don’t use that. PROFESSOR: DAG, shortest path. Every time we have
dynamic programming, DAG, shortest path. OK? AUDIENCE: Question. PROFESSOR: Yeah. Come on, last question. You can’t get away that easily. OK, so. Who wants to play?

Leave a Reply

Your email address will not be published. Required fields are marked *