4 ms·
As one commenter on the post points out, there's a really simple optimization that can be done to make this much faster and avoid local minima: check for dead e
by mabbo 8y ago
As one commenter on the post points out, there's a really simple optimization that can be done to make this much faster and avoid local minima: check for dead ends ahead of time.
Example: I'm generating 5 new boards based on this one to check. In 3 of them, there is now a spot that cannot ever be reached. But the board is only half completed and from the spot I jumped to, I can still reach other places.
By trimming these options from the search at the moment of their conception, one can greatly reduce their search time.
- brazzy 8y agoThis, so much. I remember writing a solver for a different game, and already had a dead end check in it, but with increasing board size it took half an hour to find a solution. Then I added another check for a different dead end condition. This actually required quite a lot of additional work, more than doubling the time spent for evaluating each board state. But it brought down the time from 30 minutes to a fraction of a second!
- mabbo 8y agoSpend twice as long to prevent spending exponentially more time- usually worth it.
- jimsmart 8y agoAgreed, good call. Another possible optimisation might be to order the generated next-moves, so that the 'better' options are returned earlier in the list. Although I'm not sure what 'better' here means, exactly. But, through experimentation, one may find that visiting boards with more available options first, or vice versa(?), could produce a quicker route to the goal? (Making it an 'informed' search, a kind of greedy/best-first depth-first search)
- taeric 8y agoI posted it top-level, but I'll post here, as well. Look into Knuth's discussion of Exact Cover problems. He has a very elegant algorithm for this style of problem that, I believe, is quite hard to beat. (Would love for someone to prove me wrong.)