12:00, Wed 22 Oct 1997, WeH 7220 Latest Results with STAGE on Satisfiability Problems Justin Boyan STAGE is a new search technique which learns a problem-specific heuristic evaluation function as it searches. The heuristic is trained to predict, from features of states along the search trajectory, how well a fast search method such as hillclimbing will perform starting from each state. The search works by alternating between two stages: performing the fast search to gather new training data, and following the learned heuristic to reach a promising new start state. STAGE has produced good to excellent results on a variety of combinatorial optimization domains, including VLSI channel routing, map layout, and binpacking. In this talk, I will concentrate on presenting new results from the domain of Boolean formula satisfiability, where Selman and Kautz's WALKSAT algorithm currently reigns supreme.