Minimax: How Computers Play Games 

What currency is that?

Kromer

I too was studying counter strike for years.

@@JalizJay israeli shekel

@@JalizJay its israeli shekel

Saw that too, loved the extra bit of attention

Just recently created an MCTS AI for a project of mine and scoured the web for any resources I could find, and I can say there are not so many simple explanations for it.

I've heard this mentioned years ago when I started learning about graphics... but never though I could fully understand it. Spanning Tree should definitely do a video on this.

When somebody in Harvard is doing this, this channel can do it... The voice is familiar, CS50...

Yes

@@NiklasWest Yes, he taught cs50w and cs50ai

First, there is another level to Pokémon which is randomness. You can handle this with expected values or setting a threshold (e.g., choose the action that maximizes the chance the outcome is valued 0 or more, i.e., minimize the chance of losing without caring whether you win or draw) These are called stochastic games and they can be solved with a bit more work. What you are referring to are concurrent games. You can still decide whether a strategy is winning or not, but interestingly there are cases where you MUST pick a random strategy to guarantee a win. Consider for example we play rock-paper-scissors and your goal is to win any round (no matter how often we draw or you lose before). The only rule is that you have to specify your strategy beforehand (not to me necessarily). If you always picked rock, or decided on some intricate pattern (e.g.,in the n-th round take noch if n is prime, otherwise if it's even paper and else scissors) there is always a chance that I picked the exact opposite strategy and always counter you. Even if you include my past choices, it doesn't matter. Surprisingly, the only way you can 100% guarantee a win is if you say "I'm picking at random" because then the chance that you win eventually approaches 1 as we play more and more rounds. Technically, there is an even worse concurrent games: One that you cannot win with 100% probability, even if you play infinitely long, but with any probability ever so slightly smaller than 100%. Consider this: I have a single snowball I want to throw at you. You hide behind a hill. We play in rounds and at each round you can decide to run to your house, which would win you the game. However, if I throw my snowball in the same turn, you lose. If I decide to throw my snowball I will not have it ever again and you can just run to your house. Again, if you decide to determine your strategy beforehand as "I run at the 27th turn" there is a small chance that I would always throw at that turn, making you lose 100% of the time. So the only way that you can guarantee that you have a chance to win is again to decide randomly, e.g., by flipping a coin. If I had chosen to immediately throw my snowball you would have a 50% chance at winning. However, you could also not throw a coin but roll a dice and only run if you roll a 6. In that case I would at best have a 1/6 chance to hit you, so you win 5/6 times. And you can continue this - bring a 1000 sided dice and you increase your chances of winning to 999/1000. In fact, any number smaller than 1 can be achieved, but not 1 itself. So while this seems like very constructed games (surprise: they are!) remember than any algorithm that would solve all concurrent games (like minimax solves all normal games) would also have to solve these games correctly, so there is no realistic way to do that. What you would do in practice is to *assume* a probability distribution over your opponent's strategy, i.e., assume that they pick 40% rock, 30% paper and 30% paper, or similarly assign a probability to each of the opposing Pokémon's moves/swapping out, and then pick the optimal strategy from there.

I'm not 100% sure of the mechanics of competitive Pokémon, but for other complete information games (you know how much all players will score) like rock paper scissors or prisoner's dilemma, we can analyze using Nash's equilibrium to find the best strategy *regardless* of what other opponent will do. In rock paper scissors, there are no Nash equilibrium.

There is a bot on showdown called eaubot and it's pretty good at predicting stuff

Competitive pokemon has also some "backwards guessing" meaning you know the species of the opposing mon, you don't know the set tho then before even attempting to predict that Lando you really want to know if he's av, scarf or something else (specs with sludge bomb Kappa), that's why BO3 are a little bit lore balanced, both players have enough time to make information gathering an essential part of the set, especially in the first game. I feel that Pokémon has so many variables that making a program play at tournament level is basically impossible and, if you doubt it, there was this game at worlds that I remember, one player would've wanted something like protect and U-turn at the end of the turn, obv it's not possible, the madlad used Roar (it was VGC, I think 7gen, one of the two Mons was a Zapdos) on his own protecting Pokémon and got his protect switch out in the same turn, that day I learned that Roar bypasses protect and that humans are way too crazy for machines

@@phoe87 Wow that is awesome.

And the positions starting from 12:19 are all from Kasparov-Karpov 1987, Game 24!

More info for others: It gets a lot harder in something like chess also where not only are you limiting depth, but you have to "score" the game somehow other than by the terminal state, since after a depth of 5, 10, 15, or whichever, the game will encounter plenty of states where it's not over. So you need to find the best one. You implement a function that takes in the state and returns a score as you mentioned. In chess, this means valuing each piece in a certain way, and even making a heatmap of what value each piece has on each square. These values are determined by humans sadly, and there are plenty of other ways to evaluate these things. Chess bots will often have lots of info on openings, since otherwise it's harder to compare game states that early.

yea weird timing indeed i made a tic tac toe engine already and have been working on a chess engine for the past 3 months

mood

I totally thought you were bragging about being good at chess! I still feel computer would win against you in tic-tac-toe

@@nayankumarbarwa4317 I only play in the all-biological division. That’s where I earned my ranking against humans and trained birds.

@@parkloqi Pardon me sir! You have all the respects from a person who has defeated every single kindergartener of his area single handedly.

@@nayankumarbarwa4317 You gotta watch out for the quiet ones. Some of the older kindergartners are sharks!

Yeah that is the technique that the top chess engines use

it uses neuron network, which is very different from minmax

Maybe let the bot randomly choose the less optimal move, such as choosing a 0 on purpose when it instead could choose the -1 and continue making you lose. In chess this becomes easier, because a bot can just choose a slightly worse evaluation score, so it seems like a genuine subpar move, and not the bot purposefully throwing the game because you were playing too poorly.

You can do this with cards, as long as you don't assume the cards they're holding. Essentially, the actions(s) function for the opponent would return them playing every card that both haven't been played yet and is not in your hand.

1. no 2. no.

@@barakeel akchually, with 4 players, you might be able to use inaginary numbers; for all even numbers of players; idk if there a 3-way numbers

Luke already answered the cards half of the question, but the answers for the question regarding player count are... lacking. The short answer is, yes, you can, as long as certain conditions are met and you shift your paradigm -- no imaginary numbers needed. First up, the condition: the game must be one where there is exactly one win state and one loss state. While this sounds restrictive, think about it: in chess, you have exactly one win state -- the enemy king is currently under threat and there is no action which can rescue him -- and one lose state -- ditto, but your king instead of the enemy's. There are an absurdly large number of scenarios where this occurs, but only one such core state. (EDIT: an example where MinMax doesn't apply well would be the Civ series, where multiple end goals exist. You /can/ apply MinMax to it if you try hard enough, but it becomes a matter of unrealistic complexity far too rapidly to be of use.) So how do we implement MinMax for, say, a 4-player game that satisfies this condition? Simple: we consider the three other players in sequence. It may be easier to visualize by considering them to be a single player with 3 successive turns where they can only perform specific actions. We also consider any terminal state where our MinMax player isn't the winner to be a variant of our single lose state. Then we write our algorithm, creating our move tree like so: MinMax->Enemy[A]->Enemy[B]->Enemy[C]->MinMax->... This generalizes, too, to team-based games, where each player on each team has a specific allowed set of actions. (TeamMinMax[A]->Enemy[A]->TeamMinMax[B]->Enemy[B]->...)

The only important part is that the terminal state is assigned a value based on how good it is to the player. For example, winning is good, so it is assigned a number higher than the other states. Stalemates and draws are desireable over losing, but not over winning, so you can assign them any number between the losing state and the winning state. I'm not sure if stalemates or draws are better because I do not play much chess, so I don't know if stalemates should have a higher score than draw, or vice versa

because X wins

​@@IanKane oh yeah. Brain fart. I saw two empty spaces and was like, wait, the game isn't over 😅

@@mohammadsalman1187 😂

There is a theoretical game length limit a bit over 5000 moves each because of the 50 move draw rule which states a draw can be claimed if no capture is made and no pawn is moved for 50 consecutive moves as each of the 16 pawns can only move a maximum of 6 times and only 30 pieces can be captured there's a strict upper bound of 50(6*16+30) = 6300 If the only goal was to maximise the number of moves then maybe close to 6300 could be possible The problem isn't that the number of chess games is infinite (because it's not) but because it's a finite number that might be bigger than the number of atoms in the known universe. Chess is actually fully solved for all legal board states with 7 or less pieces

The opponent is just going to lose if they keep moving pieces back and forth with someone who's playing optimally.

@@cosmicsvids 99.999999999% of the possible chess games that could be played are absolutely completely absurd and involve both players playing in ways that show know evidence of understanding the objective; in the same way that most possible impulses that my nervous system can send to my body would not result in me walking. Because the amount of chess games are so vast, the tiny subset of games where both players are (mostly) playing with an objective of checkmate is still vast beyond human comprehension.

​@@cosmicsvids Not necessarily. Suppose only the 2 kings remain. Neither player would be able to checkmate the other, so the game would go on forever. In that case the only thing stopping the game would be the 50 move draw rule

@@paulpach at the start of the game I mean if one player keeps moving a piece back and forth the other player will just start gobbling up pieces or do a quick check mate you can only get away with that when the games down to a few pieces.

AI can't play any better than the average human could if they tried. It's a game where looking 7 or 8 moves ahead is really easy because after about 4 moves all moves are usually forced.