An adaptive plan for state-space problems
Larry A. Rendell · 1981
An adaptive plan (meta-strategy) is described which automatically generates evaluation functions for state-space problems, and which has created a function that solves the fifteen puzzle with (locally) optimal parameters. An attribute space is defined by a vector of features (functions mapping states into integers) supplied by the user. Structures (clusters) are formed in the attribute space which represent local (and often veiled) measures of performance. These regional structures constitute a refined feedback instrument for the adaptive plan. The system is an iterative one, and each iteration consists of three steps: the solving step, the region (cluster) handling step, and the regression step. After a (one-way) graph traverser attempts a training set of problem instances (solving step), the plan clusters states in the attribute space according to probabilitistic performance statistics, via a splitting algorithm (region handling step). From the clusters, parameters for a linear evaluation function are computed (regression step). In post-initial iterations, the system's graph traverser utilizes the evaluation function generated by the preceding iteration. The region handling step refines established clusters both by revising previous probability estimates and also by further splitting, in order to improve the function progressively.