Presentation Transcript
The Angel Problem : The Angel Problem John H. Conway
Presented by
Aaron Nickel and Carson English
How to Play : How to Play The angel and the devil alternate turns on an infinite chess board
The angel move to any square in (for example) 1000 kings moves of its position
The devil moves by eating away any square
The angel wins if he can move forever
The devil wins if he strands the angel
Can the angel defeat the devil? : Can the angel defeat the devil? Berlekamp has proven a chess king can be defeated on a 32 x 33 board
That’s about all we know.
Conway is offering cash to solve the problem
Flawed Potential Strategies : Flawed Potential Strategies Potential Functions
Overly Sensitive
Counter Strategy
Depends on Angel’s
Only Fools Rush In : Only Fools Rush In A fool is an angel that is required to increase his y-coordinate.
Theorem: A devil can catch a fool
Slide6 : As the angel moves, he is confined to smaller and smaller areas.
Lax Fools : Lax Fools Non-decreasing in one direction
Convert to Plain Fool
Of much higher power
1,000 becomes 8,000,000,000
Can still be trapped
A Lax Fool traveling north : A Lax Fool traveling north
Relaxed Fools : Relaxed Fools Fool has a Limited Decrease
Convert to Plain Fool
Of even higher power
Can trap any size laxity
Funneling the Relaxed Fool : Funneling the Relaxed Fool
Out-and-Out Fools : Out-and-Out Fools Distance from start strictly increases
Divide plane into sectors
Divide moves among sectors
Relaxed Out-and-Out Fool
The Kaleidoscope Strategy : The Kaleidoscope Strategy
Diversion : Diversion Theorem: For each point P and distance D, no matter how the angel moves, there will be two times at the latter of which the angel will be at least D units nearer to P than he was at the former.
His Own Worst Enemy : His Own Worst Enemy Angel eats millions
Burn every space he could have moved to
Is no worse than before for the angel
Angel returns to area finite times
Better for angel to not return
Before you sell your soul… : Before you sell your soul… While the diverting strategy goads the angel into where he might not want to go, in arbitrarily large journeys, the diversion will appear inconsequential.
Conclusion : Conclusion Still unproved either way
Prizes available
$100 for Angel
$1000 for Devil
Catch the
buzz on authorSTREAM
Copyright © 2002-2008 authorSTREAM. All rights reserved.