I remember playing Stratego as a kid at a friends house, and eventually found out some of his pieces were subtly marked (chip in the pieces). Unhiding information was very unfair :)
> The algorithm also learned far faster—it played about 34 times fewer games than DeepNash, and still ended up much stronger.
Imo, this is the critical piece and what makes the AI work at all.
With hidden information games, the best move depends on information you don’t have. So a move could be good or bad, it just depends on something that’s impossible to know.
You’d like to search ahead, meaning “if I do this they will do that” but that’s impossible since you don’t even know what the opponent can do because you don’t know their hidden state.
If the possible hidden states are randomly distributed, you are screwed. It’s just like rock paper scissors: there’s no best move if your opponent is unpredictable.
However if you can quickly learn to predict their moves, it becomes possible to make informed decisions about what to do.
It would be easy enough for a player to be purely random if that was all it took. I think the tension is that piece rank makes some layouts and move strategies more equal than others and calculating the best ones for what has been uncovered so far makes the best layouts not the best layouts.
I loved Stratego so much as a kid. But, I eventually couldn't find anyone to play with me because I crushed everyone, including my dad who was much better than me at chess. But, I never would have thought it'd be a game that models would have a hard time with. It feels relatively simple. And, inexplicably, I never even thought that there might be serious players...I've kept the board game, one of the very few things I have from young childhood, but it's been twenty years since I played. I guess it's time to find an online Stratego. Surely someone in the whole world can beat me.
Too bad I never played against an AI before they cracked it.
Does anyone else remember playing Electronic Stratego? The version where the identity of each piece was encoded on the bottom with a series of bumps? It was an even more incomplete information game: attacking a piece would only let you know if the piece was higher, lower, or even, instead of revealing the piece's identity. I played it so much as a kid that I can't even think of Stratego without hearing that electronic bomb sound in my head. I feel it is actually a better game than the original.
That is the rules we used for playing stratego. Attacker reveales his piece number and the defender declared who won, or obviously if both died they were even.
> But, I eventually couldn't find anyone to play with me because I crushed everyone
I think this is a problem with many deeper games. I remember going over to other people's houses and they would pull out obscure-board-game-xyz. The rest of the night for me was trying to figure out how to play, while others were 30 steps ahead of me.
I think you need something like chess club - stratego club - where people have all gotten to the nuance level and you can play with people of appropriate level.
I love Stratego. I used to play with my girlfriend and my brothers. We started playing with different rules too to switch it up. Like moving bombs or the flag. Or playing with the pieces reversed. Reversed pieces were interesting because the hidden information was swapped, made for some funny games.
> including my dad who was much better than me at chess.
My experience as well unfortunately. No matter how many books on chess I read, no matter how many games I played against Battle Chess to try to get better, he always won.
But about having nobody to play because you crush everyone - as long as you want to play to enjoy and not just always go full-on try-hard mode - just stop crushing everyone and you'll have people to play with.
Let people win every third game. If you're good enough (at it), they won't notice. They'll have a good time and you will. In Tekken it works to have them win some rounds (extra points if you let them have two out of three), but still win the match, tho maybe only if you're not just 2 ppl playing.
That's a rule established from rat behavior observation study, you can hear about it in every third jbp lecture.
Ever since implementing it, I never end up with nobody to play with. Just curb your wanting to always win and focus on maximizing the amount everyone enjoys playing in the long run.
Even a game where there's always a winner and a loser doesn't have to be a zero sum game.
Stratego has a special place in my heart. I have fond memories of playing it with an old family friend. Later in life I sought out an old set off eBay so I could play it with my kids. I really love that game!
I don't actually know. I had a few strong setups that I rotated through, but even after I started explaining my strategy after every game, and even giving hints during the game, my best childhood friend would still lose so much it wasn't fun for either of us so we stopped playing. He's smart, and was fine at most games, but no match in Stratego. I guess I'm just good enough at the various aspects of the game, memory, bluffing, planning, that it added up to being a pretty strong player even without much in the way of study or practice. I'm sure I'd crumble against an actual serious player, and would have back then, too, it was just that I wasn't around anyone else who liked the game enough to become good at it.
I'm curious. I could kind of see that being fun, but I could also see 1 person moving with 79 standing still, and two players who get to make all the decisions. Did you guys modify the rules?
Very little standing still. Everyone is running around. It's a bit like capture the flag, except when you tag someone you compare index cards to see who is higher rank.
I, too, remember figuring out a strategy when I was around 11, and never lost a game after that.
It's been a loooong time, and I don't recall all the details. But it revolved around doing probing attacks to determine where the ranks were in the enemy formation, and then having "channels" in my side to move up a soldier that outranked by 1 a targeted attack.
Color me surprised that it would be difficult to write a program to play it.
Most of my setups, though not all, revolved around bombs and strong soldiers held in reserve behind the bombs, sort of a rope-a-dope...sometimes, I'd kill all of their miners before the bombs surrounding the flag could be disarmed which guarantees no quick win for them. There are risks to that, in that the strong pieces can be stuck while the opponent picks off everything else, but even once people knew I regularly did that, I could still win pretty much always, so it's more than a strong opening layout.
In hindsight, maybe Stratego in childhood is part of why I love Civ games so much, which, I think, tickles a lot of the same brain parts. The setting up the board part is heavily why I liked Stratego so much, and in Civ games, you get to plan your cities and empire. Or, maybe it's just the kind of game I find satisfying, and Stratego was the first instance of it I played.
And, I'm also working on a game that kind of pulls on that same kind of upfront planning, where how you place your pieces to start is as important as how you move them; a settling and strategy game that's heavy on clever defense and using terrain and the interplay of pieces.
Oh no! Stratego had been on my mind as something we just hadn't tried hard enough to make a winning bot for, including the DeepMind effort from 2022. I was planning to make the first one.
I thought this was slightly less crank-coded than trying to prove the Riemann Hypothesis, but maybe these days you just ask Claude to do that and it tells you there's a counterexample at 1 + πi that no one ever noticed before.
I wonder why people act as if Riemann hypothesis is somehow already solved, when it is still highly probable that it is impossible for humans and slightly less impossible for AI overminds.
(Of course, tomorrow Google might announce that it has solved it.)
RH would require completely novel insight and a brilliant original thought. Unlike Navier-Stokes it's not a gradual effort and you cannot piggyback off of other mathematician's works, so "AI" will not solve it anytime soon.
There has been a lot of intermediate progress on the Riemann hypothesis, for example ruling out particular kinds of zeros, and some of those partial results even involve LLMs https://www.anthropic.com/research/riemann-zeta so I don't see why I can't possibly be a gradual effort.
The frontier is moving, but there's still no human-level starcraft bot that plays entirely through vision, like a human.
IMO it also needs to use a real mouse before I think it's a true comparison, even a casual player would have a massive advantage if they could issue selections and unit commands via query.
They already cap the actions per second a bot can take, sometimes to very low numbers. I don't remember if it was AlphaStar that limited how often you can move your camera or not, but some work definitely did.
I personally don't see why vision is important, if anything I'd frame vision as useful to humans, rather than being the baseline.
> Players were surprised, for example, by how often it tucked its flag into a corner behind just two bombs, a rarely played setup.
I like Stratego a lot. Next time, I will try this and put three bombs in the other corner to keep the opponent guessing and wasting an expected 4 extra moves.
I speculate a big part of the game is moving your power pieces (1, 2, 3) to places where they can actually attack the opponent safely. Any other placement of the flag and bombs creates a bottleneck for left-right movement on your side.
This puts the earlier "Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning", 2022 [1] in some perspective. Apparently the "mastering" in 2022 wasn't quite there yet. Four years later, the new approach seems to actually be better than humans.
> Now, a team of researchers from Carnegie Mellon, MIT, New York University, and Stanford University has done it. Their AI, called Ataraxos, beat Pim Niemeijer, arguably the best Stratego player of all time, 15 games to one, with four draws. And it took just 16 GPUs and a few thousand dollars to train it.
Just 16 GPUs, and a few thousand dollars?
What about “researchers from Carnegie Mellon, MIT, New York University, and Stanford University” this wasn’t just anyone.
That's a bit out of context, no?
The preceding sentence is
> Even DeepMind, with its exceptional budget, couldn’t build a machine that reliably beat the best human players.
so the contrast here is the budget available, not the quality of the talent, if we accept the premise that DeepMind and the universities have approximately similar level of talent.
This approach also works for Hanabi, which is a very interesting game. You can't see your own cards, but the other players can. I bought the game because someone on a reinforcement learning podcast [2] mentioned it, and actually played it multiple times.
I think that what makes these games beatable repeatedly is that they're static. Not saying an algorithm properly trained won't play better than the average player a game like MtG, or my own https://aethersummon.com (specially now while it has under 90 possible scrolls only) but if you have a regular release cadence (say weekly or bi-weekly) of relevant new "cards", then I think the playing field is much more even for humans.
Those new additions can invalidate the whole training data by a single new "card" that changes completely the dynamics and would be easy for a player to understand and incorporate but not for an algorithm (perhaps with enough compute to re-train it regularly it could) - that along with the decision trees being orders of magnitude deeper, wider and with more conditionalities than go, chess or stratego - even through the same turn with the same cards available and same table state - would probably pose much harder problems for a compute bound algo.
> Those new additions can invalidate the whole training data by a single new "card" that changes completely the dynamics
This doesn't follow. You're basically proposing that new combo decks be added all the time, and it's far simpler for an agent to scan the new cards for potential interactions with the thousands of other cards in circulation than for a human to remember all of them.
Your analogy is akin to saying that all you have to do is keep landing new code all the time, and since the agents weren't trained on the code they won't be able to identify and respond to security vulnerabilities in it as fast as humans, which hasn't turned out to be correct
No, well, in MtG you could interpret it as meaning such but what I mean is that if in the training set sequence A-B-B-A when state is C-A-X-Y is the play 80% of the time, then you have a new card (that doesn't need to be combo) that by sheer mechanics thwarts that then that strategy won't stick by the addition of that single card to the opposing deck (that you can't know if your opponent is playing or not) and having one or 2 or 3 or 10 different cards renders every calculation very problematic as a play can be the best or the worst depending on such simple things diluting further the best play as the pool grows. Then you need to take into account in MtG shuffling and drawing. I think it's fair to say it's much more difficult to model... And while an agent can learn new combos, you just need to read the card once, the agent needs to be retrained.
Doesn't this entirely depend on the latent embeddings of strategies and game space in the AI model, which may not be so concrete and explicit as you've described? That's kind of the magic of LLMs with coding, they can generalize because the abstract patterns are encoded in latent space, not the specifics.
I might be wrong but what I was thinking was that in chess (or even imperfect information games with a much smaller "range" such as Stratego,) a model can calculate all possibilities for all moves and following moves, by itself and opponent up to a depth that the human cannot. So it can see everything that can happen if it does move X-Y, then Y-Z, then A-C and figure out one that is unbeatable no matter what (or at worse leads to a draw).
But on MtG in particular that never really applies in full due to drawing new cards. You can play perfectly and still lose due to sheer randomness of draws.
The latent space I'm not sure how it translates to a game playing bot, but I would imagine that it would open it up to fail in the same ways a human fails.
On the game I'm designing it could do that (calculate all possibilities up to X depth, for all possible scrolls and table states) but it would be extremely expensive to do so (not a very good argument if compute power keeps increasing), but more than that, in contrast to something like chess, there can be many more paths and decision points where a bad decision turns into a loss, so if it assumes that the best play is X at some point, a sequence that it discarded due to not being the most probable can exist and the bot can never be sure, so if it makes a decision that plays into a "trap" he can't undo to a favourable position. While in Chess it's much clearer what is possible from a given state, it's unambiguous and the rules are fairly limited.
In stratego you have a 10x10 board game, a very clear objective and at most 40 pieces (with repeated pieces and simple mechanics amongst them), while in MtG and similar games a single piece (card) can have probably hundreds of different interactions depending on everything else going (and everything else hidden), at many points of decision. In stratego it also seems that for humans at least, most moves are "inconsequential", as it probably plays more at the psychological/bluff level. Maybe a human player that was given the same budget for training could spend a month training against bots might fare better as the strategies might be then better understood (by the article it's mentioned that the agent recovered from bad positions, so it seems that it was mostly human error, as the human was playing better up to that point).
While on MtG or Asummon, although there can be inconsequential moves (they don't matter given the context/stage of the game), every move carries with it a possibility of being consequential in unpredictable ways. Anyway, there should be ways of training models with just a rule abiding client for these games, without codifying all rules, that they can just keep playing to figure out the interactions, so if that theory is true then it should be possible to create an unbeatable bot - I'm just not sure it is without infinite time/compute and less so if the "meta" keeps changing rendering possible training inconsequential regularly.
You can definitely try to regularize against ruleset changes by generating a bunch of cards and making the agent play in randomized subsets of those cards.
I didn't look for prior work on this, but my estimate is that it's probably within 2-3 orders of magnitude of additional training compared to a static game. (Still a lot!)
Well, if your training includes regularization against ruleset changes, the model should simply handle it. (that would be the expensive option, and require vastly more training)
When the Dota 2 bot was made, they retrained the bot only partially when new patches came in, so it was definitely cheaper to adapt.
There are very few missing pieces for a game like MTG. The main reasons we don't have a Stockfish for MTG is that it's a PITA to implement the rules and that nobody cares (or at least not enough to make it happen.)
There is nothing that, in principle, makes MTG different from poker or bridge, and we have superhuman engines for both.
> There is nothing that, in principle, makes MTG different from poker or bridge
There is - metagame. There is no universal optimal strategy in a trading card game, because what is optimal depends on what decks and strategies other people are playing.
I'm sure you could train a neural network to play a specific deck within a specific metagame of a specific card game, but you would probably have to keep re-training it when there are new decks/combos/releases/rotations/banlists/metagame shifts.
MTG is also severely constrained (small hand, mana -> possible moves) although I don't think it's anywhere near the same. In my opinion the rules are effectively what change the whole dynamics. You can't plan as efficiently without knowing what your opponent holds and having to take into account all possibilities (with infinite energy/compute time perhaps)... I don't doubt you can train a model to play well, I just think it should be much more level to the human player. In MtG you also have the randomness which is not easy to model nor account for - the perfect play by an LLM can be the worse once the opponet draws next.
In my own game you don't have shuffle/draw randomness but the pool of options is statistically tending to infinite (if I would have 500 or 1000 scrolls designed and MtG depending on the format has that depth) when compared to something like chess, or this game. On the other hand in my own game you have to account for much more depth on the possible options your opponent has.
There's only so many card interactions that strong players actually think about.
Ex: you don't really care if the opponent plays Giant Growth or Chastise. The effect is that the opponent is playing a combat trick, and combat has moved from attackers favor into defenders favor.
To defeat an instant speed combat trick requires a combat trick of your own, or a generic counter spell of some kind. Some have interactions (ex: Doom Blade beats Giant Growth but not Chastise), but the overall gist is that opponents can do things after combat is declared. You only need to keep track of how many combat tricks you think the opponent has.
---------
Other situations are card advantage (ex: 2 for 1. If the opponent spends 1 cards to defeat only 2 cards of yours). The traditional card for this is Mindrot, but well placed counterspell can turn a combat trick into. 2-for-1 reversal.
You don't necessarily keep track of how your opponent makes 2-for-1 opportunities. You just have vague gists of them.
---------
Good spells have huge applicability. Doom blade or Murder is high because killing opponent creatures at instant speed handles the vast majority of creature buffed combat tricks, and also serves as a way to stop enemy combos and other such tricks.
In contrast, chastise is very niche. If the opponent were playing like Swords to Plowshares (powerful white instant speed removal), it's pretty much always better than chastise.
If the opponent plays chastise instead, you take that as a win because you know they could have had a deck of better cards. But for whatever reason decided to play with weaker cards...
I agree in a way, but at the same time, and I think it's a bit more applicable to MtG due to the limit of cards you can have as possible plays at any given time (outside of combos), and I believe too that you can train a bot to be good, better than average - I doubt arena doesn't have bots - but I still think that without unbound compute/time it's a game where human players have much better odds to outsmart an AI if they're good players. MtG has for the past 10 or more years been re-hashing the same play patterns, while introducing some new mechanics on most cycles, but pretty much you have staples throughout most editions that are just variations on that - card advantage, denial, combat tricks, removal, curve and then the rarity enabled bombs/combos
But even then (not saying I'm right) I think the depth of choices, effects and so on, on a format like modern, or legacy, would be very difficult for an AI to top against pros. If you add draft into the mix it gets worse for the AI in my view too.
Because a good play in most situations can easily be a bad play under others. That doesn't happen in chess for instance, given enough decision depth to the algos to see the future game. In my own game I think those situations can occur much easier due to you always having your full deck available. Also, in MtG it's easy to get into table states that are either ahead/behind and then you kinda just have to protect your position (like with denial decks). Then you have the effects that you might remove a creature threat (graveyard) but then that enabling a combo you weren't expecting that needs a creature on the grave, or enabling delve cards or whatever have you. It's much less clear cut for a probabilistic model to make the optimal play at every single interaction. So the more you train the model on all the variations and possible follow ups, the more you dilute its certainty isn't it? In chess, or this game, or RTS such as starcraft, that doesn't really happen in my view.
I'm also a Poker player and the way Poker AIs solved this problem was by making the best estimate of the Nash Equalibrium and playing around it.
No human can possibly keep up with all the possibilities or combinations that are accounted for.
Games of incomplete information have been IMO soft-solved as of.... Maybe 5 years ago? As in, stronger than any human can possibly reach (ie: massive GB-sized matricies accounting for all information iterated over millions of iterations of "he thinks that I think that he thinks that I think that....")
It's not a true Nash Equalibrium, which remains outside of the realm of even computers to compute. But a computer can always reach a closer / better estimate of any Nash Equalibrium, which covers all games of incomplete information.
--------
For Poker, it turns out that a few types of bet sizes (3x pot, 1.5x pot, pot, half pot, quarter pot) covered enough betting patterns to reach superhuman.
And frankly, MtG is simpler than the bluffing game in Poker. Like MtG has bluffs but it's no where close to Pokers level.
There's no crazy deep game for Red Deck Wins vs Control. The game basically plays itself out (Red tries to win before Control comes online. Control tries to stall before Red Deck Wins). There are some games with complex board states but they're largely a game of bluffing + card counting (opponent holds 4 cards, two of which were since the start of game and 2 were top decked in the last two turns. He at best has only planned for 2 responses or got lucky with the other two newest cards. Do I have a play that beats two cards yet?)
> There is nothing that, in principle, makes MTG different from poker or bridge
Only in the most general form they are games with cards and hidden information with a state space that some form of tree search can theoretically play out.
The difference is the size of the search space. In MTG the search space is unimaginably huge. It would make Go's search space look like a spec of hydrogen in the middle of the universe.
It would require completely different techniques to produce a computer good at MtG than one that is good at bridge.
I wonder how capable current AIs are with the "silent defense" variant of Stratego [1]? The article states the high level of uncertainty presents a challenge. With silent defense the uncertainty is even higher.
[1] https://www.hasbro.com/common/instruct/Stratego.PDF
"When an attack is made, the attacker is the only player who has to declare the number of his or her piece. The defender does not reveal the number of his or her piece, but resolves the attack by removing
whatever piece has a lower number from the gameboard. Players keep their own captured pieces. Exception: when a Scout attacks, the defender must reveal the number of his or her piece.
As a kid, a friend of mine had "Electronic Stratego"[1], the biggest gameplay change was that you could carry out fights without revealing the strength of either piece to the other side. I found this made for a much more interesting game and we had quite a bit of fun playing it.
> Look at competitive chess and Go and how they have fundamentally been transformed.
For people like me, competitive chess killed chess long before Deep Blue. It only feels fair that competitive chess players now feel like I did :-)
I had a math professor who played competitive chess in his youth. He told me he realized the demands for competitive chess were such that he couldn't really dedicate himself to math (or any other discipline) at the same time. So one day, he gave up chess - and refused to play it for the rest of his life.
> I am particularly disappointed that it has influenced how people play the game.
> The joy comes from the journey and the experience.
> Look at competitive chess and Go and how they have fundamentally been transformed.
Go is better since AlphaGo. Tools are better, it's easier to learn from your games, we're better at it. The AI makes sick fucking moves and we get to see.
The journey is still there, the experience is still there.
Chess I doubt is worse off either, but I don't know chess that well.
I would really love to see a serious research effort take a crack at contract bridge. Bridge, like Stratego, is an imperfect information game with a big hidden information space. Bridge also adds another wrinkle of explainability which is, I think, very interesting.
Bridge is played as a pair vs pair game, with North/South and East/West being the two pairs and seated around the table in these compass directions. A bridge hand consists of two phases: there is first an auction phase, where players go around the table bidding on contracts (agreeing to take a certain number of tricks with a certain trump suit) until a final contract is decided. Then there is the cardplay phase, where the player who won the auction is the declarer, their partner is the dummy, and the other pair are defenders. The dummy's hand is placed face up on the the table and the declarer controls which cards are played from dummy, so the cardplay phase is effectively played by only three players now, with each of the three knowing one common hand (dummy) and one private hand (their own) and not knowing the other two hands.
In both the auction and (for the defense) the cardplay phases, it is important for players to exchange some information about their hand to their partner. However, any information you exchange about your own hands also helps your opponents. You might naturally conclude that you want to come up with some secret scheme to exchange information which your opponents don't know (and it is even possible to exchange encrypted information which your opponents can't know--if the defense is known to hold a certain card, but declarer doesn't know in which hand it is, the defense could say that a signal means one thing if the card is in one defender's hand, but means a different thing if it's in the other defender's hand).
But it turns out that this ends up being very uninteresting to play, so instead, when playing bridge, there is an important rule: all of your partnership agreements must be public. If a certain bid that I make promises that I have at least 5 spades in my hand, it is the opponents' right to know that this is our agreement. You must be able to explain the information which your action provides, and you must be able to use the information that the opponents give you themselves.
This poses several problems for self-play reinforcement learning. First, a naive self-play approach will produce agreements that cannot be explained to a human. What really needs to happen is that your partner, when determining what hands you might have as part of search, must not do so simply by sampling its own system (ie by asking what it itself would have done with hand X or hand Y). The information and possibilities really need to be mediated by some kind of intermediate, rules-based description, which can be provided to the opponents as well.
You also need to be able to encode and ingest the opponents' agreements, and to use this information to inform your own decisions. And you need, in particular, to be able to handle a wide variety of agreements from your opponents; it's not enough to force them to play the same system as you.
You must also account for deceit. If, for example, I have a bid which promises that I have at least 2 cards in every suit, it's perfectly legal for me to lie and make this bid when I only have 1 card in some suit--as long as my partner is in the dark about this just as much as the opponents. So if you make this bid, and your machine opponents assume there is a 0% probability of you having lied about your hand, it is possible that they will make gross errors by not accounting for this possibility (for example, they may be in a position where all of their actions are equivalent if you told the truth, but where one action is clearly better if you didn't--a human player will naturally take this action, but a robot may just select an action randomly).
It's an interesting game and a very interesting AI challenge.
Very detailed, accurate, and insightful summary of the interesting dynamics in bridge. So well written I would have clocked it as AI except in my experience AI is terrible at discussing game dynamics.
How does AI, in a game as complex as bridge, manage to deal with a human partner, or even an AI partner? Seems like an answer we could find out.
> The information and possibilities really need to be mediated by some kind of intermediate, rules-based description, which can be provided to the opponents as well.
This is standardized at tournaments (I'm sure you know that.)
Imo, this is the critical piece and what makes the AI work at all.
With hidden information games, the best move depends on information you don’t have. So a move could be good or bad, it just depends on something that’s impossible to know.
You’d like to search ahead, meaning “if I do this they will do that” but that’s impossible since you don’t even know what the opponent can do because you don’t know their hidden state.
If the possible hidden states are randomly distributed, you are screwed. It’s just like rock paper scissors: there’s no best move if your opponent is unpredictable.
However if you can quickly learn to predict their moves, it becomes possible to make informed decisions about what to do.
Too bad I never played against an AI before they cracked it.
https://en.wikipedia.org/wiki/Stratego#Electronic_Stratego
I think this is a problem with many deeper games. I remember going over to other people's houses and they would pull out obscure-board-game-xyz. The rest of the night for me was trying to figure out how to play, while others were 30 steps ahead of me.
I think you need something like chess club - stratego club - where people have all gotten to the nuance level and you can play with people of appropriate level.
My experience as well unfortunately. No matter how many books on chess I read, no matter how many games I played against Battle Chess to try to get better, he always won.
But about having nobody to play because you crush everyone - as long as you want to play to enjoy and not just always go full-on try-hard mode - just stop crushing everyone and you'll have people to play with.
Let people win every third game. If you're good enough (at it), they won't notice. They'll have a good time and you will. In Tekken it works to have them win some rounds (extra points if you let them have two out of three), but still win the match, tho maybe only if you're not just 2 ppl playing.
That's a rule established from rat behavior observation study, you can hear about it in every third jbp lecture.
Ever since implementing it, I never end up with nobody to play with. Just curb your wanting to always win and focus on maximizing the amount everyone enjoys playing in the long run.
Even a game where there's always a winner and a loser doesn't have to be a zero sum game.
What was the secret of your success?
It's been a loooong time, and I don't recall all the details. But it revolved around doing probing attacks to determine where the ranks were in the enemy formation, and then having "channels" in my side to move up a soldier that outranked by 1 a targeted attack.
Color me surprised that it would be difficult to write a program to play it.
One thing Stratego did was implement the "fog of war". My Empire game took inspiration from Stratego and Risk.
And, I'm also working on a game that kind of pulls on that same kind of upfront planning, where how you place your pieces to start is as important as how you move them; a settling and strategy game that's heavy on clever defense and using terrain and the interplay of pieces.
I thought this was slightly less crank-coded than trying to prove the Riemann Hypothesis, but maybe these days you just ask Claude to do that and it tells you there's a counterexample at 1 + πi that no one ever noticed before.
(Of course, tomorrow Google might announce that it has solved it.)
IMO it also needs to use a real mouse before I think it's a true comparison, even a casual player would have a massive advantage if they could issue selections and unit commands via query.
I personally don't see why vision is important, if anything I'd frame vision as useful to humans, rather than being the baseline.
I like Stratego a lot. Next time, I will try this and put three bombs in the other corner to keep the opponent guessing and wasting an expected 4 extra moves.
I speculate a big part of the game is moving your power pieces (1, 2, 3) to places where they can actually attack the opponent safely. Any other placement of the flag and bombs creates a bottleneck for left-right movement on your side.
[1] https://arxiv.org/abs/2206.15378
Just 16 GPUs, and a few thousand dollars?
What about “researchers from Carnegie Mellon, MIT, New York University, and Stanford University” this wasn’t just anyone.
so the contrast here is the budget available, not the quality of the talent, if we accept the premise that DeepMind and the universities have approximately similar level of talent.
So clearly it’s due to talent as well as advances, of course.
[1] https://en.wikipedia.org/wiki/Hanabi_(card_game)
[2] https://www.talkrl.com/episodes/jakob-foerster
Those new additions can invalidate the whole training data by a single new "card" that changes completely the dynamics and would be easy for a player to understand and incorporate but not for an algorithm (perhaps with enough compute to re-train it regularly it could) - that along with the decision trees being orders of magnitude deeper, wider and with more conditionalities than go, chess or stratego - even through the same turn with the same cards available and same table state - would probably pose much harder problems for a compute bound algo.
This doesn't follow. You're basically proposing that new combo decks be added all the time, and it's far simpler for an agent to scan the new cards for potential interactions with the thousands of other cards in circulation than for a human to remember all of them.
Your analogy is akin to saying that all you have to do is keep landing new code all the time, and since the agents weren't trained on the code they won't be able to identify and respond to security vulnerabilities in it as fast as humans, which hasn't turned out to be correct
But on MtG in particular that never really applies in full due to drawing new cards. You can play perfectly and still lose due to sheer randomness of draws.
The latent space I'm not sure how it translates to a game playing bot, but I would imagine that it would open it up to fail in the same ways a human fails.
On the game I'm designing it could do that (calculate all possibilities up to X depth, for all possible scrolls and table states) but it would be extremely expensive to do so (not a very good argument if compute power keeps increasing), but more than that, in contrast to something like chess, there can be many more paths and decision points where a bad decision turns into a loss, so if it assumes that the best play is X at some point, a sequence that it discarded due to not being the most probable can exist and the bot can never be sure, so if it makes a decision that plays into a "trap" he can't undo to a favourable position. While in Chess it's much clearer what is possible from a given state, it's unambiguous and the rules are fairly limited.
In stratego you have a 10x10 board game, a very clear objective and at most 40 pieces (with repeated pieces and simple mechanics amongst them), while in MtG and similar games a single piece (card) can have probably hundreds of different interactions depending on everything else going (and everything else hidden), at many points of decision. In stratego it also seems that for humans at least, most moves are "inconsequential", as it probably plays more at the psychological/bluff level. Maybe a human player that was given the same budget for training could spend a month training against bots might fare better as the strategies might be then better understood (by the article it's mentioned that the agent recovered from bad positions, so it seems that it was mostly human error, as the human was playing better up to that point).
While on MtG or Asummon, although there can be inconsequential moves (they don't matter given the context/stage of the game), every move carries with it a possibility of being consequential in unpredictable ways. Anyway, there should be ways of training models with just a rule abiding client for these games, without codifying all rules, that they can just keep playing to figure out the interactions, so if that theory is true then it should be possible to create an unbeatable bot - I'm just not sure it is without infinite time/compute and less so if the "meta" keeps changing rendering possible training inconsequential regularly.
I didn't look for prior work on this, but my estimate is that it's probably within 2-3 orders of magnitude of additional training compared to a static game. (Still a lot!)
When the Dota 2 bot was made, they retrained the bot only partially when new patches came in, so it was definitely cheaper to adapt.
There is nothing that, in principle, makes MTG different from poker or bridge, and we have superhuman engines for both.
There is - metagame. There is no universal optimal strategy in a trading card game, because what is optimal depends on what decks and strategies other people are playing.
I'm sure you could train a neural network to play a specific deck within a specific metagame of a specific card game, but you would probably have to keep re-training it when there are new decks/combos/releases/rotations/banlists/metagame shifts.
In my own game you don't have shuffle/draw randomness but the pool of options is statistically tending to infinite (if I would have 500 or 1000 scrolls designed and MtG depending on the format has that depth) when compared to something like chess, or this game. On the other hand in my own game you have to account for much more depth on the possible options your opponent has.
Ex: you don't really care if the opponent plays Giant Growth or Chastise. The effect is that the opponent is playing a combat trick, and combat has moved from attackers favor into defenders favor.
To defeat an instant speed combat trick requires a combat trick of your own, or a generic counter spell of some kind. Some have interactions (ex: Doom Blade beats Giant Growth but not Chastise), but the overall gist is that opponents can do things after combat is declared. You only need to keep track of how many combat tricks you think the opponent has.
---------
Other situations are card advantage (ex: 2 for 1. If the opponent spends 1 cards to defeat only 2 cards of yours). The traditional card for this is Mindrot, but well placed counterspell can turn a combat trick into. 2-for-1 reversal.
You don't necessarily keep track of how your opponent makes 2-for-1 opportunities. You just have vague gists of them.
---------
Good spells have huge applicability. Doom blade or Murder is high because killing opponent creatures at instant speed handles the vast majority of creature buffed combat tricks, and also serves as a way to stop enemy combos and other such tricks.
In contrast, chastise is very niche. If the opponent were playing like Swords to Plowshares (powerful white instant speed removal), it's pretty much always better than chastise.
If the opponent plays chastise instead, you take that as a win because you know they could have had a deck of better cards. But for whatever reason decided to play with weaker cards...
But even then (not saying I'm right) I think the depth of choices, effects and so on, on a format like modern, or legacy, would be very difficult for an AI to top against pros. If you add draft into the mix it gets worse for the AI in my view too.
Because a good play in most situations can easily be a bad play under others. That doesn't happen in chess for instance, given enough decision depth to the algos to see the future game. In my own game I think those situations can occur much easier due to you always having your full deck available. Also, in MtG it's easy to get into table states that are either ahead/behind and then you kinda just have to protect your position (like with denial decks). Then you have the effects that you might remove a creature threat (graveyard) but then that enabling a combo you weren't expecting that needs a creature on the grave, or enabling delve cards or whatever have you. It's much less clear cut for a probabilistic model to make the optimal play at every single interaction. So the more you train the model on all the variations and possible follow ups, the more you dilute its certainty isn't it? In chess, or this game, or RTS such as starcraft, that doesn't really happen in my view.
No human can possibly keep up with all the possibilities or combinations that are accounted for.
Games of incomplete information have been IMO soft-solved as of.... Maybe 5 years ago? As in, stronger than any human can possibly reach (ie: massive GB-sized matricies accounting for all information iterated over millions of iterations of "he thinks that I think that he thinks that I think that....")
It's not a true Nash Equalibrium, which remains outside of the realm of even computers to compute. But a computer can always reach a closer / better estimate of any Nash Equalibrium, which covers all games of incomplete information.
--------
For Poker, it turns out that a few types of bet sizes (3x pot, 1.5x pot, pot, half pot, quarter pot) covered enough betting patterns to reach superhuman.
And frankly, MtG is simpler than the bluffing game in Poker. Like MtG has bluffs but it's no where close to Pokers level.
There's no crazy deep game for Red Deck Wins vs Control. The game basically plays itself out (Red tries to win before Control comes online. Control tries to stall before Red Deck Wins). There are some games with complex board states but they're largely a game of bluffing + card counting (opponent holds 4 cards, two of which were since the start of game and 2 were top decked in the last two turns. He at best has only planned for 2 responses or got lucky with the other two newest cards. Do I have a play that beats two cards yet?)
Only in the most general form they are games with cards and hidden information with a state space that some form of tree search can theoretically play out.
The difference is the size of the search space. In MTG the search space is unimaginably huge. It would make Go's search space look like a spec of hydrogen in the middle of the universe.
It would require completely different techniques to produce a computer good at MtG than one that is good at bridge.
[1] https://www.hasbro.com/common/instruct/Stratego.PDF "When an attack is made, the attacker is the only player who has to declare the number of his or her piece. The defender does not reveal the number of his or her piece, but resolves the attack by removing whatever piece has a lower number from the gameboard. Players keep their own captured pieces. Exception: when a Scout attacks, the defender must reveal the number of his or her piece.
1. https://boardgamegeek.com/boardgame/3513/electronic-stratego (We generally banned the use of the 'probing' feature)
https://news.ycombinator.com/item?id=49918148
I am particularly disappointed that it has influenced how people play the game.
The joy comes from the journey and the experience.
Look at competitive chess and Go and how they have fundamentally been transformed. It's not better and now the box is opened, it can't be closed.
For people like me, competitive chess killed chess long before Deep Blue. It only feels fair that competitive chess players now feel like I did :-)
I had a math professor who played competitive chess in his youth. He told me he realized the demands for competitive chess were such that he couldn't really dedicate himself to math (or any other discipline) at the same time. So one day, he gave up chess - and refused to play it for the rest of his life.
> The joy comes from the journey and the experience.
> Look at competitive chess and Go and how they have fundamentally been transformed.
Go is better since AlphaGo. Tools are better, it's easier to learn from your games, we're better at it. The AI makes sick fucking moves and we get to see.
The journey is still there, the experience is still there.
Chess I doubt is worse off either, but I don't know chess that well.
Bridge is played as a pair vs pair game, with North/South and East/West being the two pairs and seated around the table in these compass directions. A bridge hand consists of two phases: there is first an auction phase, where players go around the table bidding on contracts (agreeing to take a certain number of tricks with a certain trump suit) until a final contract is decided. Then there is the cardplay phase, where the player who won the auction is the declarer, their partner is the dummy, and the other pair are defenders. The dummy's hand is placed face up on the the table and the declarer controls which cards are played from dummy, so the cardplay phase is effectively played by only three players now, with each of the three knowing one common hand (dummy) and one private hand (their own) and not knowing the other two hands.
In both the auction and (for the defense) the cardplay phases, it is important for players to exchange some information about their hand to their partner. However, any information you exchange about your own hands also helps your opponents. You might naturally conclude that you want to come up with some secret scheme to exchange information which your opponents don't know (and it is even possible to exchange encrypted information which your opponents can't know--if the defense is known to hold a certain card, but declarer doesn't know in which hand it is, the defense could say that a signal means one thing if the card is in one defender's hand, but means a different thing if it's in the other defender's hand).
But it turns out that this ends up being very uninteresting to play, so instead, when playing bridge, there is an important rule: all of your partnership agreements must be public. If a certain bid that I make promises that I have at least 5 spades in my hand, it is the opponents' right to know that this is our agreement. You must be able to explain the information which your action provides, and you must be able to use the information that the opponents give you themselves.
This poses several problems for self-play reinforcement learning. First, a naive self-play approach will produce agreements that cannot be explained to a human. What really needs to happen is that your partner, when determining what hands you might have as part of search, must not do so simply by sampling its own system (ie by asking what it itself would have done with hand X or hand Y). The information and possibilities really need to be mediated by some kind of intermediate, rules-based description, which can be provided to the opponents as well.
You also need to be able to encode and ingest the opponents' agreements, and to use this information to inform your own decisions. And you need, in particular, to be able to handle a wide variety of agreements from your opponents; it's not enough to force them to play the same system as you.
You must also account for deceit. If, for example, I have a bid which promises that I have at least 2 cards in every suit, it's perfectly legal for me to lie and make this bid when I only have 1 card in some suit--as long as my partner is in the dark about this just as much as the opponents. So if you make this bid, and your machine opponents assume there is a 0% probability of you having lied about your hand, it is possible that they will make gross errors by not accounting for this possibility (for example, they may be in a position where all of their actions are equivalent if you told the truth, but where one action is clearly better if you didn't--a human player will naturally take this action, but a robot may just select an action randomly).
It's an interesting game and a very interesting AI challenge.
How does AI, in a game as complex as bridge, manage to deal with a human partner, or even an AI partner? Seems like an answer we could find out.
> The information and possibilities really need to be mediated by some kind of intermediate, rules-based description, which can be provided to the opponents as well.
This is standardized at tournaments (I'm sure you know that.)
https://archive.org/details/STRATEGO