logoalt Hacker News

brudgers • yesterday at 11:00 PM • 2 replies • view on HN

related, Magic the Gathering is Turing Complete.

Which to me suggests that one will encounter the halting problem in theory if not in practice.


Replies

7373737373 • today at 1:38 PM

In the 3 Card Blind format (played with only 3 vs 3 cards, the optimal play wins, short intro: https://youtube.com/watch?v=29P243ggtU8), there exists a game in the tournament history which no one has been able to solve due to the sheer combinatorial explosion of possibilities, the Hangarback Walker game: https://youtube.com/watch?v=hdaiKwKN50U

It is also possible to represent small Turing machines with unsolved halting status ("Cryptids" https://wiki.bbchallenge.org/wiki/Cryptids) as a legally reachable board state (Example: https://web.archive.org/web/20241222020126/https://aesort.co...). It's unlikely anyone manages to do that in a tournament, but it is conceivable that the outcome of a specific game will remain undetermined by any judge (unless the math or computer science problem it represents is solved).

In practice, what makes MtG games in common formats (especially optimally) unsolvable is the large amount of hidden information, and combinatorial "predictive firewall" of random deck shuffles and the vast card pool.

JTbane • today at 12:54 PM

One of the coolest things about MtG is if you set up an infinite loop that is voluntary (like, able to be ended) that often puts you in a winning position. However, if it is a true involuntary infinite loop the game ends in a draw.