exhaustive search.htm

这是博弈论算法全集第四部分:剪枝算法,其它算法将陆续推出.以便与大家共享

theorems whose proof requires a massive amount of computation <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Lehmer53">[Lehmer 53 
64]</A>. We make no attempt to survey the many results obtained thanks to 
computer-based mathematics, but merely recall a few as entry points into the 
pertinent literature: 
<UL>
  <LI>the continuing race for large primes, for example Mersenne primes of form 
  2^p-1 
  <LI>the landmark proof of the ``Four-Color Theorem'' by Appell and Haken <A 
  href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Appell77">[Appell 
  77]</A> 
  <LI>recent work in Ramsey theory or cellular-automata <A 
  href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Horgan93">[Horgan 
  93]</A>. </LI></UL>
<P>The applications of exhaustive search to which we refer in more detail is the 
esoteric field of games and puzzles. Because their rules and objectives are 
simple and rigorously defined, and progress can be quantified, games and puzzles 
have long been embraced by game theory <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#vonNeumann43">[von 
Neumann 43]</A>, <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Berlekamp82">[Berlekamp 
82]</A> and artificial intelligence (AI) communities as ideal testing 
environments. Chess was long regarded as the ``drosophila of artificial 
intelligence'', and if four decades of experimentation with chess-playing 
machines has taught us anything at all, it must be the amazing power of massive 
search to amplify the effect of a meager amount of game-specific positional 
knowledge. It has become evident that brute-force search suffices to play chess 
at a level of skill exceeded by at most a few hundred humans. 
<P>We are not concerned with heuristic game-playing in this paper, we are 
interested in ``solving'' games and puzzles by exhaustive search of their state 
spaces. Games successfully solved include Qubic <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Patashnik80">[Patashnik 
80]</A>, Connect-4 <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Allen89">[Allen 
89]</A>, Go-Moku <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Allis94">[Allis 
94]</A>, and Merrils or Nine Men's Morris <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Gasser94">[Gasser 
94]</A>, <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Gasser95">[Gasser 
95]</A>. <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Allis94">[Allis 
94]</A> surveys the state of the art and lists all games known to have been 
solved. Exhaustive search has also been applied to puzzles, which can be 
considered to be one-player games. For the Rubik's cube there is an algorithm by 
Thistlethwaite which provably solves any position in at most 52 moves, while a 
recently introduced algorithm seemingly solves any position in at most 21 moves 
<A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Kociemba92">[Kociemba 
92]</A>. 
<P>Sam Loyd's 15-puzzle (15 tiles sliding inside a 4 by 4 matrix) has so far 
resisted complete solution, although interesting mathematical results have been 
obtained. <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Wilson74">[Wilson 
74]</A> shows that the state space decomposes into two independent subspaces. 
When generalized to an <EM>n x n</EM> puzzle, finding optimal solution is 
NP-complete <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Ratner90">[Ratner 
90]</A>, whereas non-optimal strategies are polynomial <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Sucrow92">[Sucrow 
92]</A>. But as is often the case, such mathematical results for general 
<EM>n</EM> give little or no hint on how to approach a specific instance, say 
<EM>n = 4</EM>. Experience shows that improved lower bounds are the single most 
effective step towards efficient search, since they prune larger subspaces. 
Instead of the standard Manhattan distance bound, more informed bounds have been 
developed, e.g.: linear-conflict <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Hansson92">[Hansson 
92]</A>, or fringe and corner databases <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Culberson94">[Culberson 
94]</A>. With further improved bounds, <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Gasser95">[Gasser 
95]</A> discovered positions requiring 80 moves to solve and proved that no 
position requires more than 87 moves to solve. This gap between upper and lower 
bound remains a challenge. 
<P>Returning to two-person games, there have been long-standing efforts to solve 
parts of games, typically endgames, where there is little hope of solving the 
entire game, now or perhaps ever. The motivation for this may come from attempts 
to improve the strength of heuristics game-playing programs. During their 
forward search, these use heuristic evaluation functions to assess the value of 
a position, and such functions are necessarily approximations of unknown 
quality. If exact values are available not only at the leaves, but already 
further up in the game tree thanks to a precomputed minimax evaluation, this has 
two desirable consequences. First, exact values have a beneficial effect on the 
quality of the ``minimax-mix'' of heuristic values. Second, longer endgames can 
be played perfectly, i.e. such as to guarantee an outcome of at least the 
game-theoretic value. We are aware of two endgame databases that were computed 
with this goal as primary motivation: 
<UL>
  <LI><EM>Checkers:</EM> An <EM>8 x 8</EM> checkers project is headed by 
  Jonathan Schaeffer <A 
  href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Schaeffer92">[Schaeffer 
  92]</A>. His group has computed all 7-piece positions and is working on 8 and 
  9 piece positions. Their databases contain about 1.5 * 10^11 positions. A 
  workstation cluster (25-90 machines) and a BBN TC2000 allow an average of 425 
  million positions to be computed per day <A 
  href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Lake94">[Lake 
  94]</A>. 
  <LI><EM>Awari:</EM> Victor Allis first computed Awari endgame databases for 
  use in his playing program Lithidion <A 
  href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Allis94">[Allis 
  94]</A>. We have extended this work and now have all 5.5 * 10^8 positions with 
  22 or fewer stones at our disposal (T. Lincke). </LI></UL>
<P>Last but not least, the problem domain that spearheaded the drive to explore 
the limits of exhaustive search, and that gives us the clearest measure of 
progress, is chess endgames. <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Stroehlein70">[Stroehlein 
70]</A> started the race. For a summary of early results see <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Herik86">[Herik 
86]</A>. Ken Thompson computed many four and five piece chess databases, which 
have been released on two compact disks <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Thompson91">[Thompson 
91]</A>,<A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Thompson92"> [Thompson 
92]</A>. Lewis Stiller used a Connection Machine CM-2 to compute six-piece chess 
databases, each of which consists of up to 6'185'385'360 positions <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Stiller91">[Stiller 
91]</A>. Grandmaster John Nunn's books tellingly entitled ``Secrets of Rook 
Endings'', ``Secrets of Pawnless Endings'', and ``Secrets of Minor Piece 
Endings'' <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Nunn92-95">[Nunn 
92-95]</A> is the first attempt to interpret such databases for human 
consumption. 
<P>Although a direct comparison of different enumeration problems is not easy, 
due to their state spaces of different structure and varying connectivity, it is 
striking that at present, the size of state spaces of various solved problems, 
including Merrils, is of the order of 10^10 positions. The empirical fact that 
the raw size of the state space is the dominant parameter that affects 
complexity might be explained by the observation that the structure of all these 
spaces shows no regularity - they appear to be random graphs. Without 
predictable regularity to exploit, all exhaustive searches look like random 
walks in a random graph. Thus, the most telling indicator of complexity is the 
size of the space, and its connectivity is second. <BR><BR><BR><A name=3></A>
<H3>3. The Role of Exhaustive Search: Speculation</H3>
<P>After this brief presentation of a small niche of computer science and the 
work of a few researchers who have been driven by curiosity more than by any 
other motivation, let us ask some basic questions: What can we learn from dozens 
of case studies of exhaustive search reported since computers became available a 
few decades ago? Why keep computers busy for days or months exhaustively 
traversing the state space of some puzzle whose solution is merely a matter of 
curiosity? What contribution, if any, can we expected from further experiments 
based on exhaustive search? 
<P>These questions are hard to answer. Brute-force solutions are not ``elegant'' 
from a mathematical point of view. Their cryptical assertions such as ``the game 
of Merrils is a draw'', reached after producing Gigabytes of data, cannot be 
checked without computer. Neither algorithms nor results can be presented in a 
``user-friendly'' manner. Attempts to extract rules from a data base of 
positions, in order to distinguish won, lost, and drawn positions, have not been 
very successful. If done automatically, e.g. by finding predicates and producing 
a decision tree, one obtains huge trees and predicates for which humans lack 
intuition <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Gasser95">[Gasser 
95]</A>. The answer that no simpler description exists fails to satisfy players. 
They prefer a simple, intuitive rule that allows exceptions to an unmotivated, 
impractical rule that claims perfection. Extracting rules from a database in 
such a way that players can understand it requires a huge effort by a top 
expert, as shown by Grandmaster Nunn's books <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Nunn92-95">[Nunn 
92-95]</A>. 
<P>So why waste computer time to ``solve'' games in a way that has little or no 
interest to game players? One answer is undoubtedly the same as for the question 
``why climb Mount Everest?'': to prove that it can be done. But we are intrigued 
by a second answer: exhaustive search in large state spaces is a very general 
approach to combinatorial problems of any kind, and promises to be increasingly 
important. Why? For decades, computer scientists have focused attention on 
problems that admit efficient algorithms. Algorithms whose running time grows no 
faster than some polynomial of low degree in the size of the input data still 
dominate textbooks on algorithms. In contrast, problems that appear not to admit 
polynomial time algorithms, specifically, NP-complete or NP-hard problems, are 
often considered mere objects for a theorem, but dismissed as ``intractable'' 
from an algorithmic point of view. 
<P>But efficient algorithms can only be found for selected, relatively simple 
problems, whereas the world of applications is not simple. Most problems of 
practical importance, if they can be approached by computation at all, call for 
compute-intensive methods. Accordingly, the attitude towards ``intractable'' 
problems began to change. First, researchers relaxed the goal of exact or 
optimal solutions and sought efficient approximation algorithms. Second, one 
noticed that not all ``intractable problems'' are equally intractable. There 
appear to be many problems where the average, or typical, instance is relatively 
easy to solve, and only the worst-case instances are computationally very 
demanding. The venerable traveling salesman problem (TSP) may be an example. In 
tsplib <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Reinelt95">[Reinelt 
95]</A>, a collection of TSP benchmark problems that serves as a yardstick of 
progress, the currently largest provably optimal solution involves 7397 cities. 
This progress could hardly have been expected a decade ago, when the largest 
instance of a TSP known to have been solved had 318 cities <A 
href="http://nobi.ethz.ch/febi/ex_search_paper/paper.html#Lawler85">[Lawler 
85]</A>. 
<P>In view of the fact that exhaustive search occasionally does succeed in 
solving surprisingly large instances of NP-complete problems, it is time to 
reconsider identifying ``NP-complete'' with ``intractable''. But whereas 
computer scientists feel they know everything worth knowing about sorting and