[ExI] AI milestones

Wed Feb 29 18:40:15 UTC 2012

I have been asked to make a list of milestones in AI development. This 
is my current list, what have I missed? And what *actually* matters? 
Academic papers easily overstate their importance or rig demos, actual 
use is often hidden inside industry (few papers or reports), and 
impressiveness might correlate very loosely with real importance.

1950 First serious analysis of whether machines can think. Alan Turing, 
Computing Machinery and Intelligence, Mind, 59:433–460, 1950.

1955-1956 Logic Theorist by Allen Newell, Herbert Simon and J. C. Shaw. 
Intended to mimic human problem solving skills. It eventually proved 38 
of the first 52 theorems in Whitehead and Russell's Principia 
Mathematica (with new and more elegant proofs for some). They later 
developed the General Problem Solver for more general domains. 
http://shelf1.library.cmu.edu/IMLS/MindModels/logictheorymachine.pdf
McCorduck, Pamela (2004), Machines Who Think (2nd ed.), Natick, MA: A. 
K. Peters, Ltd., p. 167

1959 Arthur Samuel’s checkers program. Originally written in 1952, the 
1955 version incorporated machine learning. First demonstration of a 
program that could learn to play a game better than its creator.
Samuel, Arthur L. (July 1959), "Some studies in machine learning using 
the game of checkers", IBM Journal of Research and Development 3 (3): 
210–219, doi:10.1147/rd.33.0210
Schaeffer, Jonathan. One Jump Ahead:: Challenging Human Supremacy in 
Checkers, 1997,2009, Springer, ISBN 978-0-387-76575-4. Chapter 6.

1964 ELIZA by Joseph Weizenbaum demonstrates a conversation interface 
and that humans are very easily fooled into believing there is 
intelligence behind it. Jospeh Weizenbaum, Computer Power and Human 
Reason: From Judgment to Calculation (1976)

1964 ANALOGY by Thomas G. Evans solves geometric analogy problems of the 
same kind as found in standard intelligence tests. Performance was about 
the level of a dull Grade 9 student. Thomas G. Evans, A heuristic 
program to solve geometric-analogy problems, AFIPS '64 (Spring) 
Proceedings of the April 21-23, 1964, spring joint computer conference, 
ACM New York, NY, USA

1975 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.

1979 The first human killed in an industrial robot accident. $10 Million 
Awarded To Family Of U.S. Plant Worker Killed By Robot", Ottawa Citizen, 
August 11, 1983, p14

1979 The backgammon program BKG by Hans Berliner defeats the reigning 
world champion. This was the first computer program to defeat a world 
champion in any game (although Berliner stated that it was due to luck 
with the dice rolls).
Berliner, Hans, et al. "Backgammon program beats world champ", ACM 
SIGART Bulletin, Issue 69. January 1980. pp 6-9.

1979 MYCIN, an expert system, demonstrates performance within its own 
domain (bacterial infection) as good as some experts and better than 
general practitioners. Yu, V.L., et al. (1979). "Antimicrobial selection 
by a computer: a blinded evaluation by infectious disease experts". 
Journal of the American Medical Association 242 (12): 1279–1282. PMID 
480542.

1979 Cordell Green, David Barstow, Elaine Kant and others at Stanford 
demonstrated the CHI system for automatic programming. 
http://aaai.org/AITopics/BriefHistory

1981-1982 Douglas Lenat’s heuristic program Eurisko wins the United 
States Traveller TCS championship both years, forcing rule changes due 
to its unorthodox strategies. Douglas B. Lenat, Eurisko: A program that 
learns new heuristics and domain concepts: The nature of Heuristics III: 
Program design and results, Artificial Intelligence, vol 21:1-2, March 
1983, p. 61-98
Douglas B. Lenat, Learning program helps win national fleet wargame 
tournament, ACM SIGART Bulletin Issue 79, January 1982
Malcolm Gladwell, How David Beats Goliath: When underdogs break the 
rules, May 11 2009
http://www.newyorker.com/reporting/2009/05/11/090511fa_fact_gladwell?currentPage=all

1991 The DART tool for automated logistics planning and scheduling was 
used during Operation Desert Storm with great success, sometimes 
surprising military planners. DARPA claims this single application more 
than paid back their 30 year investment in AI. Cross, Stephen E.; 
Edward, Walker (1994). Zweben, Monte; Fox, Mark S.. eds. Intelligent 
Scheduling. University of Michigan: Morgan Kaufmann. pp. 711–729.
Reese Hedberg, Sarah (2002). "DART: Revolutionizing Logistics Planning". 
IEEE Intelligent Systems (IEEE) 17 (3): 81–83

1992 The backgammon program TD-Gammon by Gerry Tesauro reaches 
championship-level ability through reinforcement learning and self-play. 
Tesauro, Gerald (March 1995). "Temporal Difference Learning and 
TD-Gammon". Communications of the ACM 38 (3).

1994 Automatic speech recognition reaches range of human transcription 
errors for air travel planning kiosk speech. 
http://www.itl.nist.gov/iad/mig/publications/ASRhistory/index.html

1996 Genetic algorithms evolve analog electronic circuits competitive 
with human designers. Koza, J.R.; Bennett, F.H., III; Andre, D.; Keane, 
M.A.; Four problems for which a computer program evolved by genetic 
programming is competitive with human performance, Proceedings of IEEE 
International Conference on Evolutionary Computation, 1996.,
20-22 May 1996 Nagoya, pp. 1 - 10

1997 The Deep Blue chess machine beats the world chess champion, Garry 
Kasparov.Since then chess computers have increased in power.
Monty Newborn, Beyond Deep Blue; chess in the stratosphere, Springer 2011

1999 The crossword-solving program Proverb better than the average 
crossword-solver. Proverb: The probabilistic cruciverbalist. By Greg A. 
Keim, Noam Shazeer, Michael L. Littman, Sushant Agarwal, Catherine M. 
Cheves, Joseph Fitzgerald, Jason Grosland, Fan Jiang, Shannon Pollard, 
and Karl Weinmeister. 1999. In Proceedings of the Sixteenth National 
Conference on Artificial Intelligence, 710-717. Menlo Park, Calif.: AAAI 
Press.

2000 Marcus Hutter’s universal artificial intelligence agent (AIXI), a 
theoretical but well-defined agent that behaves optimally in any 
computable environment. A computable but still impractical algorithm 
(AIXItl) has been implemented. http://www.hutter1.net/ai/paixi.htm

2001 The Unmanned Aerial Vehicle Global Hawk made the first autonomous 
non-stop flight over the Pacific Ocean from Edwards Air Force Base in 
California to RAAF Base Edinburgh in Southern Australia. 
http://www.spacedaily.com/news/uav-01d.html

2001 Robotic trading agents consistently beat humans in a commodities 
trading game. Robots Beat Humans in Trading Battle. BBC.com (August 8th, 
2001) news.bbc.co.uk/1/hi/business/1481339.stm
Agent-Human Interactions in the Continuous Double Auction", IBM 
T.J.Watson Research Center, August, 2001
http://researcher.ibm.com/researcher/files/us-kephart/AgentHuman.pdf

2002 Scrabble playing software exceeds best human players. Sheppard, B. 
(2002). "World-championship-caliber Scrabble". Artificial Intelligence 
134: 241–275. doi:10.1016/S0004-3702(01)00166-7

2004 Automatic speech recognition of broadcast English reaches 10% word 
error rate. 
http://www.itl.nist.gov/iad/mig/publications/ASRhistory/index.html

2004-2007 The DARPA Grand Challenge for autonomous vehicles. In 2004 
none of the vehicles succeeded the course (the furthest distance 
travelled before getting stuck was a little over 11 km). In 2005 five 
vehicles successfully navigated the 240 km course (the Stanford vehicle 
completed it in 6:54). In 2007 the urban challenge had a 96 km course in 
urban terrain with other vehicles and a requirement to follow traffic 
rules; the winning vehicle completed it in 4:10.
Sebastian Thrun, Mike Motemerlo, Hendrik Dahlkamp et al., Stanley: The 
Robot that Won
the DARPA Grand Challenge, Journal of Robotic Systems - Special Issue on 
the DARPA Grand Challenge, Part 2, Volume 23 Issue 9, September 2006
Martin Buehler, Karl Iagnemma, Sanjiv Singh (eds.) The DARPA Urban 
Challenge, Springer tracts in advanced robotics 56, 2009

2005-2006 Bridge playing software is on par with the best bridge teams. 
http://en.wikipedia.org/wiki/Computer_bridge#Computers_versus_humans

2007 The STANDUP pun generator is found consistently entertaining by 
children. Graeme Ritchie, Ruli Manurung, Helen Pain, Annalu Waller, Rolf 
Black, Dave O'Mara. "A practical application of computational humour." 
In Cardoso, A. & Wiggins, G. (Ed.) Proceedings of the 4th. International 
Joint Workshop on Computational Creativity, London, UK, 2007, pp. 91-98.
http://inf.abdn.ac.uk/research/standup/

2009 OCR accuracy for commercial OCR software between 71% to 98% for 
typeset text. For ISO 1073-1:1976 and similar typefaces intended for OCR 
performance is human-equivalent. Holley, Rose (April 2009). "How Good 
Can It Get? Analysing and Improving OCR Accuracy in Large Scale Historic 
Newspaper Digitisation Programs". D-Lib Magazine.
http://www.dlib.org/dlib/march09/holley/03holley.html

2010 Demonstration that a surgical robot can learn tasks from human 
examples, smooth them and perform them 7-10 times faster, reaching 
superhuman performance on these tasks. van den Berg, J.; Miller, S.; 
Duckworth, D.; Hu, H.; Wan, A.; Xiao-Yu Fu; Goldberg, K.; Abbeel, P.; 
Superhuman performance of surgical tasks by robots using iterative 
learning from human-guided demonstrations, 2010 IEEE International 
Conference on Robotics and Automation (ICRA), 3-7 May 2010, Anchorage, 
AK. P. 2074 - 2081

2010 The May 6 “Flash crash”, where the Dow Jones descended 600 points 
only to return to norml after a few minutes. Algorithmic and high 
frequency trading were blamed as contributing. High frequency trading 
corresponds to more than 73% of US trading by volume, and financial news 
are increasingly presented in computer-readable form for the trading 
algorithms. http://en.wikipedia.org/wiki/Algorithmic_trading

2010 The VisLab Intercontinental Autonomous Challenge, a 13,000 km test 
run of autonomous vehicles. Four driverless electric vans successfully 
ended the drive from Italy to China, arriving at the Shanghai Expo on 28 
October, 2010. It was the first intercontinental trip ever with 
autonomous vehicles. http://viac.vislab.it/

2010 A jigsaw-puzzle solver handles 400 piece arbitrary image puzzles. 
http://people.csail.mit.edu/
taegsang/JigsawPuzzle.html

2011 Sentiment analysis for online text at the same level at human 
reliability. Andrew L Maas, Raymond E Daly, Peter T Pham, Dan Huang, 
Andrew Y Ng, Christopher Potts, Learning Word Vectors for Sentiment Analysis
Computational Linguistics (2011) Volume: 31, Issue: Jne 19-24, 2011, 
Publisher: Association for Computational Linguistics, Pages: 142-150

2011 Heuristics evolved using genetic algorithms produce a solver for 
the NP-hard solitaire game FreeCell, able to beat high-ranking human 
players. Achiya Elyasaf, Ami Hauptmann, Moshe Sipper, GA-FreeCell: 
Evolving Solvers for the Game of FreeCell, GECCO’11, July 12–16, 2011, 
Dublin, Ireland.

2011 IBM’s Watson defeats the two greatest Jeopardy! Champions during an 
exhibition match.

2011 Computer poker players remain sub-human for full ring Texas hold 
'em but approaching strong super-human in simpler versions of poker. 
Rubin, Jonathan; Watson, Ian (2011). "Computer poker: A review". 
Artificial Intelligence. doi:10.1016/j.artint.2010.12.005.

2012 The Zen series of go-playing programs reaches rank 4-5 dan (strong 
amateur level). 
http://blog.printf.net/articles/2012/02/23/computers-are-very-good-at-the-game-of-go

-- 
Anders Sandberg,
Future of Humanity Institute
Philosophy Faculty of Oxford University