Possible buggy heuristic implementation

[dingyuchen]

slidingpuzzle/src/slidingpuzzle/heuristics.py

Line 328 in 458308d

line[np.argmax(line_conflicts)] = BLANK

According to _hannson, the conflict count for a row should be the number of tiles needed to be removed to resolve the conflict, times 2. For example, for a the middle row in an 8-puzzle, [6, 5, 4] should have 2 * 2 added to the heuristic value; 6 and 5 can be moved out of the row, 4 slides into position while staying on the row, 5 and 6 slides back.
Cmiiw, your implementation does not account for this detail.

slidingpuzzle/tests/test_heuristics.py

Line 87 in 458308d

assert linear_conflict_distance(board) == 8

I believe the testcase should also be 6 instead of 8

[entangledloops]

Hi @dingyuchen! Thanks for checking out my project.

You are correct that the algorithm isn't implemented exactly the same as paper on the line in question (although they are equivalent).
I have now modified the code to more closely reflect the paper in code. However, I don't think your math matches the description as published, so I've gone ahead below and walked through the algorithm exactly as documented. (But feel free to correct me if you think I'm wrong.)

I went back and reviewed the paper and algorithm to see how I arrived at my implementation.
Prior to the section you quote, it is important to review the definition of a linear conflict:

Definition 6: Two tiles j and k are in a linear conflict if j and k are in the same line, the goal positions of j and k are both in that line, j is to the right of k, and the goal position of j is to the left of the goal position of k.

The algorithm, as you have posted above, reads as follows (for each row, summarized):

1. For each pair of tiles, count the number of conflicts
2. While there are conflicts:
   • Find the tile with largest number of conflicts.
   • Set its conflict count to 0.
   • Decrement all other conflict counts by 1.
   • Add 2 to our total distance. (Or equivalently, add 1 now and then multiply the total by 2 at the end.)

Our board:

1, 2, 3
6, 5, 4
7, 8, 0

Now let's walk through the algorithm on the row of interest [6, 5, 4] as specified, applying Definition 6.

Step 1:

• Let conflict counts = [0, 0, 0].
• Let k = 6.
  • Let j = 5.
    • Same line? Yes.
    • Goal positions on this line? Yes.
    • j is right of k? Yes.
    • Goal position of j (5) is left of goal position of k (6)? Yes.
    • There is a conflict. Increment their conflict counts: [1, 1, 0].
  • Let j = 4. Same reasoning.
    • Conflict counts: [2, 1, 1]
• Let k = 5.
  • Let j = 6. No conflict, b/c we don't have "the goal position of j is to the left of the goal position of k".
  • Let j = 4.
    • Same line? Yes.
    • Goal positions on this line? Yes.
    • j is right of k? Yes.
    • Goal position of j (4) is left of goal position of k (5)? Yes.
    • There is a conflict. Increment counters: [2, 2, 2].
• Let k = 4.
  • Let j = 6. No conflict, b/c we don't have "the goal position of j is to the left of the goal position of k".
  • Let j = 5. No conflict, b/c we don't have "the goal position of j is to the left of the goal position of k".

Final conflict counts: [2, 2, 2]

Step 2:

• Are there still conflicts? Yes.
  • The 6 tile (or any tile in this case) has largest number of conflicts.
  • Set its count to 0. Decrement all other counts by 1.
  • Current counts: [0, 1, 1]
  • Total distance: 2
• Are there still conflicts? Yes.
  • Tile 5 tile is largest. Set it 0. Decrement others.
    • Current counts: [0, 0, 0]
  • Total distance: 4
• Are there still conflicts? No.

So I arrive at a total count of 4.

However, there is more to the full implementation that I provide here (and as described in the paper).
Don't forget that this heuristic is combined with 3 others in an admissible way:

• Manhattan distance (adds 4, for the 6 and 4 tiles being out-of-place)
• Last moves (adds 0)
• Corner tiles (adds 0)

Our final total should be 8.

I have also validated this algortihm against BFS on all possible 3x3, 3x4, 4x3, and 4x4 boards. Although that isn't a proof, it does increase my confidence that I am at least not overcounting, as we would have almost certainly hit at least 1 board where the solution overshoots the distance and does not match BFS. (And in fact, in earlier versions of my code there were bugs that were caught by running through all possible boards.)

[entangledloops]

Re-opening b/c exhaustive test is now failing after latest change:

    def test_linear_conflict_distance_exhaustive():
        start = 0
        stop = None
        for i, b in enumerate(board_generator(3, 3, start, stop)):
            expected = len(search(b, heuristic=manhattan_distance).solution)
            actual = len(search(b, heuristic=linear_conflict_distance).solution)
>           assert expected == actual, f"{start + i}: {b}"
E           AssertionError: 3737: [[0 2 5]
E              [4 3 6]
E              [8 1 7]]
E           assert 18 == 20

[dingyuchen]

However, there is more to the full implementation that I provide here (and as described in the paper).
Don't forget that this heuristic is combined with 3 others in an admissible way:

Manhattan distance (adds 4, for the 6 and 4 tiles being out-of-place)
Last moves (adds 0)
Corner tiles (adds 0)
Our final total should be 8.

I see, I realised I missed out on the initialization value of dist. In that case I agree that the test result should be 8. I am unfamiliar with numpy syntax but I found it weird that the final result is still 8 after adding the decrementing.
Regardless, I trust that you've verified the math and it is correct for this case.

Decrement all other conflict counts by 1.

However, I still have doubt that this is equivalent to the algorithm published in the paper. If I have a 15puzzle with first row [2, 1, 4, 3]. My final conflict count would be [1, 1, 1, 1].
If we naively decrement all other conflicts, we would arrive at a total count of 2. However, there is under-counting since (1,2) and (3, 4) form 2 distinct "conflict groups". Each group needs to be counted separately as resolving one group's conflict will not resolve the other.
The conflict count should follow a transition like [1, 1, 1, 1] -> [0, 0, 1, 1] -> [0, 0, 0, 0], which can be hard to do by representing the conflict information like this, as we cannot determine which other tiles a tile is in conflict with.

[entangledloops]

You are correct that I should not decrement all other conflicts---only the tiles that we were originally in conflict with. I recall this is the reason I originally implemented it by setting the largest conflicting tile to be a "fake" blank, and then simply recompute conflicts from scratch. I found this to be easier to reason about. I'm going to change that back.

Secondly, the error above is actually unrelated to my recent change---it is due to last moves/corner tiles distance. When that is removed, the exhaustive search actually passes. It appears my has_col_conflict/has_row_conflict forgot to ensure that we are in the goal row/col. Going to fix this and then issue a patch. Thanks for bringing this up anyway, as it led to detecting bugs!

[entangledloops]

Okay, figured it all out. Multiple bugs here:

• Conditions on conflicts were not implemented exactly as I described above (did not check if both tiles are also in their goal line)
• Corner heuristic incorrectly ignored linear conflicts with corner tiles
• Corner heuristic cannot be used safely on boards < 4x4, b/c it conflicts not only with last moves heuristic, but also itself.
  For example, consider this board (relevant tiles shown):

X X X
X X X
1 8 0

On this board, the 8 tile move distance is already accounted for by bottom-left corner heuristic, but then is double-counted by the last moves heuristic. An analogous situation happens at top of board:

1 4 2
X X X
X X X

Here, the top-left and top-right corners double-count the 4, b/c there is no gap between corner-adjacent tiles on such small boards.

I have also added:

• the ability to disable optimizations in LCD (i.e. disable Manhattan, corner, last moves) and tests for both cases
• new (much faster) exhaustive test that leverages the datasets I uploaded to HuggingFace