Checkers

Home * Games * Checkers

Checkers board

Checkers, also American Checkers or English draughts, is a variant of Draughts played on an eight by eight board using 32 either dark or light squares. Like Chess, Checkers is a two-player zero-sum and perfect information abstract strategy board game.

Rules

Each side starts with twelve checkers, placed on the three back-ranks. Black moves first, alternating with White - there is no passing move. Checkers move one step diagonally forward, kings diagonally forward and backward. When a checker reaches the last rank, it promotes to a king. Checkers and king capture men by jumping over them to an empty square behind (checkers only forward). Captures are compulsory, one must play a capture if at least one is available, and is required to continue jumping and capturing as part of the same turn. However, a checker reaching the last row must stop to be crowned and can move no further on that turn . The side run out of moves loses.

Computer Olympiads

• 1st Computer Olympiad, London 1989
• 2nd Computer Olympiad, London 1990

Solving Checkers

In 2007, the Chinook team around Jonathan Schaeffer declared Checkers solved .

Programs

The first Checkers program was written by Christopher Strachey, National Research Development Corporation, London, in the early 1950s to run on a Pilot ACE at the National Physical Laboratory, exhausting its memory , and soon ported to the Ferranti Mark 1 . His checkers program from 1966 written in CPL is available on-line, in a corrected version with courtesy of Peter Norvig . The second program was written in 1956 by Arthur Samuel :

American checkers

• Cake by Martin Fierz
• Checker! by Gil Dodgen
• Checker Hustler by Derek Oldbury
• Checkermate by Derek Oldbury and Adrian Millett
• Checkers from AI Factory
• Chinook by Jonathan Schaeffer et al.
• Colossus Draughts by Martin Bryant
• The Duke program by Eric Jensen, Tom Truscott and Alan Biermann
• KingsRow by Ed Gilbert
• Nemesis by Murray Cash
• Sage Draughts by Adrian Millett
• Tournament Checkers by David Butler
• Wyllie by Roberto Waldteufel

Classical checkers

• Profound by Alvaro Cardoso
• Windamas by Jean-Bernard Alemanni

See also

• Draughts

Selected Publications

1952 ...

• Christopher Strachey (1952). Logical or non-mathematical Programs. Proceedings of the ACM Conference, Toronto, reprinted in David Levy (ed.) (1988). Computer Games I.
• Arthur Samuel (1959). Some Studies in Machine Learning Using the Game of Checkers. IBM Journal July 1959, reprinted in David Levy (ed.) (1988). Computer Games I.

1960 ...

• Arnold K. Griffith (1966). A new Machine-Learning Technique applied to the Game of Checkers. MIT, Project MAC, MAC-M-293
• Christopher Strachey (1966). System Analysis and Programming. Scientific American, September 1966, re-published August 23, 2011
• Arthur Samuel (1967). Some Studies in Machine Learning. Using the Game of Checkers. II-Recent Progress. pdf

1970 ...

• Arnold K. Griffith (1974). A Comparison and Evaluation of Three Machine Learning Procedures as Applied to the Game of Checkers. Artificial Intelligence, Vol. 5, No. 2
• Aviezri Fraenkel, Michael R. Garey, David S. Johnson, Thomas J. Schaefer, Yaacov Yesha (1978). The Complexity of Checkers on an N * N Board. FOCS 1978
• Tom Truscott (1978). Computer-Checkers. Personal Computing, Vol. 2, No. 9, pp. 86
• Editor (1979). Computer Checkers. Personal Computing, Vol. 3, No. 2, pp. 73
• Editor (1979). Computer Checkers. Personal Computing, Vol. 3, No. 4, pp. 70
• Editor (1979). Computer Checkers - A Checkers Program. Personal Computing, Vol. 3, No. 5, pp. 60
• Editor (1979). Computer Checkers - The Tinsely Challange. Personal Computing, Vol. 3, No. 7, pp. 88

1980 ...

• Editor (1980). A Checkers Debate. Personal Computing, Vol. 4, No. 5, pp. 83 » Martin Gardner

1990 ...

• Jonathan Schaeffer (1991). Checkers, a Preview of what will Happen in Chess? ICCA Journal, Vol. 14, No. 2
• Jonathan Schaeffer, Joe Culberson, Norman Treloar, Brent Knight, Paul Lu, Duane Szafron (1991). Checkers Program to Challenge for World Championship. SIGART Bulletin, Vol. 2, No. 2
• Jonathan Schaeffer, Joe Culberson, Norman Treloar, Brent Knight, Paul Lu, Duane Szafron (1991). Reviving the Game of Checkers. Heuristic Programming in AI 2
• Jonathan Schaeffer, Norman Treloar, Paul Lu, Rob Lake (1993). Man Versus Machine for the World Checkers Championship. AI Magazine, Vol. 14, No. 2 » WCCC 1992 - Workshop

Jonathan Schaeffer, Norman Treloar, Paul Lu, Rob Lake (1993). Man Versus Machine for the World Checkers Championship. ICCA Journal, Vol. 16, No. 2

1995 ...

• Jonathan Schaeffer, Rob Lake (1996). Solving the Game of Checkers. Games of No Chance edited by Richard J. Nowakowski, pdf
• J. Ignacio Giráldez, Daniel Borrajo (1998). Distributed Decision Making in Checkers. CG 1998
• Kumar Chellapilla, David B. Fogel (1999). Evolving Neural Networks to Play Checkers without Expert Knowledge. IEEE Transactions on Neural Networks, Vol. 10, No. 6, pp. 1382-1391.

2000 ...

• Kumar Chellapilla, David B. Fogel (2001). Evolving an Expert Checkers Playing Program without Using Human Expertise. IEEE Transactions on Evolutionary Computation, Vol. 5, No. 4, pp.422-428
• Jonathan Schaeffer (2001). Technology Transfer from One High-Performance Search Engine to Another. ICGA Journal, Vol. 24, No. 3
• David B. Fogel (2002). Blondie24: Playing at the Edge of AI. Morgan Kaufmann Publishers, Inc., San Francisco, CA. ISBN 1-55860-783-8, amazon.com
• Jonathan Schaeffer, Yngvi Björnsson, Neil Burch, Rob Lake, Paul Lu, Steve Sutphen (2003). Building the Checkers 10-Piece Endgame Databases. Advances in Computer Games 10. pdf » Endgame Tablebases
• Ed Trice, Gil Dodgen (2003). The Perfect 7-Piece Checkers Database. ICGA Journal, Vol. 26, No. 4 » Endgame Tablebases

2005 ...

• Jonathan Schaeffer, Yngvi Björnsson, Neil Burch, Akihiro Kishimoto, Martin Müller, Rob Lake, Paul Lu, Steve Sutphen (2005). Solving Checkers. IJCAI 2005
• Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Rob Lake, Paul Lu, Steve Sutphen (2007). Checkers is Solved. Science, Vol. 317, no. 5844
• Magdalena Kusiak, Karol Walędzik, Jacek Mańdziuk (2007). Evolutionary Approach to the Game of Checkers. 8. ICANNGA, pdf
• Jonathan Schaeffer (1997, 2009). One Jump Ahead Challenging Human Supremacy in Checkers. Springer, ISBN 0-387-94930-5, ISBN 978-0-387-76575-4
• Belal Al-Khateeb, Graham Kendall (2009). Introducing a round robin tournament into Blondie24. CIG 2009

2010 ...

• Karol Walędzik, Jacek Mańdziuk (2010). The Layered Learning method and its Application to Generation of Evaluation Functions for the Game of Checkers. 11. PPSN, pdf
• João Guerra (2011). Classical Checkers. Masters thesis, Technical University of Lisbon, pdf
• Aart Bik (2012). Computing Deep Perft and Divide Numbers for Checkers. ICGA Journal, Vol. 35, No. 4 » Perft
• Belal Al-Khateeb, Graham Kendall (2012). Effect of Look-Ahead Depth in Evolutionary Checkers. Journal of Computer Science and Technology, Vol. 27, No. 5
• Danilo Carvalho, Minh Le Nguyen, Hiroyuki Iida (2017). An Analysis of Majority Voting in Homogeneous Groups for Checkers: Understanding Group Performance through Unbalance. Advances in Computer Games 15, ResearchGate

Forum Posts

1990 ...

• A taste of things to come? by Jonathan Schaeffer, rgc, September 01, 1990
• Checkers match by Murray Campbell, rgc, August 20, 1992
• Man vs. Machine World Checkers Championship (day 5) by Robert Lake, rgc, August 21, 1992
• Tinsley vs. Chinook? by Robert Williams, rgc, August 16, 1994
• Silicon Graphics World Checkers Championship by Robert Lake, rgc, August 16, 1994
• Silicon Graphics World Checkers Championship - day 3 by Jonathan Schaeffer, rgc, August 18, 1994
• Checkers Championship - additional information by Jonathan Schaeffer, rgc, August 20, 1994
• PDN - Portable Draughts Notation by Pc Sol, rgc, July 22, 1995

2000 ...

• perft for 8x8 checkers by Aart Bik, CCC, May 08, 2009 » Perft

2010 ...

• WinBoard, exotic version by Harm Geert Muller, CCC, January 15, 2011 » WinBoard
• UCT surprise for checkers ! by Daniel Shawul, CCC, March 25, 2011
• Checkers Is Strongly-Solved for 8-pieces by Ed Trice, CCC, February 12, 2017
• Checkers Bitboard representation by Pranav Deshpande, CCC, July 02, 2017 » Bitboards

External Links

• Checkers (English draughts) from Wikipedia
• The Checker Maven
• The American Checker Federation - Welcome to the ACF website
• Checkers (ICGA Tournaments)
• AITopics / Checkers
• Chinook - World Man-Machine Checkers Champion
• A brief history of computer checkers by Martin Fierz
• Marion Tinsley from Wikipedia
• 2002 World Computer Championship
• Las Vegas computer checker championship by Martin Fierz
• 500 billion billion moves later, computers solve checkers from ChessBase news, July 19, 2007
• CheckerBoard by Martin Fierz
• CheckerBoard, A blog on checkers programming by Martin Fierz
• Portable Draughts Notation from Wikipedia
• Checker Bitboards Tutorial by Jonathan Kreuzer
• Gui Checkers 1.05 by Jonathan Kreuzer
• Perft for Checkers by Martin Fierz
• Deep Perft for Checkers by Aart Bik » Perft
• Welcome to the checkers programs page by Jean-Bernard Alemanni
• How Checkers Was Solved by Alexis C. Madrigal, The Atlantic - World Edition, July 19, 2017

References

Up one Level