Date: Tue 8 Nov 1988 17:10-EST From: AIList Moderator Nick Papadakis Reply-To: AIList@AI.AI.MIT.EDU Us-Mail: MIT LCS, 545 Tech Square, Rm# NE43-504, Cambridge MA 02139 Phone: (617) 253-6524 Subject: AIList Digest V8 #122 To: AIList@AI.AI.MIT.EDU Status: RO 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 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 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 ********************