Although the famous game looks simple, it turns out that there are 500 billion billion potential positions
Avi Blizovsky, The People editor, DailyMaily
A computer program will be able to beat any person in a game of checkers, according to Canadian researchers who unveiled Chinook this weekend - a unique software that they worked on developing for nearly twenty years. As part of the development, it took 50 computers almost twenty years of computation to mine all 500 billion billions of the possible positions in the game. In an article published in the journal Science, the team members said that this is the most complex game that has been completely solved so far.
Prof. Jonathan Shaffer, head of the computer science department at the University of Alberta in Canada, told the BBC's website that "this was a huge computational problem - a million times bigger than anything computer scientists have tried to solve so far." Prof. Shaffer, who admitted that he was "sick of the game", began trying to solve it in 1989. He consulted with the champions of the game to learn more about their tactics and how to feed that much information into a computer program.
According to him, Chinook used to solve problems similar to humans - through trial and error - in a method known as "heuristic". Prof. Shaffer added that although the software was successful and even won the World Checkers Championship in 1994, it was not perfect and occasionally lost games. Therefore, the computer scientists tried a non-heuristic approach, whereby over several years hundreds of computers would run game after game to find the sequences that would lead to wins, losses and draws. In the end, the new software accumulated so much information that it "knew" what the best move was for almost every situation. This means that every game she plays leads to a sure win or if the opponent is particularly strong - to a draw.
"I believe that we have raised the bar, and at a considerable height in terms of what can be achieved through computer technology and artificial intelligence," said Prof. Shaffer. He concluded by saying that now the researchers hope to solve more difficult games, but the most complex game of all - chess - will still be beyond the reach of scientists with the current method because the range of possibilities is several orders of magnitude larger: billion billion billion billion billion billions of possible positions - something that even at the current strength of computing will take ages to solve, he estimated.
* This news was also published in the Daily Mail of the People and Computers group
5 תגובות
I managed to reach a checker (queen) in front of the computer and then it froze it.
Chess is not the most complicated game, but in second place after the game Go.
Ariel, you are right, the algorithm is really not sophisticated, but we know that the game has no solution (if the second one is good, it leads to a draw) and they have the full situation tree, from which you can learn about other games.
Backgammon has more states and even more (by orders of magnitude), but you can also progress step by step sometimes (unless you have a P algorithm for the NPC problem 😉 )
One who plays too much.
Did they just build the full branching tree that contains all the possibilities for moving the tools during the game? If so it's really not great wisdom and nothing to do with artificial intelligence, just a big database.
The address for the game: http://games.cs.ualberta.ca/~chinook/cgi-bin/chinook.cgi