Computers kom je soms op vreemde plaatsen tegen. Om iets te besturen of te berekenen heb je niet altijd elektronica nodig. Zo zijn sommige spellen complex genoeg om er een machine mee te bouwen. Als er maar genoeg spelregels in zitten om mee te werken en om te manipuleren. Wat betekent het nu eigenlijk om Turing-complete te zijn? Hoe kan je binnenin een kaartspel als het ware een computer creëren?
De Turing-machine is een wiskundig rekenmodel, dat een abstracte machine beschrijft die symbolen op een strook tape manipuleert volgens een tabel met regels. Ondanks de eenvoud van het model is het in staat om elk computeralgoritme te implementeren.
De machine werkt op een oneindige rol tape met afzonderlijke cellen. Elke cel kan één enkel symbool bevatten dat is afgeleid van een vaste (eindige) reeks symbolen. Dit is als het ware het alfabet van de machine. De machine heeft een kop die bij elke stap van de werking van de machine boven een cel wordt geplaatst. Bij elke stap leest de kop het symbool in zijn cel. Vervolgens schrijft de machine op basis van het symbool en de huidige toestand van de machine een ander symbool in de plaats en beweegt de kop een stap naar links of rechts. De verandering van symbool en de verplaatsing links of rechts is gebaseerd op een eindige tabel die specificeert wat te doen voor elke combinatie.
Om een Turing machine en een game Magic te maken hebben we 3 zaken nodig: De oneindig lange tape, de controller die bepaalt welke actie te nemen op basis van de huidige toestand en de kop om de cellen te manipuleren.
Tape: Aangezien de regels van Magic geen vormen definiëren binnen het spel, moeten we een creatieve oplossing bedenken voor de tape. Hiervoor gaan we creature tokens gebruiken met een specifieke sterkte en kleur. De sterkte zal bepalen waar de kop staat, hoe groter de sterkte hoe verder weg van de kop. Links van de kop zijn de creature tokens groen, rechts wit. Voor de verschillende symbolen zullen we verwijzen naar 18 verschillende creatures (Aetherborn, Basilisk,….)
Controller: Zoals eerder al aangehaald, baseert een Turing machine zijn acties op de huidige toestand en een eindige tabel die specificeert wat te doen bij elke combinatie. In Magic zijn er vele kaarten die een effect hebben in de vorm: “als X doe dan Y”. We maken gebruik van een Rotlung Reanimator (RR) en Xathrid Necromancer (XN) (Wanneer RR (of XN) dood gaat, maak een zwarte zombie met sterkte 2). De kaart Artificial Evolution en Glamerdye laten ons de kleur en het creature aanpassen naar wat we willen. Er worden verschillende kopieën gemaakt van RR en XN die vervolgens ook worden aangepast.
De kop: We maken gebruik van kaarten als Infest en Cleansing Beam om de tape te beïnvloeden. In het spel Magic zal dit leiden tot het doodgaan van 1 groene of witte creature token met sterkte 2. Eén specifieke RR of XN zal dit zien gebeuren en in de plaats een nieuwe groen of witte creature token maken alsook de kop die zal opschuiven naar links of rechts.
Nu de 3 hoofdcomponenten aanwezig zijn, dient de laatste stap te worden gezet. In een klassieke game Magic speel je tegen elkaar, we gaan er dus voor zorgen dat beide spelers het spel niet kunnen winnen noch verliezen. De acties die spelers kunnen maken zullen allemaal geforceerd worden door veel specifieke kaarten te spelen die dit mogelijk maken.
De Turing machine zal nu over verschillende beurten een cel kunnen lezen, deze aanpassen en de kop opschuiven naar links of rechts op de tape.
Er zijn zoveel kaarten die gebruikt worden en zoveel nuances binnen de regels van het spel Magic dat ik ze niet allemaal heb genoemd in dit artikel. Hier wel de link naar de paper, die alles tot in detail beschrijft:
https://www.researchgate.net/publication/332590574_Magic_The_Gathering_is_Turing_Complete
Wil je de Turing machine die hier beschreven wordt in actie zien, is hier ook een leuke video uitgelegd door Kyle Hill: https://www.youtube.com/watch?v=pdmODVYPDLA&t=1227s
0 reacties