Angel Problem

“The angel problem is a question in game theory proposed by John Horton Conway.[1] The game is commonly referred to as the Angels and Devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), specified before the games starts. The board starts empty with the angel at the origin. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king. i.e. The distance from the starting square is at most k in the infinity norm.) The devil, on his turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely.”

“The angel problem is: can an angel with high enough power win?”

“There must exist a winning strategy for one of the players. If the devil can force a win then he can do so in a finite number of moves. If the devil cannot force a win then there is always an action that the angel can take to avoid losing and a winning strategy for her is always to pick such a move. More abstractly, the "pay-off set" (i.e., the set of all plays in which the angel wins) is a closed set (in the natural topology on the set of all plays), and it is known that such games are determined.”

“Conway offered a reward for a general solution to this problem ($100 for a winning strategy for an angel of sufficiently high power, and $1000 for a proof that the devil can win irrespective of the angel's power). Progress was made first in higher dimensions, with some beautiful proofs. In late 2006, the original problem was solved when independent proofs appeared, showing that an angel can win. Bowditch proved that a 4-angel can win[2] and Máthé[3] and Kloster[4] gave proofs that a 2-angel can win.”

Quoted from Wikipedia
http://en.wikipedia.org/wiki/Angel_problem

Contribute!

Know how math applies to real life, a new discovery in math, a math tidbit or an unsolved math problem? Submit a "Did You Know?" entry to the site!

You must be signed in. Don't have an account? Register here!

The most common question students ask math teachers at every level is “When will I use math?” WeUseMath.org is a non-profit website that helps to answer this question. This website describes the importance of mathematics and many rewarding career opportunities available to students who study mathematics.


 

Attorney
$187,199/yr
Physician
$187,199/yr
$126,000/yr
Cryptanalyst
$137,780/yr
Actuary
$160,000/yr
Hydrologist
$112,490/yr
Statistician
$199,710/yr
$128,610/yr
$139,670/yr

Figures represent salary potential.

20
May

Dr. Cary Oberije, a postdoctoral researcher in The Netherlands, has found that mathematical models can be used to accurately predict patients' responses to treatment. Prediction models were used to analyze lung cancer patients' likelihood of survival and...

read more