エンジェル・プロブレム
エンジェル・プロブレム (angel problem) はジョン・ホートン・コンウェイによって提起された組合せゲーム理論の問題である。一般に天使と悪魔 (Angels and Devils) ゲームとも呼ばれている。ゲームは、天使と悪魔と呼ばれる二人のプレイヤーによって、無限の広さのチェスボード(正方格子)の上で行われる。ゲームの開始前に、天使は力k(kは正の整数)を持つことを決めておく。開始時点で盤上には天使がひとつの場所にいるだけで他は空である。天使と悪魔は交互に手順が回ってくる。天使は、自分が今いる地点からチェビシェフ距離で最大kの範囲内にある空いている地点へジャンプする。悪魔は、天使のいない任意の地点にひとつブロックを置く。天使はブロックを飛び越えることはできるが、ブロックの上に乗ることはできない。天使が動けなくなったら悪魔の勝ちとなり、無限に動き続けることができれば天使の勝ちである。
このとき、十分な力を持つ天使であれば悪魔に勝てるだろうか。
このゲームには必ずどちらかのプレイヤーに必勝法が存在する。もし悪魔に必勝法があれば、有限の手数でゲームは終わる。
問題の初出は1982年のWinning Waysという本で、そのときは "the angel and the square-eater" という名前で発表された。 二次元の場合、初期の部分的な成果には以下のようなものがある。
1の力の天使に対しては、悪魔に必勝法がある (Conway, 1982) (コンウェイによればこの成果は実際はエルウィン・バーレカンプに帰する)。この証明は Kutz の論文の1.1節に見ることができる。
天使が南の方角に一度も進むことがないなら、悪魔に必勝法がある (Conway, 1982) 。
天使が常に初期地点から離れるように進むなら、悪魔に必勝法がある (Conway, 1996) 。
三次元の場合は、下記が示されている。
天使が常に北の方角に進み、悪魔はひとつの平面上でしかプレイしなければ、天使に必勝法がある。
天使が常に北の方角に進み、悪魔はふたつの平面上でしかプレイしなければ、天使に必勝法がある。
天使の力が13以上であれば、天使に必勝法がある。