!!!

http://news.bbc.co.uk/2/hi/science/nature/6907018.stm

Quote :

"Computers crack famous board game 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, 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, where, 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. 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. "

This is so cool! As for chess, I have read elsewhere that there are 10^125 possible games of chess.

Safe to say it will never be solved.

7/19/2007 4:48:54 PM

never say never



[Edited on July 19, 2007 at 4:57 PM. Reason : doesn't seem that far off]

7/19/2007 4:53:06 PM

^bill gates + the xbox learned this

7/19/2007 4:55:00 PM

A room full of PS3's could probably do it in a few decades.

7/19/2007 4:55:02 PM

rofl, how does the human brain fit on a monetary chart

is that an average worth per person? lol

7/19/2007 6:29:35 PM

what if all the human brains are working for free?

7/19/2007 6:40:54 PM

this stuff gets me giddy

http://us.penguingroup.com/static/packages/us/kurzweil/excerpts/chap6/chap6.htm

Quote :

"The human brain has about 100 billion neurons. With an estimated average of one thousand connections between each neuron and its neighbors, we have about 100 trillion connections, each capable of a simultaneous calculation. That's rather massive parallel processing, and one key to the strength of human thinking. A profound weakness, however, is the excruciatingly slow speed of neural circuitry, only 200 calculations per second. For problems that benefit from massive parallelism, such as neural-net-based pattern recognition, the human brain does a great job. For problems that require extensive sequential thinking, the human brain is only mediocre. With 100 trillion connections, each computing at 200 calculations per second, we get 20 million billion calculations per second. This is a conservatively high estimate; other estimates are lower by one to three orders of magnitude. So when will we see the computing speed of the human brain in your personal computer? The answer depends on the type of computer we are trying to build. The most relevant is a massively parallel neural net computer. In 1997, $2,000 of neural computer chips using only modest parallel processing could perform around 2 billion connection calculations per second. Since neural net emulations benefit from both strands of the acceleration of computational power, this capacity will double every twelve months. Thus by the year 2020, it will have doubled about twenty-three times, resulting in a speed of about 20 million billion neural connection calculations per second, which is equal to the human brain. If we apply the same analysis to an "ordinary" personal computer, we get the year 2025 to achieve human brain capacity in a $1,000 device.2 This is because the general-purpose type of computations that a conventional personal computer is designed for are inherently more expensive than the simpler, highly repetitive neural-connection calculations. Thus I believe that the 2020 estimate is more accurate because by 2020, most of the computations performed in our computers will be of the neural-connection type. The memory capacity of the human brain is about 100 trillion synapse strengths (neurotransmitter concentrations at interneuronal connections), which we can estimate at about a million billion bits. In 1998, a billion bits of RAM (128 megabytes) cost about $200. The capacity of memory circuits has been doubling every eighteen months. Thus by the year 2023, a million billion bits will cost about $1,000.3 However, this silicon equivalent will run more than a billion times faster than the human brain. There are techniques for trading off memory for speed, so we can effectively match human memory for $1,000 sooner than 2023. Taking all of this into consideration, it is reasonable to estimate that a $1,000 personal computer will match the computing speed and capacity of the human brain by around the year 2020, particularly for the neuron-connection calculation, which appears to comprise the bulk of the computation in the human brain. Supercomputers are one thousand to ten thousand times faster than personal computers. As this book is being written, IBM is building a supercomputer based on the design of Deep Blue, its silicon chess champion, capable of 10 teraflops (that is, 10 trillion calculations per second), only 2,000 times slower than the human brain. Japan's Nippon Electric Company hopes to beat that with a 32-teraflop machine. IBM then hopes to follow that with 100 teraflops by around the year 2004 (just what Moore's Law predicts, by the way). Supercomputers will reach the 20 million billion calculations per second capacity of the human brain around 2010, a decade earlier than personal computers.4 In another approach, projects such as Sun Microsystems' Jini program have been initiated to harvest the unused computation on the Internet. Note that at any particular moment, the significant majority of the computers on the Internet are not being used. Even those that are being used are not being used to capacity (for example, typing text uses less than one percent of a typical notebook computer's computing capacity). Under the Internet computation harvesting proposals, cooperating sites would load special software that would enable a virtual massively parallel computer to be created out of the computers on the network. Each user would still have priority over his or her own machine, but in the background, a significant fraction of the millions of computers on the Internet would be harvested into one or more supercomputers. The amount of unused computation on the Internet today exceeds the computational capacity of the human brain, so we already have available in at least one form the hardware side of human intelligence. And with the continuation of the Law of Accelerating Returns, this availability will become increasingly ubiquitous. After human capacity in a $1,000 personal computer is achieved around the year 2020, our thinking machines will improve the cost performance of their computing by a factor of two every twelve months. That means that the capacity of computing will double ten times every decade, which is a factor of one thousand (210) every ten years. So your personal computer will be able to simulate the brain power of a small village by the year 2030, the entire population of the United States by 2048, and a trillion human brains by 2060.5 If we estimate the human Earth population at 10 billion persons, one penny's worth of computing circa 2099 will have a billion times greater computing capacity than all humans on Earth.6 Of course I may be off by a year or two. But computers in the twenty-first century will not be wanting for computing capacity or memory. "

7/19/2007 6:51:01 PM

Quote :

"Safe to say it will never be solved."

safe to say if you think that, you're an idiot.

7/19/2007 7:18:26 PM

^^ aha, i mean i wouldnt say it would be solved anytime in the next year, but never? yeah right, probably in 5-10 years easily... and certainly in the next 50

Quote :

"The memory capacity of the human brain is about 100 trillion synapse strengths (neurotransmitter concentrations at interneuronal connections), which we can estimate at about a million billion bits. In 1998, a billion bits of RAM (128 megabytes) cost about $200. The capacity of memory circuits has been doubling every eighteen months. Thus by the year 2023, a million billion bits will cost about $1,000.3 However, this silicon equivalent will run more than a billion times faster than the human brain. There are techniques for trading off memory for speed, so we can effectively match human memory for $1,000 sooner than 2023."

i think their assumptions on 'measuring' human memory are a bit off tho....

[Edited on July 20, 2007 at 10:24 AM. Reason : s]

7/20/2007 10:21:22 AM

Quote :

"rofl, how does the human brain fit on a monetary chart is that an average worth per person? lol/quote] the money indicates the cost to build a computer of the given brain level. look up ray kurzweil http://www.kurzweilai.net/articles/art0134.html?printable=1 [quote] My estimate of brain capacity is 100 billion neurons times an average 1,000 connections per neuron (with the calculations taking place primarily in the connections) times 200 calculations per second. Although these estimates are conservatively high, one can find higher and lower estimates. However, even much higher (or lower) estimates by orders of magnitude only shift the prediction by a relatively small number of years. Some prominent dates from this analysis include the following: * We achieve one Human Brain capability (2 * 10^16 cps) for $1,000 around the year 2023. * We achieve one Human Brain capability (2 * 10^16 cps) for one cent around the year 2037. * We achieve one Human Race capability (2 * 10^26 cps) for $1,000 around the year 2049. * We achieve one Human Race capability (2 * 10^26 cps) for one cent around the year 2059. "

[Edited on July 20, 2007 at 12:36 PM. Reason : .]

7/20/2007 12:34:41 PM

get back to us when you've solved Go

7/20/2007 1:20:12 PM

I said what I said based on the estimate of 10^120 for the possible number of chess games.

OK, see these:

http://en.wikipedia.org/wiki/Shannon_number
http://mathworld.wolfram.com/Chess.html

Calculations and estimates by different scientists range from 10^43 to 10^123.

Of course, if you take 10^43, it will be solved in the next 50-70 years as per the charts in this thread.

If you take 10^123, it is safe to say it will probably never be solved (i.e., not in the next millenium). The number of atoms in the universe is about 10^80.

And from the mathworld link above, one dude estimates the number of games to be 10^(10^50), which is just

Quote :

"probably in 5-10 years easily"

IMPOSSIBLE in the next 5-10 years. Chess is at least 10^22 times more complex than checkers. (in terms of number of possible positions)

THINK about that, and then look at "probably in 5-10 years easily" to see if that makes sense.

[Edited on July 20, 2007 at 5:25 PM. Reason : ]

7/20/2007 4:56:01 PM

well. in fairness, they didn't test EVERY move of checkers, they used some logic to discount completely illogical moves. (or at least i'm pretty sure that's what i read about it in an article yesterday). so they could probably apply that same sort of logic to chess and knock that total number of games down considerably.

[Edited on July 20, 2007 at 5:28 PM. Reason : .]

7/20/2007 5:27:56 PM

Imagine this:

Suppose today's top parallel processing supercomputer can solve the game of checkers in 1 millisecond.

Such a computer would take AT LEAST 10^22 milliseconds to solve the game of chess.

Now:

10^22 ms ~ 600 billion years


And if we take the upper estimate of 10^123 possible games of chess, a computer which can solve checkers in 1 ms would take:

10^102 ms = 6 x 10^91 years


That's an unfathomable amount of time. Even if some computer could solve checkers in 1 nanosecond, we still get the following upper and lower bounds for that computer solving chess:

LOWER: 600,000 years
UPPER: 6 x 10^85 years


And yes, I know that technology is not static. So, if at some time in the future, a computer could solve checkers in 1 ms, a few years after that, the top machine could do it in, say, 0.1 ms.

But at the same time, some people have a hard time imagining powers of 10.

So even 600,000 years is a damn long time, and even if you reduce it by a factor of thousand, i.e., some computer being able to solve checkers in 1 picosecond, for chess you still get 600 years. And remember, this is the lower estimate. If we look at the upper estimate based on 10^123 games, yes, it will NEVER be solved.

**********************************************************

^ Not only that, but what they are really going to do to try to cut down the search space is limit themesleves, to say, a game lasting 40 moves. Because theoretically a game of chess could last infinite moves.

If they limit it to 40 moves (which I think is the typical game among masters), we will see the solution in a couple of centuries, at the very earliest.

7/20/2007 5:43:32 PM

karl fisch - did you know, shift happens

http://www.youtube.com/watch?v=ljbI-363A2Q

7/20/2007 5:48:15 PM

Quote :

"If you take 10^123, it is safe to say it will probably never be solved (i.e., not in the next millenium)."

Wait, people that are experts in the field have a hard time estimating computing growth over the next 15 years and you're willing to put limits on what will happen over the next 993? You really are retarded.

It's hard for the average person to comprehend the amount of growth that has occurred over the last 30 years of computing. It's practically unfathomable by nearly everyone what will happen over the course of the next 20 years. Quantum computing (or some other major innovation that hasn't even been thought of) could, and most likely will make Moore's law a joke. It's very possible that something like Chess will be solved in the next 20 years, within our lifetime isn't a stretch, And most definitely within the next 100 years.

And you say never? What part of never do you not understand?

7/20/2007 8:04:52 PM

searching for bobby fischer

7/20/2007 9:04:08 PM

^^ agreed, Chess will easily be solved within 100 years, and 20 years doesn't seem too farfetched.

7/20/2007 10:58:58 PM

I say 20 years for chess, 100 or 200 for Go

7/20/2007 11:10:23 PM

9x9 go? Go scales, you can just increase the board size.

7/21/2007 8:39:20 PM

my right ear started bleeding

7/21/2007 9:46:53 PM

Quote :

"Wait, people that are experts in the field have a hard time estimating computing growth over the next 15 years "

Quote :

"And most definitely within the next 100 years. "

I see what you did there...

7/21/2007 9:47:15 PM

Quote :

"Thus I believe that the 2020 estimate is more accurate because by 2020, most of the computations performed in our computers will be of the neural-connection type."

invalidates qntmfred's entire article

i'm sure we're going to completely rearchitect all our OSes and software suites in 13 years


Also, Trapezius, your analysis is very good, but you're leaving out some highly crucial shit: quantum computing. that could knock your 600 year estimate right down to 6 years

[Edited on July 22, 2007 at 8:40 AM. Reason : s]

7/22/2007 8:35:17 AM

Is there an echo in here?

7/22/2007 9:15:23 AM

^^^ i know, right? he tells me i am no expert and calls me retarded, and then uses "definitely" in his own assessment.

^^ yes, you are right about quantum computing. it might actually reduce computation time to just a few years or decades, but i don't think quantum computing will be used for something as "trivial" as figuring out chess for a long time after quantum computing becomes available. they will use it for weather, oil, medicine, space, etc, until it becomes cheap enough that some prof/researcher somewhere convinces his employer to spend considerable amount of money and time figuring out chess!

but yeah, once quantum computing (or biological/DNA computing) actually becomes a working feasible reality (not just in a lab somewhere), then it will just be a matter of time until someone uses it for that purpose.

thanks.

(some people are nice/try to be nice, and deserve responses, some are assholes and should be ignored!)

7/22/2007 1:05:20 PM

Quote :

"Wait, people that are experts in the field have a hard time estimating computing growth over the next 15 years and you're willing to put limits on what will happen over the next 993? You really are retarded. "

Agreed.

With quantum computing actually seeing some serious breakthroughs recently, making claims about what computers can't do in the next 100 years seems kind of silly. Making claims about what computers won't be able to do in the next 1000 years is absolutely moronic. Even the most intelligent thinkers 1000 years ago would be hard pressed to conceive of anything like super computers. The same goes for saying what will definitely be done, but at least those people are thinking positively. Nobody likes nay-sayers.

[Edited on July 22, 2007 at 1:31 PM. Reason : ]

7/22/2007 1:30:07 PM

Quote :

"but i don't think quantum computing will be used for something as "trivial" as figuring out chess for a long time after quantum computing becomes available."

Um, this is how a lot of new technologies are tested. On "trivial" system with defined boundaries. You have to make sure the system works before you move on to highly critical human systems.

And also, almost all of your claims are retarded.

You can't compare solving a game of checkers to solving a game of chess as a multiple of its permutations.

Once the game is mapped, it will only take a marginal amount more time to solve a game. You have a heuristic tree and after each move the computer simple has to branch properly based on the opponents move.

Now MAPPING the solution set may take millenia, but after that it will be trivial to solve. And I still doubt it will take that long. I'd make a bet that chess will be computer solved in our lifetimes. Not because we will have the raw processing power to brute force it like checkers, but because you can rule out large sets of end-game moves from chess and using theoretical heuristics you can lower to real set to a manageable size.

Much in the same way the current computers play now only on a bigger scale.

7/22/2007 1:40:03 PM

Quote :

"I'd make a bet that chess will be computer solved in our lifetimes. Not because we will have the raw processing power to brute force it like checkers, but because you can rule out large sets of end-game moves from chess and using theoretical heuristics you can lower to real set to a manageable size."

OK, that sounds like something that will be done.

But of course, my whole point was that to actually map out ALL possible chess games (or even all possible games of 40 moves) would take a very very long time.

P.S. I mean, what you said WILL surely be done first (by multiple people), just like the checkers guy did on his first try (in article in 1st post), and then one day when enough raw computing power is available, it will be cracked by mapping out the complete tree.


[Edited on July 22, 2007 at 1:47 PM. Reason : ]

7/22/2007 1:45:39 PM

7/22/2007 5:27:44 PM

good thing they didn't put all that computing power to solving something silly like cancer or something and instead focused on issues of importantance

7/22/2007 6:02:04 PM

They would have if they knew how to cure cancer with a computer, dumbass.

7/22/2007 6:27:07 PM

lol

7/22/2007 7:36:29 PM

folding@home assweasel

7/22/2007 7:38:52 PM

It's kind of neat they can make perfect checker playing apps now, but i'm not particularly impressed that a brute-force algorithm brute-forced a problem.

[Edited on July 22, 2007 at 8:49 PM. Reason : checker]

7/22/2007 8:49:38 PM

yeah, it's not the most elegant solution maybe, but still significant in the history of things

7/22/2007 8:54:40 PM

im pretty impressed, checkers is a brute force type of application. It's a very open ended game with a very small set of rules.

now, like some others have said, I want to see the solution to Go. Which there's no way in hell we will see in our lifetimes.

As for the folding@home, it's not searching for the sure for cancer. It's part of the cancer search, but it also has a ton of other applications.

7/22/2007 9:30:54 PM

GO

seriously, I wanted to start on a go engine this summer

I didn't get too far ]

7/23/2007 12:04:42 AM

^ why are you back?

[Edited on July 23, 2007 at 12:11 AM. Reason : btw, i had a dream last night that i found the algorithm to solve Go in a box of cheez-its]

7/23/2007 12:10:26 AM

way to be an asssss

7/23/2007 12:13:10 AM

hmmm, wasn't being a jerk. i just thought you were banished to the hall of infamous egg hunt aliases

[Edited on July 23, 2007 at 12:15 AM. Reason : my burst]

7/23/2007 12:15:24 AM

well, blame goonz

7/23/2007 12:16:40 AM

so, did they derive an elegant algorithm from the brute force method, or does the thing just refer to a giant database of moves?

7/23/2007 8:32:59 AM

What rules of checkers did they use? Like flying kings, have to jump, backjumps allowed, etc...

It would be nice to see the algorithm. I would like to see if they could have knocked a few years off by making a few basic changes to the algorthm...

7/23/2007 9:28:43 AM

Quote :

"get back to us when you've solved Go"

7/23/2007 9:37:22 AM