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

[Matt Gokey]

dave.devos at planet.nl wrote:
> 
> Yes. Don's scalability argument states that ELO gain is proportional 
> to time doubling.
> For me scalable use of time implies that time translates into depth.
> The extra depth is:
> 
> m - m0 = log(2)/log(b). 
> 
> So if the ELO gain for time doubling in Chess equals 100 over a wide 
> time scale and if Go has a 10 times larger branching factor than 
> Chess, then the ELO gain for time doubling in Go would equal 100/log
> (10) = 43 (everything else assumed equal).
> 
> I'm not sure i agree with Don, but i just want so say that if he is 
> right, than mathematically he is also right with a larger branching 
> factor.
Yes, this seems obvious and to me it appears you are begging the 
question - presupposing the conclusion. You said it yourself in the last 
sentence: _if_ he is right then mathematically it follows for the larger 
branching factor.  Can't argue with that.

I was trying to compare a different relationship related to the 
branching factor and other characteristics of Go to capacity of human 
logical reasoning and thinking.  The idea being to suggest a possible 
explanation for why Go may be qualitatively different than Chess in this 
regard.

So I'll attempt to put the relationship I was trying to describe with 
words into a mathematical model and then further describe my thought 
process.

Let b = branching factor
Let f = Effective avg. pruning factor(0-1), thus b*f is an effective avg 
branching factor
Let t = length of thinking time
Let p = maximum ply or depth under consideration
Let n = avg. number of positions a player can effectively evaluate in 
one unit of time (either explicitly or otherwise using whatever 
reading/learning/patterns/etc. to his avail)

Both f and n can be considered idealized measures of skill and ability 
of the player.

Let r = rough approximation (as this is a simplification/idealization) 
of the ratio of coverage of the game tree to depth p and defined as:

r(b,f,t,p,n) = n*t/(b*f)^p for all n*t<=(b*f)^p, otherwise r=1.0

Obviously if you double the time and keep the depth constant the ratio 
of coverage goes up in a linear relationship for all b.  But as time is 
increased, p is increasing presumably. Now the graph of r is not linear 
and higher b results in a faster rate of decline. Now I understand that 
this doesn't necessarily have anything to do with strength ratings.

So that is some background for the concept.  Bear with me if this 
borders on the obvious for a while.  So we all know that Go evaluation 
is very hard (for computers, but also for humans). You can't prune if 
you can't evaluate in some sense however (not with certainty anyway). 
You can't evaluate without understanding shapes/life and/or reading.

In chess these things are arguably quite a bit simpler.  So with chess 
with a much smaller starting branching factor and simpler more 
left-brain devices for pruning and evaluating the cost/benefit of 
looking deeper tends to have reasonable payback at relatively large 
depths.

Contrast with Go, starting with a much higher branching factor and 
lacking left brain (logical/reasoning) methods for pruning and 
evaluating, depth tends to create more confusion and quickly exceeds the 
brain's ability to keep track of exploding variations.  However, as you 
learn from experience you can recognize patterns for the different 
concepts and balance with analysis to effectively prune and evaluate 
position potential and group interaction and then you can go deeper with 
some confidence level in your understanding of the status of the game. 
Learning these skills while thinking about a particular game's next move 
is not generally practical and even if possible would presumably require 
enormous extra time. Yet without this ability you are left with a 
massively rapid expanding game tree to search.  Finally this is why I 
think it may be the case that doubling human thinking time for Go might 
not produce linear improvements.

Back to the model, we could add another variable perhaps:
Let c = reliability/certainty factor for the pruning and evaluations 
done during the search.  r*c might have some meaning...

And again I am not saying this is black and white.  Chess and Go share 
these same characteristics to different degrees.  I believe Chess is 
more logical/analytical and Go is more balanced analytical - 
intuitive/holistic (yin-yang thing), thus each yields to both approaches 
in different situations and ways.

But just because a rule of thumb holds for Chess doesn't mean it does 
for Go.  Of course I could be wrong, but I was just trying to introduce 
reasonable doubt, since Don always seems so sure of himself ;-)

Matt