Fog Creek Software
Discussion Board




Escaping the field: Man vs. God

There is a man standing inside an arbitrarily shaped field.
He wants to escape the field – that is to reach any place outside the field area.

He can do that in steps. Each step is a move from his current place to any place that is one unit (say, meter) apart.

The God watches man’s attempts and tries to prevent him from escaping the field. The God can read man’s mind and intervene, if he chooses so. The divine intervention could be in a form of changing the direction of the man’s move to the opposite. Say, if the man intended to move North-North-West, and the God decided to intervene, the man finds himself one meter away from his previous position, South-South-East. If the God decided not to intervene, the man moves North-North-West, as he intended.

Can the man escape the field? If yes, show how. If no, prove it.

Dmitri Papichev
Tuesday, February 01, 2005

I'll assume the person wants to get as far away from his starting point as he can.  In this case he wants to increase his radius every step of the way.

Step 1: Pick a direction and go there.  Doesn't matter what God does, he'll be 1 unit from where he was.

Step 2 - N Untill outside of the field: Pick a vector 90 degrees from the vector made from his current position and his start position.  Walk one unit in that direction.  It doesn't matter which choice God uses, the ending position will still be farther away than his past position.


or he can simply kill himself.

zekaric
Tuesday, February 01, 2005

If the divine intervention can take any form then the answer is clearly no. The God might decide that the intervention will be of the form of never letting the man move at all, in which case he can never escape the field. QED.

Let's say that the God's powers are limited to changing the direction of the move to anything the God likes, but still 1m away. Then the answer is still no, provided there is at least one point 1m away from the start that is inside the field. The God then alternates between forcing the man to that point, and then forcing him back to his start point.

If, as I suspect, the God is limited to allowing the man to make his move, and forcing him to make the opposite.... well I'll have to think about that.

David Clayworth
Tuesday, February 01, 2005

Of course, the God is almighty, but he just decided to limit his intervention here to changing the direction of the man's move to the opposite. The man always moves, but if the God intervenes, he moves to the opposite of his intended direction.

Dmitri Papichev
Tuesday, February 01, 2005

"Step 1: Pick a direction and go there.  Doesn't matter what God does, he'll be 1 unit from where he was. "

"Step 2 - N Untill outside of the field: Pick a vector 90 degrees from the vector made from his current position and his start position.  Walk one unit in that direction.  It doesn't matter which choice God uses, the ending position will still be farther away than his past position."

I see the man walks in a square when using this strategy.

JHY
Wednesday, February 02, 2005

If the God only either allows the man's own choice, or reverses the direction, then I bow to zekaric's solution.  Good puzzle, and a good solution.

David Clayworth
Wednesday, February 02, 2005

Not a square.  More of a spiral around the starting point. 

Think concentric circles.  The man wants to increase the radius of every new circle made from his point with the starting point after each step.  To do guarantee this he needs to travel along the tangent.  It's a slow expansion the further he goes out but he will keep increasing the radius every step.  So if there is a finite bound to the field then the man will make it out the field.

The proof would to be to prove that the hypotenuse of a right angle tirangle is always longer than the other two sides.  I hate proofs but I figure you can prove it by induction or something.  Been so long since I had to prove anything. :P

zekaric
Wednesday, February 02, 2005

Sorry, if you draw a line of the path he takes it'll look like a spiral or spiral in nature depending on how god plays with him. :)

zekaric
Wednesday, February 02, 2005

I get it now.  I was not reading carefully enough and intepreted the new vector is 90 degrees from the last vector.

JHY
Wednesday, February 02, 2005

Just need to say "finite field" in the problem (may be add "plane" somewhere - I'll explain later) and after some proof zacaric's solution will be ok. Strict proof will give you something like ln(N) distance from starting point at step N, which has no upper limit.

If it's not planar - Northern Hemisphere will be the field man can not escape. If it's infinite... well, you've got the point ;)

Nice riddle, BTW

DK
Thursday, February 03, 2005

OK, now we know how the man can do that.

Now the next question: how to optimize the man's escaping strategy?

Dmitri Papichev
Monday, February 07, 2005

Optimizing is tricky.  If you consider a circle, and you start at the center, I think it's clear that Zekaric's algorithm is optimal, and it will take R^2 steps (it's not exponential as DK suggested).  But for arbitrarily-shaped regions, it's tougher.  I haven't figured it out, but Zekaric's algorithm I think clearly gives only a lower bound; I think you can do better.  This is because his algorithm relies on getting away from the starting point, not getting to the closest boundary.
Interesting problem...  I'll give it some more thought.

Brian
Tuesday, February 08, 2005

Sorry, Brian, I'm too lazy to actually go and proof if the distance from starting point in zekaric's algorithm will be big O from sqr(N) or ln(N), not right now anyway. Logarithm just popped up after checking one or two elements in series and as someone noticed here the trajectory will be kind of spiral.

However I can not see, that zekaric's is "obviously" the best approach to minimize steps, can you elaborate on this?

DK
Tuesday, February 08, 2005

Hmm, sorry again, Brian - I need  to learn to read more carefully - you were referring to circular field.

We can assume God plays to maximize number of man's steps and try to solve the problem without complex math.

I'm thinking this way - let's say we have original field F1 and within it we somehow are marking smaller field attached to F1 boundary - set of all points from where man can escape in one step. The rest of F1 we call F2. Applying same operation to F2 we will get F3, etc, etc till we have our starting point in some FN, but not in FN+1. N will be the number of required steps.

To make it "the proof" we'll need three things:
1) provide method to build F2 by F1
2) show F2 will be substantially less than F1 that is max N has it's  limit
3) prove God can force man to make at least N steps

I'll stop here for now, have fun ;)

DK
Tuesday, February 08, 2005

I don't see how you would be able to optimize it.  You have a few problems that are undefined. 

1.  What is the shape of the boundary?  Depending on the shape you 'might' be able to put GOD into a no a situation where you win no matter what but the shape has to be specific.

2.  How smart is God.  If he's really really smart then he can easily point you in the direction of the farthest side and keep you going in that direction and also make you avoid the special cases in 1.

Whatever the solution the length of the users path to the border is going to be constant.  Optimization seems a tad pointless and can't be done (I think) because of these unknowns.  What would be a better question is, given the distance to the perimeter, how many steps will he need to take?

But Biran already gave the answer, Distance to perimeter squared.

zekaric
Tuesday, February 08, 2005

Does anyone mind if we stop calling it God vs. Man?  It's really wierd - this is math, not religion.  It's just a 2 player game, where player 1 is trying to create a sequence of points p_1, p_2, ... that escapes a region R.  At each turn, he creates a unit direction vector e_i, and player 2 chooses either p_i = p_i-1 + e_i or p_i = p_i-1 - e_i (these are vectors).
Player 1 wants to select the e_i to end the game as quickly as possible.  Player 2 wants to the game to go as long as possible.

zekaric:  I don't understand your recent question 1.  We've already established that given a bounded region R there exists a strategy so that the game ends in a finite number of turns.  That is, in the new notation, there exists an n with p_n outside R, regardless of the strategy of player 2.  Obviously, player 2 will try to "steer" the sequence to the furthest corner of R - that's how he extends the game.

DK: using the strategy of selecting e_i normal to p_i - p_0 (this is zekaric's algorithm) takes r^2 because it builds a bunch of right triangles.  Pythagoras tells you that hypotenuse squared goes up by one each turn.

But, the reason that zekaric's algorithm can't be optimal in the general case is that it relies on p_0, when in reality the game has no history.  Your selection of e_j should not rely on any p_i i<j.  It doesn't matter where you just were or where you started.  e_j should be a function of p_j and R.

In the case of the circle above, I cheated by starting the game at the center and applying z's algorithm.  In actuality, the optimal strategy is to pick e_i normal to p_i - c (where c is the center of the circle).  You can see this by a symmetry argument.  Importantly, player 1's play on each turn depends only on current location and the shape of the region.  (It's also easy to see here that player 2's choices are irrelevent).

zekaric: your question of how smart player 2 is.  Assume both players play optimally.  They both totally understand the game, and make the best move at each juncture.  There is no hidden information here - it's a "total information game".

DK: to expand on your "region shrinking" idea:  The function F1 -> F2 is going to be something like,
the boundary of F2 is given by the set of all points that are midpoints on chords of F1 such that the chord has length < 2. (if you draw a picture, it obvious).  Intuitively, I see that F2 will always be smaller, but 1) I can't prove it and 2) it's not enough to prove it's smaller, you have to prove that it gets smaller fast enough (i.e. that it goes to empty set in finite steps).  Ick.

Brian
Tuesday, February 08, 2005

Thank you for the pythagorian explanation - it's really good. I've made an error while trying to solve it in a more complex way.

Now for the region shrinking function - :) I like the name - it probably should be length = 2 to define boundary of F2 and a lot of wording to handle special cases like open, n-connected, nowhere-dense and other weird sets, which actually makes this a hardcore math problem rather than a riddle. Don't want to go too far in there and again - probably someone will come up with much simplier solution. So far let's just say F2 is a subset of F1, which does not include point p if there are 2 points outside F1 on distance of 2m and p is straight in the middle of interval connecting them.

To prove this process is finite - first, we can say player can not escape F2 in one step, but can escape F1\F2 in one step - we can say it, we built F2 this way (hence player can not escape FN in N-1 steps if his opponent plays right, BTW); and second, zekaric's algorithm is here to make sure player can escape any finite field in limited number of steps, so N will be less or equal to R^2, where R is the distance between starting point and the most farther point of F1.

hm... guess we did it ;) Dmitri?

DK
Wednesday, February 09, 2005

DK: but since your argument about field shrinking punts to zekaric's finiteness argument, you haven't gained anything by introducing the notion of F1, F2, ... .

I've been thinking about how to come up with a better bound than R^2, but no luck yet.  What I'm more interested in, really, is trying to figure out a better strategy than picking the furthest point and moving away from it.  But it's unlikely that this would give any sort of closed form bound.  But for instance, suppose the region is not connected - that it's 2 disjoint circles.  Clearly the circle that the game starts in is the only one that's important.  And by moving away from the furthest point you could walk all the way across the circle you are in, instead of heading for the nearest boundary.  You can construct examples where the only algorithm we have (so far) does arbitrarily worse than optimal.  And it's not enough to require connectedness, since two regions connected by a thin (width < 2) band are disconnected for purposes of this game.

Brian
Wednesday, February 09, 2005

And that's not to say that I don't think the field shrinking idea is worthwhile.  In fact, it's most interesting in the case where the region is unbounded, and the R^2 algorithm is powerless.  But I think we agree that it becomes a hard-core topology problem rather than an interesting riddle.

Brian
Wednesday, February 09, 2005

ok, let's argue a little ;)

Zekaric's algorithm was used in my reasoning to prove number of nested fields we build F1 > F2 > F3 ... is finite. No other purpose. You can use any other way to show it is finite and abandon Zekaric's algo completely.

You may not like "field shrinking idea", but (unless there is an error somewhere) we proved that if Man starts in FN but not FN+1 he can leave field in N steps and God can force Man to make at least N steps. So we are certain that optimal strategy has N steps.

What I don't like as well is that "field shrinking" does not give us some simple and precise method to know how many steps are there given specific field and starting point - we have to build those fields point-by-point. Sliding chord gives a good fast way to do it, but could(?) fail on complex shaped fields. But as you pointed out - for pre-determined strategy it seems to be doable to construct a field, that would make that strategy non-optimal...

DK
Thursday, February 10, 2005

> Zekaric's algorithm was used in my reasoning to prove number of nested fields we build F1 > F2 > F3 ... is finite

Yes, but as I said, this limits the argument to the cases where Zekaric's algorithm also applies.  That is, bounded sets.  So my point is that it doesn't tell us anything that Z's A doesn't, and it relies on Z's A to tell us anything.  Additionally, it doesn't provide a tighter bound than Z's A, for this exact reason (and because Z's A is optimal in the case of the circle).

I don't have anything against the shrinking fields.  But they would be much more interesting if they were computable or could provide a better bound (based maybe on something like curvature).

Additionally, when the region is unbounded, there doesn't seem to be an easy way to distinguish regions that have Fi = Fj for j > i (like the region |y| <= 1), one where Fi > Fi+1 but they converge to a non-empty set (as I think something like |y| < 1 + e^(-x^2) does) and a region for which it does terminate (like |y| < 1).

Brian
Thursday, February 10, 2005

You did a great job solving this Man vs. Wizard :) riddle!

I believe the "sliding chords" algorithm is the best possible one (its applicability to the complex-shaped regions could be discussed) – theoretically. To apply it on practice, the man should have the ability to calculate E(N) region boundaries (where E(N) is the escaping region of the Nth order = the region from where the man can escape the field in N moves; and E(1) being a region of immediate escape). This doesn’t look like an easy task – and without solving it the Sliding Chords solution becomes non-constructive.

Let’s try to invent something doable and see, if possible, how close it is to Sliding Chords.

We need, of course, to allow the man to collect some information about the field. Let’s give him a radar, so the man can accurately read the distance to the field boundary from any point inside a field, at any direction he point his radar to. If this boundary radar is the only tool available to the man, what strategy may he take to escape the field as soon as he can?

Dmitri Papichev
Thursday, February 10, 2005

I'm a bit too tired to write long stuff, so just one line:
  min(max(L(a), L(a+pi)) ?

DK
Thursday, February 10, 2005

Yes, exactly that - min (max (...))

It would be interesting to see how optimal such strategy is - say, to do some software modelling of that problem (game).

Dmitri Papichev
Friday, February 11, 2005

Well, looks like it's just "yet another strategy", which does not do any good for lot of fields if you use it as it is. Even a simple 10x2 bar field would be a trouble for it if starting point is somewhere in the middle of it.

DK
Saturday, February 12, 2005

ok, it doesn't work for any square larger than 1x1 too :(

DK
Saturday, February 12, 2005

Can't throw this riddle away from head :)

I've noticed, that God can keep a Man inside any given straight 1m wide corridor. So strategy to keep Man in the field can be to pick longest (in terms of min distance from starting point to the boundary of intersecion b/w corridor and field), that includes current position and keep Man in this corridor. Now, let's assume Man knows that - how would he counter this strategy.

DK
Saturday, February 12, 2005

mmm, scrap that "doesn't work for 1x1 square" comment plesae. I need more sleep.

DK
Saturday, February 12, 2005

Um, DK:  I don't mean to sound nasty, but your posts barely make sense anymore.  And the ones that do make sense seem to be patently false ("[player 2] can keep [player 1] inside any given straight 1m wide corridor").
Would you mind writing complete sentences?

Thanks.

Brian
Saturday, February 12, 2005

Hmm... Min-max algorithm apparently doen't work, as DK clearly demonstrated.
What else could be done by the man if the only tool he has is the "boundary radar"?

Dmitri Papichev
Saturday, February 12, 2005

Brian, I don't mind you sound nasty, especially when you right - it should be 2m (you had that kind of situation considered before - your "|y|<=1" field), my fault.

DK
Saturday, February 12, 2005

Can you expand on what  "min-max algorithm" is supposed to mean, and why it doesn't work?
Also, how is this radar supposed to work?  Can the player distinguish between the region |y| < 1 (winnable) and |y| <= 1 (not winnable)?

Brian
Sunday, February 13, 2005

Brian:

"Min-max algorithm" is the following: always make a move from the point X to the direction D, such as where max (L(X, D), L (X, D + pi)) is minimal (0 <= D < pi, and L(X, D) is a distance from the point X to the border in the direction of D).

DK showed, however, that this algorithm would not work, particularly for any rectangle area with the smaller side > 2.

The radar is supposed to work as follows: being pointed to the direction of D from the point X, it returns the value of L(X, D). It can't say what will be L (Y, D) for any point Y other than the current point X, for that the man should be actually at the point Y.

Dmitri Papichev
Sunday, February 13, 2005

So, can the radar distinguish between the region |y| < 1 (winnable) and |y| <= 1 (not winnable)?  Or is there an unstated assumption that makes one of these illegal?

Brian
Monday, February 14, 2005

If I understand your question correctly, the answer is no.
The radar can't make any assumptions about any other point in the field other than the current point. It can't say anything about the winnability of regions.

Dmitri Papichev
Monday, February 14, 2005

No, I guess my question isn't very clear.  It has to do with this: can the radar distinguish if the boundary is included in the region or not?  And as to why it's important, I cited those two regions, one of which is escapable and one of which isn't.  And the only difference between these two regions is that the boundary is included in one of them.
So suppose the player has his radar at (0,0), and points it with direction (0,1) - what are the outputs in the above scenarios?  Identical outputs lead to identical strategies, only one of which has any possibility of success.

Brian
Tuesday, February 15, 2005

Brian: I think of the regions with the borders exluded, that is, if you got to the border, you successfully escaped.

BTW, I do not get any satisfactory escaping algorithm for the case when the information about the region is all received from the boundary radar.

Dmitri Papichev
Saturday, February 19, 2005

Algorithm:
1. Pray to be an instrument of God's will.
2. Move in desired direction.
3. Repeat until done.

HolyMan
Wednesday, March 02, 2005

*  Recent Topics

*  Fog Creek Home