Magic: The Gatheringのルールが本質的に不完全であることの証明

トレーディングカードゲームMagic: The Gatheringは極めて洗練されたルールを持っていますが、それでも本質的に解決できない問題があります。無限ループの停止性問題です。

無限ループ

Magic: The Gatheringではカード同士の効果によって無限に何かが起き続ける事があります。そうするともはやどちらのプレイヤーも何もできなくなってしまい、ゲームを進めることができなくなってしまうため、無限ループが起きてしまったゲームは引き分けとなるルールになっています。だれも苗木トークンを生成し続ける作業で一生を終えたくないでしょう。

問題は、無限ループが起きてしまったかどうかをどうやって判定するかです。リンク先にあるようなかんたんな例では無限ループが起きたことはかんたんにわかりますが、複雑な場合でもちゃんと判定できるきちんとした方法はあるのでしょうか？

停止性問題

およそ80年前、高名なゲイセクシャルの数学者アラン・チューリングは、プログラムが（無限ループせずに）停止するかどうか判定するプログラムはないということを証明しました。

ここで言っているのは、「かんたんな無限ループなら無限ループだと判定することは可能だが、無限ループの質によっては判定は難しくなり、場合によっては不可能になる」という意味です。データが0→1→0→1→0→1と繰り返す無限ループならかんたんに判定できるでしょうが（将棋では4回繰り返すと千日手とみなすそうです）、円周率の計算をしていたら周期的なパターンで無限ループだと気づく事はできません。データがどんどん増えていくからです。

円周率ならデータが増えていく一方なのでまだわかりやすい方です。しかし複雑怪奇でどこへ向かっているのかさっぱりわからない無限ループというのもあるのです。もう少しで処理が終わるかも？と思っていたら実は終わらずに続いていったり、無限ループだと思っていたら実は処理が終わるということもありえます。無限ループかどうかをきちんと判定するのは不可能なのです。一つだけ判定する方法があるとすれば、それはそのプログラムをじっさいに実行して、無限の時間だけ待ってやることです。これは事実上不可能です。

チューリングはこのことを証明しました。厳密に言うと細かい問題点（そのほとんどは日常生活で見かけることはまずない現象や数学的な概念）があるので、証明したことになっているといったほうがいいのですが、細かいことをいい出したらキリがないですし、実用上は問題ないので、ここでは彼の証明が正しいとして話をすすめていきましょう。彼の証明は、もし判定するプログラムがあったとすると、矛盾が生じることを示すものでした。

仮に無限ループが起きるか判定するプログラムがあったとしましょう。そのようなプログラムは、別のプログラムを実行することなしに、そのプログラムの未来を予言することができます。一種のタイムマシンのようなものです。ここであまのじゃくな誰かが次のようなプログラムを書いたとしたらどうでしょう：

「自分が停止すると予言されたら無限ループを初めて、自分が無限ループすると予言されたら停止する」

こんなひどい話があるでしょうか！こんなことをされては予言は外れるに決まっています！無限ループかどうかを事前に判定するのは必ず不可能になってしまいます。ばかうけで有名なSF映画「メッセージ」の原作にもこんな記述がありましたね。

この場合はあまのじゃくプログラマの悪意がひしひしと感じられますが、そうでなくても偶然このような構成になってしまうということはあるかもしれません。というわけで、チューリングが言ったとおり、どんなに凄い予言プログラムを書いたとしても、それを敗れるプログラムは書けてしまうのです。これは停止するか否かを確実に予言する方法はないということを意味してるようにも見えます。かんたんな無限ループならたしかに判定するプログラムは作れるのですが、どんな場合でも使えるというわけではありません。じっさいにそれを実行してやる、というのが最も確実な判定方法なのです。

Magic: The Gatheringはいかなるプログラムも実行できる

もうおわかりでしょう。Magic: The Gatheringは無限ループするなら引き分けというルールですが、そもそも無限ループするかどうかを判定することは不可能なのです！

ここで、読者は疑問に思うかもしれません。停止性問題はプログラムの話です。Magic: The Gatheringに当てはめることができるのでしょうか？

できるのです！Magic: The Gatheringはコンピュータとして動作させることができます。トークンに情報を刻み込むのです。これではたからみるとゲームをしているだけなのに、実は円周率の計算をしていた、ということがありえます。そんな状態に持っていくプレイングは不自然きわまりないですが、理論上は確率は0ではありません！

現在、Magic: The Gatheringのルールは無限ループとは何かを厳密に定義してはいません。これは賢明なことかもしれません。もし定義してしまったら、その定義で無限ループと判断されるなら停止して、停止すると判断されるなら無限ループを引き起こすプログラムを、トークンの束で実行可能です。これはMagicの崩壊を意味します！！！

現実

現実には、いくつかの理由からこのことはあまり問題にはなりません。一つ目の理由は、上記の方法でMTGコンピュータを動作させるにはかなり不自然な状態に持っていかなければならないということで、そんな綱渡りのようなことをしているうちに対戦相手に叩きのめされるのがオチです。

二つ目の理由はちょっと根拠薄弱ですが、上記の方法は「～してもよい」というプレイヤーの選択がふくまれているということです（ただし、プレイヤーが意味のある情報処理を行うことはありません。常に同じ選択をするからです）。これは、場合によってはしないことによってループを停止させなければならないと解釈することもできます。しかし「そもそも現在無限ループが行われているのか？」がわからないというのがチューリングの言っていることなので、MTGコンピュータを停止させなくても良いことになるとも言えるでしょう。「その「～してもよい」をやるのはやめろ」と言われても、「今やってるのが無限ループだと？証明してみせろ。今の戦場の状態は以前の状態とはぜんぜん違うじゃないか。いつか終わるかもしれない。もしかすると後10秒で終わるかも」と言い返せばいいのです。

というわけで、主に第一の理由から、現時点ではこれは全く問題ではありません。タイトルは大げさでした。しかし将来、「～してもよい」を全く使わずにMTGコンピュータを作ることができるようなカードが出た場合――少数のカードで自然にMTGコンピュータを作ることができるようになった場合はなおさら――この問題は真に検討すべき問題となるでしょう。そうなった時、戦場の状態が以前と異なった新しいものであるにも関わらず、処理が終了するかどうかがさっぱり見当もつかないという状況が作り出される可能性があるのです。