5
$\begingroup$

There is a 8*8 maze, and a player starting at (0, 0) wants to arrive at (7, 7) in minimal moves.

For each round (a round may contain several moves), the obstacle will be randomly set at a grid it has not been set before, also, it won't be set at either (0, 0) or (7, 7).

After the obstacle is set (although the player has no idea where it is in this round), the player has to give a probability distribution of his move in this round, e.g. up: 0.5, down: 0.2, left: 0.2, right: 0.1, then his move will be generated depending on the distribution. If he bumps into the obstacle or gets out of the maze (e.g. move right when he is at (7, 0)), he has to stay at the current grid, and another move will be generated. The process goes on until he moves to a feasible grid.

When a round ends, the player will know where the obstacle was in the last round. To be clear, supposed the player is in the nth round, then he will know the history of the obstacle from the first round to the (n-1)th round.

My question is, given the history of the obstacle and the current position of the player, is there a strategy to minimized expected moves from a probabilistic perspective?

EDIT

I've wrote a simulation program, and tried several strategies with it. Define a strategy consisting of four real values, representing the probability of moving up, down, left, and right, respectively.The naive one [0.25, 0.25, 0.25, 0.25] got an average of 73 moves.

Another strategy is defined below:

  1. if up and right are both safe, return [0.5, 0, 0, 0.5]

  2. if up is safe, return [1, 0, 0, 0]; if right is safe, return [0, 0, 0, 1]

  3. if at the right most line, return [0.5, 0, 0.5, 0]; if at the up most line, return [0, 0.5, 0, 0.5]

  4. else, return [0.5, 0, 0.5, 0]

In the end, the second strategy need 18.4573 moves on average. (10000 trials)

It is a huge success when comparing with the naive one, but I am struggling with getting closer to the theoretically minimum of 14 moves. I appreciate any advice or suggestions.

Confirmation

  • There is a $(X,Y)=(0:N-1,0:N-1) \in \mathbb{R}^2, N=8$ maze

    Yes

  • There is no inner walls or paths at the maze (Then it is not a maze??),

    Yes, I called it a maze only because there is a single randomly appearing obstacle.

  • The positions cannot get outside the domain, hence evidently the movement have to be properly constrained,

    Yes, if the intended move generated by the probability distribution will make the player get out of the maze, the count of moves will increment by one, and the player has to stay at the current position until an feasible move is generated.

  • There is an changing obstacle at an unknown position $(x^o,y^o)$, for every time $t$,

    Yes

  • The obstacle position at $t=n-1$ is known at $t=n$,

    Yes

  • For every time $n$, the obstacle change their coordinates according an uniform distribution on $(X,Y)$. Hence, the obstacle can "jump" to their new position,

    Yes

  • The obstacle don't take a previous coordinate. Hence the uniform distribution is over $(X,Y)-(X^o,Y^o)$, $(X^o,Y^o)={(x^o(t),y^o(t),t=1...n-1)}$. Hence the obstacle takes its last move at $t=N^2$ and then it disappears (??),

    The obstacle won't be set on the stating point and the ending point, so the player will lose the game if he can not reach the exit in $N^2 - 2$ rounds

  • The player position $(x(t),y(t))$ one square (up, down, left or right) per time,

    Yes

  • The player cannot pass, hence make no move at all (??),

    I am not sure what you are referring.

  • If the obstacle hits the player by a player move or an obstacle change, the player loses,

    If the obstacle hits the player by a player move, as I stated in my problem, If he bumps into the obstacle or gets out of the maze (e.g. move right when he is at (7, 0)), he has to stay at the current grid, and another move will be generated. The process goes on until he moves to a feasible grid. In short, the player loses the game iff he can not reach the exit in $N^2 - 2$ rounds. If the obstacle hits the player by an obstacle change, we assume that the player is strong enough to lift the obstacle, so he can safely stay with the obstacle in the same grid.

  • If the player reach the exit, the player wins.

    Yes

$\endgroup$
6
  • $\begingroup$ sure... but it will depend on how the obstacle already used the optimal path $\endgroup$
    – Brethlosze
    May 27, 2017 at 9:06
  • $\begingroup$ But we don't know where the obstacle is and will be, that's why analyzing from a probabilistic perspective may help. $\endgroup$
    – David Chen
    May 27, 2017 at 9:19
  • $\begingroup$ Do you assume that the random position of the obstacle during the $n$-th round depends on earlier positions? If not then knowledge about earlier obstacle locations does not help. $\endgroup$ May 27, 2017 at 10:30
  • $\begingroup$ @Yiteng As I stated, the obstacle will be randomly set at a grid it has not been set before, so the player can safely move to an earlier obstacle location without having the risk bumping into the obstacle. $\endgroup$
    – David Chen
    May 27, 2017 at 10:41
  • $\begingroup$ After imposing us your problem without hearing suggestion, did you make any effort on showing us your own solution proposal? $\endgroup$
    – Brethlosze
    May 27, 2017 at 14:37

2 Answers 2

0
$\begingroup$

Lets consider the following assumptions, which you should confirm for proceeding further:

  • There is a $(X,Y)=(0:N-1,0:N-1) \in \mathbb{R}^2, N=8$ maze,
  • There is no inner walls or paths at the maze (Then it is not a maze??),
  • The positions cannot get outside the domain, hence evidently the movement have to be properly constrained,
  • There is an changing obstacle at an unknown position $(x^o,y^o)$, for every time $t$,
  • The obstacle position at $t=n-1$ is known at $t=n$,
  • For every time $n$, the obstacle change their coordinates according an uniform distribution on $(X,Y)$. Hence, the obstacle can "jump" to their new position,
  • The obstacle don't take a previous coordinate. Hence the uniform distribution is over $(X,Y)-(X^o,Y^o)$, $(X^o,Y^o)={(x^o(t),y^o(t),t=1...n-1)}$. Hence the obstacle takes its last move at $t=N^2$ and then it disappears (??),
  • The player position $(x(t),y(t))$ one square (up, down, left or right) per time,
  • The player cannot pass, hence make no move at all (??),
  • If the obstacle hits the player by a player move or an obstacle change, the player loses,
  • If the player reach the exit, the player wins.

Please confirm.

If the obstacle moves are indeed uniform, the optimal strategy is to move towards the closest position in the set $(X^o,Y^o)$, or better, to the closest position made by two joined squares taken by the obstacle (for example (1,1) and (1,2) if they happen), and stay moving inside there, until the obstacle disappears, hence ensuring victory, taking in average $N^2+4=68$ moves

If you are presenting this problem onto a contest, for winning against the fastest strategy, then the probability of being catched and move onto a closest position used by the obstacle $(X^o,Y^o)$ must equal your risk appetite to win the contest, making the algorithm faster but sub-optimal.

The strategy taking the major risk (willingly or not) will win, hence the fastest, riskiest strategy is just move straight to the end, taking $2(N-1)$=14 moves.

$\endgroup$
9
  • $\begingroup$ Thanks for providing your suggestions, and I've updated the confirmation. The major clarification is that, as I stated at the very first time, when the player bumps into the obstacle, he won't lost the game, only the number of total moves will increment by one. $\endgroup$
    – David Chen
    May 28, 2017 at 9:38
  • $\begingroup$ Are you kidding???... We everybody in here are really losing our time here. The optimal is just going straight with 14 moves, with a change of $1/N^2, 1/(N^2-1), 1/(N^2-2),...., $ of increasing the given solution in one, for each square. Any strategy will add at least 3 moves per evasion, which is much much greater than the risk of being catched. $\endgroup$
    – Brethlosze
    May 28, 2017 at 14:46
  • $\begingroup$ Hence the strategy is simply going straight. And pay for the additional move if you have the bad luck of being catched, with probability $1/63$ $\endgroup$
    – Brethlosze
    May 28, 2017 at 14:49
  • $\begingroup$ Maybe you should stay rational and carefully read through the extremely clarified problem description when imposing us the naive strategy. $\endgroup$
    – David Chen
    May 29, 2017 at 5:10
  • $\begingroup$ I of course know I should move straight to the exit, that's why I set the probability distribution to [0.5, 0, 0, 0.5] as default, but one should also consider when the player is at the edge of the maze, e.g. (7, 3), if you insist on "moving straight forward to the exit" strategy, you will set the probability distribution to [1, 0, 0, 0], but if the obstacle happens to be set at (7, 4) in this round, you will be stuck in a infinite loop because in each round, once you have decided your probability distribution, your moves will be generated based on it until the move is feasible. $\endgroup$
    – David Chen
    May 29, 2017 at 5:10
0
$\begingroup$

If the obstacle is randomly placed you don't need to randomize your strategy. Either there is a best choice and you have to choose it or there are multiple choice equivalent and you may as well choose one.

In my opinion the best strategy will consist in always moving up or right. The choice between up or right is given by the direction minimizing the expected number of steps, I think that if you don't want to brute force compute it you can safely approach it by the direction maximizing the number of cell already blocked in the past (along a shortest path).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .