Object-Oriented Programming and AI - CS50 Beyond 2019

Key Takeaways

[Music] okay let's resume welcome back to cs50 beyond everyone I hope you had a good lunch suggest as a recap this morning we talked a little bit about Python and FASTA to review 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 looking at 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 gonna 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 will 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 gonna use today called minimax to intelligently play a game is an algorithm that can even 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 gonna be the roadmap for where we're going this afternoon but before we do that what questions you have okay 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 index route and a slash more route that ends up redirecting us to a more dot 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 dot 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 just want to remind you of this where often be helpful to do what's called template inheritance that more dot HTML and index dot HTML share a lot of the same code almost all of it this 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 dot HTML for instance and then reference that file in indexed of HTML and more data HTML so I'll demonstrate that very briefly just so you get a refresher on that so if you build flask applications and something at your disposal as well so I'll create a new file called layout dot HTML and it's gonna 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 gonna be the same the styling is gonna 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 data HTML I can add code into that block so I can say okay inside this block inside the body I'm going to say create a block that I'm just gonna call 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 % this typical Jinja 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 dot HTML meaning take layout at 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 dot HTML I can do the same thing extend layout at HTML and inside of block body just say more text or whatever it might be I've simplified both index.html and more than HTML dramatically because all of the common code is just inside of layout that HTML so now if I run this flask application by typing flask run open up a web browser you see hello with the blue back 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 of template inheritance so just wanted to demonstrate that so that you had an opportunity to see that in practice questions about template or inheritance before we move on yeah great question so the question is all right in layout dot 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 like add a block which I'll call a block style for instance and and block there and you could then inside of index dot HTML and more dot HTML add block style and maybe for consistency up a block style up at the top and you could add some code here you could add okay 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 okay 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 functions going to calculate this the classic one of the classic examples of recursion calculating the factorial of a number so the factorial do some comment here will do effect 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 had something like 4 factorial that's 4 times 3 times 2 times 1 which is equal to 24 so a number of factorial is just that number times the number 1 less than 8 times the number 1 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 if 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 amuse 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 1 less than it so 5 factorial becomes 5 times the factorial of 4 and 4 is this 4 times the factorial of 3 now what goes wrong if I try and use this code something's not quite right about it all of the ideas reasonable yeah yeah so it breaks when I get down to lower numbers like factorial of 1 because then I'll do 1 times factorial of zero and factorial of 0 by this logic would be 0 times factorial of negative 1 and we're just gonna 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 is there multiple ways to do this to say alright if N equals 1 then just return 1 if the factorial of 1 is just 1 and so I could do something now and say alright I'll open up a Python interpreter from factorial import the factorial function and I can say okay what's the factorial of one and it is in fact one and I can say okay what's the factorial of two well that'll be two times the factorial of 1 which is two factorial of 3 factorial for 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 size problem until we get down to a problem of size 1 and then we've handled it now this isn't quite perfect as it doesn't handle factorial of zero 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 cs50 one 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 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 load of 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 gonna 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 but sub byte on its own too many times Python lets you call a recursive function up to a thousand times and I've 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 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 do you don't need the thing in you 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 one I'm just going to pre-program into my function the answer to that is one but if I'm trying to calculate the factorial of anything else presumably something larger than one but you should probably add checks to handle things less than that then to calculate the factorial of 5 for example I'm gonna take the number 5 and multiply it by whatever I would get by taking the factorial of 4 of n minus 1 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 and we're calculating the factorial of 4 that's not 1 so we're gonna return 4 times the factorial of 3 so now we're calculating the factorial 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 5 & 6 will indicate is just going to be 1 so it's a different slightly different way of thinking it can be confusing to reason about at 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 some 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 make it make more sense as well other things okay 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 you might see in other languages as well but the 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 is just some structure in our code that's a combination of data that were worrying 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 sort of common unified structure and so I'll give a simple example of this maybe I want to define a way of keeping track of like coordinate points so x and y coordinate pairs you could imagine that I could just say okay 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 like coordinates equals X comma Y coordinates equals X comma Y and now coordinate is equal to 28 comma 50 so you can do that to encapsulate this structure together but as things get more complicated as they become more and more pieces of data that you like to associate with this maybe not just two fields but ten or dozens of fields and if you want to begin to perform computation some 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 gonna 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 it's a class that already exists if we've been able to use the manipulate the list for existence is another example of a class some type of thing that I can manipulate and I'm creating a new class called point that's 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 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 underscore underscore init underscore underscore 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 gonna look like to create the point I want to update the 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 dot 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 gonna 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 gonna say okay 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 it 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 like okay the x coordinate of this point I could print out px 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 dot Y to print out the Y property of this particular object and so now if I run this program by running Python points top I what I get is I get printed out 10 and then 20 because I 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 different way of thinking about how to organize information inside of our objects questions about any of this very new yeah 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 itself so generally best to follow that convention other things questions about this yeah in it 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 eight 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 that 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 yeah someone else asked us 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 I'm when I say self dot 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 say I can add another function or what's called a method in the world of object-oriented programming called like shift for example if I wanted to shift by a certain X&Y amount like move the point to a different location then I would say ok self dot x equals self dot X plus however much I want to shift the x coordinate by and self dot y equals self dot y plus however much I want to shift the y coordinate by and so now if I were to say something like P dot shift shift by shift to in the X direction and 3 in the Y direction and then print out x + 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 two and three as the arguments to that X&Y and then I'm updating self dot X and self dot Y the values stored inside of the object to increment themselves by however much I want to shift the point by it 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 sequel and having our Python code interact with the sequel database without the help of cs50 sequel library for example the questions about that before we move on yeah 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 a object in order to do that yeah yeah any functions that are inside of this class or what we call methods like the shift function they all need to take the self argument if they're going to operate on the a specific point because the idea here is I could have multiple points I could create another point call it 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 dot X is a way of saying this objects X property or this objects Y property as opposed to some global X&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 what I thought we'd do now is take a look at how to actually take a web application and deploy it to the Internet such that 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 and stops working what we'd like to do with be 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 flask 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 I think this version 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 gonna 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 proc file the basically just decide 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 need to feel like you need to memorize this or anything so inside the proc file I'm gonna add this line which is gonna look a little little cryptic but I'm gonna say web : g unicorn application : app okay so what on earth is going on with that line web is just it's saying okay when I'm gonna 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 G unicorn 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 G unicorn 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 by PI so I'm going to say application and then app is the name of the variable inside of application that 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 proc file so this is just instructions to Heroku in a very succinct and sort of obscure way saying alright when you start up this application run the server J unicorn it's from an application the 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 text requirements that text 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 face 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 server 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 a flask session for sure and the third thing that we need in this case is a unicorn the name of the web server that we're actually going to be using in order to run this web application it's alright I've created a proc file creator 2 requirements dot text 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 to 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 gonna go ahead and create a new repository I'll call it Tic Tac Toe and I'll go ahead and create the repository and now I'm gonna follow a number of different steps here it's telling me what commands need to run in order to set up my repository so I need to run get in it in my tic-tac-toe directory get in it basically just sets up this directory this folder as a git repository that I can then push somewhere so alright I've initialized the 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 little 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 get repository I'm going to say git add dot to say add everything in this current directory I'm gonna commit these file is a so say prepare to deploy to Heroku is what I've just done and now I'm going to push get push and I'm probably gonna get a message that says alright I need to say specify where to push to I'm gonna push to the master branch just the default branch of the repository so I pushed that code to Myra gate repository so far all things that we've seen from yesterday if i refresh this page okay my application up I templates directory proc file requirements no text 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 gate repository so I'll now go to Heroku comm 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 gonna go to the upper right click on new and say create new app and I want to create a brand new web application I need to give it a name I'll call it Brian - tic-tac-toe hopefully nobody's taking that name alright it's available great will create that out 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 that'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 gonna click on github and if you're doing this for the first time you'll probably need to authorize it on github then maybe login to github and click authorize to approve Heroku talking to github for you and then it says there I 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 gonna click connect which is going to link that github repository to this Heroku application that I'm deploying to the internet so I'll click connect to there and right great now it's connected and now if I want to I also have this thing called automatic deploy isn't 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 pushing to 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 in the master which will trigger the automatic deploy so I'll go ahead and enable automatic deploys here so anytime I pushed a 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 this 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 and requirements text 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 new page this is brian tic-tac-toe Heroku opcom 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 to the masker branch it will also deploy online there too so I've been able to successfully deploy a flask application to the internet via Heroku questions about that yeah yeah good question Shoji unicorn is just a separate server application that's designed to sort of launch web servers then it understands how to take a flask application and actually serve it to handle incoming requests other things Julian company oh good question so it's about the domain if you look up at the top right now I'm at Brian - tick-tack-toe Heroku opcom Brian - tick-tack-toe was the name of the app that I gave it to that just happened to be available Heroku opcom is just the default name for where these applications are hosted but maybe you would like to host your website somewhere else that like Brian Tic Tac Toe comm for instance or some domain that you've purchased that you'd like to connect so the way you can do that is via 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 this 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 is website will guide you through but it will then allow you to connect some domain to the application that's running on Heroku yeah a good question if someone went back - Brian - techno tower girl calm would have still work yes it probably would yeah no file extension for the proc file just capital P proc file 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 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 application if 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 oh good question so the questions 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 problems at five 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 a 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 webpage 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 back-end server where you're making requests to a server that's processing results in 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 sentence 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 good question so yeah in requirements text you're going to need to include it in 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 requirement text otherwise Heroku is not going to be able to know that it needs to install that and you're probably going to get a like 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 will 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 we is so far you've probably implemented it 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 and 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 a lot of 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 gonna 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 right either X wins the game or a wins the game or nobody wins the game and so those are the three possible resulting saves 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 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 someone gets if X wins we're gonna say that board has a score of 1 and if a wins we're gonna say that board has a score of 0 or a negative 1 sorry and if nobody wins tie game we're gonna say that as a score of 0 doesn't favor one player or the other and so we're getting so now if you are a computer trying to play moves for X what are you trying to do to the score you're 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 gonna 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 Oh play err you're gonna want to do the opposite you're gonna 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 gonna figure out what is the move the maximizes the score or what is the move that minimizes to score questions so far generally speaking about where we're going or 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 still in play it's always turned and the game is still happening so nobody's won just yet but what is the score of this board if you're the Oh play err 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 oh and you're trying to win remember o is trying to minimize the score if X wins is the score of 1 if a wins is the score of negative 1 if nobody wins score of 0 ok P hear people saying 0 y 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 ok great so if it's turn o is gonna 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 Oh 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 1x winning and one option that led us to a board with a score of 0 nobody winning and between the two we know that oh should choose the option that's going to minimize the score 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 could play in the top middle or could play in the top right those are the two possible options for what do and all right let's explore what happens in each of those options if a plays in the top middle then where does X play well only one option left X is gonna play in the top right X is going to win that game and so what score will be give to this board one 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 of 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 this side Oh plays in the upper right when that happens X plays in the only available square the top middle and what score does this board have 0 great nobody won that game so that board has a score of 0 which means this board has great also a score of 0 and so now we get to what we would call the minimization step we know that o has two options one board that leads to a score of 1 one 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 so let's try out green smiley faces wonderful let's try something a little bit more complicated we've got this board now this board is X's turn and what is the score of this board if it's X's turn one great Y so when y why is it a score of 1 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 it first needs to consider the possible moves all right 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 I do next Willow can play Oh can play there in the top middle in which case X plays in the top right and all right X 1 there so what score would you give this board 1 great so this board also has a score of 1 but Oh didn't have to play in there Oh 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 is 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 move should oh make if ONS up in this board and if oh end up in this board well between the options of 0 & 1 always going to try to minimize the score so always going to say alright 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 I do what would X do move after move after move all right so X plays in the lower left that results in the 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 negative 1 great because what are the possible options o could play in the lower-left winning immediately 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 the score of 0 up here but that means if Oh gets into this position and it's trying to minimize the score between 0 and negative 1 oh 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 something to ition about needs to explore the possible options first is just to say alright in the upper right in that case X is 1 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 which are playing the upper right and to 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 that board up top has a score of 1 and we get at that by recursively calculating what's the best move in this position what's the best move after that questions yeah yeah good question so the question is about like 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 is maybe a boolean flag says should I maximize this or should I minimize this and if I'm maximizing it then when I consider the next players moves I'm gonna say okay try and minimize it now and if I'm currently trying to minimize my score what I'm considering my opponent's moves I'll say okay what should happen if you try to maximize that score so it just sort of flips back and forth one move after another as you go between one player's turn and the other other questions yeah 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 could make modifications to this 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 4 acts as a score of negative 1 and 0 is neutral you could imagine a situation where you would give more points for winning faster where if you can win in fewer moves and you should prefer that right now this algorithm doesn't care about how quickly you win a 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 then 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 okay some green some yellow happy to slow down and take questions if there are any otherwise we can definitely chat about that steering project time - 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 gonna do like Python Lite code this isn't exact codes I 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 minimize a particular game based on whose turn it is so the first thing we need to know is all right if the game is over if someone's already won the game then just return the score for the game right if no moves are possible someone's already won the game then the score is finalized there's no option no decision points to be made the game is over so that already is a score that's sort of 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 gonna set the value to be like negative infinity for instance or negative some really big number and then we're gonna 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 always turn so this is the real critical piece of the logic these last two lines here the idea that ok 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 a play let a play optimally and see what the score of that would be take all of those score and take the maximum of all of them because X wants to maximize the total possible score say that again it's a 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 ok it's always turn now and always going to try and do something a little bit different which we'll see in just a moment because now else if it's always turn o is going to do the exact opposite it's trying to minimize the score so let's start by assuming the value was 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 is turned to move and so these functions will sort of recursively call each other first it'll be X's turn then we'll consider minimax where it's au turn and that will consider situations where 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 they're in more possible moves if you try and do this on game like 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'll tell you the ultimate score 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 like is it a win for X win 400 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 good question in the cases so the question is like couldn't value just be negative 2 or positive 2 or even negative 1 and 1 in the case of tic-tac-toe yes where the score is only in this game where rate scores are ranging from negative 1 to 1 you can imagine though that if you were to generalize this to other names where scores could be higher or lower that you would that the maximum and minimum scores could be beyond that for tic-tac-toe though absolutely if we're only considering score than the range of negative 1 to 1 you can use negative 1 & 1 in place of negative infinity and positive infinity yeah oh good question would didn't you get some kind of error message if you tried to like encode infinity into the program like what exactly is happening there an excellent question well 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 math library and I think it's called math dot int for infinity it's just a value that represents the idea of infinity and it obeys mathematical properties so if I say like is math on infinity greater than 28 oh yeah true mouth on infinity is greater than 28 because infinity is bigger than any conceivable number but if I take like the minimum of 50 and math on infinity 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 map dot int 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 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 I I'll just open up a text editor so if I have three possible moves one of which leads me to a score of zero one of which leads me to a score of zero and one of which leads me to a score of one if Mike if I start off with a value of negative infinity the first thing I'm going to do is say all right let me consider the first move the move that has a score of zero and value is going to be set to I'm trying to maximize my score the maximum of the current value negative infinity and zero and the maximum of negative infinity and 0 is 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's no difference it doesn't matter whether I think the first mover 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 though yeah good question yes you'll 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 weights by default going to handle that situation like 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 good question so what makes this artificial intelligence instead of just brute force this is just a brute-force search but artificial intelligence was 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 then 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 algorithm to 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 if 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 CS 182 the artificial intelligence class which begins with stuff like this and dives in and goes even further and 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 okay 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 add 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 like move history keeping track of the history of the moves that you make such that you can like 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 the 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 it's alright 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 decide okay wait I didn't like that move you might consider adding an undo move button that just undoes that move and maybe that undo 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 okay if X goes here and ogos 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 playing in a corner yeah probably so we'll let the computer make a movement and I write it played in the corner I can try and block up light here I'll let the computer make the next move alright and move there and now there's really no way for a win at this point I can try playing here but let the computer make a move and okay X is 1 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 I 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 sections 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 a.m. for a look at JavaScript