ohasangit
commented
9 years ago I think we should first classify the scenarios in which this algorithm would be needed. Certain board reconfigurations are impossible to achieve, and we should try to catch these early on. On the other hand, there are many cases in which a human would be able to intuitively reach a minimal solution, and we want to make sure that our algorithm reaches the same result in these cases.
I think the worst case scenario would be akin to a sliding puzzle problem: http://www.cs.cmu.edu/~adamchik/15-121/labs/HW-7%20Slide%20Puzzle/lab.html http://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pdf
Classification of these problems may help us with heuristics or even switching between algorithms depending on what kind of problem we are detecting. Though we want a general motion planner in the end, we may not be able to optimize or catch every edge case without this kind of detection.
I propose the following algorithm:
Evaluation functions would be required both for choosing the best candidate piece for movement and for picking the best resulting board configuration. I have a couple of ideas for heuristics for these so far.
For the piece selection, we could choose pieces based on their proximity to pieces that are displaced from their desired destination. In other words, prefer pieces that are themselves displaced, then prefer pieces whose neighbors are displaced, etc. On top of this, we could have a heuristic that prefers "captured" pieces to those doing the capturing.
For the board configuration, we should try to minimize the total Manhattan distance of pieces away from their desired positions. Additionally, we could have some sort of measure of mobility in a given board configuration. Board positions that free up congestion (increase mobility) would be preferred.