"守護者"の証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/01 14:16 UTC 版)
「エンジェル・プロブレム」の記事における「"守護者"の証明」の解説
三次元の場合に力のある天使が必勝法を持つことの証明は"守護者 (guardian) "という概念を用いる。盤上の任意の大きさの立方体に、その立方体を監視する守護者を置く。守護者はプレイヤーの手番ごとに自分の監視している立方体が"危険"、"安全"、"ほぼ安全"のいずれなのか判断する。"安全"と"ほぼ安全"の定義は証明が成り立つように選ばれており、この判断は純粋に立方体のサイズとそこに含まれるブロックの密度によって決まる。 天使は指示が与えられなければ、上にジャンプし続ける。天使のいる立方体のいくつかが安全でなくなったとき、そのうち最大の立方体を監視する守護者は天使がその立方体のいずれかの辺を通って立方体から離れられるように指示される。守護者が立方体のある面から抜け出るように天使を導くには、その立方体に含まれる小さくすべて安全な立方体群を辿るようにする。各立方体群の守護者は同様に繰り返して天使を導く。天使がある立方体の中を辿る道は、実際に天使がその立方体に到達するまで決まらず、さらにそこに至っても大まかに決まるだけとなる。この性質によって悪魔は十分離れたところから天使の通る道筋を狙ってブロックを置くことができなくなる。 悪魔が天使の通る道にある安全な立方体を危険な状態にするまでにかかる時間が、天使がその立方体に到達する時間より長いと証明されることでこの戦略の有効性が示される。 この証明は2006年に Imre Leader とベラ・バラバシによって公表された。また、実質的に似た証明が2005年に Martin Kutz によってなされている。
※この「"守護者"の証明」の解説は、「エンジェル・プロブレム」の解説の一部です。
「"守護者"の証明」を含む「エンジェル・プロブレム」の記事については、「エンジェル・プロブレム」の概要を参照ください。
- "守護者"の証明のページへのリンク
