Alpha-beta pruning can be explained simply as a technique for not exploring those branches of a search tree that analysis indicates not to be of further interest either to the player making the analysis (this is obvious) or to his opponent (and this is frequently overlooked.) - Arthur L. Samuel, from Machine Learning Using the Game of Checkers II

Good Places to Start

Chinook. Maintained by Computing Science Department, University of Alberta, Canada. Chinook is the first computer program to win a human vs. machine world championship competition. Read about Chinook, download checkers software, link to checkers sites and even play against Chinook!

Readings Online

Accelerating Problem Solving. Listen to this presentation by David Fogel, CEO of Natural Selection, delivered at the Accelerating Change 2005 conference, and made available by IT Conversations: "Experiments in artificial intelligence have focused traditionally on replicating human behaviors in software. Although this approach has achieved some notable successes, including the Deep Blue chess machine that defeated Garry Kasparov in May, 1997, they are limited to addressing problems for which people already have the answers. An alternative approach, using computational intelligence methods such as evolutionary computing, can provide a computer with the ability to learn how to solve complex problems without relying on human expertise. According to Fogel, what works best is the synergistic effect obtained by combining simulated evolutionary learning with human learning. As an example of this latter approach he tells the story of Blondie24, a checkers program supplied with only minimal information that was able to reach high levels of expertise thanks to the application of genetic algorithms."

• Be sure to srcroll further down the page for information about his book, Blondie24: Playing at the Edge of AI. Morgan Kaufmann (2002).

Computers, Games and the Real World. By Matthew L. Ginsberg. Scientific American (special issue: Exploring Intelligence - Winter 1998). "More than just competing with people, game-playing machines complement human thinking by offering alternative methods to solving problems."

It's Only Checkers, but the Computer Taught Itself. By James Glanz. The New York Times (July 25, 2000). "Two computer scientists have leveled the playing field by asking a computer program called a neural network to do something much more difficult than beat a defenseless human at checkers. Knowing only the rules of checkers and a few basics, and otherwise starting from scratch, the program must teach itself how to play a good game without help from the outside world -- including from the programmers. The program did just that, using the electronic equivalent of natural selection."

Do not pass Go. Computers can beat the world's best chess players but have yet to master other classic games like Go. By David Levy. The Guardian (October 24, 2002). "Ever since Garry Kasparov's sensational 1997 loss to the IBM chess monster Deep Blue, the chess world has thirsted for revenge. But the first opportunity ended in failure in Bahrain on Saturday, when Kasparov's former pupil and successor as World Champion, Vladimir Kramnik, could only draw an 8-game match against one of the world's leading chess engines, Fritz. But this was just the latest in a long series of human versus computer encounters that illustrate the inexorable march of artificial intelligence (AI). It's a story that began at a Dartmouth University conference in 1956, when several of the founding fathers of AI defined the goals of that infant science. One of them was to create a computer program that could defeat the world chess champion. Success would, those scientists believed, reach to the very core of human intellectual endeavour. By the early 1990s, due in no small part to the successes achieved in computer chess, the interest of the AI community had spread to many other games of skill, including backgammon, bridge, Go and Scrabble. Where exactly are we now in this fascinating struggle?"

The Preface to the book, One Jump Ahead: Challenging Human Supremacy in Checkers, by Jonathan Schaeffer (1997). New York: Springer-Verlag.

Chinook: The World Man-Machine Checkers Champion. By Jonathan Schaeffer, Robert Lake, Paul Lu, et al. (1996). AI Magazine 17 (1): 21-30. "In 1992, the seemingly unbeatable World Checker Champion Marion Tinsley defended his title against the computer program CHINOOK. After an intense, tightly contested match, Tinsley fought back from behind to win the match by scoring four wins to CHINOOK's two, with 33 draws. This match was the first time in history that a human world champion defended his title against a computer. This article reports on the progress of the checkers (8 3 8 draughts) program CHINOOK since 1992. Two years of research and development on the program culminated in a rematch with Tinsley in August 1994. In this match, after six games (all draws), Tinsley withdrew from the match and relinquished the world championship title to CHINOOK, citing health concerns. CHINOOK has since defended its title in two subsequent matches. It is the first time in history that a computer has won a human-world championship."

Man Versus Machine for the World Checkers Championship. By Jonathan Schaeffer, Norman Treloar, Paul Lu, et al. (1993). AI Magazine 14 (2): 28-35.

Arthur Samuel. A brief biography that can be accessed from our page of tributes.

Related Web Sites

Checkers! By Victor Huang and Sung Ha Huh. Try to beat the checkers program, if you can, and then read the details about its programming.

Konane -- Hawaiian Checkers. From Peter Ingebretson. "About the Game: Konane is an old Hawaiian game, similar to many varieties of checkers. Strategy is reasonably simple, but the game is difficult to win against a talented opponent. The AI playing this game uses a simple minimax algorithm, with alpha-beta pruning to reduce the size of the search tree. As such, it is quite challenging when searching moves deeper than five or six turns in advance."

Robotic Draughts Player from the "Robots!" website at The University of Birmingham. "The robot arm can move to any position on the board, and has a magnet to detect when there is a draughts piece underneath it. When it wants to make a move, it lowers the magnet, to grab the piece. The computer, which decides what move to make, gets signals from the arm, then tells it where to go. The computer uses an artificial intelligence algorithm to decide which move to make." And they even have movies of the arm at work!

Related Pages

• Overview
• Bridge
• Chess
• Crossword Puzzles
• Go
• Othello
• Poker
• Scrabble
• Traveling Salesperson & NP-Complete Problems
• More Games & Puzzles

More Readings

Akl, Selim. 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.

Levy, David N. L., editor. 1988. Computer Games I. New York: Springer-Verlag. Chapter 3 offers three papers on prgramming computers to play checkers (draughts), including the studies in machine learning by A. L. Samuel.

Levy, David N. L., and D. F. Beal, editors. 1989. Heuristic Programming in Artificial Intelligence: The First Computer Olympiad. Chichester, UK: Ellis Horwood. Two papers offered, by D. Oldbury and by J. Smeets and G. Putter "draughts" playing by computer.

Samuel, Arthur L. 1967. Some studies in Machine Learning Using the Game of checkers II. In Computer Games I, ed. Levy, David L., 366-400. New York: Springer-Verlag, 1988.

Samuel, Arthur L. 1959. Some Studies in Machine Learning Using the Game of Checkers. In Computation and Intelligence: Collected Readings, ed. Luger, George F., Menlo Park, CA/Cambridge, MA/London: AAAI Press/The MIT Press, 1995.

Schaeffer, Jonathan. 1997. One Jump Ahead: Challenging Human Supremacy in Checkers. New York: Springer-Verlag. [The Preface is available online.]

Schaeffer, Jonathan, Joseph Culberson, Norman Treloar, et al. 1992. A World Championship Caliber Checkers Program. Artificial Intelligence 53 (2/3): 273-290. A central paper about the program Chinook.