Minimax Algorithm for Tic Tac Toe (Coding Challenge 154)
ฝัง
- เผยแพร่เมื่อ 13 พ.ค. 2024
- 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: th-cam.com/users/thecodingtrainjoin
🛒 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
💻Code and community contributions: thecodingtrain.com/CodingChallenges/154-tic-tac-toe-minimax.html
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.
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 !
@@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.
The minimax function is not there
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.
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.
@@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.
WOOOOOW
Didnt u ever think that was a really brute force way of thinking
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 😏"
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!
You explained this complex algorithm without assuming prior knowledge so it was SUPER easy to follow. Thanks a lot!!
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!
I like how a simple game can be so complicated.
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.
@@CardinalHijack well, except a human player will not check every possible move and memorize them especially in a larger scaled game board
i dont
haha, want real complexity? try do do the same thing but a Checkers or Chess game.
Exactly, I learned once the perfect play for both players but as the 1st player I always win/tie by going middle
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!
bro you have no idea how this helped, thank you so much!
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!
This was my first project about making an AI! Thank you for making this tutorial, it helped me a lot!
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
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.
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.
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.
Holy cow, so concise man, thank you!
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 < 3; ++i){
for(let j = 0; j < 3; ++j){
action(i, j);
}
}
}
Or alternatively,
function ticTacToeForEach(action){
for(let i = 0; i < 3; ++i){
for(let j = 0; j < 3; ++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 < rows; ++i){
for(let j = 0; j < cols; ++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
LOL NERD
@@celebezz did u actually call someone a nerd on a programming video. BRO YOU'RE ALSO HERE
This is one of the best explanation which i ever see for the minimax algorithm, thanks for sharing..
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!
BEST explanation of MINIMAX. Thank you!
This was a lot to watch! Thank you
I really like you. You are a great person for what you do on TH-cam but no bad person would be so generous with knowledge. Thank you for being you
Awesome video. Thanks. I was struggling in applying minimax in my tictactoe in python. This video helped me a lot.
Thanks for making this video! You make programming very fun!
Thank you for the explanation and the funny examples!
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
Awlll .... This was so wholesome and fun to watch!!
I watch your videos for fun !!! You are hilarious
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
Thanks ^^ Your video help me to understand this algorithm.
"I think this might actually be good" *
Welcome back Dani...🎉
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.
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
I don't even know javascript, I know c# and java. I just love his problem solving approach. Absolutely amazing
Tic Tac Toe Game in JavaScript | JS Project Day 1 | JavaScript Full Course : th-cam.com/video/LQ99hNQ-lzM/w-d-xo.html
jzz loved your technique for explaining codes❤️
Do you stalk my life by any chance? Literally learned about min max algorithm the very same day you uploaded this video.
very clear !!
Thanks
Thanks for this! :D
It's working, thank you very much.
This game never gets bored!
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.
My version does have a function that, if it knows it loses it at least makes it take as long as possible
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.
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
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!
I used this manually to find the ultimate play for the game my friend made
I'm curious what was the game
oooh what was the game?
what was the game dude?
Dude you are amazinge i love the way you solve the problem 😍👍
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.
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
Awesome idea! I can make functions for each set of move so that is like a tree!
20:45 im dying laughing. I'm saying this around the house all day to today!!! XD
Thanks i made it finally and learnt it
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.
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.
Thanks for sharing!
You are a legend!!
Omg Dan, the site is beautiful
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?
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. :-)
Tout à fait d'accord !
Thank you!!! :)
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
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
Minimax algorithm is well explained ❤️
Amazing!
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."
cubed tic-tac-toe sounds great, initially. but...how would one pick the middle??
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.
Every game should be a draw if both players are playing correctly.
Is there a video that you did this code from sketch for all the JS, html CSS codes?
thank you!
You've taught me more about the basics of game development than any game development channel.
You've helped me a lot starting with javascript ( in the most interesting way possible the DANI WAY) ... thanks 🤗
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 💗
I have been trying tic tac toe minimax for weeks and i still can't figure it out...
Purely Awesome..
You can try applying expectiMax algorithm a here, Its not always the case that opponent plays optimally.
Tnx for this nice and informative video
What is the speedup tune that plays?! I absolutely love it!
thank you so much
Entertaining and engaging
You made me think of my favorite lecturer. Keep up the quality video
What would happen if you set the score to a tie also -1 instead of 0? Will it then always win?
What is the use of parameter "depth" since we explore all the possible configurations?
He didn't use it, BUT in the end he suggested that maybe the score for every case could be affected by depth
I’ve been wanting to do this for Chess for a long time with minmax so this was exciting to see in subscriptions tab. My goal: make a chess game that can beat me (in Python). The first i,j loop you wrote which calls minmax seems redundant because you can just call minmax with the opposite isMaximizing value I think.
lol, I started just a couple of days ago( github.com/Howuhh/chess_minimax ), and before that I did it for tic tac toe, and here's the video! for Python you can use chess library, its really have all you need
I'd recommend you get worse at chess
@@aeronevans4337 HAHAHAHAHAHA
Instructions unclear. Made a multiplayer game instead
I realize that writing chess from scratch may be too much for a video, but how about using a pre-existing library and just focusing on the minimax aspect? I'm curious to see the hurdles of a larger scale game.
You're a great teacher
merci pour ce cours (France)
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
Hello,
in recursive steps the is the grid always the same, or is it a copy with a new move for every iteration?
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?
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
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.
Superb explanation
great explanation! I have understood most of the code, but can someone please explain me 'depth' and calling the minimax function recursively using 'depth+1' , and how does it help/ work. TIA
U ARE AMAAAAAAAAZIIIIIIIIIIIIING ILY
Hey there. Do you intend to continue the rubik's cube coding challenge?
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.