Local Search

Local Search

• Maybe give up on all this fancy memory-intensive search? Our initial random-walk sliding-tile solver worked pretty good!

• Use the heuristic to guide the random walk?

• Problem: Local Minima. May get to a state s all of whose neighbors are worse than s

• Even if moving out randomly, may immediately return to s

• Solution: Mix greedy moves with random moves randomly, say 50/50. The random moves are "noise moves" and might walk out of local minima

• Solution: After a while, just "restart" and hope the random walk goes better next time

• For satisfiable instances, this works really well in practice

• Optimality is generally terrible, though: long paths still

Sliding Tile Puzzles: Local Search

• We have a couple of heuristics lying around from earlier

  • Total tile distance

  • Lexical out-of-place tiles

• Throw something together and tune:

  • Noise level

  • Restart rate

Sliding Tile Puzzles: Find An Algorithm

• Humans who play with sliding tile puzzles for a while eventually find an efficient solution algorithm

  • Put each tile in place in order by moving it there

  • When this is not possible, use a "rotation macro" to make it possible

  • When the puzzle is unsat, this will be revealed at the end when the rotation macro doesn't work

• Produces "short" paths, but perhaps not shortest

• "Easy" to teach a computer this algorithm. Can it figure it out on its own? Don't know