天使の問題

天使問題（エンジェルしょうこ、英: Angel Problem）は、ジョン・ホートン・コンウェイが提唱した組合せゲーム理論の問題である。このゲームは一般に天使と悪魔ゲームと呼ばれている。 ^{[1]このゲームは、}天使と悪魔と呼ばれる2人のプレイヤーによってプレイされる。ゲームは無限のチェス盤（または2D格子の点と同等）上でプレイされる。天使はゲーム開始前に指定されたべき乗k（ 1以上の自然数）を持つ。盤は天使が1つのマスにいる状態で始まる。各ターンで、天使はチェスの王が最大でk 回移動して到達できる別の空のマス、つまり開始マスからの距離が無限大ノルムで最大でkであるマスにジャンプする。悪魔はターンで、天使がいない任意のマスにブロックを追加することができる。天使はブロックされたマスを飛び越えることはできるが、そこに着地することはできない。天使が動けなくなったら悪魔の勝ち。天使はいつまでも生き残れば勝ち。

天使の問題は、十分な力を持つ天使は勝つことができるかということです。

プレイヤーの 1 人に勝利戦略が存在する必要があります。悪魔が勝利を強制できる場合、有限数の手でそうすることができます。悪魔が勝利を強制できない場合、天使が負けを避けるために実行できるアクションが常に存在し、天使にとっての勝利戦略は常にそのような動きを選択することです。より抽象的に、「ペイオフ セット」(つまり、天使が勝つすべてのプレイの集合) は閉じた集合であり(すべてのプレイの集合の自然な位相において)、そのようなゲームは決定されていることがわかっています。もちろん、任意の無限ゲームでは、プレイヤー 2 に勝利戦略がない場合、プレイヤー 1 は常に、プレイヤー 2 が勝利戦略を持たない位置につながる動きを選択できますが、一部のゲームでは、単に永遠にプレイするだけではプレイヤー 1 に勝利がもたらされないため、未決定のゲームが存在する可能性があります。

コンウェイはこの問題の一般的な解決法に対して賞金を出しました（十分に高い力を持つ天使の勝利戦略には100ドル、天使の力に関係なく悪魔が勝てるという証明には1000ドル）。まず高次元で進展がありました。2006年後半、天使が勝てることを示す独立した証明が現れ、元の問題は解決しました。ボウディッチは4人の天使（つまり、力k  = 4の天使）が勝てることを証明し^[2]、マテ^[3]とクロスター^[4]は2人の天使が勝てるという証明を与えました。

この問題は、1982年にバーレカンプ、コンウェイ、ガイが著した『 Winning Ways 』 ^[5]で「天使と四角を食べる人」という名前で初めて発表されました。2次元では、初期の部分的な結果には次のようなものがありました。

• 天使のパワーが1であれば、悪魔は勝利の戦略を持っている（コンウェイ、1982）。（コンウェイによると、この結果は実際にはベルレカンプによるものである。）これは、クッツの論文のセクション1.1で読むことができる。^[6]
• 天使が Y 座標を決して減らさない場合、悪魔は勝利の戦略を持っていることになります (Conway、1982)。
• 天使が常に原点からの距離を広げる場合、悪魔は勝利の戦略を持っていることになります (Conway、1996)。

3次元では次のことが示されました:

• 天使が常にy座標を増加させ、悪魔が1つの平面でしかプレイできない場合、天使は勝利戦略を持っています。^[7]
• 天使が常に y 座標を増やし、悪魔が 2 つの平面でしかプレイできない場合、天使は勝利の戦略を持っています。
• 天使のパワーが 13 以上であれば、勝利戦略となります。
• 無限の数の悪魔がそれぞれ離れた場所でプレイしている場合でも、天使の力が十分に高ければ、天使は勝つことができます。(「離れた場所でプレイする」とは、悪魔が原点からこの距離内でプレイできないことを意味します)。${\displaystyle d_{1}<d_{2}<d_{3}<\cdots }$${\displaystyle d}$

最終的に、2006年（天使問題の普及に貢献した ピーター・ウィンクラーの著書「数学パズル」の出版から間もなく）、天使が2次元で勝利戦略を持っていることを示す4つの独立したほぼ同時の証明が登場しました。ブライアン・ボウディッチの証明は4天使に対して有効ですが、オッドバー・クロスターの証明とアンドラーシュ・マテの証明は2天使に対して有効です。さらに、ピーター・ガックスは、はるかに強力な天使を必要とする証明 Archived 2016-03-04 at the Wayback Machineを持っています。詳細はかなり複雑で、正確さについてジャーナルでレビューされていません。ボウディッチとマテの証明は、 Combinatorics, Probability and Computingに掲載されています。クロスターの証明は、Theoretical Computer Scienceに掲載されています。

3D では、天使は常にy座標を増加させ、悪魔は 3 つの平面に制限されているため、悪魔に勝利戦略があるかどうかは不明です。

Oddvar Kloster は、2 人の天使の問題を解決するための建設的なアルゴリズムを発見しました。このアルゴリズムは非常に単純で、また最適です。なぜなら、前述のように、悪魔は 1 人の天使に対して勝利する戦略を持っているからです。

まず、天使の開始位置のすぐ左に、下から まで、上まで垂直線を引きます。この線は天使が進む道を表しています。この道は悪魔が動くたびに更新され、盤上のマス目を「左の集合」と「右の集合」に分けます。マス目が左の集合の一部になると、ゲームの残りの間はそのままになり、天使はこれらのマス目に今後移動しません。悪魔が新しいマス目をブロックするたびに、悪魔がブロックした右の集合の 1 つ以上のマス目を左の集合に移動するように、経路のあらゆる可能な変更を検索します。経路の長さが、左の集合に移動されたブロックされたマス目の数の 2 倍を超えない場合のみ、これを行います。このような適格な経路のうち、ブロックされたマス目を左の集合に最も多く移動する経路を選択します。次に、天使はこの道に沿って 2 歩進み、前進するときには道を左側に保ちます (したがって、悪魔が正方形をブロックしていなければ、天使は北へ無限に進み続けます)。角を時計回りに回る場合、角に接する 2 つのセグメントの右側に同じ正方形があるため、天使は 1 歩も移動しないことに注意してください。 ${\displaystyle y=-\infty }$${\displaystyle y=\infty}$

マテ^[3]は、天使が前のターンに占領することができたマスを決して破壊しないナイスデビルを導入しました。天使がナイスデビルと対戦する場合、悪魔がボードの限られた領域に閉じ込めることができた場合、天使は負けを認めます（そうでなければ、天使は2つのマスの間を行ったり来たりするだけで負けることはありません）。マテの証明は2つの部分に分かれています。

1. 彼は、天使が良い悪魔に勝てば、天使は本物の悪魔に勝てることを示しています。
2. 彼は天使が善良な悪魔に勝つための明確な戦略を示しています。

大まかに言えば、第 2 部では、天使は左半分の平面全体が破壊されたと仮定し (実際に善良な悪魔によって破壊されたマス目に加えて)、破壊されたマス目を迷路の壁と見なし、「壁に手を置く」テクニックで迷路を迂回することで、善良な悪魔に勝利します。つまり、天使は迷路の壁に左手を置いたまま、壁に沿って走ります。すると、この戦略を採用した天使を善良な悪魔が罠にかけることはできないことが証明されます。

最初の部分の証明は背理法によるため、マテの証明は、本物の悪魔に対する明確な勝利戦略をすぐには導き出さない。しかし、マテは、彼の証明は原理的にはそのような明確な戦略を与えるように適応できると述べている。

ブライアン・ボウディッチは、以下のルール変更を加えたオリジナルゲームのバリエーション（ゲーム2） を定義しています^{[2] 。}

1. たとえその後に悪魔がそれを阻止しようとしたとしても、天使は既にいたどのマスにも戻ることができます。
2. k-devil はブロックされる前に、そのマス目を k 回訪問する必要があります。
3. 天使は上、下、左、右のいずれかに 1 マス移動します (公爵移動)。
4. 勝つためには、天使は回り道を描かなければなりません (以下に定義)。

迂回パスとは、半無限弧（開始点はあるものの終了点のない、自己交差しないパス）であり、次のプロパティを持つペアワイズ分離ループであるパスです。 ${\displaystyle \pi =\cup _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})}$${\displaystyle \sigma =\cup _{i=1}^{\infty }\sigma _{i}}$${\displaystyle {\gamma_{i}}}$

• ${\displaystyle \forall i:|\gamma _{i}|\leq i}$ここで、i 番目のループの長さです。${\displaystyle |\gamma _{i}|}$

(明確に定義されるためには、は の終点で始まり で終わり、は の開始点で終わる必要があります。) ${\displaystyle \gamma_{i}}$${\displaystyle \sigma_{i}}$${\displaystyle \sigma_{i}}$${\displaystyle \sigma_{i+1}}$

Bowditch は、5 人の悪魔で変更 2 と 3 を加えたゲームのバリエーション (ゲーム 1) を検討します。次に、このゲームで勝つ戦略は、元のゲームで 4 人の天使で勝つ戦略になることを示します。さらに、5 人の悪魔をプレイする天使 (ゲーム 2) は、かなり単純なアルゴリズムを使用して勝利を達成できることを示します。

ボウディッチは、ゲーム 2 で幻の天使が 5 人の悪魔と対戦することを想像することで、4 人の天使がゲームのオリジナル バージョンに勝つことができると主張しています。

天使は幽霊がたどる道をたどりますが、ループは避けます。したがって、この道は半無限の弧なので、天使は以前いたどのマスにも戻らず、元のゲームでもこの道は勝利の道となります。 ${\displaystyle \sigma}$

ゲームの 3 次元バージョンでは、強力な天使が勝利戦略を持っていることを示す証明は、「守護者」を利用します。任意のサイズのキューブごとに、そのキューブを監視する守護者がいます。守護者は、監視しているキューブが安全でない、安全、またはほぼ安全であるかどうかを各移動ごとに決定します。これが機能するように、「安全」と「ほぼ安全」の定義を選択する必要があります。この決定は、そのキューブ内のブロックされたポイントの密度とキューブのサイズのみに基づいています。

天使に命令が与えられなければ、天使はただ上に移動するだけです。天使が占めているキューブのいくつかが安全ではなくなった場合、これらのキューブのうち最大のものの守護者は、天使がそのキューブの境界の 1 つを通って出られるように手配するように指示されます。守護者がキューブから特定の面まで天使を護衛するように指示された場合、守護者はすべて安全なサブキューブの経路をプロットすることによってそれを行います。次に、これらのキューブの守護者は、それぞれのサブキューブを通って天使を護衛するように指示されます。特定のサブキューブでの天使の経路は、天使がそのキューブに到着するまで決定されません。到着したとしても、経路は大まかにしか決定されません。これにより、悪魔は経路に沿って十分に離れた場所を選択してそれをブロックすることができなくなります。

この戦略が機能することが証明できるのは、天使の進路にある安全なキューブを悪魔が安全でないキューブに変えるのにかかる時間が、天使がそのキューブに到達するのにかかる時間よりも長いためです。

この証明は2006年にイムレ・リーダーとベラ・ボロバスによって発表された。^[8] 実質的に同様の証明は2005年にマーティン・クッツによって発表された。^{[6] [9]}

• 殺人運転手問題。強力で機動力のある敵と、非常に機動力があるがそれほど強力ではない敵を対決させる数学的なゲームです。
• 追跡-逃避は、類似した一連の問題です。
• マクスウェルの悪魔
• ラプラスの悪魔

• ジョン・H・コンウェイ著「天使の問題」
• クロスターの天使問題サイト