3 ms·
While 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 str
by devit 7y ago
While 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.
- UncleMeat 7y agoIn game playing theory, an optimal strategy is a function that takes any state and tells you the proper next move. It does not matter how you got there For MTG strategy to be computable you must be able to compute whether entering this computation is a good choice, which requires solving the halting problem.
- manifestsilence 7y agoThis does mean that MTG is not algorithmically solvable, which is very interesting. However, in most cases I think it is heuristically trivial to determine the best move.
- UncleMeat 7y agoSure, but that isn't what theory people care about. Most real world SAT instances are tractable. But SAT is still NP-Complete.
- manifestsilence 7y agoTrue. There's sort of a divide in this thread over two questions that are interesting in completely different ways. One is how deep a game MTG is in practice, and the other is whether it is an algorithmically solvable game (no). My take-away, other than it being really cool that it's Turing-Complete, is that any bot will need to accept that not all infinities it could get stuck in are even detectable and resort to heuristics at a certain point.
- devit 7y agoNot really, it's possible that there is always a strategy that can be proven to be better than entering the computation (because it wins the game deterministically, for instance).