エンジェル・プロブレム
エンジェル・プロブレム (angel problem) はジョン・ホートン・コンウェイによって提起された組合せゲーム理論の問題である。一般に天使と悪魔 (Angels and Devils) ゲームとも呼ばれている。ゲームは、天使と悪魔と呼ばれる二人のプレイヤーによって、無限の広さのチェスボード（正方格子）の上で行われる。ゲームの開始前に、天使は力"k"（"k"は正の整数）を持つことを決めておく。開始時点で盤上には天使がひとつの場所にいるだけで他は空である。天使と悪魔は交互に手順が回ってくる。天使は、自分が今いる地点からチェビシェフ距離で最大"k"の範囲内にある空いている地点へジャンプする。悪魔は、天使のいない任意の地点にひとつブロックを置く。天使はブロックを飛び越えることはできるが、ブロックの上に乗ることはできない。天使が動けなくなったら悪魔の勝ちとなり、無限に動き続けることができれば天使の勝ちである。
このとき、十分な力を持つ天使であれば悪魔に勝てるだろうか。
このゲームには必ずどちらかのプレイヤーに必勝法が存在する。もし悪魔に必勝法があれば、有限の手数でゲームは終わる。もし悪魔に必勝法がなければ、天使は常に自分が負けないように手を選ぶことで無限にゲームを続けることができ、勝敗の定義からそれが天使の必勝法となる。より抽象的には、天使の勝つすべてのゲームプレイの集合は、すべてのゲームプレイの自然な位相空間に対して閉じている、つまりゲームは決定的である。当然ながら、無限に続けられるあらゆるゲームはプレイヤー2が必勝法を持たないときプレイヤー1は自らが負けないような手を選び続けることができるが、ゲームの勝敗の定義次第では単にゲームを無限に続けることがプレイヤー1の勝利になるとは限らない。したがって、決定的でないゲームが存在する可能性はある。
コンウェイはこの問題に対する回答に賞金を与えると宣言した（十分な力を持つ天使の必勝法に100ドル、天使の力によらず悪魔が勝つと示すことができれば1000ドル）。当初は、チェスボードを三次元に拡張した問題に対する進展が見られた。オリジナルの（二次元の）問題では、2006年後半に、独立した複数の証明によって天使の勝利が示された。Bowditch は4の力を持つ天使が勝つことを証明し、Máthé と Kloster は、力が2あれば十分なことを示した。