[computer-go] an idea... computer go program's rank vs time

[Matt Gokey]

Don Dailey wrote:

Thanks Don, overall you may have missed my point.  I am not saying that 
human thinking time does not help in go like in chess, but rather that 
the relationship (the curve) between thinking time and strength may not 
be the same between chess and go as I thought you had been asserting and 
trying to offer some evidence for this, one part via logic and one part 
via my personal intuition.  I think there is some nugget of truth in the 
intuition of very strong go players with regard to this.  Personally I 
think the improvement given more time is less than in chess and returns 
diminish more quickly.  I was not referring to computer go or any 
computer algorithms though.

> To a point the improvement is linear - however there is gradual curve to
> this so it's not completely linear.   The surprise in computer chess was
> that it was difficult to detect that a doubling was NOT completely
> linear
> and only when computers really became strong did it start to become
> clear there was a gradual tapering off.
Are we talking about humans or computers here? Computer game play is 
entirely based on the algorithms and techniques in use.  In chess these 
are well established, scalable, and mature and so you can make 
generalizations. Not so in computer-go where there are so many wildly 
different techniques being used, some scalable to some degree or another 
and some not.

> 
> I believe the same curve exists in a properly scaled GO program but 
> since the game is deeper I believe it will appear linear for a long
> time to come, but in fact it's not strictly linear.
You may very well be right about computer-go with the proper algorithms 
since computers do not have the same limitations or abilities as the 
human mind. Whether it's linear with doubling depends on way too many 
unknown factors to even hazard a guess.

> I would also like to point out that although I believe that each
> doubling is roughly linear,  I'm not claiming you get the same 
> improvement as in chess.   You might get more or you might get
> less - actually the evidence is that you get more, perhaps because
> the game is much longer and minor improvements over hundreds of
> move add up to more likelihood of a win.
Here is where we would differ - I think it is less and it tapers off 
faster than in chess (for humans).

>>What if we look at it mathematically by looking at the branching factor? 
>>Go’s branching factor is generally considered to be about an order of 
>>magnitude greater than chess – perhaps a bit less, right?  That means 
>>that after each ply go becomes another additional order of magnitude 
>>more complex.  Now of course, in practice it’s not so simple, as 
>>breaking the game into regions and doing local reading and global 
>>analysis reduces the complexity somewhat, but in general go explodes a 
>>lot faster than chess and this fact is commonly used as one of the 
>>reasons methods used for computer chess don’t work on go especially 
>>combined with the lack of reliable evaluation.
> 
> I think this is more about information, not brute force ply.  With twice
> as much time you have twice as many thoughts, twice as much time to 
> produce a better idea,  twice everything.    I also suspect it's about
> playing the odds.  Give me twice as much time to think about something
> interesting and challenging, and it "increases my chances" of having a
> meaningful insight.  
> 
> It's always tempting to simply compare to depth or ply but I don't think
> it's about that.   When I talk about scalable algorithms instantly
> search
> comes to mind - but we can be open about this.   Who is to say some
> other
> scalable algorithm will not come along?   Perhaps some iterative
> computation
> that systematically produces (on average) a better and better move.   
Commenting about the above two paragraphs: Of course, I oversimplify as 
I pointed out to make the point about the complexity explosion due to 
both branching factor and evaluation difficulty - that is all. Reality 
is much messier.  And again I was not referring to computer-go algorithms.

> (snip)
> 
> But my point is that this is about information processing, not ply depth
> although there may be a great deal of overlap.
Agreed

>>For the sake of argument if we assume that doubling thinking time allows 
>>one to double the number of positions and alternatives that can be 
>>analyzed, this doubling would seem to have lesser impact in go where the 
>>explosion is much quicker than in chess and thus the same relationship 
>>may not hold.  
> 
> It's not clear to me that the effective branching factor is that much
> higher.   Right now it is for computers,  but for a good player most
> of the garbage is pruned and the tree is very narrow.    But even if
> I'm wrong about this,  you must remember that for ELO purposes it's 
> more about how much information you can process relative to your
> opponent,
> not how close you can get to perfect play.   Maybe that's why there is
> so much confusion about this.  
It is much higher, but pattern matching based on past experiences is 
shortcutting it to reduce the branching factor and provide an evaluation 
- the more experience you have and the stronger you get the more benefit 
you get from this ability.  Beginner players don't get much benefit 
here.  Simple pattern matching in computer-go programs seems to be 
effective only to a certain point - its not flexible enough.  It seems 
the pattern based evaluator combined with reading and other interplay 
analysis done by humans is much stronger and more capable (currently).

>>The improvement may not be linear or it may not hold for 
>>very long.  The point of diminishing returns for a human due to this 
>>could be much earlier in go than in chess.  
> 
> I actually believe the point of diminishing returns in GO to be much 
> more extended than in chess because the game is deeper strategically.
This assumes you have the cognitive power to deal with the deeper 
complexity which is the crux of my argument.  Go in a game tree sense 
quickly exceeds the brains limitations, its only because we can visually 
take advantage of the somewhat static nature of the board and use 
pattern recognition based on experience combined with reading and 
analysis that we can eventually learn to judge moves and position 
potentials.  I think it is a much more elegant and beautiful game than 
chess.  I think this is why there is so much mystery and philosophy 
mixed into the culture of go. It seems to require combining the left and 
right powers of the brain to a much greater degree than chess.
> 
> 
>>As go players get better 
>>they must learn to “sense” the board based on years of experience 
>>combined with our evolutionary tuned super parallel visual pattern 
>>matcher.  This provides the player shortcuts that otherwise would be 
>>impossible (for humans) to read out.  Assuming enough processing power 
>>and memory this problem would not necessarily hold for computer-go.  By 
>>the way, I think some of this very same thing applies to both chess and 
>>go, just a matter of different degrees.
> 
> 
> This it of course needed for strong play - but I'm arguing that it's not
> for scalability.
I agree.  I didn't say it was did I?
> 
> There is however some evidence (in chess) that the more skilled you are,
> the more scalable you can be.   Hans Berliner did a huge rating
> experiment
> with 2 versions of his world class program,  one with simple dumb
> evaluation
> and one with high quality evaluation.    He showed that the smarter 
> program improved more quickly as he continued to bump up the level.
> 
> I think several people hinted at this on this group.   Better players
> have
> better mental machinery to work with the extra time - I don't have a
> problem
> with this concept.   I think this probably also produces intransitives
> in playing strength, where a weak player with extra time appears to 
> improve at a more rapid pace when measured against another weak player, 
> but it only partially translates to extra strength against strong
> players.  
I agree, that's what I meant above referring to go players learning to 
"sense" the positions and use this to help them think about the game.

>> From my own experience with chess and go, I can say that I don’t feel 
>>overwhelmed when playing chess.  
> 
> I always felt overwhelmed even though I nearly reached USCF expert level
> or what was called candidate master strength.  
> 
> I don't feel any different in GO although I lack experience.  When I
> play
> against my programs I always feel like I could play a better move given
> more time and I never feel like I've run out of things to think about.
> I think a stronger player might realize more situations where the right
> move is obvious, but he will still encounter plenty of situations where
> he would like to have more time.
That's what I meant by not being overwhelmed - that is understanding 
enough to never feel like I've run out of things to think about.
> 
> As has been pointed out, the strongest go players will spend huge 
> amounts of time on key critical moves.
> 
> In a way, chess is easier and there are many more obvious choices to
> make in my opinion.   The obvious recapture comes to mind.   There 
> were always lots of moves in my games where I was quite confident 
> that I could play the right move without needed a lot of time. 
> However that doesn't make it non-scalable.
No disagreement here.
> 
> 
> 
>>That is, I always feel like I can think 
>>and reason about the moves fairly deeply and use simple evaluation like 
>>piece counts, protection, mobility, etc. to decide between lines of 
>>play.  I may be entirely wrong but I feel like I can think about it 
>>anyway.  
> 
> 
> I had more trouble with strategic decisions than tactics.   You can
> usually reason out tactics fairly quickly and I never felt that was
> where the time should be invested.   For me it was about making the
> right decisions - will an attack eventually work?  Should I go for
> this kind of ending or that?   Should I trade queens, expand my
> sphere of influence, etc.
> 
> But it doesn't matter.  Whatever you do it helps to have more time
> and I don't believe it's only about calculating tactical sequences.
No I didn't mean to imply that either - general positional factors as I 
mentioned are also very useful in keeping options open until you can see 
  a tactical sequence.
> 
> (snip) 
> 
>>Now with Go as a beginner still, on the other hand, I almost always felt 
>>and still feel quite overwhelmed without enough tools to understand how 
>>to plan and evaluate moves in all but the simplest isolated cases.  I 
>>know that giving me tons of extra time against a good player would not 
>>help.  
> 
> There is a ton of difference between whether it would help, and whether 
> it would help enough to give you a realistic chance of winning.    If 
> you are playing someone a few stones stronger where your odds of
> winning 
> are 1 in a million,  then you are going to feel overwhelmed (and will
> probably lose) even given a LOT of extra time.
You are right of course - it would help me play a bit better, but not 
win. I think my probability of winning would stay equal to zero.  But 
again I don't disagree that time helps, just how much it helps and how 
fast the returns for extra time diminish.
>
 > (snip)
> 
>>The interactions between areas and the explosion of the game and 
>>lack of experience to be able to “sense” good shape and proper balance 
>>early enough to lead to life and territory just simply overwhelms me. 
>>The feeling is not as severe as it was when I first learned, but it is 
>>still there.  I wonder whether even for strong amateurs this is still 
>>the case, but just happens a bit deeper.  Is this the time limit that 
>>Ray talks about where any more time is not helpful?  It is that point 
>>when it becomes so terribly complex and overwhelming that no more 
>>thinking can help given your current ability to judge potential in the 
>>positions.
> 
> 
> No, I believe this is nonsense.  You don't have to go from being 
> completely overwhelmed and in the dark to having it all figured out
> with confidence to move up a rank.   All you have to do is make 
> slightly better decisions a few time per game to play better.  
> Extra time give you this. 
That's not what I meant.  There is a lot of gray area where you can make 
better decisions between being overwhelmed trying to read vs. having it 
all figured out.