On an Erdős-Szekeres Game

この論文は、有名なエルデシュ・セケレスの定理に触発された 2 人対の置換ゲームについて、パラメータ $a \geq b$ かつ $b \in \{2,3,4,5\}$ の場合に勝者を決定し、勝利戦略を提示するものである。

要約

この論文は、数学の有名な定理をヒントにした**「二人で遊ぶカードゲーム」**について書かれたものです。少し難しい数学用語を使わず、日常の例え話を使って説明しましょう。

🎮 ゲームの正体：「数字の並び替え」対決

まず、このゲームがどんなものかイメージしてみてください。

• プレイヤー: 2 人（先攻と後攻）。
• 道具: 1 から N までの数字のカード。
• ルール: 二人は交互に、まだ使っていない数字を選んで、並べ替えていきます。
• 目的（この論文のルール）: 「負ける」ゲームです。
  • もしあなたが選んだ数字が、「長い昇順（小さい順に並んだ）」の列を作ってしまったら、あるいは「長い降順（大きい順に並んだ）」の列を作ってしまったら、その瞬間にあなたの負けになります。
  • 相手は、あなたが「昇順」や「降順」を作ってしまうように誘導しようとし、自分は作らないように必死に逃げ回ります。

このゲームは、1935 年に発見された「エルデシュ・セケレスの定理」という数学の法則に基づいています。この定理は、「数字を並べれば、必ず一定の長さの『昇順』か『降順』の列ができてしまう」と言っています。つまり、このゲームは**「いつか必ず誰かが負けてしまう」**という運命を背負ったゲームなのです。

---

🗺️ 戦略の鍵：「消えた部屋の地図」

この論文の最大の特徴は、数字の並びを直接考えるのではなく、**「2 次元のマス目（ボード）」**を使って戦略を考えたことです。

【アナロジー：お掃除ロボットと消えた部屋】
想像してください。大きな部屋（ボード）があって、二人は交互に床を掃除（マス目を塗りつぶす）していきます。

• 掃除したマスは「消えた部屋」となります。
• 二人は、**「消えた部屋の隣」**にある未掃除のマスしか選べません。
• ゴール: 部屋の一番右下の角（最後のマス）を**「誰が塗るか」**で勝敗が決まります。
  • このゲームは「塗りつぶされたら負け」なので、**「最後の角を塗らされた人が、相手が次の手で昇順・降順を作ってしまうことを強制する」ことになります。つまり、「最後の角を塗った人が勝ち」**という逆転現象が起きます。

この「ボード塗りつぶしゲーム」は、有名な「チョンプ（Chomp）」というゲームに似ています。

---

🏆 先攻（1 番手）の勝利戦略

この論文で著者（Lara Pudwell さん）が解明したのは、**「相手がどんな手を出しても、先攻の人が必ず勝つことができる」**という戦略です。特に、以下の条件で「昇順の長さ」を $a$、「降順の長さ」を $b$ としたとき、$b$ が 2, 3, 4, 5 の場合に、先攻がどう勝つかを詳しく説明しています。

1. $b=2$ の場合（単純なルール）

• 状況: 「降順の長さ 2」を作ったら負け。つまり、大きい数字の後に小さい数字が来たらアウト。
• 戦略: 常に「一番大きい数字」を並べるしかありません。
• 勝敗: 数字の総数（$a$）が奇数なら先攻の勝ち、偶数なら後攻の勝ちです。単純な「じゃんけん」のようなパターンの繰り返しです。

2. $b=3, 4, 5$ の場合（複雑な迷路）

• 状況: 降順の長さが 3 以上、4 以上、5 以上になると、戦略が非常に複雑になります。
• 著者の発見:
  • $b=3, 4$: 以前から知られていた戦略を、この「ボード塗りつぶし」の視点で再発見し、より直感的に説明しました。
  • $b=5$（新発見！）: ここが論文のハイライトです。$b=5$ になると、相手の手があまりにも多すぎて、従来の方法では勝てないように見えました。しかし、著者は**「7 つの特定のボードの形（状態）」**を見つけ出し、相手がどんな手を出しても、先攻は必ずその 7 つの形の一つに戻せることを証明しました。
  • イメージ: 相手がどんなに複雑な迷路を作っても、先攻は「常に特定の安全なルート（7 つの形）」に引き戻す魔法を持っている、ということです。

---

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

1. 数学の「ゲーム化」: 難解な数学の定理を、誰でも楽しめる「ボードゲーム」の戦略として解明しました。
2. 新しい視点: 以前は「言葉の羅列（文字列）」で分析されていたものを、著者は「図形（マス目）」で見ることで、直感的な戦略を見つけ出しました。
3. 先攻の強さ: このゲームでは、「先攻（1 番手）」が常に有利であることが、特定の条件で証明されました。

📝 まとめ

この論文は、**「数字を並べるゲーム」において、「相手がどんな手を出しても、先攻の人が『最後の角』を相手に塗らせるように誘導する」**という、完璧な勝利のレシピを $b=5$ まで見つけたという報告です。

まるで、**「相手がどんなに複雑な迷路を造っても、先攻の人は常に『出口』への最短ルートを確保し、相手を壁に追い詰める」**ような、知的で美しい戦略が描かれています。

数学が「ゲーム」を通じて、私たちに「先手必勝」のロジックを教えてくれる、とても面白い研究です。

技術概要

論文「On an Erdős-Szekeres Game」の技術的サマリー

1. 問題設定

本論文は、1935 年に発表された有名な**エルデシュ・セケレスの定理（Erdős-Szekeres Theorem）**に基づいた二人零和ゲームを分析するものである。

• ゲームの定義:

  • 二人のプレイヤーが交互に、集合 $\{1, 2, \dots, n\}$ から数字を選択し、それらを並べて置換（permutation）を構築していく。
  • パラメータ $a$ と $b$ は正の整数であり、ゲームは長さ $a$ の増加部分列（$I_a$）または長さ $b$ の減少部分列（$J_b$）が形成された時点で終了する。
  • ミセール（Misère）ルール: 本論文の主要な焦点は、**「最初に $I_a$ または $J_b$ を完成させたプレイヤーが敗れる」**というルールである。
  • 目標は、$a \ge b$ かつ $b \in \{2, 3, 4, 5\}$ の場合において、先手（Player 1）が勝つための戦略を特定し、証明することである。

• 背景:

  • 従来の研究（Harary, Sagan, West [3]）はコンピュータによる探索に依存しており、状態空間が指数的に増大するため、$a, b$ が小さい場合に限られていた。
  • Albert ら [1] は、有理数 $\mathbb{Q}$ 上でのゲームや、特定の $b$ 値に対する戦略を言語論理的なアプローチ（ternary words）で分析したが、$b=5$ のミセール版における完全な戦略は未解決だった。

2. 手法とモデル化

本論文の核心的な貢献は、置換の構築過程を2 次元グリッド上のセル塗りつぶしゲームとして視覚的・幾何学的に再定式化することにある。

• ボードモデルの構築:

  • Seidenberg [6] によるエルデシュ・セケレス定理の証明（鳩の巣原理を用いたもの）に着想を得て、$(a-1) \times (b-1)$ のグリッドを「ボード」として定義する。
  • 各セル $(c, r)$ は、現在の置換 $\pi$ において、$\pi_n$ で終わる最長増加部分列の長さが $c$、最長減少部分列の長さが $r$ であることを示す。
  • 消去領域（Eliminated Region）: 一度セル $(c, r)$ が塗られると、その左上にあるすべてのセル $(c', r')$（$c' \le c, r' \le r$）も自動的に「消去（eliminated）」される。これは、それらの長さの組み合わせが不可能になることを意味する。
  • ゲームの進行: プレイヤーは、現在の消去領域の「縁（edge-adjacent）」にある未塗りのセル（open cell）を選択して塗る。
  • 勝利条件: 右下の角 $(a-1, b-1)$ を塗ったプレイヤーが、ボード全体を消去したことになる。次のプレイヤーは必然的に $I_a$ または $J_b$ を完成させざるを得ないため、右下の角を塗ったプレイヤーが勝利する（ミセールルール下）。

• モデルの利点:

  • 従来の「ternary words（R, B, P の文字列）」による表現（Albert ら）と比較し、幾何学的な直観に基づいた戦略構築を可能にする。
  • 複数の異なる置換が同じボード状態（消去領域）に対応し得るが、勝敗の判定には影響しないことを示している。

3. 主要な結果と戦略

論文は $b$ の値ごとに先手必勝戦略を構築している。

$b=2$ の場合

• ボード: $1 \times (a-1)$ の 1 行。
• 戦略: プレイヤーは左から順にセルを塗る。
• 結果: $a$ の偶奇によって勝者が決まる。
  • $a$ が偶数なら先手勝ち、$a$ が奇数なら後手勝ち。
  • これは、$a$ 番目の手（最後のセル）を誰が取るかで決まる単純なパリティ問題である。

$b=3$ の場合

• ボード: $2 \times (a-1)$ の 2 行。
• 結果: 先手必勝（$a \ge 3$）。
• 戦略:
  • 先手は常に、行 1 と行 2 の塗られたセル数のバランスを維持する（行 1 が $k$ 個、行 2 が $k-1$ 個など）。
  • 後手が行 1 を塗れば先手は行 2 を、後手が行 2 を塗れば先手は行 1 を塗ることで、最終的に後手を負ける位置に追い込む。

$b=4$ の場合

• ボード: $3 \times (a-1)$ の 3 行。
• 結果: 先手必勝（$a \ge 4$）。
• 戦略:
  • 開局、中盤、終盤の 3 フェーズに分かれる。
  • 先手は、特定の「消去セル数のパターン」を維持する。具体的には、(行 1, 行 2) が $k$ 個、行 3 が $k-2$ 個、または行 1 が $k$ 個、(行 2, 行 3) が $k-1$ 個という状態を維持する。
  • 後手のどの手に対しても、先手はこのパターンを維持する応手が可能であり、最終的に後手を負ける位置に追い込む。

$b=5$ の場合（本研究の最大の貢献）

• ボード: $4 \times (a-1)$ の 4 行。
• 結果: 先手必勝（$a \ge 5$）。
• 戦略:
  • $b=5$ は複雑さが増し、単純な対称性やパリティだけでは記述できない。
  • 集合 $\mathcal{S}$（中盤の目標状態）: 先手は、ボードを 7 種類の特定の状態（$\mathcal{S}$）のいずれかに留めるように戦略を組む。これらの状態は、各行の「消去セル数」と「空きセルの奇偶性」によって定義される。
  • 集合 $\mathcal{E}$（終盤への移行状態）: 終盤に入り、特定の列や行にのみ空きセルが残った状態へ移行する。
  • 証明手法:
    1. 開局（最初の 4 手）で先手が $\mathcal{S}$ に到達できることを示す。
    2. 中盤において、後手が $\mathcal{S}$ から移動した場合、先手が応じて再び $\mathcal{S}$ に戻せることを、コンピュータ支援によるケーススタディと手動による検証で証明する。
    3. 終盤へ移行し、先手が勝利することを示す。
  • この戦略は、$b=5$ におけるミセール版の完全な解決策を提供し、Albert ら [1] の成果を拡張したものである。

4. 考察と意義

• 正常プレイ（Normal Play）との比較:
  • 本論文は主にミセールルールを扱っているが、付録で正常プレイ（最初に完成させた者が勝ち）についても言及している。
  • 正常プレイでは、ボードのサイズが $(b-2) \times (a-2)$ に実質的に縮小されるため、$b \ge 4$ で先手必勝となるという既存の結果 [1] と整合する。
• 戦略の複雑さ:
  • $b$ が増加するにつれて、戦略の記述はより複雑になり、ケース分けの数が爆発的に増える。$b=5$ の戦略はコンピュータ探索と人間の洞察の組み合わせによって導き出された。
  • $b \ge 6$ への一般化は今後の課題であるが、現在の手法では計算量が膨大になることが示唆されている。
• ゲームの長さ:
  • 提案された戦略を用いた場合のゲームの手数の範囲を分析し、理論的な最大長さ（定理 1 の境界）と最小長さの間に収まることを示した。
• P 状態（先手敗北状態）の分布:
  • 可能なボード状態のうち、先手が敗北する状態（P 状態）の割合を計算し、$a$ が増加するにつれてその割合が減少する傾向や、パリティによる振る舞いの違いをデータとして提示した。

5. 結論

本論文は、エルデシュ・セケレス定理に基づく二人ゲームのミセール版について、$b \le 5$ のすべてのケースにおいて先手必勝戦略を確立した。特に、2 次元グリッドモデルを用いることで、置換の構造を幾何学的に捉え、$b=5$ という以前未解決だったケースに対する具体的な戦略を提示した点が画期的である。このアプローチは、組合せゲーム理論とパターン回避の理論を結びつける新たな視点を提供し、より大きな $b$ 値に対する研究の基礎となった。