Prolog - Solving game, implementing heuristics

问题:

I want to solve a 'game'. I have 5 circles, we can rotate circles into left or into right (90 degrees).

Example:

Goal: 1,2,3,....,14,15,16 Ex. of starting situations: 16,15,14,...,3,2,1

I'm using BFS.

Heuristic function:

       heuristic(NextState,Goal,H)),

Desctiption of function:

For each number 1 <= i <= 16, find the minimum number of rotations needed to put i back in its correct position (disregarding all other numbers)
Take the maximum over all these minimums.

This amounts to reporting minimum number of rotations needed to position the "worst" number correctly, and will therefore never overestimate the number of moves needed (since fixing all numbers' positions simultaneously requires at least as many moves as fixing any one of them).

How it should be looks?

Example for circle A:

heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),0).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,A,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),1).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,A,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,A],[_,_,_,_],[_,_,_,_],[_,_,_,_]),5).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[A,_,_,_],[_,_,_,_],[_,_,_,_]),1).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,A,_,_],[_,_,_,_],[_,_,_,_]),2).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,A,_],[_,_,_,_],[_,_,_,_]),3).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,A],[_,_,_,_],[_,_,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[A,_,_,_],[_,_,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,A,_,_],[_,_,_,_]),3).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,A,_],[_,_,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,A],[_,_,_,_]),5).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,_],[A,_,_,_]),5).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,_],[_,A,_,_]),4).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,A,_]),5).
heuristic(tiles([A,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,_]),tiles([_,_,_,_],[_,_,_,_],[_,_,_,_],[_,_,_,A]),6).

Is it a good idea?

回答1:

It looks like you're trying to implement the admissible heuristic I suggested here.

I can't tell what you're trying to do with your "example for circle A" code at all, I'm afraid. The way to calculate the minimum number of rotations needed to move a particular number i from its current position to its final, correct position is by treating it as a special kind of shortest-path problem, in which:

1. There is a vertex for each position that i could be in (so 16 vertices in all).
2. There is an edge between a pair of vertices x and y whenever there is a circle that can be rotated 90 degrees (in either direction) to move whatever number is in position x to position y.

For concreteness, let's label the positions (and therefore the vertices) with letters A-P as follows:

ABCD
EFGH
IJKL
MNOP

So for example the edges leaving vertex B are to:

1. A (since rotating the top-left wheel anticlockwise will move whatever is at B to A)
2. F (since rotating the top-left wheel clockwise will move whatever is at B to F)

Rotating any of the other 4 wheels has no effect on the number in position B, so those are the only edges leaving vertex B.

Some other vertices have more edges. E.g. F has edges to:

1. B (rotating the top-left wheel anticlockwise)
2. E (rotating the top-left wheel clockwise)
3. G (rotating the centre wheel clockwise)
4. J (rotating the centre wheel anticlockwise)

Edges are unweighted (or equivalently, have weight 1) and are bidirectional, since every 90-degree rotation can be undone by the reverse rotation.

Suppose we want to calculate the minimum number of rotations needed to get the number 9 from its initial position (let's say B) to its final, correct position, I.

Traversing an edge is equivalent to rotating some circle 90 degrees, so to find the minimum number of rotations needed to move number 9 from position B to position I, we want to find a path connecting vertices B and I that uses the minimum possible number of edges. Because all edges have weight 1, this can be solved efficiently using breadth first search (if edges had various weights, you could use Dijkstra's algorithm instead). In the case of 9, the answer will be 3 (e.g. B->F->J->I).

So, that explains how to calculate the minimum number of rotations for moving a particular number home. To calculate the heuristic, do this for each of the numbers in the initial configuration, and pick the maximum overall. (Notice that the graph is the same in each case -- only the start and destination vertices will change.) This is your guaranteed-admissible heuristic rotation count value.