This two-part course introduces the basic mathematical and programming principles that underlie much of Computer Science. Understanding these principles is crucial to the process of creating efficient and well-structured solutions for computational problems. To get hands-on experience working with these concepts, we will use the Python programming language. The main focus of the class will be weekly mini-projects that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 2 of this course, the programming portion of the class will focus on concepts such as recursion, assertions, and invariants. The mathematical portion of the class will focus on searching, sorting, and recursive data structures. Upon completing this course, you will have a solid foundation in the principles of computation and programming. This will prepare you for the next course in the specialization, which will begin to introduce a structured approach to developing and analyzing algorithms. Developing such algorithmic thinking skills will be critical to writing large scale software and solving real world computational problems.
Mini-project Video
Loading...
來自 Rice University 的課程
Principles of Computing (Part 2)
251 個評分
從本節課中
Trees
This week, we will explain the importance of trees. We will also explore how to set up game trees so that we can efficiently search them.
與講師見面
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[MUSIC]
This week, we're going to play Tic-Tac-Toe again, all right?
We're going to revisit the game, because it's a simple game,
and it's interesting to see how different strategies operate, all right?
Instead of using Monte Carlo methods like we did
before, however, we're going to use Minimax, all right?
And, for this particular game, I would expect Minimax to perform better.
Why?
Because we're going to be able to search the entire
game tree here to find the best possible movie
that we can make, whereas in Monte Carlo, we
were approximating that by running a bunch of trials, okay?
And in other games, this might not be the case, it might not be possible to
search the entire tree, it might be difficult
to come up with a good scoring function.
So don't take this to mean that it's always better
to use Minimax, but we do want you to see
the sort of tradeoffs and the differences between, you know,
building a Monte Carlo player and building a Minimax player.
So let's think about how we're going to build a Minimax player for Tic-Tac-Toe.
So, let's revisit the game tree for Tic-Tac-Toe here.
Now, the first thing that I want to point out is, when you run Minimax, you're
not actually going to build a game tree, but you are going to search it, all right?
So if we start up here.
The current state of the game.
The way that we're going to search is
we're actually going to use a depth first search.
So you've already seen breath first search, but we're going to do depth first.
OK, and what that means is you're going to look at each of the options at each level.
And you're going to go here, all right.
Then you're going to look at that and you're going to go here.
OK, I'm done.
Then I move the other path.
Okay and I go all the way down to the bottom.
And then I pop all the way back up, right?
So from that, from the bottom here we're going to go all the way back up.
And then I'm going to go down the next one, all right?
Then I'm going to go this branch, this branch, this branch,
then again I'm going to go all the way back up.
And then finally I'm going to go here.
Here, here, here.
Okay, and that is a depth first search.
And the question is how do you accomplish this?
Well we could go back and we could take
our code from you know a previous project where
we did depth for or breadth first search and
we could try and modify to be depth first.
Right.
Well there's actually an easier way here, all right?
If we use recursion this just falls out naturally, all right.
So what happens when I use recursion, all right.
If I try to use recursion to search this tree what I'm going
to do is I'm going to start with the current board state, all right.
So.
So I have the current board state here, all right,
and I'm going to look at all the possible moves, all right?
So I'm going to have a loop inside my Minimax function that looks, what are the
possible moves I can make right now, and
for each possible move, you call Minimax, all right?
You make that move on the board, you call Minimax.
So I'm going to call Minimax on this, and Minimax is going to return me a score.
And you know, a move that you should make at that position as well.
All right, so it returns me a score.
And then I call Minimax on the next one, that one returns me a score.
And then I call Minimax on the next one, and that returns me a score.
And since on that I'm maximizing level, I take the maximum of all those
scores and that's the move I should mak,e which everyone has the max, all right?
And we've seen different ways of taking the max.
We've seen how to do recursion and now hopefully you understand a little bit
about trees and you can see that what I'm going to have to do here.
All right, and this is going to happen again at each level.
All right, your recursive function isn't going to do anything magic, all right?
Over here, this just becomes the starting state of the board.
All right, and so what you're going to do is to look
at all the possible moves, and you're going to call Minimax here.
And you're going to call Minimax here, and each of those are going to return a score.
Now you happen to be at a minimizing level at this point, all right?
So your going to want to take the mid, all right?
That's the only real difference here, okay?
So what we're going to pass to Minimax is a board and the player, and we're going to
implicitly use the player to determine whether or not
we're in a minimizing or a maximizing level, all right?
You want to use the scores again, where you know, X is.
You know, it gets positive scores, O gets negative scores, okay?
And so if we're at an x level, we want to
maximize, if we're at an o level we want to minimize, okay?
And you can actually do that not by
maximizing and minimizing, you can actually multiply, all right.
If you're, you know, player X, multiply by, you know, plus one.
If you're player O, multiply by minus one, all right?
And by doing that you can just always maximize, all right?
If you multiply all the scores by minus one
when you're O, you just maximized those, those scores.
So, you multiply by yourself, effectively, and then maximize always.
Okay, but you could switch back and forth and say,
If I'm X, maximize, if I'm playing for O, minimize.
That's not a problem, all right?
But, effectively, this is the idea here.
We're going to do this depth-first search on this tree.
We're going to do it using recursion.
Okay when, and we're not going to actually build the tree.
Let's look at the template that we're providing here.
The first thing I want to do is draw your attention
to the fact that we're increasing the timeout in CodeSkulptor.
Why are we doing that?
Well, this can be quite slow, the tree gets pretty
big, especially when you start from the empty board, okay?
There's a big tree to search, it can take awhile, all right?
And on the machines that I've looked at it takes about 20 to 30 seconds.
Now if your implementation isn't as fast as ours or
efficient as ours, all right, it could even take longer.
So don't feel bad if you have to increase that
time out there, at least while you're working on your program.
However, consequence of this, don't test your program using the empty board, okay?
That's the worst thing you can do, because that takes the longest, all right.
You want to test your board, your, your function
with boards that are partially filled in, okay?
Things go much faster from the second move onward, okay?
So you want to partially fill in a board and you want to
test from there and take a lot less time, all right.
And you'll be much happier, trust me, okay?
All right, the next thing.
Okay, we've hard coded the scores here.
Now player X gets a score of one, so if X wins the game he gets a score of one.
If O wins the game she gets a score of minus one, all right?
And that implicitly means when you're playing X
you're maximizing, when you're playing O you're minimizing, okay?
So don't modify this, just use these numbers as they are.
Now you're writing the mm move function, mm move takes two arguments.
It takes a board which is the current board and
it takes the player who is supposed to move next, okay.
And what it returns is both a score, and a move, right?
A move that's going to get that score, Okay?
And that score is either the maximum, or minimum
depending on who you're up, who you're playing, right?
If you're playing player X you're going to return the maximum score
you can get, and the move that get's that maximum score.
If you're playing play, player O, you return the minimum score you
can get, and the move that you know, get's that score OK.
Now there are some boards however.
The, you know there is no move.
Well, how can that be?
If the game is over, you're just going to score it, you're
going to give it a minus one a zero, or a one.
And in that cases you have no move to return, so let's just move the
convention here, that in that case you're going to
return that move minus one minus one, okay?
All right?
Now, we have some additional stuff in the template here, okay?
We want to be able to use exactly the
same infrastructure that we used for the Monte Carlo tic
tac toe player, but if you remember, the Monte
Carlo tic tac toe player had a different interface, okay?
First of all, it took a board, a player, and a number of trials,.
And second of all it just returned the mood it didn't return the score okay.
So we have to sort of have this wrapper function okay.
Instead of trying to make our our our Minimax
move behave exactly the same we're going to have this thing
called move wrapper, that looks like the Monte Carlo
function board player number of trials, and returns a move.
And what it does is it actually calls your Minimax player,
okay, inside, and returns the move that your Minimax player returned, okay?
This allows us to use exactly the same code we
used before to run the Monte Carlo player, all right?
So don't modify that Move wrapper.
You can uncomment and play.
And one thing I will caution you again, Don't uncomment that
and try to play with Player x as the first player.
All right?
Or as the machine player.
Right?
If you do that, okay, you're going to incur that very long delay, all right?
Waiting for that first move to happen.
And so when you hit run, it's just going to sit there for, you know,
30 seconds or whatever while you're Minimax
player's trying to decide where to play X.
And there's just a couple more things that I would like to point
out about your minimize players here, okay and the first is as follows.
I know the score is always going to be one zero or minus one, no matter what.
So that means if I'm in a maximizing layer, as soon as I find.
A move that would return, that returns a square of
one, I know I can't do any better, all right?
And so there's no point in checking the other moves to see if,
if you know, are there other ways that I can win the game, right?
You already found a way that you can win the game.
You can return that move and that score
immediately, and this will speed up your player significantly.
Similarly, if you're playing for O, and
you're minimizing and you ever going to score
a minus one back, you know immediately, hey, this is the best I can do.
I may as well return a score of minus
one and whatever move gets me that score, okay?
This is important.
If you don't do this, your player's going to be significantly slower, all right?
Another thing that I want to point out is not, you know, the
way in which you search the moves is now going to matter, as well.
If I'm not going to search all of them there might be,
you know, particular squares on the board that's it's better to search first.
And if you search those first you're more likely to find a win.
And, you know, this early termination condition
would kick in sooner making things faster.
So you might want to experiment with the
ways in which you search the moves, all right,
but don't do that until you actually have a
working player but do do the early termination, okay.
Right from the start.
That'll make things much faster.
It'll make it much easier for you to work on the project and debug things.
In this week's mini project, we're really bringing together a whole
bunch of different concepts that we've taught in this course, all right?
You're going to have to find the maximum and find the minimum, all right?
That was a theme early on, and where we showed you a bunch of different
ways of doing that, and we did it again, and again, and again, all right?
We're going to use recursion, okay?
And so you're going to have to be
comfortable with recursion and how it works,
This is a more complicated recursive function
than we've had you build in the past.
We're going to search, all right?
Now before we had you search using breath first search and now
we're using depth first search but
basically the concepts are similar, all right?
So you're seeing different ways of actually searching.
In order to help you do that we're going to introduce trees this week, okay?
Because the game tree here is what we're searching,
as opposed to the grid that we searched before, okay?
And, finally, you're building a player for Tic-Tac-Toe again, right?
And we've already done that.
So now, this allows you to see some of the tradeoffs involved, right?
This week, you're not really going to have to write a large number of lines of code.
Rather, this week, I want you to focus on Thinking.
I want you to think about how all of these concepts are coming together.
And I want you to think about how you
can use them to build an efficient Minimax Tic-Tac-Toe player.
And you can also think about why you know this Tic-Tac-Toe
player might be better or worse than the other Tic-Tac-Toe player.
And how you might go about thinking about which version you might choose
if you were trying to play, build a machine player for other games.
Okay, right, so I hope you have fun this week and
I hope you enjoy playing your game, once you've built it.
Although [LAUGH] it might not be that much fun,
because you're not actually going to be able to win.
