Solving the Gridlock Game

sled · 2012-01-20T14:04:22

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?

Artificial Intelligence Programming

Started by sled December 18, 2006 03:56 PM

22 comments, last by IADaveMark 12 years, 4 months ago

IADaveMark

3,839

January 19, 2012 10:02 PM

Not having read the entire thread, this seems awfully similar to the 15 puzzle (sliding number puzzle). That can be solved with a search algorithm with the heuristic being the manhattan distance that each block needs to move to its appropriate spot. In this case, if I understand correctly, we only have one block that we are concerned with getting to a goal state. Therefore, the heuristic is how many moves it would take to get to the goal if there were no other obstacles.

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

DarrylStein

653

January 20, 2012 12:04 AM

Coincidentally just read about this problem recently in the book "Evolved to Win" http://www.moshesipper.com/etw/.
Apparently its quite a hard puzzle to solve. The book gives the most recent best efforts based on genetic programming.
Chapter 10 is pertinant

alh420

5,995

January 20, 2012 01:28 PM

This is an ancient thread.
Though I'm not surprised its a lot harder to come up with a good heuristic for this puzzle then the 15slide puzzle.
Since the efficiency of the search depend _a_lot_ on the heuristic.
You want one with a good resolution so as few states as possible have the same heuristic.
If you only check the distance of the blue piece, you will have very many states that have the same heuristic.
This will reduce the A* search to resemble a simple brute force breadth first search.

IADaveMark

3,839

January 20, 2012 02:04 PM

This is an ancient thread.

Holy hell... you aren't kidding. I may need to smite someone for necro'ing this thing.

Solving the Gridlock Game

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Solving the Gridlock Game

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines