Duel"Math"ters 特別編 ～ギャクテンポインター省略証明～
ごあいさつ
えー、どこから話したものか困ってますαrufαです。アクアギャクテンポインターに対する喧々諤々をXで拝見しまして、正直すぐ収まって裁定も出るだろうし、それ以上に割と簡単な内容じゃない？と思ってたのですが、意外にも根の深い問題を抱えてまして、こーれは私が出ないとアカンな、ということで証明を書くことにしました。今回ばかりは出し惜しみ無し、仮にも「証明を与えることでループの省略を行える」という最初の発見者であると同時に、ループ証明の基礎を作らせて戴いてる実績を以て書き上げようと思います。ただ私画像とかの扱いクッソへたくそなので、いつも通り文章量で殴るタイプの記事になります。ご容赦ください。
状況確認
まずそもそもの《アクア・ギャクテンポインター》の能力のどこがまずいのか、について考えていきましょう。
アクア・ギャクテンポインター R 水文明 (10)
クリーチャー：リキッド・ピープル パワー：5000
■S・トリガー ■ブロッカー
■このクリーチャーが出た時、各プレイヤーのクリーチャーを最大1体ずつ選び、持ち主の山札の下に置く。このようにして自身のクリーチャーが選ばれたプレイヤーは、自身の山札の上から、クリーチャーが出るまで表向きにし、そのクリーチャーを出す。その後、そのプレイヤーは、自身の山札をシャッフルする。
※書式の都合、空白、改行位置は筆者の編集
単独の能力自体は《転生プログラム》や《エンペラー・キリコ》あたりを思い出す感じのテキストではあります。ループとしては要はこいつ自身を出したときにこいつを戻して、山札からこいつを出して…と繰り返すことで、相手の能力ストックが溜まって、万が一《天災デドダム》とか《桜風妖精ステップル》とかが出ていたら…というのが論旨。
で、そこで問題となってくるのが「シャッフル」の部分。例えば自分の山札の中に《ギャクテンポインター》以外のカードがあったり、あるいは相手の山札に《終末縫合王 ザ＝キラー・キーナリー》のようなカードがあった場合に、いつ停止するのか、が判別できない、あるいは本当に無限ループができるような山札構成であったとして、その山札の中身を確認することができるのか、というのが、現行の「証明不可能」をもたらしているポイントであるとのこと。
実際、山札にこのカードが4枚、仮に相手の山札には止めるような能力があるが、それはそれとしてほかのクリーチャーもたくさんいる、として、自分の山札の内容を証明したり、あるいは相手の能力ストックが致死のラインまで貯められることを"直接"証明できるのか、となるとこれはNOです。なんなら先にギャクテンポインターの能力が無限にストックされていても無理です。オニカマスとかいますし。とはいえ、これを直にやると何が起こるのかと言いますと、まず自分の山札側だけで収束するまで操作を行うことになるのですが、マトモに相手をすると、過去違法になったコンプガチャと同じような確率が降ってきます。(ざっくりハイランダーの山札25枚を100回まわして山札の中身が全部見える確率が65％程度、80％以上見えるまで150回以上、90％で約220回)しかもここから被りカードの調査のためにさらに遅い速度の収束に持っていく操作をしなければならず、ついでにギャクテンポインター以外が出てこないと証明するための必要な作業数は雑に巨大数が待ってます(どう転んでも指数3段ぐらいは欲しい)。宇宙の寿命は短いのでこれでは間に合いません。なんならここを収束する証明によって解決できたとして、相手側の能力によって停止する場合についてはもっと煩雑です。確率0や1(100%)に収束するならともかく、([止まる能力を持つカード数]/[デッキのクリーチャー数])に分散がくっついて収束も実行不可能なレベルで遅いのに計算すらやってられません。
と、いうわけで、既知の結果呼び出しもダメ、マトモに操作するのもダメ、これじゃ当然に証明にならない。 …と、一般的には思われてるわけですね。
証明方針
そもそもにして、普通に省略も証明も関係なく、大会時間も地球の寿命も(誇張表現ではないことに注意)一切気にせず全部そのまま実行した場合について考えましょう。
有限で止まる場合、最も止まりにくいケースで山札クリーチャー60枚の中にキーナリーのような「cipを止めるカード」が1枚だけ入っているケースです(母なるパックなどを使えばもっと状況は変わりますが、さすがに割愛)。このとき、1/59(これはギャクテンポインターの能力で山札の下にクリーチャーを送る処理による)のカードを引き込む期待値は当然に60回程度ではありますが、実際60回試すとしてそこまでにキーナリーが出る確率は64％程度しかありません。しかし、80％期待値で95回、90%期待値で135回、99.99%期待でも517回と実はわりかし現実的な回数でなんとかなります。確率入れてシミュレータ回して最大値の推移を確認しても、MAXで400回程度もあればなんとかなります。この数字は私がデュエマで普段省略せず(ループ開始地点に行くための基礎部分で必要な範囲として)召喚を回してる回数とほぼ同じなので、極めて現実的な範囲で収まっているといえます。なので、ギャクテンポインターの能力が止まるのなら普通にやればいい。
一方で無限に止まらない場合、止めるカードが無いためギャクテンポインターの能力による呼び出しは、「悠久ヴォルグの第一証明(山札の確認作業)」と同じ現象が起きます。つまり、シャッフルして出す処理によって視認したカードとその順番の無限リストから、デッキリストへの全単射が与えられるため、デッキ内容の全てが確認できるというもの。ただし、こちらの収束はとんでもなく遅く、同一のカード名が複数枚入っている可能性も担保する場合、当たり前に数億～数兆枚の確認作業が必要となります(ここガッチガチに統計学やってればそこまで要らないはずではあるんですが、私はそっちは分野ではないので…)。こんなの実行できるわけありません。
問題は「止まるのか止まらないのかが不明である」という点。止まるならすぐ終わるし、止まらないならずっと終わらないので、閾値を定めることもできないし、実行できる範囲にあるかもわからない。ですが、ギャクテンポインターの通常処理に一工夫加えることで、開示する情報量を増やさず確率的に等価に、かつ『有限か無限かだけを小手数で判別できる』手段が得られたらどうでしょうか。つまり、本来の処理では同時に行っていた「有限か無限かの確認」と「デッキの内容の確認」をあえて分けることで、有限/無限それぞれの状況に対して場合分けをし、混乱なく処理を与えることを以て「省略」とするという方向。
具体的にはギャクテンポインターの能力で最も煩雑な、処理のたびにシャッフルが挟まっている部分のみを「有限か無限かの判定には無関係である」ことを証明によって省略し、「シャッフルせず1枚ずつ山札を開ける処理」に差し替えてしまう、という方針で行きます。ただし、これが省略できるのは、あくまでこの操作が「有限か無限かの確認作業である」ためであり、ここで出たカードの能力がストックされたりするわけではないことに注意してください。
証明
命題：ギャクテンポインターのシャッフルは、本来得られる情報量を超えない範囲での操作によって省略可能である
山札の列Dと山札に含まれているカードのカード名リストCについて、以下の定義を与える。
・a,b,n,mは自然数(今回は0を含まない流儀を用いる)
・tは非負整数(自然数に0を付けたもの)
・Dの大きさmは山札の枚数と等しく、全てのDの要素D_nにおいて、a<bのときD_aはD_bより上にあるとする。(山札のX番目を必ず上から数えるよ、って意味です)
・カード名のリストCからカード名C_1～C_nを得ることができる。(デッキシート通りでも発売順でも、入ってるカードの種類のリストが作れるという意味です。なおそのリストが見れるのかは話が別です)
・C_nに対し、n≦mであり、DからCへの全射が存在することは無条件に与えられる。(山札を全て表向きにしたときに、「複数枚入ってて名前が被ること」はあっても、「カードに名前が書いてない」ことや、「リストにあるカード名で山札に1枚も入っていない」ことは起きないよ、という意味です)
シャッフルされた山札Dxに対し、ギャクテンポインターの能力を1度使用することを考える。この時Dx_1～Dx_aまでのカードが公開され、Dx_aを除く公開されたカードがシャッフルされる。この時プレイヤーは空のリストCtとCoに出現したカードの記録が認められる。Ctのうち何も記録されてないリストはC0である。このときDx_tに対して、以下の場合分けを行う。
①D1_aがギャクテンポインターの能力を停止させる機能を持つ
この場合、自明に以降の処理が行えないため、有限であることを示せる。またここまで通常の処理のみを行っているため、以降は正規の対戦処理を行うことができる。
②D1_aがギャクテンポインターの能力を停止させる機能を持たない
D1_1～D1_aをC0に書き込んだリストC1を得る。この時各C0_nに対してカード枚数も書き込み、またCoには枚数情報を除いた同様のリストを得る。
a=mの場合はCo=Cとなり、かつDがギャクテンポインターの能力を停止させることができないことが判明するために無限の処理を行うことができるため、山札の開示と無限処理を得ることができる(ここの証明は割愛します。悠久ヴォルグと同じことが起きます)。
a<mの場合、この状況で改めてギャクテンポインターの能力を１度使用する。Dx_aは処理により山札の一番下に行くため、D1_a=D2_mである。このとき前回と同様にD2_1からD2_bまでのカードが公開されるが、この時出たカードのリストをC0に書き込みC2を得て、CoにC1の内容を書き足す(重複するカードに対しては記録しない)。
以上の操作を再帰的に行うことで、Co=C への収束を得るか否か、また有限への停止をするかが認められる。(すべての山札の内容が分かった上で停止する可能性もある。デッキにクリーチャーが２枚で、山札の下から２番目がワルドだった場合などが該当。)
ここで山札列Dに対し、a<q<mかつm-q<aであるDx_qについて考える。Dx_qより下にあるカードについて、ギャクテンポインターの能力を停止させる能力を持たないことだけがわかっていれば、山札をDx_mまでめくる必要はなく、Dx_1～Dx_qまでをランダムに確認できればよいことが分かる。
能力よりDx+1_mは能力よりDx_aであることが分かっており、これはCxに記載された公開情報である。またDx_aはギャクテンポインターの能力を停止しないことがわかっており、よってDx+1においてC=Coの確定に必要な検証枚数は最大でもm-1枚である。
一方で、Dx_1～Dx_aまでのカードに対して、それらのカードはギャクテンポインターの能力処理を停止させる機能を持たないことが確定している。それらのカードは判定を冗長にしているだけのため、有限か無限かという判定に限れば、これらのカードは山札から除外しても問題はなく、Dx_a+1～Dx_mの順序が不明であることは自明なため、Dx_a+1～Dx_mを改めてシャッフルする必要が無いことがわかる。
ただし、一様に全て山札から除外すると、残りの山札の公開情報と合わせると容易に採用枚数が判明する。これは本来の処理では得られない情報である。
ここで{Dx+1_q～Dx+1_m}⊂{Dx_1～Dx_a}の条件を与える。{Dx_1～Dx_a-1}をシャッフルし、誰も内容を確認せず一部y(<a)枚を山札に戻し、残りを裏向きに除外すると、Dx_aだけはDx+1_mであることが判明しているが、それ以外のカードDx+1_mについて、それは「山札に戻ったDx_nなのか、除外されたDx_nと偶然同名の2枚目のカードなのか」はシャッフルによって不明となっており、単に「除外された束のカードに再判定が必要ない」ことのみを情報として得られる。
またDx_1=Dx_aの場合は、Dx_a=Dx+1_mより、山札の位置としてどこに除外してあっても問題にならないことがわかる。これはDx+2の時にシャッフルされるが、Dx_aとDx+1_aをシャッフルし片方を山札の一番下に戻すことにより、どちらが山札にあるか(およびDx_aと同名カードの枚数)の情報を秘匿できる。
以上により、プレイヤーの目線からはDx_a=Dx_q-1の条件を満たした場合を除き、山札の内容はCoによってカード種類のみ判明し、カード枚数が不明である状態を作ることができる。この時有限、無限に関わらず検証すべき山札の枚数は
1/2+(a-1)y/(a-y)
枚ずつ減少するため、省略を行わない検証作業よりも早い検証を行うことができる。
以上により、ギャクテンポインターのシャッフル操作を情報を増やさず省略し、山札を検証する速度を大幅に上げる方法を得られた。
証明の概要と実際の省略手順
さて、ここまではカッチカチに書いちゃったので、「じゃあ実際何をするの？」という話です。本来の流れは「ループできるかできないかが時間内にわからないからループできないじゃん」だったのを、「まず有限無限の判定で長いところを省略してしまえ」という話。無限ループしないなら普通に処理できるし、無限ループすることが確定したなら悠久ヴォルグと同じ証明機序で回せるのは自明(読者の課題とする。This is easy exercise)なので、その手前にある「時間内にできるかわからないループ確認」を省略しに行けばいいのです。省略と言っても、本当に全てを省略できるわけではありませんが、もとより「証明できた範囲の処理を省略する」ルールなんだから、できるとこだけやればいいんです。それが今回の証明の範囲。具体的には「ギャクテンポインターのシャッフル効果だけを省略する」という芸当です。
手順としましては、まずギャクテンポインター側の人が自分だけでループを回すことを想定します。１回目は普通にギャクテンポインターを対象に能力を使ってください。このとき、ギャクテンポインター以外のクリーチャーが出たら当然停止するのはわかると思います。これでギャクテンポインターが出た場合、次にこれから「山札」「待機所」「除外ゾーン」の3つに分割します。
まず山札の一番下に置いたギャクテンポインターを「待機所」に送ります。次に他の表向きにしたギャクテンポインター以外のカードをシャッフルし、裏向きに1枚以上(見たカードの半分程度が望ましい)を選んで「除外ゾーン」に置きます。残りを山札に戻し、シャッフルします。次のギャクテンポインターは、この残った山札に対して行い、山札をめくりきるか、ギャクテンポインターが出るまで行います。次にギャクテンポインターがめくれた時、同じ分割操作を行い、以降は「待機所」に置かれたカード2枚置かれるたびにシャッフルして片方を除外し、片方を山札に戻します(まぁ自分側の場合置かれるのはギャクテンポインターだけではありますが)。これを繰り返して山札の一番下がギャクテンポインターであるか、山札をめくりきることができれば、この場合無限ループになっていることが証明できます。それ以外のクリーチャーをめくった場合、有限性が担保されたので待機所、除外ゾーンの両方を全て山札に戻し、改めて本来の通常の処理をやり直してください。この際検証のために見えた情報と実際に手順を行う処理に見える情報の出現確率に違いは無く、対戦相手から見えたカードに対して枚数の同定もお互いに不可能のため、いずれのプレイヤーも検証によって情報は得られていないとみなすことができます。
次に自分側のみの無限ループが成立した場合、悠久ヴォルグ証明と同じ山札の開示が発生します。本来の無限ループであることの証明は山札の開示と同程度の情報が担保されていないといけないためです。ただここまでの条件を満たしている場合、既に山札の開示は実質なされているので(最低でも全部のカードが１回以上開示されている)、同意がとられていればここ自体は省略しても構いません。
そして相手側のループに入ります。手順としては自分側と同様に、
・まず通常処理を1回やる
・処理後のカードを「山札」「待機所」「除外」に分ける
・めくったクリーチャーは一度待機所に送り、それ以外から１枚以上をランダムに除外して残りを山札に戻してシャッフル
・待機所は２枚になったらシャッフルして「山札」と「除外」に１枚ずつ送る
・どこかでストップする能力が出たら全部山札に戻して通常処理でやり直し、めくりきることが出来たらループ成立として山札公開
こうすることで、本来調べないといけないカード枚数より遥かに少ない手順で有限か無限かだけの検証が行えます。これを以て「ギャクテンポインターの"シャッフル操作"の省略」として宣言します。
実情と提言
…とまぁ、ループすることではなく、"確認作業のシャッフルだけを省略する証明"のためにめたくた書きましたが。実際ちゃんと証明が与えられるのはここまでが限界だったりします。ただし判定後は普通にループ証明を回せるので、その手前に別の証明を与えるだけで良かったんです。
ただ先日悠久ヴォルグに関する問題を出した際、極めて残念な解答結果になってまして…正直これをちゃんと証明として認めさせるのは現実的には無理かなぁ、というのが本音だったりします。悠久ヴォルグ(7年前)の時にも言ったのですが、これが通らないからってゴネたり遅延したりするのは絶対にやめましょう。…とか言ってたらかつての悠久ヴォルグは証明が拡散された少し後にルールが生えてきたので、今回もそうなる可能性を否定はしませんが。誰だあんなルール作ったやつ。許さんぞ総合ルール4.4。
一方で水面下でルールを確認した上で実態調査を友人がしてくれているので、うまい落としどころを見つけたらその際には提言させていただけたらなと。そっちは数学屋(語弊のある表現)の私の分野外ですし。裁定は偉い人にお任せします。あくまでも、こちらが出せるのは証明できる事実まで。
おわりに
この記事は以上となります。本当に長かった。この話はこれでおしまい、とはできないのが悲しいところ。これから皆さんが実際にプレイする際に混乱を招かない方法については、公式のみならずある意味プレイヤー全体の問題なのかもしれません。ルールの範囲で出来ることを探すのは良いことではあるんですが、見つけた物の責任もある程度ついてくるわけで。
証明についても反証があればお待ちしてますし、疑問などありましたら私のXアカウントにリプライを送っていただければ、できる範囲でお答えします。ジャッジの方がいらっしゃってこちらを参考にするもよし、プレイに不安がある方も作用機序について知れば少し安心できるでしょうし、そもそも知とは共有してこそですし。
最後に、私は普段デュエル・マスターズのデバッグ作業で遊んでます。普段の生息地こそXですが、文量が重い内容になったらNoteに書いてます。お手すきでしたら他の記事も見ていただけたら嬉しいです。
ここまでご覧いただき、ありがとうございました。