[MUSIC PLAYING] BRIAN YU: OK, let's resume. Welcome back to CS50 Beyond, everyone. Hope you had a good lunch. So just as a recap,
this morning, we talked a little bit about Python and
Flask did a review of some of the features of Python,
looked at some new things that we didn't explore in CS50,
things like the input function, things like exception
handling and how to handle them, diving a little
more in detail into data structures, like dictionaries
and sets, and such. And then we took a look
at Python, or Flask, looking at building web
applications with variable routing and looking at how we can use that to
begin to build more interesting, more sophisticated web applications. This afternoon, we're going
to pick up where we left off, dive a little bit more into Python,
looking at some other language features, looking at recursion,
looking at object-oriented programming. We'll take a look at how to take a Flask
web application, which is right now just running locally on your
computer or in CS50 sandbox, or elsewhere, and actually
deploy it to the internet. We'll use Heroku, a service where, for
free, you can take a web application and deploy it to the internet so
that anyone can use it from anywhere. And finally, we'll conclude by taking a
look at another domain within computer science, that of
artificial intelligence, looking at how to write programs
that can make computers intelligent, and, in this case,
intelligently play games, although the algorithm that
we're going to use today, called Minimax, to
intelligently play a game is an algorithm that can
be applied to situations. More generally, whenever you need a
computer to be able to make decisions in situations where different
decisions can ultimately lead to different outcomes. So that's going to be the roadmap
for where we're going this afternoon. But before we do that,
what questions do you have? OK, with that, we'll go ahead and
take one look at a Flask feature that we didn't quite touch on, but
that is going to be ultimately useful. I've prepared a simple Flask application
right here that has two routes, a slash route-- that's just
a default indexed route-- and a slash more route that ends up
redirecting us to a more.html page. If I open up index.html, it's a pretty
simple website that just says hello. The background has been styled to be
blue via the style body background color blue there. And inside more.html, I've
done, basically, the same thing. The only difference is that there's some
text inside the body of the page that wasn't there in index.html. And so this is a situation
that came up in CS50, and I just want to
remind you of this, where it can often be helpful to do
what's called template inheritance. That more.html and index.html
share a lot of the same code. Almost all of it is the same. The only difference is what's
inside the body of the page. And so this can be a
common case where it would be useful to factor out the
common code into a file that's just called layout.html,
for instance, and then reference that file in the
index.html and more.html. So I demonstrate that very briefly
just so you get a refresher on that, so as you build Flask applications,
it's something at your disposal as well. So I'll create a new
file called layout.html, and it's going to look basically the
same as what the index page looks like. But the area where my pages
are different-- the header is the same, the title is
going to be the same, the styling is going to be the same. The only difference is in
the body of the web page. And here, I just want some custom block,
whereby in index.html and more.html, I can add code into that blocks. So I can say, OK, inside this block,
inside the body, I'm going to say, create a block that I'm
just going to call a body. But it could be called anything. It could be called main, or content,
or some other name for the block. And then end block, again, using
the curly braces and percent signs. It's typical [INAUDIBLE] syntax. And all I'm doing here is basically
saying, inside the body of this layout, that HTML page, is a
section where I'm going to insert code at some point in time. And so that means I can very easily
make some modifications to index.html to simplify this page dramatically. I can get rid of,
basically, all of the code, except for hello, which
I'm going to need. And I'll just say at the top, extends
layout.html, meaning take layout.html and use that as the starting
point for this HTML page. And the only thing that I need to change
is to say, OK, inside of block body, instead of it being empty, let
me just put the word hello there. And likewise, in more.html, I can do
the same thing, extend layout.html. And inside of block body, just say
more text, or whatever it might be. I've simplified both
index.html and more.html dramatically because all of the common
code is just inside of layout.html. So now, if I run this Flask
application by typing flask run, open up a web browser, you see
hello with the blue background. I go to slash more, you see the same
thing, also with the blue background. And that common code of the title,
the blue background, all of that is there because of that
shared template inheritance. So just wanted to demonstrate that
so you had an opportunity to see that in practice. Questions about template
inheritance before we move on? Yeah? AUDIENCE: When you wanted to change
the style of more, for instance, but then the style is
going to be [INAUDIBLE].. So how would you do that? BRIAN YU: Great question. So the question is, all right, in
layout.html, we've put some styling. We made the background color blue. What if I wanted to add
other styling to this page? Well, what you could do
is just add another block. Add a block, which I'll call
block style, for instance, and end block there. And you could then, inside of index.html
or more.html, add block style. And maybe for consistency, I'll
put block style up at the top. And you could add some code here. You could add, OK, I want the body
to have a font size of 24 pixels, or something like that, whereby
now, if I run this web application and go to slash more,
more text is larger. If I go to slash more, notice
the size of the text gets bigger. So I've been able to add style code
just by putting it in block style, and block style is just going to be
inserted right here inside of the web page. So you can add as many
blocks as you'd like in order to customize your layouts however
best fits your needs in the program. Other things? OK, so there are two Python-related,
or programming concepts, more generally, that I wanted to
talk about today before we move on, the first of which is recursion. So this is something that
we touched on briefly. If you took CS50 this past semester,
it came up briefly on the CS50 quiz. But recursion is this idea
of we can have functions, functions that are running code. But functions can also call themselves. We know that functions
can call other functions, but functions can call
themselves, oftentimes, to create some sort of useful effect. And so the function that
I'm going to write here is a function that's going to
calculate-- this the classic, one of the classic examples of recursion--
calculating the factorial of a number. So the factorial, I'll
just do some comments here. I'll do factorial.pi. If I had a number like 5 factorial, 5
factorial is equal to 5 times 4 times 3 times 2 times 1,
which is equal to 120. If I add something like 4 factorial,
that's 4 times 3 times 2 times 1, which is equal to 24. So a number factorial
is just that number times the number one less than it
times the number one less than it, so on and so forth,
up until you get to 1. You multiply that all
out, and the result is whatever you get as the
value of the factorial. And I would like to
write a function that calculates the factorial of some
number, some number n, for example. So I define a function
called factorial n. And the interesting
thing that I can do here is notice that 5 factorial is really
just 5 times 4 times 3 times 2 times 1. And this 4 times 3 times 2 times
1 is the same as just 4 factorial. And so the recursive idea that I can use
here is the factorial of some value n is going to be just n times
the factorial of n minus 1. I take the number and multiply
it by the factorial of the number one less than it. So 5 factorial becomes five
times the factorial of 4. And 4 is just 4 times
the factorial of 3. Now, what goes wrong if
I try and use this code? Something's not quite right about
it, although the idea is reasonable. Yeah? AUDIENCE: It breaks at one or minus one. BRIAN YU: Yeah. So it breaks, when I get down to
lower numbers, like factorial of 1. Because then I'll do 1 times
factorial of 0, and factorial of 0, by this logic, would be 0
times factorial of negative 1. And we're just going to keep going
into the negative numbers now and it's just never going to stop. So when I write a
recursive function, it's important to have what's called a base
case, some point at which this function is going to stop running. And so I could say something
like, OK, 1 factorial is just 1. So the simple way to do this-- as
there are multiple ways to do this-- is to say, all right, if n
equals 1, then just return 1. Because the factorial of 1 is just 1. And so I could do something
now and say, all right, I'll open up a Python
interpreter from factorial. Import the factorial function. And I can say, OK, what's
the factorial of 1? And it is, in fact, 1. And I can say, OK, what's
the factorial of 2? Well, that'll be 2 times the
factorial of 1, which is 2. Factorial of 3, factorial
of 4, factorial of 5, and we're getting the correct results
just by calling the function itself again, by recursively calling the
function on a smaller and smaller sized problem until we get down to a problem
the size 1, and then we've handled it. Now, this isn't quite perfect because
it doesn't handle factorial of 0, but you can make some
slight modifications to make it handle that as well. But that's the general
idea of recursion. And recursion is actually going
to come up later this afternoon, as we start to talk about
artificial intelligence, but it comes up more generally in
programming in many different cases. And in fact, if you go on
to take CS51, recursion is going to be a big
component of that course and thinking recursively and thinking
about how to write recursive functions. So just wanted to introduce that. Yes? AUDIENCE: Can you show what it looks
like if you forgot the base case but try to run it? BRIAN YU: Great question. What happens if you forget the base
case but try to run it anyways? We'll give that a shot. So if I didn't include
if n equals 1 return 1, and I just had return n
times factorial of n minus 1, I'll load up Python again. Say from factorial import factorial. This is that idea of importing
a function from a module that we talked about
earlier this morning. If I try and do
factorial of 5 right now, for instance, I'm going to get an error. I get a recursion error,
specifically which is that maximum recursion
depth has been exceeded. I've tried to call a function
on its own too many times. Python lets you call a recursive
function up to 1,000 times, and I have exceeded that because
this would go on infinitely if it would let me do so. So that is what happens if
you don't have a base case. If you ever see a recursion error, which
you might this afternoon if you choose to implement the artificial
intelligence algorithm, that's what you can expect to see. Questions about the idea of recursion? Yeah? AUDIENCE: With the line return
at times factorial minus 1, is that factorial function
already predefined? BRIAN YU: This factorial
function is not predefined. This factorial function
is just a name that is referencing the function itself. So this function, as
part of the way it works, is going to use itself
to try and calculate the answer to a smaller problem. AUDIENCE: So you don't really
need the thing in purple, right? The top line will still do the job? BRIAN YU: You don't need the thing in-- AUDIENCE: The last three lines,
you don't really need them, right? BRIAN YU: So you do
need these three lines, and the reason is this is handling the
logic of what the function is doing. So the first thing my
function is doing is checking to see if I've hit my base case. If I'm calculating the
factorial of 1, I'm just going to pre-program into my
function the answer to that is 1. But if I'm trying to calculate
the factorial of anything else-- presumably something larger
than 1-- but you should probably add checks to handle
things less than that, then to calculate the
factorial of 5, for example, I'm going to take the
number 5 and multiply it by whatever I would get by taking
the factorial of 4 of n minus 1. AUDIENCE: How does the computer know
what that factorial n minus 1 is? BRIAN YU: Good question. How does the computer know what
the factorial of n minus 1 is? It calls the function again. So now we're running
factorial one more time. We're calculating factorial of 4. That's not one 1. We're going to return 4
times the factorial of 3. So now, we're calculating
the factorial of 3, which is 3 times the factorial of 2,
which is 2 times the factorial of 1. and the factorial of 1, as these
if conditions on lines 9 and 6 will indicate, is just going to be 1. So it's a slightly
different way of thinking. It can be confusing to
reason about it first. It seems like I'm assuming
that the problem is solved and just using that in order to solve
the problem, which doesn't quite make sense sometimes. But if you try it on smaller examples,
you can sometimes get a sense for it. And hopefully, when we
get to the algorithm that we'll show later
this afternoon, that will help it make more sense as well. Other things? OK, so that's recursive programming. And one other programming model
or paradigm that I thought was probably worth demonstrating,
or at least showing, is the idea of object-oriented
programming, something that you might see in other languages,
as well, but that Python supports, and something that will
come in handy for us as we begin to deal with databases
and dealing with web applications that interact with data later on. And the idea of
object-oriented programming is that object-oriented programming
is a programming paradigm that's based on the idea of an object. And all an object is just
some structure in our code that's a combination of data that
we're storing about the object, and also some code that we
can run with the object. So it's a way of encapsulating
data and code together inside of one common unified structure. And so I'll give a
simple example of this. Maybe I want to define a way of
keeping track of coordinate points, so x and y-coordinate pairs. You could imagine that
I could just say, OK, x equals some value and
y equals some value, and then just manipulate
those x and y values together. But it would be nice to be
able to take those two values and encapsulate them inside
of a single structure. Now, we saw that we could
use a tuple to do this. I could say coordinates
equals x comma y. Coordinates equals x comma y. And now coordinates is
equal to 28 comma 50. So you can do that to encapsulate
the structure together. But as things get more
complicated as there becomes more and more pieces of data
that you like to associate with this. Maybe not just two fields,
but 10, or dozens of fields. And as you want to begin to
perform computations and operations on these coordinates,
this sort of programming can sometimes start to
get a bit difficult. And so object-oriented
programming is designed to make this a little bit easier. And so I'll create a new
file called points.pi. And I'm going to define
a new class called point. And you can think of a class
as just a new type of object that I'm allowing myself to create. So the string, for instance,
is a class that already exists and we've been able
to use and manipulate. The list, for instance, is another
example of a class, some type of thing that I can manipulate. And I'm creating a new class
called point that is just going to store x and y-coordinates. And so now, what I'm going to write is
what's called a constructor function. This will look a little
bit cryptic at first, but hopefully it'll become
clear in just a moment. The constructor function in Python,
by default, is called init, __init__, for initialize. And __init__ is going to take three
arguments-- we'll see why in a moment-- self, x, and y. Self is going to refer
to the object in question and x and y are going to
be arguments that we're going to provide when we
first create this point. And so I'll show you what this
function is going to look like. To create the point, I
want to update the object. Self is the name of this object. And I'm going to set a property of
it called x to be equal to whatever the argument is, just equal to x. And I'm going to say self.y equals y. So this looks a little bit
strange, probably unfamiliar if you haven't seen this
sort of syntax before. But what I've done is
I've created a class now that allows me to just
create point objects. And so to create a point object,
what I'm going to do is say p-- just some variable-- equals point. That's the name of the class. And then I'm going to provide
the x and y arguments to it. I'm going to say point-- the x-coordinate will be 10 and
the y-coordinate will be 20. And so just like that, I've been
able to create a point object, passing in 10 as the value of
x and 20 as the value of y. And I don't provide anything for self. Self is just this assumed
argument in the world of Python object-oriented programming
that just refers to the point that I have just created. So now, if I wanted to print out
the x-coordinate of this point, I could print out p.x. In Python objects, you use the dot
notation, something dot something else, to access a particular
property of that object. And I can print out p.y to print out the
y property of this particular object. And so now if I run this program, by
running Python points.pi, what I get is I get printed out 10 and then 20. Because it printed out
the x value of the point and then it printed out the y value
of the point, and both of them are stored inside of this
object that's just called p. So this is a very new way of
thinking about programming, a different way of thinking about
data, a different way of thinking about how to organize information
inside of our objects. Questions about any of this? Very new. Yeah? AUDIENCE: Were any visualization
functions gaps for self? Or is there any alternative
that you can write for self? BRIAN YU: Good question. The question is, does
this need to be self? I think, technically, it
could be something different, but the convention in
Python is to call it self. So generally best to call
it by its convention. Other things? Questions about this? Yeah? AUDIENCE: What is the __init__? BRIAN YU: __init__ stands
for initialization. This is basically, how
do I create a new point? And what I'm saying is
to create a new point, I need to provide two arguments,
an x and a y-coordinate. And I set the x value of
the point to be whatever that x argument is, and I
set the y value of the point to be whatever the y argument is. And I use this function here on line 8. When I create a new point
by saying point 10, 20, that's calling this __init__ function,
passing in the value of x and the value of y as 10 and 20. And I can show you this. If I add a print statement here,
I'll say creating a new point with coordinates x and y. So anytime I run this __init__ function,
it's going to say creating the new point with coordinates x and y,
such that now if I run this code, it says creating a new point
with coordinates 10 and 20. Because 10 and 20 were passed in as the
arguments to that __init__ function, and then it creates the point so that I
can then print out what the values of x and y actually are. Yeah? AUDIENCE: instead of saying "self,"
could you say "he" [INAUDIBLE]?? BRIAN YU: Yes. So someone else asked this a moment ago. Self is just the convention in Python. It's generally accepted as a way of
referring to the object in question. So when I say self.x, I am
modifying self, the object, and updating it to store some
additional data alongside it. And so there are other
things I can do here. I can add another
function, or what's called a method, in the world of
object-oriented programming called shift, for example. If I wanted to shift by a certain
x and y amount, like move the point to a different location,
then I would say, OK, self.x equals self.x
x plus however much I want to shift the x-coordinate by. And self.y equals
self.y plus however much I want to shift the y-coordinate by. And so now, if I were to
say something like p.shift, shift two in the x direction
and three in the y direction, and then print out x and y. Well, then what I'm going to get
is I'm going to get 12 and 23. So you look at that code
to see why it works. I'm calling the shift
method, which is just a fancy word for function in the
world of object-oriented programming, passing in 2 and 3 as the
arguments to that, x and y. And then I'm updating self.x and self.y,
the values stored inside of the object, to increment themselves by however
much I want to shift the point by. So this is the basic idea of
object-oriented programming. We're not going to use
this too much today, but we'll come back to it
in about two days time. I just wanted to introduce it now so
that when we see it in two days' time, it looks a little bit familiar. And we'll see how this become
very, very practical when we start dealing with
databases and dealing with SQL and having our Python code
interact with a SQL database without the help of a CS50
SQL library, for example. Questions about that before we move on? Yeah? AUDIENCE: Could you have built a
keyboard from the Tic-Tac-Toe thing as [INAUDIBLE]? BRIAN YU: Great question. Could you have designed the
Tic-Tac-Toe game board using a class instead of using the list of lists
that we were using this morning? Absolutely. And potentially, that might
be a better design for it as you think about the
different operations you might want to do with it. But yes. And you're welcome to try that, too,
if you'd like to, later this afternoon, if you want to try and use an
object in order to do that. Yeah? AUDIENCE: So because we
created the class there, do you need to use the self
documentation for future functions that you're going to write? BRIAN YU: Yeah. Any functions that are inside of this
class, or what we'll call methods, like the shift function, they all need
to take the self argument if they're going to operate on a specific point. Because the idea here is I
can have multiple points. I could create another
point called P2 and that could have different coordinates. And that point has its own
x value and its own y value, and those are manipulated separately. And so self.x is a way of saying this
object's x property, or this object's y property, as opposed to some
global x and y property that all of the objects share. They're specific to a particular object. Other things? All right. So we'll wrap up there for Python,
but I thought what we'd do now is take a look at how to
actually take a web application and deploy it to the internet. Right now, we've been running Flask
applications on our own computers locally by typing flask run,
and as soon as we quit Flask, the application stops running. It stops working. What we'd like to do with being able to
host our Flask web applications online on the internet, such that anyone can
access them, should they desire to. And there are a number of different
ways to do this, but one of the easiest happens to be a service called Heroku. Heroku offers a bunch
of different tiers, but there is a free tier that
allows you to upload and run a fast web application online for free. And that's the one we're
going to be exploring today. So a couple of steps. What I'm going to do is I'm going to try
and take the Tic-Tac-Toe example from earlier this morning. And this is one that's
not quite working yet. Yeah, this version doesn't
actually let you play, but we'll try and at least upload
it so you can see the board online. And we're going to take
this Flask application and we're going to prepare it for
Heroku and then deploy it to Heroku. And so I'll show you the
steps for doing that. The steps are also online
on CS50's documentation. And of course, this
lecture video will also be online later, too, if you want
to go back and reference that later. So the first thing I'm
going to do is Heroku requires a file called the Procfile
that basically just site decides, when I start running this application,
what exactly is going to happen. And so there are a lot of steps
that are going to be involved here. None of it is particularly necessarily
intellectually interesting, but it's good to get an understanding,
or at least get exposure to it, such that if you want to do
something like this in the future, it's available to you. But certainly don't feel like you
need to memorize this or anything. So inside the Procfile, I'm
going to add this line, which is going to look a little cryptic. I'm going to say web colon
gunicorn application colon app. OK. So what on earth is
going on with that line? Web, this is saying, OK, when
I'm going to launch this, I'd like to launch a web server. And what exactly should I do when
I try and launch the web server for this Heroku application? Well, I'm going to run gunicorn, which
is basically a web server program. Right now, we've been just
using a program called Flask as our web server, which has the same
name as the Python library called Flask. gunicorn tends to be a little bit more
stable, a little more robust, better for a production quality
program, if you're trying to deploy something
to the internet for people to use more globally. Application is the
name of the Python file from which I'm going to be
running the application from. So it's called application.pi. So I'm going to say application. And then app is the name of the
variable inside of application.pi that represents my Flask app. This word "app" corresponds
to the word "app," here on line 5, where I said, OK, create
a flask application and call it app. That name corresponds to
this name in the Procfile. So this is just instructions to Heroku
in a very succinct and sort of obscure way, saying when you
start up this application, run this server, gunicorn, from
an application, dot pi file, and run the web application
called app, basically telling the server what to do. The next file that I need is a
file called requirements.txt. requirements.txt is a file that's
going to contain dependencies. In other words, what things
does my server on Heroku need to install in
order for my application to be able to work correctly? You probably faced
similar issues when you were trying to run web applications
earlier this morning, where you needed to install
Flask and you needed to install Flask-Session in order
to get the application working on your own computer. Same thing is going to be
true of Heroku servers. So when you try and upload
a web application there, it needs to have the necessary
dependencies installed in order for the application to be able to work. So what are the requirements? Well, we need to
install Flask, for sure. We need to install
Flask-Session, for sure. And the third thing that
we need, in this case, is gunicorn, the name of the
web server that we're actually going to be using in order
to run this web application. So all right, I've created a Procfile,
created a requirements.txt file. All of this is just to
set up my application such that I can deploy it to Heroku now. Questions about what I've done so far? OK. Next step, there are a number of
ways to deploy something into Heroku. The easiest way is probably just
to deploy it from a git repository. So what I can do now
is go to github.com. Recall that we learned about
git and GitHub yesterday. I'm going to go ahead and
create a new repository. I'll call it Tic-Tac-Toe, and I'll
go in and create the repository. And now, I'm going to follow a
number of different steps here. It's telling me what commands I need to
run in order to set up my repository. So I need to run git __init__
in my Tic-Tac-Toe directory. git __init__ basically just sets
up this directory, this folder, as a Git repository that
I can then push somewhere. So all right, I've initialized a new Git
repository in my Tic-Tac-Toe directory. And now what I'd like to do is
set it up so that when I push, it's going to push to
this GitHub repository. And that's this command, git remote
add origin, basically just saying, remember that origin is
where on GitHub am I going to push my code to when I run git push. So I'm going to copy that
command, paste that in there. I've added the origin, saying
I'm going to push to GitHub. And now, I'm going to add all
my code to the Git repository. I'm going to say git add dot to say, add
everything in this current directory. I'm going to commit these files. So say, prepare to deploy to
Heroku is what I've just done. And now I'm going to push, git push. And I'm probably going to
get a message that says, all right, I need to
specify where to push to. I'm going to push to the
master branch, just the default branch of the repository. So I push that code to my Git
repository, so far all things that we've seen from yesterday. If I refresh this page, my
application.pi, templates directory, Procfile file, requirements.txt,
they're all located now inside of my Git repository. And now, I just need to
tell them my Heroku account to launch a web application that's
based on this Git repository. So I'll now go to heroku.com. And I mentioned an email
near the beginning of class, that you should sign
up for Heroku accounts. You're welcome to do
so, if you'd like to, in order to experiment with
this type of thing on your own. I'm going to go to the upper right,
click on New, and say Create New App. I want to create a brand
new web application. I need to give it a name. I'll call it brian-tictactoe. Hopefully, nobody's taken that name. All right, it's available. Great. We'll create that app. And OK, I've created a new Heroku app. And now, the next step I need to do
is link it to my GitHub repository so it's actually pulling
the code from GitHub. So under Deployment Method-- again, there are a number of different
ways to deploy the application. The one we're going to explore
today is deploying from GitHub. So I'm going to click on GitHub. And if you're doing
this for the first time, you probably need to authorize it on
GitHub's end, maybe log into GitHub and click Authorize to approve
Heroku talking to GitHub for you. And then it says, connect to GitHub. Find a repository. The name of my repository
is Tic-Tac-Toe. I'll go ahead and search for that. All right, here's the repository. I'm going to click
Connect, which is going to link that GitHub repository
to this Heroku application that I'm deploying to the internet. So I click Connect there. And great, now it's connected. And now, if I want to,
I also have this thing called Automatic Deploys,
where you can say anytime someone pushes to the
master branch, automatically redeploy the application so that
the version online matches whatever is on the master branch. And this can be very powerful because it
means that any time you make a change, you can update the version
online just by typing git push, push into the master branch. And Heroku will automatically
do the deployment. This also makes it very important that
the master branch is a working branch. And so again, if you're trying
features, experimental things, things that might break, always
a good idea to experiment on a separate branch. And only when you feel
confident about it, merge it back into master, which
will trigger the automatic deploy. So I'll go ahead and enable
Automatic Deploy here. So anytime I push to master,
it will automatically deploy. You can also manually deploy. Say, all right, I'd like to deploy this
application from the master branch. And I'll go ahead and
click Deploy Branch. And we'll see if this works. Hopefully, it works. You can see it's installing Python. It's installing pip. In a moment, it's going to try and
install my dependencies, so things like Flask and Flask-Session, which
are the different dependencies I defined in requirements.txt. And then it's going to try
and start up my application. Questions about anything
while this is running? I see some green smiley faces. Great. All right, it's launched
the web application. It's given me a URL. If I take this URL, copy
it, go to a new page, this is brian-tictactoe.herokuapp.com. Press Return, and all right, great. Tic-Tac-Toe shows up
deployed on the internet. And if you all go to that same URL,
you can all see it now as well. If I make changes to it,
push it to the master branch, it will also deploy online there, too. So I've been able to successfully deploy
a Flask application to the internet by Heroku. Questions about that? Yeah? AUDIENCE: So does gunicorn just
understand the Flask syntax and treats it as its own? Because you said it's from
Flask or more dependable. BRIAN YU: Yeah, good question. So gunicorn is just a separate
server application that's designed to sort of
launch web servers and it understands how to take
a Flask application and actually serve it to
handle incoming requests. Other things? Julie do you have something? AUDIENCE: Do you have a particular
domain [INAUDIBLE] that you look up? BRIAN YU: Oh, good question. So it's about the domain. If you look up at the top right now,
I'm at brian-tictactoe.herokuapp.com. brian-tictactoe was the name
of the app that I gave it to that just happened to be available. Herokuapp.com is just the
default name for where these applications are hosted. But maybe you would like to host
your website somewhere else, at like, briantictactoe.com, for
instance, or some domain that you've purchased that you'd like to connect. So the way you can do that
is by Heroku Settings. The first thing you'll need to do
is actually purchase the domain, and there are a number of services
via which you can do that. But once you own it, if you go to
the Settings of your application, here in Heroku's control panel, you can
just add a domain to the application. And if you just click that
Add Domain button there, that will allow you to then connect
that domain to the web application on Heroku. You'll have to do a little
bit of configuration that Heroku's website
will guide you through, but it will then allow you to connect
some domain to the application that's running on Heroku. Yeah? AUDIENCE: So if someone typed in
brian-tictactoe.herokuapp.com, even after you connected the domain,
will it still be [INAUDIBLE]?? BRIAN YU: Good question. If someone went back to
brian-tictactoe.herokuapp.com, would it still work? Yes, it probably would. Yeah? AUDIENCE: What's the file
extension for Procfile? BRIAN YU: No file
extension for the Procfile. Just capital P, Procfile. No extension necessary there. Other things? All right, so that's deploying a
web application to the internet. You can do this with Flask applications. You can do it with other
applications as well. When we go into building React
applications later on in the week, you can do the same thing there. So as you build any of your
applications this week, if you'd like to give deploying into
the internet a try, or even applications you build after this class or outside
of this class, feel free to do so, and these steps should help you
get up and running with that. Other questions about Heroku and
deploying our web application that way? Yeah? AUDIENCE: Do you think that Heroku is
better than the GitHub for hosting? BRIAN YU: Oh, good question. So the question's about GitHub
hosting service, GitHub Pages. So GitHub Pages is used
for serving static sites. For those of you who took
CS50 this past semester, you might remember problem
set 5 home page, wherein you were able to create, basically,
an HTML CSS web page for yourself, about yourself, or something
you're interested in. And then if you wanted
to, we gave you an option to deploy that to the internet. And we did that by GitHub Pages,
which is a service built into GitHub. It's free. And it basically lets you take a
repository and turn it into a web page that GitHub will host for free. That works only for
static pages, pages that are just static HTML CSS JavaScript. But it doesn't work for if you're
trying to run a web server, so something like the Tic-Tac-Toe
game that we have that has some backend server,
where you're making requests to a server that's processing
results and rendering templates. You can't run a Flask app off
of GitHub Pages, for example. So Heroku is a little bit
more flexible, in that sense, in that you can deploy static sites. You can also deploy dynamic sites
that have the sort of interactivity that you might want, that have
a server that you can talk to, that have a database, for instance,
whereas GitHub Pages can't quite do that. Yeah? AUDIENCE: For the
requirements.txt, do you need to add into that every library
that you're using in your Python code? BRIAN YU: Good question. So yeah, in requirements.txt,
you're going to need to include in
it any library that you have installed into your Python code. So if you're using
some external library, you're going to need to include
that in requirements.txt. Otherwise, Heroku's not going to be able
to know that it needs to install that and you're probably going to get
a Module Not Found Import Error type of thing when you try
to deploy the application. And if you try and deploy
it and something goes wrong, which does happen from
time to time with Heroku, you can always go to
the logs, which show you the errors that have
happened as you were working on trying to deploy the application. And those errors can
often help you get guided to what it is that you need to
change or fix to get it working. All right, other things? OK, then we'll change
gears here a little bit and move away from web programming,
just for a little time, in order to talk about the world
of artificial intelligence. So we've been making a Tic-Tac-Toe
game so far this morning. So far, you've probably
implemented, hopefully, the ability for a user to make
a move, or at least an ability to update the board based on the move. Maybe you've gotten around to
implementing, checking whether or not someone's won the game or
the ability to reset a game. But what we'd like to
do now is not just allow humans to play against other
humans, but to allow a human to play against some artificial
intelligence that is able to behave in some sort of intelligent way. And so what we're going
to do this afternoon is explore one algorithm
called Minimax that is particularly useful
for two-player games, especially, wherein both players
are trying to compete for differing outcomes and players
need to each make moves based on choosing among the
available moves that are there. And so we have here a Tic-Tac-Toe board. And that Tic-Tac-Toe
board we can really divide into three possible
outcomes of what can happen at the end of a Tic-Tac-Toe game. Either X wins the game or O wins
the game or nobody wins the game. And so those are the three
possible resulting states. And of course, there are many
ways to get to those outcomes. There are many ways X can win, many ways
O can win, many ways nobody can win. But those are the three
possible outcomes. And what we're going to do is to
make this into a computational-- you put this in computational
terms, mathematical terms that a computer can understand. We're going to assign each of
these possible outcomes a score. So if X wins, we're going to
say that board has a score of 1. And if O wins, we're going to
say that board has a score of 0, or a negative 1, sorry. And if nobody wins, tie game, we're
going to say that has a score of 0, doesn't favor one player or the other. So now, if you are a computer
trying to play moves for X, what are you trying to do to the score? Are you trying to maximize the
score or minimize the score? Yeah, you want to maximize
the possible score. If you have an option between
a situation that will take you to a score of negative 1 and a situation
that will take you to a score of 1, you're going to pick the one
that takes you to the score of 1 because that's the one
that maximizes your score. And if you're the O player, you're
going to want to do the opposite. You're going to want to
try to minimize the score, because if you're choosing
between these three options, you want to choose the board
that has the minimum score. And so ultimately, in
this game, X is going to be trying to maximize
the score and O is going to be trying to minimize the score. And what the Minimax
algorithm is going to do is it's a recursive algorithm
that's going to figure out, what is the move that
maximizes the score or what is the move that
minimizes the score? Questions so far, generally
speaking, about where we're going and what we're doing? All right. We'll take a look at this. So we have a board that
looks something like this. This is a game that's still in play. It's O's turn and the
game is still happening. So nobody's won just yet. But what is the score of this board? If you're the O player, what
is the score of the board? So think about that for a little bit. Nobody's won just yet, but what
would you say the score of this board would be if you're O and
you're trying to win? Remember, O is trying
to minimize the score. If X wins, it's a score of 1. If O wins, it's a score of negative 1. If nobody wins, it's a score of 0. OK, I hear people saying 0. Why 0? Someone tell me, why
is this a score of 0? What is the logic you went through
to mentally get at the idea that this is a score of 0? Yeah? AUDIENCE: If it's O's turn, O
is going to block X [INAUDIBLE].. BRIAN YU: OK, great. So if it's O's turn, O is going to block
X, playing in the upper right corner. And in that case, X has to
play in that top middle square. And in that case, nobody
wins and the score is 0. Now, of course, O didn't have
to play in the upper right. O could have played in the
top middle, in which case X played in the upper right, and
then X would have won the game and that board has a score of 1. And so what was the logic here? We had two possible options, one
option that led us to a board with a score of 1, X winning, and
one option that led us to a board with a score of 0, nobody winning. And between the two,
we know that O should choose the option that's
going to minimize, choose the one with the score of
0, play in the upper right, block X from winning the game. So let's formalize that a little bit. What are the possible
moves that X can make-- or that O could make, for instance? Well, O could play in the top middle
or O could play in the top right. Those are the two possible
options for what O can do. And all right, let's explore what
happens in each of those options. If O plays in the top middle,
then where does X play? Well, only one option left. X is going to play in the top right. X is going to win that game. And so what score will
we give to this board? AUDIENCE: 1. BRIAN YU: 1. Great. That board has a score of 1. And so what about the
score of this board? If this board needs to have a score, and
the only thing that can result from it is something with a score of 1, what
score would you give this board? Great, also 1. Because once you get to this position,
you're going to get to this position, and this board has a score of 1. So this board must
also have a score of 1. So now, let's explore the side. O plays in the upper right. When that happens, X plays in the
only available square, the top middle. And what scored does this board have? 0, great. Nobody won that game so that board has a
score of 0, which means this board has? AUDIENCE: 0. BRIAN YU: Great, also a score of 0. And so now, we get to what we
could call the minimization step. We know that O has two
options, one board that leads to a score of 1, 1 board
that leads to a score of 0. What should happen? Well, it's going to pick the one
that has the score of 0, which means this board also has a score of 0. That's the basic idea of what the
Minimax algorithm is going to do. It's going to explore those
possibilities, calculate the scores, and when it sees that
it has multiple options, it's going to ask itself, which of those
options is going to minimize the score, for the O player, at least,
and then choose that option. Questions so far? All right. Oh, green smiley faces. Wonderful. Let's try something a
little bit more complicated. We've got this board now. This board, it's X's turn. And what is the score of
this board if it's X's turn? AUDIENCE: 1. BRIAN YU: 1, great. Why? So why is it a score of 1. AUDIENCE: X can win. BRIAN YU: X can win right away. X can play in the upper right-hand
corner and X is going to win this game. But how would a computer know that? How would a computer be
able to figure that out? Well first, it needs to
consider the possible moves. Well, X could play in the lower left. A computer doesn't know that it
shouldn't play in the lower left. So it needs to explore that possibility. X plays in the lower left. OK, what can O do next? Well, O can play there in
the top middle, in which case X plays in the top right. And all right, X won there. So what score would you give this board? 1, great. So this board also has a score of 1. But O didn't have to play in there. O could play in the top right, in
which case X plays in the top middle, and this board has a score of 0. Nobody wins, which means this
board also has a score of 0. And so now, here's the interesting step. The Minimax algorithm is
recursive, in the sense that when X is trying to make a
decision about what move to make there, it needs to think about
what moves should O make if O ends up in this board? And if O ends up in this board,
well, between the options of 0 and 1, O is going to try to minimize the score. So O is going to say, all
right, this is the board that gives me the minimum score, so I
should play in the upper right corner. And so that board also has a score of 0. So in other words, if X chooses
to play in the lower left, then if both players
are playing optimally, that game is going to be tied. And we're able to
calculate that recursively by thinking, what would O do? What would X do? Move after move after move. All right, so X plays in the lower left. That results in a score of 0. What else could X do? X could play in the top middle. But what happens then? What's the score of this board? AUDIENCE: Negative 1. BRIAN YU: Negative 1, great. Because what are the possible options? O could play in the lower left, winning
immediately, a score of negative 1. Or O could play in the
upper right and that would result in a tied game, a score
of 0, which means a score of 0 up here. But that means that if O
gets into this position and is trying to minimize the
score, between 0 and negative 1, O is always going to pick this option,
the option that minimizes the score. So that board has a score
of negative 1 as well. And then, of course, the final
one, the one that all of you probably saw immediately,
obviously and intuitively, but that a computer doesn't have any
way of having some intuition about, needs to explore the
possible options first, is just to say, all right, in
the upper right, in that case, X has won the game. That has a score of 1. And so between those
three options, the option of a score of 0, negative
1, and 1, we should choose the option that maximizes the score. We should play in the upper right. And so that board up at the top,
we can conclude, has a score of 1. So a lot of calculation to get to
what was intuition for us, the idea that board up top has a score of 1. And we can get at that by
recursively calculating. What's the best move in this position? What's the best move after that? Questions? Yeah? AUDIENCE: So are you using
recursion on, like, two functions? If you're going to
implement it, do you have-- do you have like X's best position
and then [INAUDIBLE] that position, and then [INAUDIBLE] the X function
to call O for the next step? BRIAN YU: Yeah, good question. So the question's about
actually implementing this. We'll take a look at some
pseudocode in a moment. But generally speaking, there are
a couple ways you could do this. You could have two different
functions, one that's doing maximizing, one that's doing minimizing. But the code is really, very similar. So what you probably want to do is have
a function that's going to optimize and one of the arguments,
maybe a Boolean flag that says, should I maximize this or
should I minimize this? And if I'm maximizing it, then when
I consider the next player's moves, I'm going to say, OK,
try and minimize it now. And if I'm currently trying
to minimize my score, when I'm considering
my opponent's moves, I'll say, OK, what should happen
if you try to maximize that score? So it just sort of flips back and
forth, one move after another, if you go between one
player's turn and the other. Other Questions? Yeah? AUDIENCE: I'm assuming there's
situations where the next step is two equally good options. How are the [? AIGs, ?] in that case? BRIAN YU: Yeah, good question. What happens if there are two equally
good options, two options that both have the same score? In that case, the [? I ?]
doesn't really care. You can pick the first one. You can pick a random one. You can pick whatever you want. So certainly, that's
something you could do. Now, there are ways you can make
modifications to the scoring system. It all really boils down to what
the scoring system is, whereby right now, winning is a score
of 1 for X. Losing for X is a score of negative
1, and 0 is neutral. You can imagine a
situation where you would give more points for winning faster,
where if you can win in fewer moves, then you should prefer that. Right now, this algorithm doesn't
care about how quickly you win. So even if there are
two in a row, if you have some other way of guaranteeing
that you'll win the game, you might do something else instead. And the algorithm could very reasonably
choose that, and that's to be expected. But if you want to make it so
that if you can win faster, you'll win faster, than
you want to encode, somewhere in the scoring
system, some notion of if you're winning in fewer
moves, that's preferable. Other things, questions? How do we feel about the general
idea of what this algorithm is doing? OK, some green, some yellow. Happy to slow down and take
questions if there are any. Otherwise, we can definitely chat
about this during project time, too. All right, let's take a look at
actually some of the pseudocode, some code we could
actually write in order to implement an algorithm like this. So we're going to do Python-like code. This isn't exact code, so don't
try and type this into Python and expect it to work. But this will give you the general
idea of what we're trying to do. We're trying to Minimax a particular
game based on whose turn it is. So the first thing we need to
know is, if the game is over, if someone's already won the game, then
just return the score for the game. If no moves are possible,
someone's already won the game, then the score is finalized. There is no option, no
decision points to be made. The game is over. So there already is a score. That's our base case for when
the game's over that's going to, ultimately, have some sort of score. But then we need to
say, all right, we need to figure out what the available
moves are for the game. In the case of Tic-Tac-Toe, that's
as simple as just looking for, what are the empty squares? But it's important to just
look for the empty squares because you don't want to
consider moving into places that are illegal moves, moves that
there already is an X or an O there, for instance. You want to consider only the
available moves for the game. And then we'll say, OK, if it's
X's turn, what should we do? If it's X's turn, we want
to maximize the score. And so if we want to
maximize the score, we should start by assuming that the
value is as small as possible. So we're going to set the value to
be negative infinity, for instance, or negative some really big number. And then we're going to say,
OK, for every possible move, let's consider that possible move. The new value of this board is going
to be the maximum of the current value, which starts out as negative infinity,
and whatever the score of the board would be for if you were to make
that move and it were O's turn. So this is the real critical piece of
the logic, these last two lines here, the idea that for every
possible move that X can make, let's consider, what would
the score of that move be if you were to make that
move and then let O play? Let 0 play optimally and see
what the score of that would be. Take all of those scores and
take the maximum of all of them, because X wants to maximize
the total possible score. I'll say that again because I
know it's little bit confusing. We start by assuming the value is
really, really low, because we're trying to maximize the score. We want to increase the score. And then consider all the possible
moves we can make and take the maximum of the value of
all those possible moves. And how do we figure out the
value of those possible moves? Well, we recursively call
the Minimax algorithm again, considering the game board with
that move having been made, and then say, it's O's
turn now and O is going to try and do something a
little bit different, which we'll see in just a moment. Because now else, if it's O's turn,
0 is going to do the exact opposite. It's trying to minimize the score. So let's start by assuming the
value is really, really high, some really, really big thing. And then for every possible
move, the value of this position is the minimum of all of the
possible moves that you could make, and then assuming that
it's X's turn to move. And so these functions will
recursively call each other. First, it'll be X's turn. Then it'll consider Minimax,
where it's O's turn. And that will consider situations where
it's X's turn, going down and down and down and down, considering
all possible options to be able to play optimally. Now, this works for a
game like Tic-Tac-Toe, but is not going to work as well if
you consider more complex games, where there are more possible moves. If you try and do this on a
game like chess, for instance, the algorithm is just
going to take ages in order to figure out the optimal move. And so to be able to
play games like that, you need to employ some
more advanced techniques. But this is probably
one of the simpler ways to think about how to pick the best
move out of a set of possible moves. Then at the end, you return the value. In other words, what is
the score of this board? That will tell you the ultimate
score of the board, whether it's a winning board, a losing board, or a
neutral board, in which nobody can win. This algorithm will just give
you the score of the board. Is it a win for X, win
for O, or nobody wins? If you wanted to get
the actual best move you should make, then what you care
about is, which of these moves, in this list of moves, is going
to produce the maximum score? And you can think about
adding a little bit of logic there in order to keep track of what
the best possible move so far is, such that you can then later use that move in
order to figure out what move to make. Questions? Yeah? AUDIENCE: Does value have
to be negative or positive? Because couldn't it just be negative
1 or negative 2 or postive 2? BRIAN YU: Good question. So the question is, couldn't value
just being negative 2 or positive 2, or even negative 1 and 1? In the case of Tic-Tac-Toe,
yes, where in this game, scores are ranging from negative 1 to 1. You can imagine, though, that
if you were to generalize this to other games, where
scores could be higher or lower, that the maximum and
minimum scores could be beyond that. For Tic-Tac-Toe, though, absolutely. If we're only considering score
within the range of negative 1 to 1, you can use negative 1 and 1
in place of negative infinity and positive infinity. Yeah? AUDIENCE: Wouldn't you get error
message because you can never really reach infinity, so that
would count for infinity? BRIAN YU: Oh, good question. Wouldn't you get some
kind of error message if you tried to encode
infinity into the program? What exactly is happening there? An excellent question. While you can't actually have an
infinity, Python, and many languages, have a value that can
sort of simulate infinity. In Python, it's inside
the Map library, and I think it's called map.inf for infinity. It's just a value that
represents the idea of infinity. And it obeys mathematical properties. So if I say, is math.inf
greater than 28? Well, yeah, true. math.inf
is greater than 28 because infinity is bigger
than any conceivable number. But if I take the minimum of 50 and
math.inf, that's going to give me 50. Because if you try and take the
minimum of 50 and an infinite number, 50 is the smaller one
between the two of them. So math.inf is a value you can use
to stand in for infinity, at least in Python, and that will behave
the way you would expect infinity to behave, for instance. Questions about any of that? Yeah? AUDIENCE: [INAUDIBLE]. BRIAN YU: Yeah. So the idea here is that
if I am the X player and I'm trying to maximize the score,
I care about which of my possible moves is going to maximize my score. So imagine for a moment that-- let's just open up a text editor. So if I have three possible
moves, one of which leads me to a score of 0, one of
which leads me to a score of 0, and one of which leads
me to a score of 1, if I start off with a
value of negative infinity, the first thing I'm
going to do is say, let me consider the first move,
the move that has a score of 0. And value is going to be set to-- I'm trying to maximize my score-- the maximum of the current
value, negative infinity, and 0. And the maximum of negative
infinity and 0 with 0, because 0 is bigger than negative infinity. Now, I consider the second move. Well, value is going to be the
maximum of 0, the current score, and the new score is 0. And OK, there is no difference. It doesn't matter whether I pick
the first move or the second move, so the value of this is 0. And then finally, I consider the
last move that has a score of 1. So this is going to be max of 0 and 1. And between those two,
the maximum of those is 1. So ultimately, this
tells me that I should be choosing the last move
because that's the one that's going to maximize the score. So if I just keep taking the max over
all of the possible moves I can make, eventually, I'll end up with the
maximum possible score that I can have. Good question. Yeah? AUDIENCE: So if you're writing
[INAUDIBLE] or something bit more complicated, you're
also going to have to take into account
multiple scenarios where you can end up with a score--
you'd end up with a score of 1. You'd need some way to
decide between them. BRIAN YU: Good question. Yes, you ultimately need some
way to decide between if you have multiple things of the same score. Likely, however you choose to implement
that will have some ways by default, going to handle that situation. Maybe you're just taking the
first one or the last one is probably going to be
the most common situation. The algorithm doesn't really
care which of those you pick. Yeah? AUDIENCE: What method describe
this algorithm [INAUDIBLE]?? BRIAN YU: Good question. So what makes this
artificial intelligence instead of just brute force? This is just a brute force search. But artificial intelligence
is generally described as just the ability of machines
to be able to make decisions that we would consider to be intelligent
decisions, intelligent or smart decisions. And this is an example of what we
might call a search algorithm, which is one of the basic algorithms
used in AI, this idea of trying to search through a
space of possible moves to figure out what the
best possible move is. And of course, this
is probably just only scratching the surface of what
artificial intelligence is really about. Then you later can get into more
sophisticated search algorithms, get into heuristics and other
algorithms, like A star, and so forth. There are more ways to make this
even more efficient, instead of just searching everything. This is just giving you
a little bit of a taste. If you're interested in
artificial intelligence, this stuff seems cool to you
and you'd like to do more of it, if you're a student here
at Harvard, I'd highly recommend CS182, the
artificial intelligence class, which begins with stuff
like this and dives in and goes even further into
looking at how to program even more sophisticated artificial intelligence. I'm happy to chat with you more
about that during project time, if you'd like. But this is just scratching
the surface, in short. Other things? OK, well with our remaining time, I
thought I'd propose a couple of things that you can try to do. So let's continue working
on our Tic-Tac-Toe projects. If you're still working
on making moves and being able to detect whether
someone's won the game, feel free to keep working on that. But then consider adding
some additional features. Add the ability to reset
the game, for instance. If you're looking for something a
little bit sort of intermediate step to be able to do, consider adding
move history, keeping track of the history of the move that you
make, such that you can undo a move, for instance. And if you're really feeling up to
the challenge-- this is going to be, I will warn, a little bit
challenging, especially at first-- if you really are up for it,
try and implement a button like let the computer
make a move for me that is going to play the optimal
move in a given situation. So you can think about how
you can do that as well. If you'd like to add to
the game in other ways, you're welcome to do that, too. I'll show you what a finished
product might look like. Certainly, you can feel free to
play with the styling of things in order to make things
look a little nicer. I'll go ahead and run
Tic-Tac-Toe, too, and go here. All right, I've got a
Tic-Tac-Toe game, whereby the X player can play a move
somewhere and the O player can play a move somewhere. And if the O player decides, OK
wait, I didn't like that move, you might consider adding an Undue
move button that just undoes that move. And maybe that Undue move
button can work multiple times, such that if I get to this position
and X wants to undo their move, you can click Undo again, get
back to the starting position. And you can also consider adding
situations where if X goes here and O goes here, what should X do
in order to win the game? Anyone know, in a situation like
this, what the optimal move for X is? AUDIENCE: Playing in a corner. BRIAN YU: Playing in a corner. Yeah, probably. So we'll let the computer make a move. And all right, it played in the corner. I can try to block. I'll play here. I'll let the computer
make the next move. All right, it moved there. And now, there's really no way
for O to win at this point. I can try playing here, but
let the computer make a move. And OK, X has won this game. So a lot of possible features
you have to implement. You definitely don't have to do the
Minimax AI step if you don't want to, because it is a little
bit involved, but thought I'd introduce the algorithm so you
can try it, if you would like to. But we'll open it up. It's flexible. Feel free to try any of these. If you have a project of your own
in mind that you'd like to work on, feel free to work on that, too. And what I think we'll do is
we'll take the middle section. If you're in the front
half of the middle section, go ahead and go to room 136. If you're in the back half of the
middle section, go to room 212. And we'll have the two
section on the side stay in the auditorium for the time being. We'll work on project time between now. Feel free to work until
around 5:00 or so. The staff will be here till 5:00,
and we'll reconvene here tomorrow at 10:00 AM for a look at JavaScript.
