quote:CHICAGO — With uniform pieces and diagonal moves, checkers is simple enough for a child to learn. But to achieve absolute mastery of the game, scientists needed to run hundreds of computers for nearly 20 years, analyzing roughly 500 billion billion scenarios.
By completing the project, a team of Canadian researchers have officially "solved" checkers, creating an unbeatable program that will choose the best move in every possible situation.
This achievement represents a major benchmark in the field of artificial intelligence, which uses games to develop complex problem-solving strategies for computers. ...
quote: The entire solution includes 500,995,484,682,338,672,639 possible board configurations, according to the study, which was funded by the Canadian and Alberta governments.
posted
So that's what they're up to in Canada. I suppose now that that's all settled they'll turn to conquering the world now.
Posts: 959 | Registered: Oct 2005
| IP: Logged |
quote:The resulting program proves that checkers is a "draw" game; in other words, perfect play by both players will always result in a draw.
That can be said about any game, can't it?
quote: The entire solution includes 500,995,484,682,338,672,639 possible board configurations, according to the study, which was funded by the Canadian and Alberta governments.
So what they're basically hinting at is that, for each possible board combination, they have a predetermined move? It implies theoretically infinite depth analysis, all the way to the game conclusion; that can't be adequately done in real time.
"How about a nice game of chess?"
Posts: 3486 | Registered: Sep 2002
| IP: Logged |
posted
NH: no, it can't. There are some games that lead to a definite winner, given perfect play by both.
And you're right, it can't be done in real time. That's why they precomputed all moves necessary to determine the correct move at any point in time. Given they managed to reduce the problem space so much, I assume they have an algorithm to force uncomputed sequences to converge to the solved space (and proven to work at doing so).
Apparently professional checkers matches start with three random moves, and they claim to have solved many of the previously unconsidered cases generated by those as well (and be well on the way to solving the rest).
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
posted
At least we don't have to worry about the Matrix until computers can win at Go. If checkers and chess is the best the computers can do, it wouldn't be a very realistic dystopia.
Posts: 3950 | Registered: Mar 2006
| IP: Logged |
quote:The resulting program proves that checkers is a "draw" game; in other words, perfect play by both players will always result in a draw.
That can be said about any game, can't it?
No. There are many games that can be shown to be a win for one player or the other. Nim, for example.
Posts: 10645 | Registered: Jul 2004
| IP: Logged |
Printer-friendly view of this topic
