61–70 of 194 posts
Eh, just because you have a big 20000 choose 60 initial set doesn't make it "most complex".
From the paper: "In this work, we solve this problem by reformulating the construction to exclusively use cards with mandatory effects." So it's more a of a subset of MTG's rules. Still, there are commercial video games out beyond MTG and they've been out for some time. Why has the game theory field not kept up with them?
Why assume that it hasn't? The paper cites http://drops.dagstuhl.de/opus/volltexte/2018/8805/pdf/LIPIcs... which claims to "show the undecidability of whether a team has a forced win in a number of well known videogames including: Team Fortress 2, Super Smash Brothers: Brawl, and Mario Kart."
Earlier quoted context omitted.
> EDIT: This from the real abstract sounds very strange: > "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable." It's not so strange: the game is Turing complete, so the winner can be undecidable because who wins is the…
Can you ELI5 how a game can be Turing complete? I have only heard that in relation to programming languages.
I think what they do is set up a sequence of cards that 'initialises' the game state with various creatures and resources. These together with the game rules form the Turing machine. Then they have a sequence of cards that correspond to the 'paper tape' of symbols a Turing machine operates on.
MtG is played by choosing 60 cards from 20k. Everything is finite. There must be some generalization in order to make it noncomputable. There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large. EDIT: This from the real abstract sounds very strange: "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows…
20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.
MtG is played by choosing 60 cards from 20k. Everything is finite. There must be some generalization in order to make it noncomputable. There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large. EDIT: This from the real abstract sounds very strange: "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows…
Earlier quoted context omitted.
> EDIT: This from the real abstract sounds very strange: > "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable." It's not so strange: the game is Turing complete, so the winner can be undecidable because who wins is the…
Can you ELI5 how a game can be Turing complete? I have only heard that in relation to programming languages.
The tape is represented by tokens whose strength increases with their distance from the read head, such that the current cell is the weakest one. On every loop iteration, it gets killed (read) and triggers different effects depending on its type, such as getting replaced (writing a new value), changing the effects that will be active on the next iteration (changing state) and dealing damage to one side of the tape but not the other (moving the read head).
MtG is played by choosing 60 cards from 20k. Everything is finite. There must be some generalization in order to make it noncomputable. There are probably many games that can somehow encode a halting problem if the board size is made arbitrarily large. EDIT: This from the real abstract sounds very strange: "Our result is also highly unusual in that all moves of both players are forced in the construction. This shows…
AFAIK 60 the minimum number of cards you have to put in your deck, but (at the least at the times) there was not a maximum number. 20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.
Some thoughts about AI: After Chess, Go and StarCraft 1, Magic is definitely an interesting game for AI to tackle next. While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account. From an AI perspective Magic is also very hard because it is: * Non-deterministic * Partially observable…
but those interactions are actually not as large as a real time game such as Dota or even Go. Your deck has an X amount of cards and the synergies can be easily calculated from a machine. The real problem would be, is it smart enough to beat an unknown opponent deck?
For go modeling basically you have in input an image of the go board, and for DOTA an image of your screen and the action you have are "limited" and do not change wildly depending of the state of your screen (except if you're dead on Dota).
For Magic, you can't just use deep reinforcement learning with an image input, you need to somehow track the state of your deck, cards, instant effects, what your opponent did ...
Earlier quoted context omitted.
AFAIK 60 the minimum number of cards you have to put in your deck, but (at the least at the times) there was not a maximum number. 20k is the number of unique cards, but you can put as much as 4 copies of the same card in your deck for the vast majority of cards. You can also put as many "normal" lands as you wish in your deck.
As many as you can shuffle unassisted is the upper limit.
Eh, just because you have a big 20000 choose 60 initial set doesn't make it "most complex".
Deck building is not the entirety of the decision involved in playing magic. One of the points in the paper is that the number of decisions in the game is potentially infinite and that the consequences of those decisions can at lease in principle be rendered incomputable.