Checkers solved!

6f0a333c785da81d479a0f58c2ccb203
0
monjardin 102 Jul 19, 2007 at 20:34

Interesting board game AI news:

Chicago Tribune:

“With its uniform pieces and simple moves, checkers may seem like a simple kid’s game. But it took hundreds of computers running continuously for nearly 20 years before researchers announced today that the game has officially been solved, a major benchmark in the development of artificial intelligence….

Now, the programmers behind Chinook have fully solved the game, creating an unbeatable program that will choose the best move in every possible situation.”

Does anyone think chess will ever be “solved” as well?

EDIT: It’s too bad it was solved through brute force.

14 Replies

Please log in or register to post a reply.

6aa952514ff4e5439df1e9e6d337b864
0
roel 101 Jul 19, 2007 at 21:27

I guess chess will ever get solved as well, altough there are very many possible paths trough the game-states, the number is finite, and computer power increases and increases.

6837d514b487de395be51432d9cdd078
0
TheNut 179 Jul 20, 2007 at 00:43

Heh, 20 years ago. What a hundred 386s did in 20 years, a PlayStation 3 could probably solve in real-time ;) I wonder how loud those machines must have been. With those big old turbine fans, crunching hard drives… Hehe, the good old days.

BTW, chess has already been solved. It’s called the fools mate ;)

6f0a333c785da81d479a0f58c2ccb203
0
monjardin 102 Jul 20, 2007 at 02:56

@TheNut

BTW, chess has already been solved. It’s called the fools mate ;)

:lol: The fool’s mate does require a bit of cooperation though.

820ce9018b365a6aeba6e23847f17eda
0
geon 101 Jul 20, 2007 at 09:55

@TheNut

What a hundred 386s did in 20 years (…) I wonder how loud those machines must have been. With those big old turbine fans, crunching hard drives… Hehe, the good old days.

I believe the “20 years” refers to the total computer time. With “hundreds of computers”, that’s about a few weeks, which seems reasonable.

I can’t believe someone would rent a really big server room full of computers and UPS-es for 20 years, just for something like that.

46462f88a1670d7e9cbbfa360aa20134
0
juhnu 101 Jul 20, 2007 at 12:11

How do we define “the best possible”-movement? I guess it depends whether the opponent can see the evolving idea or not, so moves that are less obvious would be better?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jul 20, 2007 at 16:52

@geon

I can’t believe someone would rent a really big server room full of computers and UPS-es for 20 years, just for something like that.

Believe it.

The effort required up to hundreds of computers working since 1989 to analyze all possible board combinations of checkers, roughly 500 billion-billion scenarios.

“Had I known it 18 years ago it was this big of a problem, I probably would’ve done something else,” Schaeffer said. “But once I started, I had to finish.”

6aa952514ff4e5439df1e9e6d337b864
0
roel 101 Jul 20, 2007 at 18:16

Maybe a bit more information: http://www.spectrum.ieee.org/jul07/5379 (he took a break from 1997 to 2001)

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Jul 20, 2007 at 22:56

This is like the world’s most anti computer science project ever, I f**king swear.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jul 21, 2007 at 07:01

What do you mean? It’s a triumph of computer science. The result about checkers may not be all that useful in practice but the techniques and technology (for storing and searching databases of moves) that they developed to solve the problem may well be more broadly applicable.

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Jul 21, 2007 at 09:56

Well, come on, solving a problem with tons of power and memory it a little bit too simple for me. I mean, one could assume there ain’t a logical way to do it, but I personally doupt it. Anyway, it’s solved :)

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jul 21, 2007 at 14:49

If you read the articles, it’s not just brute-forcing. They have to be very careful about trimming unnecessary paths, and were able to discard 99.9% of the state space. That still left several computer-decades worth of time though, the problem is just that huge.

If by a logical way to do it, you mean by a mathematical proof that the game ends in a draw if both sides play perfectly, the scientists did publish a paper proving that fact. They apparently needed to do this computation in order to help figure out the details of the proof; I don’t know exactly why.

46462f88a1670d7e9cbbfa360aa20134
0
juhnu 101 Jul 22, 2007 at 14:40

@Reedbeta

If you read the articles, it’s not just brute-forcing. They have to be very careful about trimming unnecessary paths, and were able to discard 99.9% of the state space. That still left several computer-decades worth of time though, the problem is just that huge. If by a logical way to do it, you mean by a mathematical proof that the game ends in a draw if both sides play perfectly, the scientists did publish a paper proving that fact. They apparently needed to do this computation in order to help figure out the details of the proof; I don’t know exactly why.

Maybe it was a brute-force proof :)

F56b5bbf67ceb306761a1069e6e44d1d
0
Pallav_Nawani 101 Sep 09, 2007 at 09:18

@monjardin

With its uniform pieces and simple moves, checkers may seem like a simple kid’s game. But it took hundreds of computers running continuously for nearly 20 years before researchers announced today that the game has officially been solved, a major benchmark in the development of artificial intelligence….

This has nothing to do with artifical intelligence of course. “Solving” any game does exactly nothing for artificial intelligence. It just indicates that brute computing power, combined with techniques developed specially for that game, has created a calculator which can calculate every move nearly perfectly. Cars have been outrunning us humans for a hundred years now.

571e76cbcc8b9d6f75e758533c3f744f
0
slickmasterizzy 101 Dec 11, 2007 at 23:23

i agree mathamatical equations are not truely AI

if you want to have fun try to make a program that can beat people in the game of go.