Cookie Notice

An image of packages of Magic: The Gathering playing cards
Nathan Rupert

Computing

“Magic: The Gathering” is officially the world’s most complex game

A new proof with important implications for game theory shows that no algorithm can possibly determine the winner.

by Emerging Technology from the arXiv
May 7, 2019
An image of packages of Magic: The Gathering playing cards

Magic: The Gathering is a card game in which wizards cast spells, summon creatures, and exploit magic objects to defeat their opponents.

In the game, two or more players each assemble a deck of 60 cards with varying powers. They choose these decks from a pool of some 20,000 cards created as the game evolved. Though similar to role-playing fantasy games such as Dungeons and Dragons, it has significantly more cards and more complex rules than other card games.

And that raises an interesting question: among real-world games (those that people actually play, as opposed to the hypothetical ones game theorists usually consider), where does Magic fall in complexity?

Today we get an answer thanks to the work of Alex Churchill, an independent researcher and  board game designer in Cambridge, UK; Stella Biderman at the Georgia Institute of Technology; and Austin Herrick at the University of Pennsylvania.

His team has measured the computational complexity of the game for the first time by encoding it in a way that can be played by a computer or Turing machine. “This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” they say.

First, some background. An important task in computer science is to determine whether a problem can be solved in principle. For example, deciding whether two numbers are relatively prime (in other words , whether their largest common divisor is greater than 1) is a task that can be done in a finite number of well-defined steps and so is computable.

In an ordinary game of chess, deciding whether white has a winning strategy is also computable. The process involves testing every possible sequence of moves to see whether white can force a win.

But while both these problems are computable, the resources required to solve them are vastly different.

This is where the notion of computational complexity comes in. This is a ranking based on the resources required to solve the problems.

In this case, deciding whether two numbers are relatively prime can be solved in a number of steps that is proportional to a polynomial function of the input numbers. If the input is x, the most important term in a polynomial function is of the form Cxn, where C and n are constants.  This falls into a class known as P, where P stands for polynomial time.

By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. If the input is x, the most important term in an exponential function is of the form Cnx, where C and n are constants. And as x increases, this becomes bigger much faster than Cxn. So this falls into a category of greater complexity called EXP, or exponential time.

Beyond this, there are various other categories of varying complexity, and even problems for which there are no algorithms to solve them. These are called non-computable.

Working out which complexity class games fall into is a tricky business. Most real-world games have finite limits on their complexity, such as the size of a game board. And this makes many of them trivial from a complexity point of view. “Most research in algorithmic game theory of real-world games has primarily looked at generalisations of commonly played games rather than the real-world versions of the games,” say Churchill and co.

So only a few real-world games are known to have non-trivial complexity. These include Dots-and-Boxes, Jenga, and Tetris. “We believe that no real-world game is known to be harder than NP previous to this work,” says Churchill and co.

The new work shows that Magic: the Gathering is significantly more complex. The method is straightforward in principle. Churchill and co begin by translating the powers and properties of each card into a set of steps that can be encoded.

They then play out a game between two players in which the play unfolds in a Turing machine.  And finally they show that determining whether one player has a winning strategy is equivalent to the famous halting problem in computer science.

This is the problem of deciding whether a computer program with a specific input will finish running or continue forever. In 1936, Alan Turing proved that no algorithm can determine the answer. In other words, the problem is non-computable.

So Churchill and co’s key result is that determining the outcome of a game of Magic is non-computable. “This is the first result showing that there exists a real-world game for which determining the winning strategy is non-computable,” they say.

That’s interesting work that raises important foundational questions for game theory. For example, Churchill and co say the leading formal theory of games assumes that any game must be computable. “Magic: The Gathering does not fit assumptions commonly made by computer scientists while modelling games,” they say.

That suggests computer scientists need to rethink their ideas about games, particularly if they hope to produce a unified computational theory of games. Clearly, Magic represents a fly in the enchanted ointment as far as this is concerned.

Ref: arxiv.org/abs/1904.09828 : Magic: The Gathering Is Turing Complete

×

You've read 1/3 of your free monthly feature stories. Subscribe for unlimited access.

Subscribe nowSign in

Green New Deal

The economic argument behind the Green New Deal

Economist Mariana Mazzucato explains how it's about much more than renewable energy.

01.
Let’s keep the Green New Deal grounded in science
Everything we know from recent research indicates that nuclear, carbon capture, and hydropower are essential to curbing climate change.
02.
The Green New Deal has been released. Here are four key tech takeaways
The proposal is ambitious, wide-ranging, and somewhat pragmatic about technology’s role. But whether it will ever see the light of day is unclear.
03.
Conservative climate groups hope to seize the Green New Deal moment too
But is there a conservative approach that can really work at this stage?

Computing

New security flaws have been found in Intel chips—this is what you need to do right now

The four new vulnerabilities, uncovered by cybersecurity researchers, affect almost every chip the firm has made since 2011....

The news: Intel and a group of security researchers from universities and security firms around the world have revealed four security flaws similar to the Spectre and Meltdown security holes uncovered last year that affected billions of chips. There’s no evidence (yet) that the latest set of vulnerabilities have been exploited by hackers, but they could be used to pilfer all kinds of sensitive data.

The Not-So-Fab Four: The flaws make it possible to target computers’ central processing units, or CPUs. These are the “brains” of the machines, orchestrating their other functions. To speed things up, CPUs use a process known as “speculative execution”, which means they try to guess ahead of time the processes they will be asked to run and the data needed.

Like Spectre and Meltdown, the new security holes can be used to compromise CPUs engaged in this guesswork. One called ZombieLoad could let intruders steal information from applications and cloud-based systems. Another called Rogue In-Flight Data Load could manipulate chips’ memories in ways that expose sensitive information. The two other flaws, dubbed Fallout and Store-to-leak-forwarding, could be exploited to steal data or compromise operating systems. (If you want to check whether your computers are at risk or get more details about the flaws, you can use an online tool made available by the researchers here.)

What you should do: The best fix would be to rip out all the chips and replace them—but that would be prohibitively expensive. The next best fix is to apply software patches developed by Intel and others. Amazon, Apple and Google have already released patches—so make sure you are updated to the latest version. Apple says iPhones, iPads and Watches are not affected. Some security researchers also recommend disabling hyper-threading, an Intel feature that lets certain core tasks to run in parallel on its chips to boost processing speed. 

The disclosure debate: This new chipocalypse will rekindle the debate over how and when hardware vulnerabilities should be disclosed to the public. Intel has said it discovered the flaws a year ago, but it needed time to work out disclosure plans and to develop patches. However, that means many customers have only just discovered their machines were more vulnerable to hacking than they thought.

Link
Author

Martin GilesI am the San Francisco bureau chief of MIT Technology Review, where I cover the future of computing and the companies in Silicon Valley that are shaping it. Before joining the publication, I led research and publishing at a venture capital firm focused on business technology. Prior to that, I worked for The Economist for many years as a reporter and editor, most recently as the paper’s West Coast-based tech writer.

ImageAP

Expand

Blockchain

You can now pay with cryptocurrency at Whole Foods

Cameron and Tyler Winklevoss want you to pay for groceries, movies, ice cream, and many other everyday retail products using cryptocurrency. ...

The news: The twins’ digital currency company, called Gemini, has formed a new partnership with payments startup Flexa to incorporate crypto-payment capabilities into the scanners that let you pay with services like Apple Pay.

Users can now use an app called Spedn to pay with Bitcoin, Bitcoin Cash, Ether, or Gemini’s dollar-backed stablecoin called the Gemini dollar for items at retailers including Whole Foods, Regal Cinemas, Baskin-Robbins, Starbucks, and others, according to Fortune.

Will crypto-payments stick this time? The cryptocurrency industry has wanted to achieve mainstream adoption in retail for ages. A number of merchants tried to accept Bitcoin payments in the past, but it was probably too early: paying with crypto had yet to take off, and many retailers stopped taking it. In many cases that’s probably been down to price volatility and slow processing times.

Speed merchant: In this case, Flexa will serve as a bridge between merchants and the blockchain, and will settle the payments in real time using its own network. Merchants can choose to take the payment in either cryptocurrency or dollars. According to Gemini, processing payments like this will be cheaper than using credit card networks.

Hush hush: But all six merchants Fortune asked about the project refused to comment, and one person familiar with the project stated anonymously it is “experimental.” They said that participating retailers don’t want to discuss the project until they learn more about whether and how people will use it.

Keep up with the fast-moving and sometimes baffling world of cryptocurrencies and blockchains with our twice-weekly newsletter Chain Letter. Subscribe here. It’s free!

Link
TaggedBitcoin, Cryptocurrency
Author

Mike OrcuttI’m an associate editor at MIT Technology Review, focusing on the world of cryptocurrencies and blockchains. My reporting, which includes a twice-weekly, blockchain-focused email newsletter, Chain Letter (sign up here), revolves around one central question: Why does blockchain technology matter?

Expand

Climate Change

The deepest-ever dive to the bottom of the Mariana Trench found litter there

The dive to the ocean's deepest point turned up some surprises....

The news: During a four-hour exploration of the Mariana Trench, retired naval officer Victor Vescovo piloted his submarine to 10,927 meters (35,849 feet) below the sea’s surface, making it the deepest dive on record. He spent four hours at the bottom. The Mariana Trench is in the Pacific Ocean, east of the Philippines and south of Japan.

Epic trip: The Mariana Trench dive is part of a series of dives known as the Five Deeps Expedition: an attempt to visit the deepest point in each of the world’s five oceans. Vescovo, who is funding the mission himself, has already completed dives in the Indian, Atlantic, and Southern Oceans. He is aiming to tackle the Arctic’s deepest point—known as Molloy Deep— in August this year.

Super-sub: The submarine, named DSV Limiting Factor, is 15 feet long and 9 feet wide. It has a titanium hull that is 3.5 inches thick and able to withstand the incredible pressures at the ocean floor. It is built to dive for 16 hours at a time—but also has emergency air supplies for a further 96 hours.

Record-breaker: Don Walsh and Jacques Piccard first reached the deepest part of the Mariana Trench, Challenger Deep, in 1960 in a US Navy bathyscape called Trieste. Walsh was on board the ship that accompanied this latest attempt. Vescovo's Five Deeps team estimate that he went around 50 feet deeper than the Trieste. Film director James Cameron also reached the bottom in 2012. 

Unwelcome find: While Vescovo potentially discovered four new species, he also found a plastic bag and candy wrappers. It’s not the first time plastic has been found at the bottom of the sea, but it’s a reminder of the scale of the problem. About 8 million tons of plastic are thrown into the ocean every year, mostly washed into the sea by rivers. There will be more plastic than fish in the sea by 2050 if current trends continue, according to the United Nations.

Sign up here to our daily newsletter The Download to get your dose of the latest must-read news from the world of emerging tech.

Link
Author

Charlotte JeeI write The Download, the only newsletter in tech you need to read every day. Before joining MIT Technology Review I was editor of Techworld. Prior to that I was a reporter covering the intersection of politics, the public sector and technology. In my spare time I run a venture called Jeneo aimed at making tech events more inclusive. I regularly do public speaking and crop up on the BBC from time to time. Sign up for The Download here.

ImageTamara Stubbs

Expand

Silicon Valley

A WhatsApp security flaw let hackers install spying software via voice calls

The vulnerability was fixed on Friday, but it’s a blow to a company that prides itself on providing secure communications to its 1.5 billion users, using end-to-end encryption....

The details: The security hole let an attacker read messages on the target’s device. It used WhatsApp’s voice calling feature to call someone and then install surveillance software, even if the call was not picked up. The call would often disappear from the device’s call log. It was discovered earlier this month by WhatsApp’s own security team. It targeted specific users and was developed by Israeli security company NSO Group, according to the Financial Times.

Who’s behind it? Its development is likely to have been directed by a government, and the suspected attacks were targeted to specific individuals, WhatsApp said. It didn’t name any of them. 

What do I need to do? Make sure you’re using the latest version of WhatsApp. Although your phone might have auto-updated since Friday already, it’s worth checking. For Android devices, that involves opening the Google Play store and looking in “My Apps & Games” to see if WhatsApp needs updating or not. The latest version is 2.19.134. For iOS, you need to check the App Store and make sure you’re using WhatsApp version 2.19.51.

Sign up here to get your dose of the latest must-read news from the world of emerging tech in our daily newsletter The Download.

Link
Author

Charlotte JeeI write The Download, the only newsletter in tech you need to read every day. Before joining MIT Technology Review I was editor of Techworld. Prior to that I was a reporter covering the intersection of politics, the public sector and technology. In my spare time I run a venture called Jeneo aimed at making tech events more inclusive. I regularly do public speaking and crop up on the BBC from time to time. Sign up for The Download here.

ImageAssociated Press

Expand

Topics