マジック：ザ・ギャザリングは、魔法使いが呪文を唱えたり、モンスターなどのクリーチャーを呼び出したり、魔法のオブジェクトを使って相手を倒したりするカードゲームだ。
このゲームでは、それぞれ異なるパワーを持つ60枚のカードのデッキを、2人以上のプレイヤーが組み立てる。プレイヤーは、ゲームの進化とともに作られていった約2万種類のカードからカードを選んでデッキを構成する。ダンジョンズ＆ドラゴンズなどのロールプレイング・ファンタジーゲームに似ているが、他のカードゲームよりもはるかに多くのカードを使って、より複雑なルールに従わなければならない。
こうした事情が提起する興味深い問題がある。それは、（通常ゲーム理論家が考える仮想的なゲームとは対照的に、人々が実際にプレイする）現実世界のゲームの中で、マジック：ザ・ギャザリングの複雑さはどの程度なのだろうかという疑問だ。
英国ケンブリッジの独立研究者でありボードゲームデザイナーのアレックス・チャーチル、ジョージア工科大学のステラ・ビダーマン、ペンシルベニア大学のオースティン・ヘリックスらの研究のおかげで、1つの答えが得られている。
チャーチルらのチームは、マジック：ザ・ギャザリングをコンピューターやチューリングマシンでプレイできるようにエンコードして、ゲームの計算上の複雑さを初めて測定した。その結果、「文献で知られている、計算上もっとも複雑な現実世界のゲームが、マジック：ザ・ギャザリングであることを証明できました」と述べている。
いくつかの予備知識を説明しておこう。コンピューター科学における重要な作業は、ある問題が原理的に解決できるかどうかを判断することだ。たとえば、2つの数が互いに素であるかどうか（言い換えると、その2つの数の最大公約数が1より大きいかどうか）を判断するのは、明確に定義された有限回のステップで実行できる作業であり、つまり計算可能である。
通常のチェスのゲームで、白に勝利できる戦略があるかどうかを決定するのも計算可能だ。このプロセスに含まれるのは、考えられる一連の動きをすべてテストし、白が勝てるかどうか判断する作業であ …