Author |
Topic: Supercomputer vs Human (Read 1277 times) |
|
pallab
Forum Full Member
Arimaa player #1589
Gender: 
Posts: 19
|
 |
Supercomputer vs Human
« on: Mar 19th, 2008, 9:20pm » |
 Quote  Modify
|
I have a silly question. If one provides best possible hardware available (say like Hydra or Deep blue in chess) will they be able to beat best human players?. I know that Omar's challenge excludes such hardware but I am just curious.
oops: My gender was female, 
|
| « Last Edit: Mar 19th, 2008, 9:26pm by pallab » |
 IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Supercomputer vs Human
« Reply #1 on: Mar 19th, 2008, 10:10pm » |
Quote Modify
|
on Mar 19th, 2008, 9:20pm, pallab wrote:| I have a silly question. If one provides best possible hardware available (say like Hydra or Deep blue in chess) will they be able to beat best human players?. I know that Omar's challenge excludes such hardware but I am just curious. |
|
It's not a silly question at all, and in fact we've discussed it extensively here in the past. One of the old guard may be able to find a link for you in the forum archive.
IIRC, the general consensus was "no": bot_bomb running on a supercomputer still couldn't beat the top players. The reasoning is the branch factor of Arimaa is so high (3000-15000 possible moves per turn) that it rapidly outstrips any computer's ability to search deeply with a brute force technique, no matter how fast.
If a supercomputer were 3000 times faster than a desktop PC, this would give it the ability to search only one ply deeper, where current Arimaa bots can typically search 2.5 to 3.5 plies deep. Contrast this with chess, where supercomputers can search 12 to 16 plies ahead.
Experiments with letting regular bots search for long periods of time (hours to days) have not resulted in bots that play significantly better, and letting a desktop PC search for 2 days per turn is (very roughly) equivalent to letting a supercomputer search for 2 minutes per turn.
|
| « Last Edit: Mar 19th, 2008, 10:13pm by IdahoEv » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Supercomputer vs Human
« Reply #2 on: Mar 19th, 2008, 10:20pm » |
Quote Modify
|
The answer to your question is that we have no idea whether a supercomputer could win the Arimaa Challenge. If you read further than this you will get a garbage answer. Stop reading now. You have been warned.
I guess supercomputers come in different sizes. For the sake of argument, let's consider a computer 1000 times faster than the actual challenge hardware.
There is fairly good evidence that computer playing strength increases according to the logarithm of computing power, at least for chess. Therefore if you know how many ratings points it is worth to double the speed, you can extrapolate the gain of many doublings.
I did one experiment on one bot (provided by jdb) playing against itself. In addition to all the other reasons not to generalize from the result, the experiment had a huge statistical margin of error.
http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;nu m=1124835841
But, since it is the only result we have for Arimaa, let's use it. Let's say that a doubling of speed is worth 68 rating points. A computer that is 1000 times faster is 2^10 times faster. Ten doublings would be worth 680 rating points.
Right now Bomb2005CC is rated 1905, while chessandgo is rated 2500. If Bomb got 680 points better, it would be rated 2585, i.e. higher than the best player in the world by a little bit.
Therefore the bogus answer to your question is yes, a supercomputer could beat the best human player.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Supercomputer vs Human
« Reply #3 on: Mar 19th, 2008, 10:37pm » |
Quote Modify
|
on Mar 19th, 2008, 10:10pm, IdahoEv wrote:| Experiments with letting regular bots search for long periods of time (hours to days) have not resulted in bots that play significantly better, and letting a desktop PC search for 2 days per turn is (very roughly) equivalent to letting a supercomputer search for 2 minutes per turn. |
|
It's quite true that computers playing at postal speeds haven't seemed significantly better than those playing live. The trouble with that anecdotal evidence is that the human opponents can't restrict themselves to only thinking about the position for 2 minutes per reply. If nothing else they can ponder during the two days the computer is thinking.
Right now there is some anecdotal evidence contrary to the postal anecdotal evidence: a sense among some of the humans playing in the qualifying phase that Bomb2005CC is playing a bit stronger than it used to. I don't know the specs of Omar's machines, but by Moore's Law they should be twice as fast as they were two years ago, and four times as fast as they were four years ago. By my bogus reasoning above, Bomb would be playing 68 points and 136 points better respectively, enough for us to feel a difference.
In my heart of hearts, I believe that I could beat Bomb running on a supercomputer. I estimate my strategic judgment as worth more than Bomb's dumbness accelerated one thousand times faster. But pride goeth before a fall. A lot of human chess players were confident too, right up until they got beaten.
|
| « Last Edit: Mar 19th, 2008, 10:38pm by Fritzlein » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Supercomputer vs Human
« Reply #4 on: Mar 20th, 2008, 2:49am » |
Quote Modify
|
Interesting question to ponder. I guess if someone were to parallelize Bombs code to run on a supercomputer, it would probably have a pretty good chance of winning against the current top human players.
But then again our top players may not even be at the chess equivalent of a Masters level. I would not expect someone who has played chess as a hobby for 2 or 3 years without any books or coach to guide them to reach Masters level in that time frame. That is basically the situation our top Arimaa players are in right now. Maybe 10 years from now we might have the chess equivalent of master or grand master level players.
Although supercomputers would not qualify for the Arimaa challenge, they may still be needed to win the challenge 
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Supercomputer vs Human
« Reply #5 on: Mar 21st, 2008, 12:22pm » |
Quote Modify
|
on Mar 19th, 2008, 10:37pm, Fritzlein wrote:
I don't know the specs of Omar's machines, but by Moore's Law they should be twice as fast as they were two years ago, and four times as fast as they were four years ago. |
|
The specs for the hardware used is posted each year with the challenge details. For example the 2008 hardware is:
http://arimaa.com/arimaa/challenge/2008/hardware.html
Though the challenge match rules say:
"The hardware will typically be a standard general purpose computer that can be purchased within $1000 USD."
I think these servers would be more than that if they were fully purchased. I usually just rent them and the price is round $120 per month.
It is hard to say though without running some benchmarks how much faster the machines are each year.
|
| « Last Edit: Mar 21st, 2008, 12:29pm by omar » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Supercomputer vs Human
« Reply #6 on: Mar 21st, 2008, 2:00pm » |
Quote Modify
|
Thanks for the link, Omar. The disk and RAM size are exactly 4X what they were for the first Arimaa Challenge four years ago. The CPU is harder to gauge, but looking at some random benchmarks on the Internet, it looks like that has increased approximately 4X as well, with dual cores instead of one and Conroe instead of Pentium 4.
In terms of extrapolating computer strength, IdahoEv was looking at additional ply of search depth whereas I was looking at doublings of search speed. If twice the speed is worth 68 points, then an extra ply should be worth about 476 rating points, i.e. 7 times as much because the branching factor of Arimaa is about 2^14.
Right now BombP2 is rated 1838 and BombP1 is rated 1762, for a difference of only 76 points for a whole ply. That would seem to bust my theory pretty conclusively, and support the notion that BombP4 (about what a supercomputer could do in 2 minutes/move) would not be a contender for winning the Challenge.
On the other other hand, BombP1's rating is probably inflated by newcomers getting stuck there on the ladder, while BombP2's rating is probably deflated from experienced players doing some bot-bashing. I expect that the true value of an extra ply is somewhat more than 76 rating points and somewhat less than 476 rating points.
|
|
IP Logged |
|
|
|
Arimabuff
Forum Guru
Arimaa player #2764
Gender:
Posts: 589
|
|
Re: Supercomputer vs Human
« Reply #7 on: Mar 21st, 2008, 3:06pm » |
Quote Modify
|
on Mar 19th, 2008, 10:37pm, Fritzlein wrote:
...In my heart of hearts, I believe that I could beat Bomb running on a supercomputer. I estimate my strategic judgment as worth more than Bomb's dumbness accelerated one thousand times faster. But pride goeth before a fall. A lot of human chess players were confident too, right up until they got beaten. |
|
Just to play the Devil's advocate, can't you make room for the possibility that Bomb running on a supercomputer would come up with moves that would be tactically so perfect, so well thought out, that it would prevent you from any strategic gain? After all, you've only played against Bombp3 and had plenty of time to think about your next move. Imagine what a Bombp6 could come up with. I think a supercomputer could do that and maybe a little more.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Supercomputer vs Human
« Reply #8 on: Mar 21st, 2008, 4:53pm » |
Quote Modify
|
on Mar 21st, 2008, 3:06pm, Arimabuff wrote:| Just to play the Devil's advocate, can't you make room for the possibility that Bomb running on a supercomputer would come up with moves that would be tactically so perfect, so well thought out, that it would prevent you from any strategic gain? After all, you've only played against Bombp3 and had plenty of time to think about your next move. Imagine what a Bombp6 could come up with. I think a supercomputer could do that and maybe a little more. |
|
I quite agree that if you look far enough ahead tactically, it is equivalent to good strategy. A fast enough computer wouldn't need to be smart to beat me. The faster the computer is, the dumber it can be and still win. On that extreme, a computer that could index about 10^43 positions could win with no evaluation other than won/lost.
In that light the discussion is all about how fast is "fast enough" given the current level of bot dumbness. Supposing that BombP6 would be strong enough, we can estimate the necessary speed. Using the formula n=b^(d/2), the number of nodes to examine would be 15000^(6/2) = 3,375,000,000,000. According to Wikipedia, Hydra (with 64 processors) examines 200,000,000 nodes per second, so it would only need a little under 5 hours to do six ply. A computer only 140 times faster than Hydra could do six ply within tournament time controls. Is that about the speed of the fastest computer on earth? Somebody who knows more about supercomputers than I know should comment.
|
|
IP Logged |
|
|
|
Isaac Grosof
Forum Guru
Longtime Arimaa Fan
Gender:
Posts: 175
|
|
Re: Supercomputer vs Human
« Reply #9 on: Mar 24th, 2008, 5:24pm » |
Quote Modify
|
Deep blue=11.38 gigaflops
Blue Gene/P=1000 gigaflops
88x more powerful, or 17,600,000,000 nodes per second,
191 seconds for ply 6, and >2 for ply 5
Next year, power will double and the computers will be there.
With good use of reserve and a optional switch to 5ply if necessary, todays computers could do it.
|
| « Last Edit: Mar 24th, 2008, 5:25pm by Isaac Grosof » |
IP Logged |
Sorry about that one thing.
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print