Game complexity: Difference between revisions

Revision as of 13:22, 17 February 2023

Revision as of 13:29, 17 February 2023

Line 454:

|style="text-align:right;"|infinite

|style="text-align:right;"|<ref>{{cite arXiv | author = CDA Evans and Joel David Hamkins | title = Transfinite game values in infinite chess | year = 2014| class = math.LO | eprint = 1302.4377 }}</ref>

|{{Unknown}}, but mate-in-n is decidable<ref name="Brumleve2012">{{cite journal | author = Stefan Reisch, Joel David Hamkins, and Phillipp Schlicht | title = The mate-in-n problem of infinite chess is decidable | journal = Conference on Computability in Europe | year = 2012 | pages = 78–88 | arxiv = 1201.5597 | url = https://arxiv.org/pdf/1201.5597.pdf}}</ref>

|-

|[[Magic: The Gathering]]

Line 462:

|style="text-align:right;"|

|style="text-align:right;"|

|style="text-align:right;"|<ref name="Churchill2020">{{cite journal | author = Alex Churchill, Stella Biderman, and Austin Herrick | title = Magic: the Gathering is Turing Complete | journal = Fun with Algorithms | year = 2020 | arxiv = 1904.09828 | url = https://arxiv.org/pdf/1904.09828.pdf}}</ref>

|AH-hard<ref name="Biderman">{{cite arXiv | author = Stella Biderman | title = Magic: the Gathering is as Hard as Arithmetic | year = 2020 | class = cs.AI | eprint = 2003.05119 <!-- | url = https://arxiv.org/pdf/2003.05119.pdf -->}}</ref>

|-