It is currently Fri Mar 29, 2024 8:05 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 23 posts ]  Go to page 1, 2  Next
Author Message
Offline
 Post subject: Re: Computer are strong?!
Post #1 Posted: Fri Dec 17, 2010 7:36 pm 
Lives in sente
User avatar

Posts: 924
Location: Pittsburgh
Liked others: 45
Was liked: 103
Rank: lazy
KGS: redundant/silchas
Tygem: redundant
Wbaduk: redundant
DGS: redundant
OGS: redundant
Tis the season for good trolling. Trollololol lol lol lol lol.

EDIT: I'm not the OP, but was responding to his attempt at trolling.


Last edited by Redundant on Mon Dec 20, 2010 1:19 pm, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #2 Posted: Fri Dec 17, 2010 8:10 pm 
Lives in gote
User avatar

Posts: 388
Location: Riverside CA
Liked others: 246
Was liked: 79
Rank: KGS 7 kyu
KGS: Krill
OGS: Krill
Redundant wrote:
Tis the season for good trolling. Trollololol lol lol lol lol.


http://www.youtube.com/watch?v=iwGFalTR ... r_embedded

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #3 Posted: Sat Dec 18, 2010 6:32 am 
Lives in sente

Posts: 1037
Liked others: 0
Was liked: 180
Was that a question?

a) Define "strong" (what does that term means to you)
b) Recognize that it isn't "computers" that might be strong at go but computer programs that might be -- but how well the program would do in a finite amount of time would then depend on power of the hardware on which running. Without the constraint "time" the computer itself is irrelevant.

Other questions about the performance of go playing software are possible. For example, the "Turing Test" with respect to programs playing go. (given a collection of game records, some human vs human and some human vs "bot", with how much certainty/acuracy can you identify the "bot" players)

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #4 Posted: Sun Dec 19, 2010 8:44 pm 
Dies in gote

Posts: 43
Liked others: 4
Was liked: 22
Once you place the constraint at "reasonable thinking time" (e.g. practical for usual tournament/casual play with human opponent), it does not really matter that much. It is a significant factor, but not drastically so; you may gain or lose two or three ranks but you will remain in the same ballpark. Either the algorithm is too generic and scales extremely slowly, or it is highly tuned and it gains the baseline strength very quickly, but gets caught in bad biases in hairy situations and will scale even poorer in these.

_________________
Go programmer and researcher: http://pasky.or.cz/~pasky/go/
EGF 1921, KGS ~1d and getting weaker

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #5 Posted: Mon Dec 20, 2010 6:44 am 
Lives in sente

Posts: 1037
Liked others: 0
Was liked: 180
pasky wrote:
Once you place the constraint at "reasonable thinking time" (e.g. practical for usual tournament/casual play with human opponent), it does not really matter that much. It is a significant factor, but not drastically so; you may gain or lose two or three ranks but you will remain in the same ballpark. Either the algorithm is too generic and scales extremely slowly, or it is highly tuned and it gains the baseline strength very quickly, but gets caught in bad biases in hairy situations and will scale even poorer in these.


Need to take this apart (several issues)

1) The performance of some of these algorithms may be extremely non-linear with respect to time (time being interpreted as a combination of machine power and real time). Below enough time performanace might be terrible but above some critical amount improvement with reasonable additional time modest and above some point improvement very slow as time increases exponentially.

2) You can't go by how the algorithms of several years ago behaved so the rest of what you say is outdated. The dominant algorithm now used by all the strongest programs does not behave the way you have described. Currently performance is limited purely by time and isn't "biased" in the way you think. Given enough time these algorithms would discover the best next move. For these programs "tuning" is adjusting behavior so as to get the best performance within the constraint of actual time given the allowed computer power. How that is done might or might not introduce "bias" (it doesn't have to -- need not be deterministic*)

3) Objectives differ. Are we after the strongest possible program (given the time/machine power constraint) or the strongest one that can pass or come close to passing the Turing test within that constraint? (not obviously identifiable as a non human player -- if presented with a set of games some of which between two humans and some between a human and this program you could not easily/certainly separate into the two subsets)

* And here don't try to go into a discussion of "pseudo-random" vs "random" since could use an approximate true random (for example, the time used by the opponent to make the previous move)

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #6 Posted: Mon Dec 20, 2010 9:14 am 
Beginner
User avatar

Posts: 12
Liked others: 4
Was liked: 6
KGS: liquido
Mike Novack wrote:
pasky wrote:
Once you place the constraint at "reasonable thinking time" (e.g. practical for usual tournament/casual play with human opponent), it does not really matter that much. It is a significant factor, but not drastically so; you may gain or lose two or three ranks but you will remain in the same ballpark. Either the algorithm is too generic and scales extremely slowly, or it is highly tuned and it gains the baseline strength very quickly, but gets caught in bad biases in hairy situations and will scale even poorer in these.


Need to take this apart (several issues)

1) The performance of some of these algorithms may be extremely non-linear with respect to time (time being interpreted as a combination of machine power and real time). Below enough time performanace might be terrible but above some critical amount improvement with reasonable additional time modest and above some point improvement very slow as time increases exponentially.

2) You can't go by how the algorithms of several years ago behaved so the rest of what you say is outdated. The dominant algorithm now used by all the strongest programs does not behave the way you have described. Currently performance is limited purely by time and isn't "biased" in the way you think. Given enough time these algorithms would discover the best next move. For these programs "tuning" is adjusting behavior so as to get the best performance within the constraint of actual time given the allowed computer power. How that is done might or might not introduce "bias" (it doesn't have to -- need not be deterministic*)

3) Objectives differ. Are we after the strongest possible program (given the time/machine power constraint) or the strongest one that can pass or come close to passing the Turing test within that constraint? (not obviously identifiable as a non human player -- if presented with a set of games some of which between two humans and some between a human and this program you could not easily/certainly separate into the two subsets)

* And here don't try to go into a discussion of "pseudo-random" vs "random" since could use an approximate true random (for example, the time used by the opponent to make the previous move)


Actually I agree with pasky here. Both of us have experience in Computer Go using MCTS (the dominant algo you speak of). Yes, MCTS programs do gain more strength from more time, but within "reasonable" time limits that humans might use, the difference is not so big. MCTS seems to gain about 1 stone with every doubling of the thinking time. This corresponds to "It is a significant factor, but not drastically so; you may gain or lose two or three ranks but you will remain in the same ballpark."

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #7 Posted: Mon Dec 20, 2010 10:56 am 
Lives in sente
User avatar

Posts: 1103
Location: Netherlands
Liked others: 408
Was liked: 422
Rank: EGF 4d
GD Posts: 952
are people actually writing reasoned posts in response to an ANNOUNCED troll post?

Do you guys read the OP's anymore?

_________________
Tactics yes, Tact no...

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #8 Posted: Mon Dec 20, 2010 11:00 am 
Lives in sente
User avatar

Posts: 761
Liked others: 152
Was liked: 204
Rank: the k-word
Computer are

VARY STONG!


This post by palapiku was liked by: gaius
Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #9 Posted: Mon Dec 20, 2010 11:05 am 
Tengen
User avatar

Posts: 4844
Location: Mechanicsburg, PA
Liked others: 62
Was liked: 505
Rank: Wbaduk 7D
KGS: magicwand
Tygem: magicwand
Wbaduk: rlatkfkd
DGS: magicwand
OGS: magicwand
acking troll:
there are computer program that will play perfect endgame.
so computers are stronger than professionals in some sense
:)

_________________
"The more we think we know about
The greater the unknown"

Words by neil peart, music by geddy lee and alex lifeson

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #10 Posted: Mon Dec 20, 2010 3:19 pm 
Lives in sente
User avatar

Posts: 1103
Location: Netherlands
Liked others: 408
Was liked: 422
Rank: EGF 4d
GD Posts: 952
Redundant wrote:
Tis the season for good trolling. Trollololol lol lol lol lol.

EDIT: I'm not the OP, but was responding to his attempt at trolling.


Haha, I didn't realize this was a response to another thread, I just assumed that the subject line was good rickroll material. My bad!

_________________
Tactics yes, Tact no...

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #11 Posted: Mon Dec 20, 2010 4:03 pm 
Lives in sente
User avatar

Posts: 924
Location: Pittsburgh
Liked others: 45
Was liked: 103
Rank: lazy
KGS: redundant/silchas
Tygem: redundant
Wbaduk: redundant
DGS: redundant
OGS: redundant
shapenaji wrote:
Redundant wrote:
Tis the season for good trolling. Trollololol lol lol lol lol.

EDIT: I'm not the OP, but was responding to his attempt at trolling.


Haha, I didn't realize this was a response to another thread, I just assumed that the subject line was good rickroll material. My bad!


There actually was a post before me in this thread, but the poster got the banhammer, and his post was deleted.

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #12 Posted: Tue Dec 21, 2010 1:47 am 
Lives in sente
User avatar

Posts: 1103
Location: Netherlands
Liked others: 408
Was liked: 422
Rank: EGF 4d
GD Posts: 952
To our esteemed moderator: In future, if someone is being banworthy, mind leaving a little something-something behind? I was profoundly confused at first

_________________
Tactics yes, Tact no...

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #13 Posted: Tue Dec 21, 2010 2:02 am 
Lives in gote
User avatar

Posts: 643
Location: Munich, Germany
Liked others: 115
Was liked: 102
Rank: KGS 3k
KGS: LiKao / Loki
How to treat such trolls is being discussed in a thread in the Suggestions forum

_________________
Sanity is for the weak.

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #14 Posted: Tue Dec 21, 2010 6:19 am 
Beginner

Posts: 4
Liked others: 0
Was liked: 0
Rank: AGA 8kyu
GD Posts: 20
Computer are strong?!

Pie are square.

No, brownies are square; pie are round.

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #15 Posted: Tue Dec 21, 2010 7:23 am 
Lives in sente

Posts: 1037
Liked others: 0
Was liked: 180
liquido wrote:
Actually I agree with pasky here. Both of us have experience in Computer Go using MCTS (the dominant algo you speak of). Yes, MCTS programs do gain more strength from more time, but within "reasonable" time limits that humans might use, the difference is not so big. MCTS seems to gain about 1 stone with every doubling of the thinking time. This corresponds to "It is a significant factor, but not drastically so; you may gain or lose two or three ranks but you will remain in the same ballpark."


I think you are considering too small a portion of the curve.

Consider the shape of the curve performance vs time (number of algorithm steps) over a large range. What I am saying is that below some number of steps (too little time) won't be other than random moves. In this region the curve is very steep, great improvement when more time is allowed. And at the other end gogin to take a lot more than doubling to increase one level. So yes, somewhere in between you would observe what you say you do (doubling time per level improvement). But I think:

a) That's over a relatively small number of playing levels. Keep in mind that even an exponent of 2 grows quickly.
b) The strongest programs are currently above this point pon the curve. In other words, the implementations are fast enough that they are able to play at acceptable speed (from the human point of view) at a level where for them to go up another level would take much more than doubling the time.

You want a practical example? How about MFOG 12.21? It is supposed to be at 1 dan on a "standard" 2 core machine that a program buyer might be expected to have but the bot on KGS is playing at 2 dan on a machine about 6 times more powerful than "standard" (equivalent to six times the time).

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #16 Posted: Tue Dec 21, 2010 7:50 am 
Tengen
User avatar

Posts: 4511
Location: Chatteris, UK
Liked others: 1589
Was liked: 656
Rank: Nebulous
GD Posts: 918
KGS: topazg
Mike Novack wrote:
I think you are considering too small a portion of the curve.

Consider the shape of the curve performance vs time (number of algorithm steps) over a large range. What I am saying is that below some number of steps (too little time) won't be other than random moves. In this region the curve is very steep, great improvement when more time is allowed. And at the other end gogin to take a lot more than doubling to increase one level. So yes, somewhere in between you would observe what you say you do (doubling time per level improvement). But I think:

a) That's over a relatively small number of playing levels. Keep in mind that even an exponent of 2 grows quickly.
b) The strongest programs are currently above this point pon the curve. In other words, the implementations are fast enough that they are able to play at acceptable speed (from the human point of view) at a level where for them to go up another level would take much more than doubling the time.


I agree with this, although I think both sides have an important point. It is I suspect hard to know what the ratio is for different strengths, even picking an individual bot. Also, I suspect now that the "nearly random moves" area of thinking time allowance is in small fractions of a single second. I suspect a bot taking 3 seconds per move will play fairly strongly compared to, say, 30 seconds per move.

Mike Novack wrote:
You want a practical example? How about MFOG 12.21? It is supposed to be at 1 dan on a "standard" 2 core machine that a program buyer might be expected to have but the bot on KGS is playing at 2 dan on a machine about 6 times more powerful than "standard" (equivalent to six times the time).


Supposed to be what sort of 1 dan? A "standard 2 core machine" = 1 dan on KGS or as defined somewhere else?

Also, doubling processing power is a better measure than doubling time if being compared to humans (which presumably the 2 dan has been earned against)

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #17 Posted: Tue Dec 21, 2010 8:22 am 
Beginner
User avatar

Posts: 12
Liked others: 4
Was liked: 6
KGS: liquido
Mike Novack wrote:
I think you are considering too small a portion of the curve.

Consider the shape of the curve performance vs time (number of algorithm steps) over a large range. What I am saying is that below some number of steps (too little time) won't be other than random moves. In this region the curve is very steep, great improvement when more time is allowed. And at the other end gogin to take a lot more than doubling to increase one level. So yes, somewhere in between you would observe what you say you do (doubling time per level improvement).


You are correct in the lower extreme of time, but anything longer than 10s is well into this curve and less than 10s is not really reasonable thinking time for a human (topazg has basically already pointed this out). Bear in mind that most MCTS programs can do in the order of 10000 playouts a second.

The trend I describe actually continues for a quite some time. Have a look at this study: http://cgos.boardspace.net/study/index.html This extended up to 8388608 playouts for Mogo and many more for Fatman. I have not seen or done any tests myself to support this trend on 19x19, but I see no reason this trend should not hold.

Mike Novack wrote:
You want a practical example? How about MFOG 12.21? It is supposed to be at 1 dan on a "standard" 2 core machine that a program buyer might be expected to have but the bot on KGS is playing at 2 dan on a machine about 6 times more powerful than "standard" (equivalent to six times the time).


Is this a 1 dan on KGS? You also have to bear in mind that scaling over multiple cores or a cluster has other performance penalties and is currently one of the areas of research in Computer Go.

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #18 Posted: Tue Dec 21, 2010 8:50 am 
Tengen
User avatar

Posts: 4511
Location: Chatteris, UK
Liked others: 1589
Was liked: 656
Rank: Nebulous
GD Posts: 918
KGS: topazg
liquido wrote:
The trend I describe actually continues for a quite some time. Have a look at this study: http://cgos.boardspace.net/study/index.html This extended up to 8388608 playouts for Mogo and many more for Fatman. I have not seen or done any tests myself to support this trend on 19x19, but I see no reason this trend should not hold.


This is very interesting. As the playouts is presumably the primary factor, a bigger board should have the curve arrive later due to the additional time to complete the payouts presumably? If so, how much longer does a 19x19 playout take than a 9x9 playout, having averaged out including overhead time?

From the table you sent, and assuming 10,000 playouts per sec, Mogo gets stronger as follows:

6.5 secs/move = 2469
13.1 = 2580
26.2 = 2659
52.4 = 2757

1.75 mins/move = 2815
3.5 = 2893
7.0 = 2959

So, interestingly, there's 2 full stones of difference between 6.5 and 26.2 seconds, which I wouldn't have guessed. Just as interestingly, it's another 2 stones stronger at 7 mins per move - I would have thought it would have flattened off before into the minutes per move, but it's only really 7-14-28 minutes where the flattening off is clear. At lower levels, this increase is obviously more marked than 1 stone per doubling in playouts, so the comparative playout time for 19x19 boards is quite relevant I think.

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #19 Posted: Tue Dec 21, 2010 8:58 am 
Beginner
User avatar

Posts: 12
Liked others: 4
Was liked: 6
KGS: liquido
topazg wrote:
This is very interesting. As the playouts is presumably the primary factor, a bigger board should have the curve arrive later due to the additional time to complete the payouts presumably? If so, how much longer does a 19x19 playout take than a 9x9 playout, having averaged out including overhead time?


A very quick test with my program shows that playouts on a 9x9 are about 4.68 time faster than a 19x19, and considering 361/81=4.46, the speed of playouts seems to be directly proportional to intersections on the board.

Top
 Profile  
 
Offline
 Post subject: Re: Computer are strong?!
Post #20 Posted: Tue Dec 21, 2010 9:29 am 
Tengen
User avatar

Posts: 4511
Location: Chatteris, UK
Liked others: 1589
Was liked: 656
Rank: Nebulous
GD Posts: 918
KGS: topazg
liquido wrote:
topazg wrote:
This is very interesting. As the playouts is presumably the primary factor, a bigger board should have the curve arrive later due to the additional time to complete the payouts presumably? If so, how much longer does a 19x19 playout take than a 9x9 playout, having averaged out including overhead time?


A very quick test with my program shows that playouts on a 9x9 are about 4.68 time faster than a 19x19, and considering 361/81=4.46, the speed of playouts seems to be directly proportional to intersections on the board.


Awesome, thanks, which makes it, (the equivalent of, obviously actual performance will be lower on 19x19):

3.25 secs/move = 2063
6.5 = 2270
13.1 = 2339
26.2 = 2469
52.4 = 2580

1.75 mins/move = 2659
3.5 = 2757
7.0 = 2815

So it looks like about 4 stones between my original figures of 3 and 30 seconds per move. Even though this is seriously back of the envelope, I think I stand corrected. So, as liquido said, one stone per doubling in a "normal time controls" range (6.5 secs per move up to 3.5 minutes per move seems to fit this) is reasonably accurate, according to this table at least.

It would be interesting to see if this isn't accurate. Presumably, because of the fact that the number of possible variations on a 19x19 board is so much larger, 10,000 playouts on a 9x9 board will provide considerably better overall accuracy than 10,000 playouts on a 19x19 board. It would be very interesting to see this scaled to 19x19.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 23 posts ]  Go to page 1, 2  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group