Code Bullet: I created an AI to Play Chess

Hey guys, what is up? It’s your boy, the big CB. What a dumb intro. Today I’m gonna be tackling the little-known game called, wait, what is it? Oh yeah, chess. Yeah, chess. You know, the one that was famously conquered by IBM’s deep blue in 1997. Yeah, so this is gonna be like that. Only we’re gonna make this one a little bit different. It’s going to be worse, much worse. I’m only one man. Okay, now that I’ve picked your interest, let’s jump into making the digital version of chess. I’m using JavaScript language to code this bad boy. So when it’s done, you guys can just click a link and try to bait it and you probably will. Alright, the first thing is to make the checkerboard grid thing. Boom. Next up, we need to add a piece object, which will just store all the functionality, which is universal for all the chess pieces. And then we’ll add a king piece, which contains all the functionality unique for the king piece. Of course, I’ll add all the other pieces later, but let’s just start with the king. Now we need a board object to store all the pieces. And wait for it. Boom. That’s a king on a board, maybe hell yeah. Okay, let’s add all the other pieces and position them on the board. Very nice. We got the pieces on the board. They don’t do anything, but they sure do look pretty. Okay, so we’re gonna want to move these pieces around. So first, let’s start by being able to move any piece to any space. Okay, you can do that now, magical. The pieces also don’t take each other, so you can just stack them up, which is nice. Let’s start trying to stop the player from being stupid. Okay, let’s go through all the pieces. First up is the king. The king could move in any direction, but only a distance of one block. Next is the queen. She can move horizontally and vertically. I don’t know why I’m telling you all this. I’m 98% sure you guys know how to play chess, so I’ll just speed through the next few. Piece of them looks easy because the logic was already done for the queen. Now it’s moved weirdly. They can just jump shit, which is great because at the moment all the pieces can do that. Points are actually the hardest because they can do whatever they bloody want, like move two on the first turn and attack diagonally and stuff. And yeah, that’s all of them. We also need to stop pieces from moving onto their own teammates, and with an exception of nights, we need to stop pieces from moving over other pieces. What am I doing now? I thought we were pretty much done. Obviously, we need to make pieces take enemy pieces when they land on them. Now we just need to alternate between white and black turns, and we are done. Hell yeah. Okay, so I added some sprites for the pieces, so they’re not just letters, and I’m really happy with how it turned out. So you can see that game is now done, and if you want to move onto, sorry, that was as long as I could last for the straight face, but this is so stupid. So I scaled the images down a bit so the game is actually usable. Now we’ve got the game happening, now we just need some friends to come over and play it with. Who needs friends when you can make your own? I’m so alone. Okay, let’s talk AI. Evan, you should use neural networks. Yeah, that’s a good idea. If you want to waste your life waiting for it to train, now screw that. We’re going to be using an algorithm called minimax. Alright, to help explain minimax, we’re going to play a little game. It’s a shit game, but trust me, it’s important. So we have this tree. There are two players. Player A is trying to reach the highest number possible, and player B is trying to reach the lowest number possible. Each player takes turns to pick a direction to go down the tree. For example, player A chooses left, and player B chooses right, and player A goes left, and player B goes right, which gets to a score of 6. So the question is, assuming that player B is perfectly logical and plays the best moves possible, then which move should you make first as player A? Pause the video if you want to figure it out for yourself. So the trick is to work backwards. Start from the bottom and figure out if player B was at each intersection on the bottom layer, which direction would they choose? So remember B is trying to minimize the score. So for the bottom left, they would choose the right direction as it is the lower of the two. This means that the red player should consider the value of that intersection to be 2, as assuming that player B plays logically, there is no way of reaching that 9. We do this for the rest of the intersections in that layer. Then we look one layer up, and think if player A was at each of these intersections, which action would they take? And looking at the left most one again, we now know that going left will result in a 2, and going right will result in a minus 1, so we choose 2. Go up another layer, and then it’s B’s turn, and finally you are left with the choice of going left to reach a 2 or going right to reach a 1. If you can’t figure out which direction to go now, then there’s no helping you. And that’s great, Norbert, what does this have to do with chess? I’m glad you asked, otherwise the segway would be difficult. And it’s hard, chess is just a big game of minimax. Hear me out. We can create a scoring system by giving values to all the pieces, then adding out all the white piece values, and then subtracting the black piece values. So from white’s perspective, you are trying to reach a high score, as that means that more good white pieces are still on the board, and from the black players perspective, you are trying to reach a low score. Does this sound familiar? Like anything I’ve been recently talking about in detail? It’s minimax, baby! But instead of only being able to do 2 moves, like in our little minimax example, on the first turn, white has 20 possible moves, and then black has 20 possible moves. Which means that this tree gets big quick. Like in our example, after 4 moves, we had 16 scores to choose from. However, with chess after 4 moves, we have about 160,000 scores, which is fun, and we’ll address this later, we’ll reduce that a bit. So our AI needs to generate all the boards, which is possible to race from our current one, within a certain number of moves. Then calculate the scores and do some cheeky minimax to find the best possible move it can take. Alright, enough talk, let’s get the AI going. Let’s start with an AI looking one move ahead. At this point, he plays more or less like a toddler. He doesn’t think about what the other player must do, he just takes the pace with the highest value. This is hardly impressive, and pretty easy to beat, even for me. So let’s step it up a notch, now he looks 3 moves ahead. This means that he thinks of every possible move he can do, then for each of those, he thinks of every possible response the enemy player can do, and for each of those responses he thinks of every possible move, he can do in response to that enemy move. So yeah, it’s a bit. Now this worked reasonably well, good enough to beat my sorry ass, but Grandmasters think like something like 7 moves ahead, and IBM’s Deep Blue was able to beat them. So we got a fair way to go. Let’s try for 4 moves. Ah shit. This has taken way too long. Come on, anytime now. Viewer attention is dropping. Okay, screw this. We’re going to need to change our mini max formula a little bit. Introducing Alpha Beta pruning. I’m not going to explain here in huge detail, but there are plenty of boring YouTube videos you can watch if you want to. But let’s have a look at our old example. Alright, so we got an example here. Let’s start in the bottom left. So B is going to try and minimize the score, so we got 9 and 2. It’s going to pick 2. Alright, we got A is going to try and maximize these 2 scores, so we need to figure this one out first. So if B is here, it’ll pick minus 1. So now A should consider this intersection 2, this intersection minus 1. Okay, pick 2, go up here. B is going to choose the lowest of these 2. So we need to figure out what this will be. So we got 2, come down. A is going to pick the biggest of these 2. Don’t know any of those. So B is going to pick the least of these. That’s going to be 3. We know that A is going to choose the greater of these 2. We don’t know what this is, but we don’t actually have to figure this out. Because we know that it will be at least 3. Right, if there’s something greater than 3, AL choose that. So AL choose at least 3. B has the choice of 2, or something which is greater than or equal to 3. So it’s obviously going to choose the rate of 2. So without even checking this area, we know that B is going to choose this direction. So that’s how we’re going to reduce the number of scores we look at. Because we didn’t even need to check out these scores. And so that’s Alphabet approoning. That’s the basics of it anyway. So I’ve now implemented Alphabet approoning, and let’s see how long it takes to do 4 moves. Hey, that’s not terrible. That’s not the worst. Now that we’re more or less happy with the AI, let’s test it out. Hmm, what to do? I kind of suck at chess, and I can’t be bothered playing seriously. So there’s this game known as chess level 100, which you can get from the Microsoft Store, where you can adjust the difficulty of the chess AI. So we’re just going to let the AI’s battle it out. And fight! Oh my god. Oh my god. I’m making a lot of really bad AI lately. Not bad. Here’s what we’re going to do. It’s not getting through. I’ve been here for an hour and a half. Waiting to beat the first bloody level. So I’ll let my AI just fight itself, and I’ll talk about why it’s terrible. So, he’s no IBM D-Blue. Sad. What is wrong with it? Well, chess is a complicated game. It’s not as simple as a sani values to each piece, and telling the AI to get the most points. There are many more variables at play. For example, the positions of the pieces are important. Like a rook which is stuck in the corner, it’s not nearly as valuable as one which can move around. That’s how AI struggles in the early game, where the whole point is to get pieces in the most strategic positions. To solve this, AI is often have dictionaries of starting most to rely on in the early game. Also, in my version of chess, there’s no real concept of stalemate. So when it’s looking ahead, it doesn’t consider that as an option, which means it always runs into that problem. And there are so many other things that we can add to this AI to make it actually good. But this video is already long enough, so I might improve it in a later video and see how high the chess 100 we can get. If that sounds interesting, leave a comment, let me know. If you’re still here, I bet you’re interested in artificial intelligence. Well then you should check out Brood.org, which states to how to think like a computer scientist. Instead of just passively watching a computer learn over generations, which is what most of my videos are, you get to actually learn and master these concepts by solving fun and challenging problems. Brood has a new course on machine learning with interactive lessons to help you explore the versatile model of search trees. They break down complicated topics into smaller chunks, which makes mastering really difficult topics super easy. So what are you waiting for? The first 200 people to use this link, we get 20% off the annual subscription. So if you want to deepen your understanding of machine learning and support this channel at the same time, then you should go check them out. I’m sorry if I sounded a bit raspy in this video. I’m a bit sick still. I got brokeitis. I actually do though. It’s only the light version, but it’s still not ideal. Yeah. Bye.