I found this interesting article on Kotaku stating that after mastering the ancient game of "Go", Google has tasked DeepMind to study and play Collectible Card Games. Specifically Hearthstone and Magic. The article goes on to talk about the programming and all, but seems more focused on Hearthstone. Personally, I think conquering Hearthstone will be DeepMind's first goal, since the card pool is much smaller and older MTG cards has so much errata that it will be hard to make sure it's catalog of rules text for those cards is correct.
When it really starts to tackle MTG, I'll be extremely interested to see what format it chooses and the deck it builds. Will be a deck no one has seen before, or will end up building a deck exactly like one of the tier 1 decks in the format?
I think that if the AI can master go, it can do MTG.
Eh. While there are orders of magnitude more board states in Go than in Chess, certainly more than a modern computer could track, it's still a finite number. Go is fundamentally a game with very simple rules. A game like Magic has complex rules, and the game pieces themselves often change the rules. Occasionally, we find edge cases where the rules actually don't cover a situation, which can completely break a mechanical understanding of the subject. In the real world, the HJ of the event makes a ruling on the situation and the game goes on, then a high-level judge makes an [O] ruling online, and eventually the rules are amended to fix the omission. A computer attempting to analyze a ruleset can't do that.
I think that if the AI can master go, it can do MTG.
Eh. While there are orders of magnitude more board states in Go than in Chess, certainly more than a modern computer could track, it's still a finite number. Go is fundamentally a game with very simple rules. A game like Magic has complex rules, and the game pieces themselves often change the rules. Occasionally, we find edge cases where the rules actually don't cover a situation, which can completely break a mechanical understanding of the subject. In the real world, the HJ of the event makes a ruling on the situation and the game goes on, then a high-level judge makes an [O] ruling online, and eventually the rules are amended to fix the omission. A computer attempting to analyze a ruleset can't do that.
So i will give you that "finite" number of board states there(though everything is finite), however I don't think that because the rules cannot be fallowed, that will make the AI any less capable of playing MTG with ease. that being said there is the issue with MTG having a certain number of luck involved in the process and it is hard to say if the AI can manage to over come this, or guessing what your opponent will do. I suppose it will just make the best plays it can given the current state of the board? that is the only limitation i see atm, everything else is just a matter of time, though im interested in what you think of this.
Magic has two things Go does not: Luck of the Draw, and Player bluffing. A computer needs to predict the probability of draws, as well as learn the tells of players. Or else a player can exploit this by making seemingly sub-optimal moves.
Magic has two things Go does not: Luck of the Draw, and Player bluffing. A computer needs to predict the probability of draws, as well as learn the tells of players. Or else a player can exploit this by making seemingly sub-optimal moves.
you can kinda bluff in go. but it def not the same lol
do you play go aswell?
anyways, i suppose comparing the two games is apples and oranges.
Magic has two things Go does not: Luck of the Draw, and Player bluffing. A computer needs to predict the probability of draws, as well as learn the tells of players. Or else a player can exploit this by making seemingly sub-optimal moves.
Neither of these are issues. Computers can play poker better than the best humans simply by counting cards.
The bigger issue is that some information is not just hidden but fundamentally inaccessible. A poker deck is the same every time. To play high level magic is it is necessary to determine the likely contents of the opponent's deck. That is a tall order.
Magic has two things Go does not: Luck of the Draw, and Player bluffing. A computer needs to predict the probability of draws, as well as learn the tells of players. Or else a player can exploit this by making seemingly sub-optimal moves.
Neither of these are issues. Computers can play poker better than the best humans simply by counting cards.
The bigger issue is that some information is not just hidden but fundamentally inaccessible. A poker deck is the same every time. To play high level magic is it is necessary to determine the likely contents of the opponent's deck. That is a tall order.
I have not thought of this, how do you teach a AI something that doesn't really exist? not really a rule, I suppose. to play magic well i guess we may need to solve this.
I think that if the AI can master go, it can do MTG.
Eh. While there are orders of magnitude more board states in Go than in Chess, certainly more than a modern computer could track, it's still a finite number. Go is fundamentally a game with very simple rules. A game like Magic has complex rules, and the game pieces themselves often change the rules. Occasionally, we find edge cases where the rules actually don't cover a situation, which can completely break a mechanical understanding of the subject. In the real world, the HJ of the event makes a ruling on the situation and the game goes on, then a high-level judge makes an [O] ruling online, and eventually the rules are amended to fix the omission. A computer attempting to analyze a ruleset can't do that.
So i will give you that "finite" number of board states there(though everything is finite), however I don't think that because the rules cannot be fallowed, that will make the AI any less capable of playing MTG with ease. that being said there is the issue with MTG having a certain number of luck involved in the process and it is hard to say if the AI can manage to over come this, or guessing what your opponent will do. I suppose it will just make the best plays it can given the current state of the board? that is the only limitation i see atm, everything else is just a matter of time, though im interested in what you think of this.
No, everything is not finite. Magic does not have a finite number of board states, even with a finite number of cards.
Luck is not at issue here; we're talking about the computer understanding how to play the game, not necessarily how to out-play the opponent. While there is a lot of strategy involved, Go fundamentally has simple rules. The official rules document for the American Go Association has 12 rules in total, filling just 6 pages. The Magic Comprehensive Rules has 117 sections, most with a number of sub-rules within them (and some of those have sub-rules, and so on). Not counting glossary and credits, it takes up 173 pages. And the cards themselves can often change the game rules on-the-fly. Magic fundamentally has complex rules.
I think that if the AI can master go, it can do MTG.
Eh. While there are orders of magnitude more board states in Go than in Chess, certainly more than a modern computer could track, it's still a finite number. Go is fundamentally a game with very simple rules. A game like Magic has complex rules, and the game pieces themselves often change the rules. Occasionally, we find edge cases where the rules actually don't cover a situation, which can completely break a mechanical understanding of the subject. In the real world, the HJ of the event makes a ruling on the situation and the game goes on, then a high-level judge makes an [O] ruling online, and eventually the rules are amended to fix the omission. A computer attempting to analyze a ruleset can't do that.
So i will give you that "finite" number of board states there(though everything is finite), however I don't think that because the rules cannot be fallowed, that will make the AI any less capable of playing MTG with ease. that being said there is the issue with MTG having a certain number of luck involved in the process and it is hard to say if the AI can manage to over come this, or guessing what your opponent will do. I suppose it will just make the best plays it can given the current state of the board? that is the only limitation i see atm, everything else is just a matter of time, though im interested in what you think of this.
No, everything is not finite. Magic does not have a finite number of board states, even with a finite number of cards.
Luck is not at issue here; we're talking about the computer understanding how to play the game, not necessarily how to out-play the opponent. While there is a lot of strategy involved, Go fundamentally has simple rules. The official rules document for the American Go Association has 12 rules in total, filling just 6 pages. The Magic Comprehensive Rules has 117 sections, most with a number of sub-rules within them (and some of those have sub-rules, and so on). Not counting glossary and credits, it takes up 173 pages. And the cards themselves can often change the game rules on-the-fly. Magic fundamentally has complex rules.
I am not convinced magic doesn't have a finite number of board states. But i'm not arguing that I'm saying given enough time i'm sure the AI can adapt. it is an infant now yes, but magic isn't a unsolvable problem. its just a tricky hill to climb.
Side note, it is very difficult to compare these games in a constructive manner lol
The existence of unbounded combos proves that Magic doesn't have a finite number of board states.
(Edit: Magic is Turing-complete. Then again, so is Conway's Game of Life, which has even simpler rules than Go.)
That depends on what you mean by "unsolvable". For example, it may be that Magic is an undecidable problem when it comes to computability theory (I believe this is likely, considering both players' libraries and the opponent's hand are hidden information). Proving that Magic is undecidable would make it a "solved" problem as far as computability theory goes, but would make it "unsolvable" in a more colloquial sense.
The existence of unbounded combos proves that Magic doesn't have a finite number of board states.
(Edit: That said, Magic is Turing-complete. Then again, so is Conway's Game of Life, which has even simpler rules than Go.)
That depends on what you mean by "unsolvable". For example, it may be that Magic is an undecidable problem when it comes to computability theory (I believe this is likely, considering both players' libraries and the opponent's hand are hidden information). Proving that Magic is undecidable would make it a "solved" problem as far as computability theory goes, but would make it "unsolvable" in a more colloquial sense.
Hm, i suppose you are onto something there as far as unsolvable. Clearly you hold a higher knowledge of this so I will retract my argument and watch how things develop.
as far as infinite number of board states i guess i will take your word for it.
Formaly, yes, there are an infinite numbers of board states.
But i think : Kiki + Conscripts + any number of token can be grouped into just one state relevant for the decision tree.
Except that any player might interact with it at any point so you can't just ignore the exact board state.
A simpler proof that there are an infinite possible number of Magic games is to observe that there are infinitely many possible decks, unless you limit the AI just to considering decks that are 60 cards.
Regardless the number of possible games is close enough to infinite as makes no difference for computation and vastly larger than in Go.
Formaly, yes, there are an infinite numbers of board states.
But i think : Kiki + Conscripts + any number of token can be grouped into just one state relevant for the decision tree.
Except that any player might interact with it at any point so you can't just ignore the exact board state.
A simpler proof that there are an infinite possible number of Magic games is to observe that there are infinitely many possible decks, unless you limit the AI just to considering decks that are 60 cards.
Regardless the number of possible games is close enough to infinite as makes no difference for computation and vastly larger than in Go.
then maybe instead of saying infinite we could use vastly larger. However we r arguing Symantecs. Regardless the two are different games and require a different approach. Obviously it cannot be brute forced and memorize every game state / tree. It will need to think and therfore be superior ai.
I think timing becomes a problem. With some combinatorial games, giving the option of "no move" makes the game unsolvable.
There are also just many decisions that aren't correct or incorrect at the time, especially with the lack of knowledge of hidden information. It's not comparable to the same probabilistic strategy of Poker. Sure, I can say "Hey, he has five cards in hand and four copies of X in his hand, the odds he has it is blah", but actual players can do much better than that intuitively: If your opponent passed on their turn with two blue up, you're telegraphing counterspell regardless of the odds.
Go and Chess and Poker have much a much shorter list of rules and preparation involved.
Someone could bring Battle of Wits just to mess with the Computer's head.
I'd be interested to see what format they try to teach the computer. Then I'd be interested to see if they introduce it to that format's metagame. No format is "solved" but a large part of being ready to play Magic competitively is to know the popular strategies and how to identify them and then play around them. But you also need to be able to adapt to rogue decks.
Is the computer designing their deck too? If so it will be harder to teach it how to build a balanced deck instead of letting it build a pile of hate against the meta with no real way to win.
It actually doesn't matter, if there are unlimited states or not. The AI did not calculate every possible move in Go either.
There seems to be a miscommunication, here. My statement about infinite board states was a comment on the complexity differential between Magic and Go. Go has too many board states to keep a record of, but that number is still finite. Magic has an infinite number of board states. Kiki-Conscripts was simply an easily-written example to show luo xiang that Magic has infinite board states, not an example of a board state the AI would have trouble with.
A more relevant board state example is the Turing computer made of Magic cards, which I linked to. The board state:
Alex: Kazuul Warlord hacked to trigger off Yetis and changed to an Assembly-Worker
Alex: Kazuul Warlord hacked to trigger off Zombies and changed to an Assembly-Worker
Alex: 36 copies of Rotlung Reanimator (all nontoken, from Clone, etc.), all hacked twice to change Cleric and Zombie to specific other types, changed to be Assembly-Workers, granted phasing, with 18 phased out
Alex: Chancellor of the Spires (Alex is owner)
Alex: Tajuru Archer hacked to trigger off Reflections and changed to be an Assembly-Worker
Alex: 6 or more Assembly-Worker Reflection tokens
Alex: Vengeful Dead hacked to trigger off Assassins
Alex: Resolved Gather Specimens
Alex: No instant/sorcery cards in graveyard
Bob: Noxious Ghoul changed to an Assembly-Worker
Bob: Noxious Ghoul hacked to trigger off Yetis and changed to be an Assembly-Worker
Bob: 8 copies of Rotlung Reanimator, changed to be Assembly-Workers and hacked to several specific creature types
Bob: No instant/sorcery cards in graveyard
Cathy: Aether Flash
Cathy: Necroskitter
Cathy: No card in graveyard except Time and Tide
(Any): A large number of Dralnu's Crusades, hacked in specific ways to manipulate all our creature types
(Any): Curse of Death's Hold enchanting Alex
(Any): Engineered Plague naming Yeti
(Any): Engineered Plague naming Zombie
(Any): Blight Sickle equipped to Alex's Tajuru Archer
(All): At 1 life
Alex's Zombie tokens then represent the tape to the right of the head, with their toughness/marked damage representing how close to the head they are (1 toughness from dying is 1 step from the head, 2 toughness from dying is 2 steps, etc.). Yeti tokens do the same thing for the tape left of the head. Each token has two other creature types indicating a value (18 values total).
This board state can solve any Turing-complete calculation.
Next challenge: Implement Deep Mind using this board state, and then have the actual Deep Mind analyze it.
Google DeepMind is Now Analysing Magic and Hearthstone Cards
When it really starts to tackle MTG, I'll be extremely interested to see what format it chooses and the deck it builds. Will be a deck no one has seen before, or will end up building a deck exactly like one of the tier 1 decks in the format?
If it still isn't working here is the link without URL tags:
http://kotaku.com/google-deepmind-is-now-analysing-magic-and-hearthstone-1767628685
Two Score, Minus Two or: A Stargate Tail
(Image by totallynotabrony)
So i will give you that "finite" number of board states there(though everything is finite), however I don't think that because the rules cannot be fallowed, that will make the AI any less capable of playing MTG with ease. that being said there is the issue with MTG having a certain number of luck involved in the process and it is hard to say if the AI can manage to over come this, or guessing what your opponent will do. I suppose it will just make the best plays it can given the current state of the board? that is the only limitation i see atm, everything else is just a matter of time, though im interested in what you think of this.
you can kinda bluff in go. but it def not the same lol
do you play go aswell?
anyways, i suppose comparing the two games is apples and oranges.
Neither of these are issues. Computers can play poker better than the best humans simply by counting cards.
The bigger issue is that some information is not just hidden but fundamentally inaccessible. A poker deck is the same every time. To play high level magic is it is necessary to determine the likely contents of the opponent's deck. That is a tall order.
Luck is not at issue here; we're talking about the computer understanding how to play the game, not necessarily how to out-play the opponent. While there is a lot of strategy involved, Go fundamentally has simple rules. The official rules document for the American Go Association has 12 rules in total, filling just 6 pages. The Magic Comprehensive Rules has 117 sections, most with a number of sub-rules within them (and some of those have sub-rules, and so on). Not counting glossary and credits, it takes up 173 pages. And the cards themselves can often change the game rules on-the-fly. Magic fundamentally has complex rules.
Two Score, Minus Two or: A Stargate Tail
(Image by totallynotabrony)
Side note, it is very difficult to compare these games in a constructive manner lol
Board state #2: 5x Mountain, Kiki-Jiki, Conscripts, Conscripts token
Board state #3: 5x Mountain, Kiki-Jiki, Conscripts, 2x Conscripts tokens
.
.
.
Board state #X: 5x Mountain, Kiki-Jiki, Conscripts, (X-1)x Conscripts tokens
The existence of unbounded combos proves that Magic doesn't have a finite number of board states.
(Edit: Magic is Turing-complete. Then again, so is Conway's Game of Life, which has even simpler rules than Go.)
That depends on what you mean by "unsolvable". For example, it may be that Magic is an undecidable problem when it comes to computability theory (I believe this is likely, considering both players' libraries and the opponent's hand are hidden information). Proving that Magic is undecidable would make it a "solved" problem as far as computability theory goes, but would make it "unsolvable" in a more colloquial sense.
Two Score, Minus Two or: A Stargate Tail
(Image by totallynotabrony)
Hm, i suppose you are onto something there as far as unsolvable. Clearly you hold a higher knowledge of this so I will retract my argument and watch how things develop.
as far as infinite number of board states i guess i will take your word for it.
Except that any player might interact with it at any point so you can't just ignore the exact board state.
A simpler proof that there are an infinite possible number of Magic games is to observe that there are infinitely many possible decks, unless you limit the AI just to considering decks that are 60 cards.
Regardless the number of possible games is close enough to infinite as makes no difference for computation and vastly larger than in Go.
There are also just many decisions that aren't correct or incorrect at the time, especially with the lack of knowledge of hidden information. It's not comparable to the same probabilistic strategy of Poker. Sure, I can say "Hey, he has five cards in hand and four copies of X in his hand, the odds he has it is blah", but actual players can do much better than that intuitively: If your opponent passed on their turn with two blue up, you're telegraphing counterspell regardless of the odds.
Someone could bring Battle of Wits just to mess with the Computer's head.
I'd be interested to see what format they try to teach the computer. Then I'd be interested to see if they introduce it to that format's metagame. No format is "solved" but a large part of being ready to play Magic competitively is to know the popular strategies and how to identify them and then play around them. But you also need to be able to adapt to rogue decks.
Is the computer designing their deck too? If so it will be harder to teach it how to build a balanced deck instead of letting it build a pile of hate against the meta with no real way to win.
I think it's neat. And a hell of a lot better story than Microsoft's twitter AI.
"Sometimes, the situation is outracing a threat, sometimes it's ignoring it, and sometimes it involves sideboarding in 4x Hope//Pray." --Doug Linn
Art is life itself.
A more relevant board state example is the Turing computer made of Magic cards, which I linked to. The board state:
Alex: Kazuul Warlord hacked to trigger off Yetis and changed to an Assembly-Worker
Alex: Kazuul Warlord hacked to trigger off Zombies and changed to an Assembly-Worker
Alex: 36 copies of Rotlung Reanimator (all nontoken, from Clone, etc.), all hacked twice to change Cleric and Zombie to specific other types, changed to be Assembly-Workers, granted phasing, with 18 phased out
Alex: Chancellor of the Spires (Alex is owner)
Alex: Tajuru Archer hacked to trigger off Reflections and changed to be an Assembly-Worker
Alex: 6 or more Assembly-Worker Reflection tokens
Alex: Vengeful Dead hacked to trigger off Assassins
Alex: Resolved Gather Specimens
Alex: No instant/sorcery cards in graveyard
Bob: Noxious Ghoul changed to an Assembly-Worker
Bob: Noxious Ghoul hacked to trigger off Yetis and changed to be an Assembly-Worker
Bob: 8 copies of Rotlung Reanimator, changed to be Assembly-Workers and hacked to several specific creature types
Bob: No instant/sorcery cards in graveyard
Cathy: Aether Flash
Cathy: Necroskitter
Cathy: No card in graveyard except Time and Tide
(Any): A large number of Dralnu's Crusades, hacked in specific ways to manipulate all our creature types
(Any): Curse of Death's Hold enchanting Alex
(Any): Engineered Plague naming Yeti
(Any): Engineered Plague naming Zombie
(Any): Blight Sickle equipped to Alex's Tajuru Archer
(All): At 1 life
Alex's Zombie tokens then represent the tape to the right of the head, with their toughness/marked damage representing how close to the head they are (1 toughness from dying is 1 step from the head, 2 toughness from dying is 2 steps, etc.). Yeti tokens do the same thing for the tape left of the head. Each token has two other creature types indicating a value (18 values total).
This board state can solve any Turing-complete calculation.
Next challenge: Implement Deep Mind using this board state, and then have the actual Deep Mind analyze it.
Two Score, Minus Two or: A Stargate Tail
(Image by totallynotabrony)
Marath, Will of the Wild
Friendly Kess Twin Combo
Tatyova - Sir Bounce A Lot
Gonti's Luxury Pie
Prime (Eldrazi) Speaker Zegana (Retired)