MTGのチューリング完全性【要約版】
Alex Churchill、Stella Biderman、Austin Herrickの論文『Magic: The Gathering is Turing Complete』を解説します。この論文はMagic: The Gatheringがチューリング完全であることを証明しています。
チューリング完全とは、どんな計算でもできるということです。チューリング完全なものには、パソコン、スマホ、多くのプログラミング言語、Excelなどがあります。また、Mine Craftやマリオメーカーもチューリング完全であることが知られています。Mine Craftなら、レッドストーン回路を使ってあらゆる計算ができます。
翻訳に際して原著者から許可をいただいていますが、この記事は要約です。原論文も合わせてご覧ください。具体的には、論文の3章と4章の内容になります。後日、全訳版を公開する予定です。全訳版には計算機科学の面白い考察も含まれるので、ご期待ください。
おかしなところがあれば指摘していただけるとありがたいです。
追記
この記事の執筆を手伝っていただいたαrufα φluwind氏が、この記事の中心的な概念であるチューリングマシンをより分かりやすく解説した記事を執筆してくださいました。こちらも是非一緒にご覧ください。
また、論文を執筆したAlex Churchill氏本人がFUN With Algorithmsで講演した動画もご覧ください。論文を理解する大きな助けになると思います。
チューリングマシンとは
チューリングマシンとは、どんな計算でもできる架空の機械です。
チューリングマシンはテープとヘッドで構成されます。
テープは左右に無限に続いていて、マス目状に区切られています。マス目には記号を書くことができます。
ヘッドはテープの一つのマス目に設置されると、そのマス目の記号を読みとり、記号を書き換えることができます。空白のマスは空白記号が書いてあると解釈します。
ヘッドが1マス書き換えるたびに、その時のヘッドの状態に応じてコントローラーが命令通りにヘッドを左右どちらかに1マス動かします。
「ヘッドがどのように記号を書き換えるのか」「どのような時に計算を終了するか」をあらかじめ命令して、チューリングマシンに与えておきます。
以下の手順で計算を行います。
チューリングマシンに命令を与え、テープに入力を書く
ヘッドがテープの記号を読み取る
ヘッドの状態と読み取った記号に応じて記号を書き換える
ヘッドの状態と読み取った記号に応じて右か左に1マス戻る
ヘッドの状態と読み取った記号に応じて状態を変える
停止状態になったら計算を終え、停止状態でなければ2に戻る
詳しくはwikipedia等をご参照ください。
MTGチューリングマシンを作る方法
以前からMTGがチューリング完全であることは知られていたようです。この論文では、MTGのカードの効果を使ってチューリングマシンをそのままの形で実装する方法(以下この記事ではMTGチューリングマシンと呼ぶ)が紹介されています。
アリスとボブがMTGをプレイするとします。(数学では伝統的に2人の登場人物をAlice、Bobと名付けます。これは、頭文字がA、Bだからです。)
MTGチューリングマシンはフィールド上で構成されています。アリスが初期状態を与えると、カードの効果が連鎖的に発動し、最後にボブを倒してフィールド上に結果を出力します。
チューリングマシンを実装するには以下のパーツを作らないといけません。
テープ
コントローラー(命令)
ヘッド
ヘッドの状態
テープ
トークンやクリーチャー1枚をテープの1マスとみなします。
各トークンのタフネスとパワーをヘッドからの距離とします。
ただし、2/2をヘッドの位置とし、3/3はその左、4/4はその左…、のようにマスの位置を定めます。マスの記号として、クリーチャータイプを使います。18個のタイプを用いてチューリングマシンを再現します。今回再現するのはRogozhin’s (2, 18) UTMという万能チューリングマシンです。このマシンは2つの状態と18個の記号だけであらゆる計算を実行できます。
今回は18個の記号として、霊基体、バジリスク、セファリッド、デーモン、エルフ、フェアリー、巨人、ハーピー、イリュージョン、巨大戦車、カヴー、リヴァイアサン、マイア、ノッグル、オーク、ペガサス、サイ、スリヴァーを使います。
例えば、緑の5/5霊基体・トークンは頭の左から3番目のマスに第1記号が書かれていることを表し、白の10/10スリヴァーは頭の右から9番目のマスに第18記号が書かれていることを表しているとします。
コントローラー(命令)
チューリングマシンの命令は「ヘッドが○○の状態のとき××の記号を読み取ったら、記号を▲▲に書き換えて、右/左に1マス動く」という指示をいくつか集めたものです。
これを再現するために、2枚のカードを使います。
これらはクリーチャーが死んだときに、その状態やクリーチャータイプに応じて結果を出力することができます。
これらのカードを《人工進化》《幻色染め》で編集して、命令をプログラミングします。
《人工進化》を使って《腐れ肺の再生術師》のコピーを大量に作り、それぞれを編集します。
以下、文中で「ハック」「ハッキング」などの表現が出てきたら、そのカードは《人工進化》や《幻色染め》で編集されたということです。
各命令の編集方法が論文のTable Ⅱに載っています。
ヘッド
以下の方法で新しいセルを読み込みます
アリスに《蔓延》/Infest(すべてのクリーチャーは、ターン終了時まで-2/-2の修整を受ける)を唱えさせる。
タフネスが2の固有トークンが死亡する。
死亡したトークンのクリーチャータイプに応じて《腐れ肺の再生術師》が発動する。
死亡したトークンに対応した新しい2/2トークンが生み出される。これによって、テープに書かれたデータは失われずに済む。
チューリングマシンは次に左か右に移動し、ヘッドの片側にある全てのトークンに+1/+1カウンターを、反対側にある全てのトークンに-1/-1カウンターを追加して、テープの順番を保つようにトークンを修正する。左右への移動は、まず《浄化の光線》/Cleansing Beamを唱え、次に《魂を吹き消すもの》/Soul Snuffersを唱えることで実装されます。
ヘッドの状態
ここまでの説明で状態を1つ持つチューリングマシンは構成できました。
2つ目の状態を実装するために、フェイズインとフェイズアウトを用います。フェイズアウトしたカードは存在しないかのように扱われるため、フェイズインしているカードの効果だけが発動します。エンチャント《不可視の外套》/Cloak of Invisibilityを用いて《腐れ肺の再生術師》にフェイズを与え、2つ目の状態の命令を実装します。
MTGチューリングマシンを動かす方法
このマシンのポイントは、アリスとボブは行動の選択肢が常に1つしかないことです。アリスとボブがそれぞれ強制された行動をとり続けることで計算が勝手に行われます。
計算の開始と実行
計算開始時に必要なパーツが論文のTable Ⅰに載っています。
アリスのライブラリは《浄化の光線》、《合同勝利》、《魂を吹き消すもの》
ターン開始時、アリスの手札は1枚
ボブは《野生の喚起》をコントロール→アリスは手札を発動しないといけない
アリスは《太陽と月の輪》にエンチャントされている→手札は発動後ライブラリの一番下に戻る
アリスは土地を一つコントロールするが、《窒息》の効果で永久にタップされたままなので、《野生の喚起》の能力で唱える以外に、引いた呪文を唱えることができない
両者とも《魅力的な執政官》をコントロールしているため攻撃できない。
ボブは《リサイクル》をコントロールしており、ドローステップは飛ばされる
《蔓延》でヘッドが読み込み→《腐れ肺の再生術師》か《ザスリッドの屍術師》発動
アリスはオーラ《錯覚の利得》をコントロールしている。
ここで《錯覚の利得》の役割について、原論文の説明を引用しておきます。
ここから先は、ブログ著者の力不足により要約することができなかったので、原論文を引用します。
ヘッドを左右に動かす方法
ヘッドの状態を変える
テープを伸ばす
チューリングマシンのテープは本来無限の長さを持ちますが、MTGであらかじめ無限のクリーチャーを準備するのは不可能です。そこで、必要に応じてテープをつけ足す機構を用意します。
停止
まとめ
MTGはチューリング完全である
MTGでのチューリング完全な計算モデルの一例としてMTGチューリングマシンを構成できる
MTGチューリングマシンはチューリングマシンとほぼ同じ構造を持つ
計算が始まるとプレイヤーは常に選択肢が一つしかない状態に置かれ、それを実行し続けると、最後に一方のプレイヤーが勝利して、フィールド上に計算結果が出力される。
また、任意のフィールドの勝敗を判定するアルゴリズムは存在しないことなどが説明されています。
余談 人力計算モデル
HTMLはプログラミング言語か?というのはいろんな所で聞く話題です。この問いに対してはいろんな答えがありますが、よく聞くのは、「HTML+CSSはチューリング完全だからプログラミング言語」という答えです。
ただ、私はこの答えが腑に落ちない点があります。それは、ユーザーがボタンを何度も押さないと計算が実行されない点です。計算の1ステップごとにユーザーが干渉しないと計算が進まみません。ユーザーはあくまで「動力源」で計算はしていないので、HTML+CSSが計算をしたことになります。しかし、勝手に計算をしてくれるjavascriptとこれを同列に「プログラミング言語」だと語るのはモヤモヤするわけです。
私はこのような計算モデルを勝手に「人力チューリング完全モデル」と呼んでいます。この観点に立てば、HTML+CSSは"人力"チューリング完全言語です。今回紹介したMTGチューリングマシンもアリスが行動を起こさないと計算が進まないので人力モデルですね。
人力モデルは計算のステップ数だけ人間が作業をしないと計算が進みませんので、実用的ではありません。おそらくですが、MTGチューリングマシンで足し算をするだけでも桁数に比例して大量の処理が必要ですので、実用的ではないでしょう。人力ではないチューリングマシンがMTGで実現されれば、Excelの代わりにMTGをプレイする日が来るかもしれません。
追記 停止性問題とは? 09/27/2022
Noteやtwitterでこの記事を引用していただいているようです。力をいれて書いた記事なので、うれしい限りでございます。この記事のリンクは「チューリング完全だから盤面の判定問題が停止性問題だ」という文脈で紹介されることが多いようですので、停止性問題について簡単に書き加えておきます。詳しい説明は全訳版をお待ちください。
結論から言うと、「MTGのある盤面がどちらのプレイヤーの必勝局面かを判定するアルゴリズムはない」「MTGはとても複雑なゲーム」というお話です。
停止性問題
チューリングマシンは停止して答えを出力します。つまり、チューリングマシンが停止しなかったら、答えを出力できないのです。今回の記事でもMTGチューリングマシンを停止させるための機構が組み込まれていましたよね。チューリングマシンというのは停止してこそ意味があります。
ただ、停止しないチューリングマシンも作れます。無限ループが簡単な例ですね。同じ操作を繰り返すばかりで出力が得られないのであれば意味がありません。そこで、「あるチューリングマシンが停止するのか判断できるチューリングマシン」を作ることができればうれしいわけです。これを停止性問題といいます。
残念ながら停止性問題はチューリングマシンでは解けないことが証明されています。どう頑張っても原理的に不可能です。つまり、コンピュータのアルゴリズムがちゃんと動作するかをコンピュータで確認するのは無理ということです。
さて、今回の記事ではMTGがチューリング完全であることを証明しました。つまり、あらゆるチューリングマシンはMTGの盤面に落とし込むことができます。チューリングマシンの停止性問題が解けないということは、その盤面がどちらかのプレイヤーにとっての必勝局面なのかを判定するチューリングマシン=アルゴリズムは存在ということなのです。
ちなみに、停止性問題がチューリングマシンで解けるなら数学者はいらなくなります。ある定理の反例を探索して、反例が見つかり次第停止してそれを出力するチューリングマシンを作りましょう。反例が無ければ停止しないので、このマシンの停止性問題を解けば定理の真偽が分かりますね。もちろん停止性問題はチューリングマシンでは解けないので、コンピュータが完全に数学者に代わるのはまだまだ先になりそうです。やはり数学は一筋縄にはいかないのですね。
MTGの複雑さ
MTGのある盤面が必勝局面なのかは判定できないことが分かりました。つまり、オセロのように完全読み(あり得る選択肢を全て列挙して最善手を選ぶ方法)はできないということです。これは「選択肢の多いので探索しきれない」という技術的な問題ではなく、停止性問題というもっと原理的なものであることに注意してください。
ゲームがチューリング完全というのは、ルールが厳密に定められたターン制ゲームの中では最も複雑で自由度が高いということです。「チューリング完全なゲームは人間には楽しめないほど難解になるのではないか?」という予想があったのですが、その反例がなんとMTGだったのです。
Acknowledgement
最後になりましたが、論文を執筆し和訳を許可してくださったAlex Churchill氏、論文の共著者のStella Biderman氏、Austin Herrick氏、論文の和訳を手伝ってくださり、たくさんの意見をくださったαrufα φluwind氏(twitter:@F_arufa)、この記事の公表に協力してくれた友人に感謝申し上げます。
この記事が気に入ったらサポートをしてみませんか?