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 <#94 (comment)>, 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.