The RushHour Puzzle – an Artificial Intelligence Toy Problem
What’s the RushHour Puzzle about?
The RushHour puzzle is a sliding block puzzle and one of the toy problems of Artificial Intelligence. It’s about moving cars on a game board, that are stuck in traffic, so that the main car can exit the traffic. Each car can only move forward/backward on it’s lane. You probably already have seen such boards (and you can find a massive amount of applets for playing the RushHour Puzzle online, e.g. here, here or here, to only name a few):
Solving Point 1 of Part I and Part II of the RushHour puzzle problem of the University of Princeton of has recently been scope of our homework during my MSc studies. The harder of the tasks is to implement the “AdvancedHeuristic”, a heuristic that is consistent on the one hand and better than the blocking cars heuristic on the other hand. Consequentially it still has to be computationally cheap enough to let A* produce better results fast – otherwise it has missed it’s target.
I’ve chosen to implement a voting system, where each car that blocks the lane of the red car can vote for how it wants to free the lane (=”exit strategy”). The exit strategies that have the best amount-of-cars-that-voted-for-this-exit-strategy/amount-of-cars-to-be-moved are going to get applied, until the lane is free. The total amount of cars to be moved for sure is the heuristic value then. E.g. for the picture above, the size-3 purple car is blocking the lane of the red car. It cannot move up, as there is too less space for this car. It’s exit strategy will be down, for which the size-2 black car and the size-3 blue car have to be moved.This will be the exit strategy the purple car votes for. Calculation of the heuristic value = sum of moves to be done at least until the puzzle has been completed:
- Move blue and black car: 2 moves
- Move purple car: 1 move
- Move red car: 1 move
Therefore this advanced heuristic will return the value 4.
Why didn’t I choose a less complicated heuristic? Because there are several special cases for which other heuristics will fail to deliver a consistent result (consistency was required for the homework, although there are many non-consistent heuristics that still deliver exact results, and do it way faster than this approach) – see report for more details. And just for completion: there are further approaches for consistent heuristics conceivable. One would be to sort the nodes on open “correctly” with using floating point weights instead of pure integer weights.
java binary, md5: f7581a20242bcf3f037daf83574d5d76, sha1: 61405903363f6107deb44edf3d42f35b52e47398
java source, md5: 2bb50230d606cd6583b842e2c5df1d5c, sha1: b19883a839ffb5db3d9f3a0f2e56d0cfa07489bd
report, md5: cc2e69551aa929458637a7f01762a608, sha1: 915e2478477691309704c1377adcedf12a0dde94
The report was made for the purpose of my studies only and is no highly sophisticated scientific work – so you may have to dig into the code yourself to fully understand how the mentioned heuristic is working.