Minimax: How Computers Play Games

The best tutorial, I was looking for. Thank you so muchhhh

👏

If this has stirred your thoughts, this book will be a whirlwind. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell

Amazing content!

well explained.🎉
Helps a lot thank you for sharing your knowledge so perfectly. ❤

I was just going through week 0 of CS50 AI and was wondering why you sounded so similar to Brian Yu, until I realised this channel IS by Brian Yu 😅

Hi, loved your video. Could you please make a video on the A* Algorithm too?

I think this is a great introduction to this concept, and I know this intentionally did not cover all topics that would be necessary to create a computer to limit the complexity of the video so the average person could follow along, but if you were truly interested in this, I recommend that you explore concepts such as transposition tables which is another optimization that computer make when playing complex games like chess. Another concept not covered in this video is move generation, for tic-tac-toe this is simple, you can place your tile anywhere your opponent hasn’t, but for games like chess, it is somewhat difficult to create an efficient method of generating every possible move in a given position. For example, one method you could use to generate move in a position is by creating an array of every piece of which side it is to move, this could be done my looping over all squares in a chessboard and adding the qualifying squares to an array, along with the piece, and then you have to create individual functions to generate the moves of each piece, for sliding pieces this is easy, you can use a list of offsets to gather the directions each piece can move in. For pieces like the knight and pawn this isn’t so easy, I recommend looking at an example chess engine that implements its own move generation to learn more about this. When he was talking about the evaluation function, he only talked about material values, though I believe that he should have at least mentioned other things such as piece square tables, which encourage the computer to move its pieces to certain squares, also pawn structure, which encourages the computer to keep their pawns undoubled, and there are much more, but one more important one is king safety, which makes the bot keep its king away from enemy pieces. If you want to learn more about this I recommend looking at open source chess bots such as stockfish, or sunfish, if you want to explore a more simple engine, or don’t know c++.

How was this drawing line called again?

How do you play this game?

The Colonist AI needs help.

Just a note for some who may have missed - while going recursively for minimax function call, the TURN variable will switch. Maybe it is obvious, but i think the guy didn't mention that explicitly.

I once wrote a good AI for a a game I made using minimax and alpha-beta pruning, but I relied a lot on pseudo-code examples and even after writing it there were things about it, especially the alpha-beta pruning, that I didn't understand. This makes it a lot clearer!

Just great

About the definition of the games: I would call chess a complicate game, not complex. Therer are more variables than in tic-tac-toe, but they are still set. A chess game with a changing pattern would be complex, i guess.

that's criminal!!!
no decent function/program has more than one return. having three different "return value" is a crime. you can code it with only one at no extra cost.
you are checking player(s) two times when it's value can't change. use a binary value, for the player, instead of Max Min. if the condition is true, you do Max code, else, you do Min code.

I would say it should be the average of all possible terminal states

kurwwaaaa

I think having it determine game state values by derivatives of an end game state just throws a lot out the window and I don't think an evaluator function can bridge that.
One thing is at the start there simply are many positions one can take. For tictactoe that's not really an issue as all choices are equal (generally right, except the middle) but for other games, it's important to determine the value of positions themselves such as holding the middle (in chess or tictactoe) where deriving a move from an end state can by chance cover that but without valuing it like that, it can just as well set up somewhere else. That especially comes about with closing state branches off which leads me to number two where there's more to a game than playing optimally. Sometimes we sacrifice a piece in order to gain an upper hand or there's other tricky moves like opening up a color for diagonals to get a bishop or queen out or something idk. I think because it can't value any moves themselves it's necessary for it to have to try to calculate everything and then to cut it off to 5 moves out or whichever. It's inefficient and not even the best way to play. There are pokemon mods where the computer knows all your moves, pokemon, what they're holding etc and it picks the best move based on that. Now us knowing that means we can simply play into that and switch into what would be a terrible play had they not played "optimally".
Anyways ty for the video thought it was interesting.

Why are you adding an "uh" syllable to everything-uh? Lol

in TikTacToe any game cannot last more than 9 moves. But in chess, there are no bounds. Games can go on forever if players just move the same piece back and forth. Thus no matter how powerful your computer is, you can't apply minimax without limiting the depth, or it will recurse until it gets a stack oveflow.

As someone who already knew all of this, I've never seen a video or person anywhere explain this so well. Both concise and simple, but also covers everything in the detail it needs. You go over each function required, pruning, and that it assumes your opponent is perfect. The only simple thing you missed is the reason for the name: min then max since you play best, then your opponent does, and so on.

I’ve often seen it called “min-max”

When I was younger, I had that exact same table.

It's worth understanding that LLMs still work with all of these principles, just scaled up a whole whole lot, with oppositional logic being replaced by manually tuned reward functions.

Similar to a modern chess engine, language models create their own algorithm for estimating the result of any action it takes. This results in a system that is effectively a "predict the next word in a sentence" generator that understands very well how language works, but that also understands very little about the meaning of individual words other than how they are related to each other through language. To an LLM, words and word combinations are no different than pieces moving on a chess board to a learning model based chess engine.

People doesn't play tik tak toe with only 3 X and 3 O???

Answer is actually really simple. "How computers play games?" If game is simple they calculate, if it's hard they use predefined shortcuts and if there is any random element at all, then they cheat.

great!!!

With tic tac toe there are many symmetrical positions. Thus dynamic programming can significantly reduce the search tree.

What software do you use to create the image from your videos?

Wonderful explanation and illustration.

but why not search the tree initially and store the result in a database. Overtime, you would have built a database of game states and values. Of course, if the game is too complex, then even searching initially would take forever and impratical.

Is it called minimax because using minmax doesn’t work in code terms or just for easier human interpretation

which software do you use to create an animation

Can i ask Why you made halting video private

so it was how Deep Blue defeated Kasparov on chess

I assume all tic-tac-toe games played by AI result in a tie, right?

Also, the optimal first move is probably always to pick the middle? If this is the case, how does player 2 determine where to make his move, when all corner and all sides are equal to each other? How does an AI randomly choose a spot? Some sort of default positional choice?

Just now I happened to watch your piegion

Just now I happened to watch your pigeon and wholes video .namasthe Sir ,In India Iknow mystic persons who percept or touch the physical or material sence of maths how they crossed this barrier .any how sir very nice plessure tomeet you from some other part of globe .minds crossed the barriers .Res sir me remain good night

Then why tf AIs are so bad at videogames lol

providing the best platform for AI to cook me again and once again in scrabble. when i get to 54 its already at 189,we simply cannoh compete!

Great video! Visually amazing!

What would be the approach if you wanted to set difficulty for a bot? In this case it's able to calculate the optimal solution but what if you wanted it to purposely play at a lower level while still trying to win?

This was a great video Thank you! You're on of the best

the MATH is WRONG! Wake up NEO!