13 ms·
Magic: The Gathering is Turing Complete
- kowdermeister 7y agoDeepMind engineers are probably getting triggered by this headline :)
- gwern 7y agoThey'll have to finish solving Hanabi first: https://twitter.com/deepmindai/status/1092471486936436736 https://twitter.com/deepmindai/status/1092471486936436736
- C1sc0cat 7y agoerm "Though similar to role-playing fantasy games such as Dungeons and Dragons" No MTG is not at all similar to role playing games.
- gberger 7y agoIt is similar in lore/setting.
- EamonnMR 7y agoThat was an accurate statement in, say, 1994 but boy did it diverge. Though now they've published a D&D book based on an MTG specific setting so I suppose they could converge again.
- toyg 7y agoIt should also be mentioned that Magic effectively "ate up" D&D, when Wizards Of The Coast (owners of MTG) bought TSR (owners of D&D).
- C1sc0cat 7y agoNot sure that's true MTG is not based on any of the DnD settings nor does it have Character Races and Classes.
- aloisdg 7y agoYou have creature type (a list of tags basically). A Human Soldier or a Goblin Wizard is common in MTG.
- C1sc0cat 7y agoYou Have a thief in Catan
- maxsilver 7y agoYep. In fact, the opposite is now true. Some of DnD is now (in part) based on MTG, including an MTG setting, MTG Character Races, and such. http://dnd.wizards.com/products/tabletop-games/rpg-products/guildmasters-guide-ravnica http://dnd.wizards.com/products/tabletop-games/rpg-products/...
- eequah9L 7y agoThe whole sentence makes even less sense: "Though similar to role-playing fantasy games such as Dungeons and Dragons, it has significantly more cards and more complex rules than other card games." As if similarity to D&D said anything at all about number of cards relative to other card games.
- feenix566 7y agoD&D has infinite cards.
- jbattle 7y agoif my nerd history is correct - MTG almost killed dungeons and dragons in the 90's!
- Loughla 7y agoDid it? I sort of thought the 90's death of D&D was more of the hangover of the 'devil worshipping' accusations of the 80's finally hitting. That and D&D being associated with all things nerd, which was very out of vogue through the 90's.
- mipmap04 7y agoIt definitely took a lot of attention at my local game shop away from traditional table top role playing.
- C1sc0cat 7y agocough 4th Edition cough but Pathfinder took over
- lawn 7y agoSomehow I highly doubt Magic is the most complex played game in the world. For instance there are many different card games, what's to say Magic is more complex than them?
- dagw 7y agoBasically their argument is that in all those other games determining the optimal strategy is computable (in the computer science sense) while MTG is the only non-computable real world game they could find. If that is a valid definition of a 'complex' game is left as an exercise to the reader.
- UncleMeat 7y agoComplex in a cs sense. Chess is fully computable. Magic is not.
- stellaathena 7y agoDid you actually read the paper? There's a mathematical definition of complexity that is used, and on that metric it is shown to be far harder than any other previously analyzed game.
- lawn 7y agoYes. The paper is good, the title of the submission was not. Of course by now the title and even the submission link has completely changed (it was linked to an article before).
- CryoLogic 7y agoI actually believe it may be the hardest card game to compute. Magic has been around since 1993, and releases new cards every year. There are currently > 15,000 unique cards in the game. When playing, you don't know what the next card drawn will be. You also don't know what is in your opponents hand. In poker for example, there is a very small pool of possible top decks and hands. Search trees in Magic (especially "eternal" formats that allow you to pick cards from any expansion) would be too massive to compute. These cards are not vanilla either (not just statpools) - they contain over 100 categorical effects and many of them have unique effects. I'd guess at least 1000 have unique effects and interactions. Add on to that the fact that magic is both a pro-active and re-active card game. In most card games (aka hearthstone for example) you cast cards on your turn. In Magic you can cast many cards "in response" e.g. counterspells. You can also just play some cards on opponents turn. Beyond this the game is split into a number of phases and card timing by phase is very important. Sometimes you want to cast on end step vs combat - the same spell does the same thing but might be much lower risk depending on the phase.
- hu3 7y agoDirect link to the study "Magic: The Gathering is Turing Complete": https://arxiv.org/pdf/1904.09828.pdf https://arxiv.org/pdf/1904.09828.pdf
- petters 7y agoThanks, from reading the abstract, is sounds as if they have an algorithm for the halting problem.
- justinmchase 7y agoThank you sir, I am not smart enough to find the direct link from the overview page linked apparently.
- hu3 7y agoYou're welcome. When I posted this, the thread linked to a sensationalist article. The link was later edited along with the title.
- emilfihlman 7y agoEh, just because you have a big 20000 choose 60 initial set doesn't make it "most complex".
- dagw 7y agoThat's not their argument either. The gist of their argument is that you can combine those cards and the legal moves they allow to encode a Turing machine and thus determining the winner is equivalent to solving the halting problem.
- k__ 7y agoAlso, most of the cards are probably some basic lands and simple creatures without any skills.
- gpderetta 7y agoI would be surprised if this is the case. Of those 20k unique cards, exactly 5 are basic lands (6 if you count Wastes). I also have a feeling that vanilla creatures are less common than non-vanilla creatures (and creatures are a just a subset of all card types).
- wyldfire 7y agoThey meant most of the 60 chosen are lands.
- rcxdude 7y agoDeck 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.
- simonh 7y agoAnd the paper proves that this is true even if all the moves in the game are forced by cards that give you no choices to make as players.
- Sahhaese 7y agoDoes it actually make sense to say that something that is non-computable is most complex? That seems like a contradiction.
- theoh 7y agoI think you are misunderstanding the article. The point is that when the game is considered as a computation, the problem of figuring out who is going to win is not computable. Like every discussion of the halting problem, this is about whether or not a program exists that can calculate how some other specific program will behave.
- Sahhaese 7y agoI understood that, but question whether it's meaningful to say that is therefore more complex. Complexity theory just doesn't apply? (Or does it?)
- theoh 7y agoWell, it's at least as complex as a Turing machine. That's a statement of complexity. Maybe you are asking whether it is possible for the winning strategy of a very simple deterministic game to be non-computable. In other words, maybe there's a possible way of defining computability which is orthogonal to complexity. The CS definitions of both terms are closely connected to Turing machines, though. Can you imagine a simple deterministic game that couldn't be "solved" by an algorithm?
- babyloneleven 7y agoThe set of all problems that can be solved by a Turing machine if there's an answer (possibly hanging if there's no answer) sits at the top of the complexity hierarchy (it's equivalent to the recursively enumerable languages) The usual complexity classes of decision problems, such as P and NP, are subsets of what a Turing machine can solve, and so are weaker complexity classes.
- stellaathena 7y ago
- dagw 7y agoThe actual article (as opposed to this summary) states that it's the most computationally complex game, which is quite a different claim.
- arey_abhishek 7y agoIt should be retitled as 'MTG is the most complex game we've played'. I would counter that other card driven games like Android Netrunner, Terraforming Mars, Lisboa, Hanabi, etc are just as or even more complex.
- mattashii 7y agoI have to disagree on that. At least Terraforming Mars and Hanabi have a playtime limited by ever-dwindling resources. I don't know the other games, but I suspect they also have some kind of supply that has a limit in how much it can be used/aquired. MTG has ways to return to a previously seen play state, technically allowing a game to continue infinitely, depending on your deck, of course.
- eru 7y agoLoops don't really add complexity. MtG can add now tokens of arbitrary number. So that can add arbitrary complexity.
- T-hawk 7y agoTerraforming Mars can continue infinitely. The end state requires players to deliberately take the actions to reach it. If no player chooses to end the game, it never will. Players could continue forever to use engines that generate points each round, to unbounded totals. By game theory they shouldn't; eventually a player will be able to end the game while ahead and should do so; but we're already disregarding the motivation of winning for MTG. (An expansion introduces a rule that each round automatically advances one of the game-ending parameters, but says you can play either with or without that rule.)
- Xelbair 7y agoI played Netrunner a lot, and it beats MTG in base rules(as i do mean absolute minimum of MTG rules) complexity. When it comes to cards themselves, and their effect on gameplay, it blows netrunner away. Just look how effect layers are constructed, or even a simple stack and priority itself, not to mention infinite loops. I do agree that i had way more fun playing Netrunner, mostly because you cannot be mana screwed/flooded like in mtg - as you can spend action to get resources or cards.
- baltimore 7y agoI'll see your Magic and raise you Nomic: https://en.m.wikipedia.org/wiki/Nomic https://en.m.wikipedia.org/wiki/Nomic
- remedan 7y agoI've never heard of Nomic before but now I really want to get a group of nerds together and attempt to play it.
- bulte-rs 7y agoPlease count me in ;-) Can't think of anyone in my direct environment crazy enough to try this.
- mikelevins 7y agoI had a group of friends who played it in the 1980s. It was a long-lived informal group of game-players that started in the 1970s, and has continued (with almost-total replacement of the membership over time) until roughly the present day. We played very different games at different times--pencil-and-paper roleplaying games; Risk and Diplomacy; Civilization; Cosmic Encounter; Illuminati; MMORPGS; Nomic; custom versions of several of the above using modified rules and our own maps and other materials. Nomic worked quite well for one of the iterations of the group. It was very entertaining--though exhausting to play--and it was educational about the legislative process. I think the most significant thing I learned about legislation is that, regardless of what it is theoretically supposed to accomplish, what it actually does accomplish is to reward legislators who are skillful at gaming the legislative process. I learned other things, too: - Given an incentive, people can be incredibly flexible and creative in trying to outmaneuver one another in dealmaking. - Very often, the most capacious bladder wins. - If you succeed in making rules about what is allowed, you must expect that others will make rules redefining the terms used in those rules. - Any self-serving proposal can be made to sound like it's for the common good with the right combination of incentives, creativity, and charisma. - No matter how bitterly someone opposes your proposal, you can still get their support if you can find the right payoff and add it to your proposal. - There is no way to limit what other legislators can do to a proposal through amendments (we tried all sorts of things, and they all ultimately failed). I also learned that real-world legislators have to have incredible endurance. A hotly-contested game of Nomic can drag on for hours and leave all the participants completely exhausted. Real legislation must be much more grueling. The stakes are higher, the costs and rewards are more significant, and the game never ends.
- lozenge 7y ago"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. " What is this input? Board size?
- cluoma 7y agoUsually it would be number of legal moves. Of course this would also change throughout the game as pieces are removed.
- philipov 7y agoThe number of legal moves is an intermediate calculation. The input is the initial game state, and the output is usually the number of possible final game states.
- philipov 7y agoIt is board size for Go, because the starting condition is an empty board. For chess, I would expect the complexity to also be a function of the number of pieces, and possibly the types of pieces.
- adrianN 7y agoIf you generalize chess to an N*N board, it becomes PSPACE complete to decide which player has a winning strategy: https://www.sciencedirect.com/science/article/pii/0022000083900302?via%3Dihub https://www.sciencedirect.com/science/article/pii/0022000083...
- boomlinde 7y agoI think that the number of positions that need to be considered for a brute force exhaustive search are roughly proportional to an exponential function of the number of moves made, so the statement holds true for that. In reality, the number of possible moves is not constant and depends on the current position.
- petters 7y agoMtG 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 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."
- lmm 7y ago> 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 result of some arbitrarily complex computation. Imagine we play a "game" where I win if there's a nontrivial zero of the Riemann zeta function with real part not equal to one half, otherwise you win. Neither of us has any decisions to make in this game. It's still very difficult to determine who's going to win.
- rishav_sharan 7y agoCan you ELI5 how a game can be Turing complete? I have only heard that in relation to programming languages.
- simonh 7y agoMagic is played by taking a card from the top of your pile and following the instructions on it, then your opponent does the same. In normal games the decks are shuffled, but for this to work you have to be able to program the order of the cards in both decks. In this paper they program the game by constructing the decks using a subset of cards that all have mandatory effects. 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.
- yorwba 7y agoI guess this is newsworthy because a paper was put on arXiv, but the result has been known for a while. See e.g. this submission a year ago: https://news.ycombinator.com/item?id=15712377 https://news.ycombinator.com/item?id=15712377
- mettamage 7y agoI'll just make my submission here then as I don't want to clutter the front page [1]. The submission includes a list of a lot of things that are accidentally turing complete including Magic The Gathering. [1] http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html http://beza1e1.tuxen.de/articles/accidentally_turing_complet...
- Dylan16807 7y agoI've always objected to the CSS example. It's demonstrating that CSS can do basic arithmetic. When you combine basic arithmetic and an infinite loop, you can make a "Turing machine" with limited memory. But CSS is not providing that loop. CSS is not Turing complete. It's like pulling the state table out of a Turing machine and showing it off all by itself. It doesn't take much to extend it into a full Turing machine, but it's also not doing much at all by itself. A Turing machine is simple, and half a Turing machine is really simple. It's missing the point of "accidental Turing completeness" if it can't iterate to an actual result.
- IggleSniggle 7y agoOff the cuff conjecture, but wouldn't any number of render methods allow for an infinite loop? Animation methods come to mind first.
- svachalek 7y agoIn CSS itself, I don't know of a way to feed one result back into an earlier one and thus create a loop. If you're talking about JavaScript, it is and was intended to be Turing complete. Edit: Just saw the HTML/CSS3 example on the page. Mind blown.
- x0to1 7y agoFrom 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?
- Drup 7y agoNo it isn't: The goal is to use a specific construction with specific cards to build a universal Turing machine. Unlike previous attempts, which used cards that leave some room for Player agenda, this new version doesn't.
- yorwba 7y ago> 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-FUN-2018-14.pdf 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."
- r34 7y agoI'd claim strongly, that any game with: - finite number of pieces (eg. cards) - finite number of actions each round - clear endgame criteria is computionally solvable. What comes with randomness is stochasticity, but if that made game unsolvable what about poker (solved for limit heads-up) and even scrabble? Probably it's kind of semantic problem. I'm not complexity nor game theory expert.
- hjk05 7y agoMTG doesn’t have finite number of pieces, or finite number of actions each turn though. Naturally people have implemented Turing machines in mtg. www.toothycat.net/~hologram/Turing Also, the endgame criteria of mgt can be changed, but that said there is only a finite number of simple possible endgames in a sense.
- HelloNurse 7y agoIt depends. I'm pretty sure it is possible to layer an unlimited number of contrasting win/lose conditions; distinguishing essentially different "endgames" seems slippery.
- EamonnMR 7y agoWell some cards can create additional (potentially infinite) game pieces or resources with which to preform more actions per round.
- Khoth 7y agoActions in Magic: the Gathering let you create "tokens" which are like cards but aren't limited in number. Although you can only have a finite number in any given game, there's no upper bound on how many you can have.
- bow_ 7y agoThere is indeed no limitation on the number of tokens in a game. There are many combo wins that involve having (technically) infinite tokens, dealing infinite damage, gaining infinite life, taking infinite turns. You get the idea. I said technically because in practice, setting this to a very large number is enough for the win. Dealing 1e6 damage is, although possible, already way overkill in most cases when your opponent starts with 20 life.
- vaylian 7y agoSome 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 * Antagonistic
- shapiro92 7y agobut 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?
- dagw 7y agoand the synergies can be easily calculated from a machine This article is all about how those synergies are Turing complete and thus cannot be easily calculated since doing so reduces down to solving the halting problem. edit: that being said I suspect that writing an AI that plays "well enough" to beat human players, as opposed to optimally, is quite doable.
- mratsim 7y agoAs a Magic player (since 1996) and Go player (since 2004) and also deep learning scientist, the main issue with Magic is modeling the game. The interactions and exceptions are really numerous, I expect Magic Arena and Magic Online are a mess of spaghetti code. 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 ...
- Endy 7y ago
- devit 7y agoWhile this paper shows that a player can create a game state where deciding the game result is Turing-complete, it does not show that doing so is an optimal strategy under any circumstance (in particular, the setup requires a starting situation where the player can just win the game instead of performing the setup). So it seems perfectly possible (and in fact highly likely) that this result does not hold if players play optimally, especially if deck selection is included in the strategy.
- simonh 7y agoThe paper hasn't got anything to do with optimal game strategies, it's just showing what it is possible to achieve computationally within the rules of the game. If you're looking for advice on how to pay to win, this paper really isn't for you.
- stellaathena 7y agoThis is not correct: the paper does have to do with optimal strategies. They even say as much in the abstract. >In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem, solving a problem that has been open for a decade
- manifestsilence 7y agoThis is an important distinction, as I've found that the optimal strategies in Magic are very rarely the most intricate ones or the ones involving recursive constructs. Occasionally a trivial infinite loop becomes part of a top deck, but you definitely aren't going to see someone doing the equivalent of calculating pi to win. I think the Turing completeness is definitely still part of the appeal of Magic, because the bizarre edge cases and complexity occasionally do creep in to even serious play and add a lot of interest, but the complexity is of the iceberg variety, where most of it rarely makes itself visible most of the time.
- simonh 7y agoOK that's fair enough, but it's not saying anything about what optimal strategies might actually be, just examining their potential complexity in an extreme edge case scenario.
- cosmolev 7y agoA collection of things that are Turing-complete by accident https://news.ycombinator.com/item?id=16383072 https://news.ycombinator.com/item?id=16383072
- halfdeadcat 7y agoOh good. This will be handy if I ever need to compute FFT's using only Magic cards.
- thatoneuser 7y agoBasic question but what does being Turing complete actually signify? I get the concept but don't know why it matters.
- UncleMeat 7y agoIt means telling whether the game is a draw or a win is undecidable. So magic strategy is not computable.
- zahrc 7y agoGeneral and obvious answer: That means something can (theoretically) compute on it’s own, on the highest computing level. Personal importance: something like mgtg and duplo train tracks, which isn’t intended to build a Turing computer, is used to build one, it’s challenging and a creative outlet of tech knowledge. My favorite example is red stone in Minecraft.
- mankyd 7y agoIn theory, if you can perform a computation/algorithm on one turing-complete device, you can transform it to run on another. That is to say, anything your desktop computer can do, Magic can do as well (albeit much much _much_ slower).
- vectorEQ 7y agosaying anything your computer can do in such a sentence is misleading. computers are far far away from turing machines these days. they can do much more. for example, good luck making a socket connection on Magic the gathering. even if you can compute everything you need with it, you will never succeed to connect...
- mankyd 7y agoThat's a statement about the practical engineering involved, yes. However, saying a computer is "Turing complete" is not misleading. It is purely a statement of its mathematical properties. If sockets were given absurd timeouts and/or you could run MtG at much higher speeds, (and it was given a medium through which it could communicate), it would have no problem making a socket connection. It is only the practicality of the matter that becomes a barrier.
- logfromblammo 7y agoSo add a new rule: Choice-lock. If any player is unable to make a choice for some finite countable number of consecutive turns, they lose. This could have also prevented combining infinite turn combos with the ante-related cards to produce "I have created a game state where I can take ownership all the cards in your deck, and then win," which was fun to do in the original M:tG PC game, even though running through the combo to actually take all of the cards was a bit tedious.
- stellaathena 7y agoThis seems like a bizarre rule to add. Why is this result even a bad thing for Magic?
- logfromblammo 7y agoIt makes it more difficult to create challenging-but-still-fair bots in computerized versions of the game.
- hannasanarion 7y agoBut that's already how bots are made. You don't need to add rules to the game before you can constrict the thinking time of entertainment AI
- manifestsilence 7y agoChallenging but fair bots are by definition not supposed to treat the game as totally algorithmically solvable. They can work fine on heuristics rather than algorithms, the same way that players do. There are moments when a player needs to think through all the possibilities available in the game state, and other moments when they just use a rule of thumb, like, "use this card to destroy the greatest threat currently out because time is not currently on my side to wait for what they might play next".
- magnat 7y agoNow, if only we had algorithm to decide whether for provided game table state, the chain of triggers ever stops or continues indefinitely.
- crimsonalucard 7y agoTuring completeness in something designed to be domain specific is a sign of bloat and is a sort of smell. It's a sign of a design taken so far that it now has the capability to compute anything when in all intents and purposes it's design is domain specific. One other example of this is css. Did you know css is Turing complete? Note that most programming languages are Turing complete because that is the domain: To express every possible computation in the language, and thus in these cases Turing completeness is not a design smell.
- hannasanarion 7y agoCSS is not turing complete. CSS can do arithmetic, but it has no way to designate routines or repeat its own behavior.
- crimsonalucard 7y agoYou are not categorically wrong because I missed some semantics in my statements. However the essence of what your saying is incorrect. Let me rephrase more specifically: CSS3 + HTML5 is turing complete. Since CSS is always used in the context of HTML I left that out, but rigor is important! source: https://stackoverflow.com/questions/2497146/is-css-turing-complete https://stackoverflow.com/questions/2497146/is-css-turing-co... Note that this happened with the later versions of CSS indicating that the specification became turing complete after years and years of tacking on features. This is the pattern of bloat accumulating over time.
- cryptica 7y agoI don't understand why researchers are so interested in 'Turing completeness'. The concept of a Turing machine which operates on a strip of tape is outdated and no longer intuitive. It would be good if the abstraction of a 'Turing machine' could be refined into something more modern.
- Retra 7y agoThe importance of Turing Completeness is the capabilities it offers, not the model of the machine that offers them. The machine doesn't matter at all, which is precisely why the "strip of tape" is still used.
- pazimzadeh 7y agoConsidering that all of life essentially runs on a strip of tape and machine(s) that can read and write to it, I think it's still pretty relevant.
- stellaathena 7y agoTo be more specific about what the other responses say: Being "equivalent to a TM" and being "equivalent to the Python compiler" mean the exact same thing. Pretty much every widely used model of computation is equivalent in computing power to Turing machines. The notable exceptions are all weaker than Turing machines, such as arithmetic circuits.
- djakjxnanjak 7y agoYou might like the RASP: https://en.m.wikipedia.org/wiki/Random-access_stored-program_machine https://en.m.wikipedia.org/wiki/Random-access_stored-program...