Fijn dat je er bent!

Om de ervaring op onze website zo magisch mogelijk te maken voor je, gebruiken we cookies. Deze worden ingezet voor digitale veiligheid en om onze advertenties te verbeteren.

Magic is ingewikkeld!

MagnusMagicus
4 jaren geleden
Awesome! Wat zijn we toch slim met z'n allen
TheRobinros
4 jaren geleden
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
 bijgewerkt door TheRobinros 4 jaren geleden
bartist
4 jaren geleden
Quote:
57 minuten geleden
..... 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...


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
 bijgewerkt door bartist 4 jaren geleden
TheRobinros
4 jaren geleden
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!
bartist
4 jaren geleden
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)
 bijgewerkt door bartist 4 jaren geleden
TheRobinros
4 jaren geleden
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
 bijgewerkt door TheRobinros 4 jaren geleden
bartist
4 jaren geleden
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
Sunitram
4 jaren geleden
Quote:
31 minuten geleden
Was het niet al lang duidelijk dat MtG minstens $0^{(\omega)}$ is?


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
bartist
4 jaren geleden
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.
Dordledum
4 jaren geleden
Dit draadje is als alpha-nerd inmiddels niet meer te volgen.
bartist
4 jaren geleden
Ow, jammer heb nog zo mn best gedaan om het voor iedereen begrijpbaar te houden
BluezamX
4 jaren geleden
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.
Mango
4 jaren geleden
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.
 bijgewerkt door Mango 4 jaren geleden
TheRobinros
4 jaren geleden
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.
 bijgewerkt door TheRobinros 4 jaren geleden
Mango
4 jaren geleden
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.
 bijgewerkt door Mango 4 jaren geleden
TheRobinros
4 jaren geleden
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
Mango
4 jaren geleden
Ja, het artikel is interessant genoeg om er hier op dit forum over te discussieren.
MagnusMagicus
4 jaren geleden
Absoluut mee eens! Ik heb wel een technische achtergrond, maar ik volg maar de helft van de duscussie, maar vindt het wel erg interessant
Mango
4 jaren geleden
De auteurs construeren een speciale Magic toestand die gekoppeld kan worden aan de werking van een door Rogozhin in de vakliteratuur beschreven Universele Turing Machine, namelijk de (2, 18 ) UTM. Afhankelijk van de begin-condities kan de UTM stoppen (overwinning voor speler A), of hij kan niet stoppen (remise, vanwege een oneindige loop). De auteurs concluderen hieruit dat Magic minstens zo complex is als het Halting probleem.

Deze conclusie gaat mij te ver. Je kunt deze analyse immers ook toepassen op allerlei aanzienlijk eenvoudiger spelen. Neem Rock, Paper, Scissors. De regels zijn als volgt. Spelers A en B kiezen tegelijkertijd R, P of S. Nu geldt: P wint van R, R wint van S, S wint van P. Indien de spelers dezelfde keuze maken is er geen score.

Ik organiseer een RPS computer toernooi. Er strijden steeds twee programma's (A en B) tegen elkaar. Wie het eerst 100 punten heeft gescoord, wint de partij. Beide computer programma's mogen initiele parameters gebruiken maar ook letten op het spelverloop (laatste X zetten bijhouden). Nu bouw ik een Turing Machine (d.w.z. een overkoepelend computer programma) die de zetten van spelers A en B berekent en uitvoert, en de overall score bijhoudt. Het kan zijn dat A uiteindelijk wint met zeg 100 - 91, of B wint, maar dat is aan de computer codes en de initiele parameters van de twee programma's niet zomaar af te lezen. Daarnaast is het mogelijk dat op een gegeven in de partij de twee programma's dezelfde zetten beginnen uit te voeren: PP, RR, RR, RR, SS, PP, SS, RR..... Die string zou in principe oneindig lang kunnen zijn (niet ondenkbaar wanneer twee versies van hetzelfde programma A tegen elkaar spelen). Als dat zo zou zijn, haalt geen van de spelers de 100 punten en is de partij onbeslist. Het is niet a priori te bepalen of de partij tussen A en B hiermee te maken krijgt. Dus heb je hier ook een Halting Probleem.

Betekent dit nu dat Rock, Paper, Scissors een complex spel is? Nee, de complexiteit schuilt in de onbeperkte strategische mogelijkheden van de twee programma's.
 bijgewerkt door Mango 4 jaren geleden
TheRobinros
4 jaren geleden
Het verschil zit hem in de onberekenbaarheid van RPS. Als twee spelers dit spel spelen, kan je nooit van een van beiden zeggen wat zijn volgende zet zou zijn. Dat is zijn strategie en hoe vaak je hem bekijkt, de speler kan zelf altijd besluiten iets anders te doen... Dat is waarom RPS werkt. Als je namelijk exact zou kunnen voorspellen wat je tegenstander doet, zou je altijd kunnen winnen. En dat kan je tegenstander ook. Dus wint iedereen ieder spel RPS en dat kan niet.

Een computer, of algemener een UTM, kan je wél voorspellen. Deze maakt, aan de hand van zijn programma, wat berekeningen en zegt dan wat hij gaat doen. Maar dit zal, met dezelfde input, altijd dezelfde output zijn.

Stel je voor dat je een computer hebt, genaamd "Pieter", die zo gebouwd is dat hij altijd een som voor je uitrekent. Geef Pieter de som 37+5, hij gaat rekenen, en geeft je 42. Pieter doet het perfect en maakt nooit fouten. En een andere computer, genaamd "Henk", die een stelling van een schaakbord als input heeft en altijd de beste zet voor wit geeft, en het ook nooit fout heeft. Henk kan perfect uitrekenen wat wit moet doen met schaken, en Pieter kan perfect rekenen.
Maar als je Henk de som 37+5 geeft, zal Henk vast lopen. En vice versa, Peter zal vastlopen als je hem het Siciliaans voorschotelt. Nu is de vraag: bestaat er een computer die twee inputs nodig heeft: namelijk een "blauwdruk van een computer" en een input, die perfect kan uitrekenen of de computer van zijn blauwdruk de input kan verwerken, of dat hij vastloopt? Stel, zo'n computer kan je bouwen. Noem deze computer dan even "Jan". Dus als je Jan de computer Pieter en de input 37+5 geeft, zal Jan zeggen "Ja hoor, dat lukt hem wel!" En Jan zal ook zeggen "Nope, die loopt vast!" als je hem Pieter en het Siciliaans geeft. Jan doet dat perfect en kan het met alle computers... Dus kunnen we een computer maken die precies hetzelfde als Jan doet, maar aan het einde vastloopt als Jan zegt "Ja hoor" en "Ja hoor" zegt als Jan "Nope" zegt. Die noemen we wel Klaas. Dus Klaas loopt vast als we hem Henk en een schaakbord geven, maar zegt "Ja hoor" als je Henk en een rekensom geeft.

Stel, we geven Klaas een blauwdruk van zichzelf, twee keer. Wat komt er dan uit? Klaas kan ofwel "Ja hoor" zeggen, of vastlopen. Aangezien Jan perfect is, kan Jan dit uitrekenen. Als Klaas vastloopt, zegt Jan "Nope". Maar dan zegt Klaas "Ja hoor" en had Jan het dus fout. En andersom, als Klaas "Ja hoor" zou zeggen, zou Jan zeggen dat het Klaas wel lukt, en dus loopt Jan weer vast. Dus Jan heeft het hoe dan ook fout.

Oftewel: er is een computer en een input waarvan Jan niet kan zeggen of het lukt voor die computer om het uit te rekenen. Maar Jan werkte perfect, dus kan Jan niet bestaan. Dus er is geen computer die uit kan rekenen of een bepaalde computer vast loopt op een bepaalde input, of niet. Dat is het Halting Problem: je kan geen algoritme geven wat voor je uitrekent of je computer vastloopt of niet.

De computer die je nu maakt bestaat uit anders gehackte Xathrid Necromancers en Rotlung Reanimators en de input is een bepaalde hoeveelheid groene en witte tokens die respectievelijk 3/3, 4/4, 5/5, etc. zijn en bepaalde creature types hebben. Er is hier geen "vrije wil": de spelregels van Magic bepalen exact hoe de rest van het spel gaat verlopen (wat dus anders is dan RPS). De computer doet een hele hoop rekenwerk met als output ofwel "ik win het spel" ofwel een oneindige loop, waardoor hij vast loopt. Er is geen manier om uit te rekenen welke van de twee gaat gebeuren, want anders konden we daar wel een computer van bouwen en had je eigenlijk laten zien dat Jan wél bestaat. Dus de judge kan niet bepalen wie er wint, of dat het een gelijkspel is omdat we allebei de boardstate niet kunnen veranderen, dat zou namelijk betekenen dat de judge uit kan rekenen wat een computer níet kan, en dan zouden we gewoon de hersenen van een judge in de computers stoppen. Dus is Magic minstens net zo moeilijk als het Halting Problem, want je kan niet bepalen wat er in een compleet geforceerd spel Magic gebeurt als je het Halting Problem niet op kan lossen.
Om te posten dien je eerst in te loggen.
Info
  • 23 posts
  • Laatste post TheRobinros 4 jaren geleden
  • Gemaakt door n4ppy 4 jaren geleden
iDeal Riverty Bancontact Sofort Mastercard Visa PayPal DPD PostNL
Top