Matt Gokey wrote:
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.
Let me expand on this. Perhaps due to the nature of Go and
the human style learning needed to judge some moves and positions to be
advantageous many (like 20-60+) stones out with possible interplay
between groups (a tree which cannot possibly be read excluding ladders),
ranking gained by experience and training our super massively parallel
pattern matching system out paces time doubling based improvements. So
for a hypothetical example only, let's say for a player with an
arbitrarily chosen rating of 1000, a time doubling from 30 minutes to 1
hour per game increases strength by 100 points. Another time doubling
may only increase by 75 points and another by 40 and then another by 20.
For a player with a different rating a doubling might increase by 200,
then 150, then 90. Maybe its not a predictable curve even - maybe there
are plateaus or steps or hills and valleys. That's the thought - due to
the nature of go the increases might not be linear nor consistent
between players of different strengths. I hesitate to venture what
others believe, but it seems based on Ray's and Mark's and others' posts
that there is a gut feeling amoung go players that this may be the case.
Perhaps they care to comment further.
And again I feel I have to repeat that I am not and was not
characterizing computer-go engines. In computer-go where there are so
many wildly different techniques being used, some scalable to some
degree or another and some not, it doesn't make sense to make
generalizations. Whether a specific program's scalability results in
any improvements linear or otherwise with time-doubling depends entirely
on the algorithms and techniques in use.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/