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

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

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

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

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

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

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

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

人気の記事ランキング

1. This scientist rewarmed and studied pieces of his friend’s cryopreserved brain 10年冷凍保存の脳は「驚くほど良好」——蘇生は「まったく別の話」
2. Future AI chips could be built on glass AIチップの熱問題、解決策は「ガラス」　年内に商業生産へ
3. What do new nuclear reactors mean for waste? 新型原子炉が続々登場、核廃棄物管理の「手引き」は書き直せるか
4. The Pentagon is planning for AI companies to train on classified data, defense official says 【独自】米国防総省、軍事機密データでAIモデルの訓練を計画