9 replies to this topic

[chubtoad]

The game of checkers has finally been solved.
http://www.nature.co.../070716-13.html
It is sort of interesting that the game is a draw rather than a player 1 win.

[JohnDoe1234]

Yup... The problems are solvable... we just need time to figure out how to harness the full capability of the hardware and languages we've developed.

I love seeing things like this, thanks for the post.

[Live Forever]

I'm surprised checkers is just now being solved. It seems like a pretty simple game. (especially compared to chess and Go and stuff)

[JohnDoe1234]

Kinda struck me as odd too, but oh well

[chubtoad]

Really not that simple compared to other games that are not solved. For example 6x6 dots and boxes is still unsolved. 10^20 is by no means a small number even by today's computational standards. The game is still not even close to being solvable by exaustive search; it was solved with lots of cleverness.

[Live Forever]

I guess I am just overoptimistic with this kind of stuff. )

I had just assumed that as good as computers are at chess nowadays that they were close to "solving" chess, but that is so much more complicated than checkers.

[Live Forever]

The solving of checkers was mentioned in the latest episode of Bloggingheads for anyone interested:
http://bloggingheads...id=350&cid=2042
They mention some of the work gong into solving the game of poker as well.

[jaydfox]

I guess I am just overoptimistic with this kind of stuff. )

I had just assumed that as good as computers are at chess nowadays that they were close to "solving" chess, but that is so much more complicated than checkers.

Yeah, we're still a long way off from solving chess, though we've long since passed the point where computers can beat the best humans.

The game of Go promises to hold out at least another decade, possibly two or three. I had originally thought Go would hold out against brute force, requiring lazy AI programmers to actually bother to program a modicum of artificial intelligence into their contestants. However, some bad news on that front: a Chinese researcher thinks that, with a few optimizations, a brute force system will be able to beat a world-class Go player in a decade or so.

Edit: link: http://slashdot.org/...7/10/10/1758244

Don't get me wrong, I think it's important to show that computers can perform these kinds of feats. But it's hardly more than a glorified calculator if it's simply using brute force. For me, Go is an excellent playground for AI research, and it'd be a shame for it to succumb to brute force methods (since, after all, an AGI is not going to rely on brute force methods alone, if at all).

Perhaps what we need is a renaissance in game AI, using limited computer power to focus researchers on AI design rather than brute force optimization techniques. For example, writing a chess program that can beat a chess champion, using a Pentium II 233 Mhz with 256 MB of RAM. Maybe that's not possible, but it'd certainly take the emphasis off mere brute force. Even if we allowed more modern computer, e.g. circa 2004, it's probably a lot less computing power than was available to the Deep Blue chess computer (or whatever it was called).

And if we should see a Go program beat a Go champion in the next 15 years, I'd like to see research continue into repeating the feat with a tenth the hardware, a hundredth, a thousandth!

[treonsverdery]

Item

Edited by treonsverdery, 29 November 2007 - 03:14 AM.