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

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

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

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

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

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

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

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

人気の記事ランキング

1. Google’s new Project Astra could be generative AI’s killer app 世界を驚かせたグーグルの「アストラ」、生成AIのキラーアプリとなるか
2. These AI Minecraft characters did weirdly human stuff all on their own マイクラ内に「AI文明」、 1000体のエージェントが 仕事、宗教、税制まで作った
3. Google’s new Project Astra could be generative AI’s killer app 世界を驚かせたグーグルの「アストラ」、生成AIのキラーアプリとなるか
4. We saw a demo of the new AI system powering Anduril’s vision for war オープンAIと手を組んだ 防衛スタートアップが目指す 「戦争のアップデート」