Minimax Algorithm for Tic Tac Toe (Coding Challenge 154)
In this challenge I take the Tic Tac Toe game from coding challenge #149 and add an AI opponent for a human player by implenenting the Minimax algorithm. Code: thecodingtrain.com/challenges...
🕹️ p5.js Web Editor Sketch: editor.p5js.org/codingtrain/s...
🎥 Previous video: • Coding Challenge #153:...
🎥 Next video: • Coding Challenge #155:...
🎥 All videos: • Coding Challenges
References:
🔗 Geeks for Geeks - Minimax Algorithm in Game Theory: www.geeksforgeeks.org/minimax...
📚 Minimax on Wikipedia: en.wikipedia.org/wiki/Minimax
Videos:
🏗 Algorithms Explained - minimax and alpha-beta pruning: • Algorithms Explained -...
🔴 Livestream Archive: • Coding Train Live 188:...
Related Coding Challenges:
🚂 #94 2048 Sliding Puzzle Game: • Coding Challenge #94: ...
🚂 #149 Tic Tac Toe: • Tic Tac Toe in p5.js (...
Timestamps:
0:00 Introduction to the challenge
2:17 Explanation of the Minimax algorithm
8:20 Start Coding
12:54 Check to see if anybody won
14:16 Recursively check the max score for all the spots (AI)
16:51 Recursively check the min score for all the spots (Human)
18:15 Refactor using min() and max()
19:05 Fix bugs
21:13 Final output
22:46 Ideas and Suggestions
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: kzread.infojoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#beginners #tictactoe #minimaxalgorithm #games #p5js #javascript
Пікірлер: 464
💻Code and community contributions: thecodingtrain.com/CodingChallenges/154-tic-tac-toe-minimax.html
@theunknown4834
4 жыл бұрын
why is this comment posted eleven hours before the video was? because he has a 2000IQ play to prevent people from commenting they are first.
@ankur.singhs2111
4 жыл бұрын
Hey by Minimax Algo the user will never win and eventually throw our game. How can we create the EASY MEDIUM DIFFICULT modes of this ? Please guide a little !
@abhikprithu9954
3 жыл бұрын
@@ankur.singhs2111 I was also thinking the same. Then I have come up with an idea. Instead of determining the AI move each time with miniMax, for few moves(may one or two) we can call a random function to make a move for the AI. This way users will get some chances to win the game. We can also vary the difficulty by changing the amount of random moves the AI will make.
@WaldoTheWombat
Жыл бұрын
The minimax function is not there
@erickoavenada969
Жыл бұрын
Hey, what type of javascript u usin
This reminds me of one time that i made Tic Tac Toe in Flash using AS2. I wanted to create unbeatable AI so i just hardcoded every possible move combination. It was about 4K lines of if statements.
@kevnar
4 жыл бұрын
I made a game once where you had to make your way through a maze with a monster hunting you. I needed an maze-solving algorithm to compute a path to the player at any given state. I had no idea what A* was back then, and there was no internet to look it up, so I created what basically amounts to a dead-end floodfill that leaves only the path to the goal. I had no idea that a dead-end floodfill was a thing either. I thought I invented it. We're living in wonderful times with millions of coders all sharing ideas.
@Unifrog_
4 жыл бұрын
@@kevnar Breadth-first search seems like it could still be quite useful if you have multiple entities trying to navigate to the one location and you search from that location until you find all of them. The end result being a tree that gives you the shortest path from all the entities to the target at once by traversing the tree back to the root on each.
@mariadimitrova3703
4 жыл бұрын
WOOOOOW
@SH1xmmY
4 жыл бұрын
Didnt u ever think that was a really brute force way of thinking
@dharmang
4 жыл бұрын
tf are u talking? 4k line lmao Wouldnt possibly go more than 200
Dan talking to the ai is the most adorable thing I've seen on the internet for a while 🤣 19:14 "No, no, Bad X! Bad X! 😡" 19:28 "Oh Woah! You're not going in order, you're making weird decisions" 19:56 "That's a good move X, I see what you did there 😏"
@abhijitkumarsinha
Ай бұрын
he was talking to his ex
I like how a simple game can be so complicated.
@CardinalHijack
3 жыл бұрын
It shows how powerful the human brain is. All of this is going on in your head when you play this "simple game". Even the most basic version: "which move means I don't lose" is being played in your head when you play tic tac toe.
@AnoNymous-ie3wc
3 жыл бұрын
@@CardinalHijack well, except a human player will not check every possible move and memorize them especially in a larger scaled game board
@WittyMick03
3 жыл бұрын
i dont
@pedroduran8927
3 жыл бұрын
haha, want real complexity? try do do the same thing but a Checkers or Chess game.
@superkaj1001
3 жыл бұрын
Exactly, I learned once the perfect play for both players but as the 1st player I always win/tie by going middle
i love how natural this teaching video is and you didn't successfully run it on the first try and that shows so much truthfulness to everyone who codes :') how it's okay to make mistakes and learn from it and be better every step of the way!
I listened to your explanation of the algorithm first and tried to implement it before seeing your way of doing it. I spent close to all night finding all the little bugs in my program and seeing you stumble your way across it yourself made me feel much better about my night lol :'D. Thank you, you've made creative coding very precious to me.
It's crazy how this is my current homework assignment and here I'm sitting watching a step by step tutorial how to solve it. Like it's too good to be true. THANKS for this!
@AhmadMahirShadab_1
Ай бұрын
mind if i ask, what school did give you this assignment?
I've wrote a form of minimax function in my own board game. I used depth in a reverse way, instead of starting at 0 and incrementing I started at a set value and decremented, when the minimax function was called with a depth of 0 it would just make a random move. Doing this let me use the depth variable as a Difficulty setting for different AI. Easy had a depth of 0 (so it just played randomly), Novice had a depth of 1, Intermediate was randomly either depth 1 or 2, Hard was depth 2 or 3, and Insane was always depth 4.
You explained this complex algorithm without assuming prior knowledge so it was SUPER easy to follow. Thanks a lot!!
This made me laugh with all the drum rolls haha nice, love it, happy i caught two of the errors before you did it made me feel better xD Thanks for this btw, very helpful with visual learning with additional commentary too. Cheers!
Thank you so much! I've tried for weeks to understand and implement this algorithm, but after watching this video i've finally done it!
bro you have no idea how this helped, thank you so much!
This was my first project about making an AI! Thank you for making this tutorial, it helped me a lot!
"I think this might actually be good" *
really like your simple way of explaining the concept, save my night. To me, the term each player playing optimally was the confusing part that is actually connected to the choice of optimal score from each layer in the tree.
Fantastic video. So well explained with so much energy.
This guy thanking vscode for everything it fixes for him and everytime it points him to an error is the only thing keeping the human race from being dominated by AI. Loved it, subscribed
BEST explanation of MINIMAX. Thank you!
I implemented this and then set up a game with two random starting moves followed by the minimax algorithm playing against itself. I found that the ai just gives up if it cant win since losing in 3 moves is no worse than blocking and losing in 4. dividing the winning score by the depth made the algorithm avoid losing sooner because taking longer to lose means less of a score against it.
You are an amazing educator! Fantastic stuff.
I really like you. You are a great person for what you do on KZread but no bad person would be so generous with knowledge. Thank you for being you
This is one of the best explanation which i ever see for the minimax algorithm, thanks for sharing..
Hey Dan! I have a recommendation for you since you do *a lot* of multidimensional array loops in your videos. May I suggest a useful abstraction to reduce code duplication: The gridForEach! (this can either be a method on an object or a global method) The gist is that instead of writing all these for loops over and over, we can write it once in this method and use higher order functions to our advantage. This one is specifically made for the loops in this video, but it can be easily changed for any style of loop: function ticTacToeForEach(action){ for(let i = 0; i for(let j = 0; j action(i, j); } } } Or alternatively, function ticTacToeForEach(action){ for(let i = 0; i for(let j = 0; j action(board[i][j]); } } } Now instead of rewriting that loop everywhere, we can just do: (first implementation) ticTacToeForEach( (i, j)=> { // board[i][j] = ... }); (second implementation) ticTacToeForEach( cell => { if ( cell === 'X' ){ } }); I do this all the time when working with grids. class Grid { constructor(rows, cols){ this.rows = rows; this.cols = cols; this.cells = [ ]; } forEach(action){ for(let i = 0; i for(let j = 0; j action(cells[ i ][ j ]); } } } } Now to loop over our grid we can do myGrid.forEach( cell => { cell.isFlagged = false; // now you can operate on cells without caring about index positions }); Of course this can be varied as necessary. The grid foreach could easily also return the index values if they're needed. Hope this can be useful
@celebezz
2 жыл бұрын
LOL NERD
@onebacon_
Жыл бұрын
@@celebezz did u actually call someone a nerd on a programming video. BRO YOU'RE ALSO HERE
Thank you for the explanation and the funny examples!
Awesome video. Thanks. I was struggling in applying minimax in my tictactoe in python. This video helped me a lot.
I didn't knew about the algorithm and I used recursion calls to predict the CPU next move, will definitely try the algorithm and very well explained!
The best first move is always the center, and that should be pre-programmed. It blocks the most wins for the opposition and makes the first players chances have the most potential win positions.
Thanks for making this video! You make programming very fun!
Holy cow, so concise man, thank you!
Woot woot! Another epic coding train journey!
It was fun to watch, and the explanation of the algorithm was also clear and understandable.
Still fun and amazing🤣thanks you Dan
This was a lot to watch! Thank you
I watch your videos for fun !!! You are hilarious
I don't even know javascript, I know c# and java. I just love his problem solving approach. Absolutely amazing
20:45 im dying laughing. I'm saying this around the house all day to today!!! XD
your explain is amazing especially your innovation of how to be programmed on your computer, and the background is the code screen and your movements on it. wow thanks alot
Would you like to play a game ? Falken: Did you ever play tic-tac-toe? Jennifer: Yeah, of course. Falken: But you don't anymore. Jennifer: No. Falken: Why? Jennifer: Because it's a boring game. It's always a tie. Falken: Exactly. There's no way to win. The game itself is pointless! But back at the war room, they believe you can win a nuclear war. That there can be "acceptable losses."
Wow, this guy is an amazing teacher. I could know, cus' I'm extremely dumb (when it comes to things like this) and I do understand it now.
Awlll .... This was so wholesome and fun to watch!!
Welcome back Dani...🎉
Thanks for this! :D
Do you stalk my life by any chance? Literally learned about min max algorithm the very same day you uploaded this video.
Thanks ^^ Your video help me to understand this algorithm.
It's working, thank you very much.
I used this manually to find the ultimate play for the game my friend made
@isamiwind438
4 жыл бұрын
I'm curious what was the game
@whistletoe
4 жыл бұрын
oooh what was the game?
@blasttrash
3 жыл бұрын
what was the game dude?
My actual FIRST interaction with a computer was maybe in 1970 at some sort of freestanding Tic Tac Toe kiosk at the Los Angeles Museum of Natural History. It amazed me that I could interact with a TV screen and that it seemed intelligent!
jzz loved your technique for explaining codes❤️
great video! one tip: not copying the entire matrix worked in this case, but won't work in games when tokens move or change like in chess or reversi
very clear !! Thanks
Instructions unclear. Made a multiplayer game instead
This game never gets bored!
Dude you are amazinge i love the way you solve the problem 😍👍
I think for the first time we all are happy to see that our opponent is winning 21:48 , yea it seems like this AI is my child 💗
When I wrote a tic-tac-toe game in high school, I had a loop check every row, column and diagonal for a scenario where the AI could win by selecting an empty spot: an O-O-blank scenario. If it found one, it filled it and won the game. Next it would look for scenarios where the player would win, X-X-blank, and block them by choosing the empty spot. If it couldn't find either scenario anywhere on the board, it would just choose one at random. With only 9 spaces and half of the turns belonging to the player, the AI quickly becomes reactive and competitive instead of random. It wasn't perfect, and my implementation was awful with giant nested if-then-else trees, but the finished product worked and was as fun as you could expect from tic-tac-toe.
@TheCodingTrain
Жыл бұрын
Thanks for sharing!
I remembered minimax being a thing to use with tic tac toe, but didn't remember the code, so I wrote my own thing. Your version is way simpler. It takes a good programmer to write simple code.
@d4m4s74
3 жыл бұрын
My version does have a function that, if it knows it loses it at least makes it take as long as possible
Thanks i made it finally and learnt it
Awesome idea! I can make functions for each set of move so that is like a tree!
You've helped me a lot starting with javascript ( in the most interesting way possible the DANI WAY) ... thanks 🤗
I wanted to implement it for another game but I couldn't fully remember the principles of minmax, which I would like to use. Really enjoyed your video
This would not help in this game, but for a chess game or connect-four, if you can't go through all possible depths, you can add a fourth and fifth weight to the results. Win, Lose, Tie or Opponent-Stale, Me-Stale, Opponent-loss, Me-Loss. Being stale equates to an inability to win, lose or tie, and also to not have lost something, like in chess. A loss, such as losing a piece, not the game. A win, clearly being +8. A Loss being -8. A tie being +4. An opponent-loss +2. Me-loss -2. Opponent-stale +1, Me-Stale -1. If you can't win, then you want to tie, to end quick. If you can't do either, then it is better that an opponent has a loss, or that they are unable to win, lose, tie or make you have a loss. (Depending if you are playing for points or just a win... Desires might change. Also not all would apply to some games.) I really wish there was a better game for playing and training with AI and minimax. Though this game is good to show that when done "not bad", AI VS AI and AI vs Player, should always result in a tie. Connect-four is a good one, with simple logic, which minimax would work great on, as well as any card games that are not just "blind luck draws". Chess is good for deep-learning, heuristics and working within constrained depts. There is another game which is expandable, simple and can easily be adapted to minimax and weighting and AI training. I forgot what it is called, but it is a line-game. You have a grid of dots and each player makes a line, on each turn. The goal is to make the most "boxes". If you make a line and it creates a box, then you get that box and you get one more move after. (Done right, with a good setup, you can get many boxes in one turn.) It doesn't require any real complex visual display and the rules are simple. The board can be as complex or simple as needed. It can have obstructions, voids, pre-made "lines", be small or massive. There was another game called "SOS", but I forgot how that was played. The rules were equally as simple.
Entertainment + Coding = Coding Train
You are a legend!!
Thank you!!! :)
thank you very much because there is no video available in French and even if you speak English I understood more than I would have imagined. Now I can do mine in French. :-)
@marcgenevey
Жыл бұрын
Tout à fait d'accord !
You've taught me more about the basics of game development than any game development channel.
thank you!
Entertaining and engaging
thank you so much
Omg Dan, the site is beautiful
Tnx for this nice and informative video
Amazing!
Purely Awesome..
Minimax algorithm is well explained ❤️
22:37 If you start, you can never lose. You went top left, which is correct. It goes defensive, and goes central. You should now go on the opposite diagonal (bottom right). This opens two paths for you to win. It can block with either blocking one of the other corners (defensive), or a outer-central square (offensive). If it goes defensive, you take the other open diagonal and have two paths to win. If it goes offensive, you block, and force a draw. Given how minimax works, my bet is it goes offensive, and you are forced into the draw, every single time. If the computer starts, you always lose. Don't let it start.
@hwfjj1989
4 жыл бұрын
Every game should be a draw if both players are playing correctly.
Nice program, easy to follow, but would it be easy enough to make it higher dimensional? Like say 3D tic-tac-toe, or even 4D?
thanks a lot
U ARE AMAAAAAAAAZIIIIIIIIIIIIING ILY
Quick question please. Hey, this has helped a lot - I've implemented it in C++, well trying - my game can do a larger custom sized grid and the 3 in a row is also custom. i.e. win checks of 2-5 in a row. For some reason it only puts a O in the first box, and everything looks good. I've been here for 5 hours now without looking for help.
You're a great teacher
Hey i have a challenge/ suggestion for you. A dungeon core ai simulator. A simulation where two A.I.’s fight each other. One an intruder running through a dungeon, fighting the inhabitants and looking for treasure, with the goal of getting to the core, and the dungeon’s core seeking to protect its life. Every time the intruder wins by killing the core the simulation starts again. However, the core remembers what happened last time, it remembers everything the other A.I. does. When the dungeon wins, a random (or fixed) amount of time passes without the interference of new intruders. After that time new intruders come. When the intruder survives the dungeon, they leave and all intruders that follow them know what they experienced in the dungeon. If the intruders all die no new information about the dungeon reaches the next intruders. The A.I. that controls the core can change things about the dungeon within a set of rules. Create monster, make them stronger, absorb dead creatures, and many such things. The A.I. can upgrade itself, the core, and the dungeon itself, with some rules and limits. There must always be a direct path to the core from the entrance of the dungeon.
X’s second move is not optimal as it forces a tie. Going to the opposite corner or edge after you go in the center is much better as it keeps the game going, allowing the player to make a mistake without the risk of the player forcing a win. X going to the opposite corner on move two returns a 1/3 winning chance, while going to the opposite edge on move two returns a 5/12 winning chance, AKA the best move
I want say REALLY REALLY REALLY THANK YOU even I don't know how to make my Tic-Tac-Toe AI and even I'm never learn about Algorithm and you explain it with very clear and very easy to learn Thank You Sir, now I have the best Tic-Tac-Toe AI that's maybe never Lose (I never win against it) One more THANK YOU VERY MUCH (^v^) Wish you have a nice day and can teach us more about cool Algorithm like this
Superb explanation
The obvious next step after teaching Tic-Tac-Toe to an AI is Global Thermonuclear War.
I have done all the steps I mentioned except designing a triple table, which requires more effort from me and because I am not good at art
Is there a video that you did this code from sketch for all the JS, html CSS codes?
thanks
You'r the best♥️
Try it on a bigger board, I.e 5x5 or 6x6, but you still only need 3 in a row to win. Would give far more possible game states and probably more varied gameplay
@kingasasin177
3 жыл бұрын
Imagine if the game board was also wrapped so you could have like x x o o x in a row and x would win
First time seeing this KZreadr, that intro man. Wasn't what I was expecting at 1:15 AM!
I have impress that AI is just all posibilities calculated but no a decision inself.
merci pour ce cours (France)
the video shows exactly when i start an AI for connect4 !!!
@beri4138
4 жыл бұрын
How did it go?
I love how it only takes 30 minutes to code a Tic Tac Toe AI that can’t be beaten.
Dude I LOVE Sebastian League
wow, best teacher online
You made me think of my favorite lecturer. Keep up the quality video
Great video. Both illuminating and funny. I'm a bit confused about one aspect of this algorithm. In this video (and other solutions I've looked at) the depth variable is passed into the Minimax function but I don't see where it's actually used within the code. What am I missing?
@qwest500
2 жыл бұрын
The depth is just a counter variable used to keep track in case of wanting to time the function or limit the function in larger games. ( 11:44 ) In this game, he only uses checkWinner() to end the recursive call, but alternatively if he wanted he could set a depth threshold to end on as well. (If no win is found before depth = 4, end, for the sake of processing power or time). Tldr: I believe depth isn’t used in this video, just there for practice
I'm also unbeatable. I memorized all the patterns years ago and still haven't forgot them. I play sometimes against a computer, (even the impossible ones) to make sure I'm still not rusty.