AITopics / Checkers

TOOLBOX

BROWSE TOPICS

ABOUT THIS SITE

Fair Use Notice
© AAAI 2000-2008

pmwiki.org
pmwiki-2.2.0-beta65

edit SideBar

Checkers

(a subtopic of Games & Puzzles)

Contents

Good Places to Start
Readings Online
Related Web Sites
Related Pages
More Readings

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

News of the Week: Computer Science - Program Proves That Checkers, Perfectly Played, Is a No-Win Situation. By Adrian Cho. Science (July 20, 2007; Vol. 317. no. 5836, pp. 308 - 309 | DOI: 10.1126/science.317.5836.308a). "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[:]"

Checkers Is Solved. By Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen. Science (4 September 2007: Vol. 317. no. 5844, pp. 1518 - 1522).
- Abstract: "The game of checkers has roughly 500 billion billion possible positions (5 x 1020). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: Perfect play by both sides leads to a draw. This is the most challenging popular game to be solved to date, roughly one million times as complex as Connect Four. Artificial intelligence technology has been used to generate strong heuristic-based game-playing programs, such as Deep Blue for chess. Solving a game takes this to the next level by replacing the heuristics with perfection."
Also see:
- Checkmate for checkers - Computer program is unbeatable at English draughts. By Tom Geller. news @ nature.com (July 19, 2007). "Long-time world checkers champion Marion Tinsley consistently bested all comers, losing only nine games in the 40 years following his 1954 crowning. He lost his world championship title to a computer program in 1994 and now that same program has become unbeatable; its creators have proved that even a perfectly played game against it will end in a draw. Jonathan Schaeffer and his team at the University of Alberta, Canada, have been working on their program, called Chinook, since 1989.... The results were announced today in the journal Science [fn]. The paper and supporting materials, including the ability to play Chinook, are available on the web at http://www.cs.ualberta.ca/~chinook. Jaap van den Herik, editor of the International Computer Games Journal, calls the achievement 'a truly significant advance in artificial intelligence'. ... Schaeffer notes that his research has implications beyond the checkers board. The same algorithms his team writes to solve games could be helpful in searching other databases, such as vast lists of biological information because, as he says, 'At the core, they both reduce to the same fundamental problem: large, compressed data sets that have to be accessed quickly.'"
- Checkers computer becomes invincible. By Bryn Nelson. MSNBC.com (July 19, 2007). "The new achievement, led by the University of Alberta’s Jonathan Schaeffer, has been likened by other scientists to scaling Mount Everest. More tangibly, the work could ramp up artificial intelligence and parallel computing know-how and lessen the load for other programs trying to sift through vast DNA databases or produce machine-assisted language translations. Michael Littman, a professor of computer science at Rutgers University in Piscataway, N.J., said Schaeffer’s checkers program had succeeded in 'not just taking on the best human being, but taking on the game itself.' ... Schaeffer isn’t resting on his laurels, however. Next week, the computer scientist and his colleagues will bring a poker-playing computer program dubbed Polaris to Vancouver, Canada, to challenge two professional players in a $50,000 world championship as part of the annual conference for the Association for the Advancement of Artificial Intelligence."
- Alberta researchers crack checkers code. By Joseph Hall. TheStar.com (July 19, 2007). "The game of checkers has been crowned. After 18 and a half years of work - running as many as 200 computers at a time - University of Alberta scientists have developed a program that can win or draw every single time it plays the ancient board game. The achievement - which represents the 'perfect' mastery of a computer over the most complex game yet - was reported Thursday in the academic journal Science. 'This is a huge advance on the state of the (artificial intelligence) art,' says Jonathan Schaeffer, head of the Edmonton school’s computer science department and lead study author. “... But why spend all that time and artificial intelligence on … well…checkers? “If you asked my wife she’d give you a different answer than me,” says Schaeffer, 50. 'But I guess there’s a technical story here and a personal story here.' ... "
- Computers crack famous board game. BBC News (July 19, 2007). "It could be a case of game over for draughts - scientists say the ancient board game has finally been solved. A Canadian team has created a computer program that can win or draw any game, no matter who the opponent is."
- Computers Solve Checkers -- It's a Draw King me! Top computer scientist proves perfect play leads to draw, recounts battle for world championship, gets kinged. By JR Minkel. Scientific American (July 19, 2007). "So what game will fall to computers next? Schaeffer and colleagues speculate it will be Othello, an eight-by-eight disk-flipping game. Chess presents a far mightier challenge, but researchers are 'in the realm of thinking about' solving it, Herik says, which he calls 'a tremendous achievement.' The great white whale of games remains the Asian pastime Go."
- Canadian software "solves" checkers: it can't lose. By Randolph E. Schmid. The Associated Press / available from The Seattle Times / also available from USATODAY.com (July 19, 2007). "'Clearly ... the world is not going to be revolutionized' by this, said Jonathan Schaeffer, chairman of the department of computing science at the University of Alberta. The important thing is the approach, he said. In the past, game-playing programs have used rules of thumb -- which are right most of the time, he said -- to make decisions. 'What we've done is show that you can take nontrivial problems, very large problems, and you can do the same kind of reasoning with perfection. There is no error in the Chinook result. ... Every decision point is 100 percent.'"
- Checkers 'solved' after years of number crunching. By Justin Mullins. NewScientist.com news (July 19, 2007). "The ancient game of checkers (or draughts) has been pronounced dead. The game was killed by the publication of a mathematical proof showing that draughts always results in a draw when neither player makes a mistake. For computer-game aficionados, the game is now 'solved'."
- Computer Checkers Program Is Invincible. By Kenneth Chang. The New York Times (July 19, 2007). "For an exercise in futility, go play checkers against a computer program named Chinook."
- Checkers Solved: It's a Draw. By Larry O'Hanlon. Discovery News (July 19, 2007). "What do you call a game with 500,000,000,000,000,000,000 possible play positions? Checkers, of course. That's according to computer scientists who have succeeded in 'solving' the well-known game for every possible smart move."
- The Next Jump in Artificial Intelligence - Computer program is unbeatable at checkers. By Brittany Grayson. Discover (July 19, 2007). "An unanticipated benefit of Chinook is that it helps checkers players, who have started bringing their puzzles and arguments to Schaeffer to solve. In one case, Chinook settled a dispute that was almost two centuries old. In 1800, an article in a checkers journal presented a particular checkers situation...."
- Cracking the draughts code. Reuters / available from smh,com.au (July 20, 2007). "The team at the University of Alberta said they had 'solved' draughts, the 5000-year-old popular board game also known as chequers (or checkers)."
- It took nearly 2 decades, but computer is king of checkers - Researchers hope breakthrough can lead to bigger discoveries in other fields By Robert Mitchum. chicagotribune.com (July 20, 2007). "As opposed to previous applications like Deep Blue, the program's searches save time by testing only the most relevant moves from the enormous number of possible board combinations. 'We built a huge database and had to compress it into something that was manageable, and could be accessed and searched fast by people,' Schaeffer said. 'That core infrastructure that we developed is generic enough for other applications.' ... [A]rtificial intelligence researchers are developing smarter programs that can be generalized to master multiple games. Whereas the checkers programmers had to invent tricks to efficiently search their huge database of information, general game players, or GGPs, are programs designed to come up with such strategies themselves. 'We're trying to get the intelligence of programmers and put that into a computer,' [Michael] Genesereth said. 'The programs have to figure out for themselves how to deal with very different situations.'"
- Computer program takes draughts crown - Chinook unbeatable after creator's 18 years of work - Achievement a big step for artificial intelligence. By Ian Sample. The Guardian (July 20, 2007). "The game of draughts, played on a board with eight by eight squares, is the most complicated game ever solved thanks to artificial intelligence. ... Peter Cowling, a computer scientist at Bradford University, said: 'This program could play draughts against God and it would get a draw. But if Deep Blue played chess against God it would lose badly because there's so much it doesn't understand.' ... Given that there are 500 billion billion possible arrangements of draughts on a board, the proof took extraordinary computing skill, said Professor Cowling. ... Dr [Jonathan] Schaefer said the effort had taken its toll. 'It's been 18 years and my patience has been tried. I was pretty naive in the beginning and didn't think it was going to take so long, but once I'd got it going I was determined to finish it. But this is the end. Life is too short to spend this much time on one thing.'"
- Endgame - U of A prof has solved the game of checkers, designing a computer program that can't be beat. By Keith Gerein. The Edmonton Journal (July 20, 2007). "Checkers is the largest non-trivial game of skill to be solved, about a million times more complex than the previous leader, Connect Four."
- Alberta professor crowns ultimate checkers king. By Katherine Harding, with a report from Erin Anderssen. globeandmail.com (July 20, 2007). "[T]his spring - more precisely, on April 29 at 6:03 p.m. - the computer stopped. It popped out a single word: Draw. Prof. [Jonathan] Schaeffer and his team had solved checkers.... Prof. Schaeffer said people often consider the game - which uses 12 red and black pieces called checkers - simple because it is easy to learn the rules. 'It took me less than a minute to teach it to my daughter,' he said. 'But just because the rules of checkers are simple does not mean it's a simple game. It's a beautiful game with incredibly deep strategy.' He said their research is a major breakthrough in the field of artificial intelligence and that computer scientists have often used popular games such as chess and checkers as an experimental test bed because the 'characteristics of intelligent behaviour are fundamental in those games.'"
- And watch this Canadian Press (CP) video report available from globeandmail.com (July 19, 2007).
... and this interview: 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. By Kate Lunau. Macleans.ca (July 20, 2007). "Macleans.ca: Why do you think this story’s generated so much interest? Jonathan Schaeffer: I’m not sure - you tell me! I ... M: Now that you’ve shown a perfect game will always end in a draw, do you think that will hurt the popularity of checkers? JS: It won’t kill the game. Look, I like to play chess. I learned chess as a kid and I was a serious, competitive person. But I’m realistic enough. I know that around the world, let’s say there are 100,000 players that are better than me. But I still play chess for the intellectual challenge, the beauty of the game, the social contacts, the friends that I’ve made, and the competitive spirit. When Deep Blue came along, all I did was shrug my shoulders and say, “Now instead of 100,000 chess players out there that are better than me, there are 100,001. Who cares?” When it comes to checkers it’s no different. No checkers player who’s playing for the love of the game is going to be dissuaded just because there happens to be a computer program out there that’s perfect. M: What does all this mean, besides the fact that we now know a perfect game of checkers will end in a draw? ..."

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 scroll further down IT Conversations 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, and Martin Bryant. AI Magazine 17(1): Spring 1996, 21-29. "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, Robert Lake. AI Magazine 14(2): Summer 1993, 28-35."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."

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.

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!

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!