Discovery & AI
Computer Search and Rules of Thumb
Also called: Heuristic search
- Personal interest
- Formal theory
- Working interpretation
Computers can search through far more possibilities than intuition alone, using logic solvers, optimization, listing every case, or trial-and-improve methods inspired by evolution. The skill is building a search whose answers can be checked and understood.
How can I set up a search that saves effort without skipping cases that matter?
Why it attracts me
Some questions can be settled by looking at every possibility, if you can afford to. Others have so many possibilities that you need clever shortcuts. I like both, especially when a well-built search comes back with something exact.
The idea
A search has three parts: the set of candidates, a way to move through it, and a test for success. Rules of thumb (computer scientists call them heuristics) decide where to look first. They save enormous effort, but they can also hide cases. A good search gives answers that can be checked independently and states its coverage plainly. Finding an answer may take a huge search while checking it takes seconds, and that imbalance is what makes computer search so useful for discovery (AI Systems That Discover, Not Just Summarize).
An example
In my Scheduling Optimization Lab, seven jobs share one machine, and simple rules of thumb compete against the best order, found by checking all 5,040 possible orders. My Kryptos K4 side quest shows the other side. Exact searches there have ruled out large, clearly defined families of possible cipher methods, but the page is careful that each one is ruled out only in the exact form that was searched. By contrast, a public decoding method, once its lookup tables were left free to adjust, could fit 200 of 200 random test messages, so fitting one proposed message was not evidence for it.
Where it connects
Puzzles and codes (Puzzles and Secret Codes) are where I practice this on a small scale. The math of networks (Networks: The Math of Connections) turns curiosity about structure into questions a search can answer.
What this does not establish
A search that finds nothing rules out only the cases it actually covered. It does not show that no answer exists, and a fast rule of thumb can miss the case that matters.
Questions I'm still exploring
- How do I show that a search really covered every case it claims to cover?
- When is a rule of thumb good enough, and when do I need to check everything?
- How can a search report what it skipped, not only what it found?
Sources and further reading
- Marijn J. H. Heule, Oliver Kullmann and Victor W. Marek, "Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer" (SAT 2016) — A huge logic-solver search that settled a math question and produced a proof that could be checked independently.
- Judea Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving (Addison-Wesley, 1984)
Working interpretation: drafted from my notes and interests for review. It is not a direct quotation, and I may still change it.