Artificial Intelligence

From Chessprogramming wiki
Jump to: navigation, search

Home * Artificial Intelligence

Bernd Besser, computerzeitalter [1]

Artificial Intelligence, (AI)
the intelligence of machines and the branch of computer science that aims to create it. While 'machine intelligence' was already mentioned by Alan Turing in the 1940s during his research at Bletchley Park [2] [3] , the term 'artificial intelligence' was coined by John McCarthy in the proposal for the 1956 Dartmouth Conference [4] . In its beginning, Computer Chess was called the Drosophila of Artificial Intelligence. In the 70s, when brute-force programs started to dominate, and competitive and commercial aspects have taken precedence over using chess as a scientific domain, the AI community more and more lost interest in chess [5] . In disagreement with the AI establishment in the 80s, Peter W. Frey concluded, that the AI community should follow computer chess methods rather than the other way around [6] .

Drosophila of AI

Donald Michie

Quote from I remember Donald Michie by Maarten van Emden [7] :

In the 1970s DM was fond of proclaiming “Chess, the Drosophila Melanogaster of Artificial Intelligence”. A public pronouncement of his point of view can be found in an interview with H.J. van den Herik held in 1981 (“Computerschaak, schaakwereld en kunstmatige intelligentie” by H.J. van den Herik, Academic Service, 1983) [8] . It is a long interview, from which I quote DM’s answer to the question: “What do you think about the applicability of the research done in computer chess?” 
The applicability is I think enormous and quite critical. Scientific study of computer chess, which includes the technological work, but goes far beyond that, is the most important scientific study that is going in the world at present. In the same sense, if I were asked what was the most important study in process during the first world war, I would say the genetic breeding experiments on the drosophila fruit fly by Morgan and his colleagues. The analogy is very good. The final impact of the early work in laying down the basic theoretical framework for the subject was just enormous, unimaginable. We see now the industrial take-off of genetic engineering which is the delayed final outcome for human society of the fly-breeding work. The use of chess now as a preliminary to the knowledge engineering and cognitive engineering of the future is exactly similar, in my opinion, to the work on drosophila. It should be encouraged in a very intense way, for these reasons. 

John McCarthy

Quote by John McCarthy from What is Artificial Intelligence? [9] [10]:

Alexander Kronrod, a Russian AI researcher, said 'Chess is the Drosophila of AI.' He was making an analogy with geneticists' use of that fruit fly to study inheritance. Playing chess requires certain intellectual mechanisms and not others. Chess programs now play at grandmaster level, but they do it with limited intellectual mechanisms compared to those used by a human chess player, substituting large amounts of computation for understanding. Once we understand these mechanisms better, we can build human-level chess programs that do far less computation than do present programs. Unfortunately, the competitive and commercial aspects of making computers play chess have taken precedence over using chess as a scientific domain. It is as if the geneticists after 1910 had organized fruit fly races and concentrated their efforts on breeding fruit flies that could win these races.

Anthony Cozzie

Anthony Cozzie in a forum discussion about McCarthy's statement [11] [12] :

First, the author of this quote is simple WRONG. The generally accepted theory of how humans play chess is that the brain does fuzzy matching on a database of several hundred thousand positions. The amount of computation needed to do that is FAR greater than the amount expended by a "conventional" AB searcher, and yet the computer plays MUCH better than the average human. The simple fact of the matter, which you refuse to recognize, is that AB-search with reasonable heuristics is the most efficient way to play chess with Von Neuman machines.
Secondly, the existence of current amateur and commercial programs does nothing to prevent you from writing whatever kind of chess playing agent you want. If you want to experiment, no one is stopping you or him from applying to NSF for research money and giving it a shot. The existence of "fruit fly races" - and his fruit fly analogy is totally flawed. A better analogy would be that a geneticist decided to make a fruit fly that could run faster than a human - does nothing to prevent casual study of one's own fruit flies. 

Heuristic Programming

Remembering Kronrod

Quote from Remembering A.S. Kronrod by Evgenii Landis and Isaak Yaglom [13]:

Only in 1955 did a real opportunity arise for A.S. Kronrod to work with an electronic computer. It was the M­2 computer constructed by I.S. Bruk, M.A. Kartsev, and N.Ya. Matyukhin in the laboratory of the Institute of Energy named after Krzhizhanovsky and directed by I.S. Bruk. This laboratory later became the to Institute for Electronic Control Machines. The mathematics/machine interface was developed by A.L. Brudno, a great personal and like­minded friend of A.S. Kronrod.
When he started with enthusiasm to program the M­2 machine, A.S. Kronrod quickly came to the conclusion that computing is not the main application of computers. The main goal is to teach the computer to think, i.e., what is now called "artificial intelligence" and in those days "heuristic programming".
A.S. Kronrod captivated a large group of mathematicians and physicists (G.M. Adelson ­Velsky, A.L. Brudno, M.M. Bongard, E.M. Landis, N.N. Konstantinov, and others). Although some of them had arrived at this kind of problems on their own, they unconditionally accepted his leadership. In the room next to the one housing the M­2 machine the work of the new Kronrod seminar started. At the gatherings there were heated discussions on pattern recognition problems (this work was led by M.M. Bongard; versions of his program "Kora" are still functioning), transportation problems (the problem was introduced to the seminar and actively worked on by A.L. Brudno), problems of automata theory, and many other problems.

Intellectual Foundations

Quote from Biography AS Kronrod by Alexander Yershov [14]

In 1958, Kronrod, Adelson-Velsky, and Landis selected "Snap" ("подкидного дурака") as the intellectual foundations for the development of the game heuristic programming. The program itself was a fiasco - but the basic principles (board games, search techniques and limited depth) were formulated. Further research laboratories in the field of game theory culminated in the first ever chess duel between the program of the Institute of Soviet and American best program developed at Stanford University under the direction of J. McCarthy. By telegraph match was played in four games ended 3-1 in favor of our institute. At the time, chess became a guinea pig for all programmers interested in artificial intelligence.

The 12th IJCAI

In a panel discussion at the 12th International Joint Conference on Artificial Intelligence, Robert Levinson, Feng-hsiung Hsu, Tony Marsland, Jonathan Schaeffer, and David Wilkins commented on the relationship between computer chess and AI research [15] . As pointed out by Peter W. Frey, many emphasized the discrepancy between both domains and seemed to lament the inferiour status of the work of computer chess - some excerpts quoted by Frey in his Computer Chess vs. AI paper [16] .

Jonathan Schaeffer

 Sadly, most of the work currently being done on computer chess programs is engineering, not science. For example, the engineering of special-purpose VLSI chips to increase the speed of a chess program only underlines the importance chess programmers attach to speed. In my opinion, conventional computer-chess methods will yield little of further interest to the AI community. 

Tony Marsland

 Pruning by analogy is a powerful general-purpose tool and if developed satisfactorily for a perfect information game like chess would almost certainly be applicable to related decision-tree searches...
It is remarkable that no significant improvement has been made to that method, despite the passage of 15 years. Not even attempts to implement simple forms of the idea in serious chess programs. 

Robert Levinson

Psychological evidence indicates that human chess players search very few positions, and base their positional assessments on structural/perceptual patterns learned through experience.
The main objectives of the project are to demonstrate capacity of the system to learn, to deepen our understanding of the interaction of knowledge and search, and to build bridges in this area between AI and cognitive science. 

David Wilkins

Hardware advances have made chess a less fertile ground for addressing the basic issues of AI. The game is small enough that brute-force search techniques have dominated competitive computer chess, and I see little AI interest in squeezing out the last few hundred points on the chess ratings. 

AI as Sport

John McCarthy from AI as Sport, 1997 [17] , in a review of Monty Newborn's Deep Blue vs. Kasparov [18] :

Now that computers have reached world-champion level, it is time for chess to become a Drosophila again. Champion-level play is possible with enormously less computation than Deep Blue and its recent competitors use. Tournaments should admit programs only with severe limits on computation. This would concentrate attention on scientific advances. Perhaps a personal computer manufacturer would sponsor a tournament with one second allowed per move on a machine of a single design. Tournaments in which players use computers to check out lines of play would be man-machine collaboration rather than just competition.
Besides AI work aimed at tournament play, particular aspects of the game have illuminated the intellectual mechanisms involved. Barbara Liskov demonstrated that what chess books teach about how to win certain endgames is not a program but more like a predicate comparing two positions to see if one is an improvement on the other. Such qualitative comparisons are an important feature of human intelligence and are needed for AI. Donald Michie, Ivan Bratko, Alen Shapiro, David Wilkins, and others have also used chess as a Drosophila to study intelligence. Newborn ignores this work, because it is not oriented to tournament play. 

Making Computer Chess Scientific

A further note by John McCarthy from Making Computer Chess Scientific [19] :

AI has two tools for tackling problems. One is to use methods observed in humans, often observed only by introspection, and the other is to invent methods using ideas of computer science without worrying about whether humans do it this way. Chess programming employs both. Introspection is an unreliable way of determining how humans think, but introspectively suggested methods are valid as AI if they work.
Much of the mental computation done by chess players is invisible to the player and to outside observers. Patterns in the position suggest what lines of play to look at, and the pattern recognition processes in the human mind seem to be invisible to that mind. However, the parts of the move tree that are examined are consciously accessible.
It is an important advantage of chess as a Drosophila for AI that so much of the thought that goes into human chess play is visible to the player and even to spectators. When chess players argue about what is the right move in a position, they follow out lines of play, i.e. argue explicitly about parts of the move tree. Moreover, when a player is found to have made a mistake, it is almost always a failure to follow out a certain line of play rather than a misevaluation of a final position. 

Go, the new Drosophila of AI

A quote by Gian-Carlo Pascutto on AI in Go and Chess [20] :

There is no significant difference between an alpha-beta search with heavy LMR and a static evaluator (current state of the art in chess) and an UCT searcher with a small exploration constant that does playouts (state of the art in go).
The shape of the tree they search is very similar. The main breakthrough in Go the last few years was how to backup an uncertain Monte Carlo score. This was solved. For chess this same problem was solved around the time quiescent search was developed.
Both are producing strong programs and we've proven for both the methods that they scale in strength as hardware speed goes up.
So I would say that we've successfully adopted the simple, brute force methods for chess to Go and they already work without increases in computer speed. The increases will make them progressively stronger though, and with further software tweaks they will eventually surpass humans. 

Poker, the next Challenge

Graham Kendall and Jonathan Schaeffer on Poker [21] :

For many years Chess (and perhaps more recently Go) has served as the Drosophila of AI research. Decades of research culminated in the defeat of Garry Kasparov by DEEP BLUE in May 1997. There is still an active research community that uses Chess as a test-bed for AI research (as seen in this journal), but the game is limited in the types of challenges that it can offer to the AI researcher. Being a game of perfect information (both players know the full state of the game at any given point) with a relatively small branching factor, researchers have reduced the challenge of building a strong AI for Chess to merely one of deep brute-force search. The research challenges are to create a good evaluation function, and to design an effective search algorithm. This “solution” to Chess is unappealing to many AI purists. Nevertheless, alternative AI approaches have been largely ineffective.

Poker, as an experimental test-bed for exploring AI, is a much richer domain than Chess (and Go).

  1. Imperfect information. Parts of the game state (opponent hands) are not known.
  2. Multiple players. Many popular poker variants can be played with up to 10 players.
  3. Stochastic. The dealing of the cards adds a random element to the game.
  4. Deception. Predictable play can be exploited by an opponent. Hence, deceptive play is an essential ingredient of strong play (e.g., bluffing).
  5. Opponent modelling. Observing your opponent(s) and adjusting your play to exploit (perceived) opponent tendencies is necessary to maximize poker winnings.
  6. Information sparsity. Many poker hands end in the players not revealing their cards. This limits the amount of data available to learn from.

Subfields

Deep Learning

See also

Selected Publications

1945 ...

1950 ...

1955 ...

1960 ...

1965 ...

1970 ...

1975 ...

1980 ...

1985 ...

1990 ...

1991

1992

1993

1994

1995 ...

1996

1997

1998

1999

2000 ...

2005 ...

2006

2007

2008

2009

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017

AI Game Programming Wisdom

Forum Posts

External Links

Wikipedia

The abandonment of connectionism in 1969 [39] [40]
Physical symbol system from Wikipedia
Digital organism from Wikipedia
Virtual world from Wikipedia
Second Life from Wikipedia

AI in Media

BBC - Future - The cyborg chess players that can’t be beaten by Chris Baraniuk, December 04, 2015 » David Levy, Boris Alterman, Shay Bushinsky, Mark Lefler

Famous AI Programs

Machine Creativity

Associations

AITopics / HomePage
AITopics / AINews

Journals

ScienceDirect - Artificial Intelligence - Online Access
Artificial Intelligence (journal) from Wikipedia

Online Courses

  • MIT OpenCourseWare tries to put as much MIT course material online as possible. Here are two courses on Artificial Intelligence:
6,034 Artificial Intelligence, Spring 2005
6.034 Artificial Intelligence, Fall 2010, Video Lectures by Patrick Winston

Misc

AI on the Web

References

  1. Schaakkunst Bernd Besser
  2. Alan Turing Scrapbook - the Origins of Artificial Intelligence by Andrew Hodges
  3. B. Jack Copeland, Diane Proudfoot (2011-2012). Turing, Father of the Modern Computer. The Rutherford Journal - The New Zealand Journal for the History and Philosophy of Science and Technology, Vol. 4 » with photos of Alan Turing, John von Neumann, Dietrich Prinz, Christopher Strachey, Jack Good, Arthur Samuel, Herbert Simon, Allen Newell, ...
  4. John McCarthy, Marvin Minsky, Nathaniel Rochester, Claude Shannon (1955). A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence.
  5. Hermann Kaindl (1985). What Happened with AI's Drosophila? ÖGAI 1985: 194-203
  6. Peter W. Frey (1991). Memory-Based Expertise: Computer Chess vs. AI, ICCA Journal, Vol. 14, No. 4
  7. I remember Donald Michie (1923 – 2007) « A Programmers Place by Maarten van Emden, June 12, 2009
  8. Jaap van den Herik (1981). Computer Chess Today and Tomorrow: An Interview with Donald Michie. Computer Chess Digest Annual 1984
  9. John McCarthy (1989). The Fruitfly on the Fly. ICCA Journal, Vol. 12, No. 4
  10. John McCarthy (1990). Chess as the Drosophila of AI. Computers, Chess, and Cognition, pp. 227-237
  11. Fruit fly races by Steven Edwards, CCC, April 06, 2005
  12. Re: Fruit fly races by Anthony Cozzie, CCC, April 06, 2005
  13. Evgenii Landis, Isaak Yaglom (1987). Remembering A.S. Kronrod. (2002). Translation by Viola Brudno, Edited by Walter Gautschi, ps
  14. Биография А.С. Кронрода, Biography AS Kronrod by Alexander Yershov (translated by Google Translate)
  15. Robert Levinson, Feng-hsiung Hsu, Tony Marsland, Jonathan Schaeffer, David Wilkins (1991). The Role of Chess in Artificial Intelligence Research. IJCAI 1991, pdf, also in ICCA Journal, Vol. 14, No. 3, pdf
  16. Peter W. Frey (1991). Memory-Based Expertise: Computer Chess vs. AI. ICCA Journal, Vol. 14, No. 4
  17. John McCarthy (1997). AI as Sport. Science, Vol. 276
  18. Monroe Newborn (1997). Kasparov versus DEEP BLUE: Computer Chess Comes of Age. Springer
  19. Making Computer Chess Scientific by John McCarthy
  20. Re: Chess vs Go // AI vs IA by Gian-Carlo Pascutto, June 02, 2010
  21. Graham Kendall, Jonathan Schaeffer (2006). Poker. ICGA Journal, Vol. 29, No. 3
  22. Rosenblatt's Contributions
  23. General Problem Solver from Wikipedia
  24. Publications of John Maynard Smith (pdf)
  25. The abandonment of connectionism in 1969 - Wikipedia
  26. Frank Rosenblatt (1962). Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. Spartan Books
  27. Physical symbol system from Wikipedia
  28. K-line (artificial intelligence) from Wikipedia
  29. John McCarthy (1997). Chess as the Drosophila of AI. Computer Science Department, Stanford University, condensed version of the 1990 paper, pdf
  30. Re: ICCA Journal Sinks To A New Low by Amir Ban, CCC, January 25, 1998
  31. Christian Jongeneel (1996). The informatical worldview, an inquiry into the methodology of computer science. Ph.D. thesis, Delft University of Technology, advisor Henk Koppelaar, The evolution of information in man and machine | Christian Jongeneel
  32. Terasem Journal of Personal Cyberconsciousness - Marvin Lee Minsky discussing his book, The Emotion Machine
  33. Mark Watson · GitHub
  34. Java implementation of algorithms from Norvig and Russell's Artificial Intelligence: A Modern Approach. 3rd edition
  35. Chess Metaphors – Artificial Intelligence and the Human Mind by Diego Rasskin-Gutman, ChessBase News, January 28, 2010
  36. Dap Hartmann (2010). Sander Bakkes: Rapid Adaptation of Video Game AI. Review, ICGA Journal, Vol. 34, No. 1
  37. Transcript of Kasparov’s TED talk, May 2017
  38. 20 Years after Deep Blue: How AI Has Advanced Since Conquering Chess by Larry Greenemeier, Scientific American, June 2, 2017
  39. Connectionism from Wikipedia
  40. Marvin Minsky, Seymour Papert (1969). Perceptrons.
  41. Intelligence from Wikipedia

Home