JavaScript Tic Tac Toe Project Tutorial – Unbeatable AI w/ Minimax Algorithm

JavaScript Tic Tac Toe Project Tutorial  – Unbeatable AI w/ Minimax Algorithm


In this video I will be showing you how to create a tic-tac-toe game from start to finish using JavaScript HTML and CSS. I will also show you how to create the AI using the minimax algorithm. I expect you to have basic knowledge about HTML CSS and JavaScript But you don’t have to know anything too advanced However it may take a few rewatches to completely understand the minimax algorithm If all you are interested in is the minimax algorithm feel free to skip to that section by clicking the link in this description for section 7. To get the most out of this video you should create the tic-tac-toe game along with me on your own computer If you get lost while writing the code you can check out the github repository that goes along with this video This video has many sections And there is a folder in the github Repo for every section in the video the folder has what your code should look like at the end of each section Check out this video’s description For links to the code for the each section as well as links to skip ahead to that part of the video Before we start creating anything Let’s make sure your development environment is set up an easy way to create this project is to use codepen.io Just go to the site, and then create a new pen There is a section to put your HTML your CSS and your JavaScript And then everything you create will show up right over here. Also. Don’t forget to give your pin a name and save it However I’m actually going to create the project locally on my machine instead you can do that with any text editor I’m using sublime text. I’m gonna open sublime text, and then go to file open Now I’m selecting a folder. I already created for this project inside this project create three files I use the sidebar enhancement package add-on so I get more options when I right click here So we’re gonna create the three files. We’re gonna create Tic Tac Toe.html Now style.css and Then the last one is going to be script.js Tic-tac-toe.html. I’m going to paste in basic HTML boilerplate code That should be included in most projects. You can see that in the head. There is already a link to style.CSS and also at the end of the body There is a link to the script.js javascript file so that’s how all these three files that we created are connected The first thing you should do is insert the title so right inside the title here. I’ll put Tic-tac-toe, and if you’re accreting the project in code pen you actually don’t need any of this code all of this is automatically included Now let’s start setting up the basic HTML structure First of all I want to let you know that just like any programming project there are an infinite ways to create a tic-tac-toe game There’s not really a right way to do it as long as it works We’re going to use a table to create the 9 by 9 grid needed for the tic-tac-toe board After we get this code in we’ll add some CSS to make it look more like a traditional tic-tac-toe board Now press command shift D to duplicate that three times, and we’ll just change this to one this to two and then command shift D two more times Three four five six seven eight We’re also going to need to display who is the winner of the game so at the bottom? We’ll add a div with the class of endgame Also, we’ll add a button that will allow the player to reset the game after it ends While we are putting this at the bottom later. We’ll add some CSS to position the in-game message on the top of the tic-tac-toe board Also, that reset button will eventually go into the in game element next we’ll start working on the CSS Okay before we switch over to our CSS file you can see that I opened up a browser window right here, and it’s going to show everything that we’ve created right now the table There’s nothing in the table, so it doesn’t show the table, but we can see the replay button also I didn’t realize I named one of my files and correctly this was supposed to be script J S so I’m going to right click and rename now. This is with my special Add-on here, so not everyone can rename right from in sublime So now we have the right name script J. S not script at CSS. Okay We’ll go over to our style tab here and the first thing we’re gonna style is the TD element The TD element if we go back into our HTML That’s what all the cells in our tic-tac-toe game all the squares are the TD elements, so we’re gonna set up border And I hide in a width We’ll just stop for a second just to see what that looks like so far So it’s already starting to look like a tic-tac-toe board let’s put in a few more things And let’s see what that does I’ll save that refresh the page and Now you can see well. We did add this cursor:pointer, so it looks like you can click each square when you’re on it And you can see it still doesn’t look like a tic-tac-toe board exactly so again a few more things for the styling now I’m going to add some styles to the table element So that’s going to style the whole table element that includes everything else here So border-collapse:collapse, that’s what is going to make it look more like this, so we don’t have the two lines for each cell Now this is just some stuff for positioning. It’s gonna make sure it’s centered position:absolute means it’s not going to be related to other things on the page and The left fifty percent and then margin left negative 155 pixels is just a way to Center it so it’s gonna move 50 percent to the left and if we just if we didn’t have the margin left with the edge would be at the center So if I take that out and then refresh that you can see the edge is right in the center But we have to move it back over so the negative 155 pixels the whole thing is 310 pixels 310 divided by 2 is 155 so that’s why we go negative 155 pixels left And the top 50 is just so there’ll be some space at the top because it’s absolute now It’s not related to where this button is so this button just pops up at the top Now we want to make this look more like a tic-tac-toe game by removing the edge border all the way around We’re gonna use the first child selector So let’s see what this would actually select table T our first child TD so first We’re gonna go to the table, and then the T our first child so there’s the first child This is the second child This is the third child so we’re only selecting the first child which is basically the whole top row here and TD. Which is going to which will be every TD element so for every square in this first row here We’re going to do something Border top equals zero, let’s save there and refresh that page you can see now there’s not a border on top So I’m just gonna copy this Scroll down here Let’s copy this. Let’s get that more toward the top here so we have more room Pasted here, so now instead of first child we’re going to do last child It’s a border top and a border bottom, and then if we just look what that looks like we just removed the bottom Now we’re gonna. Just change this up slightly We’re gonna cut that and then put it on the end of the TV, so we’re gonna Select every table TR and then just the first child TD so we go back here This is the first child This is the first child and this is the first child Instead of border top it’s gonna be border left And we can see what that’s gonna look like and then just the same thing instead of first child last child and border, right Okay now it’s starting to look like a tic-tac-toe board Now I’m just gonna add some code. That’s going to Style, this this in-game element this in-game element is gonna look like a little a modal that pops on top of the tic-tac-toe board At the end of the game, so let me add code for that Okay now I got this whole end game element you can see we have it display:none Because it’s not going to display until the end of the game and actually just to see what it looks like let’s just remove this Display:none for a second and see what that’s gonna look like see it’s gonna. Just pop on top just like that And let’s put that back Again, you can change styling any way you want to make it look a little more exciting than what I’m doing Now we’re gonna finally get into the JavaScript code the JavaScript part of this video is broken up into four sections First we’re going to set up some variables and add the ability to click a square and show a mark Second we are going to add logic to determine the winner and show the winning combination Third we’ll create a very basic AI and add the code to notify who the winner is and finally and this is the most complicated section will create the logic for an unbeatable AI Using the minimax algorithm. I’ll demonstrate how it works with some diagrams So like I said this first section will set up some variables so first we’re gonna initialize the board so The bar or edge board means original board and this is eventually going to be an array That keeps track of what’s in each square the tic-tac-toe board if it’s an X or it’s an O or nothing And now this is how will show that the human player is going to be 0 and we’ll have also have a Const of the AI player which will set to X Now you can create these as anything It doesn’t even have to be X and O and it’ll show up in the boards over there and now we’re going to create an array that’s going to show the winning combinations for the tic-tac-toe board and Inside this each winning combination is going to be an array so it’s an array full of arrays So we have 0 1 2 so each square This is square 0 this is Square 1 and this is square 2 if if we have oh-o-oh across that would score for tic-tac-toe and The other two ways to win across 0 3 6 this would be 0 3 6 so that would be a diagonal win and Now I just put the other winning combinations in there so cells equals document dot query selector all and Dot cell and let’s zoom out a little bit so that means the cells Variable is going to store a reference to each cell here Document that query selector all is going to select each Element on the page that has the class of cell which are all these TD elements and then we’re gonna have to call a function to start the game, which is just gonna be the start game function and Now we’ve defined the function so this is what will happen when the game starts Also one thing to point out is that remember when you click replay? It’s also going to run the start game function so this start game function will run at the beginning But also whenever you click replay it will run the start game function We have the document dot query selector, and we’re going to select the in game element And we’re going to set the style so we’re gonna modify the CSS style Specifically the display property we’re going to set the display property to none Now if we go back into the style you can see that this the display property is already set to none but Remember this will also happen when we hit the replay button that will run the start game function and at the end of the game the in game Element is not going to be set to display none is actually showing up so when you click replay It will be set to none again and now we’re going to Finally load something into the original board variable that we have up here We’re gonna set it to array dot from array 9 dot keys This is just a fancy way right here to make the array be every number from 0 to 9 so It’s gonna create an array of nine elements And it’s gonna be get just the keys for that element which is 0 through 9 and it’s gonna create an array From that other array, so just to show you what I’m talking about. I’m just going to console that log that here So if I save that I’m going to run this Now I’ll open up the JavaScript console. You’ll see we have an array of Elmas 0 through 8 here But let’s remove this for now Now throughout the course of the game We’ll actually be adding X and X’s and O’s to this so whenever we restart the game We want to remove all the X’s and O’s from the board So we’re going to do that with a for loop so We’re just gonna go through cells that length and remember cells is this up here So it’s a reference to every cell up here. I’m gonna go through every cell up there And we’re gonna do three things each cell so Cells eye is gonna be each item of the cell when it loops through this for loop I’m gonna set the intertext to nothing so there will be nothing in the cell and We’re going to do remove property background color That’s because I already know that when someone wins we’re going to highlight each Square that’s part of the winning combination in a certain color and if the game is restarting we want to remove that background color, so we’re back to having no background color and Then one final thing We’re gonna add an event listener on the click event and we’re going to call the turn click function So now every time anybody clicks one of these things We’re going to call the turn click function and the turn click function is the next thing we’re going to define in our program For now just so you can see what’s going to happen we’re going to do a console dot log and Actually inside the trunk click function. We’re going to pass in something, so I’m just going to call this square It’s just gonna pass in a click event so we’re gonna console that log Square target dot ID So now it’s just going to log the ID of whatever square was clicked, so I’m going to save this I’ll refresh this page, and then let’s see what happens. I’m going to click Oh, I’m getting an unexpected token. Let’s see what I did wrong there says number line 28 Oh I just forgot to put the word function here, so this is supposed to be a function. Let’s save that refresh and Okay cannot read property remove property It looks like I spelled this wrong this would be style so maybe you already noticed while it’s typing it in earlier But this is a good way to troubleshoot your code Just look in the JavaScript console, and they’ll give you an idea of what you did wrong so now let’s refresh this That’s why it’s good to try things out periodically while you’re programming so you can catch things quickly I’m I’m actually gonna clear the console and then refresh so you can see that There’s no errors and now if I click it. Oh six because that’s the zero one two three four five six C I’m gonna click there click there wherever I click you can see in the console Here’s 0 here’s 8 you can see it appearing down the console down here I know it’s kind of small, but it’s showing the ID of the square that I’m clicking But we actually don’t want it to just console that log every time you click somewhere, so I’m gonna delete this here And we’re gonna call another function inside the trunk click we’re gonna call the turn function and we’re gonna pass in the ID that we’re clicking and We’re gonna pass in H. You player because it’s the human player That’s doing the term so actually That’s the only thing that’s going to be in the turn click function is calling the turn function and the reason why we don’t go directly to the turn function is because the turn function can be called with either the human player or The AI player so if a human is clicking we’re gonna call the turn function with the human player and not the AI player So now let’s define the turn function This time I’ll remember to put the word function the turn function is going to take two parameters the square ID and the player and you can see that’s what we pass it up here the square ID and the player this is the human player and So we’re gonna set two things So first of all we’re gonna set the board array or ridge board at the ID that we’ve clicked to player So on this array. It’s going to show the player who just took a turn in that spot But we don’t actually see that array. We’re also gonna have to update the display so we can see where you just clicked Okay, document dot get element by ID That’s going to select an element with the ID and the square ID if you remember from in the HTML we have the square IDs here, so we’re gonna select the element that was just clicked and Set the inner text to equal Player so if I save that and refresh if I click here Wherever I click you can see an oh it pops up So right now. We can fill that all up, and then that’s all we can do, but let’s see if the replay button works Yeah, we can click replay, and we can keep putting an O in here, so this is kind of fun for a few seconds But I think we need some more functionality of our game here So now we’re entering the second part of the JavaScript section Which is actually the fifth part of this video where I’m going to add logic to determine the winner and show the winning combination remember you can check the link in the description of this video to link to the github repo where you can get the actual code that I’m using and Remember the folder for each section shows what the code should look like at the end of each section so if you get the code for the end of section 4 You’ll be exactly where I am now so whenever a turn is taken We are going to check if the game has been won, so I’m gonna add this let game 1 equals check when and Check win is going to be another function We’re going to define in just a second, but we’re gonna pass in two things the original board array Which is an array that shows? everything on the board where the X’s and O’s are and The player the current player because we want to check if a certain player has just one if game one So if we find that the game has been won called the game over function With the game one variable you’ll see here that this is not just going to be a true or false Variable we’re gonna have some other information that will be passing into the game over function Okay, now. I will define the check win function which is going to receive the board and The player the reason why we have to pass in the original board here And we don’t just reference the original board variable in this function is because later in this program We will be passing in things that are not the original board There are different versions of the board than what the current version of the board actually is you’ll understand that when I get to it Now this line that I’m typing is really just a fancy way to find all the places on the board They have already been played in Let’s bring this down to this line here So we’re going to use the reduce method the reduced method is going through going to go through every element of the board array and do something and it’s going to give back one single value the Accumulator is the value that’s going to give back at the end? And we’re going to initialize the accumulator to an empty array the e is the element in the board array that we’re going through and the I’s Index so if the element equals the player Then this is a ternary operator, so then we’re going to do this. We’re going to just contact I that just means we’re gonna take the array the accumulator array and we’re going to add the index to that array and then if He does not equal player. We’re just going to return the accumulator Just as it was so we’re not going to add anything to the accumulator So this is just a way to find every index that the player has played in And we’re going to set game 1 to equal null and Then we’re gonna check if the game has been one We’re gonna do that with a for loop so? This is a for Loop, actually this supposed to be winged combos dot entries so remember at the very top we have the win combos This is every single thing that could create a win Every array here could create a win So we’re going to have to loop through every wind combo every possible way that a player could can win so when combos dot entries is just a way to get the index and the win so we’re gonna have one variable that’s 0 because this is index 0 That’s gonna be the index and the win each win that we’re looping through the wind is going to be this array with 0 1 2 So we’re gonna need the index of the winds we need the index and the win in this for of loop If when dot every when de every means we’re going to go through Every element in the wind so for instance the first one with just every element would be 0 1 2 so If winda every so for every element in that 0 1 & 2 we’re gonna check if Plays that index of L is more than negative 1 so the plays is from up here plays is the all the places that the player has played on the board and Index of so we’re gonna see if the index of the element is more than negative 1 That’s just a fancy way of saying of saying has the player played in Every spot that counts as a win for that win so has the player playing all these spots And then it’s a loop has the player playing all these spots has the player playing all these spots We go through every single one to see if the players play in all the spots that constitutes a win combo If so that means the player has won, so we’re gonna set game 1 2 equal Index index player player so now we know which wind combo the player won act and we know which player has won, and now we’re just going to break from the function and After all that we’re going to return game 1 so if nobody wins Game one will be null if someone does win Game one will contain which when it was and which player 1, so let’s go back up here if game 1 then run game over if game has no if game 1 is null this will be false if Game 1 contains this here this will be true And we’ll run the Gamo over function so now let’s define the GAMEOVER function And The GAMEOVER function is going to accept game 1 our game 1 was defined right up here And we’re gonna pass in here, and that’s gonna go into here Inside the game over function we’re gonna have two for loops first of all we want to highlight all the squares that are part of the winning combination And then we want to make it so the user cannot click any more squares because the game is over Let index of win combos and we’re gonna pass in game one index So that was the index of the winged combo that was the winner for this game so we’re gonna go through every index of that win combo and We’re going to do something Document dot get element by ID the index that’s the index from the win combo dot style dot background color, so we’re gonna set the background color to Something what we set the background color will depend on who just won the game Game one dot player. That’s who won the game if game 1 dot player equals the human player now This is a ternary operator. We’re gonna set the background color to blue if it’s the AI player we’re gonna set the background color to red and That’s the end of this for loop now. We’re going to have one more for loop and Now we’re going to go through every cell and we’re going to make it so you can’t click that cell anymore So we’re gonna remove the event listener the remove the click event listener, and we have to also pass in what that click event event listener was to the term click and Set this to false Okay, so now let’s see how this works. We’re going to refresh here with all of our new code, ooh We have some air here missing initializer and destructuring declaration 41 so let’s go up there Hmm oh We just I think it’s just so we have an extra parentheses here. Let’s see if that solves the problem Now let’s clear the console and refresh Unexpected token 44 so let’s see what happened there and Here it looks like Here I was missing a parenthesis it should be index of element is less than negative 1, so let’s try that we’re gonna refresh this and Another here ok. Let’s see what we did here I Don’t think we need this parenthesis, so let’s see if that fix the problem I Think it just fixed the problem, so let’s try this out. Okay if we put three in a row It turns the blue, and we can’t click anywhere. Let’s replay now We should be able to click three in a row turns a blue, and we can’t click anywhere Turns a blue. We can’t click anywhere so that works We can now determine a winner next up. We’re going to create a basic AI and show the winner box Well I hope you’re still falling along and creating your own program along with my program We’ve just started Section six so if you get the code from the github repository That shows the end of section five you should be caught up with where I’m at now Again, just check the link in the description for that code right now There’s no AI so the computer doesn’t even do anything when you play you’re just only putting O’s in there So we’re gonna change that in this section this will just be a basic AI Without the minimax algorithm in the next section. We’re going to implement the minimax algorithm So let’s go back up to the turn click function so when the turn click function is Run the human player is going to take a turn But right after the human player takes a turn the AI player will take a turn so Before the AI player takes a turn we’re gonna check if it’s a tie So if it’s a tie game that means every square is full and nobody has won yet So if every square is full the computer player is not going to take a turn so if there’s not a tie Then the computer player will take a turn turn That spot AI player So just up like up here. We put in the target ID that was clicked here we’re gonna get the ID based on this other function the best spot function is going to return the ID to click and Instead of the human player we have the AI player taking the turn let’s do one last thing while we’re in this function Right now you can click on a place That’s already been clicked so we want to make it so you cannot click on a place. That’s already been clicked so let’s add that logic right up here if typeof a ridge board Square that target dot ID Equals equals number so if you remember the original board array Gets filled with the numbers 0 through 9 and then when a turn is taken that Index will be replaced Not with a number anymore, but with the X or the O the human player or the computer AI player so if the type of the ID that was just clicked is a number that means that neither the human nor the AI player has played in that spot so if nobody is play in that spot, then let’s Cut those out put it right here, then we’ll do this We’ll run the turns here so the human player and then the computer play right there So you can see we made two functions check tie and best spot So let’s create those functions. Let’s go down to the bottom here, and we’ll start with the best spot function Now this is how we’re going to find the spot for the AI player to play remember I said that eventually we’ll make it more complicated, but this time. We’re just going to make something really simple So the best spot function is just going to run a different function we still have to create That’s gonna find all the empty squares and just get the first element from the empty square So it’s just always going to play in the first empty squares so before we create the check tie function Let’s finish creating the empty squares function. I’ll put it right up here So function empty squares So we’re going to filter every element in the original board to see if the type of the element equals a number if the type of is a number we’re going to return that so all the squares that are a number are empty and the squares are an X or an O are not empty and The best spot is just going to find the first square. That’s not empty so Now like I said, we’re going to have that checked eye function so to check if it’s a tie we just use the empty squares function that we just created if The length equals equals zero that means every squares filled up And nobody’s won yet because normally every time someone plays a turn it check to see if someone’s won So if every square is filled up and nobody is one that means there’s a tie we’re gonna do a few things inside a for loop Because we’re gonna do something to every single cell in the tic-tac-toe board So we’re going to set the background color of every cell to green And we’re gonna remove the event listener so the user can’t click anywhere right now because the game’s over and We’re going to declare a winner. This is actually a function. We sought to create declare winner Tie game that’s what we’re gonna pass in the words tie game and return true because True it’s a true that it’s a tie or if this if statement is false. We’re going to return false Okay, we just create a new function so now we have to define that function the clear winner let’s put that one right up here Declare Winner oh And we’ve passed in whoo Right down here. We passed some tie game But we’ll also sometimes pass and if the computer wins or if the human wins So inside this function we’re going to do something So we’re finally going to show The in game section it was set the style was set to display none But now it’s gonna be set to this display block. I’m just gonna duplicate this line I’m gonna select that in game dot text So now if we go back into the HTML The dot txt he is here so the ink inside endgame and then inside text That in our we’re gonna set the inner text To who that’s what we passed in here so if it’s a tie game It’s gonna say tie game So we also wanted to say if you win, or you lose so let’s go over the game over up here and When there’s a game over? We’re going to also call the declare winner function and we’re gonna Have a ternary operator to see what we’re gonna pass into the declared winner function So if the game won that player is a human player we’re gonna pass in the words you win Else we’re going to pass in the words you lose So I think we’re done implementing this basic AI so you can actually play a full game of tic-tac-toe Let’s save it and test and see if we get any ears no error so far. Let’s see Yep, so I played here the computer I’ll I’m going played on the next open spot the computer play on the next open spot, and it says you win So let’s replay now. Let’s see if I can get the computer to win You lose Now let’s see if we can get a tie game Tie game So we just saw every in state you win you lose and tie game at This point you have a fully functional tic-tac-toe game However as you can see it’s pretty easy to beat Now we will create an unbeatable AI using the minimax algorithm After we implement the minimax algorithm, you will never see the message you win on the screen Much of this section on the minimax algorithm is taken by a great article by Achmed abdul Saheb on the topic I have linked to the article in the description of this video I definitely recommend you check it out a minim X algorithm can best be defined as a Recursive function that does the following things one returns a value if a terminal stay is found in this case Positive 10 zero and negative 10 to go through available spots on the board 3 call the minim x function on each available spot a recursion for evaluate returning values from function calls and 5 returned the best value I’m going to go through the code for the minim x function. Don’t worry If you don’t completely understand it at first after I show the code I’m going to use an example and diagram to demonstrate the algorithms function calls one by one Also, if you’re anything like me you may want to watch this section more than once to get a grasp on it before we define the minimax function will change the best spot function It’s actually just going to return the result of calling the minimax function it’s going to call the minimax function passing in a ridge board and a I player because it’s the AI player playing and It’s going to get dot index because the result of the minimax Function is an object and dot index will be the index at the computer to play in So we’ll define the minimax function with two arguments new board and player then we need to find the indexes of the available spots in the board using the empty squares function and Set them to a square called avail spots We’ll check for terminal States meaning someone winning and return a value accordingly if Zero wins you should return negative 10 if X wins you should return positive 10 In addition if the length of the available spots array is 0 that means There is no more room to play the game has resulted in a tie and you should return 0 Next you need to collect the scores from each of the empty spots to evaluate later Therefore make an array called moves and loop through empty spots while collecting each moves index and score in an object called move Then set the index number of the empty spot that was stored as a number in the original movie Then set the empty spot on the new board to the current player and Call the minimax function with the other player and the newly changed new board Next you should store the object Resulted from the minimax function call that includes a score property to the score property of the move object if the minimax function does not find a terminal state It keeps recursively going level by level deeper into the game This recursion happens until it reaches a terminal state and returns a score one level up Finally minimax resets new board to what it was before and pushes the move object to the moves array Then the minimax algorithm needs to evaluate the best move in the moves array it Should choose with the highest score when AI is playing and the move with the lowest score when the human is playing? therefore if the player is AI player it sets a variable called best score to a very low number and Loops through the moves array if a move has a higher score than best score the algorithm stores that move in Case there are moves with similar score only the first one will be stored The same evaluation process happens when player is heyou player But this time best score would be set to a high number and minimax looks for a move with the lowest score to store at the end minimax returns the object stored in best move I Want to emphasize again that it’s okay, if it takes a few Reviews to understand this I had to go over it multiple times I first learned it, but this next example should help before we go over the example Let’s actually just try this out just to make sure I didn’t make any mistakes when I was creating the code so I save that Refresh over here and let’s see ooh Reference air or rigid board not defined JavaScript 76 let’s go up to 76 up here and This should be there’s be an eye in there. Okay. Let’s save that refresh and let’s see if we have any more ears And this seems to be working Let’s see if it’s possible when it’s not possible to win they did something right Okay, gonna, try it out a little more later, but let’s go over to the example in this example We are starting with this board configuration and then following how the minimax algorithm determines the next move Assume the AI is X and the human players oh I’m gonna use this figure right here to follow the algorithms function calls one by one remember in this example We’re pretending R at the end of a tic-tac-toe game So there’s just one more move left so the board looks like this So we’re gonna go through the code to figure out the exact logic that the program takes to figure out where to play so in Figure 1 we’re at the very beginning of the minimax algorithm and a ridge board and the AI player is fed into the algorithm and The algorithm is going to make a list of the three empty spots that it finds, so if you see right here We have the spot here here the middle and then the bottom-left It’s gonna check for terminal States, and then loop through every empty spot starting from the first one here, it’s going to The new board by placing the AI player in the first empty spot after that it’s going to call itself With new board and the human player and wait for the function call to return a value So we’re just on the first function call we’re not to the end of the first function call yet But now we’re already going to the second function call So while the first function call is still running the second one starts? By making a list of the two empty spots at vines just these two that’s here where it’s making list of the two empty spots It’s going to check for terminal States, and then loop through the empty spot starting at the first one Then it changes the new board by placing the human player in the first empty spot after That it calls itself with new board and the AI player and waits for the function call to return a value We’re at the third function called which is right here Still function called two and one have not finished the algorithm makes a list of empty spots and this time It’s going to find a win the human player is going to win therefore it returns an object with the score property and value of negative ten and Since this second function call up here listed two empty spots The minimax changes the new board by placing the human player in the second empty spot so B right here And then it calls itself with the new port in the AI player so from function two we got two function 3 by placing a spot here in the middle and Then we go from function 2 to function 4 by placing a spot in on that bottom left The algorithm is makes a list of four spots the algorithm. Just makes a list of empty spots and Finds a win for the human player after checking for terminal States And then it’s going to return negative 10 again on The second function call the algorithm collects the values coming from lower levels the third and the fourth function calls Since the human player’s turn resulted in the two values the algorithm chooses the lowest of the two values on The second function called algorithm collects the values coming from the lower levels, so we already had the index and then we’re gonna assign the score here and We’re gonna assign the index the new board and then we’re pushing all the moves on to the moves array So that’s how all the values have been collected from the third and fourth function calls since the human player’s turn Resulted in the two values the algorithm chooses the lowest of the two values So here’s if the players the AI player else, which is what we’re at now because the player is a human player It’s going to run this code to select the lowest of the values Since both values are similar it chooses the first one and returns up to the first function call That’s down here when it returns moves best move At this point the first function call has evaluated the score of moving the AI player in the first empty spot Next it changes the new board by placing AI player in the second empty spot, so this was the first empty spot here’s the second one in the middle it’s gonna call itself with the new board and the human player and I’m gonna skip through some of this of every single thing that happens But you can see in function call 1 there are three empty spots And that’s why there are Three and level one so the first empty spots function call to the second empty spot function call five and the third empty spot Function call six to empty spots here two moves here and Here since we found a terminal State. You don’t actually go any further and here There’s two empty spots so we try these two and then eventually you get down to eight and Because of the recursive nature and like I was showing before this gets passed up to the top now Toward the end of ring the algorithm the three branches of the first function call have all been evaluated We got the negative 10 the 10 and the negative 10 But because the AI player’s turn Resulted in those values the algorithm returns an object containing the highest score Which is the +10 at index 4 which is the middle index? So in this scenario the minimax concludes that moving the X to the middle of the board results in the best outcome Now to speed things along I didn’t explain every single function call But if you check the article they link to in the description it goes into even more detail about this I hope with my explanation and just being able to play with the code a little bit You’ll be able to understand the logic behind the minimax algorithm Okay, and there’s one final thing I still need to do you can see that the replay button is right up here in the corner And we want to put it in the popup box So I’m just gonna go over to the HTML file and I’m gonna select this button and then at least on the Mac it’s control command up, so it’s going to move that line up, and then I’m just gonna tab it over and That should put the button in the right spot, so let’s refresh here And now the replay button doesn’t show up until the game is over and you can put the replay button right on that little pop-up And You now have an unbeatable tic-tac-toe game? There are many ways this game can be improved so for extra practice you can think about other features you can implement for Instance maybe you want to make it two-player so there can be two human players instead of a human and a computer player Well, thanks for watching. My name is Bo Carnes. Don’t forget to subscribe and remember use your code for good

Comments

  1. Post
    Author
  2. Post
    Author
  3. Post
    Author
    Helsey sin

    I have made the same implementation of the minimax algorithm…although still the AI is not working properly.
    https://codepen.io/helsey/pen/oEGrjy?editors=0010

  4. Post
    Author
    Richard Kirigaya

    Great video. Am trying to make an S.O.S game on a 7×7 grid. its alot like tic-tac.toe. how do i do it with this logic?

  5. Post
    Author
    Curtis Campbell

    Please zoom out and scroll down so not all of the code relevant to what you're talking about is covered up by the progress bar on Youtube, for those of us who are constantly pausing to try and keep up with your super fast autocomplete, that I am very jealous of.

  6. Post
    Author
  7. Post
    Author
    BubuSnow93

    Program is bugged, if you play the sequence "1,3,9" the computer will answer with "5,2,6" instead of going "5,2,8" and winning.

  8. Post
    Author
  9. Post
    Author
  10. Post
    Author
  11. Post
    Author
  12. Post
    Author
    Channel Channel

    Who knows plz Relpply. I'm new in coding world and this video is great but my simple doubt is how to save apk file in laptop and also how to add Banner ad in this games…

  13. Post
    Author
    Urketadic

    Isn't it 308px in width not 310?
    There is 4 borders and each one is 2px, so three boxes plus borders is not 310.

  14. Post
    Author
  15. Post
    Author
    Richard Ramos

    on 20:00 wow , on the first time I've watch this I'm having a hard time figuring out where that getElementByID(squareID) came from, I'm so slow I guess, because I thought you can only use getElementById by only getting the id when you declare it on the DOM, I was so frustrated that I stop watching this, now for the second time, I figure it now, so that squareID is a reference of the Cell ID itself and you also don't need to put a a quote to the getElementById("squareID") because the event squareId came from a square.targe.id so it is an id by itself, AM I right ? May I also ask if there is any way I can do that by using the querySelector ? like this
    document.querySelector(squareId).innerText = player; so only getElementById is allowed for this?

  16. Post
    Author
  17. Post
    Author
    Rutansh Trivedi

    there is a problem in the logic..you can find it in a 39:00 minute..when it pops up saying tie game instead of saying "You Win" otherwise it is very informative.. thank you..

  18. Post
    Author
  19. Post
    Author
  20. Post
    Author
  21. Post
    Author
  22. Post
    Author
    Joshua OConnell

    Playing 5, 4, 3 will result in a loss. This should be a win. How do I fix this? I tried it with my code and the GitHub provided code.

  23. Post
    Author
    Wowotuning Gonzalez Mesa

    good tutorial, really well explained but i would like to put some pictures instead of X or O

  24. Post
    Author
  25. Post
    Author
  26. Post
    Author
    Sandor Deli

    At 39:05 it wasnt a TIE, than you WON actually (altough all the fields are reserved, you have 3 squares in a row from the top left to the bottom right)… Anyway I really appreciate your video it has helpd a me a lot. Thank you for it.

  27. Post
    Author
  28. Post
    Author
  29. Post
    Author
  30. Post
    Author
    Satbir Singh

    Hey dude, Many thanks for the video. Has been great to go through it. Learned a lot. I noticed some errors, which I think allows the algorithm to be beaten. Another user in the comments also mentioned it.

    at 41.20 Line 94 should be huPlayer, and not Player.

    With it being Player, I could always win if I played 1,8,6,3,9. But once that was corrected, I couldn't win.
    Also I'm still learning a lot, but early on you state the game is a tie, however you clearly won. I think that is because the checkTie function only checks for empty spaces, and not if the game has already been won (because of this when testing early on I noticed, if you win, and there are still spaces on the board, the aiPlayer takes a turn. I guess this doesn't matter as with the minimax algorithm, its impossible to win, so the best you can hope for is a tie).

    Hope this helps other people who go through this video. Really awesome, and thank you so much for sharing.

  31. Post
    Author
    Mr. Sandman

    Great tutorial. How did you figure out what properties of the game were required, and which order you'd have to go through? Is there a resource you use that lists the game mechanics?

  32. Post
    Author
    Sarah Amin

    thanks so much for your effort, i'm learning javascript and i have a question, what S in line 66 stands for i'm confused and also a and e in line 43?

  33. Post
    Author
    Jerkules

    Trying to work out a lil bug on my end. My problem is with the minimax function. I get the whole, score is undefined. I will be able to work it out, but just wondering does the .score property become defined to the minimax function at line 95 and line 97, in the code written by you guys at 41:53?

  34. Post
    Author
  35. Post
    Author
    powerful duas and wazifas

    HELP PLEASE!
    This is a really great tutorial and I'm currently done with part 4. The O's aren't showing up and the console says there's an error and 'style' is not defined, so i copy and pasted the html, css, and JS (part 4 only) and the O's still don't show up and 'style' is still not defined, what do i do? 🙁

  36. Post
    Author
    freeCodeCamp.org

    Check out this playlist of more game development tutorials: https://www.youtube.com/playlist?list=PLWKjhJtqVAbmqFs83T4W-FZQ9kK983tZC

  37. Post
    Author
  38. Post
    Author
    powerful duas and wazifas

    I need help on part 5, the blue squares aren't showing up when I win, I'm using codepen.io here's the link
    https://codepen.io/Love2program/pen/GBaBwa

    EDIT: Nvrm, it works! Just some silly mistakes I made.

  39. Post
    Author
  40. Post
    Author
    Alon Attar

    * If only one square is marked on the board and the middle slot is free – mark the middle square. i am coding my tic tac toe by this logic , and until now it wotks great

    * If a row, column, or diagonal is marked with two slots of the computer – mark my disruptor.

    * If the row, column or diagonal is marked with two squares of the opponent – mark the third slot.

    * If three squares are marked and my central squares – to mark a block in a row or line in which one of the opponent's squares is marked, preferably a corner slot.

    * If there is a vacant corner and on either side of it two empty lines – mark the corner

    * If the middle slot is free, mark it

    * If there are three available slots in a row, in a row or diagonally – mark the corner

    * If there is an available slot – mark it

  41. Post
    Author
  42. Post
    Author
  43. Post
    Author
  44. Post
    Author
  45. Post
    Author
  46. Post
    Author
    Randy Nasworthy

    Not sure what I'm doing wrong, but I have the code exactly like in the video. However I get an error and the O's don't show when I click the spaces.

    This is my line 32:
    funtion turn(squareId, player) {

    I get this error code:
    Uncaught SyntaxError: Unexpected identifier script.js:32

    I also get this error when pressing the 'replay' button:
    Uncaught ReferenceError: startGame is not defined
    at HTMLButtonElement.onclick (tictactoe.html:34) tictactoe.html:34

    This is my line 34 in html:
    <button onClick="startGame()">Replay</button>

  47. Post
    Author
    fanta123

    It would be better tutorial if you'd showed your thought process and order in which you would actually create those functions. You just follow line by line from the finished code trying to explain why. Too much of: 'You will see later, we will need later on, You'll understand when I get to it…' etc. which is confusing. In real life you don't know exactly what you will need later.

  48. Post
    Author
  49. Post
    Author
    Hayosiko Takagumi

    You don't really teach anything properly, you just explain how things work.
    You just quickly tell what this does to this and you go so fast. Even when I set the speed of the video to .75 I can't keep along.

    Would have been a great tutorial with a bit more effort.

  50. Post
    Author
  51. Post
    Author
  52. Post
    Author
    Thrisha Ram

    At 38:44 after you won, the computer makes a new move ! The game must be over by then and it should not be possible for the computer to make another move..

  53. Post
    Author
  54. Post
    Author
    Binnie Ali Abdullahi

    so the only thing I'm confused about is lets say huPlayer has three in a row but on the next move the aiPlayer has a space that would allow them to win the game it still says ai wins although the huPlayer took the first move
    how would you fix that?

  55. Post
    Author
    MrRufus302

    How does one get the game to work on TOUCHSCREEN? With the vast majority of devices being touchscreen, I am a little disappointed that the functionality required a mouse.

    I am learning JS, so any mention of targeting DOM elements is well beyond my capability presently.

  56. Post
    Author
  57. Post
    Author
  58. Post
    Author
  59. Post
    Author
    Nicolae Crefelean

    51:10 – It looks like the game cares more about the human player not to win, than defeating the player. Instead of making the winning move on cell 4, it blocked the human player (cell 2) from winning. 😛

  60. Post
    Author
    BKofficer23

    I am at 20:33, just got done with the turn function. It seems in the turn function that origBoard can also be huPlayer or aiPlayer and still work. There must be a reason to choose origBoard over the other two. Anyone know why?

    Another way:

    function turn(squareId, player) {
    origBoard[squareId] = player;
    document.getElementById(squareId).innerText = player;
    }

    can be:

    function turn(squareId, player) {
    huPlayer[squareId] = player;
    document.getElementById(squareId).innerText = player;
    }

    and still work.

    Thanks you geniuses.

  61. Post
    Author
    JLNC

    Instead of using the AI player, is it possible to simply replace the AI player with a second human player? Been trying to play around with the code but so far no success.

  62. Post
    Author
  63. Post
    Author
    Fu Helen

    Revised method in Github to prevent player winning: in the minmax function change the line **moves.push(move);** to:

    if ((player === aiPlayer && move.score === 10) || (player === huPlayer && move.score === -10))

    return move;
    else
    moves.push(move);

  64. Post
    Author
  65. Post
    Author
    Antonio Comique

    play my own version of tic-tac-toe at http://tonixhub.com/. This is purely written in JavaScript using classes with singleton. 😉 enjoy! You may download my code at https://github.com/tonix00/tic-tac-toe

  66. Post
    Author
  67. Post
    Author
  68. Post
    Author
  69. Post
    Author
  70. Post
    Author
    Air Crash

    19. document.querySelector(".endgame").style.display = "none"; this part is pain in the neck every time I enter it inside my code it displays this message "Uncaught TypeError: Cannot set property 'display' of null
    Line: 19"

  71. Post
    Author
  72. Post
    Author
    Lisa Ford

    when i win sometimes it still tells me its a tie…i have checked the arrays in the const winCombos and all the posibilties are there…is anyone else running up on this problem

  73. Post
    Author
    Џон Мастерман

    Im new to coding, but very curious as to why not use margin: 0 auto to center it instead of that odd looking styling ?

  74. Post
    Author
  75. Post
    Author
    Kristopher Werlinder

    0:10 Is not a Tie Game, it is Win game for circle. Someone know what is missing for this algorithm to work?

  76. Post
    Author
  77. Post
    Author
  78. Post
    Author
  79. Post
    Author
    just me g

    thanks a lot
    I made my first js game . ..
    I can't understand how is the Algorithm works
    but it's a great start . . .
    +
    the links in the description are so helpful 3>

  80. Post
    Author
    Łukasz Kobylański

    I found bug. (Which occurs only b4 minmax alg. is implemnted) however -> if you race with AI for win EG i put O on left bottom corner then AI X in the top left corner I shall win when going bottom mid O AI goes middle top X then I put 3rd O in the bottom right corner and now instead win for me there is an AI turn and win for AI.

  81. Post
    Author
    Łukasz Kobylański

    Another bug when you win with last move the game is also draw. I know that Player vs minmax will never win. However if someone want to apply PvP have to fix that 🙂

  82. Post
    Author
  83. Post
    Author
  84. Post
    Author
  85. Post
    Author
    Josip

    Would somebody help me make my Tic Tac Toe have a scoreboard and make the board size user input (anywhere from 3×3 to 6×6)?

  86. Post
    Author
  87. Post
    Author
  88. Post
    Author
    Rishan Plays

    Can't you do document.getElementByClassName(".cell"); instead of document.querySelectorAll(".cell"); ?

  89. Post
    Author
  90. Post
    Author
  91. Post
    Author
  92. Post
    Author
  93. Post
    Author
    Youssef YouSSef

    in the last attempt there's a case when u hit the 3 cross but the program consider it like it's a tie

  94. Post
    Author
  95. Post
    Author
  96. Post
    Author
  97. Post
    Author
    Anish Sah

    Brilliant tutorial. Btw can you tell me how you got the browser output display to the right of the editor?
    Thanks,
    Anish

  98. Post
    Author
  99. Post
    Author
  100. Post
    Author
    Boris Hypecode

    You code doesn't work! I win several game on the last move and I got a "Tie game"… If an unbeatable ai is to don't recognize a human win so it's unbeatable… And I don't speak about looooong line of code without a word about it, the "const-let-var lottery" and the "you'll see later". Just take a little more time to explain what and why you do things and it'll improve your tutorial.

Leave a Reply

Your email address will not be published. Required fields are marked *