| تبليغات | X |
با سلام خدمت همه شما عزیزان. در پست قبلی فقط جواب مسئله مشهور 8 وزیرو براتون گذاشتم. اما امروز می خوام روش حل مسئله مشهور 8 وزیرو و بطور کلی n وزیرو براتون شرح بدم.
این مسئله بدین صورته که شما باید 8 وزیرو طوری تو صفحه شطرنج قرار بدین تا هیچکدوم نتونه یکی دیگه رو برداره.جالبه بدونین که این مسئله تقریبا قدمتی به اندازه ابداع خود شطرنجهبرای همین معلوم نیست اولین با چه کسی اونو مطرح کرده.ولی ظاهراً آقای Karl Friedrich Gauss ( ریاضی دان آلمانی ) اونو برای اولین بار حل کرد.پیدا کردن تنها یک راه حل آنگونه که در ادامه می بینیم کار سختی نیست اما اگر بخواهیم همه راه حل ها رو بدست بیاریم دیگه کار خیلی سخت می شه.روش بازگشتی ( Backtracking ) ه در طراحی سیستم های خبره کاربرد زیادی داره تنها راه حل شناخته شده برای این مسئله مشهوره. برای 8 وزیر ما 12 راه حل یکتا و با روش متقارن سازی ما 92 روش داریم.
حال شما مسئله رو در حالت کلی n وزیر در نشر بگیرین.اگر n عددی اول باشه یک راه به راحتی با رسم یک خط راست در یک صفحه n*n محدود به وجود می یاد. تا زمانیکه هیچ دو خط راستی همدیگرو در بیشتر از یک نقطه قطع نمی کنن، خط مستقیم y= a*x+b که برابر 1 یا 1- نیست می تونه یک راه حل باشه.طول عرض مختصات از 0 شروع می شه:
N=7 ; y=2x --à (0,0) , (1,2) , (2,4) , (3,6) , (4,1) , (5,3) , (6,5);
حتما می دونین که 8 = 2 * 4 ، بله به سواد خودتون شک نکنین چون صفحه ما بیشتر از 7 خونه نداره مجبور شدیم از اون 7 تا کم کنیم . (-:
با a= 2,3,4,5 و b=0,1,2,3,4,5,6 به راحتی می شه 28 راه حل پیدا کرد.
برای اعدادی که اول نیست یا به عبارتی مختلط هستن که می تونیم اونا رو به صورت n=p * q تعریف کنیم ، ما می تونیم با یک ضرب مستقیم از راه حل های p وزیر و q وزیر تموم راه حل ها رو بدست بیاریم.بدین صورت که هر وضعیت مکانی باری مسئه p وزیر یک راه حل هم برای مسئله q وزیر به حساب می یاد.مثلاً برای 5*7=35 ما می تونیم 10*40 ̂ 7 + 40 * 10 ̂ 5 راه حی داشته باشیم. خیلی بزرگه نه؟
برای ایجاد یک راه حل در حالت کلی n بذارین در نظر بگیریم که یک سطح تقسیم شده به صورت j = 0,1,…,n-1 و i=0,1,…,n-1 داشته باشیم.
حال فرض کنید n یک عدد زوج باشه.داریم:
1) if n is not 6k+2
j=2i+1, for 0 <=i< n/2
j=2i mod n, for n/2 <= i < n
2) if n is not 6k
j= (n/2 + 2i-1) mod n, for 0 <= i < n/2
j=(n/2 + 2i+2) mod n ,for n/2 <= i < n
امیدوارم که مطلب تقریباً براتون روشن شده باشه.
راستی جالبه یه مطلب راجع به سوپر وزیر (SuperQueen ) به شما بگم. در نظر بگیرین علاوه بر حالت فوق وزیر ها نتونن از طریق حرکت اسب یا همون L معروف همدیگرو بزنن! به نظر شما این راه حل وجود داره؟ جالبه بدونین که این راه از صفحه 10 * 10 شروع می شه و در این صفحه تنها 1 مورد راه حل وجود داره!
پایین شما یک جدول از ره های ممکنه برای این مسئله می بینین. نظرتون چیه ؟؟؟!!!!!!!!!
Order < -----
Ordinary Queens -----
> < ---- Superqueens ---- >
Exec
(“N”) Total Solutions Unique
Solutions Total Sol.
Unique Sol. Time
------------------------------------------------------------------------------------------
1
1
1
1 1
2
0
0
0 0
3
0
0
0 0
4
2
1
0 0
5
10
2
0 0
6
4
1
0 0
7
40
6
0 0
8
92
12
0 0
9
352
46
0
0
10
724
92
4 1
11
2,680
341
44 6
12
14,200
1,787
156 22
13
73,712
9,233
1,876 239
14
365,596
45,752
5,180
653 0.2 sec.
15
2,279,184
285,053
32,516 4,089 1.9
sec.
16
14,772,512
1,846,955
202,900 25,411 11.2 sec.
17
95,815,104
11,977,939
1,330,622 166,463 77.2 sec.
18
666,090,624
83,263,591 8,924,976
1,115,871 9.6 min.
19
4,968,057,848
621,012,754 64,492,432
8,062,150 75.0 min.
20
39,029,188,884
4,878,666,808 495,864,256
61,984,976 10.2 hrs.
21
314,666,222,712
39,333,324,973 3,977,841,852
497,236,090 87.2 hrs.
22
2,691,008,701,644 336,376,244,042
34,092,182,276 4,261,538,564 31.9 days
23 24,233,937,684,440
3,029,242,658,210 306,819,842,212 38,352,532,487 296
days
کفتم شاید به نظرتون جالب بیاد . برا همین مسئله 8 وزیر خیلی معروف که اکثر استادای نوگرا (: این برنامه خیلی قدیمی رو به دانشجوها برا حل کردن میدن رو با توضیح کانل در وبلاگ می ذارم. امیدوارم کمکتون کنه.
ابتدا به زبان Lisp :
;;;The following common lisp program is based on a solution given by% eightqueen.pro
;;;Winston and Horn ("Lisp 3rd edition",1989, p.289, 538-539.)
;;;Significant improvements and alterations were made in all but the most
;;;primitive functions. To run, simply load file and type (queen n) where
;;;n is the width of board.
;discovers if a piece threatens another
(defun threat (i j a b)
(or (= i a)
(= j b)
(= (- i j) (- a b))
(= (+ i j) (+ a b))))
;discovers if a placement is OK
(defun conflict (n m board)
(cond ((endp board) nil)
((threat n
m
(first (first board))
(second (first board)))
t)
(t (conflict n m (rest board)))))
;;this now prints a board no matter what order it is presented in
(defun print-board (board)
; (sort board #'<= :key #'car)
(format t "~%*")
(print-horizontal-border board)
(format t "*")
(dotimes (row (length board))
(format t "~%|")
(dotimes (column (length board))
(if (= column (second (assoc row board)))
(format t " Q")
(format t " .")))
(format t " |"))
(format t "~%*")
(print-horizontal-border board)
(format t "*"))
(defun print-horizontal-border (board)
(dotimes (n (+ 1 (* 2 (length board))))
(format t "-")))
;;;The following is Winston/Horn's original queen-finding algorithm.
;;;It does not discriminate sets of solutions that are closed under rotation
;;;and reflection. Thus, a single solution can be equivalent to up to 8 other
;;;solutions.
(defun queen* (size &optional (board nil) (n 0) (m 0))
(unless (= m size)
;;Check for conflict in current row and column
(unless (conflict n m board)
(if (= (+ 1 n) size)
;;If all queens placed, prin solution:
(print-board (reverse (cons (list n m) board)))
;;Otherwise, proceed to next row:
(queen* size (cons (list n m) board) (+ 1 n) 0)))
;;In any case, try with another column
(queen* size board n (+ 1 m))))
;;; This version improves on Winston/Horn in that it displays only one instance
;;;of a closed set of solutions. Thus, 8-queens solution is reduced from 96 to 12.
;;;It achieves this by using a bindings list of already-found solutions. Since a change
;;;made at a deeper level of recursive search must be accessible to a higher level,
;;;the bindings list was made a global parameter that is re-initialized when queen is called.
;;; This required an auxilliary function, thus labels.
;;;NO-REPEATS predicate returns t if no member of the set of solutions, closed under reflection
;;;and rotation, is on the bindings list.
;;;Finally, the local variable new-board was assigned to save re-calculating that data.
(defun queen (size)
;;initialize bindings variable
(defparameter *bindings* nil)
;;declare auxilliary function
(labels ((n-queen (size &optional (board nil) (n 0) (m 0))
(unless (= m size)
(let ((new-board (cons (list n m) board)))
(unless (conflict n m board)
(if (= (+ 1 n) size)
;;check to see if solution is repeated
(if (no-repeats new-board (- size 1))
(progn ;only print solution if not already printed
(print-board new-board)
(setf *bindings* (append (list (sort-board new-board))
*bindings*)))) ;change bindings
(n-queen size (cons (list n m) board) (+ 1 n) 0))))
(n-queen size board n (+ 1 m)))))
;;call auxilliary function:
(n-queen size nil 0 0)))
(defun no-repeats (board size)
"looks to see if a permutation of current board has already been found--assumes a properly sorted bindings list"
;(format t "~&Bindings are: ~a" *bindings*)
;(format t "~&Equiv. Class is: ~a" (make-set board size))
(if (equal *bindings* nil) ;check to see if bindings in nil---find has a problem with this
t
(labels ((find-double (-eq-class-)
(if (equal nil -eq-class-)
t
(and (not (find (first -eq-class-) *bindings* :test #'equal)) ;find solution in bindings
(find-double (rest -eq-class-))))))
(find-double (make-set board size)))))
(defun reflect-horizontal (board size &optional (new-board nil))
"reflects across horizontal axis"
(if (equal board nil)
new-board
(reflect-horizontal (rest board) size (cons (list (- size (first (first board)))
(second (first board)))
new-board))))
(defun rotate-90 (board size &optional (new-board nil))
"reflects across diagonal axis"
(if (equal board nil)
(sort-board new-board)
(rotate-90 (rest board) size (cons (list (second (first board))
(- size (first (first board))))
new-board))))
(defun make-set (board size)
(let*((board1 (sort-board board))
(board2 (rotate-90 board1 size))
(board3 (rotate-90 board2 size))
(board4 (rotate-90 board3 size))
(board5 (reflect-horizontal board1 size))
(board6 (rotate-90 board5 size))
(board7 (rotate-90 board6 size))
(board8 (rotate-90 board7 size)))
(list board1
board2
board3
board4
board5
board6
board7
board8)))
(defun sort-board (board &optional (counter 0))
"sorts a board configuration into ascending order by rows"
(if (= counter (length board))
nil
(cons (assoc counter board)
(sort-board board (+ counter 1)))))
Now we see this solution in Prolog:
%
nocheck(_,[]).
nocheck(X/Y, [X1/Y1 | Rest]) :- X=\=X1,Y=\=Y1,
abs(Y1-Y) =\= abs(X1-X),
nocheck(X/Y,Rest).
legal([]).
legal([X/Y | Rest]) :-
legal( Rest),
% member(X,[1,2,3,4,5,6,7,8]),
member(X,[1,2,3,4,5,6,7,8]),
nocheck(X/Y,Rest).
if(Test,Then) :- Test,!,Then.
if(_,_,Else) :- Else.
manual(X) :- write('ls: list the solutions
cn: output the number of solutions
mp; display mapping on the board for solutions
\n
Enter Command:'),
read(X),
write('You enter:'), write(X), nl.
eightqueens :- manual(CMD),
eightqueens_body(CMD).
eightqueens_body(CMD) :-
CMD == 'mp',findall( X, eightqueens_map(X), L),
len(L,N),write('There are '),write(N),write(' solutions.').
eightqueens_body(CMD) :-
CMD == 'ls',findall( X, eightqueens_list(X), L),
showlist3(L,1), len(L,N),write('There are '),write(N),write(' solutions.').
eightqueens_body(CMD) :-
CMD == 'cn',findall( X, eightqueens_cnt(X), L),
len(L,N),write('There are '),write(N),write(' solutions.').
eightqueens_map(X) :-
X = [_/1,_/2,_/3,_/4,_/5,_/6,_/7,_/8],
legal(X),
showlist(X),
write('['),tab(1),
showlist2(X).
eightqueens_list(X) :-
X = [_/1,_/2,_/3,_/4,_/5,_/6,_/7,_/8],
legal(X).
%legal(X),
%write('['),
%showlist3(X).
eightqueens_cnt(X) :-
X = [_/1,_/2,_/3,_/4,_/5,_/6,_/7,_/8],
legal(X).
showlist([]) :- nl.
showlist([X|Y]) :- X = C/_, showboard(C,8), showlist(Y).
showlist2([]) :- write(']\n\n\n').
showlist2([X|Y]) :- write(X), tab(1), showlist2(Y).
showlist3([],0) :- nl.
showlist3([X|Y],N) :- N1 is N + 1, write(N), tab(1), write('['), showlist2(X), showlist3(Y,N1).
showboard(X,N) :- X = 0, write('Q|'), N1 is N -1, showboard2(N1).
showboard(X,N) :- X > 0, write(' |'), X1 is X - 1, N1 is N -1, showboard(X1,N1).
showboard2(N) :- N < 0, write('\n').
showboard2(N) :- N = 0, write(' |'),N1 is N -1, showboard2(N1).
showboard2(N) :- N > 0, write(' |'),N1 is N - 1, showboard2(N1).
len([],0) :- nl.
len([_|T], N) :- len(T, N1), N is 1 + N1.
The intellectual roots of AI, and the concept of intelligent machines, may be found in Greek mythology. Intelligent artifacts appear in literature since then, with real (and fraudulent) mechanical devices actually demonstrated to behave with some degree of intelligence. Some of these conceptual achievements are listed below under "Ancient History."
After modern computers became available, following World War II, it has become possible to create programs that perform difficult intellectual tasks. From these programs, general tools are constructed which have applications in a wide variety of everday problems. Some of these computational milestones are listed below under "Modern History."
Ancient History |
Greek myths of Hephaestus and Pygmalion incorporate the idea of intelligent robots. Many other myths in antiquity involve human-like artifacts. Many mechanical toys and models were actually constructed, e.g., by Hero, Daedalus and other real persons.
Aristotle invented syllogistic logic, the first formal deductive reasoning system.
Talking heads were said to have been created, Roger Bacon and Albert the Great reputedly among the owners.
Ramon Llull, Spanish theologian, invented machines for discovering nonmathematical truths through combinatorics.
Invention of printing using moveable type. Gutenberg Bible printed (1456).
Clocks, the first modern measuring machines, were first produced using lathes.
Clockmakers extended their craft to creating mechanical animals and other novelties.
Rabbi Loew of Prague is said to have invented the Golem, a clay man brought to life (1580).
Early in the century, Descartes proposed that bodies of animals are nothing more than complex machines. Many other 17th century thinkers offered variations and elaborations of Cartesian mechanism.
Hobbes published The Leviathan, containing a material and combinatorial theory of thinking.
Pascal created the first mechanical digital calculating machine (1642).
Leibniz improved Pascal's machine to do multiplication & division (1673) and envisioned a universal calculus of reasoning by which arguments could be decided mechanically.
The 18th century saw a profusion of mechanical toys, including the celebrated mechanical duck of Vaucanson and von Kempelen's phony mechanical chess player, The Turk (1769).
Luddites (led by Ned Ludd) destroyed machinery in England (1811-1816).
Mary Shelley published the story of Frankenstein's monster (1818).
George Boole developed a binary algebra representing (some) "laws of thought."
Charles Babbage & Ada Byron (Lady Lovelace) worked on programmable mechanical calculating machines.
Bertrand Russell and Alfred North Whitehead published Principia Mathematica, which revolutionaized formal logic. Russell, Ludwig Wittgenstein, and Rudolf Carnap lead philosophy into logical analysis of knowledge.
Karel Capek's play "R.U.R." (Rossum's Universal Robots) produced in 1921 (London opening, 1923). - First use of the word 'robot' in English.
Warren McCulloch & Walter Pitts publish "A Logical Calculus of the Ideas Immanent in Nervous Activity" (1943), laying foundations for neural networks.
Arturo Rosenblueth, Norbert Wiener & Julian Bigelow coin the term "cybernetics" in a 1943 paper. Wiener's popular book by that name published in 1948.
Emil Post proves that production systems are a general computational mechanism (1943). See Ch.2 of Rule Based Expert Systems for the uses of production systems in AI.
Vannevar Bush published As We May Think (Atlantic Monthly, July 1945) a prescient vision of the future in which computers assist humans in many activities.
A.M. Turing published "Computing Machinery and Intelligence" (1950). - Introduction of Turing Test as a way of operationalizing a test of intelligent behavior.
Claude Shannon published detailed analysis of chess playing as search in "Programming a computer to play chess" (1950).
Isaac Asimov published his three laws of robotics (1950).
Modern History |
| 1956 | John McCarthy coined the term "artificial intelligence" as the topic of the Dartmouth Conference, the first conference devoted to the subject. |
|
| Demonstration of the first running AI program, the Logic Theorist (LT) written by Allen Newell, J.C. Shaw and Herbert Simon (Carnegie Institute of Technology, now Carnegie Mellon University). |
| 1957 | The General Problem Solver (GPS) demonstrated by Newell, Shaw & Simon. |
| 1952-62 | Arthur Samuel (IBM) wrote the first game-playing program, for checkers, to achieve sufficient skill to challenge a world champion. Samuel's machine learning programs were responsible for the high performance of the checkers player. |
| 1958 | John McCarthy (MIT) invented the Lisp language. |
|
| Herb Gelernter & Nathan Rochester (IBM) described a theorem prover in geometry that exploits a semantic model of the domain in the form of diagrams of "typical" cases. |
|
| Teddington Conference on the Mechanization of Thought Processes was held in the UK and among the papers presented were John McCarthy's Programs with Common Sense, " Oliver Selfridge's "Pandemonium," and Marvin Minsky's "Some Methods of Heuristic Programming and Artificial Intelligence." |
| Late 50's & Early 60's | Margaret Masterman & colleagues at Cambridge design semantic nets for machine translation. |
| 1961 | James Slagle (PhD dissertation, MIT) wrote (in Lisp) the first symbolic integration program, SAINT, which solved calculus problems at the college freshman level. |
| 1962 | First industrial robot company, Unimation, founded. |
| 1963 | Thomas Evans' program, ANALOGY, written as part of his PhD work at MIT, demonstrated that computers can solve the same analogy problems as are given on IQ tests. |
|
| Ivan Sutherland's MIT dissertation on Sketchpad introduced the idea of interactive graphics into computing. |
|
| Edward A. Feigenbaum & Julian Feldman published Computers and Thought, the first collection of articles about artificial intelligence. |
| 1964 | Danny Bobrow's dissertation at MIT (tech.report #1 from MIT's AI group, Project MAC), shows that computers can understand natural language well enough to solve algebra word problems correctly. |
|
| Bert Raphael's MIT dissertation on the SIR program demonstrates the power of a logical representation of knowledge for question-answering systems |
| 1965 | J. Alan Robinson invented a mechanical proof procedure, the Resolution Method, which allowed programs to work efficiently with formal logic as a representation language. (See Carl Hewitt's history of logic programming). |
|
| Joseph Weizenbaum (MIT) built ELIZA, an interactive program that carries on a dialogue in English on any topic. It was a popular toy at AI centers on the ARPA-net when a version that "simulated" the dialogue of a psychotherapist was programmed. |
| 1966 | Ross Quillian (PhD dissertation, Carnegie Inst. of Technology; now CMU) demonstrated semantic nets. |
|
| First Machine Intelligence workshop at Edinburgh - the first of an influential annual series organized by Donald Michie and others. |
|
| Negative report on machine translation kills much work in Natural Language Processing (NLP) for many years. |
| 1967 | Dendral program (Edward Feigenbaum, Joshua Lederberg, Bruce Buchanan, Georgia Sutherland at Stanford) demonstrated to interpret mass spectra on organic chemical compounds. First successful knowledge-based program for scientific reasoning. |
|
| Joel Moses (PhD work at MIT) demonstrated the power of symbolic reasoning for integration problems in the Macsyma program. First successful knowledge-based program in mathematics. |
|
| Richard Greenblatt at MIT built a knowledge-based chess-playing program, MacHack, that was good enough to achieve a class-C rating in tournament play. |
| Late 60s | Doug Engelbart invented the mouse at SRI. |
| 1968 | Marvin Minsky & Seymour Papert publish Perceptrons, demonstrating limits of simple neural nets. |
| 1969 | SRI robot, Shakey, demonstrated combining locomotion, perception and problem solving. |
|
| Roger Schank (Stanford) defined conceptual dependency model for natural language understanding. Later developed (in PhD dissertations at Yale) for use in story understanding by Robert Wilensky and Wendy Lehnert, and for use in understanding memory by Janet Kolodner. |
|
| First International Joint Conference on Artificial Intelligence (IJCAI) held in Washington, D.C. |
| 1970 | Jaime Carbonell (Sr.) developed SCHOLAR, an interactive program for computer-aided instruction based on semantic nets as the representation of knowledge. |
|
| Bill Woods described Augmented Transition Networks (ATN's) as a representation for natural language understanding. |
|
| Patrick Winston's PhD program, ARCH, at MIT learned concepts from examples in the world of children's blocks. |
| Early 70's | Jane Robinson & Don Walker established influential Natural Language Processing group at SRI. |
| 1971 | Terry Winograd's PhD thesis (MIT) demonstrated the ability of computers to understand English sentences in a restricted world of children's blocks, in a coupling of his language understanding program, SHRDLU, with a robot arm that carried out instructions typed in English. |
| 1972 | Prolog developed by Alain Colmerauer. |
| 1973 | The Assembly Robotics group at Edinburgh University builds Freddy, the Famous Scottish Robot, capable of using vision to locate and assemble models. |
| 1974 | Ted Shortliffe's PhD dissertation on MYCIN (Stanford) demonstrated the power of rule-based systems for knowledge representation and inference in the domain of medical diagnosis and therapy. Sometimes called the first expert system. |
|
| Earl Sacerdoti developed one of the first planning programs, ABSTRIPS, and developed techniques of hierarchical planning. |
| 1975 | Marvin Minsky published his widely-read and influential article on Frames as a representation of knowledge, in which many ideas about schemas and semantic links are brought together. |
|
|
The Meta-Dendral learning program produced new results in chemistry (some rules of mass spectrometry) the first scientific discoveries by a computer to be published in a refereed journal. |
| Mid 70's | Barbara Grosz (SRI) established limits to traditional AI approaches to discourse modeling. Subsequent work by Grosz, Bonnie Webber and Candace Sidner developed the notion of "centering", used in establishing focus of discourse and anaphoric references in NLP. |
|
| Alan Kay and Adele Goldberg (Xerox PARC) developed the Smalltalk language, establishing the power of object-oriented programming and of icon-oriented interfaces. |
|
| David Marr and MIT colleagues describe the "primal sketch" and its role in visual perception. |
| 1976 | Doug Lenat's AM program (Stanford PhD dissertation) demonstrated the discovery model (loosely-guided search for interesting conjectures). |
|
| Randall Davis demonstrated the power of meta-level reasoning in his PhD dissertation at Stanford. |
| Late 70's | Stanford's SUMEX-AIM resource, headed by Ed Feigenbaum and Joshua Lederberg, demonstrates the power of the ARPAnet for scientific collaboration. |
| 1978 | Tom Mitchell, at Stanford, invented the concept of Version Spaces for describing the search space of a concept formation program. |
|
| Herb Simon wins the Nobel Prize in Economics for his theory of bounded rationality, one of the cornerstones of AI known as "satisficing". |
|
| The MOLGEN program, written at Stanford by Mark Stefik and Peter Friedland, demonstrated that an object-oriented representation of knowledge can be used to plan gene-cloning experiments. |
| 1979 | Bill VanMelle's PhD dissertation at Stanford demonstrated the generality of MYCIN's representation of knowledge and style of reasoning in his EMYCIN program, the model for many commercial expert system "shells". |
|
| Jack Myers and Harry Pople at University of Pittsburgh developed INTERNIST, a knowledge-based medical diagnosis program based on Dr. Myers' clinical knowledge. |
|
| Cordell Green, David Barstow, Elaine Kant and others at Stanford demonstrated the CHI system for automatic programming. |
|
| The Stanford Cart, built by Hans Moravec, becomes the first computer-controlled, autonomous vehicle when it successfully traverses a chair-filled room and circumnavigates the Stanford AI Lab. |
|
| Drew McDermott & Jon Doyle at MIT, and John McCarthy at Stanford begin publishing work on non-monotonic logics and formal aspects of truth maintenance. |
| 1980's | Lisp Machines developed and marketed. |
|
| First expert system shells and commercial applications. |
| 1980 | Lee Erman, Rick Hayes-Roth, Victor Lesser and Raj Reddy published the first description of the blackboard model, as the framework for the HEARSAY-II speech understanding system. |
|
| First National Conference of the American Association of Artificial Intelligence (AAAI) held at Stanford. |
| 1981 | Danny Hillis designs the connection machine, a massively parallel architecture that brings new power to AI, and to computation in general. (Later founds Thinking Machines, Inc.) |
| 1983 | John Laird & Paul Rosenbloom, working with Allen Newell, complete CMU dissertations on SOAR. |
|
| James Allen invents the Interval Calculus, the first widely used formalization of temporal events. |
| Mid 80's | Neural Networks become widely used with the Backpropagation algorithm (first described by Werbos in 1974). |
| 1985 | The autonomous drawing program, Aaron, created by Harold Cohen, is demonstrated at the AAAI National Conference (based on more than a decade of work, and with subsequent work showing major developments). |
| 1987 | Marvin Minsky publishes The Society of Mind, a theoretical description of the mind as a collection of cooperating agents. |
| 1989 | Dean Pomerleau at CMU creates ALVINN (An Autonomous Land Vehicle in a Neural Network), which grew into the system that drove a car coast-to-coast under computer control for all but about 50 of the 2850 miles. |
| 1990's | Major advances in all areas of AI, with significant demonstrations in machine learning, intelligent tutoring, case-based reasoning, multi-agent planning, scheduling, uncertain reasoning, data mining, natural language understanding and translation, vision, virtual reality, games, and other topics. |
|
| Rod Brooks' COG Project at MIT, with numerous collaborators, makes significant progress in building a humanoid robot |
| Early 90's | TD-Gammon, a backgammon program written by Gerry Tesauro, demonstrates that reinforcement learning is powerful enough to create a championship-level game-playing program by competing favorably with world-class players. |
| 1997 | The Deep Blue chess program beats the current world chess champion, Garry Kasparov, in a widely followed match. |
|
| First official Robo-Cup soccer match featuring table-top matches with 40 teams of interacting robots and over 5000 spectators. |
| Late 90's | Web crawlers and other AI-based information extraction programs become essential in widespread use of the world-wide-web. |
|
| Demonstration of an Intelligent Room and Emotional Agents at MIT's AI Lab. Initiation of work on the Oxygen Architecture, which connects mobile and stationary computers in an adaptive network. |
| 2000 | Interactive robot pets (a.k.a. "smart toys") become commercially available, realizing the vision of the 18th cen. novelty toy makers. |
|
| Cynthia Breazeal at MIT publishes her dissertation on Sociable Machines, describing KISMET, a robot with a face that expresses emotions. |
|
| The Nomad robot explores remote regions of Antarctica looking for meteorite samples. |
|
|
