Jump to content

  • Log In with Google      Sign In   
  • Create Account

Solving the Gridlock Game


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
23 replies to this topic

#1 sled   Members   -  Reputation: 154

Like
0Likes
Like

Posted 18 December 2006 - 09:56 AM

I recently stumbled upon a small flash game called Gridlock that is a fun puzzle game. Now I'm trying to write a program to solve it. How the game is played The game consists of a 6x6 board with horizontal and vertical blocks of length 2 or 3 and width 1. The objective is to move the horizontal blue block out through the hole on the right side of the board. To do so, you will need to move other blocks out the way. The horizontal blocks can be moved left and right and the vertical blocks can be moved up and down. Writing a program to solve any puzzle My initial attempt to solve this puzzle was with brute force. I started by looking at the initial board and figuring out all possible moves that could be made (There are generally ~4-10 moves that can be made given a board state). Then I create new boards with these states and check if any of them are in the winning state (the blue block is out to the right). If there are no winners, I repeat the process of analyzing all possible moves and creating new boards. The problem with this attempt is that the space we are searching grows too fast. Generally it takes me ~15-50 moves to solve the puzzle. So a conservative estimate of the number of boards checked with brute force (breadth first search) would be 4^15 (could be 10^50 or worse). The next step What I plan to do next is play the game some more and try to figure out the strategy I am using the solve it. And by "figure out" I mean I want to be able to write down in words or explain to someone else steps they can take to solve the game. Once I figure this out, I think it will be much easier to implement an efficient algorithm. Has anyone played the game and come up with such a strategy? Another idea that I have is creating a heuristic to evaluate how "good" a board is. Meaning a board that is only a few steps away from being solved will get a higher score than a board that is not close to being solved. If this was possible then the N best boards could be evaluated (beam search) at each depth in the search tree. The problem with this is rating what a good board is. Usually a better board is one where there are fewer blocks in between the blue block and the exit. This is similar to saying the blue block is closer to the exit on the right side (but not quite - there are slight differences). I think this might run into problems though in cases where you need to make your position worse before you can make it better. Any suggestions on this idea or any other ideas?

Sponsor:

#2 pinacolada   Members   -  Reputation: 834

Like
0Likes
Like

Posted 18 December 2006 - 10:16 AM

From my experience with the game, I don't think rating boards as "good" or "bad" will be too productive. It's pretty difficult to look at a board and judge how close you are to finishing (unless you can actually see the solution). In fact, most of the tricky puzzles are deliberately set up so that there are states which look really good, but are in fact dead ends.

I think in this case, it wouldn't be too hard to just keep track of every possible state of the game. There's (relatively) not that many. If you have, say.. 10 cars, and each of them can be moved to 5 possible positions, that's ~9 million states. Not too hard to handle.

So, step 1: encode every possible state in memory. Then start from the initial state and figure out which states you can reach from that state by making a single move. Mark those states as "reachable". Also, for each reachable state, keep track of the shortest path that was used to reach it.

Then take all the states that were newly marked as "reachable", and figure out which states are reachable from those. Repeat. Stop when your goal state gets marked "reachable", and your solution is the path to that state.

If you want to be more efficient, you could start searching from both the start and the end simultaneously.

It's kind of like your brute force search, except brute force will end up searching the same exact board state multiple times. This method makes sure that each possible board state only gets checked out once.

I believe this kind of programming technique is called "dynamic programming"

#3 Luhz   Members   -  Reputation: 109

Like
0Likes
Like

Posted 18 December 2006 - 11:31 AM

I think it could be done with a brute force AI using traditional pathfinding techniques. The fact that each block on the board can only move in two directions greatly limits the number of possible states for each board. The biggest problem with that approach would be having the algorithm recognize when a loop has been reached in the pattern.

Another way to try it would be to consider the shapes of all the pieces given, and to create a set of solutions with those blocks, then to have the algorithm attempt to reach those solutions from the starting point.

#4 varuna82   Members   -  Reputation: 126

Like
0Likes
Like

Posted 18 December 2006 - 01:10 PM

You can use A* algorithm. It is originally used for pathfinding. But, you can use it for single player puzzel solving.

For A* you need a good heuristic. The trick is, it's not just brute force. While brute forcing you move in the best possible direction.

Regards.
Varuna.

#5 varuna82   Members   -  Reputation: 126

Like
0Likes
Like

Posted 18 December 2006 - 01:14 PM

http://www.geocities.com/jheyesjones/astar.html

Try this one! :-)

#6 sled   Members   -  Reputation: 154

Like
0Likes
Like

Posted 18 December 2006 - 02:08 PM

As pinacolada said, using A* probably isn't viable because we can't think of a way to evaluate what a "good" board is. If you can think if a good evaluation function I'd be glad to hear it.

#7 ID Merlin   Members   -  Reputation: 115

Like
0Likes
Like

Posted 18 December 2006 - 04:15 PM

I think the best idea posted is to use brute force, but recognize previously encountered board positions.

#8 Vorpy   Members   -  Reputation: 869

Like
0Likes
Like

Posted 19 December 2006 - 06:43 AM

For recognizing previously encountered positions, you can use a hash table. For a good and fast hash function, look up zobrist hashing. It's a technique to generate hash codes for game boards that makes it very fast to generate a hash code for a new board that is reached by moving one peice on an old board. For each posible position of each peice you generate a random 32 bit number. The hash code for a board is just the number for each peice on the board XORed together. When moving a peice, you just remove it from the hash code by XORing its current value with the old hash code, then XOR in the value of its new location.

#9 Asbestos   Members   -  Reputation: 169

Like
0Likes
Like

Posted 19 December 2006 - 08:50 AM

For everyone suggesting brute force:

Do you think this is the way humans solve the puzzle? Commit 9 million states to memory at the beginning, or go through tens of thousands of possibilities each game?

I would think certainly not. So there is guaranteed to be a better algorithm. Above people have said that A* wouldn't work as there is no way to judge the worth of a board, but there must be some rough measure, otherwise we couldn't do it. Sure, they can lead you into easy-looking dead-end solutions, but even with those tricks, the game is still solvable by humans without doing a brute-force ten-thousand possibility search.

Anyone got any thoughts?

#10 sled   Members   -  Reputation: 154

Like
0Likes
Like

Posted 19 December 2006 - 10:06 AM

Asbestos, I definitely agree with you that there must be a better method than brute force search as we humans can usually solve the puzzle in 20-100 moves. (Although I think it's important to point out that we probably analyze more than a 100 moves in our head and automatically erase the bad ones. I think we are also able to do a good job of remembering moves we already did so we don't end up repeating them or returning to a previous state. This is effectively pruning branches of the search tree that we don't think it would be a good idea to take.)

However, I don't think the human method is necessarily done by rating how "good" a board is. When I try to solve the puzzle, I usually start by looking at the first block between the blue block and the exit. I then try to figure out what pieces I need to move to be able to move that first block, and repeat.

As an example, consider the following game board where the periods are empty space, the B's are the blue block, and the numbers are regular blocks.


. . . 3 3 .
. . . 2 . .
B B 1 2 . .
. . 1 4 4 .
. . 1 . . .
. . 5 5 . .


To solve this, I would see I need to move block 1, and to do this, I would need to move block 5. Next I would see that I need to move block 2, and to do this, I would need to move blocks 3 and 4 (and possibly 1 and 5). I also try to make sure that in the process of clearing block 2, I don't move other blocks in the path of the blue block.


Steps:
1. Move block 1
a. Move block 5
2. Move block 2
a. Move block 3
b. Move block 4
c. Possibly move blocks 1 and 5 - but make sure I'm not moving them back to previous positions where they are blocking B


I think this algorithm could possibly work. This would involve performing a search on the first block in the way, then performing a search on the second block in the way while trying not move other blocks in the way of the blue block. The algorithm would also need to avoid making moves that "reset" previous moves or series of moves.

This approach would probably fail for the more complex cases where you need to make things "worse" before you can make them "better". However, I think its a good first step and once it works well for simple cases, it could be tweaked for the complex cases.

I look forward to trying to implement this, as well as an efficient brute force method after my finals this week. I'll be sure to post my results :)

#11 Vorpy   Members   -  Reputation: 869

Like
0Likes
Like

Posted 19 December 2006 - 10:58 AM

Maybe look at this as trying to recursively solve subproblems.

First try to move the blue block one space closer to the goal. If it is blocked, try to move the block in its path out of the way. There may be two different ways it can be moved, so treat each direction as a subproblem, and apply this algorithm recursively (to the task of moving the block the number of spaces needed to clear the way for the blue block). Then move the blue block. Keep repeating this until the blue block has reached the goal.

Now the tricky thing is what to do if you need to move the blue block (or whatever block we're currently trying to move) backwards in order to clear its path forward, since then we might end up freeing the square that was ahead of it, but then when we're done it might be further back and blocked by something else...

Maybe just allow the block to be moved backwards and blocked in this fashion, but whenever trying to move a block by one space, remember the state of the board (and also which block we were trying to move) so if that exact situation comes up again the recursion terminates to avoid cycles. At that point, the algorithm backtracks to one of the earlier decisions (to either move a block up or down, or left or right) and chooses the other direction.

I wonder if there are boards for which this algorithm wouldn't work...

Also I've found that the more standard name of this game in literature is "Rush Hour", since that is the name it was first sold under. wikipedia entry on Rush Hour (board game)

#12 Sneftel   Senior Moderators   -  Reputation: 1781

Like
0Likes
Like

Posted 19 December 2006 - 11:06 AM

A* is never less viable than Dijkstra's algorithm; if you can't think of a good heuristic, just use h(X)=0. In this case, the heuristic could simply be the distance of the target block from the goal. Obviously this is nowhere near an exact heuristic. Nevertheless, it's still admissible (and consistent, for that matter), so it can't hurt, and might well help. Never underestimate the advantage a bad heuristic has over no heuristic.

#13 sled   Members   -  Reputation: 154

Like
0Likes
Like

Posted 19 December 2006 - 11:29 AM

Vorpy, thanks for the link. It looks like there is a solver that implements a brute force breadth first search.

Sneftel, can you think of a good Heuristic for this game?

#14 lonesock   Members   -  Reputation: 803

Like
0Likes
Like

Posted 19 December 2006 - 01:25 PM

for the heuristic to be admissible, it should be the least cost possible to get to the solution, so I would suggest as a starting point:

h =
distance from car to exit
+
for each perpendicular car/truck blocking the exit, the distance it would have to move to get out of the way


#15 Sneftel   Senior Moderators   -  Reputation: 1781

Like
0Likes
Like

Posted 20 December 2006 - 03:25 AM

what he said. [grin] Usually the best heuristics are (a) ridiculously oversimplified, and (b) cheap and obvious to evaluate. Don't fall into the trap of making your heuristic too detailed and smart: It can make proving admissibility more difficult, and spend time giving A* information it doesn't need.

#16 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 23 December 2006 - 03:43 AM

I made a breadth first solver for this Gridlock game and it took about 0.1 seconds (or less) to solve a puzzle with 700 MHz CPU. So A* isn't really necessary unless you're planning on writing the solver for a mobile phone or something..

#17 bugboy   Members   -  Reputation: 156

Like
0Likes
Like

Posted 28 December 2006 - 08:55 PM

Genetic Algorthimn might be faster than a brute search.

#18 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 29 December 2006 - 08:23 AM

I disagree - genetic algorithms are utterly dependent on the quality of the heuristic that evaluates the fitness of a given solution. More critically, this isn't the sort of problem that is easy to encode - how would you represent solutions for this problem as a fixed-length string?

A* isn't completely stupid, even with a crude heuristic - even in it's worst case, it at least avoids checking duplicate states twice, and it will be easy to encode states for the A* algorithm. A GA will need a very clever encoding and fitness heuristic - why suffer by trying to be clever when dependable old A* is far more appropriate?

#19 Álvaro   Crossbones+   -  Reputation: 13907

Like
0Likes
Like

Posted 02 January 2007 - 04:41 AM

Quote:
Original post by bugboy
Genetic Algorthimn might be faster than a brute search.

I hope that was a joke.

#20 Yui Chiba   Members   -  Reputation: 100

Like
0Likes
Like

Posted 19 January 2012 - 10:02 AM

I have to say I think most of the answers to this are incorrect, so far. With the exception of the 'subproblem' idea, I don't think that anyone has described a viable "human approach" other than brute force, and that's why I don't see anything more than the human approach coming out.... Then there's the A* method. TBPH, I'm not sure what that is. If it's the hash method, then I think it's the same as the brute force method, right?

Anyway, whatever.... Here are two good ways to solve these puzzles that could probably be adapted to AI.

First off, you will need to be programming some 'brute force', but before you do that, you're going to have to give the computer something more to work with than the pieces, the board, and where the blue peg belongs....

STEP 1
Either:
A) Have the computer calculate viable end states for the board, itself.

or

B) Have the computer calculate which pieces need to be moved such that the goal can be reached, and then have the computer eliminate the closest possible end-of-the-line scenarios.

Considering A:
A heavily populated board has only 12 pieces on it. Just knowing the pathing and understanding that pieces are not allowed to overlap, a computer can descover an end-desired result. There are usually only 2-4 good end states. Most of the time 2-3 of those are reachable states.

Considering B:
It helps a lot to know the closest possible fail states, in my opinion. If you can figure those out, then you can see the core problems with the board. Example: if two 3-tall pieces need to touch the bottom of the board for you to reach your goal, but there is a 3-wide piece, then you know the blue piece must be moved past the first 3-tall piece before the second 3-tall piece is put into place. Knowing this quickly eliminates hundreds of moves from any game where there are two 3-talls and a 3-wide.

Step 2
Following A:
Now, you need to have the computer solve it. The issue I see with the proposed method, which is just 'brute force', and very similar to my method, is that it is a ground-up method. You need a sky-down approach. Discover which moves are necessary to bring you to your end state instead of which moves are not. When I look at a board, I always think to myself, "I need to make the blue piece move. To do that, I need to move this piece out of the way, and to move this piece out of the way, I need to move this piece up and these two pieces over." Rather than, "I can move these three pieces. Which one is best." I can't know which move is best until I know what belongs where.

Following B:
Basically, the same principles apply. If you're trying to find the closest fail states, though, you need to look at the white space more than the pieces themselves. Notice the possible positions pieces can live in. Sometimes a 2-tall piece can be either above or below a 3-wide. You need to decide on whether not victory is achievable while the 2-tall piece is above that 3-wide and whether or not victory is possible while the 2-tall piece is below. You'll sniff out the end states that do not work, and you'll discover when it is impossible to move that piece out of a fail end state. Often, a piece needs to be moved into a successful half early in the game; however, there are times when a piece must be kept in fail space until you are about half way through, and then it needs to be transferred. So, you need to account for time, not only asking which pieces belong where, but also asking "... at what point in the game".


Here's the path I recommend:
1) Find the possible end states. The final 3-tall is out of the way, and the blue piece is clear.
2) Find the possible board configurations where pieces do not obstruct the main path. 2-tall pieces need to be all the way up or at 0-3y (where the bottom of the board is 0y). 3-tall pieces need to be all the way down.
3) Discover the states in which all points on the path can be simultaneously open, if there are any. If not, discover which parts of the path cannot be simultaneously open and mark these as important moves.
4) Discover how to move the blue piece to the left wall. That should be your start state in every game.
5) Work backwards from a clear-path state to discover where pieces need to be such that the path can be cleared. Make a note of all possible states that clear a path for the blue piece to move forward.
6) Work backwards from the second main-path clear state to each of the first main-path clear states. Exclude any impossible first main-path clear states from the solution.
7) Repeat steps 5 and 6 for the 3rd clear state. Repeat them for the 4th clear state.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS