Talk:Angel problem

Defn of distance

Is the power measured as Pythagorean or New York distance? Or some other metric? -- The Anome 10:55, 17 Oct 2004 (UTC)

New York distance. It doesn't matter though for the purposes of the angel problem. Barnaby dawson 14:26, 17 Oct 2004 (UTC)

See Conway's 1996 paper. Rich Farmbrough, 15:41 12 October 2006 (GMT).

According to the current text, it's neither of those two, but rather the sup norm. But I don't see why you say it wouldn't matter -- the 2d game is now known to be a win for the devil if the angel has power 1 (8 reachable cells), and a win for the angel if she has power 2 (24 reachable cells). That would seem to leave two intermediate cases: power 2 with Manhattan norm (12 reachable cells), and power sqrt(5) with Euclidean norm (20 reachable cells). Do we know the outcome of those two games, or are they still open? Joule36e5 (talk) 22:18, 11 December 2008 (UTC)

The second of these intermediate cases is a win for the Angel. It is remarked in my (Kloster's) paper (but perhaps unclearly) that the angel never needs to perform a diagonal move of length 2sqrt(2). And in fact, Johan Wästlund has proved that an angel with power 2 in the x direction and 1 in the y direction (14 reachable cells) can win. Okloster (talk) 19:23, 11 January 2009 (UTC)

Lower bound for C in 3D case?

Is there a known lower bound for the angel's power C in the three-dimensional case so that the angel has a winning strategy? I.e., is a number c known such that a winning strategy exists for all C >= c? -- Schnee 00:04, 25 Oct 2004 (UTC)

My seminar notes say that it works in general (The qualifier 'For high enough powered' is not necessary). I put it in to start with as I didn't have the notes to hand. Also adding further proved result. Barnaby dawson 14:27, 31 Oct 2004 (UTC)

13 is such a lower bound (details). Smaller values should not be too hard to obtain, at the cost of more involved arguments. -- AgentM 11:45, 5 Nov 2004 (UTC)

Cool, thanks. I'll check out that dissertation. ^^ -- Schnee 18:28, 5 Nov 2004 (UTC)

Further to discussion with Imre leader the proof is not known to generalise to C lower than 13. The link given above shows that the proof works for 13 and above. I've corrected the text. Barnaby dawson 23:02, 5 Nov 2004 (UTC) (I don't normally edit on weekdays but I felt I should correct my own error).

Multi-dimensional angels

Shouldn't Tom Körner be credited for the proof? Gdr 19:41, 2004 Nov 7 (UTC)

As I understand Tom Körner showed that for high enough dimension the angel can escape but not for 3 dimensions. Imre Leader gave a seminar about his proof which Tom Körner knew about (They are in the same department). But Tom did not ask for credit. So probably not. This other guy who published the paper linked to above should probably be mentioned though. I'll do that. Barnaby dawson 21:39, 7 Nov 2004 (UTC)

So doesn't Körner deserve credit for the "high enough dimension" step? Gdr 00:23, 2004 Nov 8 (UTC)

The Natural Topology on the Set of all Plays

Hello, the above was referred to in the article. Which topology is that? --AlephNull 16:08, 25 November 2005 (UTC)

Further, in the same paragraph, it would help simply to define the word play. I just found myself writing paragraphs of speculation... Fun but eventually annoying... Orthografer 23:42, 15 August 2006 (UTC)

I've been told following standard teminology: a game is a set of rules, as chess and go are games. A play is the result of actually playing the game once. A move is an action of one player in a game, like e4, a move that in chess notation means "move pawn to the square e4." In a game that allows infinitely many moves, we normalize by making illegal moves possible (automatically giving a win to the other side) and padding each play that has finitely many moves by adding infinitely many irrelevant moves that don't change the outcome of the play. Thus any move is possible regardless of circumstance within the play, and all games are infinite. It is a fact that this normalized set P of plays is the product of a countable sequence of copies of the set M of moves. We give M the discrete topology and P the product topology. Orthografer 19:21, 25 August 2006 (UTC)

Style

Hi Barnaby I made the edit, because I thought it would be clearer to a lay person who would have no idea what "the angel has power k" means. They might think it means something like in a role playing game. So, I think it's more than style, it's about a better understanding for the reader. Hope you can live with my edit. Mccready 01:49, 30 April 2006 (UTC)

Resolved?

A paper from Prof. Bowditch of the University of Southampton, claiming a winning strategy for the 4-Angel:

http://www.maths.soton.ac.uk/staff/Bowditch/papers/bhb-angel.pdf Nchua 01:00, 9 September 2006 (UTC)

I shall have a look at this paper today and change the article if appropriate. Barnaby dawson 08:42, 9 September 2006 (UTC)

It's still a preprint, from what I can tell. I doubt you will find an error so readily, and in any case WP:NOR means reviewing this paper is pointless. It's definitely worth mentioning, given that Bowditch is a highly respected mathematician, so his claim of a proof is notable. Bowditch's abstract also mentions that Kloster has a proof for the 2-angel, but I can't find a written proof using Google. --C S (Talk) 11:41, 9 September 2006 (UTC)

Almost half way through the paper. Is really quite interesting. I'm not going to claim just because I've read it and failed to find an error that its valid. But I might put up an outline of his approach once I've read it. Hence reading it is worthwile (even just for wikipedia's sake).

Also I don't recall WP:NOR stating that you couldn't assess the reliability of a source. I think that's kind of crucial. At the very least with a mathematical breakthrough that must mean reading through the proof (where you can understand it). You'd be right of course that that isn't enough to conclude a source is reliable. Barnaby dawson 16:37, 9 September 2006 (UTC)

I've finished reading the paper. It's a lovely argument and quite accessible. It requires a tiny bit of knowledge in graph theory but is almost all from first principles otherwise. I'm betting this proof is correct. I will now add a section with some notes on the claimed proof. Barnaby dawson 13:32, 12 September 2006 (UTC)

Verified

I have removed the not verified message. The anonomous editor who added it did not specify what information in the section was not verifiable. For the record all the results in there (apart from the recent proof claims) come from the notes I took at a seminar on the angel problem (including a solution for the 3D case) given by Imre Leader. I have seen proofs of all of them bar the last. We might not be able to find these proofs in print. Barnaby dawson 08:01, 30 September 2006 (UTC)

Avoiding interference with the academic process

I have removed a sentence saying that two of the claimed proofs have been accepted in a peer reviewed journal on the suggestion of the author of one of them. He felt that this was not normally general knoledge and that it might seem to give priority to those solutions. Barnaby dawson 13:08, 2 October 2006 (UTC)

Well, that's very nice of him, but really priority isn't based on publication date, as well he knows. A more important issue is that we need to provide important information like this to our readers as appearing in some peer-reviewed journal is an integral part of whether the general reader will accept something to be solved or not. For example, I had to revert an edit from another article that removed a description of the problem as "solved". But it's solved by reasonable standards. It would be absurd to not provide this info and wait until all these solutions get published or an author retracts his paper. So I'm going to reinstate the information on publication. --C S (Talk) 12:41, 13 May 2007 (UTC)

The Bowditch and Máthé papers have been published in the May issue of Combinatorics, Probability and Computing. So the justification for removing the info (that it is not generally known info) is not really a good one anymore. --C S (Talk) 12:51, 13 May 2007 (UTC)

Remove unsolved tag?

Is this still supposed to have the "Unsolved Problems" tag? The article states flatly in the end of the introduction that the problem is solved, but later doubt is raised as to whether the proofs actually work. --Whiteknox 12:37, 28 July 2007 (UTC)

Different powers of angel and demon?

After reading the article, I was still uncertain about the status of the 2D problem. Suppose the angel has power k and the devil has power m. What is the result of the game for different values of k and m?

As I understood: k=1: Devil wins (Conway) k>=2, m=1: Angel wins. (Máthé, Bowditch)

How about the cases k>=2 and m>=2? Were these results proved too or are they still open? There must be some limit, i.e. even if the angel has power 1000, if the devil has enough power (take 10^10 for example), he can bound the angel. —Preceding unsigned comment added by 212.50.147.101 (talk) 07:36, 26 October 2007 (UTC)

When k>=2*m, the angel wins. After the devil has blocked m squares, the angel pretends that the squares were blocked one by one in some sequence and that m 2-angel moves were interleaved, as in the k=2, m=1 game. She then jumps to the square where she would end up if she followed her winning strategy in this imagined sequence.

When m>=k*k, the devil wins, by identifying areas of k by k squares on the real board with the single squares on an imagined board, where he plays using Berlekamp's strategy for trapping a king. Okloster (talk) 19:49, 11 January 2009 (UTC)

the article is a bit unclear. it doesn't mention the idea of the devil having power except in the part about bowditch's proof. I assume the power of the devil means the amount of blocks he can lay per turn? 67.176.160.47 (talk) 07:11, 19 March 2010 (UTC)

3-D angels

Does anyone know whether a 1-angel can win in 3 dimensions? --128.12.103.70 (talk) 19:36, 15 April 2008 (UTC)

If he has power 2 or more, he wins in 2 dimensions and therefore in 3. With power of 1 in 3 dimensions, I don't think it was solved. Anyone know a file that allows me to play the angel problem on either side and can be downloaded for free? srn347

The 1-angel wins in 3D. See [http://home.broadpark.no/~oddvark/angel/variations.html] Okloster (talk) 20:00, 11 January 2009 (UTC)

Description and Illustration

In Conway's paper the Devil is described as destroying or "eating" squares. But in the description here the squares are said to be "blocked". I think the original language should be preserved. Likewise, most descriptions follow Conway in describing the game as taking place on a checkerboard-style grid of squares, but the illustration here shows a Go-board style grid of intersections. The change is unnecessary and potentially confusing. One of the hallmarks of the original problem is its vivid and memorable imagery, I think the presentation here should preserve this. 67.83.200.217 (talk) 05:21, 19 April 2009 (UTC)

Proof that the Devil wins againts a 1-Angel in 2D?

The article contains some sketches of proofs for complex cases like a "high-powered 3D angel", but there is no indication of the proof for what I believe is the simplest case, the 1-angel in 2D. The article states that in this case the Devil wins, but wouldn't it make sense to have at least a sketch of this proof (or if it is too complicated, at least an indication of this)? 80.194.194.190 (talk) 09:29, 21 August 2009 (UTC)

?? Is this poorly explained or the easiest problem ever??

How did anyone ever publish a paper on proving (say) the 4-angel? If I'm the angel, and my coordinates are the origin, I can just move 4 spaces to the top-right every turn and run away from the devil. If he blocks that one square, I'll just move four spaces to the top-left instead. In fact, I can't see how for any power, even 1, the devil has a prayer of winning. I feel this article must be really poorly explaining something because it seems a joke otherwise. Red Slash 23:57, 13 May 2013 (UTC)

Your suggested strategy of heading in one direction if possible otherwise turn doesn't work as the devil can just set up a trap as far in advance as it needs. The difficulty arises from needing to avoid such traps. 121.45.39.192 (talk) 02:32, 21 April 2016 (UTC)

Win for the Devil

The proof that the 1-angel loses to the devil is quite easy, and it's found in Kutz's PhD paper (first few pages) http://www.mpi-inf.mpg.de/alumni/d1/2009/mkutz//diss/kutz_angel.pdf — Preceding unsigned comment added by 2.24.200.212 (talk) 00:39, 12 December 2013 (UTC)

infinite devils

"If we have an infinite number of devils each playing at distances d_1 < d_2 < d_3 < \cdots then the angel can still win if it is of high enough power." This is obviously not true. For a given power k, there is a distance d where 8*k^3 devils can play. So if the angel goes that far out it can be trapped in one turn. So the angel is bounded and can be trapped by randomly adding blocks until it can't move. Folket (talk) 13:10, 1 April 2014 (UTC)

Is Gacs’ proof correct?

I recently read through all four claimed solutions to the Angel Problem. I am confident that Kloster’s proof and Máthé’s proofs are correct. Kloster’s proof is the cleanest, simplest, one of the two strongest ones ($k=2$), and of the two strongest proofs, the only one that directly provides a constructive algorithm. This article should therefore be updated (either by me or someone else) to include a description of this solution. Bowditch’s proof also seems correct (although it’s more complicated), but actually only proves the $k=9$ case, not the $k=4$ case, since Lemma 3.7 (in the journal version; Lemma 2.7 in the arXiV version) is incomplete.

I spent quite a bit of time trying to read Gacs’ proof and found a potentially problematic section. Lemma 4.4 states, “Using the fact that the angel’s current position is in a (−1)-safe cell”; I do not know how to verify this claim though, especially since Lemma 4.4 doesn’t seem to make any reference as to the actual position of the angel at this time, merely about which cells are currently “clean” and “safe,” and I was also unable to verify that this claim is correct in general. I emailed Professor Gacs last month and he said he didn’t remember the proof in enough detail to answer my question.

I know this constitutes original research, and I am not a professional mathematician (I’m a software engineer); is there any way to update the article with this information? If anyone else has read these proofs, did you notice the same issues? rdl381 (talk) 07:43, 29 October 2022 (UTC)