En het is nu wetenschapelijk aangetoond

"We conjecture that optimal play in Magic is far harder than this result alone implies, and leave the true complexity of Magic and the reconciliation of Magic with existing theories of games for future research."

https://arxiv.org/abs/1904.09828

"Magic: The Gathering is a popular and famously complicated trading card game about magical combat. 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. To do this, we present a methodology for embedding an arbitrary Turing machine into a game of Magic such that the first player is guaranteed to win the game if and only if the Turing machine halts. Our result applies to how real Magic is played, can be achieved using standard-size tournament-legal decks, and does not rely on stochasticity or hidden information. Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. We conclude with a discussion of the implications for a unified computational theory of games and remarks about the playability of such a board in a tournament setting."


via https://www.technologyreview.com/s/613489/magic-the-gathering-is-officially-the-worlds-most-complex-game/

haha, maar dat wisten de meeste spelers natuurlijk wel

Een Cyclopean Mummy, die is pas ingewikkeld!

Awesome! Wat zijn we toch slim met z'n allen

Hmm, ik dacht dat ik hier een X aantal tijd geleden al een link met een Universal Turing Machine in een spel Magic had gepost, volgens mij gebeurt hier niet bijzonder veel meer. Kortom: Magic is moeilijk genoeg dat je in-game kan programmeren, en als je echt wil en (extreem veel) tijd te veel hebt, kan je een spel Magic zo opzetten dat het je vertelt hoe je een sudoku met gegeven inputs op moet lossen, of een spel opzetten dat voor je uitrekent of je de spell van je tegenstander moet counteren, gegeven jullie decklists.

Los daarvan: extreem awesome natuurlijk! Die paper ga ik zeker een keer goed lezen

Edit: Okay, dit is wat dieper dan ik dacht: Magic is blijkbaar het eerste spel dat "undecidable" is: met geforceerde zetten is er een situatie waarin het onbepaalbaar is wie er wint. Vergelijk dat met bijvoorbeeld een spel schaak: gegeven twee perfecte schakers, kan je uitrekenen hoe het spel verloopt en wie er uiteindelijk wint. Het kost tot nu toe alleen te veel rekenkracht om die vraag te kunnen beantwoorden. Er was nog niet bekend of er een spel was waarbij dit onmogelijk was, en blijkbaar is Magic zo'n spel

als ik het vak Complexiteitstheorie nog goed kan herinneren, impliceert reduceren van een sudoku probleem naar een potje MtG dat MtG NP-Compleet is, wat gelijk staat aan onbeslisbaar.
Ik had een tijd geleden wel eens papers gezocht over de complexiteit van MtG, waar ik een paper heb gelezen waarin werd bewezen dat een enkele optimale zet (gegarandeerde winst) bepalen voor 1 beurt een Co-NP compleet probleem is (of, in het nederlands: het is "efficient" te verifieren of iets niet een optimale zet is, maar niet efficient te bepalen of een zet wel optimaal is)

Ik weet trouwens hoeveel mensen complexiteitstheorie of berekenbaarheidstheorie hebben gehad, dus ik post later een kleine uitleg zodat iedereen (soort van) kan snappen waar ik het over heb

Ja, als ik mijn hoofd even gebruik voor ik iets typ, had ik dat ook wel bedacht ja... Want dat is dus exact wat het Halting Problem geeft...
Ik heb uit interesse wel wat gelezen over complexiteitstheorie en het is ook in een paar wiskunde-bachelor-vakken voorbij gekomen, maar expert ben ik er zeker niet in. Enlighten me!

Ik hoop dat ik dan niet te veel blaat, het is een hoop theorie met redelijk wat belangrijke details.

Allereest, Turingmachines. Om die niet ingewikkeld te maken ga ik het erop houden dat dit machines zijn die kunnen herkennen/beslissen of een serie van acties je naar het gewenste eindresultaat brengen.
Herkennen betekent dat de turingmachine 3 resultaten kan geven: accept (de acties brengen het gewenste resultaat), reject (het tegenovergestelde), of loop (de acties veroorzaken een infinite loop)
Bepalen betekent dat de turingmachine maar 2 resultaten kan geven: accept of reject.

Dit is al heel wat informatie, dus als voorbeeld:
- Gegeven een mono-colored deck die alleen basic land en vanilla creatures, een bepaalde openingshand en een tegenstander die alleen basic land speelt, kun je dan op beurt 5 winnen? Er is een turingmachine die dat beslist, want er is een machine te maken die voor iedere variatie van deze gegevens de acties kan bepalen zo dat het antwoord ja (accept) of nee (reject) is.
- Gegeven 2 willekeurige standard decks en 2 openingshanden, kun je winnen? Er zijn infinite loops, die wij herkennen als infinite loops omdat wij het grote plaatje kunnen zien en het gebrek aan voortgang kunnen deduceren. Een turingmachine zal echter niet kunnen bepalen of iets daadwerkelijk verplicht oneindig door gaat. Daarom is voor dat probleem slechts een machine te maken die oplossingen herkend.

Dat laatste is wat ze het Halting probleem noemen: Het is onmogelijk om een machine te maken die een een oneindige loop herkent.
Dit is eigenlijk pas stap 1 in uitleggen waarom Magic een enorm complex is, ik zal morgen meer vertellen. (ik moet ook de theorie ophalen en wil geen fouten maken)

Uhuhh, zo ver was ik. Maar dat Magic Turing-volledig is, is een aantal jaar geleden al aangetoond. De basis van de Turingmachine die in de paper beschreven wordt, was er namelijk al een tijdje, en werkend. Toegegeven, niet zo elegant als hier en niet in legale 60-kaarten Legacy-decklist-vorm waarbij je op beurt 1 het spel op zo'n manier forceert dat beide spelers geen keuzes meer kunnen maken en het enige wat er de komende paar honderd beurten gaat gebeuren een sh*tload aan triggers is, maar wat is er dan precies nieuw hier? Was het niet al lang duidelijk dat MtG minstens $0^{(\omega)}$ is?

Sorry als dit voor de leek wat moeilijk te volgen is, trouwens. Er zijn weinig dingen waar ik enthousiaster ben dan van Magic, maar wiskunde is er wel eentje

Ik zal morgen de paper in z'n diepgang uitpluizen, en dan terugkomen op je vraag. Mijn grootste zorg was dat ik geen abracadabra spreek voor de mensen die dit mogelijk interessant vinden en dit ook willen volgen (docenten gewoonte )

Er zijn namelijk nog wat haken en ogen aan de Turing machines verbonden, voordat ik kan praten over complexiteit classes, en die reductie vanaf het sudoku probleem waar we het al eerder over hadden. Maar mijn voornaamste doel is het zo verwoorden dat Joe average het ook (soort van) kan volgen

Is dit net zo'n ding als de flavortext van Niv-Mizzet, the Firemind? ^^"

Als leek gesproken kan ik het buiten dat redelijk volgen; al sta ik er wel van te kijken dat er blijkbaar zoiets is als complexiteitstheorie. Je weet dat de wetenschap ver is als men een studie kan maken van hoe moeilijk dingen zijn

Ik heb nog niet de tijd gevonden om de paper door te lezen, maar ik kan wel wat vertellen over TheRobinros het over heeft: de O-notatie.

In complexiteitstheorie wil je kunnen inschatten hoe lang het duurt om iets uit te voeren op basis van hoe groot je probleem is.
Bijvoorbeeld: voor een deck van n kaarten, hoe lang duurt het voor je 1 specifieke kaart pakt? In het slechtste geval is die kaart de laatste kaart, dus zal je dan n kaarten moeten pakken. Dit zetten we neer als O(n): in het slechtste geval moeten er n acties gedaan worden om tot een resultaat te komen.

Als je machine "efficient" is, dan kost het O(n^x) stappen om tot een antwoord te komen (waarbij x 0 of groter is). Een on-efficiente machine doet vaak O(x^n) stappen over, waarbij x 2 of groter is.
Het verschil maakt duidelijk als je echte getallen invult. Stel dat iedere stap 1 seconde kost om uit te voeren, het grote van het probleem is n=100, en x=2. Bij n^x is het 100^2 stappen dus 10000 seconden, wat bijna 3 uur is. Bij x^n dus 2^100 stappen komt dat neer op 4*10^22 jaar.

Dit draadje is als alpha-nerd inmiddels niet meer te volgen.

Ow, jammer heb nog zo mn best gedaan om het voor iedereen begrijpbaar te houden

Nooit gedacht dat ik de Big O notatie ooit nog ergens anders langs zou zien komen... Blijkt dat vak over complexiteit van code toch nog nuttig.

Ik heb gisteren de tijd genomen om het artikel gelezen. Naar mijn mening (als beta-wetenschapper) is het een zwak en rommelig artikel. De auteurs construeren een sterk vereenvoudigde Magic toestand, stellen dat het spelen hiervan overeenkomt met de werking van een Turing machine, claimen vervolgens dat de Turing machine niet zal stoppen, en concluderen daaruit dat Magic ook op het allereenvoudigste niveau (met alleen maar gedwongen zetten) onbeslist en derhalve complex is.

Het artikel beschrijft uitvoerig het grote aantal Magic kaarten dat nodig is in hun model, maar het blijft duister waarom juist deze set nodig is (je zou denken dat je hetzelfde kunt bereiken met veel minder kaarten). De claim dat de Turing machine in dit geval niet stopt, wordt niet bewezen terwijl dat toch cruciaal is. De auteurs leggen hun paradoxale resultaat, dat met alleen maar gedwongen zetten toch onduidelijk is wat de uitkomst van het spel is, niet uit aan de lezers. De auteurs gaan er ook aan voorbij dat van het spel Magic allang bekend is dat er in het spel oneindige loops mogelijk zijn. De mogelijkheid van oneindige loops bewijst dus niets over de complexiteit van het spel.

Ik heb de indruk dat het artikel geschreven is door personen zonder een academische graad in de wiskunde of computerwetenschappen. Zo is de derde auteur, Austin Herrick, een freshman (eerstejaars student). De tweede auteur (Stella Biderman) omschrijft zichzelf als part-time student computerwetenschappen die bezig is voor haar Master titel; zij is dus een undergraduate student. De eerste auteur (Alex Chuchill) zou verbonden zijn aan de universiteit van Cambridge (UK) als "independent researcher" (kennelijk iemand zonder officiele functie en zonder salaris); een Google search leverde mij geen resultaten op.

Ik ben het eens dat het niveau van het artikel wat te wensen overlaat, maar niet om de redenen die je hier noemt. Het beschrijven van een universele Turing Machine ís genoeg om de geclaimde resultaten aan te tonen. Zoek eens op het Halting Problem. Je kan de TM programmeren zoals je wil, door de Rotlung Reanimators en Xathrid Necromancers andere tokens te laten maken. Nu is de vraag: kan je met een gegeven vast programma en een gegeven input bepalen of het programma ooit afloopt? Oftewel: kan je bepalen of speler A wint? Het blijkt dat dit uitrekenen, op de makkelijke gevallen na, niet sneller kan dan het gewoon doen... Wat een probleem is als je programma niet termineert. Dát is het Halting Problem, en dat is dus na te bootsen in een spel MtG. Je kan dus een boardstate opbouwen waarvan het voor de judge onmogelijk is om uit te rekenen of je wint of dat de game een draw is, anders dan het spel laten lopen tot het afgelopen is (wat dus niet per se hoeft te gebeuren). En dat is, like, best wel een soort van probleem.

Wat ik net beschreef wordt als "common knowledge" beschouwt binnen complexiteitstheorie en dat claimen is niet iets wat je echt hoeft te verdedigen. En dit is dus een redelijk basaal spel Magic, waarin beide spelers alleen maar geforceerde zetten kunnen doen (als in: ze hebben geen keuze anders dan hun sideboard bekijken en conceden), waarin de situatie voor kan komen dat de judge niet kan bepalen dat je combo infinite is en het spel dus een draw. De conclusie die de schrijvers van het artikel claimen is dus compleet gerechtvaardigd.

Ik waarschuw nog maar even. Dit is geen serieus wetenschappelijk artikel. Daarvoor is het veel te slecht geschreven. Je kunt het ook zien door naar de verantwoording te kijken. Normaal gesproken staat er dan (in het geval van studenten) dat het om een afstudeerscriptie gaat. En dan staat er ook de naam van de studiebegeleider bij. Dat moet iemand zijn met PhD in Computer Science. Als het gaat om een artikel van een promovendus, staat er in de VS meestal ook de grant (financiele ondersteuning) bij. Maar al deze informatie ontbreekt.

Kennelijk gaat het hier om een hobby-project van een ex-student of een werkeloze afgestudeerde (Alex Churchill uit de UK) in samenwerking met twee undergraduate studenten uit de VS. Voor online Publisher "Arxiv" maakt dat niet uit. Die publiceren alles, hoe zwak het artikel ook is.

En daar ben ik het volledig mee eens. Het artikel is niet best geschreven en wat je hier noemt, is terecht. Maar inhoudelijk is er niets mis met de paper en is het zeker de discussie waard, lijkt mij

Ja, het artikel is interessant genoeg om er hier op dit forum over te discussieren.