perfect knowledge in AI

Dave R's latest post  to the cog ai list reminds us of the ultimate.
Perfect knowledge is a thing. Is there any such thing, really? How can it
be pursued?
Can we distinguish
perfect knowledge rom its perfect representation


Much there is to say about it. In other schools, we start by clearing the
obscurations in our own mind  . That is a lifetime pursuit.
While we get there, I take the opportunity to reflect on the perfect
knowledge literature in AI, a worthy topic to remember

I someone would like to access the article below, email me, I can share my
copy


ARTIFICIAL INTELLIGENCE 111
Perfect Knowledge Revisited*
S.T. Dekker, H.J. van den Herik and
l.S. Herschberg
Delft University of Technology, Department of Mathematics
and Informatics, 2628 BL Delft, Netherlands
ABSTRACT
Database research slowly arrives at the stage where perfect knowledge
allows us to grasp simple
endgames which, in most instances, show pathologies never thought o f by
Grandmasters' intuition.
For some endgames, the maximin exceeds FIDE's 50-move rule, thus
precipitating a discussion
about altering the rule. However, even though it is now possible to
determine exactly the path lengths
o f many 5-men endgames (or o f fewer men), it is felt there is an
essential flaw if each endgame
should have its own limit to the number o f moves. This paper focuses on
the consequences o f a
k-move rule which, whatever the value o f k, may change a naive optimal
strategy into a k-optimal
strategy which may well be radically different.
1. Introduction
Full knowledge of some endgames involving 3 or 4 men has first been made
available by Str6hlein [12]. However, his work did not immediately receive
the
recognition it deserved. This resulted in several reinventions of the
retrograde
enumeration technique around 1975, e.g., by Clarke, Thompson and by
Komissarchik and Futer. Berliner [2] reported in the same vein at an early
date
as did Newborn [11]. It is only recent advances in computers that allowed
comfortably tackling endgames of 5 men, though undaunted previous efforts
are on record (Komissarchik and Futer [8], Arlazarov and Futer [1]). Over
the
past four years, Ken Thompson has been a conspicuous labourer in this
particular field (Herschberg and van den Herik [6], Thompson [13]).
As of this writing, three 3-men endgames, five 4-men endgames, twelve
5-men endgames without pawns and three 5-men endgames with a pawn [4] can
be said to have been solved under the convention that White is the stronger
*The research reported in this contribution has been made possible by the
Netherlands
Organization for Advancement of Pure Research (ZWO), dossier number 39 SC
68-129, notably
by their donation of computer time on the Amsterdam Cyber 205. The
opinions expressed
are
those of the authors and do not necessarily represent those of the
Organization.
Artificial Intelligence 43 (1990) 111-123
0004-3702/90/$3.50 © 1990, Elsevier Science Publishers B.V. (North-Holland)
112 S.T. D E K K E R ET AL.
side and Black provides optimal resistance, which is to say that Black will
delay
as long as possible either mate or an inevitable conversion into another
lost
endgame. Conversion is taken in its larger sense. It may consist in
converting
to an endgame of different pieces, e.g., by promoting a pawn; equally, it
may
involve the loss of a piece and, finally and most subtly, it may involve a
pawn
move which turns an endgame into an essentially different endgame: a case in
point is the pawn move in the KQP(a6)KQ endgame converting it into
KQP(a7)KQ (for notation, see Appendix A).
The database, when constructed, defines an entry for every legal configura-
tion; from this, for each position, a sequence of moves known to be optimal
can be derived. The retrograde analysis is performed by a full-width
backward-
chaining procedure, starting from definitive positions (mate or
conversion), as
described in detail by van den Herik and Herschberg [18]; this yields a
database. The maximum length of all optimal paths is called the maximin (von
Neumann and Morgenstern [16]), i.e., the number of moves necessary and
sufficient to reach a definitive position from an arbitrary given position
with
White to move (WTM) and assuming optimal defence
CONCLUSION
It has now become clear that the notion of optimal play has been rather
naively
defined so far. At the very least, the notion of optimality requires a
specific
value of k for k-optimality and hence a careful bookkeeping of all relevant
anteriorities. These additional requirements form but one instance of
aiming to
achieve optimal play under constraints; of such constraints a k-move rule is
merely one instance. In essence, it is not our opinion that a k-move rule
spoils
the game of chess; on the contrary, like any other constraint, it may be
said to
enrich it, even though at present it appears to puzzle database
constructors,
chess theoreticians and Grandmasters alike.