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

[Matt Gokey]

[EMAIL PROTECTED] 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

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Vlad Dumitrescu]

Hi Matt,

On 1/25/07, Matt Gokey <[EMAIL PROTECTED]> wrote:

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 ;-)


If I may venture trying to rephrase your arguments, do you mean that
since difficulty grows exponentially there may be a qualitative leap
between chess and go?

Comparing chess and go is difficult, but I think this effect can be
seen between 9x9 and 19x19 go too: the two games are quite different,
because in 9x9 there is practically no strategic element and this
element brings a whole new dimension to the game.

Or did I misunderstand you?

best regards,
Vlad
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Don Dailey]

On Thu, 2007-01-25 at 03:27 -0600, Matt Gokey wrote:
> 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. 

You are still missing the point. 

What you are describing looks great on paper,  but that's now how
the extra time works.   Even if you are given 10X more time,  the
benefit will come from not from suddenly being able to grasp master
level concepts, but from repairing the little mundane problems 
that  are just within your reach.  

And it will only effect a small number of moves.   Most of the
moves will be exactly as you say, confusing, and you will not be
able to improve them (and I think this is the partly the source 
of what I consider the misconception some of us are having.)

The other source of the misconception you also touched on.  You
mentioned "enormous extra time", which is correct.  It DOES INDEED
require enormous extra time,  even in computer chess to make
anything more than a modest improvement.The reason you just
can't imagine that "a lot" of extra time will help you play a
better move is because most of the time it won't!   Your 
intuition is correct but your conclusion is incorrect.   

The improvement will come only from little mundane improvements
of a very small number of moves - but that is enough to make
your level of play go up a  bit.   

Please note that for weak players,  a LOT of moves need to be
improved, and for strong players only a few need to be improved.
But the way this works is that the stronger you get,  the 
more impact improving just a few moves makes because your
opponent is more likely to take advantage of your mistakes.

Someone once did a computer chess experiment with really long
and deep searches and they studied how often computers "changed
their minds" when making moves.   As it turns out,  the rate
of change (per ply or per doubling) tapers off as you go deeper
and deeper.And yet the strength improvement is almost
the same for each doubling.   

The computers follow your cognitive intuition that you posted
about,  they can think for an enormous amount of time and still
not improve on the move.Improvement isn't about making ALL the
moves better, only a few.   It's almost always possible, given
more time, to find some improvements in a few of your moves
and this is what makes you play better.

Since it takes
geometrically increasing amounts of time to make the same
strength jump,  there is no chance you will play enormously
better given any practical amount of time,  which probably
matches both your intuition on this,  and the actual facts.


- Don









___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[terry mcintyre]

Go, being a matter of efficiency over one's opponent, may be even more 
susceptible to improvement via many small improvements over many moves than is 
chess. As long as you don't leave weak shapes behind, picking up a point here, 
a point there at a slightly faster rate than your opponent will give you the 
game.
 




 

Expecting? Get great news right away with email Auto-Check. 
Try the Yahoo! Mail Beta.
http://advision.webevents.yahoo.com/mailbeta/newmail_tools.html ___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Don Dailey]

On Thu, 2007-01-25 at 08:23 -0800, terry mcintyre wrote:
> Go, being a matter of efficiency over one's opponent, may be even more
> susceptible to improvement via many small improvements over many moves
> than is chess. As long as you don't leave weak shapes behind, picking
> up a point here, a point there at a slightly faster rate than your
> opponent will give you the game.

And this indeed seems to be the case.   When I was testing 19x19 cgos 
with Steve, the performance rating between versions that did 2x 
simple MC play-outs was enormous, over 300 points per doubling.

That rate of improvement tapered off with higher levels because the
simple MC algorithm is strictly limited in scalability.  

I also had a difficult time producing a player that was less than
200 ELO stronger than a random player.   Even a single play-out,
which seems hardly enough to discriminate between moves, is
enormously stronger than a random player.It was pretty much
like this:

   ASSUME computer is black

   1. play 1 random game.

   2. If black wins,  play one of the first N black moves in the 
  play-out  (all-as-first, for me it's some-as-first.)

   3. If white wins, play one of the black move NOT in the play-out.

   4. Crush a random player!


Of course 2 play-outs was incredibly effective against against a
1 play-out player,  4 beats 2,  8 beats 4 and the tapering effect
is very gradual up to the level we were able to test - where the
computer was not able to play a game without losing on time.

This was despite the fact that the algorithm is limited.   There
is a point in the 9x9 version where it hits the wall.   For
Botnoid (AnchorMan) 5000 simulations is almost as good as it
gets and it plays very quickly at this level.   This is not
a refutation of the principle,  it's just that AnchorMan has
a very un-scalable algorithm.   1 ply monte carlo cannot 
discover much of anything even if given infinite number of
play-outs but this changes completely when a tree is added
such as in UCT.

- Don




 
> 
> 
> 
> 
> __
> Get your own web address.
> Have a HUGE year through Yahoo! Small Business.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Jim O'Flaherty, Jr.]

Terry,

Where's the notion that through small increments, there is no reasonable path 
from a house 3 bedroom house to a 10 story building?  Isn't the consistency of 
the assumption set around how a house is designed and built fundamentally (as 
in pardigm-ally) different than that of how designing and building a 10 story 
building?  And doesn't the assumption set for the 10 story building have to be 
mostly abandoned when creating the design and building a 100 story building?

Isn't there's a point where the shift from one complex infrastructure to 
another results in a setback as nuanced assumptions must be abandoned when 
their lower dependent assumptions have to be reorganized or even replaced?


Jim

- Original Message 
From: terry mcintyre <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]; computer-go 
Sent: Thursday, January 25, 2007 10:23:13 AM
Subject: Re: [computer-go] an idea... computer go program's rank vs time

Go, being a matter of efficiency over one's opponent, may be even more 
susceptible to improvement via many small improvements over many moves than is 
chess. As long as you don't leave weak shapes behind, picking up a point here, 
a point there at a slightly faster rate than your opponent will give you the 
game.
 






 Get your own web address.
 Have a HUGE year through Yahoo! Small 
Business.___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Stuart A. Yeates]

On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote:



I also had a difficult time producing a player that was less than
200 ELO stronger than a random player.   Even a single play-out,
which seems hardly enough to discriminate between moves, is
enormously stronger than a random player.It was pretty much
like this:

   ASSUME computer is black



0.  with probably P, play a random move (using the same selection
methodology as the random player)

  1. play 1 random game.


   2. If black wins,  play one of the first N black moves in the
  play-out  (all-as-first, for me it's some-as-first.)

   3. If white wins, play one of the black move NOT in the play-out.

   4. Crush a random player!




Surely by varying P, you can get a player arbitarily close to the random
player?

Or am I missing something?

cheers
stuart
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Nick Apperson]

ofcourse you are correct, P = 1.0 is just the random player.  Obviously the
ELO as a function of P is going to be continuous.  So, being really close to
P=1.0 will make for a player that is only very slightly better than random.

I think it is also interesting to consider a player worse than random.  Take
your 1 trial MC program and instead of playing only moves than win, play
only moves that lose.  My guess is that the skill difference between this
program and random would be greater than between random and 1 trial MC, but
I would be interested to see a trial of this.

On 1/25/07, Stuart A. Yeates <[EMAIL PROTECTED]> wrote:




On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote:
>
>
> I also had a difficult time producing a player that was less than
> 200 ELO stronger than a random player.   Even a single play-out,
> which seems hardly enough to discriminate between moves, is
> enormously stronger than a random player.It was pretty much
> like this:
>
>ASSUME computer is black


 0.  with probably P, play a random move (using the same selection
methodology as the random player)

   1. play 1 random game.
>
>2. If black wins,  play one of the first N black moves in the
>   play-out  (all-as-first, for me it's some-as-first.)
>
>3. If white wins, play one of the black move NOT in the play-out.
>
>4. Crush a random player!
>


Surely by varying P, you can get a player arbitarily close to the random
player?

Or am I missing something?

cheers
stuart

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[terry mcintyre]

So what would it take to get corporate sponsorship of the sort which
drove the chess computing field? Where is the Go equivalent of Deep
Thought?

Near as I can tell, David Doshay's Sluggo is the only large-scale
parallel effort. Mogo uses at most 4 CPUs. What might be accomplished
with one of the top500.org clusters of hundreds or thousands of CPUs?




 

Finding fabulous fares is fun.  
Let Yahoo! FareChase search your favorite travel sites to find flight and hotel 
bargains.
http://farechase.yahoo.com/promo-generic-14795097___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Nick Apperson]

I am writing my program to scale to n processors because I think that is the
direction hardware is headed.  However, I think clever programming will do
more than computational power with go.

On 1/25/07, terry mcintyre <[EMAIL PROTECTED]> wrote:


So what would it take to get corporate sponsorship of the sort which
drove the chess computing field? Where is the Go equivalent of Deep
Thought?

Near as I can tell, David Doshay's Sluggo is the only large-scale
parallel effort. Mogo uses at most 4 CPUs. What might be accomplished
with one of the top500.org clusters of hundreds or thousands of CPUs?


--
Expecting? Get great news right away with email 
Auto-Check.
Try the Yahoo! Mail 
Beta.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Don Dailey]

On Thu, 2007-01-25 at 17:41 +, Stuart A. Yeates wrote:
>  0.  with probably P, play a random move (using the same selection
> methodology as the random player)
> 
> 
>1. play 1 random game.
> 
>2. If black wins,  play one of the first N black moves in
> the
>   play-out  (all-as-first, for me it's some-as-first.)
> 
>3. If white wins, play one of the black move NOT in the
> play-out. 
> 
>4. Crush a random player!
> 
> 
> Surely by varying P, you can get a player arbitarily close to the
> random player?
> 
> Or am I missing something?

This is actually the way I ended up implementing it,  I play a random
move with some probability, otherwise I do the 1 play-out thing.

It feels like an ugly hack although it was practical enough to suit me.


- Don

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Don Dailey]

On Thu, 2007-01-25 at 12:17 -0600, Nick Apperson wrote:
> I am writing my program to scale to n processors because I think that
> is the direction hardware is headed.  However, I think clever
> programming will do more than computational power with go.

I take the point of view that clever programming IS more computational 
power.  I have never advocated WASTING power.  

- Don


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[David Doshay]

On 25, Jan 2007, at 10:14 AM, terry mcintyre wrote:


So what would it take to get corporate sponsorship of the sort which
drove the chess computing field? Where is the Go equivalent of Deep
Thought?


The Japanese Govt and industrial sponsorship of the Fifth Generation
Project, which did have playing Go on its list, collapsed very soon
after the Japanese real estate bubble burst, over 15 years ago.


Near as I can tell, David Doshay's Sluggo is the only large-scale
parallel effort. Mogo uses at most 4 CPUs. What might be accomplished
with one of the top500.org clusters of hundreds or thousands of CPUs?


Corporate sponsorship would be required for access to a top500
cluster, but for a smaller scale attempt I have already offered the
72 CPUs in my largest cluster for a scaling study. Nobody took
me up on the offer, so I gave the time to a physics computation.
That computation should be done in less than a month, and I
will repeat the offer now. We can also put a few of my clusters
together and scale up a bit more. However, if nobody responds
in a short while, I will again turn the cluster back to physics.

If you have a MC-UCT code that can scale up to multiple CPUs
then contact me off the list. I am open to collaboration.

Repeating my experience to date: with the algorithms in use by
SlugGo, more that 20 or so processors and deeper lookahead
than just a few moves not only does not play better, but it plays
worse. MC-UCT clearly has better scaling behavior.

Cheers,
David




___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Nick Apperson]

I don't rememeber citing you as saying that.  My however was in reference to
myself.

On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote:


On Thu, 2007-01-25 at 12:17 -0600, Nick Apperson wrote:
> I am writing my program to scale to n processors because I think that
> is the direction hardware is headed.  However, I think clever
> programming will do more than computational power with go.

I take the point of view that clever programming IS more computational
power.  I have never advocated WASTING power.

- Don


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Chris Fant]

Have you considered refocusing towards MC Go?


On 1/25/07, David Doshay <[EMAIL PROTECTED]> wrote:


On 25, Jan 2007, at 10:14 AM, terry mcintyre wrote:

> So what would it take to get corporate sponsorship of the sort which
> drove the chess computing field? Where is the Go equivalent of Deep
> Thought?

The Japanese Govt and industrial sponsorship of the Fifth Generation
Project, which did have playing Go on its list, collapsed very soon
after the Japanese real estate bubble burst, over 15 years ago.

> Near as I can tell, David Doshay's Sluggo is the only large-scale
> parallel effort. Mogo uses at most 4 CPUs. What might be accomplished
> with one of the top500.org clusters of hundreds or thousands of CPUs?

Corporate sponsorship would be required for access to a top500
cluster, but for a smaller scale attempt I have already offered the
72 CPUs in my largest cluster for a scaling study. Nobody took
me up on the offer, so I gave the time to a physics computation.
That computation should be done in less than a month, and I
will repeat the offer now. We can also put a few of my clusters
together and scale up a bit more. However, if nobody responds
in a short while, I will again turn the cluster back to physics.

If you have a MC-UCT code that can scale up to multiple CPUs
then contact me off the list. I am open to collaboration.

Repeating my experience to date: with the algorithms in use by
SlugGo, more that 20 or so processors and deeper lookahead
than just a few moves not only does not play better, but it plays
worse. MC-UCT clearly has better scaling behavior.

Cheers,
David




___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[David Doshay]

We are thinking about it, but others have code that is far ahead
of whatever our first effort is likely to produce, so I favor a
collaboration.

We are still investigating behavior that we do not expect from
SlugGo, and we are working on a number of fronts to move
from where we have been (using multiple GNU Gos) towards
our original intent of several completely different Go engines.
Adding MC-UCT makes sense, but there are only so many
hours in a day, and only a few of us working, so MC-UCT
has not yet become our highest priority.

But we have not considered moving to pure MC-UCT.

Cheers,
David



On 25, Jan 2007, at 12:30 PM, Chris Fant wrote:


Have you considered refocusing towards MC Go?


On 1/25/07, David Doshay <[EMAIL PROTECTED]> wrote:


On 25, Jan 2007, at 10:14 AM, terry mcintyre wrote:

> So what would it take to get corporate sponsorship of the sort  
which

> drove the chess computing field? Where is the Go equivalent of Deep
> Thought?

The Japanese Govt and industrial sponsorship of the Fifth Generation
Project, which did have playing Go on its list, collapsed very soon
after the Japanese real estate bubble burst, over 15 years ago.

> Near as I can tell, David Doshay's Sluggo is the only large-scale
> parallel effort. Mogo uses at most 4 CPUs. What might be  
accomplished
> with one of the top500.org clusters of hundreds or thousands of  
CPUs?


Corporate sponsorship would be required for access to a top500
cluster, but for a smaller scale attempt I have already offered the
72 CPUs in my largest cluster for a scaling study. Nobody took
me up on the offer, so I gave the time to a physics computation.
That computation should be done in less than a month, and I
will repeat the offer now. We can also put a few of my clusters
together and scale up a bit more. However, if nobody responds
in a short while, I will again turn the cluster back to physics.

If you have a MC-UCT code that can scale up to multiple CPUs
then contact me off the list. I am open to collaboration.

Repeating my experience to date: with the algorithms in use by
SlugGo, more that 20 or so processors and deeper lookahead
than just a few moves not only does not play better, but it plays
worse. MC-UCT clearly has better scaling behavior.

Cheers,
David




___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Don Dailey]

That was just a statement, "I have never advocated WASTING power" to
help
make it clear that I believe in squeezing the most out of each cpu
cycles,
not just making some algorithm as fast as it can be but also using the
best algorithms.  

I did not take your post as some kind of contradictory statement.

- Don


On Thu, 2007-01-25 at 14:27 -0600, Nick Apperson wrote:
> I don't rememeber citing you as saying that.  My however was in
> reference to myself.
> 
> On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote:
> On Thu, 2007-01-25 at 12:17 -0600, Nick Apperson wrote:
> > I am writing my program to scale to n processors because I
> think that 
> > is the direction hardware is headed.  However, I think
> clever
> > programming will do more than computational power with go.
> 
> I take the point of view that clever programming IS more
> computational
> power.  I have never advocated WASTING power. 
> 
> - Don
> 
> 
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
> 

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Matt Gokey]

Vlad Dumitrescu wrote:

Hi Matt,

On 1/25/07, Matt Gokey <[EMAIL PROTECTED]> wrote:


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 ;-)


If I may venture trying to rephrase your arguments, do you mean that
since difficulty grows exponentially there may be a qualitative leap
between chess and go?

Not really.  I merely am raising a question about the assertion that
human doubling of thinking time results in _linear_ improvements. I am
not claiming that there is no improvement - never have.  I am not
claiming that every turn must produce better results to improve overall
play - never have.  However I am trying to explain a rationale for the
possibility that improvements may not be linear based on the nature of Go.



Comparing chess and go is difficult, but I think this effect can be
seen between 9x9 and 19x19 go too: the two games are quite different,
because in 9x9 there is practically no strategic element and this
element brings a whole new dimension to the game.

Yes it is difficult to compare.  Don ventured into these waters by
asserting that a relationship fairly well established and reliable in
Chess holds for Go.

As for between 9x9 and 19x19 Go, obviously 19x19 is harder and games are
much more strategically and tactically interesting, but I think a
similar relationship between chess and 9x9 Go probably holds, just
differs by degree.



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Matt Gokey]

Don Dailey wrote:
You are still missing the point. 

I can say the same of you.

I merely am raising a question about the assertion that doubling of 
_human_ thinking time results in _linear_ improvements. I am not 
claiming that there is no improvement - never have.  I am not claiming 
that every turn must produce better results to improve overall play - 
never have.  However I am trying to explain a rationale for the 
possibility that improvements may not be linear based on the nature of Go.



What you are describing looks great on paper,  but that's now how
the extra time works.   Even if you are given 10X more time,  the
benefit will come from not from suddenly being able to grasp master
level concepts, but from repairing the little mundane problems 
that  are just within your reach.
How do you know this? Improvements could come from many other different 
sources.




And it will only effect a small number of moves.   Most of the
moves will be exactly as you say, confusing, and you will not be
able to improve them (and I think this is the partly the source 
of what I consider the misconception some of us are having.)
I don't have this "misconception".  I basically agree with this and 
don't think I said anything explicitly contradictory to this.




The other source of the misconception you also touched on.  You
mentioned "enormous extra time", which is correct.  It DOES INDEED
require enormous extra time,  even in computer chess to make
anything more than a modest improvement.The reason you just
can't imagine that "a lot" of extra time will help you play a
better move is because most of the time it won't!   Your 
intuition is correct but your conclusion is incorrect.   
You are putting words into my posts.  As I said several times already I 
am not claiming extra time won't help improve play.  Of course it will. 
 You are not listening to my conclusion.  Step back and re-read my 
posts.  I don't claim my writing to be of super clarity and I might not 
be explaining myself well enough, but why not try to keep an open mind 
and not make assumptions about things I didn't write.




The improvement will come only from little mundane improvements
of a very small number of moves - but that is enough to make
your level of play go up a  bit.

Yes and improvement may also come from other insights as well.



Please note that for weak players,  a LOT of moves need to be
improved, and for strong players only a few need to be improved.
But the way this works is that the stronger you get,  the 
more impact improving just a few moves makes because your

opponent is more likely to take advantage of your mistakes.

Sounds reasonable.


Someone once did a computer chess experiment with really long
and deep searches and they studied how often computers "changed
their minds" when making moves.   As it turns out,  the rate
of change (per ply or per doubling) tapers off as you go deeper
and deeper.And yet the strength improvement is almost
the same for each doubling. 
But I' not talking about computers or chess. I think there is already a 
consensus that the doubling rule holds well in chess.  You don't have to 
continue to convince me of that.



The computers follow your cognitive intuition that you posted
about,  they can think for an enormous amount of time and still
not improve on the move.Improvement isn't about making ALL the
moves better, only a few.   It's almost always possible, given
more time, to find some improvements in a few of your moves
and this is what makes you play better.

Yes. You are repeating yourself.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[terry mcintyre]

let's step back a bit and define terms. How do we define "a linear improvement 
in Go"?

Would that be a linear increase in ELO points, or what?
 
Terry McIntyre




 

Want to start your own business?
Learn how on Yahoo! Small Business.
http://smallbusiness.yahoo.com/r-index___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Matt Gokey]

terry mcintyre wrote:
let's step back a bit and define terms. How do we define "a linear 
improvement in Go"?

Don can correct me if I'm wrong,

The hypothesis is: For any player rating each doubling of thinking time 
creates a rating increase by a fixed constant value.




Would that be a linear increase in ELO points, or what?

Yes, but I suppose any presumably valid rating system.

Of course this is an approximation since both rating systems and 
thinking effectiveness are not precise measures.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Don Dailey]

On Thu, 2007-01-25 at 20:16 -0600, Matt Gokey wrote:
> Don Dailey wrote:
> > You are still missing the point. 
> I can say the same of you.
> 
> I merely am raising a question about the assertion that doubling of 
> _human_ thinking time results in _linear_ improvements. I am not 
> claiming that there is no improvement - never have.  I am not claiming 
> that every turn must produce better results to improve overall play - 
> never have.  However I am trying to explain a rationale for the 
> possibility that improvements may not be linear based on the nature of Go.

It's possible,  but I think my curve (it is a curve, it gradually tapers
off as you get closer to perfection which is an obvious limit)  holds 
in all non-trivial games of perfect information.   The curve may have
a different shape or slope but it's there.  

It's already easy to produce in computer go despite a reluctance by
many (not you of course) to  admit it.   My sense is that 
many on this group want to believe that we just happen to be at the
top of the curve but that it immediately falls off.   There is no
rational reason to believe that other than superstition. 

> > What you are describing looks great on paper,  but that's now how
> > the extra time works.   Even if you are given 10X more time,  the
> > benefit will come from not from suddenly being able to grasp master
> > level concepts, but from repairing the little mundane problems 
> > that  are just within your reach.
> How do you know this? Improvements could come from many other different 
> sources.

I thought I was being generous.  I do believe 10 or 20x is enough time
to produce a lot of mini-conceptual breakthroughs.But I know from
my experience in game programming that most of the improvement comes
from fixing all the misconceptions that 1 less ply couldn't see.  

When I was young and naive about computer chess,  I couldn't understand
why going from 5 to 6 ply was almost as good as going from 3 to 4 ply,
but it's clearly the case.A lot of very strong players never got
over this type of incorrect thinking - they only focused on what a
computer COULDN'T do with only 1 extra ply (or double the time.)

> > 
> > And it will only effect a small number of moves.   Most of the
> > moves will be exactly as you say, confusing, and you will not be
> > able to improve them (and I think this is the partly the source 
> > of what I consider the misconception some of us are having.)
> I don't have this "misconception".  I basically agree with this and 
> don't think I said anything explicitly contradictory to this.

That's why I used the terminology "some of us",  I would have said
"you are having" if I thought it was your stance.

> > 
> > The other source of the misconception you also touched on.  You
> > mentioned "enormous extra time", which is correct.  It DOES INDEED
> > require enormous extra time,  even in computer chess to make
> > anything more than a modest improvement.The reason you just
> > can't imagine that "a lot" of extra time will help you play a
> > better move is because most of the time it won't!   Your 
> > intuition is correct but your conclusion is incorrect.   
> You are putting words into my posts.  As I said several times already I 
> am not claiming extra time won't help improve play.  Of course it will. 
>   You are not listening to my conclusion.  Step back and re-read my 
> posts.  I don't claim my writing to be of super clarity and I might not 
> be explaining myself well enough, but why not try to keep an open mind 
> and not make assumptions about things I didn't write.

To an extent I admit that I was putting words in your mouth.  I was in
the mode where I was responding to the group as a whole even though
I was really addressing you more specifically.You never said, "you
can't imagine that a lot of extra time would help" so I apologize 
for being so loose with this.
 

> > The improvement will come only from little mundane improvements
> > of a very small number of moves - but that is enough to make
> > your level of play go up a  bit.
> Yes and improvement may also come from other insights as well.

I agree, but for a modest amount of extra time, to be frank, you
will be making far less errors and still playing pretty much the
same perhaps with a  few exceptions.   With a LOT of extra
time I believe you will be having insights and really "finding"
a few nice moves.   I believe go is rich in opportunities to 
do this,  and I completely disagree with those that feel the
game is closed beyond what you can quickly recognize and there
is no scope to discover interesting things because it's just
too complicated and confusing.

> > Please note that for weak players,  a LOT of moves need to be
> > improved, and for strong players only a few need to be improved.
> > But the way this works is that the stronger you get,  the 
> > more impact improving just a few moves makes because your
> > opponent is more likely to take advantage of your mi

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

[Matt Gokey]

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/

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

[Don Dailey]

On Thu, 2007-01-25 at 21:44 -0600, Matt Gokey wrote:
> 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.

I think this is a case where our gut feelings are not particularly 
reliable.I've already discussed several reasons why we might be 
led falsely to believe our strength is pretty much fixed, but I'll
just summarize here: 

  1. How we perceive time.

  2. The ranking system which puts us in a box. 

  3. Undo worship of stronger players.

  4. Broken cognitive model of what it takes to play a
 better game.

- Don

   

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Don Dailey]

On Thu, 2007-01-25 at 21:40 -0600, Matt Gokey wrote:
> terry mcintyre wrote:
> > let's step back a bit and define terms. How do we define "a linear 
> > improvement in Go"?
> Don can correct me if I'm wrong,
> 
> The hypothesis is: For any player rating each doubling of thinking time 
> creates a rating increase by a fixed constant value.
> 
> > 
> > Would that be a linear increase in ELO points, or what?
> Yes, but I suppose any presumably valid rating system.
> 
> Of course this is an approximation since both rating systems and 
> thinking effectiveness are not precise measures.

ELO ratings are a very convenient statistical mechanism to predict
performance between any 2 players.  If you are 200 ELO higher than
someone, you are expected to win about 3 out of 4 games.   

Although I claimed a linear improvement in ELO for each factor of X
time increase,  I do believe there is a very gradual fall-off as
you get closer to perfection. This has been shown empirically
with chess.It follows that this would happen in GO too.   I
believe the fall-off in go is much more gradual (just the opposite
naturally of what many on this group are claiming)  because it's
a richer game strategically.  

- Don



> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Arend Bayer]

Hi Don,

On 1/25/07, Don Dailey <[EMAIL PROTECTED]> wrote:


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.

I think this is a case where our gut feelings are not particularly
reliable.I've already discussed several reasons why we might be
led falsely to believe our strength is pretty much fixed, but I'll
just summarize here:



I have to admit it is sometimes getting tiresome to continue to read some of
your (in my mind) misconceptions about go, in particular when you always
continue to push them because it is such-and-such in chess etc. without ever
believing anything that some of the strong go players (some a lot stronger
than me) have to say.

I am EGF 4D. A friend of mine is EGF 6D. When I show him the opening of a
game and some moves that I have thought quite some time during the game, and
then some more time while reviewing the game -- then often he can still tell
me immediately how I have been wrong, and explain me why. But of course that
is just "undo worship of stronger players". If a 6D shows one of his games
to a pro, again the pro will be able to tell him some mistakes in direction
in judgements by only giving the game a very quick glance.

I am not sure why I am explaining this, since you will dismiss such
experience anyway due to some odd consideration that has nothing to do with
any go experience. Btw among go players around my strength I probably
believe more than most in substantial improvements by longer thinking times
- but it is still very small compared to the standard deviation of strength
among the amateur go population. (Which is a much better scale when you want
to compare strength differences for added thinking time between go and
chess, rather than ELO, in my opinion.)

Arend
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/