[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.