Subject: brute-force vs. intuition in math & chess
Math-Fun: this is a draft of an unsent message on brute force vs. intuition
From: Bill Dubuque
Date: Aug 1996
The Beauty of Chess is Skin Deep
but the Beauty of Math is Infinitely Deep
Summary: some thoughts on intuition vs. brute-force in chess and math,
motivated by recent discussion of intelligence in chess in the newsgroup
comp.ai.philosophy (after the ACM Challenge: Deep Blue vs. Kasparov).
>From: Drew McDermott
>Newsgroups: comp.ai.philosophy
>Subject: Deep Blue and Intelligence
>Date: Mon, 19 Feb 1996 12:37:20 -0500
>
>The New York Times ran a post-mortem of the Deep-Blue-Kasparov chess
>match today, quoting various notables (Simon, Searle, Hofstadter,
>Gelernter, and others) on the question of whether the machine was
>"really" intelligent. Simon said it was, but the consensus among most
>of the others was that Deep Blue's relative success merely indicated
>that chess, contrary to expectation, requires no intelligence. ...
I conjecture that optimal chess play is essentially random and
of complexity far transcending human comprehension. I base this
conjecture on recent detailed analyses of endgame strategies made
possible via the construction of gigabytes of endgame databases.
These databases supply exact game-theoretic values (win/loss/draw)
and optimal move sequences for small-men endgames (e.g. Ken
Thompson distributes CD's for five-men endgames). Such perfect
information has motivated a reanalysis of the classical
human-derived endgame strategies with a surprising result that
optimal play often violates human heuristics and further may be
so complex in general that it is beyond the grasp of mere mortals.
Grandmasters have had severe difficulties playing against these
endgame databases. Optimal play is so complex that in one case
a recognized endgame expert (Roycroft) was able to comprehend a
certain endgame database only with enormous effort and the aid
of automated inductive-learning algorithms [Her] [Kop] [Mic].
See the Appendix below for an example of such complexity.
If the endgame holds such complexity then human comprehension of
optimal middlegame (and entire game) strategy is surely hopeless.
Such results seem to indicate that chess is random from a resource-
based Kolmogorov complexity point of view; i.e. probably it is not
possible to abstract from optimal play some structured general
strategy because deep tactics may produce exceptions to all human
comprehensible plans and strategies--a huge endgame database itself
may be the shortest possible description of the optimal strategy.
If this turns out to be true, then human strategies will only be
useful against humans--deeper searching programs will be able to
refute shallow human strategies. I think that we have already
begun to see some of this in the recent ACM match between
Kasparov and Deep Brute. In the long run it may prove impossible
for humans to comprehend the deep random variations that chess
programs compute as optimal. There may be no flowing themes, just
random forced tactical considerations that stem from deep
searches--perhaps the beauty of human chess lies only skin deep.
It is important to keep in mind that such brute-force game tree
searching fails miserably once one turns attention to games with
bushier trees (such as Go). Human ingenuity still reigns supreme
navigating bushlands in these combinatorially exploding jungles.
The same holds true of brute-force tree searching in many other
domains, e.g. theorem proving in mathematics. For example,
recently there has been a flurry of research applying effective
techniques in algebra towards proving elementary theorems in
geometry [Kap]. Thus we now know algorithms that automatically
decide the truth of theorems in elementary Euclidean geometry of
the sort one encounters in high-school, e.g. Appolonius' Circle
Theorem (cf. Appendix below). Such proofs proceed by brute force
calculation instead of geometric intuition, lemmas, analogies,
and all the other techniques that are the common arsenal of the
geometer. Do such algorithms herald the death of geometry? Of
course not, for such algorithms provide absolutely no insight
whatsoever into the structure of a proof--they churn and grind
and leave us with a solitary bit of truth just as the chess
endgame database leaves us with a win/lose/draw result but no hint
whatsoever of any plan or strategy. But the importance of a proof
or chess game lies much deeper than its result: it may herald the
discovery of a new idea with widespread application or it might
be a prototypical illustration of a general theme, etc--the
possible utilities are endless. The importance of Wiles proof of
Fermat's Last Theorem stems not from its truth value but rather
from the application of its methods to the Taniyama-Weil
conjecture and its consequent role in the Langlands program--a
major research theme in contemporary mathematics. On the other
hand, the brute-force proof of the four-color theorem contributes
merely a single bit of information to mathematical knowledge.
As another mathematical example I mention a theorem of Jacobson:
a ring is commutative if for every element x there is an integer
n > 1 such that x^n = x. Although this theorem may be proved
automatically for small n by existing brute-force equational
completion-based theorem provers, the general case is thought to
be far out of reach [KZ]. Jacobson's marvelous proof is an easy
corollary of his deep structure theory for rings, a structure
theory which is a prime example of the modern axiomatic method
and structuralistic trend in twentieth-century mathematics. Such
deep and beautiful triumphs of human ingenuity will never be the
result of pure brute-force, no matter how Deep the Brute. The
beauty of chess may lie only skin deep but the beauty of math
transcends even transfinite mechanical depths (as we know from
the deep work of Goedel, Turing, and Feferman [Fe1] [Fe2] [Fe3]).
Long live ingenuity!
-Bill Dubuque
Appendix
"With the relatively small queen-versus-rook ending it is not impossible
that a human could eventually understand, explain and perhaps even
master for his own use the bizarre intricacies of machine play. But
only a small step up the ladder of complexity, to queen and pawn (on
g7) versus queen, is sufficient to exceed such a possibility.
Komissarchik and Futer [1974] built an exhaustive database for this
ending. A computed minimax-optimal strategy takes the white king on a
labored and mysterious journey, circumnavigating the board more than
once, before the preconditions for safe pawn promotion are finally
established. Figure 15.3 from Komissarchik and Futer [KF] 1974 is
reproduced below. Roycroft comments on "... the white king's contorted
peregrinations throughout the solutions full length". Qualified
students of this result believe that human insight into the detailed
rationale is unlikely to be attainable [Roy] 1986."
--excerpted from [Mic], p. 247
Figure 15.3: A king's labored and mysterious journey.
+-----------------------------------------------------------------------+
| | | | | | | | |
| | ------- | | | | -----------+ |
| | / | \ | |\ | | | \ | | |
| | / | \ | | \| | | \ | | |
|--------/--------+--------\----|---+\-------+--------+--------\-----|--|
| / | | | \ | | \ | | | \ | |
| / | | | \| | | | | WP | / | |
| \ | | | | | | |\ | / | |
| \ | | | | \ | | \| / | | |
|--------\--------+--------+--------+-----\--+----|---+\---/---+-----|--|
| | \ | | -------------\------------\---+ | | |
| ---------\ | | WK | |\ | | +-- -|-|-----+ |
| \ | | | start | | \ \ | | | |/| |
| \ | | | | --------\ \ \| | |/| | |
|--------\--------+--------+--------+---|----+----\-\--\|---/|-+-|------|
| | \ | | | | | \ \ |\/ | | | |
| | | | | | | | \ +---+ |
| | | | | | \ | | \ | |
| | | | | | \ | | / | |
|--------+---|----+--------+--------+--------\--------+/-------+--------|
| | | | | | | \ /| | |
| | | | | | | \ / | | |
| | \ | | | | / \ | | |
| | \ | | | | | \| | |
|--------+-------\+--------+--------+--------+---|----+\-------+--------|
| | |\ WK end| | | | | \ | |
| | | \ \ | | | | | \ | |
| | | \ \ | | | | | \------ |
| | | \ \ | | | | | / |
|--------+--------+--------\-\------+--------+---|----+--------+/-------|
| | | | \ \ | | | | /| |
| | | | \ \-----\ | | | / | |
| | | | \ | \ | / | / | |
| | | | \| \ | / | / | |
|--------+--------+--------+--------+\-------/--------/--------+--------|
| | | | | \ / | \ / | | |
| | | | | / | \/ | | |
| | | | | | | | |
| | | | | | | | |
+-----------------------------------------------------------------------+
APPOLONIUS' CIRCLE THEOREM: The altitude pedal of the hypotenuse of
a right-angled triangle and the midpoints of the three sides of the
triangle lie on a circle; i.e. in the figure below, the pedal point
H lies on the circle determined by the midpoints EFG.
B (0,b) #
# #
# #
# # H (h,j)
# *
# * # # *
# * # #
# # # F (f,i)
G (0,g) * # *
# # #
* # # #
# # #
* # # * M (c,d) * #
# # #
* # # #
# # * #
* # #
########################*##########################
C (0,0) * E (e,0) A (a,0)
* *
*
(Hypotheses)
h1 := 2 e - a = 0 (E is midpoint of CA)
h2 := 2 f - a = 0 (F is midpoint of AB, 1st coordinate)
h3 := 2 i - b = 0 (F is midpoint of AB, 2nd coordinate)
h4 := 2 g - b = 0 (G is midpoint of BC)
h5 := (c - e)^2 + d^2 - (c - f)^2 - (d - i)^2 = 0 (length EM = length FM)
h6 := (c - e)^2 + d^2 - c^2 - (d - g)^2 = 0 (length EM = length GM)
h7 := (h - a) b + a j = 0 (H lies on AB)
h8 := - a h + b j = 0 (CH is perpendicular to AB)
(Conclusion)
Z := (c - e)^2 + d^2 - (c - h)^2 - (d - j)^2 = 0 (length EM = length HM)
Appolonius' Circle Theorem is equivalent to the proposition
P(a,b,c,d,e,f,g,h,i,j) :=
for all real numbers a,b,c,d,e,f,g,h,i,j:
if h1, h2, h3, h4, h5, h6, h7, and h8 = 0
then Z = 0
References
[CCC] Computers, Chess, and Cognition, T. Anthony Marsland and
Jonathan Schaeffer (ed.), Springer Verlag 1990.
[CL] Computational Logic: Essays in Honor of Alan Robinson,
J. Lassez and G. Plotkin (ed.), MIT Press, 1991.
[Fe1] Feferman, S. Transfinite recursive progressions
of axiomatic theories. Journal of Symbolic Logic, 27 (1962) 383-390.
[Fe2] Feferman, S. Turing in the land of O(z). In (R. Herken, ed.),
The Universal Turing Machine: A Half-century Survey, pp. 113-147.
Oxford University Press, 1988.
[Fe3] Feferman, S. Penrose's Goedelian Argument: A Review of _Shadows
of the Mind_ by Roger Penrose. PSYCHE: an interdisciplinary journal of
research on consciousness 2(7), May 1995. (Symposium on Roger Penrose's
_Shadows of the Mind_).
http://psyche.cs.monash.edu.au/volume2-1/psyche-95-2-07-shadows-5-feferman.html
ftp://ftp.cs.monash.edu.au/psyche/v2-1/psyche-95-2-07-shadows-5-feferman.txt
[Her] Herschberg, I.S. et. al., Verifying and Codifying
Strategies in a Chess Endgame, [CCC], 183-196.
[Kap] Geometric Reasoning, Deepak Kapur (ed.), MIT Press, 1988.
[KZ] Kapur, D. and Zhang, H., A Case Study of the Completion
Procedure: Proving Ring Commutativity Problems, [CL], 360-394.
[KF] Komissarchik, E.A. and A.L. Futer, Computer Analysis of a
Queen Endgame, Journal of the International Computer Chess
Assoc., vol. 9 (1986) no. 4, 189-198.
[Kop] Kopec, D., Advances in Man-Machine Play, [CCC], 9-32.
[Mic] Michie, D., Brute Force in Chess and Science, [CCC], 239-258.
[Roy] Roycroft, A.J., Queen and Pawn on b7 against Queen, in booklet
no. 7 of "Roycroft's 5-Man Chess Endgame Series", Chess Endgame
Consultants and Publishers, London, England.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Date: Wed, 21 Aug 1996 17:48:13 -0700
From: Marc Le Brun
Subject: Re: brute-force vs. intuition in math & chess
Bill, thanks again for yet another delightful and illuminating
exposition! (The King's Peregrination diagram alone is worthy
of framing). I embrace it 105%, but can't resist some kibbitzing:
I'd like to counsel some caution in casting these issues as
a dichotomy of "brute-force vs. intuition". First, because
arguments against "brute force" sometimes get confused into
arguments against *power* (eg the old AI folly of expecting human
equivalence from a PDP10, or whatever). More power *also* enables
more elegance and depth, and we can use all the leverage we can
get. Second, because the ill-defined word "intuition" can provoke
mysticism about whether there are "unautomatable" human activities.
The issue is really about the relative values of unstructured raw
complexity versus crafted parsimony in intellectual arsenals.
Also, without rehasing my earlier message, I want to again express
enthusiasm for a yet-to-emerge discipline of "theory engineering".
To take the chess example, we've still only scratched the surface.
Can we characterize further which end games *are* amenable to non-
enumerative analysis? Is it all but some easy set (like, say,
pawns-not-on-knight-7?) or some "small" list of explicit exceptions?
Certainly a chess program using such knowledge would be less
resource-intensive than one lugging around an entire 10^50 leaf move
tree (even if the exceptional set was, say, 10^6 specific cases, so
still far beyond human capacity)! Or, perhaps there are less-chaotic
but nonetheless effective, algorithms for handling such positions,
except that they aren't "optimal", taking a "few" moves longer to
force the win?
And if *any* kind of theory of the end game is possible, then perhaps
a mid game theory can be constructed with reference to it (as in human
praxis). Certainly it might be hairier than we'd like, yet more
tractable than a giant table lookup. In fact statements like "White
can always win" or "Chess is a draw" are candidate theories. Why not
"No win issues from 1. P-QR4" or "Knights on the rim are dim"? (Perhaps
hedged with a CD ROM of footnotes!). The presence of complexity is not
evidence for the absence of simplicity.
I think it's exciting that we are beginning to have the resources to
*start* to form theories of chess, or DNA encodings, or economics,
or whatever, in all their awesome complexity. But brute-force
enumeratuions only pin the specimens down, the real work of a
"descriptive anatomy" is still to be seriously undertaken,
let alone constructing a more general "comparative anatomy".
(And there's no reason to eschew the use of power tools in
these endeavors, either).
There are certainly things we can't know, but there's far more
that we simply don't yet know *how* to know.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
From: hbaker@netcom.com (Henry G. Baker)
Subject: Re: brute-force vs. intuition in math & chess
Date: Wed, 21 Aug 1996 19:01:50 -0700 (PDT)
> The Beauty of Chess is Skin Deep
> but the Beauty of Math is Infinitely Deep
[snip]
> Such results seem to indicate that chess is random from a resource-
> based Kolmogorov complexity point of view; i.e. probably it is not
> possible to abstract from optimal play some structured general
> strategy because deep tactics may produce exceptions to all human
> comprehensible plans and strategies--a huge endgame database itself
> may be the shortest possible description of the optimal strategy.
^^^^^^^^^^^^^^^^^
??? An exhaustive search _program_ is certainly considerably shorter
than a CDROM full of endgames. So the reference to Kolmogorov must
only be suggestive, rather than descriptive.
(A minor nit in an otherwise outstanding essay.)
--
Henry Baker
www/ftp directory:
ftp.netcom.com:/pub/hb/hbaker/home.html