3 ms·
In 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
by UncleMeat 8y ago
In 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 8y 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 8y agoSure, but that isn't what theory people care about. Most real world SAT instances are tractable. But SAT is still NP-Complete.
- manifestsilence 8y 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 8y 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).