Solving the Gridlock Game
Members - Reputation: 154
Posted 18 December 2006 - 09:56 AM
Members - Reputation: 834
Posted 18 December 2006 - 10:16 AM
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"
Members - Reputation: 109
Posted 18 December 2006 - 11:31 AM
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.
Members - Reputation: 126
Posted 18 December 2006 - 01:10 PM
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.
Members - Reputation: 869
Posted 19 December 2006 - 06:43 AM
Members - Reputation: 169
Posted 19 December 2006 - 08:50 AM
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?
Members - Reputation: 154
Posted 19 December 2006 - 10:06 AM
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.
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 :)
Members - Reputation: 869
Posted 19 December 2006 - 10:58 AM
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)
Senior Moderators - Reputation: 1781
Posted 19 December 2006 - 11:06 AM
Members - Reputation: 799
Posted 19 December 2006 - 01:25 PM
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
Senior Moderators - Reputation: 1781
Posted 20 December 2006 - 03:25 AM
Posted 23 December 2006 - 03:43 AM
Posted 29 December 2006 - 08:23 AM
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?
Members - Reputation: 100
Posted 19 January 2012 - 10:02 AM
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....
A) Have the computer calculate viable end states for the board, itself.
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.
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.
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.
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.
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.