Benjamin Jantzen (Virginia Tech), Cruz Davis (University of Massachusetts, Amherst)
Recently, one of us presented a paper on the history of “algorithmic discovery” at an academic conference. As we intend the term, algorithmic discovery is the production of novel and plausible empirical generalizations by means of an effective procedure, a method that is explicitly represented and executed in finitely many steps. In other words, we understand it to be discovery by computable algorithm. An anonymous reviewer for the conference saw things differently, helpfully explaining that “[a]nother, more common name for algorithmic discovery would be heuristics.” This comment prompted us to investigate further to see what differences (if any) there are between heuristics and algorithmic discovery.
The aim of this paper is to compare and contrast heuristics with algorithmic discovery and to explore the consequences of these distinctions within their applications in science and other areas. To achieve the first goal the term ‘heuristic’ is treated as a family resemblance concept. So for a method or rule to be classified as a heuristic it will have to satisfy a sufficient number of the properties involved in the family resemblance. There are eight features that we specify that are involved with being a heuristic. The first five correspond to the heuristic search program in artificial intelligence. The last three pick out more general characterizations of heuristics as methods that lack a guarantee, are rules of thumb, or transform one set of problems into another. We argue that there are methods of algorithmic discovery that have none of the eight features associated with heuristics. Thus, there are methods of algorithmic discovery which are distinct from heuristics.
Once we’ve established that heuristic methods do not exhaust the methods of algorithmic discovery, we compare heuristic methods with non-heuristic discovery methods in their application. This is achieved by discussing two different areas of application. First, we discuss how heuristic and non-heuristic methods perform in different gaming environments such as checkers, chess, go, and video games. We find that while heuristics perform well in some environments – like chess and checkers – non-heuristic methods perform better in others. And, interestingly, hybrid methods perform well in yet other environments. Secondly, heuristic and non-heuristic methods are compared in their performance in empirical discovery. We discuss how effective each type of method is in discovering chemical structure, finding diagnoses in medicine, learning causal structure, and finding natural kinds. Again, we find that heuristic and non-heuristic methods perform well in different cases.
We conclude by discussing the sources of the effectiveness of heuristic and non-heuristic methods. Heuristic and non-heuristic methods are discussed in relation to how they are affected by the frame problem and the problem of induction. We argue that the recent explosion of non-heuristic methods is due to how heuristic methods tend to be afflicted by these problems while non-heuristic methods are not.
