So the BBC informs me that computers have now “solved” the game of checkers such that their program can play every game to a win or a draw. Cool. How did they do it? Well, basically, they did it the way I would have done it if I were faced with said problem: try every possible combination of moves. But, because ‘brute force’ doesn’t sound as nice as ‘non-heuristic approach,’ you can guess what the researchers called it. One of the head researchers is quoted as saying:
“I think we’ve raised the bar – and raised it quite a bit – in terms of what can be achieved in computer technology and artificial intelligence.”
Maybe I’m confused on what we’re counting as artificial intelligence these days, but I was under the impression that forcing a computer to check every possible combination of moves did not count. If there were some sort of clever optimization algorithm hiding in there, maybe, but there’s no mention of anything of that nature in the article. Maybe one of you computer-science types can step in and enlighten me? Please?
3 responses to “Checkers and A.I.”
*confused* They told us in 391 that a complete minimax tree for checkers had been done years ago.
Oh, and to answer your question, “heuristic” in computer science-ese is basically a euphemism for “guess because it’s too computationally expensive to actually solve.” If you CAN actually solve the problem, hey, more power to you.
What they’ve done is an established and valid system — why guess if you don’t have to? imagine tic-tac-toe — that obviously produces the best results when you can explore the entire game tree. More complicated games have too large a tree and require you to start guessing, which can be an interesting challenge but is ultimately a sub-optimal solution, from the standpoint of getting the right move.
Personally, I think it’s boring to have the entire tree solved (what’s the fun in playing a computer you can’t beat?), but it is the optimal solution for accuracy. Mostly it’s down to the standard tradeoff of speed vs. correctness. Speed is a more interesting challenge (to me anyway), and usually preferred to exact correctness, but sometimes people want The Right Answer, and that’ll definitely be true in more advanced AI problems.
(From a technical standpoint, there are still challenges. A theoretical computer playing with this tree has to quickly find the optimal move from a position in however-many-billion nodes they said there were, which could be an interesting storage/caching problem for people who like that kind of thing. And of course that reminds me that the whole thing serves as an interesting example of the presolve-and-cache technique that’s sometimes used for big problems, which you have to agree is a good optimization for any problem you’ll have to solve lots of times.)
Hey, they took all the fun out of it.
I guess now they can program checkers AI players with an exactly known difficulty. Say you don’t want to feel entirely stupid: they could populate the decision tree with 50% wins and 50% losses. Say you want a challenge–10% losses, and the challenge isn’t so much playing the game as hunting out the decision tree. Oh, wait, sounds like more fun to a computer than to me…
I’m sorry, Dave. I won. Would you like to play again, Dave?