"Long before it's in the papers"
August 03, 2010

RETURN TO THE WORLD SCIENCE HOME PAGE

Computers can play “perfect” checkers game

July 23, 2007
Courtesy Science
and World Science staff

Com­put­ers have played eve­ry pos­si­ble check­ers move and solved the game once and for all, prov­ing that a per­fect­ly played game ends in a draw, sci­ent­ists say.

Sci­en­tists have put on­line a reduced-strength ver­sion of a per­fect com­put­er check­ers play­er, in or­der to give hu­man play­ers "a chance" at a draw. The game is he­re.

Such a feat has­n’t been ac­com­plished for the more com­plex game of chess, al­though com­put­ers can ri­val most of the best play­ers at that game.

Com­put­er sci­en­tists use games as test cases for re­search in ar­ti­fi­cial in­tel­li­gence. In the new proj­ect, Jon­a­than Scha­ef­fer and col­leagues at the Un­ivers­ity of Al­ber­ta in Ed­mon­ton, Can­a­da, found that in check­ers, if black moves first, and both sides play per­fect­ly, the game ends in a draw. 

To reach this con­clu­sion, doz­ens of com­put­ers have been play­ing the game with state-of-the-art ar­ti­fi­cial in­tel­li­gence tech­niques al­most con­tin­u­ously since 1989, ac­cord­ing to Scha­ef­fer and col­leagues. 

Check­ers has about 500 bil­lion pos­si­ble po­si­tions and is the most chal­leng­ing pop­u­lar game that com­put­ers have solved to date, Scha­ef­fer’s team said. The find­ings ap­peared in the July 19 early on­line is­sue of the re­search jour­nal Sci­ence.

Games with a small “search space,” or num­ber of pos­si­ble moves, can be com­pletely solved with com­put­ers by ex­am­in­ing eve­ry pos­si­ble set of moves from a giv­en start­ing po­si­tion. Re­search­ers won’t try to con­quer chess yet since it has an im­mense search space that would re­quire the fastest com­put­ers eons to solve, ac­cord­ing to the sci­en­tists.

* * *

Send us a comment on this story, or send it to a friend

 

Sign up for
e-newsletter
   
 
subscribe
 cancel

On Home Page         

LATEST

  • F­ungus-treat­ed vio­lin beats St­rad in bli­nd te­st

  • Show­er­heads may spray ger­ms in your fa­ce

EXCLUSIVES

  • Re­port: cells “from space” have un­usual make­up

  • Dol­phins and the evo­lution of teach­ing

  • D­rug may tri­ck body into “think­ing” you ex­ercised

  • Tit-for-tat: bi­rds found to re­pay war­­time help

  • Musi­cal genes may be com­ing to light

MORE NEWS

  • R­ock-hurl­ing zoo chimp stock­ed am­mo in ad­vance: study

  • Fai­th found to re­duce er­rors on psycho­logical test

  • Dood­ling gets its due: ti­ny art­works may aid mem­ory

  • From or­al to mor­al? Dirty deeds may prompt “bad taste” reac­tion

Computers have played every possible checkers move and solved the game once and for all, creating a computer that plays an unbeatable game, researchers report. Such a feat hasn’t been accomplished for the more complex game of chess, although computers can rival most of the best players at that game. Computer scientists use games as test cases for research in artificial intelligence. In the new project, Jonathan Schaeffer and colleagues at the University of Alberta in Edmonton, Canada, found that in checkers, if black moves first, and both sides play perfectly, the game ends in a draw. To reach this conclusion, dozens of computers have been playing the game with state-of-the- art artificial intelligence techniques almost continuously since 1989, according to Schaeffer and colleagues. Checkers has about 500 billion possible positions and is the most challenging popular game that computers have solved to date, Schaeffer’s team said. The findings appeared in the July 19 early online issue of the research journal Science. Games with a small “search space,” or number of possible moves, can be completely solved with computers by examining every possible set of moves from a given starting position. Researchers won’t try to conquer chess yet since it has an immense search space that would require the fastest computers eons to solve, according to the scientists.