Checkers

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 Some Studies in Machine Learning Using the Game of Checkers. II—Recent Progress

Games & Puzzles

Contents

Vertical Tabs

Good Starting Places

Publication

Man Versus Machine for the World Checkers Championship

."In August 1992, the world checkers champion, Marion Tinsley, defended his title against the computer program CHINOOK. Because of its success in human tournaments, CHINOOK had earned the right to play for the world championship.Tinsley won the best-of-40-game match with a score of 4 wins, 2 losses, and 33 draws. This event was the first time in history that a program played for a human world championship and might be a prelude to what is to come in chess. This article tells the story of the first Man versus Machine World Championship match."

Source

By Schaeffer, Jonathan ; Norman Treloar, Paul Lu, Robert Lake
CHINOOK

General Readings

Link

Program Proves That Checkers, Perfectly Played, Is a No-Win Situation

"If two players face off at checkers and neither makes a wrong move, then the game will inevitably end in a draw. That's the result of a proof executed by hundreds of computers over nearly 2 decades and reported online by Science this week." (Science News of the Week, July 20 2007)

Source

2007
Link

The Macleans.ca Interview: Jonathan Schaeffer

"The computer scientist who solved checkers on whether he's killed the game, why his wife is so happy and what game he's going after next" (Macleans, July 20 2007)

Source

2007
Podcast

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

Source

Sep 17 2005, By Fogel, David, 33 min
genetic algorithms
Link

It's Only Checkers, but the Computer Taught Itself

"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."  (The New York Times, July 25, 2000).

Source

2000
Link

Computers, Games and the Real World

"More than just competing with people, game-playing machines complement human thinking by offering alternative methods to solving problems." (Scientific American, "Exploring Intelligence" 1998)

Source

1998
Link

One Jump Ahead: Challenging Human Supremacy in Checkers

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

Source

Podcasts

Podcast

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

Source

Sep 17 2005, By Fogel, David, 33 min
genetic algorithms

Classic Articles & Books

Pages

Publication

Machine learning

Source

By Samuel, A. L., 1959
classic
Publication

Programming a computer to play games

Source

By Samuel, A. L., 1960
classic
Publication

Some studies in machine learning using the game of checkers

The studies reported here have been concerned with the programming ofa digital computer to behave in a way which, if done by human beings oranimals, would be described as involving the process of learning. Whilethis is not the place to dwell on the importance of machine-learning procedures,or to discourse on the philosophical aspects,1 there is obviously avery large amount of work, now done by people, which is quite trivial inits demands on the intellect but does, nevertheless, involve some learning.

Source

By Samuel, A. L. , 1959
classic
Publication

Some Studies in Machine Learning Using the Game of Checkers, II - Recent Progress

A new signature table technique is described together with an improved book learning procedure which is thought to be much superior to the linear polynomial method described earlier. Full use is made of the so called “alpha-beta” pruning and several forms of forward pruning to restrict the spread of the move tree and to permit the program to look ahead to a much greater depth than it other- wise could do. While still unable to outplay checker masters, the program’s playing ability has been greatly improved.

Source

By Samuel, A. L., 1967
classic, signature tables
Publication

A comparison and evaluation of three machine learning procedures as applied to the game of checkers

Source

By Griffith, A. K. , 1974
classic
Publication

A theory of chess and noughts and crosses

By Davies, D. W. , 1950
classic

Pages

Vertical Tabs