Comment by GistNoesis

Comment by GistNoesis 4 days ago

You may need to add some factor for the Hamming distance to make it admissible. On a 4x4 board each move change at most 4 bits. So 4 x the hamming distance should be OK.

Edit: I 'm maybe getting this wrong confusing lower bound and upper bound. Sorry I'm a little rusty.

Edit2: For 4x4 one lower bound is hamming distance/4 , because you need at least these many moves to reach the goal. For 5x5 hamming distance / 5 and so on... But not sure how much this will reduce the need to graph.

dooglius 4 days ago

Hamming distance doesn't strike me as a useful metric here because how "close" two rows are is entirely dependent on what the other rows are. E.g. if you have a row of all 1's then two rows with maximal hamming distance are only one move away and if on average you have a bunch of n/2-weight rows then two rows different by 1 bit are not close. The best you can do is count the number of total rows matching the target I think?

Reply View 1 reply

vitus 4 days ago

Yeah, that was what I tried with row-Hamming / col-Hamming (namely: treat entire rows / cols as matches or not). I then used the min of the two to address those issues.
Either way, I guess my implementation had a bug -- A* does yield a significant speedup, but adding the 0.25x scaling factor to ensure that the heuristic is admissible loses almost all of those gains.
For some concrete numbers: with the bug that basically reduced to BFS, it ran in about 7s; with the bug fixed but a wildly inadmissible heuristic, it ran in about 0.01s; with the heuristic scaled down by 4x to guarantee its admissibility, it ran in about 5s.
I think scaling it down by 2x would be sufficient: that lower bound would be tight if the problem is one row move and one column move away from the goal state, but potentially all four rows and columns would not match. In that case, it ran in about 1.6s.

Reply View | 0 replies

fuglede_ 4 days ago

Thanks for sharing your thoughts!

I know of some work on trying out various heuristics for A*; Section 5 of https://arxiv.org/pdf/2201.06508 gives some examples of what works and what doesn't. I don't think D* Lite specifically has ever featured. There's plenty of room for trying to come up with other heuristics, and just for other takes in general.

> But for bigger boards you won't be able to materialize the whole graph.

If we restrict to boards corresponding to solvable puzzles, the number of vertices is https://oeis.org/A002884 (1, 1, 6, 168, 20160, 9999360, 20158709760, …) and indeed grows quickly. It's possible to manipulate the 7×7 case (https://arxiv.org/abs/2503.01467, shameless plug) but anything bigger than that seems hard.

One can ask, for example, how many moves are needed for the hardest n×n Swapple. For n = 1, …, 7 the answers are 0, 3, 6, 9, 12, 15, 18 respectively, but we don't know what the answer is for n = 8.

Reply View 0 replies