ANAMIKA

'(The Blog) With No Name', perhaps best described as a stream of notes and thoughts - 'remembered, recovered and (sometimes) invented'.

Tuesday, October 11, 2005

Reflections On 'Angel Problem'

These are speculations on possible connections between critical phenomena (from Physics) and John Conway's 'Angel problem' (from game theory). The following two pages introduce the problem:

www.mathworld.wolfram.com/AngelProblem.html
www.msri.org/publications/books/Book29/files/conway.pdf

In brief, the 'Angel' and the 'Devil' play a game on a 2d infinite chessboard; the Angel tries to escape and the Devil tries to trap him in some finite region. On a 1d lattice the devil wins trivially. In 3d, the
Angel has plenty of space to move (it seems). but 2d remains open - nobody knows if the Angel can surely escape or the Devil can definitely trap him. Fuller details are in above sources, especially the latter.

My doubt: Are there connections between some statistical mechanics model (possibly possessing criticality) and the Angel problem?

As far as I know, one strong (if not defining) feature of criticality is the absence of a length scale in the system and it appearing the same at all length scales - in other words it is a fractal. An example would be a water-steam mixture at critical point - every bubble of steam would contain water drops of arbitrary sizes suspended within each of which would contain steam bubbles of arbitrary sizes and so on...

Conway's paper mentioned above (evocatively) describes a path on a 2d board which can give the Angel *some chance* of escape - this path (sections 7 and 9 of the paper) appears to show fractal property. So, one feels the system is critical (a leap there - and a gap in my understanding! the possible trajectory of the Angel is possibly fractal; not necessarily the system) - there presumably is some mapping between some statistical model that exhibits criticality and the game. Moreover, there is a general *promising* strategy for the Angel, attributed to Korner (and mentioned in Conway's paper) which seems to sweep over all length scales of the system - reminiscent of Scaling theory (?).

There is the issue of interpreting the criticality (of course, assuming it exists in 2d Angel problem). The guess is that the scenario is somewhat like this:

- If the game were played on a 1d lattice, whatever the Angel does, the Devil traps him with infinitely many moves to spare.
- In a 3d lattice of cubes , the angel can win and at every stage he has many cubes to move into and his path can fill a 3d subspace of the full space.
- In 2d chessboard , the situation is perhaps *critical* - the angel can avoid getting trapped but gets confined to a fractally subspace of the 2d
space; he needs to stay on and move on a 1-d fractal and any deviation from this path traps him.

I guess phenomena such as 'Percolation' and 'Anderson localization' in statistical mechanics (the essential nature of both phenomena show dependence on the dimension of the system; I guess the former is a classical phenomenon and the latter is quantum - not sure about the essential difference) might have some relvance to the Angel's quest for free movement.

One also wonders whether the fractal path of the Angel in 2d is like a 'strange attractor'. I have also seen (not understood) 'cool' phrases like 'fractal wave packets'. Any possible links with these thoughts ..? Or is it that the above is 'not even wrong' to borrow Pauli's phrase?!

3 Comments:

  • At 7:48 PM, Anonymous Anonymous said…

    Nice info! The One dimensional case I understand, but is it proved that in the 3D case, the angel can escape?

    I don't get it when the paper says that the devil can defeat a chess king on any board of size at least 32x33. We are given the board to be infinite!

     
  • At 9:25 PM, Blogger R.Nandakumar said…

    Vishnu, thanks for your interest.

    i don't know the details of the 32X33 board. the gist of it is probably that EVEN with such a small board, the devil can eat enough squares to trap the angel - even the devil needs space to build his trap and that much of room suffices, if the angel's power is limited. with power 1, the angel will need something like 16 moves to reach the boundary at the least and within that time, the devil can have his trap ready - and crucially the trap needs only to be of 'thickness' only 1. perhaps the result could be rephrased: on an infinite 2d board, the devil can catch the angel of power 1 within a 32X33 rectangle around the origin - no elaborate chase stretching over light-years.

    as for 3d, i have seen a proof somewhere online (cant recollect where, sorry) that an angel of power at least 13 can certainly escape. it was just my speculation that the angel can escape in 3d and also move in a full 3d subspace of the 3d space without being caught.

     
  • At 6:08 AM, Blogger enu said…

    angel of power 2 problem was solved in 2006
    see
    http://en.wikipedia.org/wiki/Angel_problem

     

Post a Comment

<< Home