from the Next-target-for-DeepMind? dept.
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.
Magic: The Gathering is Turing Complete (arXiv:1904.09828)
The simple codebreaking game Mastermind turns 50 this year. Vice goes into some background regarding the now classical game and its heyday.
If you only know Mastermind as a well-worn and underplayed fixture of living room closets and nursing home common areas, you may have no idea just how big this thing was in its early years. Invented in 1970, Mastermind would sell 30 million copies before that decade was up, and boast a national championship at the Playboy Club, a fan in Muhammed Ali, official use by the Australian military for training, and 80% ownership amongst the population of Denmark. "I never thought a game would be invented again," marvelled the manager of a Missouri toy store in 1977. "A real classic like Monopoly."
[...] If you don't know Mastermind at all, i.e. you never lived in Denmark, it's played over a board with a codemaker who creates a sequence of four different colored pegs, and a codebreaker who must replicate that exact pattern within a certain number of tries. With each guess, the codemaker can only advise whether the codebreaker has placed a peg in its correct position, or a peg that is in the sequence but incorrectly placed. According to the game's creators, an answer in five tries is "better than average"; two or fewer is pure luck. In 1978, a British teenager, John Searjeant, dominated the Mastermind World Championship by solving a code with just three guesses in 19 seconds. (In second place was Cindy Forth, 18, of Canada; she remembers being awarded a trophy and copies of Mastermind.)
Mordechai Meirowitz, an Israeli telephone technician, developed Mastermind in 1970 from an existing game of apocryphal origin, Bulls and Cows, which used numbers instead of colored pegs. Nobody, by the way, knows where Bulls and Cows came from. Computer scientists who adapted the first known versions in the 1960s variously remembered the game to me as one hundred and one thousand years old. Whatever its age, it's clear nobody ever did as well out of Bulls and Cows as Meirowitz, who retired from game development and lived comfortably off royalties not long after selling the Mastermind prototype to Invicta, a British plastics firm expanding from industrial parts and window shutters into games and toys.
The story relates a couple of tales of intrigue related to the game.
The game originated in the early 1990s in the mind of Richard Garfield, at the time a graduate student working towards a PhD in combinatorial mathematics at the University of Pennsylvania. A life-long tabletop gamer, he had approached a publisher to pitch an idea for a game about programming robots, only to be told that the company needed something more portable and cheaper to produce.
Magic was Garfield's response, and it involved one major innovation that set it apart from any game previously released.
Magic's latest set marks a turning point for the game. Magic Origins focuses on five of the game's most popular recurring characters – a move that provides a jumping-on point for new players intimidated by over two decades' worth of accumulated storylines.
I played D&D, Gamma World, Traveller, and many RPG's avidly into college, but when I first saw Magic and its $20 price for a single card I discovered there were lines I would not cross. As an adult I have a civil engineering friend whom I've watched over the last decade and a half disappear and then emerge, going cold turkey, only to re-submerge for another year. For those who took up Magic, why did you take it up and do you still play?