[EventHorizon]

You are a scientist whose had a bad day and wish to take it out on your favorite maze running rodent.

The setup:

1. The maze is set on a nxn grid, where n is some large integer.

2. The mouse will always move in the direction that will get it to the cheese the quickest, but can only move north, south, east, and west. The mouse prefers different cardinal directions consistently (it only matters that it is consistent, you can choose the ordering to maximize time), but only uses this preference to break ties when two paths of equal lengths are encountered. Assume the mouse takes 1 second to move from one square to another.

3. At any time, you can pause time and place a wall (essentially a brick the size of the square) in a grid square. Once time starts again, the mouse instantly determines the new optimal path and follows it. Obviously, if the mouse is even partially in the square you cannot place a wall there (your day wasn't _that_ bad).

4. Walls cannot be removed once placed.

5. You can place the cheese and start the mouse anywhere in the maze, but you cannot move the mouse or cheese once initially placed.

6. You must always leave at least one path open to the cheese from the mouse's current location.

The goal:

Make the mouse take as long as possible before it gets the cheese.

Scoring criteria:

Score = time taken/(n*n). This essentially measures how many times on average each square (even blocked off ones) is traveled through by the mouse.

What is the best strategy you can come up with (and the score associated with it)?

I found a flash game called "Maze Stopper" (and it's sequel "Maze Stopper 2", both by FlashRelax), and it is essentially this idea. Just search for "Maze Stopper" in google (I play it from kongregate, a flash game site) for the game if you want to test out some ideas (though you cannot place starting positions, and the pathfinding has very minor (though exploitable) flaws). I have practically all the high scores for the interesting levels, and have been looking for some competition.

I have a pretty good solution for the limit as n approaches infinity (that I used on the large map in the original "Maze Stopper"), but I'm not positive that it is optimal. (I'll post a description and it's in-the-limit score later)

[EventHorizon]

Here's a simple strategy to get people started.

Strategy = make the mouse snake through a maze created all at the beginning. The mouse starts in one corner and the cheese in the opposite

Score as n->infinity = .5

The mouse will go through each unblocked square once, and there will be just about as many unblocked squares as blocked squares (equal in the limit). Therefore, the score is .5.

More complicated strategies involve building as the mouse moves. For instance, you can make two paths of equal length, and block the mouse when he is at the end of one.

[Prime]

I don't quite understand the conditions. How is the maze set up initially? How can solution be independent of the initial setup? What if there was but one path to the cheese? Then the mad scientist could not set any new walls. Do you have a picture of the maze?

[Guest]

What is the best strategy you can come up with (and the score associated with it)?

Suppose the mouse is at the bottom right, and the cheese is at the top left corner. The mouse will start to move alternately N and W. Start building a wall from the cheese toward the center of the board, but leave the last brick at the western and northern edges of the board open. You will meet the mouse in the middle of the board, and the mouse will continue to skirt one side of the wall you have just built. All you have to do to stop the mouse from getting the cheese is fill in the brick you left open on whichever side the mouse is on. In the meantime, you can build walls wherever you like. This should be better than the "snaking" method, because you are not just reacting to the mouse's move, can plan ahead, and set traps. Haven't worked out what you do in your "spare" time though...

[Guest]

What is the best strategy you can come up with (and the score associated with it)?

Finish your diagonal wall, but leave a space for the mouse to go around it. While it is making its way back to its starting point, build another diagonal wall adjacent to the first (leaving 1 square's width in between for the mouse to mosey along). When the mouse is about to round the SE corner of the wall, block it, and force it to go all the way back to the NW corner. Repeat building NW/SE walls until the mouse is forced to the NE or SW corner, and back down to the SE corner. Do the same thing on the other half of the board. Score as n->\infty = 1.

[EventHorizon]

I don't quite understand the conditions. How is the maze set up initially? How can solution be independent of the initial setup? What if there was but one path to the cheese? Then the mad scientist could not set any new walls. Do you have a picture of the maze?

The maze is initially empty (no walls), and you get to choose where to place the mouse and cheese. The only requirement about the initial setup of the maze is that it is large and square, has cheese in it, and the mouse. You could have walls initially, but it is equivalent to add them before the mouse moves.

Finding the best initial placement of the mouse/cheese is part of the puzzle as well.

Did that make it clear? Ask any more questions if you have em.

[EventHorizon]

Suppose the mouse is at the bottom right, and the cheese is at the top left corner. The mouse will start to move alternately N and W. Start building a wall from the cheese toward the center of the board, but leave the last brick at the western and northern edges of the board open. You will meet the mouse in the middle of the board, and the mouse will continue to skirt one side of the wall you have just built. All you have to do to stop the mouse from getting the cheese is fill in the brick you left open on whichever side the mouse is on. In the meantime, you can build walls wherever you like. This should be better than the "snaking" method, because you are not just reacting to the mouse's move, can plan ahead, and set traps. Haven't worked out what you do in your "spare" time though...

The mouse will not alternate N and W. In the OP, I said that the mouse has a preference for directions, and will break ties (equal length paths) consistently. So if he goes W, the paths for N and W will still be equal length paths, so the mouse will move W again. Similarly with N. Obviously, you could overcome this easily.

Finish your diagonal wall, but leave a space for the mouse to go around it. While it is making its way back to its starting point, build another diagonal wall adjacent to the first (leaving 1 square's width in between for the mouse to mosey along). When the mouse is about to round the SE corner of the wall, block it, and force it to go all the way back to the NW corner. Repeat building NW/SE walls until the mouse is forced to the NE or SW corner, and back down to the SE corner. Do the same thing on the other half of the board. Score as n->\infty = 1.

XOOXOOXOO

OXOOXOOXO

OOXOOXOOX

XOOXOOXOO

OXOOXOOXO

OOXOOXOOX

(let x's be walls, and o's be open squares)

I think your score would be higher. You make the mouse move along diagonal-like paths. If you look at what the grid would look like, 2/3 of the squares are open, and 1/3 are walls. The mouse travels over the unwalled squares twice, so that makes the score 4/3 as n->\infty (btw, it's nice to see another LaTeX user ). Of course, there are more unused squares at the ends, but those are insignificant as n->\infty.

Not a bad first strategy to post. Think about it some more, and I'm sure you can come up with a better one.

Edited October 17, 2008 by EventHorizon

[Guest]

The mouse will not alternate N and W. In the OP, I said that the mouse has a preference for directions, and will break ties (equal length paths) consistently. So if he goes W, the paths for N and W will still be equal length paths, so the mouse will move W again. Similarly with N. Obviously, you could overcome this easily.

(...)

I think your score would be higher. You make the mouse move along diagonal-like paths. If you look at what the grid would look like, 2/3 of the squares are open, and 1/3 are walls. The mouse travels over the unwalled squares twice, so that makes the score 4/3 as n->\infty (btw, it's nice to see another LaTeX user ). Of course, there are more unused squares at the ends, but those are insignificant as n->\infty.

Not a bad first strategy to post. Think about it some more, and I'm sure you can come up with a better one.

LOL. Nothing says "nerd" like LaTeX!

Anyway, you're right about it being 4/3. I forgot the mouse couldn't move diagonally when I calculated the wall "density".

I'm a bit confused by the first part of your post though. If the mouse is n-1 squares to both the south and east of the cheese, after it moves in its preferred direction, say, west, it will be n-1 squares to the south, and n-2 to the west. Would it not then turn north, and then west again?

Just out of curiosity, and if it doesn't give away your strategy, what is your score?

[EventHorizon]

...

I'm a bit confused by the first part of your post though. If the mouse is n-1 squares to both the south and east of the cheese, after it moves in its preferred direction, say, west, it will be n-1 squares to the south, and n-2 to the west. Would it not then turn north, and then west again?

...

If you look at the optimal paths from one square north and west, they will be equal in length. Since the mouse will breaks ties by going in a preferred direction, he goes, lets say, north. After going north one square, the optimal paths of one more square north and one square west are still equal in length. The mouse is required to break ties consistently based on direction, so it will go north again. It will keep going north until it is directly east of the cheese.

...

Just out of curiosity, and if it doesn't give away your strategy, what is your score?

2.5.

I moved away from using diagonal paths because of too many unused squares and due to the starting position of the flag/character in the flash game (which no longer applies due to n->\infty, etc), so I'll look into what can still be done if I use diagonal paths. The score may improve by a little.

...

Thinking about it, it seems I can get it to 2 2/3 using diagonal paths (one less time going over the squares, but still gain time due to wall density).

Of course, still post any strategies improving on 4/3.

[Prime]

Here is a fresh idea. Make mouse "pay" while you're building the wall, while preventing it from even starting to traverse the structure.

Start with an empty maze cheese and mouse close by. The cheese is marked with letter "C" on the picture. Mouse -- with the letter "m". The order in which blocks were placed once the mouse approached within 2 steps from cheese are marked with the black numbers indicating the order, in which they were built.

While the "diamond" in the illustration is built, the mouse will tread back and forth on the same two squares.

Then you let the mouse run along one of the sides while preparing a trap. Preset the second line of cheese defense as blocking squares as marked with blue numbers, placing 1 and 2 in advance, then as the mouse moves between 1 and 2 place the block marked with the blue 3. After that make mouse tread back an forth as much as space allows, while placing new blocks. Then guide the mouse out of the diamond.

After that, win tempos by building the blocks diagonally when you must. Some "Single pass" points may be created (marked with yellow), which must be now treated as mouse’s goal. Guide mouse into position where it would have a choice of 2 equal paths and make it tread back and forth while you increase each path in turn by 2 steps (just like in the beginning).

It is hard to estimate the board size / time ratio with this strategy. With the big board you must find the optimal point when to stop treading the mouse at the same spot and let it run along the perimeter. If you play it right, for most blocks you built the mouse will make an idle step. Then it will traverse multiple perimeters twice, or more.

[EventHorizon]

Here is a fresh idea. Make mouse "pay" while you're building the wall, while preventing it from even starting to traverse the structure.

Start with an empty maze cheese and mouse close by. The cheese is marked with letter "C" on the picture. Mouse -- with the letter "m". The order in which blocks were placed once the mouse approached within 2 steps from cheese are marked with the black numbers indicating the order, in which they were built.

While the "diamond" in the illustration is built, the mouse will tread back and forth on the same two squares.

Then you let the mouse run along one of the sides while preparing a trap. Preset the second line of cheese defense as blocking squares as marked with blue numbers, placing 1 and 2 in advance, then as the mouse moves between 1 and 2 place the block marked with the blue 3. After that make mouse tread back an forth as much as space allows, while placing new blocks. Then guide the mouse out of the diamond.

After that, win tempos by building the blocks diagonally when you must. Some "Single pass" points may be created (marked with yellow), which must be now treated as mouse’s goal. Guide mouse into position where it would have a choice of 2 equal paths and make it tread back and forth while you increase each path in turn by 2 steps (just like in the beginning).

It is hard to estimate the board size / time ratio with this strategy. With the big board you must find the optimal point when to stop treading the mouse at the same spot and let it run along the perimeter. If you play it right, for most blocks you built the mouse will make an idle step. Then it will traverse multiple perimeters twice, or more.

Not bad.

Each time you add a square in the lower part of the diamond, you actually increase the length of that path by 4 squares (but only 2 on the upper part). So you can get more than just 2 squares traversed for each of those squares built (possibly 4 with the right tie breakers).

So....how will your strategy continue? And what does your score end up as?

[Prime]

Not bad.

Each time you add a square in the lower part of the diamond, you actually increase the length of that path by 4 squares (but only 2 on the upper part). So you can get more than just 2 squares traversed for each of those squares built (possibly 4 with the right tie breakers).

So....how will your strategy continue? And what does your score end up as?

I'm not sure how that would work...

You have 2 paths of equal length n each. The mouse moves in its preferred direction.

Now one path is n+1 and the other n-1 long. Add 3 to the n-1 path.

The two paths become n+1 vs n+2. The mouse moves back to the original square, the two paths are:

n vs n+3. Now add 3 to the n path making them n+3 vs. n+3.

The mouse again moves in its prefered direction.

There may be other increments and more than one step treading.

However, the real problem here is estimate of the order of the rodent's travel. I envision the resulting maze as a network of nested diamonds, with some paths inside to lead the mouse outside the outer diamond before it managed reaching the entrance point to the inner diamond. In such way the pest traverses perimeter of each diamond, travels some distance inside those diamonds, and treads on the same spot, while a new corridor is created.

[EventHorizon]

I'm not sure how that would work...

You have 2 paths of equal length n each. The mouse moves in its preferred direction.

Now one path is n+1 and the other n-1 long. Add 3 to the n-1 path.

The two paths become n+1 vs n+2. The mouse moves back to the original square, the two paths are:

n vs n+3. Now add 3 to the n path making them n+3 vs. n+3.

The mouse again moves in its prefered direction.

There may be other increments and more than one step treading.

However, the real problem here is estimate of the order of the rodent's travel. I envision the resulting maze as a network of nested diamonds, with some paths inside to lead the mouse outside the outer diamond before it managed reaching the entrance point to the inner diamond. In such way the pest traverses perimeter of each diamond, travels some distance inside those diamonds, and treads on the same spot, while a new corridor is created.

You have the mouse moving one square each time, but stays at two given squares. Since adding a square in the lower half of the diamond adds 4 to the length of a path, you can move 2 each time.

For example:

Let the mouse prefer moving right and left more than up (for tie breakers). Let it also prefer moving down to left,right, or up. (eg, down > right > left > up)

Starting with the mouse directly below the cheese, and a wall between. The mouse will move right because of the tie breaker (path lengths are - left=4 right=4). Let the mouse then move up (to one square down and one right of the cheese). Add a wall to the right side of the diamond (down=6 right=6). Let the mouse move to it's original location (left=4 right=8), then build a wall on the left side of the diamond (left=8 right=8). Rinse and repeat.

Your right though, the real problem concerns the rest of the strategy.

[EventHorizon]

You have the mouse moving one square each time, but stays at two given squares. Since adding a square in the lower half of the diamond adds 4 to the length of a path, you can move 2 each time.

For example:

Let the mouse prefer moving right and left more than up (for tie breakers). Let it also prefer moving down to left,right, or up. (eg, down > right > left > up)

Starting with the mouse directly below the cheese, and a wall between. The mouse will move right because of the tie breaker (path lengths are - left=4 right=4). Let the mouse then move up (to one square down and one right of the cheese). Add a wall to the right side of the diamond (down=6 right=6). Let the mouse move to it's original location (left=4 right=8), then build a wall on the left side of the diamond (left=8 right=8). Rinse and repeat.

Your right though, the real problem concerns the rest of the strategy.

Yet another oops.....the mouse won't go up, it will go right. But it still works.....two right, two left, etc.

[Prime]

I think, in general, good strategies should deviate toward making the rodent to tread the same squares as much as possible. And when you no longer can send mouse down the same path and make it return, when closing path, build the new perimeter as close as possible. Preferably on top of the path, which mouse has traveled already. Per each square blocked make mouse traverse as many squares as possible. The total ratio is hard to estimate with a good strategy. Perhaps, recursively. First finding best patterns for a smaller board, then using the entire board as an entity for a larger board calculation. Looks like a computer simulation problem to me. I can't imagine how a simple formula could be derived here.

[EventHorizon]

I think, in general, good strategies should deviate toward making the rodent to tread the same squares as much as possible. And when you no longer can send mouse down the same path and make it return, when closing path, build the new perimeter as close as possible. Preferably on top of the path, which mouse has traveled already. Per each square blocked make mouse traverse as many squares as possible. The total ratio is hard to estimate with a good strategy. Perhaps, recursively. First finding best patterns for a smaller board, then using the entire board as an entity for a larger board calculation. Looks like a computer simulation problem to me. I can't imagine how a simple formula could be derived here.

You basically check to see which areas are traversed over how many times. Given a fairly consistent strategy, you can come up with a score rather easily by looking at areas and wall densities, etc. It makes it a lot easier with only caring about the score in the limit.

[EventHorizon]

I think, in general, good strategies should deviate toward making the rodent to tread the same squares as much as possible. And when you no longer can send mouse down the same path and make it return, when closing path, build the new perimeter as close as possible. Preferably on top of the path, which mouse has traveled already. Per each square blocked make mouse traverse as many squares as possible. The total ratio is hard to estimate with a good strategy. Perhaps, recursively. First finding best patterns for a smaller board, then using the entire board as an entity for a larger board calculation. Looks like a computer simulation problem to me. I can't imagine how a simple formula could be derived here.

I'll try to put together a little simulator over this weekend, and post the source code. I have a paper I need to work on, so I may not actually get to it all that soon.

Feature wish list:

1. arrows showing paths (where the mouse would go if in that square).

2. ability to set things up initially.

3. ability to choose direction preferences.

4. ability to save replays, and play them back. As well as stop the playback at any point to try something different.

5. choose the size of the grid.

6. able to change the speed of replay playback/mouse movement, and have the option of letting the mouse move 1 space when paused.

7. can choose between smooth (mouse walks from square to square) and discrete (mouse jumps 1 square at a time).

Can anyone think of any other features it should have....besides ensuring world peace and curing cancer while eliminating poverty, terraforming other planets, and providing cheap renewable energy?

[Guest]

OK. I think I see how you get 5/2.

...always leaving two paths to the cheese, and making each path alternately longer by just the right amount at the critical moment to send the mouse back from whence it came (I started them at opposite corners of the board). The mouse essentially moves back and forth along the same two edges of the board n/2 times (the time it takes you to fill the board), and then moves through the maze you have been constructing once (through nearly half the squares) for a score of 5/2. I say "nearly" because you have to begin building walls at two adjacent corners of the board, and because of time constraints, you can only use about 1/6 of the cheese-side of the board initially (the mouse gets there in 2n moves), but I think you can grow that pretty quickly to full width. It's hard to explain. I'll try and post a picture tomorrow.

You may even be able to send the mouse part-way into the maze to increase the score, but I haven't worked that out yet. If it can be done, you might end up with a score proportional to n.

[Guest]

OK. I think I see how you get 5/2.

...always leaving two paths to the cheese, and making each path alternately longer by just the right amount at the critical moment to send the mouse back from whence it came (I started them at opposite corners of the board). The mouse essentially moves back and forth along the same two edges of the board n/2 times (the time it takes you to fill the board), and then moves through the maze you have been constructing once (through nearly half the squares) for a score of 5/2. I say "nearly" because you have to begin building walls at two adjacent corners of the board, and because of time constraints, you can only use about 1/6 of the cheese-side of the board initially (the mouse gets there in 2n moves), but I think you can grow that pretty quickly to full width. It's hard to explain. I'll try and post a picture tomorrow.

You may even be able to send the mouse part-way into the maze to increase the score, but I haven't worked that out yet. If it can be done, you might end up with a score proportional to n.

Oops. Never mind. I miscalculated. That gives you a score of only 3/2...

[EventHorizon]

Oops. Never mind. I miscalculated. That gives you a score of only 3/2...

I just found a way to up my score to 3 without using diagonal paths, and 3 1/3 using diagonal paths.

It is also starting to look like it may be possible to increase it a couple times further (possibly up to some function of n, as you suggested previously). (edit -- I just read back through the posts, and didn't see a mention of this...maybe I heard it elsewhere....)

I haven't yet started working on the simulator, though I thought of another feature to add -- undo/redo.

Edited October 19, 2008 by EventHorizon

[EventHorizon]

...

It is also starting to look like it may be possible to increase it a couple times further (possibly up to some function of n, as you suggested previously). (edit -- I just read back through the posts, and didn't see a mention of this...maybe I heard it elsewhere....)

...

It was in your last and second to last posts. Guess I didn't read those too carefully/thought you mentioned it earlier.

As for the simulator, it's coming along. I'm done with the gui (except for some funny behavior with the scroll pane), initialization(preferences,mouse,cheese), pathfinding, and graphics. I just need to get the mouse moving, keep scores, handle replays, and allow undo/redo.

[EventHorizon]

Here's the beta version of my maze stopper simulator!

It is just the java code (feel free to make sure I didn't hide any malicious code in there....though it is just one 1000 line file, so it may be hard to follow), so you'll need to compile it yourself. To watch a replay (I didn't include any, but you can post your strategy as a replay file) you will need to click redo repeatedly. A replay is loaded like you just undid the whole thing, so if you hit start or step it will erase the replay's history.

If you have any questions, find a bug, or find something about it irritating....let me know and I'll look into answering your question/fixing the problem.

Feel free to post replays with the description of your strategy...or even just of good techniques to slow the mouse down. I'll post the replay of my best strategy sometime soon......just don't go and beat my "Maze Stopper" (the flash game) scores too quickly

[EventHorizon]

I updated the simulator slightly. I got rid of the scroll pane weirdness (it updates correctly now), and removed a bug in the undo/redo/history stuff (it allowed you to completely block off the cheese from the mouse). I'll look into getting the smooth movement to be more than just making it look smooth (eg, have time increase with it and include it in the history somehow (I don't really want 10* more information in the history)). I may also add in diagonal movement too (to be more like the flash game...maybe even have a checkbox to mimic the flash game's errors or add in an approximation to the score that would be received).

mazestopsim.zip

[EventHorizon]

It seems nobody's posting...so here's one sample replay. It has a score of 2 as n->\infty (this is because the mouse passes through the vertical corridors four times each and their density is 1/2 (half walls and half open squares)). Here's a tip for playing the replay.... after clicking redo once, you can press spacebar to redo again, etc.

replay_2_score.zip

How would you improve on it?

[EventHorizon]

I posted youtube videos of all my interesting record runs on Maze Stopper and Maze Stopper 2. I thought I should add a link here.

youtube videos

I do have strategies with better scores (for this posted problem). Though I am still not sure about a limit (currently seems like O(log(n)) where n is the length of the edge of the square map).