Computational Complexity
The number of legal positions in English draughts is estimated to be 1020, and it has a game-tree complexity of approximately 1040. 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 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'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.
Read more about this topic: English Draughts
Famous quotes containing the word complexity:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)