1. Duplicate detection is done delayed and in bulk, not after expanding each node
2. The linear memory access of the bulk check is more cache friendly than random-like hash table access
Allow me to quote from the first Google result:
Surprisingly, delayed duplicate detection is useful even when all nodes fit in memory, resulting in reduced running time due to improved cache performance. In the standard implementation of breadth-first search in memory, the Open list is stored in a hash table. As each new node is generated, it is looked up in the hash table, which often results in a cache miss, since the hash function is designed to randomly scatter the nodes.
http://www.ijcai.org/Past%20Proceedings/IJCAI-2003/PDF/267.p...
Javascript is not the best language to write AI.
https://gist.github.com/CyberShadow/39f43cf25dac0534f8a9
The solver uses BFS with delayed duplicate detection for pruning visited states (instead of, say, hash tables).
The DDD part can be summed up in two lines of code:
These were part of the solver's code at one point, although now I've expanded them a bit to improve memory efficiency.I love D.