Check on checkers: in perfect game, there's no winner.
Computers can now play a flawless game of checkers checkers, game for two players, known in England as draughts. It is played on a square board, divided into 64 alternately colored—usually red and black or white and black—square spaces, identical with a chessboard. . A calculation that began almost 2 decades ago shows that if both players make perfect moves, the game will be a draw every time. The achievement makes checkers the most complicated game to have been solved completely.
Computers have been able to beat people at checkers since 1994, when a program called Chinook Chinook, indigenous people of North America
Chinook (shĭnk`, chĭ–), Native American tribe of the Penutian linguistic stock. won the checkers world championship. The program, written by computer scientist Jonathan Schaeffer Jonathan Herbert Schaeffer (born 1957) is a Canadian researcher and professor at the University of Alberta and the Canada Research Chair in Artificial Intelligence. of the University of Alberta in Edmonton, used rules of thumb to guess the best available move, a method that imitates how people play. Now, Schaeffer has removed the guesswork with a program that examined every possible position that can occur on a checkerboard checkerboard
the pattern of a chess or draft board; used in many circumstances to display the results of mixing a specific number of variables. The variables are listed in columns designated along the horizontal border and the same or different variables in lines along the vertical to find the best move every time.
The brute-force calculation underlying o the new program was conceptually simple but logistically demanding, because checkers has approximately 500 billion billion (5 x [10.sup.20]) possible positions. Each player starts with 12 pieces on an 8-by-8 checkerboard, and he or she moves a piece by sliding it forward and diagonally one square. A piece captures an enemy by jumping diagonally across it into an open square. The last player with pieces on the board wins.
Beginning in 1989, Schaeffer used as many as 200 computers simultaneously to grind out the problem. He started with the endgame Endgame
blind and chair-bound, Hamm learns that nearly everybody has died; his own parents are dying in separate trash cans. [Anglo-Fr. Drama: Beckett Endgame in Weiss, 143]
See : Death , putting just two pieces on the board and calculating every possible outcome for each position they might assume. Then he did the same for three pieces, then four, and so on up to 10. At that point, 39 trillion positions were possible.
Each step in this process took 10 times as much work as the previous step, so continuing in this way was impractical. Instead, Schaeffer turned to the beginning of a game, calculating all the positions that could result from one move, then two moves, then three moves, and so on. The program continued the game until there were only 10 pieces left, at which point it checked its database of endgames to find the outcome. Ultimately, the analysis included somewhere between 100 trillion and a quadrillion One thousand times one trillion, which is 1, followed by 15 zeros, or 10 to the 15th power. See space/time. checkers positions. Schaeffer and his colleagues report their results in an upcoming Science.
"We're pushing the frontiers of what computers can solve," Schaeffer says. "If we had waited 10 or 20 years, the Years, The
the seven decades of Eleanor Pargiter’s life. [Br. Lit.: Benét, 1109]
See : Time machines would be faster," making the problem easy. As it was, he and his team had to invent clever ways of storing and searching the data.
For example, they stored the outcomes for the 39 trillion possible positions for endgames in a mere 237 gigabytes of computer-storage space, an average of 154 positions per byte. The mathematicians are now applying these techniques to bioinformatics, looking for Looking for
In the context of general equities, this describing a buy interest in which a dealer is asked to offer stock, often involving a capital commitment. Antithesis of in touch with. ways to manage the massive quantity of data generated by the sequencing of genomes.
"It's just a prodigious amount of work," says Ken Thompson (person) Ken Thompson - The principal inventor of the Unix operating system and author of the B language, the predecessor of C.
In the early days Ken used to hand-cut Unix distribution tapes, often with a note that read "Love, ken". of Mountain View, Calif.-based Google, who in 1983 developed the first master-level chess computer program. Thompson says that solving checkers brings computers a step closer to being able to solve more-complicated games, such as chess or go. However, he estimates that those tasks will take another 100 years to complete. Chess has about 1020 times as many positions as checkers does, Schaeffer says.