「マジック：ザ・ギャザリング」は世界で最も複雑なゲームだった

マジック：ザ・ギャザリングは、魔法使いが呪文を唱えたり、モンスターなどのクリーチャーを呼び出したり、魔法のオブジェクトを使って相手を倒したりするカードゲームだ。

このゲームでは、それぞれ異なるパワーを持つ60枚のカードのデッキを、2人以上のプレイヤーが組み立てる。プレイヤーは、ゲームの進化とともに作られていった約2万種類のカードからカードを選んでデッキを構成する。ダンジョンズ＆ドラゴンズなどのロールプレイング・ファンタジーゲームに似ているが、他のカードゲームよりもはるかに多くのカードを使って、より複雑なルールに従わなければならない。

こうした事情が提起する興味深い問題がある。それは、（通常ゲーム理論家が考える仮想的なゲームとは対照的に、人々が実際にプレイする）現実世界のゲームの中で、マジック：ザ・ギャザリングの複雑さはどの程度なのだろうかという疑問だ。

英国ケンブリッジの独立研究者でありボードゲームデザイナーのアレックス・チャーチル、ジョージア工科大学のステラ・ビダーマン、ペンシルベニア大学のオースティン・ヘリックスらの研究のおかげで、1つの答えが得られている。

チャーチルらのチームは、マジック：ザ・ギャザリングをコンピューターやチューリングマシンでプレイできるようにエンコードして、ゲームの計算上の複雑さを初めて測定した。その結果、「文献で知られている、計算上もっとも複雑な現実世界のゲームが、マジック：ザ・ギャザリングであることを証明できました」と述べている。

いくつかの予備知識を説明しておこう。コンピューター科学における重要な作業は、ある問題が原理的に解決できるかどうかを判断することだ。たとえば、2つの数が互いに素であるかどうか（言い換えると、その2つの数の最大公約数が1より大きいかどうか）を判断するのは、明確に定義された有限回のステップで実行できる作業であり、つまり計算可能である。

通常のチェスのゲームで、白に勝利できる戦略があるかどうかを決定するのも計算可能だ。このプロセスに含まれるのは、考えられる一連の動きをすべてテストし、白が勝てるかどうか判断する作業であ …

人気の記事ランキング

1. Can the US battery market untangle from China? 送電網の蓄電池から中国製を締め出し、米国が払う「自立」の代償は
2. Promotion How AI could reshape Japan’s white-collar workforce 【10/6開催】AIで浮いた人材、次の一手は地方に——冨山和彦氏ら登壇
3. Donated livers can be made biologically younger 「若返る」提供肝臓、機械灌流が生物学的年齢を逆戻りさせる
4. Meet a mouse whose brain cortex is made up of human cells 脳容積の半分がヒト細胞に、スタンフォード大が作った「異種皮質マウス」
5. This geneticist’s age-reversal tech could help restore sight 失明マウスの視力回復に成功、若返りブームの震源となった研究者