14 replies to this topic

[monjardin]

Interesting board game AI news:

Chicago Tribune:
[INDENT]"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."[/INDENT]

Does anyone think chess will ever be "solved" as well?

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

[roel]

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.

[TheNut]

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 ;)

[monjardin]

TheNut said:

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

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

[geon]

TheNut said:

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.

[juhnu]

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?

[Reedbeta]

geon said:

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.

Quote

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

Quote

"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."

[roel]

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

[Mihail121]

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

[Reedbeta]

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.

[Mihail121]

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 :)

[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.

[juhnu]

Reedbeta said:

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 :)

[Pallav Nawani]

monjardin said:

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.

[slickmasterizzy]

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.