Terminate `IDFSearch` when two consecutive depths reach the same number of moves

[lgarron]

This can help prevent infinite search in situations where a solution was provided but the state space is small enough to enumerate during normal search.

[ArhanChaudhary]

A little unrelated, but shouldn't this be called IDAStarSearch or something similar? Iterative deepening search with pruning tables is IDA*, right?

[lgarron]

A little unrelated, but shouldn't this be called IDAStarSearch or something similar? Iterative deepening search with pruning tables is IDA*, right?

I don't know that we have enough heuristics in place to qualify as A*? @rokicki probably knows more.

[rokicki]

Right. What we do is pretty basic IDFS. We do have a heuristic, but we do not order the children by that heuristic and "explore most promising children first" so I don't think it really qualifies as IDA*.

I'd be happy to look at references that suggest I'm wrong, however.

On Tue, Jan 14, 2025 at 3:07 PM Lucas Garron @.***> wrote:

A little unrelated, but shouldn't this be called IDAStarSearch or something similar? Iterative deepening search with pruning tables is IDA*, right?

I don't know that we have enough heuristics in place to qualify as A*? @rokicki https://github.com/rokicki probably knows more.

— Reply to this email directly, view it on GitHub https://github.com/cubing/twsearch/issues/94#issuecomment-2591287255, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLS3CYSQPZMQ3HQ2WL2D2KWKB3AVCNFSM6AAAAABVCEVY3WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKOJRGI4DOMRVGU . You are receiving this because you were mentioned.Message ID: @.***>

--

• https://cube20.org/ http://cube20.org/ - https://golly.sf.net/ http://golly.sf.net/ - https://alpha.twizzle.net/ / -

[ArhanChaudhary]

A little unrelated, but shouldn't this be called IDAStarSearch or something similar? Iterative deepening search with pruning tables is IDA*, right?

I don't know that we have enough heuristics in place to qualify as A*? @rokicki probably knows more.

@rokicki and I talked about this some time earlier, and we concluded that the IDA* was indeed the correct terminology for what C++ twsearch uses (see https://cubing-org.slack.com/archives/CKD5E53A4/p1737658381579609). Is there any specific reason why Rust twsearch uses IDFS instead of IDA*? Your HashPruningTable implementation does give a lower bound, which makes IDA* applicable.

[lgarron]

Is there any specific reason why Rust twsearch uses IDFS instead of IDA*?

Yes, the reason cited above. It was named before you and @rokicki talked. :P

Additionally, the IDFS struct can take a non-trivial prune table as a SearchAdaptation and does so for KPuzzle by default, but it doesn't have to. So it is in fact only in charge of the DFS with iterative deepeding.

[ArhanChaudhary]

Is there any specific reason why Rust twsearch uses IDFS instead of IDA*?

Yes, the reason cited above. It was named before you and @rokicki talked. :P

Additionally, the IDFS struct can take a non-trivial prune table as a SearchAdaptation and does so for KPuzzle by default, but it doesn't have to. So it is in fact only in charge of the DFS with iterative deepeding.

Sorry, let me be more specific in what I mean. Rust twsearch seems to do the recursive step of IDA*.

https://github.com/cubing/twsearch/blob/d029155d0c7509d99642382af3397b209800793a/src/rs/_internal/search/idf_search/idf_search.rs#L347

This matches the IDA* wikipedia's pseudocode:

function search(path, g, bound)
    node := path.last
    f := g + h(node)
    if f > bound then return f

So that seems to be fine and dandy. However, Rust twsearch does not seem to relay the minimum heuristic information upstream:

https://github.com/cubing/twsearch/blob/d029155d0c7509d99642382af3397b209800793a/src/rs/_internal/search/idf_search/idf_search.rs#L275

Once again from wikipedia's pseudocode:

procedure ida_star(root)
    bound := h(root)
    path := [root]
    loop
        t := search(path, 0, bound)
        if t = FOUND then return (path, bound)
        if t = ∞ then return NOT_FOUND
        bound := t
    end loop
end procedure

I brought my above concern above specifically because of this observation. I interpreted the code as just a slightly faster version of IDFS rather then IDA*, hence why I proclaimed that in the above.

[lgarron]

If the the code were implemented from an algorithm or spec, I suspect we would have more meaningful answers to your questions.

But there is a lot of design work in that code to be done, and therefore a lot of missing features.

If you want to tackle passing up the heuristic feel free, else I'm not sure when we'd have time to get to experimenting with it.

[rokicki]

We do the first level. (Regarding moves on the same axis.) That’s almost all the benefit.

• https://cube20.org/ http://cube20.org/ - https://golly.sf.net/ http://golly.sf.net/ - https://alpha.twizzle.net/ / -

On Sun, Feb 23, 2025 at 10:47 AM Lucas Garron @.***> wrote:

If the the code were implemented from an algorithm or spec, I suspect we would have more meaningful answers to your questions.

But there is a lot of design work in that code to be done, and therefore a lot of missing features.

If you want to tackle passing up the heuristic feel free, else I'm not sure when we'd have time to get to experimenting with it.

— Reply to this email directly, view it on GitHub https://github.com/cubing/twsearch/issues/94#issuecomment-2677057934, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLSYR4R3DTAFW5REEHKD2RIJS7AVCNFSM6AAAAABVCEVY3WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDMNZXGA2TOOJTGQ . You are receiving this because you were mentioned.Message ID: @.***> [image: lgarron]lgarron left a comment (cubing/twsearch#94) https://github.com/cubing/twsearch/issues/94#issuecomment-2677057934

If the the code were implemented from an algorithm or spec, I suspect we would have more meaningful answers to your questions.

But there is a lot of design work in that code to be done, and therefore a lot of missing features.

If you want to tackle passing up the heuristic feel free, else I'm not sure when we'd have time to get to experimenting with it.

— Reply to this email directly, view it on GitHub https://github.com/cubing/twsearch/issues/94#issuecomment-2677057934, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMOLSYR4R3DTAFW5REEHKD2RIJS7AVCNFSM6AAAAABVCEVY3WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDMNZXGA2TOOJTGQ . You are receiving this because you were mentioned.Message ID: @.***>