Minimax Algorithm for Tic Tac Toe (Coding Challenge 154)

[@TheCodingTrain]

💻Code and community contributions: thecodingtrain.com/CodingChallenges/154-tic-tac-toe-minimax.html

[@theunknown4834]

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]

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]

​@@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

[@dobroslavtokos5013]

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]

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_]

@@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]

WOOOOOW

[@SH1xmmY]

Didnt u ever think that was a really brute force way of thinking

[@dharmang]

tf are u talking? 4k line lmao Wouldnt possibly go more than 200

[@fridaaa0]

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?

[@RasperHelpdesk]

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.

[@breakthroughwithdr.d]

interesting take Rasper, you approach proves without question that AI is not even remotely real Artificial Intelligence. Its computer learning, which is completely bound and always will be completely bound by the golden rule "GIGO"

[@sarahallisa7005]

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!

[@anonymosranger4759]

I like how a simple game can be so complicated.

[@CardinalHijack]

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]

@@CardinalHijack well, except a human player will not check every possible move and memorize them especially in a larger scaled game board

[@WittyMick03]

i dont

[@pedroduran8927]

haha, want real complexity? try do do the same thing but a Checkers or Chess game.

[@GaraxyAurora]

Exactly, I learned once the perfect play for both players but as the 1st player I always win/tie by going middle

[@Unifrog_]

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.

[@whistletoe]

You explained this complex algorithm without assuming prior knowledge so it was SUPER easy to follow. Thanks a lot!!

[@kissesfromcrocodiles4600]

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.

[@danielerusso_1589]

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!

[@tcjoker]

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

[@aditya95sriram]

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

[@ambysoo]

LOL

[@seancpp]

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

[@celebezz]

LOL NERD

[@onebacon_]

@@celebezz did u actually call someone a nerd on a programming video. BRO YOU'RE ALSO HERE

[@JD_Mortal]

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.

[@hosseinmomeni2954]

after 19:30 we can all agree on "never copy paste a block of code"

[@JD_Mortal]

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.

[@petfama4211]

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

[@ipechman]

bro you have no idea how this helped, thank you so much!

[@robertroberto4749]

BEST explanation of MINIMAX. Thank you!

[@prachinainawa3055]

So good explanation

[@VierSiebenAlliance]

Thank you for the explanation and the funny examples!

[@SantaClausdtm]

I really like you. You are a great person for what you do on KZbin but no bad person would be so generous with knowledge. Thank you for being you

[@algawiye3182]

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

[@jtsoldier]

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]

Every game should be a draw if both players are playing correctly.

[@miigashish]

I don't even know javascript, I know c# and java. I just love his problem solving approach. Absolutely amazing

[@theunknown4834]

I used this manually to find the ultimate play for the game my friend made

[@isamiwind438]

I'm curious what was the game

[@whistletoe]

oooh what was the game?

[@blasttrash]

what was the game dude?

[@d4m4s74]

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]

My version does have a function that, if it knows it loses it at least makes it take as long as possible

[@vickyparihar7665]

You've helped me a lot starting with javascript ( in the most interesting way possible the DANI WAY) ... thanks 🤗

[@blushingbutterfly7742]

This was my first project about making an AI! Thank you for making this tutorial, it helped me a lot!

[@tafferinthedark]

"I think this might actually be good" *

[@josefindelamotte3824]

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!

[@virajsamani8083]

Thanks i made it finally and learnt it

[@marcchen4574]

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.

[@pencoftgulubane1452]

Is there a video that you did this code from sketch for all the JS, html CSS codes?

[@Bluehawk2008]

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!

[@Seawolf159]

I have been trying tic tac toe minimax for weeks and i still can't figure it out...

[@SimpleCarGuy]

This guy is so pleasant to watch, I wish I had this energy and positivity! Also, thanks for leaving the mistakes in, doesn’t make me feel so dumb.

[@rivards1]

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!

[@jusephwinclic165]

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

[@guy6311]

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."

[@alitaylan4267]

This is one of the best explanation which i ever see for the minimax algorithm, thanks for sharing..

[@sachintharuka6154]

Minimax algorithm is well explained ❤️

[@namyak-bf9od]

i tried to follow, but couldn't get the setup right. it always spawns two O objects when i click

[@namyak-bf9od]

I got it figured out, just took like 15 hours of chatGPT helping me. I did it in unity, so there wasn’t a clear tutorial to follow

[@CardinalHijack]

Fantastic video. So well explained with so much energy.

[@rekyo3116]

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!

[@AaronProgZ]

Thanks for making this video! You make programming very fun!

[@vickyparihar7665]

Welcome back Dani...🎉

[@trifortay]

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.

[@misterp9084]

What is the use of parameter "depth" since we explore all the possible configurations?

[@luksky0795]

He didn't use it, BUT in the end he suggested that maybe the score for every case could be affected by depth

[@drivers99]

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.

[@howuhh8960]

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

[@aeronevans4337]

I'd recommend you get worse at chess

[@SystemOfATool]

@@aeronevans4337 HAHAHAHAHAHA

[@ashadodhiawala5039]

Can you make a sudoku solver as a coding challenge

[@findus8269]

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.

[@fatimazahrachriha9103]

I watch your videos for fun !!! You are hilarious

[@tanmayagarwal8513]

Entertainment + Coding = Coding Train

[@akhilsharma1778]

Awesome video. Thanks. I was struggling in applying minimax in my tictactoe in python. This video helped me a lot.

[@charliecode]

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 !

[@gdxx100]

I have impress that AI is just all posibilities calculated but no a decision inself.

[@krccmsitp2884]

It was fun to watch, and the explanation of the algorithm was also clear and understandable.

[@doomkeepercanada]

You are an amazing educator! Fantastic stuff.

[@anidea8012]

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 💗

[@pradeepkumarreddykondreddy7048]

You have not at all used 'depth' parameter in the minimax() function. What is the use of depth parameter in minimax() function. You forgot to use depth or is it not required ?? Does it need to be used as terminating condition in minimax() function ??

[@PhenixArcher]

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.

[@TheLunarah]

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

[@PraisePelumi]

wow, best teacher online

[@carlsb3rg]

Somehow no-one has commented that there is no point in passing the global variable "board" as a parameter to the minimax() function, or that checkWinner appears to be operating on the global variable and not the one passed as a parameter (which happens to work since they are references to the same object). Great video as always, though :)

[@phos4us]

Woot woot! Another epic coding train journey!

[@virtual_GaRy]

You missed something. If CPU plays a corner and you play centre, then CPU would win by playing opposite corner and follow it up in another corner, on the opposite of your move from the first moves diagonal. However your CPU does not play that second move. The only real way to not lose for the 2nd player is to play opposite corner after CPU puts it in a corner as its first.

[@felixdiestelhorst]

Can you make one video with the alpha and beta algorithms ?

[@pradeepkumarreddykondreddy7048]

Entertaining and engaging

[@NaotoHieda]

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

[@Hallomn]

Instructions unclear. Made a multiplayer game instead

[@abhisheksahu4428]

jzz loved your technique for explaining codes❤️

[@stickguy9109]

a month of struggling and rewatching again and again. I am still not able to implement this

[@apollossevere8602]

Awlll .... This was so wholesome and fun to watch!!

[@justgame5508]

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]

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

[@atrumluminarium]

*Fun fact:* whoever occupies the middle square in tic tac toe has a very big advantage in the game. In fact, for two perfect players, if whoever goes first plays the middle the game is guaranteed to end in a draw. Source: Numberphile Edit: Thank you for the replies pointing out my error it's fixed now

[@geetaagarwal4622]

Fun fact:You are wrong

[@wertik4536]

You can actually come up with a counter move to make it a tie, not a win tho.

[@atrumluminarium]

Double checked you guys are right I'll fix my comment thank you. Apologies I saw the video a long while ago

[@Democracy_Manifest]

You're a great teacher

[@Toopa88]

Do you stalk my life by any chance? Literally learned about min max algorithm the very same day you uploaded this video.

[@MitsuoRLCoach]

20:45 im dying laughing. I'm saying this around the house all day to today!!! XD

[@cyberkraken1606]

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?

[@qwest500]

thank you!

[@wege8409]

Holy cow, so concise man, thank you!

[@joshuabowman515]

First time seeing this KZbinr, that intro man. Wasn't what I was expecting at 1:15 AM!

[@thekapilkhandelwal]

You can try applying expectiMax algorithm a here, Its not always the case that opponent plays optimally.

[@DrWho2008t101]

thanks

[@stoicfloor]

This game never gets bored!

[@MuhammadAhyaAulia-xb7bt]

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

[@adi2rox]

This was a lot to watch! Thank you

[@carlitoz450]

why if you start at center ? btw thanks for your videos, they're both fun and really well done

[@carlitoz450]

i did a connect four program in Prolog in my early university years.... that was so before that kind of tutorial existed.... I wish I could have so precious material back then !

[@sarayan8749]

U ARE AMAAAAAAAAZIIIIIIIIIIIIING ILY

[@mohammadhoseinmolaian7759]

Dude you are amazinge i love the way you solve the problem 😍👍

[@piotrjaga6929]

thank you so much

[@SolvingOptimizationProblems]

It's working, thank you very much.

[@user-pw5do6tu7i]

MIT's lecture is also very good

[@LudumWon]

This man drew on his wall 😂

[@ryanyang3347]

There’s a piece of paper

[@doctordk388]

@@ryanyang3347 It's a white board(5:33) his finger erases a bit of marker(and at other parts of the video)

[@neillunavat]

Whiteboard paint type thing. Not wall

[@Linuxdirk]

I love how it only takes 30 minutes to code a Tic Tac Toe AI that can’t be beaten.

[@mathewsjoby6455]

Awesome idea! I can make functions for each set of move so that is like a tree!

[@A_Lesser_Man]

cubed tic-tac-toe sounds great, initially. but...how would one pick the middle??

[@markvador6667]

Still fun and amazing🤣thanks you Dan

[@andydedu5884]

You've taught me more about the basics of game development than any game development channel.