English draughts

English draughts, also called American checkers or "straight checkers", commonly called checkers in the U.S., but commonly called draughts in some other countries, is a form of the draughts board game played on an 8×8 board with 12 pieces on each side that may only move and capture forward.

Computational complexity

It is a common misconception that English draughts has been solved. The best computers can now beat all humans, but English draughts is not yet completely solved. It is generally expected that English draughts will be solved by the 2010s.

Related Topics:
Solved - 2010s

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The number of legal positions in English draughts is estimated to be 1018, and it has a game-tree complexity of approximately 1031.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

When draughts is generalized 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.

Related Topics:
Generalized - EXPTIME-complete

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In November 2004, the Chinook team announced that the tournament opening in English draughts called the White Doctor (10-14 22-18 12-16) has proven to be a draw.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~