News@Nature ran a story about how a group at the University of Alberta, Canada, led by Jonathan Schaeffer, has created a computer program called Chinook that ’solves’ the game of checkers. No matter how good of a game you can play against it, the best that you can ever do is play against it to a draw.
Since 1994, computers have been able to beat the World’s checker champions. But the Chinook program goes to the next level of sophistication by considering every possible board position in the game. Rather than calculate what move to make based on logic that considers the current board position, finding the best move amounts to doing a quick search over their database of moves — that’s over 500 billion billion (5 * 1020) possible positions. Researchers are saying that the approach taken by the researchers takes AI to the next level.
The Chinook program is on-line — you can play against it here. The news@nature article compares the relative complexity of different games, ranging from tic-tac-toe to Go.
How do the ’state-space complexities’ of information management problems rank among these? It’s interesting to think about where the state of technology will be in 2100.
