Jump to content

English draughts

From Wikipedia, the free encyclopedia
(Redirected from Computer checkers)
English draughts
A standard American Checker Federation (ACF) set: smooth red and white 1.25-inch (32 mm) diameter pieces; green and buff 2-inch (51 mm) squares
Genres
Players2
Playing timeCasual games usually last 10 to 30 minutes
ChanceNone
SkillsStrategy, tactics
Synonyms
  • American checkers
  • straight checkers
  • checkers (or chequers)
  • draughts (or drafts)

English draughts (British English) or checkers (American English), also called straight checkers or simply draughts,[note 1] is a form of the strategy board game checkers (or draughts). It is played on an 8×8 checkerboard with 12 pieces per side. The pieces move and capture diagonally forward, until they reach the opposite end of the board, when they are crowned and can thereafter move and capture both backward and forward.

As in all forms of draughts, English draughts is played by two opponents, alternating turns on opposite sides of the board. The pieces are traditionally black, red, or white. Enemy pieces are captured by jumping over them.

The 8×8 variant of draughts was weakly solved in 2007 by a team of Canadian computer scientists led by Jonathan Schaeffer. From the standard starting position, both players can guarantee a draw with perfect play.

Pieces

[edit]

Though pieces are traditionally made of wood, now many are made of plastic, though other materials may be used. Pieces are typically flat and cylindrical. They are invariably split into one darker and one lighter colour. Traditionally and in tournaments, these colours are red and white, but black and red are common in the United States, as well as dark- and light-stained wooden pieces. The darker-coloured side is commonly referred to as "Black"; the lighter-coloured side, "White".

There are two classes of pieces: men and kings. Men are single pieces. Kings consist of two men of the same colour, stacked one on top of the other. The bottom piece is referred to as crowned. Some sets have pieces with a crown molded, engraved or painted on one side, allowing the player to simply turn the piece over or to place the crown-side up on the crowned man, further differentiating kings from men. Pieces are often manufactured with indentations to aid stacking.

Rules

[edit]

Starting position

[edit]
The starting setup; Red moves first.

Each player starts with 12 men on the dark squares of the three rows closest to that player's side (see diagram). The row closest to each player is called the kings row or crownhead. The player with the darker-coloured pieces moves first. Then turns alternate.

Move rules

[edit]

There are two different ways to move in English draughts:

  1. Simple move: A simple move consists of moving a piece one square diagonally to an adjacent unoccupied dark square. Uncrowned pieces can move diagonally forward only; kings can move in any diagonal direction.
  2. Jump: A jump consists of moving a piece that is diagonally adjacent an opponent's piece, to an empty square immediately beyond it in the same direction (thus "jumping over" the opponent's piece front and back ). Men can jump diagonally forward only; kings can jump in any diagonal direction. A jumped piece is considered "captured" and removed from the game. Any piece, king or man, can jump a king.

Jumping is always mandatory: if a player has the option to jump, they must take it, even if doing so results in disadvantage for the jumping player. For example, a mandated single jump might set up the player such that the opponent has a multi-jump in reply.

Multiple jumps are possible, if after one jump, another piece is immediately eligible to be jumped by the moved piece—even if that jump is in a different diagonal direction. If more than one multi-jump is available, the player can choose which piece to jump with, and which sequence of jumps to make. The sequence chosen is not required to be the one that maximizes the number of jumps in the turn; however, a player must make all available jumps in the sequence chosen.

Kings

[edit]

If a man moves into the kings row on the opponent's side of the board, it is crowned as a king and gains the ability to move both forward and backward. If a man moves into the kings row or if it jumps into the kings row, the current move terminates; the piece is crowned as a king but cannot jump back out as in a multi-jump until the next move.

End of game

[edit]

A player wins by capturing all of the opponent's pieces or by leaving the opponent with no legal move. The game is a draw if neither side can force a win, or by agreement (one side offering a draw, the other accepting).

Shortest possible game

[edit]

The December 1977 issue of the English Draughts Association Journal published a letter from Alan Beckerson of London who had discovered a number of complete games of twenty moves in length. These were the shortest games ever discovered and gained Alan a place in the Guinness Book of Records. He offered a £100 prize to anybody who could discover a complete game in less than twenty moves. In February 2003, Martin Bryant (author of the Colossus draughts program) published a paper on his website[1] presenting an exhaustive analysis showing that there exist 247 games of twenty moves in length (and confirmed that this is the shortest possible game) leading (by transposition) to 32 distinct final positions.

Rule variations

[edit]
Within the permanent collection of The Children's Museum of Indianapolis
  • In tournament English draughts, a variation called three-move restriction is preferred. The first three moves are drawn at random from a set of accepted openings. Two games are played with the chosen opening, each player having a turn at either side. This tends to reduce the number of draws and can make for more exciting matches. Three-move restriction has been played in the U.S. championship since 1934. A two-move restriction was used from 1900 until 1934 in the United States and in the British Isles until the 1950s. Before 1900, championships were played without restriction, a style is called Go As You Please (GAYP).
  • One rule which has fallen out of favor is the huffing rule. In this variation jumping is not mandatory, but if a player does not make a jumping move when there is one available to them (either deliberately or by failing to see it), the opponent may declare that the piece that could have made the jump is blown or huffed, i.e. removed from the board. After huffing the offending piece, the opponent then takes their turn as normal.[2] Huffing does not appear in the official rules of the World Checkers Draughts Federation, of which the American Checker Federation and English Draughts Association are members.[3][4]
  • Two common rule variants, not recognised by player associations, are:
  1. Capturing with a king precedes capturing with a man. In this case, any available capture can be made at the player's choice.
  2. A man that has jumped to become a king can then in the same turn continue to capture other pieces in a multi-jump.

Notation

[edit]
Squares are identified by numbers 1–32. In draughts diagrams, the Black side is typically shown at the top. In printed diagrams, dark and light squares are often reversed for legibility.

There is a standardised notation for recording games. All 32 reachable board squares are numbered in sequence. The numbering starts in Black's double-corner (where Black has two adjacent squares). Black's squares on the first rank are numbered 1 to 4; the next rank 5 to 8, and so on. Moves are recorded as "from-to", so a move from 9 to 14 would be recorded 9-14. Captures are notated with an "x" connecting the start and end squares. The game result is often abbreviated as BW/RW (Black/Red wins) or WW (White wins).

Sample game

[edit]

White resigned after Black's 46th move.

[Event "1981 World Championship Match, Game #37"]
[Black "M. Tinsley"]
[White "A. Long"]
[Result "1–0"]
1. 9-14 23-18 2. 14x23 27x18 3. 5-9 26-23 4. 12-16 30-26 5. 16-19 24x15 6. 10x19 23x16 7. 11x20 22-17 8. 7-11 18-15 9. 11x18 28-24 10. 20x27 32x5 11. 8-11 26-23 12. 4-8 25-22 13. 11-15 17-13 14. 8-11 21-17 15. 11-16 23-18 16. 15-19 17-14 17. 19-24 14-10 18. 6x15 18x11 19. 24-28 22-17 20. 28-32 17-14 21. 32-28 31-27 22. 16-19 27-24 23. 19-23 24-20 24. 23-26 29-25 25. 26-30 25-21 26. 30-26 14-9 27. 26-23 20-16 28. 23-18 16-12 29. 18-14 11-8 30. 28-24 8-4 31. 24-19 4-8 32. 19-16 9-6 33. 1x10 5-1 34. 10-15 1-6 35. 2x9 13x6 36. 16-11 8-4 37. 15-18 6-1 38. 18-22 1-6 39. 22-26 6-1 40. 26-30 1-6 41. 30-26 6-1 42. 26-22 1-6 43. 22-18 6-1 44. 14-9 1-5 45. 9-6 21-17 46. 18-22 BW

Unicode

[edit]

In Unicode, the draughts are encoded in block Miscellaneous Symbols:

  • U+26C0 WHITE DRAUGHTS MAN
  • U+26C1 WHITE DRAUGHTS KING
  • U+26C2 BLACK DRAUGHTS MAN
  • U+26C3 BLACK DRAUGHTS KING

Sport

[edit]

The men's World Championship in English draughts dates to the 1840s, predating the men's Draughts World Championship, the championship for men in International draughts, by several decades. Noted world champions include Andrew Anderson, James Wyllie, Robert Martins, Robert D. Yates, James Ferrie, Alfred Jordan, Newell W. Banks, Robert Stewart, Asa Long, Walter Hellman, Marion Tinsley, Derek Oldbury, Ron King, Michele Borghetti, Alex Moiseyev, Lubabalo Kondlo,[5] Sergio Scarpetta, Patricia Breen, and Amangul Durdyyeva.[6] Championships are held in GAYP (Go As You Please) and 3-Move versions.

From 1840 to 1994, the men's winners were from Scotland, England, and the United States. From 1994 to 2023, the men's winners were from the United States, Barbados, South Africa and Italy.

The woman's championship started in 1993. As of 2022, the women's winners have been from Ireland, Turkmenistan, and Ukraine.

The European Cup has been held since 2013; the World Cup, since 2015.

Computer players

[edit]

The first English draughts computer program was written by Christopher Strachey, M.A. at the National Physical Laboratory (NPL), London.[7] Strachey finished the programme, written in his spare time, in February 1951. It ran for the first time on the NPL's Pilot ACE computer on 30 July 1951. He soon modified the programme to run on the Manchester Mark 1 computer.

The second computer program was written in 1956 by Arthur Samuel, a researcher from IBM. Other than it being one of the most complicated game playing programs written at the time, it is also well known for being one of the first adaptive programs. It learned by playing games against modified versions of itself, with the victorious versions surviving. Samuel's program was far from mastering the game, although one win against a blind checkers master gave the general public the impression that it was very good.

Scott M Savage's checkers, 1983, the first robot game

In November 1983, the Science Museum Oklahoma (then called the Omniplex) unveiled a new exhibit: Lefty the Checker Playing Robot. Programmed by Scott M Savage, Lefty used an Armdroid robotic arm by Colne Robotics and was powered by a 6502 processor with a combination of BASIC and Assembly code to interactively play a round of checkers with visitors. Originally, the program was deliberately simple so that the average visitor could potentially win, but over time was improved. The improvements proved to be frustrating for the visitors, so the original code was reimplemented.[8]

In the 1990s, the strongest program was Chinook, written in 1989 by a team from the University of Alberta led by Jonathan Schaeffer. Marion Tinsley, world champion from 1955–1962 and from 1975–1991, won a match against the machine in 1992. In 1994, Tinsley had to resign in the middle of an even match for health reasons; he died shortly thereafter. In 1995, Chinook defended its man-machine title against Don Lafferty in a thirty-two game match. The final score was 1–0 with 31 draws for Chinook over Don Lafferty.[9] In 1996 Chinook won in the U.S. National Tournament by the widest margin ever, and was retired from play after that event. The man-machine title has not been contested since.

In July 2007, in an article published in Science Magazine, Chinook's developers announced that the program had been improved to the point where it could not lose a game.[10] If no mistakes were made by either player, the game would always end in a draw. After eighteen years, they have computationally proven a weak solution to the game of checkers.[11] Using between two hundred desktop computers at the peak of the project and around fifty later on, the team made 1014 calculations to search from the initial position to a database of positions with at most ten pieces.[12] However, the solution is only for the initial position rather than for all 156 accepted random 3-move openings of tournament play.

Computational complexity

[edit]

The number of possible positions in English draughts is 500,995,484,682,338,672,639[13] and it has a game-tree complexity of approximately 1040.[14] By comparison, chess is estimated to have between 1043 and 1050 legal positions.

When draughts is generalized so that it can be played on an m×n board, the problem of determining if the first player has a win in a given position is EXPTIME-complete.

The July 2007 announcement by Chinook's team stating that the game had been solved must be understood in the sense that, with perfect play on both sides, the game will always finish with a draw. However, not all positions that could result from imperfect play have been analysed.[15]

Some top draughts programs are Chinook, and KingsRow.

See also

[edit]

Notes

[edit]
  1. ^ When this word is used in the UK, it is usually spelt chequers (as in Chinese chequers); see further at American and British spelling differences.

References

[edit]
  1. ^ "Colossus Games". Colossus Games. 9 September 2021.
  2. ^ Cady, Alice Howard (1896). Checkers: A Treatise on the Game. New York: American Sports Publishing Company. p. 15. ISBN 1340551446.
  3. ^ "Rules of Draughts (Checkers)". World Checkers Draughts Federation. 2012.
  4. ^ "Federation-Members". World Checkers Draughts Federation. 1 December 2019.
  5. ^ "PE's Lubabalo Kondlo crowned world draughts champion". YouTube.
  6. ^ WCDF champions list
  7. ^ The Proceedings of the Association for Computing Machinery Meeting, Toronto, 1952.
  8. ^ "But Can It Type". The Daily Oklahoman. The Daily Oklahoman. 25 November 1983. p. 51. Retrieved 26 March 2022.
  9. ^ "Man vs. Machine World Championship: Petal, Mississippi, January 7–17, 1995". Chinook.
  10. ^ Chang, Kenneth (July 19, 2007). "Computer Checkers Program Is Invincible". The New York Times.
  11. ^ Schmid, Randolph E (July 19, 2007). "Computer can't lose checkers". USA Today.
  12. ^ "Checkers 'solved' after years of number crunching". New Scientist. July 19, 2007. Archived from the original on December 14, 2007.
  13. ^ "Chinook - Total Number of Positions". webdocs.cs.ualberta.ca. Retrieved 2017-11-18.
  14. ^ Schaeffer, Jonathan (2007). "Game over: Black to play and draw in checkers". ICGA Journal. 30 (4): 187–197. CiteSeerX 10.1.1.154.255. doi:10.3233/ICG-2007-30402.
  15. ^ Schaeffer, Jonathan (14 September 2007). "Checkers Is Solved". Science. 317 (5844): 1518–1522. Bibcode:2007Sci...317.1518S. doi:10.1126/science.1144079. PMID 17641166. S2CID 10274228.
[edit]