5 ms·

https://davidkoloski.me/blog/intelligent-brute-forcing/ https://davidkoloski.me/blog/intelligent-brute-forcing/ might help, if you don't already have some sort

by asicsp 4y ago

https://davidkoloski.me/blog/intelligent-brute-forcing/ https://davidkoloski.me/blog/intelligent-brute-forcing/ might help, if you don't already have some sort of automatic solver to figure out solutions.

freediver 4y ago
This was a great read, thanks for posting. Would like to see similar quality article for solution to similar problems using genetic algorithms.
- sterlind 4y ago
  I dunno how you'd use genetic algorithms, since solutions are paths, and there's usually no way to splice segments of candidate paths together. This kind of problem is known as planning in old AI, and it's languishing. most techniques are just variations of A*, with things like symmetry detection and heuristics tailored to game benchmark problems. It's the kind of thing (IMO) that deep RL fails at, since unlike Chess or Go where your solution-finding simply needs to beat a competitor, here your solution needs to be exactly correct (and ideally minimal.) It's very sparse.
sumul 4y ago
This is excellent, thanks for sharing. My solver is designed to find every possible solution so that I can evaluate the ratio of "best" solutions to all solutions. A lot of these optimizations are super interesting, but since I'm intentionally going for comprehensive brute force (rather than finding any winning solution as quickly as possible), they're mostly off the table, at least as long as puzzles are randomly generated and I need to filter them based on solution space characteristics like this. I did realize while reading this that I could get a little more sophisticated by finding out the number of moves in a best solution using an aggressively optimized fast solver. If that number is within a range that's fun to play, say 8-11 moves, then go ahead and find all the rest of the solutions with the maximum brute force. If not, then just scrub the whole thing since I wouldn't use that puzzle anyway.

by asicsp 4y ago

freediver 4y ago

This was a great read, thanks for posting. Would like to see similar quality article for solution to similar problems using genetic algorithms.

sterlind 4y ago
I dunno how you'd use genetic algorithms, since solutions are paths, and there's usually no way to splice segments of candidate paths together. This kind of problem is known as planning in old AI, and it's languishing. most techniques are just variations of A*, with things like symmetry detection and heuristics tailored to game benchmark problems. It's the kind of thing (IMO) that deep RL fails at, since unlike Chess or Go where your solution-finding simply needs to beat a competitor, here your solution needs to be exactly correct (and ideally minimal.) It's very sparse.

sumul 4y ago

This is excellent, thanks for sharing. My solver is designed to find every possible solution so that I can evaluate the ratio of "best" solutions to all solutions. A lot of these optimizations are super interesting, but since I'm intentionally going for comprehensive brute force (rather than finding any winning solution as quickly as possible), they're mostly off the table, at least as long as puzzles are randomly generated and I need to filter them based on solution space characteristics like this. I did realize while reading this that I could get a little more sophisticated by finding out the number of moves in a best solution using an aggressively optimized fast solver. If that number is within a range that's fun to play, say 8-11 moves, then go ahead and find all the rest of the solutions with the maximum brute force. If not, then just scrub the whole thing since I wouldn't use that puzzle anyway.