1 00:00:00,000 --> 00:00:00,980 2 00:00:00,980 --> 00:00:03,920 [MUSIC PLAYING] 3 00:00:03,920 --> 00:00:12,260 4 00:00:12,260 --> 00:00:14,810 BRIAN YU: OK, let's resume. 5 00:00:14,810 --> 00:00:16,770 Welcome back to CS50 Beyond, everyone. 6 00:00:16,770 --> 00:00:18,050 Hope you had a good lunch. 7 00:00:18,050 --> 00:00:20,337 So just as a recap, this morning, we talked 8 00:00:20,337 --> 00:00:22,670 a little bit about Python and Flask did a review of some 9 00:00:22,670 --> 00:00:24,836 of the features of Python, looked at some new things 10 00:00:24,836 --> 00:00:27,481 that we didn't explore in CS50, things like the input function, 11 00:00:27,481 --> 00:00:29,480 things like exception handling and how to handle 12 00:00:29,480 --> 00:00:31,430 them, diving a little more in detail into data 13 00:00:31,430 --> 00:00:33,860 structures, like dictionaries and sets, and such. 14 00:00:33,860 --> 00:00:36,410 And then we took a look at Python, or Flask, 15 00:00:36,410 --> 00:00:39,260 looking at building web applications with variable routing 16 00:00:39,260 --> 00:00:42,710 and looking at how we can use that to begin to build more interesting, more 17 00:00:42,710 --> 00:00:44,115 sophisticated web applications. 18 00:00:44,115 --> 00:00:46,490 This afternoon, we're going to pick up where we left off, 19 00:00:46,490 --> 00:00:49,240 dive a little bit more into Python, looking at some other language 20 00:00:49,240 --> 00:00:52,804 features, looking at recursion, looking at object-oriented programming. 21 00:00:52,804 --> 00:00:55,970 We'll take a look at how to take a Flask web application, which is right now 22 00:00:55,970 --> 00:00:58,712 just running locally on your computer or in CS50 sandbox, 23 00:00:58,712 --> 00:01:00,920 or elsewhere, and actually deploy it to the internet. 24 00:01:00,920 --> 00:01:04,254 We'll use Heroku, a service where, for free, you can take a web application 25 00:01:04,254 --> 00:01:07,170 and deploy it to the internet so that anyone can use it from anywhere. 26 00:01:07,170 --> 00:01:10,700 And finally, we'll conclude by taking a look at another domain within computer 27 00:01:10,700 --> 00:01:12,710 science, that of artificial intelligence, 28 00:01:12,710 --> 00:01:15,650 looking at how to write programs that can make computers intelligent, 29 00:01:15,650 --> 00:01:17,484 and, in this case, intelligently play games, 30 00:01:17,484 --> 00:01:19,691 although the algorithm that we're going to use today, 31 00:01:19,691 --> 00:01:21,650 called Minimax, to intelligently play a game 32 00:01:21,650 --> 00:01:24,429 is an algorithm that can be applied to situations. 33 00:01:24,429 --> 00:01:27,470 More generally, whenever you need a computer to be able to make decisions 34 00:01:27,470 --> 00:01:29,990 in situations where different decisions can ultimately 35 00:01:29,990 --> 00:01:31,116 lead to different outcomes. 36 00:01:31,116 --> 00:01:34,073 So that's going to be the roadmap for where we're going this afternoon. 37 00:01:34,073 --> 00:01:36,420 But before we do that, what questions do you have? 38 00:01:36,420 --> 00:01:39,730 39 00:01:39,730 --> 00:01:44,120 OK, with that, we'll go ahead and take one look at a Flask feature 40 00:01:44,120 --> 00:01:47,390 that we didn't quite touch on, but that is going to be ultimately useful. 41 00:01:47,390 --> 00:01:51,540 I've prepared a simple Flask application right here that has two routes, 42 00:01:51,540 --> 00:01:53,900 a slash route-- that's just a default indexed route-- 43 00:01:53,900 --> 00:01:58,910 and a slash more route that ends up redirecting us to a more.html page. 44 00:01:58,910 --> 00:02:03,290 If I open up index.html, it's a pretty simple website that just says hello. 45 00:02:03,290 --> 00:02:06,680 The background has been styled to be blue via the style body background 46 00:02:06,680 --> 00:02:08,810 color blue there. 47 00:02:08,810 --> 00:02:12,350 And inside more.html, I've done, basically, the same thing. 48 00:02:12,350 --> 00:02:15,950 The only difference is that there's some text inside the body of the page that 49 00:02:15,950 --> 00:02:18,620 wasn't there in index.html. 50 00:02:18,620 --> 00:02:20,927 And so this is a situation that came up in CS50, 51 00:02:20,927 --> 00:02:22,760 and I just want to remind you of this, where 52 00:02:22,760 --> 00:02:26,810 it can often be helpful to do what's called template inheritance. 53 00:02:26,810 --> 00:02:31,070 That more.html and index.html share a lot of the same code. 54 00:02:31,070 --> 00:02:32,370 Almost all of it is the same. 55 00:02:32,370 --> 00:02:34,830 The only difference is what's inside the body of the page. 56 00:02:34,830 --> 00:02:36,538 And so this can be a common case where it 57 00:02:36,538 --> 00:02:39,560 would be useful to factor out the common code into a file that's just 58 00:02:39,560 --> 00:02:41,840 called layout.html, for instance, and then 59 00:02:41,840 --> 00:02:46,000 reference that file in the index.html and more.html. 60 00:02:46,000 --> 00:02:49,070 So I demonstrate that very briefly just so you get a refresher on that, 61 00:02:49,070 --> 00:02:52,310 so as you build Flask applications, it's something at your disposal as well. 62 00:02:52,310 --> 00:02:55,870 So I'll create a new file called layout.html, 63 00:02:55,870 --> 00:02:59,060 and it's going to look basically the same as what the index page looks like. 64 00:02:59,060 --> 00:03:01,550 But the area where my pages are different-- the header is 65 00:03:01,550 --> 00:03:02,720 the same, the title is going to be the same, 66 00:03:02,720 --> 00:03:04,440 the styling is going to be the same. 67 00:03:04,440 --> 00:03:06,830 The only difference is in the body of the web page. 68 00:03:06,830 --> 00:03:12,710 And here, I just want some custom block, whereby in index.html and more.html, 69 00:03:12,710 --> 00:03:15,050 I can add code into that blocks. 70 00:03:15,050 --> 00:03:19,147 So I can say, OK, inside this block, inside the body, I'm going to say, 71 00:03:19,147 --> 00:03:21,230 create a block that I'm just going to call a body. 72 00:03:21,230 --> 00:03:22,100 But it could be called anything. 73 00:03:22,100 --> 00:03:25,460 It could be called main, or content, or some other name for the block. 74 00:03:25,460 --> 00:03:29,270 And then end block, again, using the curly braces and percent signs. 75 00:03:29,270 --> 00:03:30,830 It's typical [INAUDIBLE] syntax. 76 00:03:30,830 --> 00:03:34,250 And all I'm doing here is basically saying, inside the body of this layout, 77 00:03:34,250 --> 00:03:36,470 that HTML page, is a section where I'm going 78 00:03:36,470 --> 00:03:38,490 to insert code at some point in time. 79 00:03:38,490 --> 00:03:43,370 And so that means I can very easily make some modifications to index.html 80 00:03:43,370 --> 00:03:44,930 to simplify this page dramatically. 81 00:03:44,930 --> 00:03:47,630 I can get rid of, basically, all of the code, 82 00:03:47,630 --> 00:03:50,210 except for hello, which I'm going to need. 83 00:03:50,210 --> 00:03:57,360 And I'll just say at the top, extends layout.html, meaning take layout.html 84 00:03:57,360 --> 00:04:00,750 and use that as the starting point for this HTML page. 85 00:04:00,750 --> 00:04:04,800 And the only thing that I need to change is to say, OK, inside of block body, 86 00:04:04,800 --> 00:04:09,870 instead of it being empty, let me just put the word hello there. 87 00:04:09,870 --> 00:04:18,320 And likewise, in more.html, I can do the same thing, extend layout.html. 88 00:04:18,320 --> 00:04:22,079 And inside of block body, just say more text, or whatever it might be. 89 00:04:22,079 --> 00:04:24,900 I've simplified both index.html and more.html 90 00:04:24,900 --> 00:04:29,500 dramatically because all of the common code is just inside of layout.html. 91 00:04:29,500 --> 00:04:33,240 So now, if I run this Flask application by typing flask run, 92 00:04:33,240 --> 00:04:37,140 open up a web browser, you see hello with the blue background. 93 00:04:37,140 --> 00:04:40,440 I go to slash more, you see the same thing, also with the blue background. 94 00:04:40,440 --> 00:04:43,530 And that common code of the title, the blue background, all of that 95 00:04:43,530 --> 00:04:46,379 is there because of that shared template inheritance. 96 00:04:46,379 --> 00:04:49,170 So just wanted to demonstrate that so you had an opportunity to see 97 00:04:49,170 --> 00:04:51,299 that in practice. 98 00:04:51,299 --> 00:04:53,590 Questions about template inheritance before we move on? 99 00:04:53,590 --> 00:04:54,582 Yeah? 100 00:04:54,582 --> 00:04:59,080 AUDIENCE: When you wanted to change the style of more, for instance, 101 00:04:59,080 --> 00:05:01,515 but then the style is going to be [INAUDIBLE].. 102 00:05:01,515 --> 00:05:02,939 So how would you do that? 103 00:05:02,939 --> 00:05:03,980 BRIAN YU: Great question. 104 00:05:03,980 --> 00:05:07,480 So the question is, all right, in layout.html, we've put some styling. 105 00:05:07,480 --> 00:05:08,950 We made the background color blue. 106 00:05:08,950 --> 00:05:12,370 What if I wanted to add other styling to this page? 107 00:05:12,370 --> 00:05:15,010 Well, what you could do is just add another block. 108 00:05:15,010 --> 00:05:18,120 Add a block, which I'll call block style, for instance, 109 00:05:18,120 --> 00:05:20,650 and end block there. 110 00:05:20,650 --> 00:05:29,560 And you could then, inside of index.html or more.html, add block style. 111 00:05:29,560 --> 00:05:32,500 And maybe for consistency, I'll put block style up at the top. 112 00:05:32,500 --> 00:05:33,880 And you could add some code here. 113 00:05:33,880 --> 00:05:38,050 You could add, OK, I want the body to have a font size of 24 pixels, 114 00:05:38,050 --> 00:05:45,100 or something like that, whereby now, if I run this web application 115 00:05:45,100 --> 00:05:49,825 and go to slash more, more text is larger. 116 00:05:49,825 --> 00:05:52,450 If I go to slash more, notice the size of the text gets bigger. 117 00:05:52,450 --> 00:05:56,470 So I've been able to add style code just by putting it in block style, 118 00:05:56,470 --> 00:06:00,640 and block style is just going to be inserted right here inside of the web 119 00:06:00,640 --> 00:06:01,310 page. 120 00:06:01,310 --> 00:06:03,580 So you can add as many blocks as you'd like in order 121 00:06:03,580 --> 00:06:08,739 to customize your layouts however best fits your needs in the program. 122 00:06:08,739 --> 00:06:09,280 Other things? 123 00:06:09,280 --> 00:06:11,920 124 00:06:11,920 --> 00:06:15,400 OK, so there are two Python-related, or programming concepts, 125 00:06:15,400 --> 00:06:18,250 more generally, that I wanted to talk about today before we move on, 126 00:06:18,250 --> 00:06:19,870 the first of which is recursion. 127 00:06:19,870 --> 00:06:22,660 So this is something that we touched on briefly. 128 00:06:22,660 --> 00:06:26,380 If you took CS50 this past semester, it came up briefly on the CS50 quiz. 129 00:06:26,380 --> 00:06:29,950 But recursion is this idea of we can have functions, 130 00:06:29,950 --> 00:06:31,330 functions that are running code. 131 00:06:31,330 --> 00:06:34,340 But functions can also call themselves. 132 00:06:34,340 --> 00:06:36,340 We know that functions can call other functions, 133 00:06:36,340 --> 00:06:38,256 but functions can call themselves, oftentimes, 134 00:06:38,256 --> 00:06:40,580 to create some sort of useful effect. 135 00:06:40,580 --> 00:06:42,610 And so the function that I'm going to write here 136 00:06:42,610 --> 00:06:45,235 is a function that's going to calculate-- this the classic, one 137 00:06:45,235 --> 00:06:49,100 of the classic examples of recursion-- calculating the factorial of a number. 138 00:06:49,100 --> 00:06:51,670 So the factorial, I'll just do some comments here. 139 00:06:51,670 --> 00:06:56,020 I'll do factorial.pi. 140 00:06:56,020 --> 00:07:00,550 If I had a number like 5 factorial, 5 factorial is equal to 5 times 4 times 141 00:07:00,550 --> 00:07:03,610 3 times 2 times 1, which is equal to 120. 142 00:07:03,610 --> 00:07:08,620 If I add something like 4 factorial, that's 4 times 3 times 2 times 143 00:07:08,620 --> 00:07:11,200 1, which is equal to 24. 144 00:07:11,200 --> 00:07:12,957 So a number factorial is just that number 145 00:07:12,957 --> 00:07:15,790 times the number one less than it times the number one less than it, 146 00:07:15,790 --> 00:07:17,560 so on and so forth, up until you get to 1. 147 00:07:17,560 --> 00:07:19,268 You multiply that all out, and the result 148 00:07:19,268 --> 00:07:21,460 is whatever you get as the value of the factorial. 149 00:07:21,460 --> 00:07:23,200 And I would like to write a function that 150 00:07:23,200 --> 00:07:28,600 calculates the factorial of some number, some number n, for example. 151 00:07:28,600 --> 00:07:31,030 So I define a function called factorial n. 152 00:07:31,030 --> 00:07:33,070 And the interesting thing that I can do here 153 00:07:33,070 --> 00:07:40,830 is notice that 5 factorial is really just 5 times 4 times 3 times 2 times 1. 154 00:07:40,830 --> 00:07:46,420 And this 4 times 3 times 2 times 1 is the same as just 4 factorial. 155 00:07:46,420 --> 00:07:51,550 And so the recursive idea that I can use here is the factorial of some value n 156 00:07:51,550 --> 00:07:57,490 is going to be just n times the factorial of n minus 1. 157 00:07:57,490 --> 00:08:00,820 I take the number and multiply it by the factorial of the number 158 00:08:00,820 --> 00:08:02,260 one less than it. 159 00:08:02,260 --> 00:08:06,280 So 5 factorial becomes five times the factorial of 4. 160 00:08:06,280 --> 00:08:10,080 And 4 is just 4 times the factorial of 3. 161 00:08:10,080 --> 00:08:12,080 Now, what goes wrong if I try and use this code? 162 00:08:12,080 --> 00:08:14,996 Something's not quite right about it, although the idea is reasonable. 163 00:08:14,996 --> 00:08:15,553 Yeah? 164 00:08:15,553 --> 00:08:19,455 AUDIENCE: It breaks at one or minus one. 165 00:08:19,455 --> 00:08:20,080 BRIAN YU: Yeah. 166 00:08:20,080 --> 00:08:23,080 So it breaks, when I get down to lower numbers, like factorial of 1. 167 00:08:23,080 --> 00:08:27,220 Because then I'll do 1 times factorial of 0, and factorial of 0, 168 00:08:27,220 --> 00:08:29,623 by this logic, would be 0 times factorial of negative 1. 169 00:08:29,623 --> 00:08:32,289 And we're just going to keep going into the negative numbers now 170 00:08:32,289 --> 00:08:33,909 and it's just never going to stop. 171 00:08:33,909 --> 00:08:36,100 So when I write a recursive function, it's 172 00:08:36,100 --> 00:08:39,490 important to have what's called a base case, some point at which this function 173 00:08:39,490 --> 00:08:40,890 is going to stop running. 174 00:08:40,890 --> 00:08:44,494 And so I could say something like, OK, 1 factorial is just 1. 175 00:08:44,494 --> 00:08:47,410 So the simple way to do this-- as there are multiple ways to do this-- 176 00:08:47,410 --> 00:08:52,060 is to say, all right, if n equals 1, then just return 1. 177 00:08:52,060 --> 00:08:54,760 Because the factorial of 1 is just 1. 178 00:08:54,760 --> 00:08:57,560 And so I could do something now and say, all right, 179 00:08:57,560 --> 00:09:01,360 I'll open up a Python interpreter from factorial. 180 00:09:01,360 --> 00:09:03,730 Import the factorial function. 181 00:09:03,730 --> 00:09:06,130 And I can say, OK, what's the factorial of 1? 182 00:09:06,130 --> 00:09:07,660 And it is, in fact, 1. 183 00:09:07,660 --> 00:09:09,800 And I can say, OK, what's the factorial of 2? 184 00:09:09,800 --> 00:09:13,780 Well, that'll be 2 times the factorial of 1, which is 2. 185 00:09:13,780 --> 00:09:16,990 Factorial of 3, factorial of 4, factorial of 5, 186 00:09:16,990 --> 00:09:21,250 and we're getting the correct results just by calling the function itself 187 00:09:21,250 --> 00:09:24,432 again, by recursively calling the function on a smaller and smaller sized 188 00:09:24,432 --> 00:09:27,640 problem until we get down to a problem the size 1, and then we've handled it. 189 00:09:27,640 --> 00:09:30,310 Now, this isn't quite perfect because it doesn't handle factorial of 0, 190 00:09:30,310 --> 00:09:32,200 but you can make some slight modifications 191 00:09:32,200 --> 00:09:33,700 to make it handle that as well. 192 00:09:33,700 --> 00:09:35,410 But that's the general idea of recursion. 193 00:09:35,410 --> 00:09:37,510 And recursion is actually going to come up later this afternoon, 194 00:09:37,510 --> 00:09:39,593 as we start to talk about artificial intelligence, 195 00:09:39,593 --> 00:09:43,030 but it comes up more generally in programming in many different cases. 196 00:09:43,030 --> 00:09:45,566 And in fact, if you go on to take CS51, recursion 197 00:09:45,566 --> 00:09:47,440 is going to be a big component of that course 198 00:09:47,440 --> 00:09:50,790 and thinking recursively and thinking about how to write recursive functions. 199 00:09:50,790 --> 00:09:52,280 So just wanted to introduce that. 200 00:09:52,280 --> 00:09:52,600 Yes? 201 00:09:52,600 --> 00:09:55,474 AUDIENCE: Can you show what it looks like if you forgot the base case 202 00:09:55,474 --> 00:09:56,330 but try to run it? 203 00:09:56,330 --> 00:09:56,870 BRIAN YU: Great question. 204 00:09:56,870 --> 00:09:59,960 What happens if you forget the base case but try to run it anyways? 205 00:09:59,960 --> 00:10:01,070 We'll give that a shot. 206 00:10:01,070 --> 00:10:03,500 So if I didn't include if n equals 1 return 1, 207 00:10:03,500 --> 00:10:06,520 and I just had return n times factorial of n minus 1, 208 00:10:06,520 --> 00:10:08,030 I'll load up Python again. 209 00:10:08,030 --> 00:10:10,599 Say from factorial import factorial. 210 00:10:10,599 --> 00:10:12,890 This is that idea of importing a function from a module 211 00:10:12,890 --> 00:10:14,722 that we talked about earlier this morning. 212 00:10:14,722 --> 00:10:16,430 If I try and do factorial of 5 right now, 213 00:10:16,430 --> 00:10:18,320 for instance, I'm going to get an error. 214 00:10:18,320 --> 00:10:21,110 I get a recursion error, specifically which 215 00:10:21,110 --> 00:10:24,140 is that maximum recursion depth has been exceeded. 216 00:10:24,140 --> 00:10:28,550 I've tried to call a function on its own too many times. 217 00:10:28,550 --> 00:10:31,980 Python lets you call a recursive function up to 1,000 times, 218 00:10:31,980 --> 00:10:34,700 and I have exceeded that because this would go on infinitely 219 00:10:34,700 --> 00:10:36,020 if it would let me do so. 220 00:10:36,020 --> 00:10:38,270 So that is what happens if you don't have a base case. 221 00:10:38,270 --> 00:10:41,561 If you ever see a recursion error, which you might this afternoon if you choose 222 00:10:41,561 --> 00:10:44,360 to implement the artificial intelligence algorithm, 223 00:10:44,360 --> 00:10:46,947 that's what you can expect to see. 224 00:10:46,947 --> 00:10:48,530 Questions about the idea of recursion? 225 00:10:48,530 --> 00:10:49,238 Yeah? 226 00:10:49,238 --> 00:10:53,222 AUDIENCE: With the line return at times factorial minus 1, 227 00:10:53,222 --> 00:10:56,720 is that factorial function already predefined? 228 00:10:56,720 --> 00:10:59,420 BRIAN YU: This factorial function is not predefined. 229 00:10:59,420 --> 00:11:01,700 This factorial function is just a name that 230 00:11:01,700 --> 00:11:03,900 is referencing the function itself. 231 00:11:03,900 --> 00:11:06,050 So this function, as part of the way it works, 232 00:11:06,050 --> 00:11:08,780 is going to use itself to try and calculate 233 00:11:08,780 --> 00:11:11,450 the answer to a smaller problem. 234 00:11:11,450 --> 00:11:15,770 AUDIENCE: So you don't really need the thing in purple, right? 235 00:11:15,770 --> 00:11:19,140 The top line will still do the job? 236 00:11:19,140 --> 00:11:22,095 BRIAN YU: You don't need the thing in-- 237 00:11:22,095 --> 00:11:25,629 AUDIENCE: The last three lines, you don't really need them, right? 238 00:11:25,629 --> 00:11:27,420 BRIAN YU: So you do need these three lines, 239 00:11:27,420 --> 00:11:30,630 and the reason is this is handling the logic of what the function is doing. 240 00:11:30,630 --> 00:11:32,810 So the first thing my function is doing is checking 241 00:11:32,810 --> 00:11:34,260 to see if I've hit my base case. 242 00:11:34,260 --> 00:11:36,620 If I'm calculating the factorial of 1, I'm 243 00:11:36,620 --> 00:11:40,490 just going to pre-program into my function the answer to that is 1. 244 00:11:40,490 --> 00:11:43,640 But if I'm trying to calculate the factorial of anything else-- 245 00:11:43,640 --> 00:11:46,140 presumably something larger than 1-- but you should probably 246 00:11:46,140 --> 00:11:48,590 add checks to handle things less than that, 247 00:11:48,590 --> 00:11:51,530 then to calculate the factorial of 5, for example, 248 00:11:51,530 --> 00:11:54,080 I'm going to take the number 5 and multiply it 249 00:11:54,080 --> 00:12:01,735 by whatever I would get by taking the factorial of 4 of n minus 1. 250 00:12:01,735 --> 00:12:04,670 AUDIENCE: How does the computer know what that factorial n minus 1 is? 251 00:12:04,670 --> 00:12:05,670 BRIAN YU: Good question. 252 00:12:05,670 --> 00:12:07,940 How does the computer know what the factorial of n minus 1 is? 253 00:12:07,940 --> 00:12:09,150 It calls the function again. 254 00:12:09,150 --> 00:12:11,190 So now we're running factorial one more time. 255 00:12:11,190 --> 00:12:13,400 We're calculating factorial of 4. 256 00:12:13,400 --> 00:12:14,330 That's not one 1. 257 00:12:14,330 --> 00:12:16,806 We're going to return 4 times the factorial of 3. 258 00:12:16,806 --> 00:12:18,680 So now, we're calculating the factorial of 3, 259 00:12:18,680 --> 00:12:22,790 which is 3 times the factorial of 2, which is 2 times the factorial of 1. 260 00:12:22,790 --> 00:12:26,240 and the factorial of 1, as these if conditions on lines 9 and 6 261 00:12:26,240 --> 00:12:28,686 will indicate, is just going to be 1. 262 00:12:28,686 --> 00:12:30,560 So it's a slightly different way of thinking. 263 00:12:30,560 --> 00:12:32,435 It can be confusing to reason about it first. 264 00:12:32,435 --> 00:12:34,940 It seems like I'm assuming that the problem is solved 265 00:12:34,940 --> 00:12:38,690 and just using that in order to solve the problem, which doesn't quite 266 00:12:38,690 --> 00:12:40,310 make sense sometimes. 267 00:12:40,310 --> 00:12:43,520 But if you try it on smaller examples, you can sometimes get a sense for it. 268 00:12:43,520 --> 00:12:44,930 And hopefully, when we get to the algorithm 269 00:12:44,930 --> 00:12:46,100 that we'll show later this afternoon, that 270 00:12:46,100 --> 00:12:47,930 will help it make more sense as well. 271 00:12:47,930 --> 00:12:51,110 272 00:12:51,110 --> 00:12:53,618 Other things? 273 00:12:53,618 --> 00:12:55,840 OK, so that's recursive programming. 274 00:12:55,840 --> 00:12:58,720 And one other programming model or paradigm that I thought 275 00:12:58,720 --> 00:13:01,210 was probably worth demonstrating, or at least showing, is 276 00:13:01,210 --> 00:13:03,460 the idea of object-oriented programming, something 277 00:13:03,460 --> 00:13:06,120 that you might see in other languages, as well, but that Python supports, 278 00:13:06,120 --> 00:13:07,953 and something that will come in handy for us 279 00:13:07,953 --> 00:13:11,320 as we begin to deal with databases and dealing with web applications that 280 00:13:11,320 --> 00:13:13,370 interact with data later on. 281 00:13:13,370 --> 00:13:15,730 And the idea of object-oriented programming 282 00:13:15,730 --> 00:13:19,270 is that object-oriented programming is a programming paradigm that's 283 00:13:19,270 --> 00:13:21,430 based on the idea of an object. 284 00:13:21,430 --> 00:13:24,490 And all an object is just some structure in our code 285 00:13:24,490 --> 00:13:28,450 that's a combination of data that we're storing about the object, 286 00:13:28,450 --> 00:13:32,050 and also some code that we can run with the object. 287 00:13:32,050 --> 00:13:35,380 So it's a way of encapsulating data and code together inside 288 00:13:35,380 --> 00:13:38,170 of one common unified structure. 289 00:13:38,170 --> 00:13:41,020 And so I'll give a simple example of this. 290 00:13:41,020 --> 00:13:45,920 Maybe I want to define a way of keeping track of coordinate points, 291 00:13:45,920 --> 00:13:48,370 so x and y-coordinate pairs. 292 00:13:48,370 --> 00:13:50,410 You could imagine that I could just say, OK, 293 00:13:50,410 --> 00:13:53,260 x equals some value and y equals some value, 294 00:13:53,260 --> 00:13:56,080 and then just manipulate those x and y values together. 295 00:13:56,080 --> 00:13:58,750 But it would be nice to be able to take those two values 296 00:13:58,750 --> 00:14:01,599 and encapsulate them inside of a single structure. 297 00:14:01,599 --> 00:14:03,640 Now, we saw that we could use a tuple to do this. 298 00:14:03,640 --> 00:14:08,350 I could say coordinates equals x comma y. 299 00:14:08,350 --> 00:14:10,360 Coordinates equals x comma y. 300 00:14:10,360 --> 00:14:12,830 And now coordinates is equal to 28 comma 50. 301 00:14:12,830 --> 00:14:15,709 So you can do that to encapsulate the structure together. 302 00:14:15,709 --> 00:14:17,500 But as things get more complicated as there 303 00:14:17,500 --> 00:14:20,620 becomes more and more pieces of data that you like to associate with this. 304 00:14:20,620 --> 00:14:23,440 Maybe not just two fields, but 10, or dozens of fields. 305 00:14:23,440 --> 00:14:26,800 And as you want to begin to perform computations and operations 306 00:14:26,800 --> 00:14:28,750 on these coordinates, this sort of programming 307 00:14:28,750 --> 00:14:30,830 can sometimes start to get a bit difficult. 308 00:14:30,830 --> 00:14:32,830 And so object-oriented programming is designed 309 00:14:32,830 --> 00:14:34,520 to make this a little bit easier. 310 00:14:34,520 --> 00:14:37,960 And so I'll create a new file called points.pi. 311 00:14:37,960 --> 00:14:41,680 And I'm going to define a new class called point. 312 00:14:41,680 --> 00:14:46,060 And you can think of a class as just a new type of object 313 00:14:46,060 --> 00:14:47,650 that I'm allowing myself to create. 314 00:14:47,650 --> 00:14:50,990 So the string, for instance, is a class that already exists 315 00:14:50,990 --> 00:14:52,900 and we've been able to use and manipulate. 316 00:14:52,900 --> 00:14:56,380 The list, for instance, is another example of a class, some type of thing 317 00:14:56,380 --> 00:14:57,490 that I can manipulate. 318 00:14:57,490 --> 00:14:59,770 And I'm creating a new class called point that is just 319 00:14:59,770 --> 00:15:02,460 going to store x and y-coordinates. 320 00:15:02,460 --> 00:15:06,445 And so now, what I'm going to write is what's called a constructor function. 321 00:15:06,445 --> 00:15:08,320 This will look a little bit cryptic at first, 322 00:15:08,320 --> 00:15:10,990 but hopefully it'll become clear in just a moment. 323 00:15:10,990 --> 00:15:16,060 The constructor function in Python, by default, is called init, __init__, 324 00:15:16,060 --> 00:15:17,630 for initialize. 325 00:15:17,630 --> 00:15:22,660 And __init__ is going to take three arguments-- we'll see why in a moment-- 326 00:15:22,660 --> 00:15:24,970 self, x, and y. 327 00:15:24,970 --> 00:15:28,450 Self is going to refer to the object in question 328 00:15:28,450 --> 00:15:30,730 and x and y are going to be arguments that we're 329 00:15:30,730 --> 00:15:34,267 going to provide when we first create this point. 330 00:15:34,267 --> 00:15:36,850 And so I'll show you what this function is going to look like. 331 00:15:36,850 --> 00:15:40,600 To create the point, I want to update the object. 332 00:15:40,600 --> 00:15:42,430 Self is the name of this object. 333 00:15:42,430 --> 00:15:46,180 And I'm going to set a property of it called x to be equal to whatever 334 00:15:46,180 --> 00:15:48,520 the argument is, just equal to x. 335 00:15:48,520 --> 00:15:51,550 And I'm going to say self.y equals y. 336 00:15:51,550 --> 00:15:53,860 So this looks a little bit strange, probably unfamiliar 337 00:15:53,860 --> 00:15:55,818 if you haven't seen this sort of syntax before. 338 00:15:55,818 --> 00:15:58,030 But what I've done is I've created a class now 339 00:15:58,030 --> 00:16:01,240 that allows me to just create point objects. 340 00:16:01,240 --> 00:16:04,840 And so to create a point object, what I'm going to do is say p-- 341 00:16:04,840 --> 00:16:06,130 just some variable-- 342 00:16:06,130 --> 00:16:07,210 equals point. 343 00:16:07,210 --> 00:16:09,220 That's the name of the class. 344 00:16:09,220 --> 00:16:11,860 And then I'm going to provide the x and y arguments to it. 345 00:16:11,860 --> 00:16:13,210 I'm going to say point-- 346 00:16:13,210 --> 00:16:17,690 the x-coordinate will be 10 and the y-coordinate will be 20. 347 00:16:17,690 --> 00:16:22,780 And so just like that, I've been able to create a point object, 348 00:16:22,780 --> 00:16:27,767 passing in 10 as the value of x and 20 as the value of y. 349 00:16:27,767 --> 00:16:29,350 And I don't provide anything for self. 350 00:16:29,350 --> 00:16:31,780 Self is just this assumed argument in the world 351 00:16:31,780 --> 00:16:36,190 of Python object-oriented programming that just refers to the point 352 00:16:36,190 --> 00:16:38,940 that I have just created. 353 00:16:38,940 --> 00:16:42,630 So now, if I wanted to print out the x-coordinate of this point, 354 00:16:42,630 --> 00:16:44,840 I could print out p.x. 355 00:16:44,840 --> 00:16:48,320 In Python objects, you use the dot notation, something dot something else, 356 00:16:48,320 --> 00:16:51,270 to access a particular property of that object. 357 00:16:51,270 --> 00:16:58,130 And I can print out p.y to print out the y property of this particular object. 358 00:16:58,130 --> 00:17:04,770 And so now if I run this program, by running Python points.pi, what I get 359 00:17:04,770 --> 00:17:07,890 is I get printed out 10 and then 20. 360 00:17:07,890 --> 00:17:10,329 Because it printed out the x value of the point 361 00:17:10,329 --> 00:17:13,079 and then it printed out the y value of the point, and both of them 362 00:17:13,079 --> 00:17:18,780 are stored inside of this object that's just called p. 363 00:17:18,780 --> 00:17:21,210 So this is a very new way of thinking about programming, 364 00:17:21,210 --> 00:17:24,001 a different way of thinking about data, a different way of thinking 365 00:17:24,001 --> 00:17:26,849 about how to organize information inside of our objects. 366 00:17:26,849 --> 00:17:28,500 Questions about any of this? 367 00:17:28,500 --> 00:17:29,010 Very new. 368 00:17:29,010 --> 00:17:29,626 Yeah? 369 00:17:29,626 --> 00:17:32,672 AUDIENCE: Were any visualization functions gaps for self? 370 00:17:32,672 --> 00:17:36,440 Or is there any alternative that you can write for self? 371 00:17:36,440 --> 00:17:37,440 BRIAN YU: Good question. 372 00:17:37,440 --> 00:17:39,420 The question is, does this need to be self? 373 00:17:39,420 --> 00:17:42,060 I think, technically, it could be something different, 374 00:17:42,060 --> 00:17:44,080 but the convention in Python is to call it self. 375 00:17:44,080 --> 00:17:48,540 So generally best to call it by its convention. 376 00:17:48,540 --> 00:17:50,670 Other things? 377 00:17:50,670 --> 00:17:52,160 Questions about this? 378 00:17:52,160 --> 00:17:52,660 Yeah? 379 00:17:52,660 --> 00:17:54,770 AUDIENCE: What is the __init__? 380 00:17:54,770 --> 00:17:57,030 BRIAN YU: __init__ stands for initialization. 381 00:17:57,030 --> 00:17:59,566 This is basically, how do I create a new point? 382 00:17:59,566 --> 00:18:01,440 And what I'm saying is to create a new point, 383 00:18:01,440 --> 00:18:04,590 I need to provide two arguments, an x and a y-coordinate. 384 00:18:04,590 --> 00:18:07,590 And I set the x value of the point to be whatever 385 00:18:07,590 --> 00:18:10,620 that x argument is, and I set the y value of the point 386 00:18:10,620 --> 00:18:12,810 to be whatever the y argument is. 387 00:18:12,810 --> 00:18:15,660 And I use this function here on line 8. 388 00:18:15,660 --> 00:18:18,420 When I create a new point by saying point 10, 20, 389 00:18:18,420 --> 00:18:23,130 that's calling this __init__ function, passing in the value of x and the value 390 00:18:23,130 --> 00:18:24,350 of y as 10 and 20. 391 00:18:24,350 --> 00:18:25,350 And I can show you this. 392 00:18:25,350 --> 00:18:30,270 If I add a print statement here, I'll say creating a new point 393 00:18:30,270 --> 00:18:33,815 with coordinates x and y. 394 00:18:33,815 --> 00:18:36,940 So anytime I run this __init__ function, it's going to say creating the new 395 00:18:36,940 --> 00:18:41,460 point with coordinates x and y, such that now if I run this code, 396 00:18:41,460 --> 00:18:44,684 it says creating a new point with coordinates 10 and 20. 397 00:18:44,684 --> 00:18:47,850 Because 10 and 20 were passed in as the arguments to that __init__ function, 398 00:18:47,850 --> 00:18:51,990 and then it creates the point so that I can then print out what the values of x 399 00:18:51,990 --> 00:18:54,066 and y actually are. 400 00:18:54,066 --> 00:18:55,515 Yeah? 401 00:18:55,515 --> 00:19:01,557 AUDIENCE: instead of saying "self," could you say "he" [INAUDIBLE]?? 402 00:19:01,557 --> 00:19:02,140 BRIAN YU: Yes. 403 00:19:02,140 --> 00:19:03,320 So someone else asked this a moment ago. 404 00:19:03,320 --> 00:19:04,910 Self is just the convention in Python. 405 00:19:04,910 --> 00:19:09,290 It's generally accepted as a way of referring to the object in question. 406 00:19:09,290 --> 00:19:13,730 So when I say self.x, I am modifying self, the object, 407 00:19:13,730 --> 00:19:16,990 and updating it to store some additional data alongside it. 408 00:19:16,990 --> 00:19:21,190 409 00:19:21,190 --> 00:19:25,210 And so there are other things I can do here. 410 00:19:25,210 --> 00:19:27,220 I can add another function, or what's called 411 00:19:27,220 --> 00:19:30,430 a method, in the world of object-oriented programming called 412 00:19:30,430 --> 00:19:32,090 shift, for example. 413 00:19:32,090 --> 00:19:35,890 If I wanted to shift by a certain x and y amount, like move the point 414 00:19:35,890 --> 00:19:37,780 to a different location, then I would say, 415 00:19:37,780 --> 00:19:41,710 OK, self.x equals self.x x plus however much 416 00:19:41,710 --> 00:19:43,900 I want to shift the x-coordinate by. 417 00:19:43,900 --> 00:19:46,720 And self.y equals self.y plus however much 418 00:19:46,720 --> 00:19:49,340 I want to shift the y-coordinate by. 419 00:19:49,340 --> 00:19:55,370 And so now, if I were to say something like p.shift, 420 00:19:55,370 --> 00:19:58,640 shift two in the x direction and three in the y direction, 421 00:19:58,640 --> 00:20:00,890 and then print out x and y. 422 00:20:00,890 --> 00:20:05,666 Well, then what I'm going to get is I'm going to get 12 and 23. 423 00:20:05,666 --> 00:20:07,540 So you look at that code to see why it works. 424 00:20:07,540 --> 00:20:09,820 I'm calling the shift method, which is just 425 00:20:09,820 --> 00:20:12,790 a fancy word for function in the world of object-oriented programming, 426 00:20:12,790 --> 00:20:16,120 passing in 2 and 3 as the arguments to that, x and y. 427 00:20:16,120 --> 00:20:20,830 And then I'm updating self.x and self.y, the values stored inside of the object, 428 00:20:20,830 --> 00:20:24,760 to increment themselves by however much I want to shift the point by. 429 00:20:24,760 --> 00:20:27,650 430 00:20:27,650 --> 00:20:30,090 So this is the basic idea of object-oriented programming. 431 00:20:30,090 --> 00:20:31,650 We're not going to use this too much today, 432 00:20:31,650 --> 00:20:33,400 but we'll come back to it in about two days time. 433 00:20:33,400 --> 00:20:36,240 I just wanted to introduce it now so that when we see it in two days' time, 434 00:20:36,240 --> 00:20:37,531 it looks a little bit familiar. 435 00:20:37,531 --> 00:20:39,834 And we'll see how this become very, very practical when 436 00:20:39,834 --> 00:20:42,000 we start dealing with databases and dealing with SQL 437 00:20:42,000 --> 00:20:44,880 and having our Python code interact with a SQL database 438 00:20:44,880 --> 00:20:49,340 without the help of a CS50 SQL library, for example. 439 00:20:49,340 --> 00:20:51,050 Questions about that before we move on? 440 00:20:51,050 --> 00:20:51,550 Yeah? 441 00:20:51,550 --> 00:20:55,940 AUDIENCE: Could you have built a keyboard from the Tic-Tac-Toe thing 442 00:20:55,940 --> 00:20:59,359 as [INAUDIBLE]? 443 00:20:59,359 --> 00:21:00,400 BRIAN YU: Great question. 444 00:21:00,400 --> 00:21:02,950 Could you have designed the Tic-Tac-Toe game board using a class 445 00:21:02,950 --> 00:21:05,440 instead of using the list of lists that we were using this morning? 446 00:21:05,440 --> 00:21:05,972 Absolutely. 447 00:21:05,972 --> 00:21:08,180 And potentially, that might be a better design for it 448 00:21:08,180 --> 00:21:09,640 as you think about the different operations you 449 00:21:09,640 --> 00:21:10,560 might want to do with it. 450 00:21:10,560 --> 00:21:10,930 But yes. 451 00:21:10,930 --> 00:21:14,096 And you're welcome to try that, too, if you'd like to, later this afternoon, 452 00:21:14,096 --> 00:21:17,864 if you want to try and use an object in order to do that. 453 00:21:17,864 --> 00:21:18,740 Yeah? 454 00:21:18,740 --> 00:21:22,400 AUDIENCE: So because we created the class there, 455 00:21:22,400 --> 00:21:25,814 do you need to use the self documentation for future functions 456 00:21:25,814 --> 00:21:26,995 that you're going to write? 457 00:21:26,995 --> 00:21:27,620 BRIAN YU: Yeah. 458 00:21:27,620 --> 00:21:31,010 Any functions that are inside of this class, or what we'll call methods, 459 00:21:31,010 --> 00:21:35,540 like the shift function, they all need to take the self argument if they're 460 00:21:35,540 --> 00:21:37,544 going to operate on a specific point. 461 00:21:37,544 --> 00:21:39,710 Because the idea here is I can have multiple points. 462 00:21:39,710 --> 00:21:42,230 I could create another point called P2 and that 463 00:21:42,230 --> 00:21:44,240 could have different coordinates. 464 00:21:44,240 --> 00:21:47,780 And that point has its own x value and its own y value, 465 00:21:47,780 --> 00:21:49,620 and those are manipulated separately. 466 00:21:49,620 --> 00:21:54,110 And so self.x is a way of saying this object's x property, or this object's y 467 00:21:54,110 --> 00:21:57,290 property, as opposed to some global x and y property that all 468 00:21:57,290 --> 00:21:58,310 of the objects share. 469 00:21:58,310 --> 00:22:00,200 They're specific to a particular object. 470 00:22:00,200 --> 00:22:03,176 471 00:22:03,176 --> 00:22:04,168 Other things? 472 00:22:04,168 --> 00:22:07,411 473 00:22:07,411 --> 00:22:07,910 All right. 474 00:22:07,910 --> 00:22:10,370 So we'll wrap up there for Python, but I thought what we'd do now 475 00:22:10,370 --> 00:22:12,703 is take a look at how to actually take a web application 476 00:22:12,703 --> 00:22:14,156 and deploy it to the internet. 477 00:22:14,156 --> 00:22:17,030 Right now, we've been running Flask applications on our own computers 478 00:22:17,030 --> 00:22:20,120 locally by typing flask run, and as soon as we quit Flask, 479 00:22:20,120 --> 00:22:21,440 the application stops running. 480 00:22:21,440 --> 00:22:22,331 It stops working. 481 00:22:22,331 --> 00:22:25,580 What we'd like to do with being able to host our Flask web applications online 482 00:22:25,580 --> 00:22:28,622 on the internet, such that anyone can access them, should they desire to. 483 00:22:28,622 --> 00:22:31,746 And there are a number of different ways to do this, but one of the easiest 484 00:22:31,746 --> 00:22:33,530 happens to be a service called Heroku. 485 00:22:33,530 --> 00:22:35,330 Heroku offers a bunch of different tiers, 486 00:22:35,330 --> 00:22:38,330 but there is a free tier that allows you to upload and run 487 00:22:38,330 --> 00:22:40,770 a fast web application online for free. 488 00:22:40,770 --> 00:22:43,520 And that's the one we're going to be exploring today. 489 00:22:43,520 --> 00:22:44,480 So a couple of steps. 490 00:22:44,480 --> 00:22:50,210 What I'm going to do is I'm going to try and take the Tic-Tac-Toe example from 491 00:22:50,210 --> 00:22:51,350 earlier this morning. 492 00:22:51,350 --> 00:22:55,539 And this is one that's not quite working yet. 493 00:22:55,539 --> 00:22:57,580 Yeah, this version doesn't actually let you play, 494 00:22:57,580 --> 00:23:00,530 but we'll try and at least upload it so you can see the board online. 495 00:23:00,530 --> 00:23:02,910 And we're going to take this Flask application 496 00:23:02,910 --> 00:23:06,784 and we're going to prepare it for Heroku and then deploy it to Heroku. 497 00:23:06,784 --> 00:23:08,700 And so I'll show you the steps for doing that. 498 00:23:08,700 --> 00:23:10,929 The steps are also online on CS50's documentation. 499 00:23:10,929 --> 00:23:12,720 And of course, this lecture video will also 500 00:23:12,720 --> 00:23:16,270 be online later, too, if you want to go back and reference that later. 501 00:23:16,270 --> 00:23:18,870 So the first thing I'm going to do is Heroku 502 00:23:18,870 --> 00:23:24,300 requires a file called the Procfile that basically just site decides, 503 00:23:24,300 --> 00:23:28,199 when I start running this application, what exactly is going to happen. 504 00:23:28,199 --> 00:23:30,990 And so there are a lot of steps that are going to be involved here. 505 00:23:30,990 --> 00:23:33,960 None of it is particularly necessarily intellectually interesting, 506 00:23:33,960 --> 00:23:36,240 but it's good to get an understanding, or at least get exposure 507 00:23:36,240 --> 00:23:38,430 to it, such that if you want to do something like this in the future, 508 00:23:38,430 --> 00:23:39,710 it's available to you. 509 00:23:39,710 --> 00:23:42,570 But certainly don't feel like you need to memorize this or anything. 510 00:23:42,570 --> 00:23:45,330 So inside the Procfile, I'm going to add this line, which 511 00:23:45,330 --> 00:23:49,380 is going to look a little cryptic. 512 00:23:49,380 --> 00:23:53,590 I'm going to say web colon gunicorn application colon app. 513 00:23:53,590 --> 00:23:54,090 OK. 514 00:23:54,090 --> 00:23:56,640 So what on earth is going on with that line? 515 00:23:56,640 --> 00:23:59,850 Web, this is saying, OK, when I'm going to launch this, 516 00:23:59,850 --> 00:24:01,762 I'd like to launch a web server. 517 00:24:01,762 --> 00:24:04,470 And what exactly should I do when I try and launch the web server 518 00:24:04,470 --> 00:24:06,180 for this Heroku application? 519 00:24:06,180 --> 00:24:10,249 Well, I'm going to run gunicorn, which is basically a web server program. 520 00:24:10,249 --> 00:24:12,540 Right now, we've been just using a program called Flask 521 00:24:12,540 --> 00:24:15,498 as our web server, which has the same name as the Python library called 522 00:24:15,498 --> 00:24:16,015 Flask. 523 00:24:16,015 --> 00:24:19,140 gunicorn tends to be a little bit more stable, a little more robust, better 524 00:24:19,140 --> 00:24:20,880 for a production quality program, if you're 525 00:24:20,880 --> 00:24:23,088 trying to deploy something to the internet for people 526 00:24:23,088 --> 00:24:24,810 to use more globally. 527 00:24:24,810 --> 00:24:26,910 Application is the name of the Python file 528 00:24:26,910 --> 00:24:28,650 from which I'm going to be running the application from. 529 00:24:28,650 --> 00:24:29,940 So it's called application.pi. 530 00:24:29,940 --> 00:24:31,830 So I'm going to say application. 531 00:24:31,830 --> 00:24:36,390 And then app is the name of the variable inside of application.pi 532 00:24:36,390 --> 00:24:37,770 that represents my Flask app. 533 00:24:37,770 --> 00:24:42,360 This word "app" corresponds to the word "app," 534 00:24:42,360 --> 00:24:47,250 here on line 5, where I said, OK, create a flask application and call it app. 535 00:24:47,250 --> 00:24:50,760 That name corresponds to this name in the Procfile. 536 00:24:50,760 --> 00:24:55,020 So this is just instructions to Heroku in a very succinct and sort of obscure 537 00:24:55,020 --> 00:24:57,390 way, saying when you start up this application, 538 00:24:57,390 --> 00:25:01,080 run this server, gunicorn, from an application, dot pi file, 539 00:25:01,080 --> 00:25:03,600 and run the web application called app, basically 540 00:25:03,600 --> 00:25:06,240 telling the server what to do. 541 00:25:06,240 --> 00:25:11,610 The next file that I need is a file called requirements.txt. 542 00:25:11,610 --> 00:25:15,840 requirements.txt is a file that's going to contain dependencies. 543 00:25:15,840 --> 00:25:18,720 In other words, what things does my server on Heroku 544 00:25:18,720 --> 00:25:21,300 need to install in order for my application 545 00:25:21,300 --> 00:25:22,680 to be able to work correctly? 546 00:25:22,680 --> 00:25:24,150 You probably faced similar issues when you 547 00:25:24,150 --> 00:25:26,580 were trying to run web applications earlier this morning, where 548 00:25:26,580 --> 00:25:28,330 you needed to install Flask and you needed 549 00:25:28,330 --> 00:25:31,140 to install Flask-Session in order to get the application working 550 00:25:31,140 --> 00:25:32,199 on your own computer. 551 00:25:32,199 --> 00:25:34,240 Same thing is going to be true of Heroku servers. 552 00:25:34,240 --> 00:25:36,365 So when you try and upload a web application there, 553 00:25:36,365 --> 00:25:39,240 it needs to have the necessary dependencies installed in order 554 00:25:39,240 --> 00:25:40,866 for the application to be able to work. 555 00:25:40,866 --> 00:25:42,073 So what are the requirements? 556 00:25:42,073 --> 00:25:44,010 Well, we need to install Flask, for sure. 557 00:25:44,010 --> 00:25:46,222 We need to install Flask-Session, for sure. 558 00:25:46,222 --> 00:25:48,180 And the third thing that we need, in this case, 559 00:25:48,180 --> 00:25:51,330 is gunicorn, the name of the web server that we're actually 560 00:25:51,330 --> 00:25:55,182 going to be using in order to run this web application. 561 00:25:55,182 --> 00:25:59,385 So all right, I've created a Procfile, created a requirements.txt file. 562 00:25:59,385 --> 00:26:02,340 All of this is just to set up my application such 563 00:26:02,340 --> 00:26:05,377 that I can deploy it to Heroku now. 564 00:26:05,377 --> 00:26:06,960 Questions about what I've done so far? 565 00:26:06,960 --> 00:26:09,640 566 00:26:09,640 --> 00:26:10,294 OK. 567 00:26:10,294 --> 00:26:13,210 Next step, there are a number of ways to deploy something into Heroku. 568 00:26:13,210 --> 00:26:16,630 The easiest way is probably just to deploy it from a git repository. 569 00:26:16,630 --> 00:26:18,400 So what I can do now is go to github.com. 570 00:26:18,400 --> 00:26:21,380 Recall that we learned about git and GitHub yesterday. 571 00:26:21,380 --> 00:26:24,520 I'm going to go ahead and create a new repository. 572 00:26:24,520 --> 00:26:30,260 I'll call it Tic-Tac-Toe, and I'll go in and create the repository. 573 00:26:30,260 --> 00:26:33,460 And now, I'm going to follow a number of different steps here. 574 00:26:33,460 --> 00:26:36,980 It's telling me what commands I need to run in order to set up my repository. 575 00:26:36,980 --> 00:26:40,900 So I need to run git __init__ in my Tic-Tac-Toe directory. 576 00:26:40,900 --> 00:26:43,840 git __init__ basically just sets up this directory, this folder, 577 00:26:43,840 --> 00:26:46,345 as a Git repository that I can then push somewhere. 578 00:26:46,345 --> 00:26:50,959 So all right, I've initialized a new Git repository in my Tic-Tac-Toe directory. 579 00:26:50,959 --> 00:26:53,500 And now what I'd like to do is set it up so that when I push, 580 00:26:53,500 --> 00:26:55,990 it's going to push to this GitHub repository. 581 00:26:55,990 --> 00:26:59,890 And that's this command, git remote add origin, basically just saying, 582 00:26:59,890 --> 00:27:02,320 remember that origin is where on GitHub am I going 583 00:27:02,320 --> 00:27:04,120 to push my code to when I run git push. 584 00:27:04,120 --> 00:27:07,630 So I'm going to copy that command, paste that in there. 585 00:27:07,630 --> 00:27:10,350 I've added the origin, saying I'm going to push to GitHub. 586 00:27:10,350 --> 00:27:12,850 And now, I'm going to add all my code to the Git repository. 587 00:27:12,850 --> 00:27:17,910 I'm going to say git add dot to say, add everything in this current directory. 588 00:27:17,910 --> 00:27:19,660 I'm going to commit these files. 589 00:27:19,660 --> 00:27:24,580 So say, prepare to deploy to Heroku is what I've just done. 590 00:27:24,580 --> 00:27:26,177 And now I'm going to push, git push. 591 00:27:26,177 --> 00:27:28,260 And I'm probably going to get a message that says, 592 00:27:28,260 --> 00:27:30,197 all right, I need to specify where to push to. 593 00:27:30,197 --> 00:27:32,530 I'm going to push to the master branch, just the default 594 00:27:32,530 --> 00:27:35,350 branch of the repository. 595 00:27:35,350 --> 00:27:39,880 So I push that code to my Git repository, so far all things 596 00:27:39,880 --> 00:27:41,530 that we've seen from yesterday. 597 00:27:41,530 --> 00:27:46,270 If I refresh this page, my application.pi, templates directory, 598 00:27:46,270 --> 00:27:49,330 Procfile file, requirements.txt, they're all located now inside 599 00:27:49,330 --> 00:27:50,710 of my Git repository. 600 00:27:50,710 --> 00:27:53,560 And now, I just need to tell them my Heroku account 601 00:27:53,560 --> 00:27:57,460 to launch a web application that's based on this Git repository. 602 00:27:57,460 --> 00:27:58,982 So I'll now go to heroku.com. 603 00:27:58,982 --> 00:28:01,190 And I mentioned an email near the beginning of class, 604 00:28:01,190 --> 00:28:02,770 that you should sign up for Heroku accounts. 605 00:28:02,770 --> 00:28:04,090 You're welcome to do so, if you'd like to, 606 00:28:04,090 --> 00:28:06,800 in order to experiment with this type of thing on your own. 607 00:28:06,800 --> 00:28:10,946 I'm going to go to the upper right, click on New, and say Create New App. 608 00:28:10,946 --> 00:28:12,820 I want to create a brand new web application. 609 00:28:12,820 --> 00:28:13,861 I need to give it a name. 610 00:28:13,861 --> 00:28:16,161 I'll call it brian-tictactoe. 611 00:28:16,161 --> 00:28:17,660 Hopefully, nobody's taken that name. 612 00:28:17,660 --> 00:28:18,743 All right, it's available. 613 00:28:18,743 --> 00:28:19,570 Great. 614 00:28:19,570 --> 00:28:22,090 We'll create that app. 615 00:28:22,090 --> 00:28:24,650 And OK, I've created a new Heroku app. 616 00:28:24,650 --> 00:28:27,710 And now, the next step I need to do is link it to my GitHub repository 617 00:28:27,710 --> 00:28:30,680 so it's actually pulling the code from GitHub. 618 00:28:30,680 --> 00:28:32,060 So under Deployment Method-- 619 00:28:32,060 --> 00:28:34,160 again, there are a number of different ways to deploy the application. 620 00:28:34,160 --> 00:28:36,743 The one we're going to explore today is deploying from GitHub. 621 00:28:36,743 --> 00:28:38,420 So I'm going to click on GitHub. 622 00:28:38,420 --> 00:28:39,900 And if you're doing this for the first time, 623 00:28:39,900 --> 00:28:42,900 you probably need to authorize it on GitHub's end, maybe log into GitHub 624 00:28:42,900 --> 00:28:45,950 and click Authorize to approve Heroku talking to GitHub for you. 625 00:28:45,950 --> 00:28:47,450 And then it says, connect to GitHub. 626 00:28:47,450 --> 00:28:49,070 Find a repository. 627 00:28:49,070 --> 00:28:52,310 The name of my repository is Tic-Tac-Toe. 628 00:28:52,310 --> 00:28:54,140 I'll go ahead and search for that. 629 00:28:54,140 --> 00:28:55,691 All right, here's the repository. 630 00:28:55,691 --> 00:28:57,440 I'm going to click Connect, which is going 631 00:28:57,440 --> 00:29:00,650 to link that GitHub repository to this Heroku application 632 00:29:00,650 --> 00:29:02,600 that I'm deploying to the internet. 633 00:29:02,600 --> 00:29:03,920 So I click Connect there. 634 00:29:03,920 --> 00:29:05,496 And great, now it's connected. 635 00:29:05,496 --> 00:29:07,370 And now, if I want to, I also have this thing 636 00:29:07,370 --> 00:29:11,060 called Automatic Deploys, where you can say anytime 637 00:29:11,060 --> 00:29:14,210 someone pushes to the master branch, automatically 638 00:29:14,210 --> 00:29:17,460 redeploy the application so that the version online matches whatever 639 00:29:17,460 --> 00:29:18,460 is on the master branch. 640 00:29:18,460 --> 00:29:21,751 And this can be very powerful because it means that any time you make a change, 641 00:29:21,751 --> 00:29:24,320 you can update the version online just by typing git push, 642 00:29:24,320 --> 00:29:25,500 push into the master branch. 643 00:29:25,500 --> 00:29:27,770 And Heroku will automatically do the deployment. 644 00:29:27,770 --> 00:29:31,109 This also makes it very important that the master branch is a working branch. 645 00:29:31,109 --> 00:29:33,650 And so again, if you're trying features, experimental things, 646 00:29:33,650 --> 00:29:36,025 things that might break, always a good idea to experiment 647 00:29:36,025 --> 00:29:36,950 on a separate branch. 648 00:29:36,950 --> 00:29:38,699 And only when you feel confident about it, 649 00:29:38,699 --> 00:29:41,510 merge it back into master, which will trigger the automatic deploy. 650 00:29:41,510 --> 00:29:43,593 So I'll go ahead and enable Automatic Deploy here. 651 00:29:43,593 --> 00:29:46,370 So anytime I push to master, it will automatically deploy. 652 00:29:46,370 --> 00:29:47,870 You can also manually deploy. 653 00:29:47,870 --> 00:29:51,300 Say, all right, I'd like to deploy this application from the master branch. 654 00:29:51,300 --> 00:29:53,120 And I'll go ahead and click Deploy Branch. 655 00:29:53,120 --> 00:29:55,220 And we'll see if this works. 656 00:29:55,220 --> 00:29:56,252 Hopefully, it works. 657 00:29:56,252 --> 00:29:57,710 You can see it's installing Python. 658 00:29:57,710 --> 00:29:58,940 It's installing pip. 659 00:29:58,940 --> 00:30:01,940 In a moment, it's going to try and install my dependencies, so things 660 00:30:01,940 --> 00:30:05,600 like Flask and Flask-Session, which are the different dependencies I 661 00:30:05,600 --> 00:30:07,910 defined in requirements.txt. 662 00:30:07,910 --> 00:30:10,282 And then it's going to try and start up my application. 663 00:30:10,282 --> 00:30:12,240 Questions about anything while this is running? 664 00:30:12,240 --> 00:30:16,180 665 00:30:16,180 --> 00:30:17,430 I see some green smiley faces. 666 00:30:17,430 --> 00:30:19,305 Great. 667 00:30:19,305 --> 00:30:21,180 All right, it's launched the web application. 668 00:30:21,180 --> 00:30:22,650 It's given me a URL. 669 00:30:22,650 --> 00:30:25,830 If I take this URL, copy it, go to a new page, 670 00:30:25,830 --> 00:30:28,830 this is brian-tictactoe.herokuapp.com. 671 00:30:28,830 --> 00:30:30,450 Press Return, and all right, great. 672 00:30:30,450 --> 00:30:32,366 Tic-Tac-Toe shows up deployed on the internet. 673 00:30:32,366 --> 00:30:35,431 And if you all go to that same URL, you can all see it now as well. 674 00:30:35,431 --> 00:30:37,680 If I make changes to it, push it to the master branch, 675 00:30:37,680 --> 00:30:40,140 it will also deploy online there, too. 676 00:30:40,140 --> 00:30:43,770 So I've been able to successfully deploy a Flask application to the internet 677 00:30:43,770 --> 00:30:45,150 by Heroku. 678 00:30:45,150 --> 00:30:46,380 Questions about that? 679 00:30:46,380 --> 00:30:46,880 Yeah? 680 00:30:46,880 --> 00:30:49,807 AUDIENCE: So does gunicorn just understand the Flask syntax 681 00:30:49,807 --> 00:30:51,220 and treats it as its own? 682 00:30:51,220 --> 00:30:53,520 Because you said it's from Flask or more dependable. 683 00:30:53,520 --> 00:30:54,770 BRIAN YU: Yeah, good question. 684 00:30:54,770 --> 00:30:58,095 So gunicorn is just a separate server application that's 685 00:30:58,095 --> 00:30:59,970 designed to sort of launch web servers and it 686 00:30:59,970 --> 00:31:02,040 understands how to take a Flask application 687 00:31:02,040 --> 00:31:05,520 and actually serve it to handle incoming requests. 688 00:31:05,520 --> 00:31:06,120 Other things? 689 00:31:06,120 --> 00:31:07,286 Julie do you have something? 690 00:31:07,286 --> 00:31:11,834 AUDIENCE: Do you have a particular domain [INAUDIBLE] that you look up? 691 00:31:11,834 --> 00:31:13,000 BRIAN YU: Oh, good question. 692 00:31:13,000 --> 00:31:14,041 So it's about the domain. 693 00:31:14,041 --> 00:31:17,533 If you look up at the top right now, I'm at brian-tictactoe.herokuapp.com. 694 00:31:17,533 --> 00:31:20,310 brian-tictactoe was the name of the app that I gave it 695 00:31:20,310 --> 00:31:22,020 to that just happened to be available. 696 00:31:22,020 --> 00:31:25,170 Herokuapp.com is just the default name for where 697 00:31:25,170 --> 00:31:26,490 these applications are hosted. 698 00:31:26,490 --> 00:31:29,670 But maybe you would like to host your website somewhere else, 699 00:31:29,670 --> 00:31:32,580 at like, briantictactoe.com, for instance, or some domain that you've 700 00:31:32,580 --> 00:31:34,320 purchased that you'd like to connect. 701 00:31:34,320 --> 00:31:36,570 So the way you can do that is by Heroku Settings. 702 00:31:36,570 --> 00:31:38,820 The first thing you'll need to do is actually purchase the domain, 703 00:31:38,820 --> 00:31:41,370 and there are a number of services via which you can do that. 704 00:31:41,370 --> 00:31:45,720 But once you own it, if you go to the Settings of your application, 705 00:31:45,720 --> 00:31:52,080 here in Heroku's control panel, you can just add a domain to the application. 706 00:31:52,080 --> 00:31:56,310 And if you just click that Add Domain button there, 707 00:31:56,310 --> 00:32:01,540 that will allow you to then connect that domain to the web application 708 00:32:01,540 --> 00:32:02,040 on Heroku. 709 00:32:02,040 --> 00:32:03,998 You'll have to do a little bit of configuration 710 00:32:03,998 --> 00:32:05,890 that Heroku's website will guide you through, 711 00:32:05,890 --> 00:32:09,014 but it will then allow you to connect some domain to the application that's 712 00:32:09,014 --> 00:32:09,841 running on Heroku. 713 00:32:09,841 --> 00:32:10,340 Yeah? 714 00:32:10,340 --> 00:32:13,651 AUDIENCE: So if someone typed in brian-tictactoe.herokuapp.com, 715 00:32:13,651 --> 00:32:17,451 even after you connected the domain, will it still be [INAUDIBLE]?? 716 00:32:17,451 --> 00:32:18,450 BRIAN YU: Good question. 717 00:32:18,450 --> 00:32:21,157 If someone went back to brian-tictactoe.herokuapp.com, 718 00:32:21,157 --> 00:32:21,990 would it still work? 719 00:32:21,990 --> 00:32:24,390 Yes, it probably would. 720 00:32:24,390 --> 00:32:25,680 Yeah? 721 00:32:25,680 --> 00:32:27,995 AUDIENCE: What's the file extension for Procfile? 722 00:32:27,995 --> 00:32:29,870 BRIAN YU: No file extension for the Procfile. 723 00:32:29,870 --> 00:32:31,550 Just capital P, Procfile. 724 00:32:31,550 --> 00:32:35,310 No extension necessary there. 725 00:32:35,310 --> 00:32:35,880 Other things? 726 00:32:35,880 --> 00:32:37,852 727 00:32:37,852 --> 00:32:40,560 All right, so that's deploying a web application to the internet. 728 00:32:40,560 --> 00:32:42,364 You can do this with Flask applications. 729 00:32:42,364 --> 00:32:44,280 You can do it with other applications as well. 730 00:32:44,280 --> 00:32:47,070 When we go into building React applications later on in the week, 731 00:32:47,070 --> 00:32:48,460 you can do the same thing there. 732 00:32:48,460 --> 00:32:50,070 So as you build any of your applications this week, 733 00:32:50,070 --> 00:32:52,740 if you'd like to give deploying into the internet a try, or even applications 734 00:32:52,740 --> 00:32:56,010 you build after this class or outside of this class, feel free to do so, 735 00:32:56,010 --> 00:33:01,110 and these steps should help you get up and running with that. 736 00:33:01,110 --> 00:33:07,183 Other questions about Heroku and deploying our web application that way? 737 00:33:07,183 --> 00:33:08,145 Yeah? 738 00:33:08,145 --> 00:33:12,484 AUDIENCE: Do you think that Heroku is better than the GitHub for hosting? 739 00:33:12,484 --> 00:33:13,650 BRIAN YU: Oh, good question. 740 00:33:13,650 --> 00:33:16,710 So the question's about GitHub hosting service, GitHub Pages. 741 00:33:16,710 --> 00:33:20,040 So GitHub Pages is used for serving static sites. 742 00:33:20,040 --> 00:33:22,320 For those of you who took CS50 this past semester, 743 00:33:22,320 --> 00:33:25,320 you might remember problem set 5 home page, wherein 744 00:33:25,320 --> 00:33:29,460 you were able to create, basically, an HTML CSS web page for yourself, 745 00:33:29,460 --> 00:33:31,620 about yourself, or something you're interested in. 746 00:33:31,620 --> 00:33:33,620 And then if you wanted to, we gave you an option 747 00:33:33,620 --> 00:33:34,980 to deploy that to the internet. 748 00:33:34,980 --> 00:33:38,430 And we did that by GitHub Pages, which is a service built into GitHub. 749 00:33:38,430 --> 00:33:39,180 It's free. 750 00:33:39,180 --> 00:33:42,450 And it basically lets you take a repository and turn it into a web page 751 00:33:42,450 --> 00:33:44,070 that GitHub will host for free. 752 00:33:44,070 --> 00:33:46,920 That works only for static pages, pages that 753 00:33:46,920 --> 00:33:50,430 are just static HTML CSS JavaScript. 754 00:33:50,430 --> 00:33:53,610 But it doesn't work for if you're trying to run a web server, 755 00:33:53,610 --> 00:33:56,550 so something like the Tic-Tac-Toe game that we have that 756 00:33:56,550 --> 00:33:58,950 has some backend server, where you're making requests 757 00:33:58,950 --> 00:34:01,620 to a server that's processing results and rendering templates. 758 00:34:01,620 --> 00:34:04,770 You can't run a Flask app off of GitHub Pages, for example. 759 00:34:04,770 --> 00:34:08,219 So Heroku is a little bit more flexible, in that sense, 760 00:34:08,219 --> 00:34:10,219 in that you can deploy static sites. 761 00:34:10,219 --> 00:34:13,388 You can also deploy dynamic sites that have the sort of interactivity 762 00:34:13,388 --> 00:34:15,929 that you might want, that have a server that you can talk to, 763 00:34:15,929 --> 00:34:18,762 that have a database, for instance, whereas GitHub Pages can't quite 764 00:34:18,762 --> 00:34:19,511 do that. 765 00:34:19,511 --> 00:34:20,010 Yeah? 766 00:34:20,010 --> 00:34:22,224 AUDIENCE: For the requirements.txt, do you 767 00:34:22,224 --> 00:34:25,530 need to add into that every library that you're using in your Python code? 768 00:34:25,530 --> 00:34:26,530 BRIAN YU: Good question. 769 00:34:26,530 --> 00:34:28,380 So yeah, in requirements.txt, you're going 770 00:34:28,380 --> 00:34:30,799 to need to include in it any library that you 771 00:34:30,799 --> 00:34:32,340 have installed into your Python code. 772 00:34:32,340 --> 00:34:34,350 So if you're using some external library, 773 00:34:34,350 --> 00:34:36,725 you're going to need to include that in requirements.txt. 774 00:34:36,725 --> 00:34:40,239 Otherwise, Heroku's not going to be able to know that it needs to install that 775 00:34:40,239 --> 00:34:43,080 and you're probably going to get a Module Not Found Import Error 776 00:34:43,080 --> 00:34:45,421 type of thing when you try to deploy the application. 777 00:34:45,421 --> 00:34:47,670 And if you try and deploy it and something goes wrong, 778 00:34:47,670 --> 00:34:49,670 which does happen from time to time with Heroku, 779 00:34:49,670 --> 00:34:51,544 you can always go to the logs, which show you 780 00:34:51,544 --> 00:34:53,639 the errors that have happened as you were working 781 00:34:53,639 --> 00:34:55,230 on trying to deploy the application. 782 00:34:55,230 --> 00:34:57,390 And those errors can often help you get guided 783 00:34:57,390 --> 00:35:02,191 to what it is that you need to change or fix to get it working. 784 00:35:02,191 --> 00:35:03,190 All right, other things? 785 00:35:03,190 --> 00:35:06,750 786 00:35:06,750 --> 00:35:08,770 OK, then we'll change gears here a little bit 787 00:35:08,770 --> 00:35:12,430 and move away from web programming, just for a little time, 788 00:35:12,430 --> 00:35:18,250 in order to talk about the world of artificial intelligence. 789 00:35:18,250 --> 00:35:22,690 So we've been making a Tic-Tac-Toe game so far this morning. 790 00:35:22,690 --> 00:35:24,850 So far, you've probably implemented, hopefully, 791 00:35:24,850 --> 00:35:27,850 the ability for a user to make a move, or at least an ability 792 00:35:27,850 --> 00:35:29,434 to update the board based on the move. 793 00:35:29,434 --> 00:35:32,224 Maybe you've gotten around to implementing, checking whether or not 794 00:35:32,224 --> 00:35:34,480 someone's won the game or the ability to reset a game. 795 00:35:34,480 --> 00:35:36,396 But what we'd like to do now is not just allow 796 00:35:36,396 --> 00:35:39,100 humans to play against other humans, but to allow a human 797 00:35:39,100 --> 00:35:43,390 to play against some artificial intelligence that is able to behave 798 00:35:43,390 --> 00:35:45,370 in some sort of intelligent way. 799 00:35:45,370 --> 00:35:47,800 And so what we're going to do this afternoon 800 00:35:47,800 --> 00:35:50,320 is explore one algorithm called Minimax that 801 00:35:50,320 --> 00:35:52,510 is particularly useful for two-player games, 802 00:35:52,510 --> 00:35:56,260 especially, wherein both players are trying to compete for differing 803 00:35:56,260 --> 00:35:59,380 outcomes and players need to each make moves 804 00:35:59,380 --> 00:36:03,040 based on choosing among the available moves that are there. 805 00:36:03,040 --> 00:36:05,430 And so we have here a Tic-Tac-Toe board. 806 00:36:05,430 --> 00:36:07,690 And that Tic-Tac-Toe board we can really divide 807 00:36:07,690 --> 00:36:11,290 into three possible outcomes of what can happen 808 00:36:11,290 --> 00:36:12,970 at the end of a Tic-Tac-Toe game. 809 00:36:12,970 --> 00:36:17,712 Either X wins the game or O wins the game or nobody wins the game. 810 00:36:17,712 --> 00:36:19,920 And so those are the three possible resulting states. 811 00:36:19,920 --> 00:36:22,420 And of course, there are many ways to get to those outcomes. 812 00:36:22,420 --> 00:36:26,170 There are many ways X can win, many ways O can win, many ways nobody can win. 813 00:36:26,170 --> 00:36:28,450 But those are the three possible outcomes. 814 00:36:28,450 --> 00:36:33,040 And what we're going to do is to make this into a computational-- 815 00:36:33,040 --> 00:36:35,440 you put this in computational terms, mathematical terms 816 00:36:35,440 --> 00:36:37,090 that a computer can understand. 817 00:36:37,090 --> 00:36:40,220 We're going to assign each of these possible outcomes a score. 818 00:36:40,220 --> 00:36:45,760 So if X wins, we're going to say that board has a score of 1. 819 00:36:45,760 --> 00:36:48,670 And if O wins, we're going to say that board has a score of 0, 820 00:36:48,670 --> 00:36:50,410 or a negative 1, sorry. 821 00:36:50,410 --> 00:36:55,960 And if nobody wins, tie game, we're going to say that has a score of 0, 822 00:36:55,960 --> 00:36:59,860 doesn't favor one player or the other. 823 00:36:59,860 --> 00:37:05,965 So now, if you are a computer trying to play moves for X, 824 00:37:05,965 --> 00:37:07,590 what are you trying to do to the score? 825 00:37:07,590 --> 00:37:10,994 Are you trying to maximize the score or minimize the score? 826 00:37:10,994 --> 00:37:12,910 Yeah, you want to maximize the possible score. 827 00:37:12,910 --> 00:37:15,670 If you have an option between a situation that will take you 828 00:37:15,670 --> 00:37:19,060 to a score of negative 1 and a situation that will take you to a score of 1, 829 00:37:19,060 --> 00:37:21,250 you're going to pick the one that takes you to the score of 1 830 00:37:21,250 --> 00:37:23,230 because that's the one that maximizes your score. 831 00:37:23,230 --> 00:37:25,270 And if you're the O player, you're going to want to do the opposite. 832 00:37:25,270 --> 00:37:27,250 You're going to want to try to minimize the score, 833 00:37:27,250 --> 00:37:29,541 because if you're choosing between these three options, 834 00:37:29,541 --> 00:37:32,350 you want to choose the board that has the minimum score. 835 00:37:32,350 --> 00:37:34,239 And so ultimately, in this game, X is going 836 00:37:34,239 --> 00:37:36,280 to be trying to maximize the score and O is going 837 00:37:36,280 --> 00:37:38,550 to be trying to minimize the score. 838 00:37:38,550 --> 00:37:40,960 And what the Minimax algorithm is going to do 839 00:37:40,960 --> 00:37:43,510 is it's a recursive algorithm that's going to figure out, 840 00:37:43,510 --> 00:37:45,910 what is the move that maximizes the score 841 00:37:45,910 --> 00:37:49,199 or what is the move that minimizes the score? 842 00:37:49,199 --> 00:37:51,740 Questions so far, generally speaking, about where we're going 843 00:37:51,740 --> 00:37:52,615 and what we're doing? 844 00:37:52,615 --> 00:37:55,160 845 00:37:55,160 --> 00:37:56,330 All right. 846 00:37:56,330 --> 00:37:57,570 We'll take a look at this. 847 00:37:57,570 --> 00:38:00,951 So we have a board that looks something like this. 848 00:38:00,951 --> 00:38:02,450 This is a game that's still in play. 849 00:38:02,450 --> 00:38:05,250 It's O's turn and the game is still happening. 850 00:38:05,250 --> 00:38:07,190 So nobody's won just yet. 851 00:38:07,190 --> 00:38:12,040 But what is the score of this board? 852 00:38:12,040 --> 00:38:14,590 If you're the O player, what is the score of the board? 853 00:38:14,590 --> 00:38:16,360 So think about that for a little bit. 854 00:38:16,360 --> 00:38:19,235 Nobody's won just yet, but what would you say the score of this board 855 00:38:19,235 --> 00:38:21,800 would be if you're O and you're trying to win? 856 00:38:21,800 --> 00:38:25,310 Remember, O is trying to minimize the score. 857 00:38:25,310 --> 00:38:26,960 If X wins, it's a score of 1. 858 00:38:26,960 --> 00:38:28,910 If O wins, it's a score of negative 1. 859 00:38:28,910 --> 00:38:33,540 If nobody wins, it's a score of 0. 860 00:38:33,540 --> 00:38:34,840 OK, I hear people saying 0. 861 00:38:34,840 --> 00:38:35,620 Why 0? 862 00:38:35,620 --> 00:38:40,087 Someone tell me, why is this a score of 0? 863 00:38:40,087 --> 00:38:42,670 What is the logic you went through to mentally get at the idea 864 00:38:42,670 --> 00:38:43,810 that this is a score of 0? 865 00:38:43,810 --> 00:38:44,916 Yeah? 866 00:38:44,916 --> 00:38:48,957 AUDIENCE: If it's O's turn, O is going to block X [INAUDIBLE].. 867 00:38:48,957 --> 00:38:49,790 BRIAN YU: OK, great. 868 00:38:49,790 --> 00:38:53,690 So if it's O's turn, O is going to block X, playing in the upper right corner. 869 00:38:53,690 --> 00:38:57,260 And in that case, X has to play in that top middle square. 870 00:38:57,260 --> 00:39:00,170 And in that case, nobody wins and the score is 0. 871 00:39:00,170 --> 00:39:02,870 Now, of course, O didn't have to play in the upper right. 872 00:39:02,870 --> 00:39:05,570 O could have played in the top middle, in which case 873 00:39:05,570 --> 00:39:09,110 X played in the upper right, and then X would have won the game 874 00:39:09,110 --> 00:39:11,009 and that board has a score of 1. 875 00:39:11,009 --> 00:39:12,300 And so what was the logic here? 876 00:39:12,300 --> 00:39:15,920 We had two possible options, one option that led us to a board 877 00:39:15,920 --> 00:39:19,400 with a score of 1, X winning, and one option that led us to a board 878 00:39:19,400 --> 00:39:21,440 with a score of 0, nobody winning. 879 00:39:21,440 --> 00:39:24,080 And between the two, we know that O should 880 00:39:24,080 --> 00:39:26,450 choose the option that's going to minimize, choose 881 00:39:26,450 --> 00:39:28,730 the one with the score of 0, play in the upper right, 882 00:39:28,730 --> 00:39:31,340 block X from winning the game. 883 00:39:31,340 --> 00:39:33,186 So let's formalize that a little bit. 884 00:39:33,186 --> 00:39:35,060 What are the possible moves that X can make-- 885 00:39:35,060 --> 00:39:36,920 or that O could make, for instance? 886 00:39:36,920 --> 00:39:42,530 Well, O could play in the top middle or O could play in the top right. 887 00:39:42,530 --> 00:39:44,839 Those are the two possible options for what O can do. 888 00:39:44,839 --> 00:39:47,630 And all right, let's explore what happens in each of those options. 889 00:39:47,630 --> 00:39:50,930 If O plays in the top middle, then where does X play? 890 00:39:50,930 --> 00:39:52,100 Well, only one option left. 891 00:39:52,100 --> 00:39:53,599 X is going to play in the top right. 892 00:39:53,599 --> 00:39:55,130 X is going to win that game. 893 00:39:55,130 --> 00:39:57,600 And so what score will we give to this board? 894 00:39:57,600 --> 00:39:58,281 AUDIENCE: 1. 895 00:39:58,281 --> 00:39:58,780 BRIAN YU: 1. 896 00:39:58,780 --> 00:39:59,280 Great. 897 00:39:59,280 --> 00:40:00,450 That board has a score of 1. 898 00:40:00,450 --> 00:40:02,200 And so what about the score of this board? 899 00:40:02,200 --> 00:40:06,130 If this board needs to have a score, and the only thing that can result from it 900 00:40:06,130 --> 00:40:10,170 is something with a score of 1, what score would you give this board? 901 00:40:10,170 --> 00:40:11,264 Great, also 1. 902 00:40:11,264 --> 00:40:14,430 Because once you get to this position, you're going to get to this position, 903 00:40:14,430 --> 00:40:16,050 and this board has a score of 1. 904 00:40:16,050 --> 00:40:18,779 So this board must also have a score of 1. 905 00:40:18,779 --> 00:40:20,070 So now, let's explore the side. 906 00:40:20,070 --> 00:40:21,390 O plays in the upper right. 907 00:40:21,390 --> 00:40:24,930 When that happens, X plays in the only available square, the top middle. 908 00:40:24,930 --> 00:40:27,040 And what scored does this board have? 909 00:40:27,040 --> 00:40:27,700 0, great. 910 00:40:27,700 --> 00:40:32,021 Nobody won that game so that board has a score of 0, which means this board has? 911 00:40:32,021 --> 00:40:32,520 AUDIENCE: 0. 912 00:40:32,520 --> 00:40:34,170 BRIAN YU: Great, also a score of 0. 913 00:40:34,170 --> 00:40:37,990 And so now, we get to what we could call the minimization step. 914 00:40:37,990 --> 00:40:40,410 We know that O has two options, one board that 915 00:40:40,410 --> 00:40:44,250 leads to a score of 1, 1 board that leads to a score of 0. 916 00:40:44,250 --> 00:40:45,240 What should happen? 917 00:40:45,240 --> 00:40:48,210 Well, it's going to pick the one that has the score of 0, which 918 00:40:48,210 --> 00:40:51,660 means this board also has a score of 0. 919 00:40:51,660 --> 00:40:55,290 That's the basic idea of what the Minimax algorithm is going to do. 920 00:40:55,290 --> 00:40:58,620 It's going to explore those possibilities, calculate the scores, 921 00:40:58,620 --> 00:41:01,290 and when it sees that it has multiple options, 922 00:41:01,290 --> 00:41:04,950 it's going to ask itself, which of those options is going to minimize the score, 923 00:41:04,950 --> 00:41:09,220 for the O player, at least, and then choose that option. 924 00:41:09,220 --> 00:41:09,940 Questions so far? 925 00:41:09,940 --> 00:41:13,640 926 00:41:13,640 --> 00:41:15,410 All right. 927 00:41:15,410 --> 00:41:16,440 Oh, green smiley faces. 928 00:41:16,440 --> 00:41:18,090 Wonderful. 929 00:41:18,090 --> 00:41:20,590 Let's try something a little bit more complicated. 930 00:41:20,590 --> 00:41:22,530 We've got this board now. 931 00:41:22,530 --> 00:41:24,810 This board, it's X's turn. 932 00:41:24,810 --> 00:41:29,413 And what is the score of this board if it's X's turn? 933 00:41:29,413 --> 00:41:29,959 AUDIENCE: 1. 934 00:41:29,959 --> 00:41:30,750 BRIAN YU: 1, great. 935 00:41:30,750 --> 00:41:31,250 Why? 936 00:41:31,250 --> 00:41:34,920 937 00:41:34,920 --> 00:41:37,260 So why is it a score of 1. 938 00:41:37,260 --> 00:41:38,610 AUDIENCE: X can win. 939 00:41:38,610 --> 00:41:39,330 BRIAN YU: X can win right away. 940 00:41:39,330 --> 00:41:42,180 X can play in the upper right-hand corner and X is going to win this game. 941 00:41:42,180 --> 00:41:43,380 But how would a computer know that? 942 00:41:43,380 --> 00:41:45,340 How would a computer be able to figure that out? 943 00:41:45,340 --> 00:41:47,506 Well first, it needs to consider the possible moves. 944 00:41:47,506 --> 00:41:49,860 Well, X could play in the lower left. 945 00:41:49,860 --> 00:41:52,780 A computer doesn't know that it shouldn't play in the lower left. 946 00:41:52,780 --> 00:41:54,480 So it needs to explore that possibility. 947 00:41:54,480 --> 00:41:55,570 X plays in the lower left. 948 00:41:55,570 --> 00:41:56,730 OK, what can O do next? 949 00:41:56,730 --> 00:42:01,050 Well, O can play there in the top middle, in which case 950 00:42:01,050 --> 00:42:02,560 X plays in the top right. 951 00:42:02,560 --> 00:42:04,230 And all right, X won there. 952 00:42:04,230 --> 00:42:06,370 So what score would you give this board? 953 00:42:06,370 --> 00:42:07,110 1, great. 954 00:42:07,110 --> 00:42:09,870 So this board also has a score of 1. 955 00:42:09,870 --> 00:42:12,290 But O didn't have to play in there. 956 00:42:12,290 --> 00:42:16,097 O could play in the top right, in which case X plays in the top middle, 957 00:42:16,097 --> 00:42:17,430 and this board has a score of 0. 958 00:42:17,430 --> 00:42:20,954 Nobody wins, which means this board also has a score of 0. 959 00:42:20,954 --> 00:42:22,620 And so now, here's the interesting step. 960 00:42:22,620 --> 00:42:25,290 The Minimax algorithm is recursive, in the sense 961 00:42:25,290 --> 00:42:29,400 that when X is trying to make a decision about what move to make there, 962 00:42:29,400 --> 00:42:32,010 it needs to think about what moves should O 963 00:42:32,010 --> 00:42:34,710 make if O ends up in this board? 964 00:42:34,710 --> 00:42:38,310 And if O ends up in this board, well, between the options of 0 and 1, 965 00:42:38,310 --> 00:42:40,620 O is going to try to minimize the score. 966 00:42:40,620 --> 00:42:43,530 So O is going to say, all right, this is the board that 967 00:42:43,530 --> 00:42:46,860 gives me the minimum score, so I should play in the upper right corner. 968 00:42:46,860 --> 00:42:50,030 And so that board also has a score of 0. 969 00:42:50,030 --> 00:42:53,090 So in other words, if X chooses to play in the lower left, 970 00:42:53,090 --> 00:42:54,890 then if both players are playing optimally, 971 00:42:54,890 --> 00:42:56,141 that game is going to be tied. 972 00:42:56,141 --> 00:42:57,973 And we're able to calculate that recursively 973 00:42:57,973 --> 00:42:59,270 by thinking, what would O do? 974 00:42:59,270 --> 00:43:00,080 What would X do? 975 00:43:00,080 --> 00:43:02,134 Move after move after move. 976 00:43:02,134 --> 00:43:03,800 All right, so X plays in the lower left. 977 00:43:03,800 --> 00:43:05,480 That results in a score of 0. 978 00:43:05,480 --> 00:43:06,800 What else could X do? 979 00:43:06,800 --> 00:43:09,394 X could play in the top middle. 980 00:43:09,394 --> 00:43:10,310 But what happens then? 981 00:43:10,310 --> 00:43:12,695 What's the score of this board? 982 00:43:12,695 --> 00:43:13,570 AUDIENCE: Negative 1. 983 00:43:13,570 --> 00:43:14,620 BRIAN YU: Negative 1, great. 984 00:43:14,620 --> 00:43:16,210 Because what are the possible options? 985 00:43:16,210 --> 00:43:19,540 O could play in the lower left, winning immediately, a score of negative 1. 986 00:43:19,540 --> 00:43:21,550 Or O could play in the upper right and that 987 00:43:21,550 --> 00:43:25,400 would result in a tied game, a score of 0, which means a score of 0 up here. 988 00:43:25,400 --> 00:43:27,400 But that means that if O gets into this position 989 00:43:27,400 --> 00:43:30,580 and is trying to minimize the score, between 0 and negative 1, 990 00:43:30,580 --> 00:43:34,300 O is always going to pick this option, the option that minimizes the score. 991 00:43:34,300 --> 00:43:36,372 So that board has a score of negative 1 as well. 992 00:43:36,372 --> 00:43:38,830 And then, of course, the final one, the one that all of you 993 00:43:38,830 --> 00:43:41,110 probably saw immediately, obviously and intuitively, 994 00:43:41,110 --> 00:43:44,110 but that a computer doesn't have any way of having some intuition about, 995 00:43:44,110 --> 00:43:46,300 needs to explore the possible options first, 996 00:43:46,300 --> 00:43:49,180 is just to say, all right, in the upper right, in that case, 997 00:43:49,180 --> 00:43:50,260 X has won the game. 998 00:43:50,260 --> 00:43:51,524 That has a score of 1. 999 00:43:51,524 --> 00:43:53,440 And so between those three options, the option 1000 00:43:53,440 --> 00:43:56,200 of a score of 0, negative 1, and 1, we should choose 1001 00:43:56,200 --> 00:43:58,084 the option that maximizes the score. 1002 00:43:58,084 --> 00:43:59,500 We should play in the upper right. 1003 00:43:59,500 --> 00:44:05,440 And so that board up at the top, we can conclude, has a score of 1. 1004 00:44:05,440 --> 00:44:09,130 So a lot of calculation to get to what was intuition for us, the idea 1005 00:44:09,130 --> 00:44:10,977 that board up top has a score of 1. 1006 00:44:10,977 --> 00:44:13,060 And we can get at that by recursively calculating. 1007 00:44:13,060 --> 00:44:14,840 What's the best move in this position? 1008 00:44:14,840 --> 00:44:17,690 What's the best move after that? 1009 00:44:17,690 --> 00:44:18,290 Questions? 1010 00:44:18,290 --> 00:44:18,947 Yeah? 1011 00:44:18,947 --> 00:44:22,426 AUDIENCE: So are you using recursion on, like, two functions? 1012 00:44:22,426 --> 00:44:25,905 If you're going to implement it, do you have-- 1013 00:44:25,905 --> 00:44:29,714 do you have like X's best position and then [INAUDIBLE] that position, 1014 00:44:29,714 --> 00:44:33,921 and then [INAUDIBLE] the X function to call O for the next step? 1015 00:44:33,921 --> 00:44:35,170 BRIAN YU: Yeah, good question. 1016 00:44:35,170 --> 00:44:37,294 So the question's about actually implementing this. 1017 00:44:37,294 --> 00:44:39,540 We'll take a look at some pseudocode in a moment. 1018 00:44:39,540 --> 00:44:41,920 But generally speaking, there are a couple ways you could do this. 1019 00:44:41,920 --> 00:44:44,400 You could have two different functions, one that's doing maximizing, 1020 00:44:44,400 --> 00:44:45,660 one that's doing minimizing. 1021 00:44:45,660 --> 00:44:48,550 But the code is really, very similar. 1022 00:44:48,550 --> 00:44:52,740 So what you probably want to do is have a function that's going to optimize 1023 00:44:52,740 --> 00:44:55,350 and one of the arguments, maybe a Boolean flag that says, 1024 00:44:55,350 --> 00:44:57,600 should I maximize this or should I minimize this? 1025 00:44:57,600 --> 00:45:00,990 And if I'm maximizing it, then when I consider the next player's moves, 1026 00:45:00,990 --> 00:45:03,100 I'm going to say, OK, try and minimize it now. 1027 00:45:03,100 --> 00:45:05,160 And if I'm currently trying to minimize my score, 1028 00:45:05,160 --> 00:45:06,600 when I'm considering my opponent's moves, 1029 00:45:06,600 --> 00:45:09,180 I'll say, OK, what should happen if you try to maximize that score? 1030 00:45:09,180 --> 00:45:11,846 So it just sort of flips back and forth, one move after another, 1031 00:45:11,846 --> 00:45:15,280 if you go between one player's turn and the other. 1032 00:45:15,280 --> 00:45:16,430 Other Questions? 1033 00:45:16,430 --> 00:45:17,670 Yeah? 1034 00:45:17,670 --> 00:45:21,690 AUDIENCE: I'm assuming there's situations where the next step is 1035 00:45:21,690 --> 00:45:23,895 two equally good options. 1036 00:45:23,895 --> 00:45:28,610 1037 00:45:28,610 --> 00:45:30,470 How are the [? AIGs, ?] in that case? 1038 00:45:30,470 --> 00:45:31,720 BRIAN YU: Yeah, good question. 1039 00:45:31,720 --> 00:45:34,060 What happens if there are two equally good options, two options that 1040 00:45:34,060 --> 00:45:35,200 both have the same score? 1041 00:45:35,200 --> 00:45:36,610 In that case, the [? I ?] doesn't really care. 1042 00:45:36,610 --> 00:45:37,450 You can pick the first one. 1043 00:45:37,450 --> 00:45:38,533 You can pick a random one. 1044 00:45:38,533 --> 00:45:40,357 You can pick whatever you want. 1045 00:45:40,357 --> 00:45:42,190 So certainly, that's something you could do. 1046 00:45:42,190 --> 00:45:45,370 Now, there are ways you can make modifications to the scoring system. 1047 00:45:45,370 --> 00:45:48,400 It all really boils down to what the scoring system is, whereby 1048 00:45:48,400 --> 00:45:51,880 right now, winning is a score of 1 for X. Losing for X 1049 00:45:51,880 --> 00:45:54,130 is a score of negative 1, and 0 is neutral. 1050 00:45:54,130 --> 00:45:56,800 You can imagine a situation where you would 1051 00:45:56,800 --> 00:46:01,060 give more points for winning faster, where if you can win in fewer moves, 1052 00:46:01,060 --> 00:46:02,230 then you should prefer that. 1053 00:46:02,230 --> 00:46:04,938 Right now, this algorithm doesn't care about how quickly you win. 1054 00:46:04,938 --> 00:46:06,970 So even if there are two in a row, if you 1055 00:46:06,970 --> 00:46:08,860 have some other way of guaranteeing that you'll win the game, 1056 00:46:08,860 --> 00:46:10,540 you might do something else instead. 1057 00:46:10,540 --> 00:46:15,030 And the algorithm could very reasonably choose that, and that's to be expected. 1058 00:46:15,030 --> 00:46:17,500 But if you want to make it so that if you can win faster, 1059 00:46:17,500 --> 00:46:19,297 you'll win faster, than you want to encode, 1060 00:46:19,297 --> 00:46:21,130 somewhere in the scoring system, some notion 1061 00:46:21,130 --> 00:46:26,460 of if you're winning in fewer moves, that's preferable. 1062 00:46:26,460 --> 00:46:28,760 Other things, questions? 1063 00:46:28,760 --> 00:46:31,724 How do we feel about the general idea of what this algorithm is doing? 1064 00:46:31,724 --> 00:46:35,210 1065 00:46:35,210 --> 00:46:37,230 OK, some green, some yellow. 1066 00:46:37,230 --> 00:46:41,180 Happy to slow down and take questions if there are any. 1067 00:46:41,180 --> 00:46:44,097 Otherwise, we can definitely chat about this during project time, too. 1068 00:46:44,097 --> 00:46:46,763 All right, let's take a look at actually some of the pseudocode, 1069 00:46:46,763 --> 00:46:48,550 some code we could actually write in order 1070 00:46:48,550 --> 00:46:51,050 to implement an algorithm like this. 1071 00:46:51,050 --> 00:46:53,020 So we're going to do Python-like code. 1072 00:46:53,020 --> 00:46:55,561 This isn't exact code, so don't try and type this into Python 1073 00:46:55,561 --> 00:46:56,620 and expect it to work. 1074 00:46:56,620 --> 00:46:59,411 But this will give you the general idea of what we're trying to do. 1075 00:46:59,411 --> 00:47:04,302 We're trying to Minimax a particular game based on whose turn it is. 1076 00:47:04,302 --> 00:47:06,760 So the first thing we need to know is, if the game is over, 1077 00:47:06,760 --> 00:47:10,630 if someone's already won the game, then just return the score for the game. 1078 00:47:10,630 --> 00:47:13,034 If no moves are possible, someone's already won the game, 1079 00:47:13,034 --> 00:47:14,200 then the score is finalized. 1080 00:47:14,200 --> 00:47:16,630 There is no option, no decision points to be made. 1081 00:47:16,630 --> 00:47:17,444 The game is over. 1082 00:47:17,444 --> 00:47:18,610 So there already is a score. 1083 00:47:18,610 --> 00:47:21,370 That's our base case for when the game's over that's going to, 1084 00:47:21,370 --> 00:47:23,579 ultimately, have some sort of score. 1085 00:47:23,579 --> 00:47:25,370 But then we need to say, all right, we need 1086 00:47:25,370 --> 00:47:27,704 to figure out what the available moves are for the game. 1087 00:47:27,704 --> 00:47:30,411 In the case of Tic-Tac-Toe, that's as simple as just looking for, 1088 00:47:30,411 --> 00:47:31,700 what are the empty squares? 1089 00:47:31,700 --> 00:47:33,410 But it's important to just look for the empty squares 1090 00:47:33,410 --> 00:47:35,826 because you don't want to consider moving into places that 1091 00:47:35,826 --> 00:47:38,630 are illegal moves, moves that there already is an X or an O 1092 00:47:38,630 --> 00:47:39,480 there, for instance. 1093 00:47:39,480 --> 00:47:43,210 You want to consider only the available moves for the game. 1094 00:47:43,210 --> 00:47:48,230 And then we'll say, OK, if it's X's turn, what should we do? 1095 00:47:48,230 --> 00:47:51,480 If it's X's turn, we want to maximize the score. 1096 00:47:51,480 --> 00:47:53,360 And so if we want to maximize the score, we 1097 00:47:53,360 --> 00:47:56,644 should start by assuming that the value is as small as possible. 1098 00:47:56,644 --> 00:47:59,560 So we're going to set the value to be negative infinity, for instance, 1099 00:47:59,560 --> 00:48:01,995 or negative some really big number. 1100 00:48:01,995 --> 00:48:04,370 And then we're going to say, OK, for every possible move, 1101 00:48:04,370 --> 00:48:06,950 let's consider that possible move. 1102 00:48:06,950 --> 00:48:13,230 The new value of this board is going to be the maximum of the current value, 1103 00:48:13,230 --> 00:48:16,460 which starts out as negative infinity, and whatever the score of the board 1104 00:48:16,460 --> 00:48:21,320 would be for if you were to make that move and it were O's turn. 1105 00:48:21,320 --> 00:48:25,280 So this is the real critical piece of the logic, these last two lines here, 1106 00:48:25,280 --> 00:48:28,740 the idea that for every possible move that X can make, 1107 00:48:28,740 --> 00:48:31,250 let's consider, what would the score of that move 1108 00:48:31,250 --> 00:48:34,580 be if you were to make that move and then let O play? 1109 00:48:34,580 --> 00:48:37,490 Let 0 play optimally and see what the score of that would be. 1110 00:48:37,490 --> 00:48:40,820 Take all of those scores and take the maximum of all of them, 1111 00:48:40,820 --> 00:48:44,879 because X wants to maximize the total possible score. 1112 00:48:44,879 --> 00:48:47,420 I'll say that again because I know it's little bit confusing. 1113 00:48:47,420 --> 00:48:50,502 We start by assuming the value is really, really low, because we're 1114 00:48:50,502 --> 00:48:51,710 trying to maximize the score. 1115 00:48:51,710 --> 00:48:53,330 We want to increase the score. 1116 00:48:53,330 --> 00:48:56,240 And then consider all the possible moves we can make and take 1117 00:48:56,240 --> 00:48:58,790 the maximum of the value of all those possible moves. 1118 00:48:58,790 --> 00:49:01,280 And how do we figure out the value of those possible moves? 1119 00:49:01,280 --> 00:49:04,380 Well, we recursively call the Minimax algorithm again, 1120 00:49:04,380 --> 00:49:08,240 considering the game board with that move having been made, 1121 00:49:08,240 --> 00:49:10,157 and then say, it's O's turn now and O is going 1122 00:49:10,157 --> 00:49:12,365 to try and do something a little bit different, which 1123 00:49:12,365 --> 00:49:13,550 we'll see in just a moment. 1124 00:49:13,550 --> 00:49:17,460 Because now else, if it's O's turn, 0 is going to do the exact opposite. 1125 00:49:17,460 --> 00:49:19,211 It's trying to minimize the score. 1126 00:49:19,211 --> 00:49:21,710 So let's start by assuming the value is really, really high, 1127 00:49:21,710 --> 00:49:23,570 some really, really big thing. 1128 00:49:23,570 --> 00:49:27,350 And then for every possible move, the value of this position 1129 00:49:27,350 --> 00:49:31,910 is the minimum of all of the possible moves that you could make, 1130 00:49:31,910 --> 00:49:34,180 and then assuming that it's X's turn to move. 1131 00:49:34,180 --> 00:49:36,740 And so these functions will recursively call each other. 1132 00:49:36,740 --> 00:49:38,210 First, it'll be X's turn. 1133 00:49:38,210 --> 00:49:40,310 Then it'll consider Minimax, where it's O's turn. 1134 00:49:40,310 --> 00:49:43,400 And that will consider situations where it's X's turn, going down and down 1135 00:49:43,400 --> 00:49:46,220 and down and down, considering all possible options 1136 00:49:46,220 --> 00:49:47,690 to be able to play optimally. 1137 00:49:47,690 --> 00:49:50,390 Now, this works for a game like Tic-Tac-Toe, 1138 00:49:50,390 --> 00:49:54,081 but is not going to work as well if you consider more complex games, where 1139 00:49:54,081 --> 00:49:55,330 there are more possible moves. 1140 00:49:55,330 --> 00:49:58,070 If you try and do this on a game like chess, for instance, 1141 00:49:58,070 --> 00:50:00,111 the algorithm is just going to take ages in order 1142 00:50:00,111 --> 00:50:01,430 to figure out the optimal move. 1143 00:50:01,430 --> 00:50:03,290 And so to be able to play games like that, 1144 00:50:03,290 --> 00:50:05,780 you need to employ some more advanced techniques. 1145 00:50:05,780 --> 00:50:07,940 But this is probably one of the simpler ways 1146 00:50:07,940 --> 00:50:11,990 to think about how to pick the best move out of a set of possible moves. 1147 00:50:11,990 --> 00:50:14,070 Then at the end, you return the value. 1148 00:50:14,070 --> 00:50:16,070 In other words, what is the score of this board? 1149 00:50:16,070 --> 00:50:18,736 That will tell you the ultimate score of the board, whether it's 1150 00:50:18,736 --> 00:50:23,036 a winning board, a losing board, or a neutral board, in which nobody can win. 1151 00:50:23,036 --> 00:50:25,410 This algorithm will just give you the score of the board. 1152 00:50:25,410 --> 00:50:28,010 Is it a win for X, win for O, or nobody wins? 1153 00:50:28,010 --> 00:50:29,850 If you wanted to get the actual best move 1154 00:50:29,850 --> 00:50:33,260 you should make, then what you care about is, which of these moves, 1155 00:50:33,260 --> 00:50:35,834 in this list of moves, is going to produce the maximum score? 1156 00:50:35,834 --> 00:50:38,000 And you can think about adding a little bit of logic 1157 00:50:38,000 --> 00:50:42,110 there in order to keep track of what the best possible move so far is, such 1158 00:50:42,110 --> 00:50:46,670 that you can then later use that move in order to figure out what move to make. 1159 00:50:46,670 --> 00:50:47,170 Questions? 1160 00:50:47,170 --> 00:50:47,794 Yeah? 1161 00:50:47,794 --> 00:50:50,264 AUDIENCE: Does value have to be negative or positive? 1162 00:50:50,264 --> 00:50:54,220 Because couldn't it just be negative 1 or negative 2 or postive 2? 1163 00:50:54,220 --> 00:50:55,390 BRIAN YU: Good question. 1164 00:50:55,390 --> 00:50:58,360 So the question is, couldn't value just being negative 2 or positive 2, 1165 00:50:58,360 --> 00:51:00,100 or even negative 1 and 1? 1166 00:51:00,100 --> 00:51:03,940 In the case of Tic-Tac-Toe, yes, where in this game, 1167 00:51:03,940 --> 00:51:05,920 scores are ranging from negative 1 to 1. 1168 00:51:05,920 --> 00:51:08,020 You can imagine, though, that if you were to generalize this 1169 00:51:08,020 --> 00:51:09,880 to other games, where scores could be higher 1170 00:51:09,880 --> 00:51:14,920 or lower, that the maximum and minimum scores could be beyond that. 1171 00:51:14,920 --> 00:51:16,480 For Tic-Tac-Toe, though, absolutely. 1172 00:51:16,480 --> 00:51:19,330 If we're only considering score within the range of negative 1 to 1, 1173 00:51:19,330 --> 00:51:22,390 you can use negative 1 and 1 in place of negative infinity 1174 00:51:22,390 --> 00:51:23,870 and positive infinity. 1175 00:51:23,870 --> 00:51:24,467 Yeah? 1176 00:51:24,467 --> 00:51:27,341 AUDIENCE: Wouldn't you get error message because you can never really 1177 00:51:27,341 --> 00:51:31,130 reach infinity, so that would count for infinity? 1178 00:51:31,130 --> 00:51:32,609 BRIAN YU: Oh, good question. 1179 00:51:32,609 --> 00:51:34,400 Wouldn't you get some kind of error message 1180 00:51:34,400 --> 00:51:37,610 if you tried to encode infinity into the program? 1181 00:51:37,610 --> 00:51:39,480 What exactly is happening there? 1182 00:51:39,480 --> 00:51:40,670 An excellent question. 1183 00:51:40,670 --> 00:51:44,330 While you can't actually have an infinity, Python, and many languages, 1184 00:51:44,330 --> 00:51:47,180 have a value that can sort of simulate infinity. 1185 00:51:47,180 --> 00:51:49,670 In Python, it's inside the Map library, and I 1186 00:51:49,670 --> 00:51:52,580 think it's called map.inf for infinity. 1187 00:51:52,580 --> 00:51:55,610 It's just a value that represents the idea of infinity. 1188 00:51:55,610 --> 00:51:57,780 And it obeys mathematical properties. 1189 00:51:57,780 --> 00:52:01,570 So if I say, is math.inf greater than 28? 1190 00:52:01,570 --> 00:52:03,500 Well, yeah, true. math.inf is greater than 28 1191 00:52:03,500 --> 00:52:05,900 because infinity is bigger than any conceivable number. 1192 00:52:05,900 --> 00:52:10,975 But if I take the minimum of 50 and math.inf, that's going to give me 50. 1193 00:52:10,975 --> 00:52:13,850 Because if you try and take the minimum of 50 and an infinite number, 1194 00:52:13,850 --> 00:52:16,130 50 is the smaller one between the two of them. 1195 00:52:16,130 --> 00:52:19,880 So math.inf is a value you can use to stand in for infinity, at least 1196 00:52:19,880 --> 00:52:23,660 in Python, and that will behave the way you would expect infinity 1197 00:52:23,660 --> 00:52:25,060 to behave, for instance. 1198 00:52:25,060 --> 00:52:30,384 1199 00:52:30,384 --> 00:52:31,550 Questions about any of that? 1200 00:52:31,550 --> 00:52:35,915 1201 00:52:35,915 --> 00:52:36,885 Yeah? 1202 00:52:36,885 --> 00:52:38,340 AUDIENCE: [INAUDIBLE]. 1203 00:52:38,340 --> 00:52:43,905 1204 00:52:43,905 --> 00:52:44,530 BRIAN YU: Yeah. 1205 00:52:44,530 --> 00:52:48,350 So the idea here is that if I am the X player 1206 00:52:48,350 --> 00:52:52,640 and I'm trying to maximize the score, I care about which of my possible moves 1207 00:52:52,640 --> 00:52:54,170 is going to maximize my score. 1208 00:52:54,170 --> 00:52:58,336 So imagine for a moment that-- 1209 00:52:58,336 --> 00:52:59,710 let's just open up a text editor. 1210 00:52:59,710 --> 00:53:03,220 1211 00:53:03,220 --> 00:53:07,390 So if I have three possible moves, one of which 1212 00:53:07,390 --> 00:53:11,290 leads me to a score of 0, one of which leads me to a score of 0, 1213 00:53:11,290 --> 00:53:14,740 and one of which leads me to a score of 1, 1214 00:53:14,740 --> 00:53:18,970 if I start off with a value of negative infinity, 1215 00:53:18,970 --> 00:53:20,950 the first thing I'm going to do is say, let 1216 00:53:20,950 --> 00:53:24,250 me consider the first move, the move that has a score of 0. 1217 00:53:24,250 --> 00:53:26,800 And value is going to be set to-- 1218 00:53:26,800 --> 00:53:28,660 I'm trying to maximize my score-- 1219 00:53:28,660 --> 00:53:33,240 the maximum of the current value, negative infinity, and 0. 1220 00:53:33,240 --> 00:53:36,070 And the maximum of negative infinity and 0 with 0, because 0 1221 00:53:36,070 --> 00:53:38,120 is bigger than negative infinity. 1222 00:53:38,120 --> 00:53:39,760 Now, I consider the second move. 1223 00:53:39,760 --> 00:53:43,600 Well, value is going to be the maximum of 0, the current score, 1224 00:53:43,600 --> 00:53:45,129 and the new score is 0. 1225 00:53:45,129 --> 00:53:46,420 And OK, there is no difference. 1226 00:53:46,420 --> 00:53:48,530 It doesn't matter whether I pick the first move or the second move, 1227 00:53:48,530 --> 00:53:50,230 so the value of this is 0. 1228 00:53:50,230 --> 00:53:53,420 And then finally, I consider the last move that has a score of 1. 1229 00:53:53,420 --> 00:53:56,770 So this is going to be max of 0 and 1. 1230 00:53:56,770 --> 00:53:59,520 And between those two, the maximum of those is 1. 1231 00:53:59,520 --> 00:54:01,270 So ultimately, this tells me that I should 1232 00:54:01,270 --> 00:54:03,250 be choosing the last move because that's the one that's 1233 00:54:03,250 --> 00:54:04,700 going to maximize the score. 1234 00:54:04,700 --> 00:54:08,260 So if I just keep taking the max over all of the possible moves I can make, 1235 00:54:08,260 --> 00:54:12,580 eventually, I'll end up with the maximum possible score that I can have. 1236 00:54:12,580 --> 00:54:14,940 Good question. 1237 00:54:14,940 --> 00:54:15,440 Yeah? 1238 00:54:15,440 --> 00:54:17,940 AUDIENCE: So if you're writing [INAUDIBLE] or something bit 1239 00:54:17,940 --> 00:54:18,845 more complicated, you're also going to have 1240 00:54:18,845 --> 00:54:20,719 to take into account multiple scenarios where 1241 00:54:20,719 --> 00:54:23,670 you can end up with a score-- you'd end up with a score of 1. 1242 00:54:23,670 --> 00:54:27,170 You'd need some way to decide between them. 1243 00:54:27,170 --> 00:54:28,170 BRIAN YU: Good question. 1244 00:54:28,170 --> 00:54:31,080 Yes, you ultimately need some way to decide between if you 1245 00:54:31,080 --> 00:54:32,910 have multiple things of the same score. 1246 00:54:32,910 --> 00:54:36,150 Likely, however you choose to implement that will have some ways by default, 1247 00:54:36,150 --> 00:54:37,500 going to handle that situation. 1248 00:54:37,500 --> 00:54:39,857 Maybe you're just taking the first one or the last one 1249 00:54:39,857 --> 00:54:41,940 is probably going to be the most common situation. 1250 00:54:41,940 --> 00:54:44,980 The algorithm doesn't really care which of those you pick. 1251 00:54:44,980 --> 00:54:45,940 Yeah? 1252 00:54:45,940 --> 00:54:48,820 AUDIENCE: What method describe this algorithm [INAUDIBLE]?? 1253 00:54:48,820 --> 00:54:52,681 1254 00:54:52,681 --> 00:54:53,680 BRIAN YU: Good question. 1255 00:54:53,680 --> 00:54:55,430 So what makes this artificial intelligence 1256 00:54:55,430 --> 00:54:56,860 instead of just brute force? 1257 00:54:56,860 --> 00:54:59,517 This is just a brute force search. 1258 00:54:59,517 --> 00:55:01,600 But artificial intelligence is generally described 1259 00:55:01,600 --> 00:55:04,150 as just the ability of machines to be able to make decisions 1260 00:55:04,150 --> 00:55:07,510 that we would consider to be intelligent decisions, intelligent or smart 1261 00:55:07,510 --> 00:55:08,290 decisions. 1262 00:55:08,290 --> 00:55:11,206 And this is an example of what we might call a search algorithm, which 1263 00:55:11,206 --> 00:55:14,059 is one of the basic algorithms used in AI, this idea of trying 1264 00:55:14,059 --> 00:55:15,850 to search through a space of possible moves 1265 00:55:15,850 --> 00:55:19,570 to figure out what the best possible move is. 1266 00:55:19,570 --> 00:55:21,880 And of course, this is probably just only 1267 00:55:21,880 --> 00:55:24,400 scratching the surface of what artificial intelligence is 1268 00:55:24,400 --> 00:55:25,642 really about. 1269 00:55:25,642 --> 00:55:28,350 Then you later can get into more sophisticated search algorithms, 1270 00:55:28,350 --> 00:55:32,206 get into heuristics and other algorithms, like A star, and so forth. 1271 00:55:32,206 --> 00:55:35,080 There are more ways to make this even more efficient, instead of just 1272 00:55:35,080 --> 00:55:35,980 searching everything. 1273 00:55:35,980 --> 00:55:37,780 This is just giving you a little bit of a taste. 1274 00:55:37,780 --> 00:55:39,520 If you're interested in artificial intelligence, 1275 00:55:39,520 --> 00:55:42,130 this stuff seems cool to you and you'd like to do more of it, 1276 00:55:42,130 --> 00:55:44,088 if you're a student here at Harvard, I'd highly 1277 00:55:44,088 --> 00:55:46,900 recommend CS182, the artificial intelligence class, 1278 00:55:46,900 --> 00:55:48,910 which begins with stuff like this and dives 1279 00:55:48,910 --> 00:55:52,330 in and goes even further into looking at how to program even more 1280 00:55:52,330 --> 00:55:53,914 sophisticated artificial intelligence. 1281 00:55:53,914 --> 00:55:56,538 I'm happy to chat with you more about that during project time, 1282 00:55:56,538 --> 00:55:57,620 if you'd like. 1283 00:55:57,620 --> 00:56:01,920 But this is just scratching the surface, in short. 1284 00:56:01,920 --> 00:56:02,860 Other things? 1285 00:56:02,860 --> 00:56:07,570 1286 00:56:07,570 --> 00:56:10,720 OK, well with our remaining time, I thought I'd propose a couple of things 1287 00:56:10,720 --> 00:56:12,340 that you can try to do. 1288 00:56:12,340 --> 00:56:14,709 So let's continue working on our Tic-Tac-Toe projects. 1289 00:56:14,709 --> 00:56:16,750 If you're still working on making moves and being 1290 00:56:16,750 --> 00:56:18,610 able to detect whether someone's won the game, 1291 00:56:18,610 --> 00:56:20,080 feel free to keep working on that. 1292 00:56:20,080 --> 00:56:22,420 But then consider adding some additional features. 1293 00:56:22,420 --> 00:56:24,710 Add the ability to reset the game, for instance. 1294 00:56:24,710 --> 00:56:27,910 If you're looking for something a little bit sort of intermediate step 1295 00:56:27,910 --> 00:56:30,790 to be able to do, consider adding move history, keeping track 1296 00:56:30,790 --> 00:56:34,330 of the history of the move that you make, such that you can undo a move, 1297 00:56:34,330 --> 00:56:35,480 for instance. 1298 00:56:35,480 --> 00:56:38,530 And if you're really feeling up to the challenge-- this is going to be, 1299 00:56:38,530 --> 00:56:41,030 I will warn, a little bit challenging, especially at first-- 1300 00:56:41,030 --> 00:56:43,321 if you really are up for it, try and implement a button 1301 00:56:43,321 --> 00:56:45,280 like let the computer make a move for me that 1302 00:56:45,280 --> 00:56:47,695 is going to play the optimal move in a given situation. 1303 00:56:47,695 --> 00:56:49,820 So you can think about how you can do that as well. 1304 00:56:49,820 --> 00:56:51,250 If you'd like to add to the game in other ways, 1305 00:56:51,250 --> 00:56:52,541 you're welcome to do that, too. 1306 00:56:52,541 --> 00:56:55,405 I'll show you what a finished product might look like. 1307 00:56:55,405 --> 00:56:58,030 Certainly, you can feel free to play with the styling of things 1308 00:56:58,030 --> 00:57:00,910 in order to make things look a little nicer. 1309 00:57:00,910 --> 00:57:05,042 I'll go ahead and run Tic-Tac-Toe, too, and go here. 1310 00:57:05,042 --> 00:57:07,000 All right, I've got a Tic-Tac-Toe game, whereby 1311 00:57:07,000 --> 00:57:10,117 the X player can play a move somewhere and the O player 1312 00:57:10,117 --> 00:57:11,200 can play a move somewhere. 1313 00:57:11,200 --> 00:57:13,810 And if the O player decides, OK wait, I didn't like that move, 1314 00:57:13,810 --> 00:57:17,405 you might consider adding an Undue move button that just undoes that move. 1315 00:57:17,405 --> 00:57:19,780 And maybe that Undue move button can work multiple times, 1316 00:57:19,780 --> 00:57:22,630 such that if I get to this position and X wants to undo their move, 1317 00:57:22,630 --> 00:57:25,590 you can click Undo again, get back to the starting position. 1318 00:57:25,590 --> 00:57:29,710 And you can also consider adding situations where if X goes here and O 1319 00:57:29,710 --> 00:57:33,220 goes here, what should X do in order to win the game? 1320 00:57:33,220 --> 00:57:36,262 Anyone know, in a situation like this, what the optimal move for X is? 1321 00:57:36,262 --> 00:57:37,650 AUDIENCE: Playing in a corner. 1322 00:57:37,650 --> 00:57:38,400 BRIAN YU: Playing in a corner. 1323 00:57:38,400 --> 00:57:39,360 Yeah, probably. 1324 00:57:39,360 --> 00:57:41,010 So we'll let the computer make a move. 1325 00:57:41,010 --> 00:57:42,690 And all right, it played in the corner. 1326 00:57:42,690 --> 00:57:43,481 I can try to block. 1327 00:57:43,481 --> 00:57:44,400 I'll play here. 1328 00:57:44,400 --> 00:57:46,108 I'll let the computer make the next move. 1329 00:57:46,108 --> 00:57:47,520 All right, it moved there. 1330 00:57:47,520 --> 00:57:49,570 And now, there's really no way for O to win at this point. 1331 00:57:49,570 --> 00:57:51,944 I can try playing here, but let the computer make a move. 1332 00:57:51,944 --> 00:57:54,796 And OK, X has won this game. 1333 00:57:54,796 --> 00:57:57,330 So a lot of possible features you have to implement. 1334 00:57:57,330 --> 00:58:00,700 You definitely don't have to do the Minimax AI step if you don't want to, 1335 00:58:00,700 --> 00:58:02,700 because it is a little bit involved, but thought 1336 00:58:02,700 --> 00:58:05,070 I'd introduce the algorithm so you can try it, if you would like to. 1337 00:58:05,070 --> 00:58:06,150 But we'll open it up. 1338 00:58:06,150 --> 00:58:06,900 It's flexible. 1339 00:58:06,900 --> 00:58:08,150 Feel free to try any of these. 1340 00:58:08,150 --> 00:58:10,320 If you have a project of your own in mind that you'd like to work on, 1341 00:58:10,320 --> 00:58:11,612 feel free to work on that, too. 1342 00:58:11,612 --> 00:58:14,070 And what I think we'll do is we'll take the middle section. 1343 00:58:14,070 --> 00:58:16,170 If you're in the front half of the middle section, 1344 00:58:16,170 --> 00:58:17,550 go ahead and go to room 136. 1345 00:58:17,550 --> 00:58:20,490 If you're in the back half of the middle section, go to room 212. 1346 00:58:20,490 --> 00:58:22,540 And we'll have the two section on the side stay 1347 00:58:22,540 --> 00:58:24,356 in the auditorium for the time being. 1348 00:58:24,356 --> 00:58:25,980 We'll work on project time between now. 1349 00:58:25,980 --> 00:58:28,080 Feel free to work until around 5:00 or so. 1350 00:58:28,080 --> 00:58:30,900 The staff will be here till 5:00, and we'll reconvene here tomorrow 1351 00:58:30,900 --> 00:58:34,260 at 10:00 AM for a look at JavaScript. 1352 00:58:34,260 --> 00:58:35,221