Canadian researchers at the University of Alberta report that they have ’solved’ the game of checkers, with a computer program, Chinook, that is incapable of losing.

While it should not be surprising to anyone that the game has been mastered by a computer, as they are simply programmed to not make mistakes, the amazing thing should be that when a game is down to the last 10 pieces on the board, 39 trillion possibilities are left.

While humans, and computers up until now, used heuristics to play the game, the researchers have changed the way the computer plays, with a different analysis of the situation, for every one of the 39 trillion possible moves. The research team states confidently that it does not matter what happens in the path from 24 checkers down to 10 on the board. The computer will, at worst, tie in those last moves from 10 to a position of win or draw.

The team also states that because of the computational power required for this brute force method of solution, it will be quite some time before the game of chess is solved this way.

With the computational power available today, it remains remarkable what the human brain can accomplish, as it is capable of the draw situation in checkers,  and the most capable computer is still not able to consistently defeat the best chess players.

Full story

[tags] computer power, checkers, chess, heuristic method, Chinook, University of Alberta, Deep Blue, brute force methodology [/tags]