Hacker News Reader

Comment by CyberShadow | Hacker News Reader

Solver and solutions:

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:

    prevStates = (prevStates ~ states).sort.uniq.array();
    states = nextStates.sort.uniq.setDifference(prevStates).array();
    // ... expand states into nextStates ...

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.

View on HN

DDD was new to me, and I was wondering how sorting all previously visited states could be faster than checking a hash table. The answer appears to be:

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...

I wrote a solver as a chrome extension : https://github.com/tburette/gameaboutsquaressolver

Javascript is not the best language to write AI.

Nice work.

Reply on news.ycombinator.com