Computer Scientists Solve Checkers

[Demosthenes]

A team of computer scientists and top-level checkers players have "solved" the game of checkers. Using various heuristics, and on an average of 50 computers a day, the team went through 500,000,000,000,000,000,000 different checkers positions, and has now developed a computer which plays "perfect" checkers. It can not lose. If you play perfectly as well, you can play to a draw. The project is called Chinook, and it has been an ongoing project since 1989.

For more information (and to play) see:
http://www.cs.ualberta.ca/~chinook/
http://en.wikipedia.org/wiki/Chinook_%28draughts_player%29

[Vollstrecker]

I always hated how simple that game was anyway, Chess is far superior imo.

[Demosthenes]

I agree. Although I don't think it's too far fetched to think that one day Chess may be "solved" as well.

[Vollstrecker]

I'd hate to see the code for that.

[Demosthenes]

I'd hate to see the code for that.

I doubt the code is all that complex. My guess is once they work out every position there really doesn't need to be any heuristics, all they need is a shortest path algorithm from the current position to mate.

[Vollstrecker]

Shows how much I know about programming. I think I turned in half my work for my Java class a year ago and managed a 'B' somehow.

[RoboticSilence]

I doubt the code is all that complex. My guess is once they work out every position there really doesn't need to be any heuristics, all they need is a shortest path algorithm from the current position to mate.

This doesn't work because the program has to change its approach as the player does. If you just have shortest-path then it'd be easy to draw against.

[Demosthenes]

This doesn't work because the program has to change its approach as the player does. If you just have shortest-path then it'd be easy to draw against.

That seems to be a very minor complication. You just need to recalculate the shortest path to mate every move your opponent makes, and then play the new shortest path. If your opponent plays perfectly as well, the shortest path should not change. If not, mate should be even simpler. Essentially the idea is still the same. There aren't any heuristic algorithms involved. Unless I'm missing something, here.

[WetWired]

No,no, there is simply a table of all the possible positions which holds the best move to make. There is no continuity. If the best move is already pre-computed, the only requirement is lots of storage.

[D3V]

That's pretty absurd, who would actually go about solving a game like checkers, but in theory I suppose they can apply it to about anything.. pretty interesting somehow, I wish they could show the best moves for each position, somewhat similar to how to solve the Rubix cube ..

[Demosthenes]

No,no, there is simply a table of all the possible positions which holds the best move to make. There is no continuity. If the best move is already pre-computed, the only requirement is lots of storage.

I believe how current endgame databases work is that they store every possible position by the pieces currently on the board. They then calculate the shortest possible path from the current position to mate move by move, because the best move may change in the situation that your opponent doesn't play perfect chess. I don't believe that they have the best move stored for every position, though. I assume that if Chess could be "solved" they would simply extend this principle to all the pieces on the board instead of limiting it to 6 like it is now.

[Vollstrecker]

As I said, I'd hate to see the code for it. :p