Accomplishments and Records

The World’s Most Complex Game is Too Complicated for a Computer

Magic the Gathering most-complex game

If you are one of those people who have difficulty remembering the rules for games, you may wish to avoid Magic. It has been classified as the most complex game in existence. This is not merely someone’s opinion; it has been backed up by a scientific study.

Prior to the 1993 release of Magic, one might consider Fizzbin to be the holder of this dubious honor. A potential disqualification, however, might lie in the fact that Fizzbin is entirely made up.

Fans of Star Trek will recall that Captain Kirk created Fizzbin so he, Spock, and McCoy could escape captivity at the hands of people who revered and mimicked 20th-century earth gangsters. (Star Trek, “A Piece of the Action,” 1968).

Fizzbin’s rules, as explained by Kirk, are as follows:

  • The game can be played with a standard Earth deck of cards, despite the slightly differing deck on Beta Antares IV.
  • How many players can take part is not specified, but four is apparently the usual number.
  • Judging from the way Kirk dealt the cards, dealing always progresses clockwise.
  • Each player gets six cards, except for the player on the dealer’s right, who gets seven.
  • The second card is turned up, except on Tuesdays.
  • Two jacks are a “half-fizzbin.”
  • If you have a half-fizzbin:
    • a third jack is a “sralk” and results in disqualification;
    • one wants a king and a deuce, except at night, when one wants a queen and a four;
    • if a king had been dealt, the player would get another card, except when it is dark, in which case he would have to forfeit that card.
  • The top hand is a “royal fizzbin,” but the odds against getting one are said to be “astronomical.” Spock admitted, “I’ve never computed them.”

Of course, the game was a hoax, and Kirk used the needlessly-complex rules to befuddle the captors so the Enterprise officers could make their getaway. You can see the scene here:

Although Fizzbin is complicated enough to cause brain cramps to people in the 23rd century, compared to Magic, it is about as simple as Tic-Tac-Toe. Magic: The Gathering is a card game created by Richard Garfield. Over 20 billion Magic cards were produced in the years 2008 to 2018.

The game has developed somewhat since its initial release. There are over 20,000 unique cards and more than 2,000 rules. The complexity created by the game structure is so great that researchers have concluded that a computer would be unable to figure out the winner.

The researchers, Alex Churchill, Stella Biderman, and Austin Herrick, published their findings, “Magic: The Gathering is Turing Complete,” in April 2019. They tested the game on a computational level by encoding it so a computer can play it. They concluded that there are so many non-trivial decisions that players must make during a game that an algorithm is not capable of determining the perfect strategy.

“This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” the paper concludes. “In addition to showing that optimal strategic play in Magic is non-computable, it also shows that merely evaluating the deterministic consequences of past moves in Magic is non-computable.”

In a game of chess, the number of possible moves is vast (a typical game can have as many as 10123 — that’s 1, followed by 123 zeros — possible moves), but it is a number that can be calculated by a computer. Magic, is different, as the paper states: “The full complexity of optimal strategic play remains an open question, as do many other computational aspects of Magic. For example, a player appears to have infinitely many moves available to them from some board states of Magic.”

The implications of this study impact the way programmers approach artificial intelligence and the way game theory is applied to real-world situations.

Recognizing the training value, the Central Intelligence Agency (CIA) developed its own version of a Magic game called “Collection Deck.” The rules, as shown in documents released under the Freedom of Information Act, require players to use their cards to affect or counter those of competing players. Collection Manager Challenge cards require an explanation of how a particular technique could be used to address real-world issues. Additionally, Reality Check cards were “used to modify a technique or problem to create matches that would otherwise not be possible.”

Read more fun facts about games.

Read more fun facts about extreme numbers.

4 replies »

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.