Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.02863 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912961054900224 |
|---|---|
| author | Nicolosi, Orazio Pisciotta, Federico Bresolin, Lorenzo |
| author_facet | Nicolosi, Orazio Pisciotta, Federico Bresolin, Lorenzo |
| contents | Motivated by the results for Magic: The Gathering presented in [CBH20] and [Bid20], we study a (different) computability problem about winning strategies in Yu-Gi-Oh! Trading Card Game, a popular card game developed and published by Konami. We show that the problem of establishing whether, from a given game state, a given computable strategy is winning is undecidable. In particular, not only do we prove that the Halting Problem can be reduced to this problem, but also that this problem is actually $Π^1_1$-complete. We extend this last result to all strategies with a reduction on the set of countable well orders, a classic $\boldsymbolΠ^1_1$-complete set. For these reductions, we present two legal decks (according to the current Forbidden & Limited List of Yu-Gi-Oh! Trading Card Game) that can be used by the player who goes first to perform them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_02863 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Deciding winning strategies in Yu-Gi-Oh! TCG is hard Nicolosi, Orazio Pisciotta, Federico Bresolin, Lorenzo Logic Computational Complexity Computer Science and Game Theory 03D35 (Primary), 91A44, 03E15 (Secondary) Motivated by the results for Magic: The Gathering presented in [CBH20] and [Bid20], we study a (different) computability problem about winning strategies in Yu-Gi-Oh! Trading Card Game, a popular card game developed and published by Konami. We show that the problem of establishing whether, from a given game state, a given computable strategy is winning is undecidable. In particular, not only do we prove that the Halting Problem can be reduced to this problem, but also that this problem is actually $Π^1_1$-complete. We extend this last result to all strategies with a reduction on the set of countable well orders, a classic $\boldsymbolΠ^1_1$-complete set. For these reductions, we present two legal decks (according to the current Forbidden & Limited List of Yu-Gi-Oh! Trading Card Game) that can be used by the player who goes first to perform them. |
| title | Deciding winning strategies in Yu-Gi-Oh! TCG is hard |
| topic | Logic Computational Complexity Computer Science and Game Theory 03D35 (Primary), 91A44, 03E15 (Secondary) |
| url | https://arxiv.org/abs/2603.02863 |