Difference between revisions of "Checkers"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Games * Checkers''' FILE:CheckersStandard.jpg|border|right|thumb| Checkers board <ref>[https://en.wikipedia.org/wiki/Checkers Checkers (English...") |
(added link) |
||
Line 123: | Line 123: | ||
* [http://www.3dkingdoms.com/checkers/bitboards.htm Checker Bitboards Tutorial] by [[Jonathan Kreuzer]] | * [http://www.3dkingdoms.com/checkers/bitboards.htm Checker Bitboards Tutorial] by [[Jonathan Kreuzer]] | ||
* [http://www.3dkingdoms.com/checkers.htm Gui Checkers 1.05] by [[Jonathan Kreuzer]] | * [http://www.3dkingdoms.com/checkers.htm Gui Checkers 1.05] by [[Jonathan Kreuzer]] | ||
− | * [http://checker-board.blogspot.com/2009/02/perft-for-checkers.html Perft for Checkers] » [[Perft]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=27814 perft for 8x8 checkers] by [[Aart Bik]], [[CCC]], May 08, 2009</ref> | + | * [http://checker-board.blogspot.com/2009/02/perft-for-checkers.html Perft for Checkers] by [[Martin Fierz]] |
+ | * [http://www.aartbik.com/strategy.php Deep Perft for Checkers] by [[Aart Bik]] » [[Perft]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=27814 perft for 8x8 checkers] by [[Aart Bik]], [[CCC]], May 08, 2009</ref> | ||
* [http://alemanni.pagesperso-orange.fr/index.html Welcome to the checkers programs page] by [[Jean-Bernard Alemanni]] | * [http://alemanni.pagesperso-orange.fr/index.html Welcome to the checkers programs page] by [[Jean-Bernard Alemanni]] | ||
* [https://www.theatlantic.com/technology/archive/2017/07/marion-tinsley-checkers/534111/ How Checkers Was Solved] by [https://www.theatlantic.com/author/alexis-madrigal/ Alexis C. Madrigal], [https://en.wikipedia.org/wiki/The_Atlantic The Atlantic - World Edition], July 19, 2017 | * [https://www.theatlantic.com/technology/archive/2017/07/marion-tinsley-checkers/534111/ How Checkers Was Solved] by [https://www.theatlantic.com/author/alexis-madrigal/ Alexis C. Madrigal], [https://en.wikipedia.org/wiki/The_Atlantic The Atlantic - World Edition], July 19, 2017 |
Revision as of 06:36, 9 January 2019
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.
Contents
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 [2]. The side run out of moves loses.
Computer Olympiads
Solving Checkers
In 2007, the Chinook team around Jonathan Schaeffer declared Checkers solved [3] [4] [5].
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 [6], and soon ported to the Ferranti Mark 1 [7] [8]. His checkers program from 1966 [9] written in CPL is available on-line, in a corrected version with courtesy of Peter Norvig [10] [11]. The second program was written in 1956 by Arthur Samuel [12]:
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. [13]
- 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
See also
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. [14]
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 [15]
- 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 [16]
- 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 [17]
- 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
- ↑ Checkers (English draughts) from Wikipedia
- ↑ Mr. Fred Investments | CheckerMaven / RulesOfCheckers
- ↑ 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 (5844). Work named by Science Magazine as one of the 10 most important scientific achievements of 2007
- ↑ Checkers Is Solved
- ↑ Chinook - Solving Checkers
- ↑ Christopher Strachey from Wikipedia
- ↑ artificial intelligence (AI) :: Early milestones in AI from Britannica Online Encyclopedia
- ↑ Christopher Strachey (1952). Logical or non-mathematical programmes. Proceedings of the 1952 ACM national meeting
- ↑ Christopher Strachey (1966). System Analysis and Programming. Scientific American, September 1966, republished August 23, 2011
- ↑ Complete Annotated Strachey Checkers Program by Peter Norvig
- ↑ Prescient but Not Perfect: A Look Back at a 1966 Scientific American Article on Systems Analysis by Peter Norvig, August 23, 2011
- ↑ English draughts - Computer players from Wikipedia
- ↑ Chinook - Solving Checkers
- ↑ Some studies in machine learning using the game of checkers by Arthur Lee Samuel from Jeremy Norman's Historyofscience.com - Used Book - Paperback - First Edition
- ↑ Marion Tinsley vs. Chinook - Wikipedia
- ↑ Blondie24 by David B. Fogel, Book Review, © Copyright 2003, Jim Loy
- ↑ perft for 8x8 checkers by Aart Bik, CCC, May 08, 2009