English draughts - AbsoluteAstronomy.com

English draughts or checkers (American English

American English

American English is a set of dialects of the English language used mostly in the United States. Approximately two-thirds of the world's native speakers of English live in the United States....

and Canadian English

Canadian English

Canadian English is the variety of English spoken in Canada. English is the first language, or "mother tongue", of approximately 24 million Canadians , and more than 28 million are fluent in the language...

), also called American checkers or straight checkers or in Israel damka, is a form of draughts

Draughts

Draughts is a group of abstract strategy board games between two players which involve diagonal moves of uniform pieces and mandatory captures by jumping over the enemy's pieces. Draughts developed from alquerque...

board game

Board game

A board game is a game which involves counters or pieces being moved on a pre-marked surface or "board", according to a set of rules. Games may be based on pure strategy, chance or a mixture of the two, and usually have a goal which a player aims to achieve...

. Unlike international draughts

International draughts

International draughts is a board game, one of the variants of draughts. It is played on a 10×10 board with alternatingly dark and light squares, of which only the 50 dark ones are used. There are two players on opposite sides, with 20 pieces each, light for one player and dark for the other...

, it is played on an eight by eight squared board (with sixty-four total squares) with twelve pieces on each side. The pieces move and capture diagonally. They may only move forward until they reach the opposite end of the board, when they are "crowned" or "kinged" and may henceforth move and capture both backward and forward.

As in all draughts variants, English draughts is played by two people, on opposite sides of a playing board, alternating moves. Traditionally the pieces are either black, red, or white. The opponent's pieces are captured by jumping over them.

Game play

Pieces - Though pieces were traditionally made of wood
Wood
Wood is a hard, fibrous tissue found in many trees. It has been used for hundreds of thousands of years for both fuel and as a construction material. It is an organic material, a natural composite of cellulose fibers embedded in a matrix of lignin which resists compression...

, now many are made of plastic
Plastic
A plastic material is any of a wide range of synthetic or semi-synthetic organic solids used in the manufacture of industrial products. Plastics are typically polymers of high molecular mass, and may contain other substances to improve performance and/or reduce production costs...

, though other materials may be used. Pieces are typically flat and cylindrical
Cylinder
Cylinder most commonly refers to:* Cylinder , a three-dimensional geometric shapeCylinder may also refer to:-Science and technology:* Cylinder , the space in which a piston travels in an engine...

. They are invariably split into one darker and one lighter colour. Traditionally, these colours are white and red, but black and red are common in the United States, and light- and dark-stained wood are supplied with more expensive sets. There are two classes of pieces: "men" and "kings". Kings are differentiated as consisting of two normal pieces of the same colour, stacked one on top of the other. Often indentations are added to the pieces to aid stacking.
Starting position - Each player starts with twelve pieces on the dark spaces of the three rows closest to that persons own side (as shown in the diagram). The row closest to each player is called the "crownhead" or "kings row". The player with the darker coloured pieces moves first.
How to move - There are two ways to move a piece:
- A simple move involves sliding a piece one space diagonally forwards to an adjacent unoccupied dark square.
- A jump is a move from a square diagonally adjacent to one of the opponent's pieces to an empty square immediately and directly on the opposite side of the opponent's square, thus "jumping directly over" the square containing the opponent's piece. An uncrowned piece may only jump diagonally forwards, kings may jump diagonally backwards. A piece that is jumped is captured and removed from the board. Multiple-jump moves are possible if when the jumping piece lands, there is another immediate piece that can be jumped; even if the jump is in a different direction. Jumping is mandatory - whenever a player has the option to jump, that person must jump (even if it's to the jumping player's disadvantage). When multiple-option jumping moves are available, whether with the one piece in different directions or multiple pieces that can make various jumping moves, the player may choose which piece to jump with and which jumping option or sequence of jumps to make. The jumping sequence chosen does not necessarily have to be the one that would have resulted in the most captures; however, one must make all available captures in the chosen sequence. Any piece, whether it is a king or not, can jump a king.
Kings - If a player's piece moves into the kings row on the opposing player's side of the board, that piece is said to be "crowned" (or often "kinged" in the U.S.), becoming a "king" and gaining the ability to move both forwards and backwards. If a player's piece jumps into the kings row, the current move terminates; having just been crowned, the piece cannot continue on by jumping back out (as in a multiple jump), until the next move. A piece is normally "crowned" by placing a second piece on top of it; 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 piece, further differentiating Kings from ordinary pieces.
How the game ends - A player wins by capturing all of the opposing player's pieces or by leaving the opposing player with no legal moves. The game ends in a draw, if neither side can force a win.

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

Tie (draw)

To tie or draw is to finish a competition with identical or inconclusive results. The word "tie" is usually used in North America for sports such as American football. "Draw" is usually used in the United Kingdom, Ireland and the Commonwealth of Nations and it is usually used for sports such as...

and can make for more exciting matches. Three-move restriction has been played in the United States 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: this style is called go-as-you-please (GAYP).

One rule of long standing that has fallen out of favour is the "huffing

Huff (board games)

Huffing is a rule used in some board games, such as Alquerque and traditional and informal English draughts . By this rule, a player who fails to make a capturing move when one is available is penalised by having the piece huffed, i.e...

" rule. In this variation jumping is not mandatory, but if a player does not take their jump (either deliberately or by failing to see it), 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. Huffing has been abolished by both the American Checker Federation and the English Draughts Association.

Two common misinterpretations of the rules are:

That capturing with a king precedes capturing with a regular piece. (In such a case, any available capture can be made at the player's choice.)
A piece which in the current move has become a king can then in the same move go on to capture other pieces (see under Kings, above).

Notation

For recording games, there is a standardised notation. All 32 reachable positions of the board are numbered in sequence. The numbering starts in black's double-corner. The blacks squares on the first rank are numbered 1 to 4, (in algebraic chess notation

Algebraic chess notation

Algebraic notation is a method for recording and describing the moves in a game of chess. It is now standard among all chess organizations and most books, magazines, and newspapers...

those being g1, e1, c1, a1. The next rank starts 5 to 8 (h2, f2, d2, b2) and so on. Moves are recorded as from-to, so a move from 9 to 14 would be 9-14. Captures are notated with an x connecting the start and end square. The result is often abbreviated as BW/RW (Black/Red wins) or WW (White wins)
A sample game. White resigned after blacks 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

Computer players

The first computer

Computer

A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...

English draughts program

Computer program

A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...

was written by Christopher Strachey

Christopher Strachey

Christopher Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design...

, M.A. at the National Physical Laboratory, London. Strachey finished the programme, written in his spare time, in February 1951. It ran for the first time on NPL's Pilot ACE

Pilot ACE

The Pilot ACE was one of the first computers built in the United Kingdom, at the National Physical Laboratory in the early 1950s.It was a preliminary version of the full ACE, which had been designed by Alan Turing. After Turing left NPL , James H...

on 30 July 1951. He soon modified the programme to run on the Manchester Mark 1

Manchester Mark 1

The Manchester Mark 1 was one of the earliest stored-program computers, developed at the Victoria University of Manchester from the Small-Scale Experimental Machine or "Baby" . It was also called the Manchester Automatic Digital Machine, or MADM...

.

The second computer programme was written in 1956 by Arthur Samuel

Arthur Samuel

Arthur Lee Samuel was an American pioneer in the field of computer gaming and artificial intelligence. The Samuel Checkers-playing Program appears to be the world's first self-learning program, and as such a very early demonstration of the fundamental concept of artificial intelligence...

, a researcher from IBM

IBM

International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...

. Other than it being one of the most complicated game playing programmes written at the time, it is also well known for being one of the first adaptive programmes. It learned by playing games against modified versions of itself, with the victorious versions surviving. Samuel's programme 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.

In the 1990s, the strongest programme was Chinook

Chinook (draughts player)

Chinook is a computer program that plays English draughts , developed around 1989 at the University of Alberta, led by Jonathan Schaeffer. Other developers are Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar. In July 2007, Chinook's developers announced that the program has been improved to...

, written in 1989 by a team from the University of Alberta

University of Alberta

The University of Alberta is a public research university located in Edmonton, Alberta, Canada. Founded in 1908 by Alexander Cameron Rutherford, the first premier of Alberta and Henry Marshall Tory, its first president, it is widely recognized as one of the best universities in Canada...

led by Jonathan Schaeffer

Jonathan Schaeffer

Jonathan Herbert Schaeffer is a Canadian researcher and professor at the University of Alberta and the Canada Research Chair in Artificial Intelligence....

. Marion Tinsley

Marion Tinsley

Marion Tinsley is considered the greatest checkers player who ever lived. He was world champion from 1955–1958 and 1975–1991. Tinsley never lost a World Championship match, and lost only seven games in his entire 45 year career...

, 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

Don Lafferty

Don Lafferty was a Grandmaster checkers player. In 1982 he defeated Derek Oldbury for the World GAYP championship with a score of 1-0-23. He was challenged for the championship in 1984 by Paul Davis, winning easily 5-0-15...

in a thirty-two game match. The final score was 1-0 with 31 draws for Chinook over Don Lafferty. In 1996 Chinook won in the USA 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
Science (journal)
Science is the academic journal of the American Association for the Advancement of Science and is one of the world's top scientific journals....

, Chinook's developers announced that the programme had been improved to the point where it could not lose a game. 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. Using between two hundred desktop computers at the peak of the project and around fifty later on, the team made just 10¹⁴ calculations to search from the initial position to a database of positions with at most ten pieces.

Computational complexity

The number of legal positions in English draughts is estimated to be 10²⁰, and it has a game-tree complexity of approximately 10³¹. By comparison, chess is estimated to have between 10⁴³ and 10⁵⁰ legal positions.

When draughts is generalized

Generalized game

In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. For example, generalized chess is the game of chess played on an n-by-n board, with 2n pieces on each side.Complexity theory studies the asymptotic difficulty...

so that it can be played on an n-by-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

Chinook (draughts player)

'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. Yet, not all positions that could result from imperfect play have been analyzed.

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Game play

Notation

Computer players

Computational complexity

See also

External links