Weighting for Godot: Learning Heuristics for GSAT

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Stochastic Search

We investigate an improvement to GSAT which associates a weight with each clause. GSAT moves to assignments maximizing the weight of satisfied clauses and this weight is incremented when GSAT moves to an assignment in which this clause is unsatisfied. We present results showing that this algorithm and its variants outperform one of the best known modifications of GSAT to date using two metrics: number of solved problems on a single try, and minimum mean number of flips to solve a test suite of problems.