Jak dotąd w tej książce widzieliśmy kilka lokalnych algorytmów wyszukiwania, w tym HILL-CLIMBING i SIMULATED-ANNEALING. Algorytmy te można zastosować bezpośrednio do problemów spełnialności, pod warunkiem, że dobierzemy odpowiednią funkcję oceny. Ponieważ celem jest znalezienie przypisania, które spełnia każdą klauzulę, funkcja oceny, która zlicza liczbę niespełnionych klauzul, wykona zadanie. W rzeczywistości jest to dokładnie miara używana przez algorytm MIN-CONFLICTS dla CSP (strona 198). Wszystkie te algorytmy wykonują kroki w przestrzeni pełnych przypisań, odwracając wartość logiczną jednego symbolu na raz. Przestrzeń zawiera zwykle wiele minimów lokalnych, przed którymi trzeba uciec, od których wymagane są różne formy losowości. W ostatnich latach przeprowadzono wiele eksperymentów, aby znaleźć dobrą równowagę między zachłannością a przypadkowością. Jeden z najprostszych i najskuteczniejszych algorytmów, jaki wyłonił się z całej tej pracy, nazywa się WALKSAT.
W każdej iteracji algorytm wybiera klauzulę niespełnioną i wybiera symbol w klauzuli do odwrócenia. Wybiera losowo jeden z dwóch sposobów wyboru symbolu do odwrócenia: (1) krok „min-konfliktów”, który minimalizuje liczbę niespełnionych klauzul w nowym stanie i (2) krok „losowego spaceru”, który losowo wybiera symbol.
Kiedy WALKSAT zwraca model, zdanie wejściowe jest rzeczywiście spełnialne, ale gdy zwraca niepowodzenie, możliwe są dwie przyczyny: albo zdanie jest niespełnialne, albo musimy dać algorytmowi więcej czasu. Jeśli ustawimy max_flips = ∞ i P > 0 , WALKSAT w końcu zwróci model (jeśli taki istnieje), ponieważ kroki błądzenia losowego w końcu dotrą do rozwiązania. Niestety, jeśli max_flips to nieskończoność, a zdanie jest niezadowalające, to algorytm nigdy się nie kończy! Z tego powodu WALKSAT jest najbardziej przydatny, gdy oczekujemy rozwiązania — na przykład problemy omówione w rozdziałach 3 i 6 zwykle mają rozwiązania. Z drugiej strony WALKSAT nie zawsze może wykryć niespełnienie, które jest wymagane do podjęcia decyzji o pociągnięciu. Na przykład agent nie może niezawodnie użyć WALKSAT, aby udowodnić, że kwadrat jest bezpieczny w świecie Wumpusa. Zamiast tego może powiedzieć: „Myślałem o tym przez godzinę i nie mogłem wymyślić możliwego świata, w którym plac nie jest bezpieczny”. To może być dobry wskaźnik empiryczny że plac jest bezpieczny, ale na pewno nie jest to dowód.