Copy Link
Add to Bookmark
Report
AIList Digest Volume 8 Issue 122
AIList Digest Wednesday, 9 Nov 1988 Volume 8 : Issue 122
AI genealogy (Bibliographic Refs and Cultural Info)
Spang Robinson Report Summary
Chess:
AI program solves Connect Four
Desktop chess machines now rated above 2200
Deep Thought makes it
----------------------------------------------------------------------
Date: Thu, 20 Oct 88 14:15:34 PDT
From: rik%cs@ucsd.edu (Rik Belew)
Subject: AI genealogy
AI GENEALOGY
Building an AI family tree
Over the past several years we have been developing a collection of
bibliographic references to the literature of artificial intelligence
and cognitive science. We are also in the process of developing a
system, called BIBLIO, to make this information available to
researchers over Internet. My initial work was aimed at developing
INDEXING methods which would allow access to these citations by
appropriate keywords. More recently, we have explored the use of
inter-document CITATIONS, made by the author of one document to
previous articles, and TAXONOMIC CLASSIFICATIONS, developed by editors
and librarians to describe the entire literature.
We would now like to augment this database of bibliographic information
with "cultural" information, specifically a family tree of the
intellectual lineage of the authors. I propose to operationalize this
tree in terms of each author's THESIS ADVISOR and COMMITTEE MEMBERS,
and also the RESEARCH INSTITUTIONS where they work. It is our thesis
that this factual information, in conjuction with bibliographic
information about the AI literature, can be used to characterize
important intellectual developments within AI, and thereby provide
evidence about general processes of scientific discovery. A nice
practical consequence is that it will help to make information
retrievals from bibliographic databases, using BIBLIO, smarter.
I am sending a query out to several EMail lists to ask for your help
in this enterprise. If you have a Ph.D. and consider yourself a
researcher in AI, I would like you to send me information about where
you got your degree, who your advisor and committee members were, and
where you have worked since then. Also, please forward this query to
any of your colleagues that may not see this mailing list. The
specific questions are contained in a brief questionnaire below, and
this is followed by an example. I would appreciate it if you could
"snip" this (soft copy) questionnaire, fill it in and send back to me
intact because this will make my parsing job easier.
Also, if you know some of these facts about your advisor (committee
members), and their advisors, etc., I would appreciate it if you could
send me that information as well. One of my goals is to trace the
genealogy of today's researchers back as far as possible, to (for
example) participants in the Dartmouth conference of 1956, as well as
connections to other disciplines. If you do have any of this
information, simply duplicate the questionnaire and fill in a separate
copy for each person.
Let me anticipate some concerns you may have. First, I apologize for
the Ph.D. bias. It is most certainly not meant to suggest that only
Ph.D.'s are involved in AI research. Rather, it is a simplification
designed to make the notion of "lineage" more precise. Also, be
advised that this is very much a not-for-profit operation. The results
of this query will be combined (into an "AI family tree") and made
publically available as part of our BIBLIO system.
If you have any questions, or suggestions, please let me know. Thank
you for your help.
Richard K. Belew
Asst. Professor
Computer Science & Engr. Dept. (C-014)
Univ. Calif. - San Diego
La Jolla, CA 92093
619/534-2601
619/534-5948 (messages)
rik%cs@ucsd.edu
--------------------------------------------------------------
AI Genealogy questionnaire
Please complete and return to:
rik%cs@ucsd.edu
NAME:
Ph.D. year:
Ph.D. thesis title:
Department:
University:
Univ. location:
Thesis advisor:
Advisor's department:
Committee member:
Member's department:
Committee member:
Member's department:
Committee member:
Member's department:
Committee member:
Member's department:
Committee member:
Member's department:
Committee member:
Member's department:
Research institution:
Inst. location:
Dates:
Research institution:
Inst. location:
Dates:
Research institution:
Inst. location:
Dates:
--------------------------------------------------------------
AI Genealogy questionnaire
EXAMPLE
NAME: Richard K. Belew
Ph.D. year: 1986
Ph.D. thesis title: Adaptive information retrieval: machine learning
in associative networks
Department: Computer & Communication Sciences (CCS)
University: University of Michigan
Univ. location: Ann Arbor, Michigan
Thesis advisor: Stephen Kaplan
Advisor's department: Psychology
Thesis advisor: Paul D. Scott
Advisor's department: CCS
Committee member: Michael D. Gordon
Member's department: Mgmt. Info. Systems - Business School
Committee member: John H. Holland
Member's department: CCS
Committee member: Robert K. Lindsay
Member's department: Psychology
Research institution: Univ. California - San Diego
Computer Science & Engr. Dept.
Inst. location La Jolla, CA
Dates: 9/1/86 - present
------------------------------
Date: Mon, 7 Nov 88 14:28:18 CST
From: smu!leff@uunet.UU.NET (Laurence Leff)
Subject: Spang Robinson Report Summary
Summary of Spang Robinson Report on Artificial Intelligence,
September 1988, Volume 4, No. 9
Lead article is on AAAI-88 report.
AT AAAI-88
Apollo, Apple, Data General, DEC, Hewlett-Packard, IBM, Sun Microsystems,
Texas Instruments (only one third of thos emarketing AI technologies
or applications were there)
TI now has Explorer II Plus and Exploer III Plux LX
Explorer MP, 16-slot processor, new release of Personal Consultant +
Symbolics introduced MacIvory which combines Genera software and Mac II.
System costs $21900 for a system with one megabyte of memory and 300 megabyte
disk.
Integrated Inference is selling a Peripheral Processor Unit that
has a SM45000 Microprogrammable Inference Processor which
costs $9,950 to $39,950.
DEC will jointly market KEE from IntelliCorp and
Knowledge Craft from Carnegie Group. They also will be selling VAX
Decision Expert (based on GE's GEN-X) and NEXPERT OBJECT.
Intellicorp is promising KEE on the IBM mainframe by December.
it is now being beta tested and will sell for $98,000.
Sun has six per cent of its business in AI. They have 130 AI products
in their Catalyst third party program. ENVOS will be selling the following for
SUN workstations
Xerox's AI Development environment
LOOPS
ROOMS
Flexis, manufacturing cell design
Factories to model a complete factory line.
ENVOS is a Xerox spinoff which is partially owned by Xerox.
Data General will be joint marketing Gold Hill Computers GoldWorks on its
MV family.
Information Builders, known for FOCUS, has acquired Level 5 Research
and developed an interface between their respective products.
Neuron Data will work with Teknowledge to provide consulting and training.
Tree Age Software has produced a system that helps the constructionof
decison tables. It allows equations to be attached to the node and
in calculating the probable financial outcome of a course of decisions.
________________________________________
Common Lisp
Common LISP comiittee accepted a working group report on a Common Lisp
Object Ssytem. The informaiton is in Object-Oriented Programming
in Common Lisp.
Gold Hill is now selling a student version of Common Lisp for $49.95
and will be upgraded to include CLOS.
They are waiting for an upgrade of Portable Common Loops to
include CLOS compatability.
________________________________________
Neural Networks
Cognitive Software introduced a neural networking product for the Macintosh.
It uses the Levco transputer boards.
Brainmaker is a $99.95 product for Neural networks
________________________________________
Shorts:
TI will be adding to SPARC proprietary features of LISP machines
such as tags memory management and garbage collection.
Professor Larry Lidsky has developed a commercial product that schedules
maintenance and issues the requisite daily work orders in nuclear power
plants.
DEC will be cutting AI activities due to general business conditions.
Symbolics had June 30, 1988 year end revenues of $81,339,000
with a net loss of $46,036,000. "Symbolics is looking for further
funding and may fact the alternative of liquidation."
Palladian Software of Cambridge released version 2.0 of its Operations Planner
which assesses the impact of changes on a PC based system.
It now has assembly modeling capability and label tailoring.
IBM's network Management system supports an IBM Knowledge Tool interface
to allow network management to be put into the system.
Gensym introduced the G2 network which supports cooperating expert systems
for distributed applications operation in real time.
------------------------------
Date: 16 Oct 88 14:06:58 GMT
From: mcvax!hp4nl!botter!star.cs.vu.nl!victor%cs.vu.nl@uunet.uu.net
Subject: AI program solves Connect Four
An AI program has solved Connect Four for the standard 7 x 6 board.
The conclusion: White wins, was confirmed by the brute force check made by
James D. Allen, which has been published in rec.games.programmer at October 1st.
The program called VICTOR consists of a pure knowledge-based evaluation
function which can give three values to a position:
1 won by white,
0 still unclear.
-1 at least a draw for Black,
This evaluation function is based on 9 strategic rules concerning the game,
which all nine have been (mathematically) proven to be correct.
This means that a claim made about the game-theoretical value of a position
by VICTOR, is correct, although no search tree is built.
If the result 1 or -1 is given, the program outputs a set of rules applied,
indicating the way the result can be achieved.
This way one evaluation can be used to play the game to the end without any
extra calculation (unless the position was still unclear, of course).
Using the evaluation function alone, it has been shown that Black can at least
draw the game on any 6 x (2n) board. VICTOR found an easy strategy for
these boardsizes, which can be taught to anyone within 5 minutes. Nevertheless,
this strategy had not been encountered before by any humans, as far as I know.
For 7 x (2n) boards a similar strategy was found, in case White does not
start the game in the middle column. In these cases Black can therefore at
least draw the game.
Furthermore, VICTOR needed only to check a few dozen positions to show
that Black can at least draw the game on the 7 x 4 board.
Evaluation of a position on a 7 x 4 or 7 x 6 board costs between 0.01 and 10
CPU seconds on a Sun4.
For the 7 x 6 board too many positions were unclear. For that reason a
combination of Conspiracy-Number Search and Depth First Search was used
to determine the game-theoretical value. This took several hundreds of hours
on a Sun4.
The main reason for the large amount of search needed, was the fact that in
many variations, the win for White was very difficult to achieve.
This caused many positions to be unclear for the evaluation function.
Using the results of the search, a database will be constructed
of roughly 500.000 positions with their game-theoretical value.
Using this datebase, VICTOR can play against humans or other programs,
winning all the time (playing White). The average move takes less
than a second of calculation (search in the database or evaluation
of the position by the evaluation function).
Some variations are given below (columns and rows are numbered as is customary
in chess):
1. d1, .. The only winning move.
After 1. .., a1 wins 2. e1. Other second moves for White has not been
checked yet.
After 1. .., b1 wins 2. f1. Other second moves for White has not been
checked yet.
After 1. .., c1 wins 2. f1. Only 2 g1 has not been checked yet. All other
second moves for White give Black at least a draw.
After 1. .., d2 wins 2. d3. All other second moves for White give black
at least a draw.
A nice example of the difficulty White has to win:
1. d1, d2
2. d3, d4
3. d5, b1
4. b2!
The first three moves for White are forced, while alternatives at the
fourth moves of White are not checked yet.
A variation which took much time to check and eventually turned out
to be at least a draw for Black, was:
1. d1, c1
2. c2?, .. f1 wins, while c2 does not.
2. .., c3 Only move which gives Black the draw.
3. c4, .. White's best chance.
3. .., g1!! Only 3 .., d2 has not been checked completely, while all
other third moves for Black have been shown to lose.
The project has been described in my 'doctoraalscriptie' (Master thesis)
which has been supervised by Prof.Dr H.J. van den Herik of the
Rijksuniversiteit Limburg (The Netherlands).
I will give more details if requested.
Victor Allis.
Vrije Universiteit van Amsterdam.
The Netherlands.
victor@cs.vu.nl
------------------------------
Date: Tue, 1 Nov 88 08:58:15 PST
From: John B. Nagle <jbn@glacier.stanford.edu>
Subject: Desktop chess machines now rated above 2200
The current issue of Chess Life reports some new ratings of commercial
chess machines. There are now portable, desktop machines playing above 2200.
One of the National (US) Masters involved in the evaluation, after losing
2 out of 3 to a Fidelity unit, said that he was beginning to feel like
John Henry going up against the steam drill.
It's getting embarasssing in the chess world. It wasn't so bad
losing to a supercomputer that occupied a sizable building. But losing
to some little box seems to be getting to some of the chess masters.
Especially when you know that next year's box will be even better.
John Nagle
------------------------------
Date: Mon 7 Nov 88 08:20:39-PST
From: Stuart Cracraft <CRACRAFT@venera.isi.edu>
Subject: Deep Thought makes it
Article 1620 of rec.games.chess:
Relay-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site venera.isi.edu
From: tsa@vlsi.cs.cmu.edu (Thomas Anantharaman)
Newsgroups: rec.games.chess
Subject: Deep Thought in Hall of Fame Chess Festival
Message-ID: <3504@pt.cs.cmu.edu>
Date: 7 Nov 88 01:26:41 GMT
Date-Received: 7 Nov 88 08:08:23 GMT
Sender: netnews@pt.cs.cmu.edu
Organization: Carnegie-Mellon University, CS/RI
Lines: 35
Deep Thought tied for first with IM Igor Ivanov (2618), in the Hall of Fame
Chess Festival over the weekend. Deep Thought scored 4.5 out of 5. In the
first three rounds it beat Hugon (2007), Papenhausen (2143) and Marshall
(2170). In the fourth round DT defeated IM Calvin Blocker (2515). In the
final round DT drew against IM Igor Ivanov (2618). Deep Thought has now
defeated 4 IMs in its past 22 games.
DT's performance rating in this tournament was 2610. Our estimate of DT's
new established rating is about 2510. This is the first time a computer has
crossed over the 2500 threshold in established rating.
The games from the last two rounds are given below.
IM Calvin Blocker (2515) vs. Deep Thought (2495):
1. e4,Nf6; 2. e5,Nd5; 3. Nc3,N:c3; 4. b:c3,d5; 5. d4,c5;
6. h3,Nc6; 7. Nf3,e6; 8. Bd3,c:d4; 9. c:d4,Nb4; 10. Be2,Qc7;
11. o-o,N:c2; 12. Bb5,Bd7; 13. B:d7,K:d7; 14. Rb1,Rc8; 15. Rb3,b6;
16. Bb2,Bb4; 17. a3,Ba5; 18. Ng5,Rf8; 19. Qe2,h6; 20. Rc1,h:g5;
21. R:c2,Qb8; 22. Qb5,Ke7; 23. a4,Rc8; 24. Ba3,Kd8; 25. Bd6,Qb7;
26. Rb2,Bc3; 27. Rb1,B:d4; 28. Rbc1,R:c2; 29. R:c2,f6; 30. Qb4,Rh4;
31. Bc7,Ke8; 32. g4,f:e5; 33. Qd2,R:h3; 34. Q:g5,e4; 35. Qg6,Ke7;
36. Bf4,Rc3; 37. Rd2,Rc1; 38. Kh2,Bc3; 39. Re2,Qa6; 40. Bg5,Kd6;
41. Qf7,Q:e2; 42. Qe7,Kc6; 43. Qe6,Kc5; 44. Be7,Kc4; 45. Qc6,Kd4;
46. resigns. (Blocker was under time pressure near the end.)
IM Igor Ivanov (2618) vs. Deep Thought (2495):
1. c4,e5; 2. Nc3,Bb4; 3. g3,Nf6; 4. Bg2,Nc6; 5. d3,d5;
6. c:d5,N:d5; 7. Bd2,Be6; 8. Nf3,N:c3; 9. b:c3,Be7; 10. Rb1,Rb8;
11. Qa4,o-o; 12. o-o,a6; 13. Be3,Qd7; 14. Rfd1,Qd5; 15. Rd2,b5;
16. Qd1,Qd8; 17. d4,e:d4; 18. B:d4,Qe8; 19. Be5,Bf5; 20. Rb3,Na5;
21. B:c7,N:b3; 22. a:b3,Rc8; 23. Ba5,Bc5; 24. Nd4,Be4; 25. Bh3,f5;
26. e3,g6; 27. Bf1,Qe5; 28. Nc2,Rf7; 29. c4,Bb7; 30. c:b5,Qe4;
31. f3,B:e3; 32. N:e3,Q:e3; 33. Kg2,a:b5; 34. B:b5,Rc1; 35. Rd8,Kg7;
36. Qd4,Q:d4; 37. R:d4,Rc2; 38. Bd2,Bc8; 39. Kf2,Be6; 40. b4,Ra7;
41. h4,Ra2; 42. ke3,h5; 43. Be2,Kf7; 44. Bd1,Rb2; 45. Be2, draw agreed.
------------------------------
End of AIList Digest
********************
