エンジェル・プロブレムのソースを表示

[[File:Angel problem with 3-angel.png|thumb|200px|薄いオレンジの場所は3の力を持つ天使がジャンプできる範囲を示す。紫の場所はすでに悪魔によってブロックされているため、天使はそこへは動けない]]

'''エンジェル・プロブレム (angel problem) '''は[[ジョン・ホートン・コンウェイ]]によって提起された組合せ[[ゲーム理論]]の問題である。一般に'''天使と悪魔 (Angels and Devils) '''[[ゲーム]]とも呼ばれている<ref name="conway1996">John H. Conway, ''[http://library.msri.org/books/Book29/files/conway.pdf The angel problem]'', in: Richard Nowakowski (editor) ''Games of No Chance'', volume 29 of MSRI Publications, pages 3&ndash;12, 1996.</ref>。ゲームは、天使と悪魔と呼ばれる二人の[[プレイヤー (ゲーム)|プレイヤー]]によって、[[無限]]の広さの[[チェスボード]]（[[格子 (数学)|正方格子]]）の上で行われる。ゲームの開始前に、天使は力''k''（''k''は[[自然数|正の整数]]）を持つことを決めておく。開始時点で盤上には天使がひとつの場所にいるだけで他は空である。天使と悪魔は交互に手順が回ってくる。天使は、自分が今いる地点から[[チェビシェフ距離]]で最大''k''の範囲内にある空いている地点へジャンプする。悪魔は、天使のいない任意の地点にひとつブロックを置く。天使はブロックを飛び越えることはできるが、ブロックの上に乗ることはできない。天使が動けなくなったら悪魔の勝ちとなり、無限に動き続けることができれば天使の勝ちである。

このとき、十分な力を持つ天使であれば悪魔に勝てるだろうか。

このゲームには必ずどちらかのプレイヤーに必勝法が存在する。もし悪魔に必勝法があれば、有限の手数でゲームは終わる。もし悪魔に必勝法がなければ、天使は常に自分が負けないように手を選ぶことで無限にゲームを続けることができ、勝敗の定義からそれが天使の必勝法となる。より抽象的には、天使の勝つすべてのゲームプレイの集合は、すべてのゲームプレイの自然な[[位相空間]]に対して[[閉集合|閉じている]]、つまりゲームは[[決定性公理|決定的である]]。当然ながら、無限に続けられるあらゆるゲームはプレイヤー2が必勝法を持たないときプレイヤー1は自らが負けないような手を選び続けることができるが、ゲームの勝敗の定義次第では単にゲームを無限に続けることがプレイヤー1の勝利になるとは限らない。したがって、決定的でないゲームが存在する可能性はある。

コンウェイはこの問題に対する回答に[[懸賞金問題|賞金を与える]]と宣言した（十分な力を持つ天使の必勝法に100ドル、天使の力によらず悪魔が勝つと示すことができれば1000ドル）。当初は、チェスボードを三次元に拡張した問題に対する進展が見られた。オリジナルの（二次元の）問題では、2006年後半に、独立した複数の証明によって天使の勝利が示された。Bowditch は4の力を持つ天使が勝つことを証明し<ref name="B">Brian H. Bowditch, "The angel game in the plane", ''Combin. Probab. Comput.'' 16(3):345-362, 2007.</ref>、Máthé<ref name="M">András Máthé, "The angel of power 2 wins", ''Combin. Probab. Comput.'' 16(3):363-374, 2007</ref> と Kloster<ref name="K">O. Kloster, "A solution to the angel problem", ''Theoretical Computer Science'', vol. 389 (2007), no. 1-2, pp. 152&ndash;161</ref> は、力が2あれば十分なことを示した。

== 単純でうまくいかない天使の戦略の例 ==
天使を勝たそうとする直観的な戦略の多くはうまくいかず、この問題の難しさはそれをどう乗り越えるかにある。たとえば、天使が自らの近くにあるブロックから逃げ続けようとする場合、悪魔は盤上の北向きに巨大な[[蹄鉄|馬蹄形]]を作った上で、天使の近くの南側からブロックを置いていくことで天使を追い込める。反対に天使が遠くを見通して遠方にある罠を避けようとする場合は、悪魔は今度は北向きに小さな馬蹄形を作って、天使のはるか南側からブロックを置いていって罠にかけられる。

天使は（自明な罠を避けるためにたまに東西にジグザグにも動いて）力の限り北に動き続ければ勝てるはずだと思うかもしれない。この戦略では、天使の到達しうる領域は（三次元でとらえれば）円錐形の中に納まることになる。悪魔は離れたところでその円錐を突っ切るように壁を作っていくことができ、いずれ天使はその壁にぶつかる。この天使は北方に進む一方なので、飛び越えられない厚さの壁を作っておけばそこで動けなくなる。

== 歴史 ==
問題の初出は1982年の''Winning Ways''という本で<ref>{{citation
 | last1 = Berlekamp | first1 = Elwyn R. 
 | last2 = Conway | first2 = John H. 
 | last3 = Guy | first3 = Richard K. 
 | contribution = Chapter 19: The King and the Consumer
 | pages = 607&ndash;634
 | publisher = Academic Press
 | title = Winning Ways for your Mathematical Plays, Volume 2: Games in Particular
 | year = 1982}}.</ref>、そのときは "the angel and the square-eater" という名前で発表された。
二次元の場合、初期の部分的な成果には以下のようなものがある。

* 1の力の天使に対しては、悪魔に必勝法がある (Conway, 1982) （コンウェイによればこの成果は実際は[[エルウィン・バーレカンプ]]に帰する）。この証明は Kutz の論文の1.1節に見ることができる<ref name="kutz2004">Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, [https://doi.org/10.17169/refubium-14116 PhD Thesis] FU Berlin, 2004</ref>。
* 天使が南の方角に一度も進むことがないなら、悪魔に必勝法がある (Conway, 1982) 。
* 天使が常に初期地点から離れるように進むなら、悪魔に必勝法がある (Conway, 1996) 。

三次元の場合は、下記が示されている。

* 天使が常に北の方角に進み、悪魔はひとつの平面上でしかプレイしなければ、天使に必勝法がある<ref name="BandL">B. Bollobas and I. Leader, ''The angel and the devil in three dimensions.'' Journal of Combinatorial Theory, Series A. vol. 113 (2006), no. 1, pp. 176&ndash;184</ref>。
* 天使が常に北の方角に進み、悪魔はふたつの平面上でしかプレイしなければ、天使に必勝法がある。
* 天使の力が13以上であれば、天使に必勝法がある<ref name="kutz2004"/>。

2006年（Peter Winkler の ''Mathematical Puzzles'' によって、この問題が一般的に知られるようになって間もなく）、二次元の場合に天使に必勝法があるとの、四つの独立した証明がほぼ同時に発表された。Brian Bowditch の[http://homepages.warwick.ac.uk/~masgak/papers/bhb-angel.pdf 証明]は4の力の天使の場合だが、Oddvar Kloster の[https://web.archive.org/web/20160107125925/http://home.broadpark.no/~oddvark/angel/Angel.pdf 証明]と  András Máthé の[http://homepages.warwick.ac.uk/~masibe/angel-mathe.pdf 証明]では2の力になっている。Péter Gács の[https://arxiv.org/pdf/0706.2817.pdf 証明]では、より大きな定数のみが対象となっている。Bowditch と Máthé による証明は ''Combinatorics, Probability and Computing'' に掲載され、Kloster のものは ''Theoretical Computer Science'' に掲載された。

さらに2008年には Johan Wästlund によって、南北方向には2の力のまま、東西方向には1の力に弱められた天使にも必勝法が存在することが示された<ref name="W">Johan Wästlund, A weaker winning angel, [http://www.math.chalmers.se/~wastlund/weakerAngel.pdf A weaker winning angel] 2008</ref>。

== 未解決の問題 ==
三次元の場合に、天使が常に北の方角に進み、悪魔はみっつの平面上でしかプレイしないと制限を置くとしたとき、悪魔に必勝法があるのかわかっていない。

== 証明の概略 ==

=== "守護者"の証明 ===

三次元の場合に力のある天使が必勝法を持つことの証明は"守護者 (guardian) "という概念を用いる。盤上の任意の大きさの立方体に、その立方体を監視する守護者を置く。守護者はプレイヤーの手番ごとに自分の監視している立方体が"危険"、"安全"、"ほぼ安全"のいずれなのか判断する。"安全"と"ほぼ安全"の定義は証明が成り立つように選ばれており、この判断は純粋に立方体のサイズとそこに含まれるブロックの密度によって決まる。

天使は指示が与えられなければ、上にジャンプし続ける。天使のいる立方体のいくつかが安全でなくなったとき、そのうち最大の立方体を監視する守護者は天使がその立方体のいずれかの辺を通って立方体から離れられるように指示される。守護者が立方体のある面から抜け出るように天使を導くには、その立方体に含まれる小さくすべて安全な立方体群を辿るようにする。各立方体群の守護者は同様に繰り返して天使を導く。天使がある立方体の中を辿る道は、実際に天使がその立方体に到達するまで決まらず、さらにそこに至っても大まかに決まるだけとなる。この性質によって悪魔は十分離れたところから天使の通る道筋を狙ってブロックを置くことができなくなる。

悪魔が天使の通る道にある安全な立方体を危険な状態にするまでにかかる時間が、天使がその立方体に到達する時間より長いと証明されることでこの戦略の有効性が示される。

この証明は2006年に Imre Leader と[[ベラ・バラバシ]]によって公表された<ref name="BandL"/>。また、実質的に似た証明が2005年に Martin Kutz によってなされている<ref name="kutz2004" /><ref name="kutz2005">Martin Kutz, Conway's Angel in three dimensions, ''Theoret. Comp. Sci.'' 349(3):443&ndash;451, 2005.</ref>。

=== Mathe による2の力の天使の証明 ===

Máthé<ref name="M"/> は''行儀のよい悪魔 (nice devil) ''の概念を作った。この悪魔は、かつて天使がいた場所および一つ前の手で天使が行くことができた地点にはブロックを置かない。天使がこの悪魔を相手にする場合には、悪魔の勝利条件を「盤上の有界領域に天使を閉じ込められたか」とする（でなければ、天使はある二地点を延々と行き来するだけで勝利できてしまう。天使が勝つには、その領域から抜け出る必要がある）。証明は大きく二段階からなる。

# 行儀のよい悪魔に勝つ天使は、本物の悪魔にも勝てる
# 行儀のよい悪魔に対する明示的な必勝法を示す

二つ目の部分は、天使は（すでに置かれているブロックに加えて）西側の面がすべてブロックされたと仮定して、そのブロックを迷路の壁と見立てて[[迷路#右手法（左手法）|左手法]]によって迷路の中を進む。つまり、天使は左手を迷路の壁において、壁に沿って進んでいく。この戦略を取る天使を行儀のよい悪魔は捉えられないことが示せる。

一つ目の部分は[[背理法]]によるため、この証明からは本物の悪魔に対して直ちに明示的な必勝法を得ることはできない。ただし、Máthé は論文の中で原理上はこの証明から明示的な戦略を導き出すことができるだろうと述べている。

=== Bowditch による4の力の天使の証明 ===
Bowditch<ref name="B"/> は元のゲームに対する変種（game 2）としてルールに次の変更を加えた。

# 天使はかつて行ったことのあるいかなる地点にも戻ることができる（その後、悪魔によってブロックされようとした場合であっても）
# k-悪魔は、ある場所にブロックを置こうとするなら k 回そこにブロックを置こうと試みる必要がある
# 天使は東西南北のひとつ隣にだけ動ける
# 天使が勝つには"回り道"をする必要がある

"回り道"は <math>\pi = \cup^{\infty}_{i=1} (\sigma_i \cup \gamma_i)</math> で定義される[[道 (グラフ理論)|道]]である。ここで <math>\sigma = \cup^{\infty}_{i=1} \sigma_i</math> は半無限の弧（自身と交差しない道で、開始点はあるが終了点が存在しないもの）であり、 <math>{\gamma_i}</math> は[[素集合|互いに素な]][[閉路]]で次の性質を満たす。

* <math>\forall i: |\gamma_i|\leq i</math> で <math>|\gamma_i|</math> は i 番目の閉路の長さを示す。

（[[Well-defined]] であるために、<math>\gamma_i</math> はその開始・終了点が <math>\sigma_i</math> の終了点と同じでなければならず、<math>\sigma_i</math> は <math>\sigma_{i+1}</math> の開始点で終わらなければならない。）

さらにもうひとつゲームの変種（game 1）を考える。game 1 は上記のルール2と3を取り入れたもので、3では5-悪魔の存在を仮定する。論文では、この game 1 について天使の必勝法があれば、それは元のゲームで4の力の天使の必勝法も存在することを示す。そして、game 2 における5-悪魔に対しては、非常に単純なアルゴリズムで天使が勝利できることを示す。

以上をもとに、元のゲームでは4の力の天使は、game 2 における5-悪魔に対する仮想の天使を想像することで悪魔に勝てることを示す。

天使は仮想の天使の道を辿るが、閉路 <math>{\gamma_i}</math> は避ける。<math>\sigma</math> が半無限の弧であるために天使はかつて自らが通った場所には戻らずに進むことができる。

== 関連項目 ==

* Homicidal chauffeur problem として知られる数学上の問題は、同様に高い能力と機動性のあるプレイヤーと、資源は豊富だが力は弱いプレイヤーの間のゲームである。

== 参考文献 ==
{{reflist}}

== 外部リンク ==
* [http://www.msri.org/publications/books/Book29/files/conway.pdf The Angel problem by John H Conway]
* [https://web.archive.org/web/20080702081929/http://home.broadpark.no/~oddvark/angel/index.html Kloster's Angel Problem site]

{{デフォルトソート:えんしえるふろふれむ}}
[[Category:ゲーム理論]]