Computers crack famous board game

[4me2]

Computers crack famous board game

Draughts has about 500 billion billion potential positions

It could be a case of game over for draughts - scientists say the ancient board game has finally been solved.
A Canadian team has created a computer program that can win or draw any game, no matter who the opponent is.
It took an average of 50 computers nearly two decades to sift through the 500 billion billion possible draughts positions to come up with the solution.
Writing in the journal Science, the team said it was the most challenging game solved to date.
Jonathan Schaeffer, lead author on the paper and chair of the department of computer science at the University of Alberta, Canada, told the BBC News website: "This was a huge computational problem to solve - more than a million times bigger than anything that had ever been solved before."
Trial and error
Professor Schaeffer, who admits he is "awful" at draughts (also known as checkers), began his attempts to solve the board game in 1989.
He consulted champion players to find out more about their game tactics and then fed this information into a computer program called Chinook.
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


Professor Schaeffer


Chinook looked at solving problems much like a human does by using trial and error to find out what appeared to be the best solutions. This is called a heuristic approach.
However, Professor Schaeffer said that although the program was extremely successful - it won the World Checkers Championship in 1994 - it was not perfect and occasionally lost games.
So the computer scientists tried another non-heuristic tack, for which, over a number of years, hundreds of computers ran through game upon game of draughts to work out the sequences that would lead to winning, losing and drawing.
Eventually, the new program gathered so much information that it "knew" the best move to play in every situation. This meant that every game it played led to a certain win, or, if its opponent played perfectly, a draw.
Chess may prove more tricky to solve


Professor Schaeffer said: "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."
With the vast number of playing possibilities, draughts is the most complex game to have been solved to date - it was about a million times more complicated to solve than Connect Four. Researchers are now hoping to move on to even bigger problems. However, it seems that grand master of the board games - chess - may remain unsolved for some time. It has somewhere in the range of a billion billion billion billion billion possible positions, meaning that computers, with their current capacity, would takes aeons to solve it.

http://news.bbc.co.uk/1/hi/sci/tech/6907018.stm

[Ganty]

Wow. Now I'd like them to do the same for Go

[Welsh Pete]

Wow. Now I'd like them to do the same for Go

Aint gonna happen matey

Have you played Go? I do from time to time, in fact I have a rther nice set and it is such a challenging game with such a simple concept...love it!

[maverick_15]

It can't play Kerplunk though...

[Over Carl]

Why can't they develop something to solve actual real life problems. I'm not impressed till they develop a computer that can pay my bills

[Ganty]

Aint gonna happen matey

Have you played Go? I do from time to time, in fact I have a rther nice set and it is such a challenging game with such a simple concept...love it!

No I've never played, something I'm keen to do though

I've got a lovely Greek chess set but that's about it

[grint]

Would this be a wrong time to set up a DF chess tournament? (via flash\email)?

[Welsh Pete]

No I've never played, something I'm keen to do though

I've got a lovely Greek chess set but that's about it

I`ve a set similar to the premier set:

http://www.mastersgames.com/cat/board/go-sets.htm

although my stones come in grey resin pots, as opposed to wood, and my board isnt as thick as the one featured. I also have a small roll up mat somewhere.

Got into Go about 10 years ago when a student and played it religiously with a pagan pisshead of an art student mate...oh the hours wasted. I keep meaning to teach wifey but I just play strategies on my own most of the time, use computer go ( http://www.smart-games.com/igowin.html ) once in a while and also play with mates when I have a chance.

I`m not very good at chess though