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.
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.
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
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.
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.
Too bad I never played against an AI before they cracked it.
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.
[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)
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.
> 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.
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.