遊戯王に必勝法はある？ “あっても分からない”と数学的に証明と報告。「Π¹₁完全」で暫定MTG超えの複雑さ【研究紹介】

イタリアのトリノ大学などに所属する研究者らが発表した論文「Optimal play in Yu-Gi-Oh! TCG is hard」は、トレーディングカードゲーム「遊戯王オフィシャルカードゲーム」（海外名：Yu-Gi-Oh! TRADING CARD GAME）において、ある戦略が確実に勝てる戦略かをコンピュータで判定できるかという問い（最適プレイの計算可能性）に対し、数学的に決定不能であると示したという研究報告である。

つまり、いかなる優秀なコンピュータプログラムを用いても、遊戯王における与えられた戦略が勝利戦略かどうかを判定するアルゴリズムは存在しないとする報告だ。

• keyboard_arrow_down 「八汰烏」「魔法都市エンディミオン」「皆既日蝕の書」「成金ゴブリン」など活用
• keyboard_arrow_down 停止性問題のさらに先、遊戯王における「Π¹₁完全」の証明

これまで「マジック：ザ・ギャザリング」（MTG）においても最適プレイの決定が計算不能であることは証明されていたが、本研究において遊戯王においても同様、あるいはそれ以上の複雑さが潜んでいることが数学的に証明されたという。

証明方法では、計算理論における有名な「停止性問題」を利用する。停止性問題とは、ある任意のコンピュータプログラムが最終的に計算を終えて停止するか、あるいは永遠にループし続けるかを、実行前にあらかじめ完璧に予測することは数学的にできるかという問いで、これは1936年にアラン・チューリングが示した通り絶対に判定できない問題である。

ここでは、この停止性問題を遊戯王のゲームで再現する仕組みをつくることで、遊戯王のある戦略が確実に勝てる戦略かをコンピュータで判定できるかという問いも不可能であることを証明する。

具体的には、遊戯王の公式ルールと実際のカードを使って、次のデッキを構築して盤面上にコンピュータ（チューリングマシン）を構築することで再現する。

まず、「八汰烏」の攻撃で相手に新たなカードを引かせず、行動を完全に封じるロック状態をつくる。その上で、フィールド魔法「魔法都市エンディミオン」に乗る魔力カウンターを、コンピュータのデータ記憶用メモリに見立てる。

そして、「皆既日蝕の書」「成金ゴブリン」「聖なる魔術師」「神聖魔導王 エンディミオン」などを用い、無限にループさせて魔力カウンターの数を自在に増減させ、盤面上でプログラムの計算処理をシミュレートする。ここで戦略として、もし計算処理が完了（停止）したら、その時点でカードのループを抜けて一斉攻撃に転じ、ゲームに勝利するという条件を設定する。

このように構築された盤面において、いつかループを抜けて勝てるのか、それとも永遠にループし続けて終わらないのかは分からない状態になる。このどちらの結末を迎えるかをゲーム開始前に完璧に見抜くことは、先ほどの停止性問題が証明している通り不可能である。

そして、計算の結末が事前予測できない以上、それに依存している、遊戯王でその戦略が必ず勝てる手順であるかどうかという問いにも、決して答えることはできない、ということになる。

つまり論文によると、この絶対に解けない停止性問題を遊戯王のルール内にそっくりそのまま組み込めた以上、いかなるコンピュータを用いたとしても、遊戯王におけるある戦略が確実に勝てる戦略かどうかを判定することは不可能（決定不能）であるという結論が導き出される。

研究はさらに進み、遊戯王TCGにおける必勝戦略の判定問題が、停止性問題よりもさらに計算が難しく、どんなコンピュータでも解けない「Π¹₁完全」（パイ・ワン・ワン完全）というレベルに到達していることも証明されたとしている。

数学の世界には、すでにΠ¹₁完全だとわかっている「NIS（No Infinite Sequence）」という難問がある。

研究チームは、NISという難問を遊戯王の盤面で再現する。具体的には、「フリントロック」と「士気高揚」というカードを組み合わせた無限ループをつくり、相手プレイヤーが毎ターン好きなだけライフポイントを回復できる状態にする。回復した量がそのまま相手が選んだ数として扱われる。

そして、相手が入力してきた数を受け取り、あらかじめ決めたコンピュータプログラムに従ってその数が正しいかどうかをチェックする。もし間違いが見つかれば、「サンダー・ボルト」で相手の盤面を吹き飛ばし、そのまま攻撃して勝つことができる。このように、相手が正しい答えをどこかで出せなければ勝利し、逆に正しい答えを無限に出し続ける方法が存在するなら永遠に勝つことができないという状況をつくり出す。

つまり、この戦略で確実に勝てるかという問いに答えるには、相手にとって、正しい答えを無限に出し続ける方法が存在するかしないかを判定しなければならない。

しかし、正しい答えを無限に続ける方法が存在しないことを判定する問題は、数学の世界では「NIS」という名前がすでについており、どんなコンピュータを使っても解けないことが証明済みである。

よって、NISが現在のどんなコンピュータでも解けない問題である以上、この遊戯王の特殊な盤面においても与えられた戦略が勝つかを計算して判定することもまた、不可能であるという結論が導き出される。論文はこのように主張する。

なお、研究者らは、今回の手法がMTGにも応用できる可能性があるとも述べている。論文において遊戯王が現時点で最も複雑なゲームとされるのは、先にこの手法による証明が完成したためであり、MTGやポケモンカードゲームなど他のカードゲームにも同等の複雑さが潜んでいる可能性は残されている。

Source: Nicolosi, Orazio, Federico Pisciotta, and Lorenzo Bresolin. “Optimal play in Yu-Gi-Oh! TCG is hard.” arXiv preprint arXiv:2603.02863 (2026).