Graham Kendall
Introduction
This page contains a history of computers playing checkers. This review is
currently done from an academic point of view but will be expanded to cover
the history of the game in due course.
You might also want to look at my home page (with
navigation bar) or my game playing research page.
I am a lecturer at The University of
Nottingham where I lecture on artificial intelligence and specialise on
how computers can learn to play games without being told how to play (i.e. they
are given no information as to game strategy, instead the computer has to "learn"
the strategy for themselves). From an academic point of view I have published
several articles on this research area (see my game
playing articles).
The page contains references to the relevant academic literature (please let
me know (by EMAIL) if I have missed any
papers).
I have also listed some of the poker sites you might find of interest. If your
site is not here, EMAIL me, and I'll
include it.
This page is part of my game playing web site.
History
Arthur Samuel, in 1952 (Samuel, 1959), wrote the first checkers program. The original program was
written for an IBM 701 computer. In 1954 he re-wrote the program for an IBM 704 and added
a learning mechanism. What makes this program stand out in AI history is that the program was
able to learn its own evaluation function. Taking into account the IBM 704 had only 10,000 words
of main memory, magnetic tape for long-term storage and a cycle time of almost one-millisecond,
this can be seen as a major achievement in the development of AI.
Samuel made the program play against itself and after only a few days play, the program was
able to beat its creator and compete on equal terms with strong human opponents.
It remains as a testament to Samuel that there was little more work done on checkers
until Jonathon Schaeffer et. al. developed Chinook (Schaeffer, all refs). This
program uses alpha-beta search (which we consider below) and also has a database
to allow it to play a perfect end game. In 1992 Chinook won the US Open and subsequently
challenged for the world championship. Dr. Marion Tinsley had been the world champion
for over 40 years. In that time he only lost three games. Playing Chinook he lost
his fourth and fifth game but ultimately won the match by 21.5 points to Chinook’s
18.5 points. In August 1994 there was a re-match but the match ended prematurely
when Dr. Tinsley had to withdraw for health reasons. As a result of this Chinook
become the official world champion. Scheaffer claimed that Chinook was rated at
2814. The best human players are rated at 2632 and 2625. Chinook did not include
any learning mechanisms.
More recently (Chellapilla, 1999), (Chellapilla, 2000) and (Fogel, 2001) developed a checkers program that "learnt" how to play a good
game of checkers. The program started knowing just the rules of the game so that it could
make legal moves. The program was allowed to evolve by creating a population of games
that competed against one another, with the best games surviving and being adapted in some way
before competing again. The adaptation was done using a neural network with the weights on the synapses being changed by an evolutionary strategy. The best program was allowed to compete against a commercial version of checkers and it beat it 6-0. The program got called Anaconda due to the way it put a strangle hold on its opponents.
I actually saw this program as the CEC conference at which the paper was presented.
It challenged anybody who cared to play it and remain undefeated throughout the duration
of the conference.
Publications
- Chellipilla K. and Fogel, D. B. 1999. Evolution, Neural Networks, Games, and Intelligence.Proc. IEEE, Vol 87, No. 9, pp 1471-1498, 1999.
This paper looks at zer-sum games paying particular attention to how strategies can be evolved without injecting
expert knowledge into the program. Games such as prisiners dilemma and checkers are considered.
- Chellipilla K. and Fogel, D. B. 2000. Anaconda Defeats Hoyle 6-0: A Case Study Competing an Evolved Checkers Program against Commercially Available Software. In Proceedings of Congress on Evolutionary Computation, July 16-19 2000, La Jolla Marriot Hotel, La Jolla, California, USA, pp 857-863.
This paper shows how a computer can simply be told the rules of a game (checkers in this case)
and then learn a good strategy. Over time the program learnt to such an extent that it was able to
compete at a level of many human players and beat commercially available software.
- Schaeffer, Jonathan 1997. One Jump Ahead: Challenging Human Supremacy in Checkers. New York: Springer-Verlag.
This is the book Jonathan Schaeffer wrote, telling the story of CHINOOK and how it became
the checkers world champion.
Take a look here
for more details
- Schaeffer J. 1996. One Jump Ahead: Challenging Human Supremacy in Checkers, Springer, Berlin
- Schaeffer J., Lake R., Lu P. 1996. CHINOOK The World Man-Machine Checkers Champion. AI Magazine, 17(1), pp 21-30
This paper tells the story of the re-match between Marion Tinsley and CHINOOK and how CHINOOK became the
world checkers champion; the first time a computer had become world champion in such a sport.
An electronic version of this paper is available at
http://www.aaai.org/Pathfinder/html/checkers.html
- Schaeffer J., Treloar N., Lu P., Lake R. 1993. Man Versus Machine for the World Checkers Championship. AI Magazine, 14(2), pp 28-35
This paper tells the story of the first time CHINOOK played Marion Tinsley. The match ended with 4 wins
for Tinsley, 2 wins for CHINOOK and 33 draws. An electronic version of this paper is available at
http://www.aaai.org/Pathfinder/html/checkers.html
- Schaeffer, Jonathan, Joseph Culberson, Norman Treloar, et al. 1992. A World Championship
Caliber Checkers Program. Artificial Intelligence 53 (2/3), pp273-290.
- Fogel, D. Blondie24 : Playing at the Edge of AI. Morgan Kaufmann, 2001, ISBN:1558607838
This book tells the story of a checkers program that learns its own strategy using evolutionary
strategies and neural networks.
- Levy, D. Beal D. F. eds. 1989. Heuristic Programming in
Artificial Intelligence: The First Computer Olympiad. Chichester, UK: Ellis Horwood.
Two papers by D. Oldbury and by J. Smeets and G. Putter are about computers playing checkers/draughts
- Levy, D. ed. 1988. Computer Games I. New York: Springer-Verlag.
Chapter 3 has three papers on prgramming computers to play checkers/draughts,
including the 1967 paper by Samuel.
- Akl, S. 1987. Checkers-Playing Programs. In Encyclopedia of Artificial Intelligence,
Vol. 1, ed. Shapiro, Stuart C., 88-93. New York: John Wiley & Sons.
- Griffith, K. A. 1974. A Comparison and Evaluation of Three Machine Learning Procedures
as Applied to the Game of Checkers. Artificial Intelligence 5: 137-148.
- Samuel A. L. 1967. Some Studies in Machine Learning using the Game of Checkers II - Recent Progress. IBM Journal of Research and Development, 11(6), pp 601-617
Reproduced in: Levy D. L. ed 1988 Computer Games I, pp366-400. New York: Springer-Verlag
- Samuel A. L. 1959. Some Studies in Machine Learning using the Game of Checkers. IBM Journal of Research and Development, 3(3), pp 210-229
Reproduced in: E. A. Feigenbaum and J. Feldman., eds Computers and Thought, New York: McGraw Hill
Reproduced in: Samuel A. L. 2000. Some Studies in Machine Learning using the Game of Checkers. IBM Journal of Research and Development, Vol. 44 No. 1/2 January/March, pp 207-226
Reproduced in: Luger G.F. ed 1995 Studies in Machine Learning Using the Game of Checkers.
In Computation and Intelligence: Collected Readings, Menlo Park, CA/Cambridge, MA/London:
AAAI Press/The MIT Press
This is the seminal work in this area. It is seen as a milestone in AI history
Links
Links
Last Updated 26th Mar 2001
