🔢 mathematics

The Dynamical Landscape of Beggar-My-Neighbour: Ultra-long Matches, Loops, and Infinite Matches

この論文は、ババ抜き（Beggar-My-Neighbour）の決定論的ダイナミクスを数学的・計算機的に解析し、ゲーム終了時間の統計的性質を明らかにするとともに、適応的な挿入戦略を用いた自動化アルゴリズムによって無限ループの存在を証明したものである。

原著者： Nicolas Andorno, Giulio Cernoia, Simone Duiz, Alessandro Michelangeli

公開日 2026-03-02

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Nicolas Andorno, Giulio Cernoia, Simone Duiz, Alessandro Michelangeli

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🃏 ゲームとは何か？（ルールのおさらい）

まず、このゲームは**「運命のカード」**のようなものです。
プレイヤーは戦略を立てたり、選択したりできません。カードを引く順番が決まっていれば、ゲームの全プロセス（誰が勝つか、何回プレイするか）は最初から決まっています。

普通のカード：ただのカード。
スペシャルカード（エース、キングなど）：これが出ると「挑戦」が始まります。相手は一定枚数のカードを出さなければならず、出せなければ負けてカードを全部取られます。

この単純なルールが、**「終わるゲーム」と「永遠に終わらないゲーム（無限ループ）」**を生み出すのです。

🔍 研究の発見：3 つの大きな物語

この論文は、このゲームを「探検」して、3 つの大きな発見をしました。

1. ゲームの長さ：「爆発する花火」のような分布

研究者は、何億回ものゲームをコンピューターでシミュレーションしました。

ほとんどのゲーム：すぐに終わります（1 回〜数十回）。
たまに：非常に長いゲーム（数百回）になります。

【比喩】
ゲームの長さは、「花火の打ち上げ」に似ています。
ほとんどはすぐに消えますが、たまにすごい勢いで長く燃え続ける花火があります。
面白いことに、この「燃え続ける時間」の分布は、「記憶がない」という不思議な性質を持っています。
「すでに 100 回プレイして長引いているから、あと 10 回で終わるだろう」という予測は全く当てになりません。
「すでに 100 回続いたゲームは、これから先も『いつ終わるかわからない』という同じ確率で続く」という、まるでサイコロを振り続けるような不思議な法則が見つかりました。

2. 超長寿ゲームの秘密：「波打つ海」

何百回も続く「超長寿ゲーム」を詳しく見ると、カードの枚数が**「波」**のように上下していることがわかりました。

片方のプレイヤーがカードを大量に持っている時、もう片方は数枚しか持っていない。
しかし、すぐに逆転して、また元の状態に戻る。

【比喩】
これは**「潮の満ち引き」のようです。
片方が「干潮（カードがなくなる）」になり、瀕死の危機に陥っても、次の波（カードの獲得）で奇跡的に生き延び、また「満潮」に戻ります。
この「満ち引き」が何百回も繰り返され、最終的にどちらかが勝つまで、この波は止まりません。
さらに、カードの配置（どこにスペシャルカードがあるか）も、完全にランダムではなく、「ほどよい乱れ」**を保ちながら動いていることがわかりました。

3. 永遠の地獄：「無限ループ」の存在

最も驚くべき発見は、「永遠に終わらないゲーム」が実際に存在するという事実です。
これまでは「たまたま見つからないだけだ」と言われていましたが、この研究では、**「無限ループ工場」**という新しいアルゴリズム（仕組み）を開発し、実際に無限に続くゲームの初期カードの配置を見つけ出しました。

【比喩】
これは**「無限の滑り台」のようなものです。
ある特定のカードの並び方だと、プレイヤーは滑り台を滑り降りて、また上に戻り、また滑り降りる……というサイクルを永遠に繰り返してしまいます。
研究者は、この「無限の滑り台」に乗り込むための「入り口（初期のカードの配置）」**を、試行錯誤と逆算の技術を使って見つけ出したのです。
しかも、その入り口は、カードが半分ずつに分かれた「公平な状態」から始まるものも存在することがわかりました。

🧩 なぜこれが重要なのか？

このゲームは、**「決定論的（すべてが決まっている）」なのに、「確率的（ランダムに見える）」**な振る舞いを示すという、数学的に非常に面白い矛盾を含んでいます。

決定論的：カードの順番が決まれば、未来は 100% 決まっている。
ランダムに見える：しかし、その動きは予測不能で、まるでサイコロを振っているような統計的な法則に従う。

この研究は、**「単純なルールから、どれほど複雑で美しい（あるいは恐ろしい）世界が生まれるか」**を示す良い例です。
また、「無限ループ」の存在が証明されたことで、このゲームの「全貌（ダイナミカル・ランドスケープ）」がようやく見えてきたと言えます。

🎯 まとめ

この論文は、「ベガー・マイ・ネイバー」という単純なゲームが、実は「終わるゲーム」「超長寿ゲーム」「永遠のループ」という 3 つの異なる世界を持っていたことを証明し、その「永遠のループ」を作るためのレシピ（カードの並び方）を初めて完成させた、画期的な研究です。

まるで、**「一見平穏な海の下に、巨大な渦（無限ループ）が存在し、その入り口を見つけるための地図を描き出した」**ような冒険物語なのです。

論文「Beggar-My-Neighbour の動的風景：超長試合、ループ、無限試合」の技術的サマリー

本論文は、確率的な要素を持たない決定論的なカードゲーム「Beggar-My-Neighbour（隣人乞食）」の数学的・計算機的な解析を行ったものである。著者らは、形式状態空間フレームワークの確立、大規模な数値シミュレーション、およびループ発見のための自動化アルゴリズムの開発を通じて、このゲームの動的な性質、特に「終了する試合」と「無限に続く試合（ループ）」の二項対立を解明した。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳述する。

1. 問題設定と背景

ゲームの性質: Beggar-My-Neighbour は、プレイヤーに選択の余地がなく、初期のデッキ構成（シャッフルと配分）によって完全に決定論的に進行するゲームである。
未解決の課題: 長年、このゲームが無限に続く（ループする）マッチが存在するかどうかは、組合せゲーム理論における未解決の問題であった。また、終了する試合の長さの分布や、超長試合（Ultra-long matches）の構造についても統一的な理解が欠けていた。
目的: ゲームの動的風景（Dynamical Landscape）を包括的に解析し、無限試合の存在を証明するとともに、その発生メカニズムと統計的性質を明らかにすること。

2. 手法とアプローチ

著者らは以下の 3 つの主要なアプローチを統合して研究を進めた。

A. 大規模数値シミュレーション

規模: 異なるデッキ構成（ $N$ 枚のカード、 $R$ ランクの特殊カード）において、 $10^7$ 〜 $10^8$ 個のランダムに選択された初期デッキをシミュレーションした。
分析対象: 試合の長さ（トリック数）の分布、勝率、デッキ内のカード数の変動、特殊カードの分離度、位置エントロピーなど。
限界: 無作為サンプリングでは、無限試合（ループ）の発生確率が極めて低いため、直接検出することは困難であった。

B. 理論的枠組みの構築

状態空間の定義: 全デッキの順序付けられた構成を状態空間 $S$ として定義し、トリックごとの遷移を決定論的関数 $F$ として形式化した。
決定論と非単射性: 前方への進行は決定論的であるが、逆方向（過去の状態の復元）は非単射的（Injectivity の欠如）であることを証明した。つまり、ある状態から逆算すると、複数の異なる前状態が存在し得るため、一意な履歴復元は不可能である。
期待値の議論: 無限試合が存在する場合、ゲームの期待長は無限大になることを理論的に示唆した。

C. 「無限ループファクトリー」アルゴリズムの開発

逆方向探索: 既存の研究（[2]）で提案されたヒューリスティックな逆構築法を、自動化されたアルゴリズムとして実装・拡張した。
適応的挿入戦略: 小さなループから出発し、特殊カードや普通カードを適応的に挿入・削除・置換するバックトラック法を採用した。
バランスの回復: 非平衡なデッキからループを生成し、そのループ内の状態から逆方向に探索することで、最終的に「平衡状態（両プレイヤーのカード数が等しい）」からループに入る初期デッキを自動発見する。

3. 主要な結果

A. 終了する試合の統計的性質

長さの分布: 終了する試合の長さ分布は、ポアソン分布ではなく、**指数分布（幾何分布の離散版）**に近似されることが確認された。
- 中間的な長さの範囲では、マッチの経過時間に関わらず終了する確率が一定であるという「無記憶性（Memory-less）」の性質が観測された。
- ただし、これは個々のゲームが確率的であるわけではなく、初期状態のアンサンブルにおける統計的近似である。
超長試合のパターン: 数百〜千回以上のトリックに及ぶ超長試合において、以下の特徴が確認された。
- 多スケール振動: マクロな周期（勝者の交替）、メソな周期、ミクロな振動が観察される。
- 準平衡状態: カード数は $N/2$ 付近で振動し続け、極端な偏りから回復する「死からの回復」現象が頻繁に起こる。
- エントロピー: 特殊カードの位置エントロピーは、極端なクラスター化も均一分散もせず、中間的な値で推移する。

B. 無限試合（ループ）の存在証明と発見

無限試合の存在: 特定の初期デッキ構成において、ゲームが無限にループすることが厳密に証明・発見された。
- 低比率設定: 特殊カードの比率が低い $(40, 1)$ 設定において、20 トリックのループを直接シミュレーションで発見。
- 標準設定: 標準的な $(52, 4)$ 設定（J, Q, K, A が特殊カード）においても、逆方向探索アルゴリズムを用いて無限ループを持つ初期デッキを構築・発見した。
ループの構造:
- 発見されたループは、プレイヤー間のカード数のバランスが一定でない「非平衡」な状態を含むものもあれば、平衡状態（カード数 26-26）から直接ループに入るものも存在する。
- 後者は、従来の構築法では見逃されていた可能性が高い。

C. 無限試合が存在するパラメータ領域

無限ループは、特殊カードの比率 $4R/N$ が極端に低い（0%）場合や極端に高い（100%）場合には発生せず、**中間的な領域（約 7%〜43% の間）**に存在する「存在窓（Existence Window）」があることが示唆された。

4. 主要な貢献

無限試合の存在の決定的な証明: 長年の未解決問題であった「標準的なルール（52 枚、4 ランク）での無限試合の存在」を、具体的な初期デッキ構成の提示とアルゴリズム的発見によって実証した。
自動化されたループ発見アルゴリズム: 「無限ループファクトリー」を開発し、手動のヒューリスティックに依存せず、系統的に無限ループを持つ初期デッキを生成・発見する手法を確立した。
動的風景の包括的マッピング: 終了する試合の統計的性質（指数分布、無記憶性の近似）と、無限試合の構造（多スケール振動、エントロピー特性）を統一的な枠組みで記述し、ゲームの動的風景を可視化した。
逆方向決定論の解明: 決定論的ゲームでありながら、逆方向への状態復元が非単射的であることを理論的に整理し、これがループ発見の難易度や状態空間の構造にどう影響するかを論じた。

5. 意義と今後の展望

学術的意義: 組合せゲーム理論、動的システム、記述集合論、数学的論理の交差点において、単純なルールから極めて複雑な振る舞い（無限ループ）が生まれるメカニズムを解明した。
実用的意義: 決定論的システムにおける「予測不可能性」の源泉（初期条件への鋭敏な依存性と状態空間の複雑なトポロジー）を理解するモデルケースを提供する。
今後の課題:
- 状態空間における収束や終結への近接性を定量化する「意味のある距離関数（Metrics）」の定義。
- 異なる初期デッキが同じループや終了状態へ収束する「バウンダリー（吸引域）」の分類。
- 無限ループが存在するパラメータ領域の厳密な境界の特定。

総じて、本論文は単なるカードゲームの分析にとどまらず、決定論的システムの複雑性、ループの存在証明、およびその発見アルゴリズムに関する重要な数学的貢献を果たしている。