Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Rémi Coulom]

Chrilly wrote:
I think on 9x9 the superiority of search based programms is now 
clearly demonstrated. Its only the question if UCT or Alpha-Beta is 
superior.

Hi Chrilly,

Thanks for your report.

The question of UCT versus Alpha-Beta is not open any more in my 
opinion. The current state of the art of Monte Carlo tree search is 
about 500 Elo points stronger than the version of Crazy Stone you tested 
against. Do you believe you can easily catch up with those 500 Elo 
points ? Also, I am convinced that UCT has tremendous potential for 
further improvement. I have improved Crazy Stone by about 50 Elo points 
per day in the past 10 days (on 9x9. The improvement on 13x13 and 19x19 
is much more). I am very confident that I can easily improve it further 
very much.


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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Tom Cooper]

My guess is that the complexity of achieving a fixed standard of play 
(eg 1 dan) using a global alpha-beta or MC search is an exponential 
function of the board size.  For this guess, I exclude algorithms 
that have a tactical or local component.  If this guess is correct 
then, even if Moore's law remains in force, this kind of program 
should not reach dan level on a 19x19 board within 20 years.


To some extent, this is testable today by finding how a global search 
program's strength scales with board size and with thinking 
time.  For example, results in which Suzie had a week to play a 13x13 
game would be interesting.


I don't mean to imply by this message that I think I am particularly 
well qualified to have an opinion on this matter, but when someone 
writes something that surprises me, I'm inclined to argue :)





On 13x13 and especially 19x19 Suzie is still weaker than Gnu-Go. I 
think the hardware is still too weak to establish the same dominance 
of search for larger board-sizes. But thats only a matter of time or 
of a few million $ to build (with Chris Fant) a Go-Chip. Actually 
about 100.000 Euro for an FPGA based project would be sufficient.


Chrilly Donninger



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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

I would not be so quick to dismiss what Chrilly is saying.  I have
noticed that over time, in science, things blend together.   For 
instance mtd(f) is a systematic way to think of aspiration search,
(tampering with the alpha/beta window  in a search) and helps us to
appreciate how they are all pretty much variations of the same
basic concepts.

I noticed a trend in computer chess towards throwing out more and
more moves.  Years ago it was only alpha/beta pruning but then later
null move pruning, then other kinds of pruning and now the tree 
is being cut in many places.   Chess search trees now look much
more like the intial (highly selective) approach that was rejected 
just a few decades ago.

UCT and Monte Carlo.   It's not as much Monte Carlo any longer.
It's turning more into an evaluation function.  When it first 
started the 
play-outs were random, now they are semi random - essentially
forming a binary evaluation function.  In fact they ARE a binary
evaluation function - since that exact node will never have this
function directly applied to it again (with the standard UCT
formulation.)

So what we have is a best first search with an evaluation function!

(I would still argue that some randomness is important - but I can't
explain why in this email but a clue:  it has to do with recovering
from misconception if you can figure that out!) 

If you look at what mtd(f) is,  it's not alpha/beta, it's more like
a hybrid - a best first search that iterates.   But it's only a  hop,
skip, and jump away from standard alpha/beta.

It's not hard to imagine that with work,  the Chrilly approach will
start looking more like the UCT approach.   After all, if anything,
things 
have moved more TOWARDS the Chrilly approach and away from the initial
things we tried in UCT/monte/carlo.

Mabye in a few years we will look back and see that we started from a
lot of different places and ended up at the same location.This 
happens all the time in science.  

In my opinion, the insight that Chrilly articulated was that all of
sudden we are now all using some type of global search - the very
idea was considered blasphemy just 2 or 3 years ago.  

- Don



On Fri, 2007-04-06 at 13:54 +0200, Rémi Coulom wrote:
> Chrilly wrote:
> > I think on 9x9 the superiority of search based programms is now 
> > clearly demonstrated. Its only the question if UCT or Alpha-Beta is 
> > superior.
> Hi Chrilly,
> 
> Thanks for your report.
> 
> The question of UCT versus Alpha-Beta is not open any more in my 
> opinion. The current state of the art of Monte Carlo tree search is 
> about 500 Elo points stronger than the version of Crazy Stone you tested 
> against. Do you believe you can easily catch up with those 500 Elo 
> points ? Also, I am convinced that UCT has tremendous potential for 
> further improvement. I have improved Crazy Stone by about 50 Elo points 
> per day in the past 10 days (on 9x9. The improvement on 13x13 and 19x19 
> is much more). I am very confident that I can easily improve it further 
> very much.
> 
> Rémi
> ___
> 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] The dominance of search (Suzie v. GnuGo)

[compgo123]

When it comes to a search, one need to ask that is my evaluation function 
perfect? If not (in almost all cases), why should one use a search algorithm 
that assumes the evaluation function is perfect? UCT can work with an imperfect 
evaluation function. A perfect answer can be obtained if the evaluation 
function is perfect. In this case there is no significant difference between 
UCT and alpha-beta. However, this does not take into account of the possibility 
of the existence of an underlying structure in the evaluation values. This 
underlying structure is not exployed in alpha-beta. It is to some extent in a 
width first algorithm.
 
Right now the significance of MC scoring is still a somewhat mystry. Also no 
one has mentioned what the search depths are for the UCT groprams.
 
 
-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Fri, 6 Apr 2007 6:54 AM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)


Chrilly wrote: 
> I think on 9x9 the superiority of search based programms is now > clearly 
> demonstrated. Its only the question if UCT or Alpha-Beta is > superior. 
Hi Chrilly, 
 
Thanks for your report. 
 
The question of UCT versus Alpha-Beta is not open any more in my opinion. The 
current state of the art of Monte Carlo tree search is about 500 Elo points 
stronger than the version of Crazy Stone you tested against. Do you believe you 
can easily catch up with those 500 Elo points ? Also, I am convinced that UCT 
has tremendous potential for further improvement. I have improved Crazy Stone 
by about 50 Elo points per day in the past 10 days (on 9x9. The improvement on 
13x13 and 19x19 is much more). I am very confident that I can easily improve it 
further very much. 
 
Rémi 
___ 
computer-go mailing list 
computer-go@computer-go.org 
http://www.computer-go.org/mailman/listinfo/computer-go/ 

AOL now offers free email to everyone.  Find out more about what's free from 
AOL at AOL.com.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Erik van der Werf]

On 4/6/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:

When it comes to a search, one need to ask that is my evaluation function
perfect?


There are exceptional cases in the late endgame and on tiny boards,
but in general this is not an interesting question (because it
obviously won't be perfect).

In my opinion the question should be: is the evaluation function of a
probabilistic nature.

Alpha/Beta cutoffs only make sense when calling the evaluation
function twice on the exact same position can be guaranteed to provide
the exact same value. This is obviously not the case for MC
evaluation, hence the success of UCT.

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[compgo123]

An imperfect evaluation has errors. Is the exact value of the error known? No. 
Thus, it's random. :)
 
Daniel Liu
 
 
-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Fri, 6 Apr 2007 10:57 AM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)


On 4/6/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: 
> When it comes to a search, one need to ask that is my evaluation function 
> perfect? 
 
There are exceptional cases in the late endgame and on tiny boards, 
but in general this is not an interesting question (because it 
obviously won't be perfect). 
 
In my opinion the question should be: is the evaluation function of a 
probabilistic nature. 
 
Alpha/Beta cutoffs only make sense when calling the evaluation 
function twice on the exact same position can be guaranteed to provide 
the exact same value. This is obviously not the case for MC 
evaluation, hence the success of UCT. 
 
Erik 
___ 
computer-go mailing list 
computer-go@computer-go.org 
http://www.computer-go.org/mailman/listinfo/computer-go/ 

AOL now offers free email to everyone.  Find out more about what's free from 
AOL at AOL.com.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chrilly]

Don Daily wrote
I noticed a trend in computer chess towards throwing out more and
more moves.  Years ago it was only alpha/beta pruning but then later
null move pruning, then other kinds of pruning and now the tree
is being cut in many places.   Chess search trees now look much
more like the intial (highly selective) approach that was rejected
just a few decades ago.


Yes, the current chess-searches are not anymore brute force at all. E.g. the 
History Heuristic as its implemented selects basically the first k (k==3) 
moves. But in contrast to the original pruning methods its "soft-pruning". 
The search depth of the remaining moves is reduced by R (R==1). An incorrect 
pruning decission is not taken "forever".  The general idea is to use 
information from the search tree to shape the search tree. Ulf Lorenz from 
the Univ. Paderborn considers the search tree as an adaptable error filter.


In Suzie we (Peter Woitke, Stefan Mertin and Chrilly) use Null-Move Pruning, 
Multi-Cut and Futility Pruning. History Pruning does not work so far. 
move-ordering is not very good and the History-Heurisitic relies on  the 
fact, that the k+1...n-th have a very low probability to generate a cutoff. 
The poor move-ordering is related to a significant odd-even effect. Suzie 
evaluates the last move too high. In chess the simple "capture the highest 
piece with the lowest one" (MVLV) rule is very effective and simple. There 
is no similar simple rule in Go. This has also a major impact on search 
efficiency.
Suzie searches currently about 10KNodes/sec. The typical search depth is 7. 
This is for 9x9 not very impressive. With better move-ordering depth 8-9 
should be possible.


A major problem is quiescence search. We have not found so far a simple and 
efficient rule. Either the rule is too selective or the quiescence explodes. 
Again in chess MVLV is very effective. Each capture reduces the search tree 
and the quiescence-search terminates by itself. Generating just captures is 
in Go not sufficient. The tactical searcher in the evaluation takes captures 
already into account. But if one generates forcing moves like e.g. 
building/destroying 2-eyes, semiais ... there is no natural termination 
limit.


Another surprising result is, that we have found so far no reasonable 
search-extensions. This is related to the relative unstable evaluation. The 
programm gets too much possibilities to "cheat". But this should hold also 
for the pruning techniques. The pruning methods have a clear positive 
effect. Depth 7 means, Suzie searches at most 8 Plies (7 normal and 1 
quiescence-moves). In chess a 7 Ply search can also 15 Plies long.



UCT and Monte Carlo.   It's not as much Monte Carlo any longer.
Yes, ecaxtly. I also think that the difference is fuzzy. Both methods fit 
into the adaptable error filter model of Ulf.


Chrilly

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chrilly]

Thanks for your report.

The question of UCT versus Alpha-Beta is not open any more in my
opinion. The current state of the art of Monte Carlo tree search is
about 500 Elo points stronger than the version of Crazy Stone you tested
against. Do you believe you can easily catch up with those 500 Elo
points ? Also, I am convinced that UCT has tremendous potential for
further improvement. I have improved Crazy Stone by about 50 Elo points
per day in the past 10 days (on 9x9. The improvement on 13x13 and 19x19
is much more). I am very confident that I can easily improve it further
very much.

Rémi

The main point of my mail was: Search works (at least in 9x9) well. I think 
we can agree on this point.


For the UCT v. Alpha-Beta question there is a simple proof of the pudding: 
Sent us the latest/strongest version and we will try to beat it.


Suzie is so far a very propretiary system which runs only under GoAheads 
GUI. And GoAhead does not support GTP. GnuGo is run with a hack. The matches 
against Crazy-Stone are done by hand. Its Stefan Mertins version of watching 
TV.
I am working currently on a modern C# based GUI which shall support also 
GTP. But progress is due to my engagement by Siemens rather slow***. Once 
this GUI exists we will be able to participate on KGS tournaments and other 
programmers could get Suzie if they like.


*** I have also done almost nothing to improve the search, the main progress 
is due to Peters intensive work on the evaluation.


Chrilly

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chrilly]

Some factors could be already gained on existing hardware. E.g. Suzie has 
currently no parallel search. Even permanent brain (thinking in the 
opponents time) is not implemented.
Suzies evaluation has also a local tactical search. Things are exponential, 
but the exponential factor is not so terrible. Modern Alpha-Beta is not 
brute-force anymore but rather selective.
Additionally so far the effort has been devoted to improve knowledge. Global 
chess like search is still in its infancy. In case of UCT there was an real 
explosion in the last time. Its - like in chess - a combination of stronger 
hardware and better methods. I think in 20 years the programms will even on 
19x19 knock on the professional-Dans doors. Similar to the situation in 
chess end of the 1980ths when the first GMs were beaten, but the programms 
were not yet on GM level. Or in other words, Go is now about in 1970.


Chrilly

- Original Message - 
From: "Tom Cooper" <[EMAIL PROTECTED]>

To: "computer-go" 
Sent: Friday, April 06, 2007 2:43 PM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)


My guess is that the complexity of achieving a fixed standard of play (eg 
1 dan) using a global alpha-beta or MC search is an exponential function 
of the board size.  For this guess, I exclude algorithms that have a 
tactical or local component.  If this guess is correct then, even if 
Moore's law remains in force, this kind of program should not reach dan 
level on a 19x19 board within 20 years.


To some extent, this is testable today by finding how a global search 
program's strength scales with board size and with thinking time.  For 
example, results in which Suzie had a week to play a 13x13 game would be 
interesting.


I don't mean to imply by this message that I think I am particularly well 
qualified to have an opinion on this matter, but when someone writes 
something that surprises me, I'm inclined to argue :)





On 13x13 and especially 19x19 Suzie is still weaker than Gnu-Go. I think 
the hardware is still too weak to establish the same dominance of search 
for larger board-sizes. But thats only a matter of time or of a few 
million $ to build (with Chris Fant) a Go-Chip. Actually about 100.000 
Euro for an FPGA based project would be sufficient.


Chrilly Donninger



___
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] The dominance of search (Suzie v. GnuGo)

[Rémi Coulom]

Chrilly wrote:
The main point of my mail was: Search works (at least in 9x9) well. I 
think we can agree on this point.


Yes.



For the UCT v. Alpha-Beta question there is a simple proof of the 
pudding: Sent us the latest/strongest version and we will try to beat it.


I do not plan to distribute new versions any more. But I will connect 
Crazy Stone to the servers, CGOS and KGS.


I believe MonteGNU might be available. It is stronger on 9x9 than both 
GNU Go, and the public versions of Crazy Stone.


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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

On Fri, 2007-04-06 at 12:43 -0400, [EMAIL PROTECTED] wrote:
> Alpha/Beta cutoffs only make sense when calling the evaluation 
> function twice on the exact same position can be guaranteed to
> provide 
> the exact same value. This is obviously not the case for MC 
> evaluation, hence the success of UCT. 

I don't know if any of this is true.  You can apply alpha beta
cutoffs whether the evaluation function is deterministic or not.

UCT calls the "random play-out" only once on any given position
and there is no reason in principle that it couldn't be a 
deterministic evaluation function instead.  I have a theory
that the search is more robust with some randomness since
deterministic evaluation functions have misconceptions.

It's all in how you choose to view things - but I see the
two search techniques as being more similar than different.   
Of course you can choose to emphasize the differences and 
view them as more different if you want to.

Here is how they are similar:

  1.  Both use global search.
  2.  Both use full width search.
  3.  Both use an evaluation function.


UCT uses a "different" search - but they are both essentially
mini-max search.   

Someone might argue that UCT is NOT full width, but it is.  
Chrilly used the terminology "soft-pruning" which means a
pruning decision is not taken "forever" (to use his definition.)

To me, a true selective program cuts of a line forever.   Otherwise
it is brute force (or full width.)   Of course this is my definition,
and possibly not the accepted definition.

When Chrilly says alpha beta he doesn't mean just classical
alpha beta - modern alpha beta is full of speculative cutoffs,
but like UCT they "are not taken forever."

It's not relevant whether Chrilly's program happens to be weaker
or stronger than Crazy Stone at the moment - because there is lot of
black art in making everything work whether it's alpha beta or
UCT.   Note that the UCT programs are not the same - they widely
vary in how strong they are.

I have this idea that perhaps a good evaluation function could
replace the play-out portion of the UCT programs.  The evaluation
function would return a value between 0 and 1 and would be an
estimate of the odds of winning.

It only comes down to whether the inherent randomness is critical
to the success of UCT or not.   If it isn't,  then a play-out is
nothing more than just an evaluation function.

- Don







 

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

On Fri, 2007-04-06 at 19:40 +0200, Chrilly wrote:
> A major problem is quiescence search. We have not found so far a
> simple and 
> efficient rule. Either the rule is too selective or the quiescence
> explodes. 
> Again in chess MVLV is very effective. 

Of course the best programs have improved on this signficantly.  Most
valuable
victim least valuable attacker works amazingly well with no other
information
available,  but the good programs now analyze to see if a capture is a
losing
capture by doing some kind of SEE (static exchange evaluator.)   I was 
surprised at the huge efficiency this gave my chess program.  It was
like a
brand new program when I discovered this.  Even if SEE is not
particularly
well implemented this works extremely well.  

I assume suzie either does this already, or if it doesn't it's because
it's
hard to implement efficiently with your hardware.   

> Each capture reduces the search tree 
> and the quiescence-search terminates by itself. Generating just
> captures is 
> in Go not sufficient. The tactical searcher in the evaluation takes
> captures 
> already into account. But if one generates forcing moves like e.g. 
> building/destroying 2-eyes, semiais ... there is no natural
> termination 
> limit. 

In go it's all messed up - no simple self-terminating rules.  There is
one idea - only deal with what was there before the quies search began.
Limit what you are trying to discover to the groups that existed at
the point the quies search began.   I don't really know if it works
or not - but it does follow the principle of "tapering", where more
focus is spent on early decisions (more pruning close to leaf nodes,
less pruning near root nodes.)

A similar idea in chess was to look at all captures in the first N ply
of quies, then only look at recaptures (and possibly up-captures.) 

- Don


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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Erik van der Werf]

On 4/6/07, Don Dailey <[EMAIL PROTECTED]> wrote:

On Fri, 2007-04-06 at 12:43 -0400, [EMAIL PROTECTED] wrote:
> Alpha/Beta cutoffs only make sense when calling the evaluation
> function twice on the exact same position can be guaranteed to
> provide
> the exact same value. This is obviously not the case for MC
> evaluation, hence the success of UCT.

I don't know if any of this is true.


Noticed the subtle "can be" in my statement above?

I'm quite aware of all the hairy details (e.g., strictly speaking the
use of a transposition table already voids the above premise).


You can apply alpha beta
cutoffs whether the evaluation function is deterministic or not.


I know quite well how alpha-beta is used in practice, but that's not
the point I tried to get across. The cool thing of alpha-beta cutoffs
is that, under certain conditions, it is guaranteed to preserve the
minimax result without searching the full tree. However, if the
evaluation function is non-deterministic that guarantee simply doesn't
make sense any more. I'm not saying that therefore alpha-beta can't be
used; in fact I'll be the first to admit that you can apply it to
*any* domain with a finite number of known legal actions. Not that
that's a good plan, but for sure you will always get something out. In
many games it will even play quite well. In practice pathology in
search is known to be rare, however, my impression is that in Go it
may be more relevant than in other games, such as chess, where, e.g.,
noise actually helps as a weak mobility component. UCT was
specifically designed to deal with uncertainty, so that's why I think
it's better suited for highly uncertain evaluations .


UCT calls the "random play-out" only once on any given position
and there is no reason in principle that it couldn't be a
deterministic evaluation function instead.


Sure, and you could even argue that the "random play-out" *is*
deterministic. Fact remains that the uncertainty/variance of one
playout is in most cases still huge, and the tree-search has to deal
with this (or in Chrilly's words, filter it). Unless the fake mobility
is helping significantly, this could be a severe disadvantage for
alpha-beta type searchers compared to UCT.


To me, a true selective program cuts of a line forever.


I would call that a greedy algorithm (because it never reconsiders
previous decisions).


I have this idea that perhaps a good evaluation function could
replace the play-out portion of the UCT programs.


Agreed.


It only comes down to whether the inherent randomness is critical
to the success of UCT or not.   If it isn't,  then a play-out is
nothing more than just an evaluation function.


My guess is that the answer which type of search works best for a
given evaluation function depends on the amounts of (deterministic)
bias and (probabilistic) uncertainty in the evaluations (and so far I
see MC mainly as an extremely noisy evaluation with not too much
systematic bias).

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

On Fri, 2007-04-06 at 23:41 +0200, Erik van der Werf wrote:
> My guess is that the answer which type of search works best for a
> given evaluation function depends on the amounts of (deterministic)
> bias and (probabilistic) uncertainty in the evaluations (and so far I
> see MC mainly as an extremely noisy evaluation with not too much
> systematic bias).

It's interesting that Sylvain seems to consider the stronger Mogo
versions more brittle in some sense.   He claimed (in so many
words) that Lazarus gets results more consistent with it's ratings
and that the strongest Mogo's do not.I wonder if this is 
because the play-outs are now more systematically biased?  

- Don


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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

I want to clarify however.

If your evaluation function is not deterministic,  aspiration
search techniques become very dicey.This is a problem
anyway with hash table implementations and speculate cutoffs
based on the the alpha beta window (and especially the
aspiration window) but it's worth mentioning.

However, there is nothing wrong with using alpha beta
search with an evauation function that is not deterministic.

- Don


On Fri, 2007-04-06 at 16:24 -0400, Don Dailey wrote:
> On Fri, 2007-04-06 at 12:43 -0400, [EMAIL PROTECTED] wrote:
> > Alpha/Beta cutoffs only make sense when calling the evaluation 
> > function twice on the exact same position can be guaranteed to
> > provide 
> > the exact same value. This is obviously not the case for MC 
> > evaluation, hence the success of UCT. 
> 
> I don't know if any of this is true.  You can apply alpha beta
> cutoffs whether the evaluation function is deterministic or not. 

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Erik van der Werf]

On 4/6/07, Don Dailey <[EMAIL PROTECTED]> wrote:

However, there is nothing wrong with using alpha beta
search with an evauation function that is not deterministic.


I agree that some limited amount of non-determinism isn't necessarily
a bad thing, and in some cases it actually helps (e.g., when mobility
is important, or to avoid the exploitation of repeatable blunders).
However, do you really believe that this still holds if the variance
causes a spread over the maximum range of possible values of the
underlying ground-truths?

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Darren Cook]

> (R==1). An incorrect pruning decission is not taken "forever".  The
> general idea is to use information from the search tree to shape the
> search tree. Ulf Lorenz from the Univ. Paderborn considers the search
> tree as an adaptable error filter.
> ...
>> UCT and Monte Carlo.   It's not as much Monte Carlo any longer.
> Yes, ecaxtly. I also think that the difference is fuzzy. Both methods
> fit into the adaptable error filter model of Ulf.

Hi Chrilly,
Do you have a recommendation for a good paper to read on this? Ideally
one that doesn't need specialized chess knowledge to appreciate, but I
may not have a choice: google is giving me 0 hits on "adaptable error
filter".

Darren


-- 
Darren Cook
http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
http://dcook.org/work/ (About me and my work)
http://dcook.org/work/charts/  (My flash charting demos)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

On Sat, 2007-04-07 at 01:12 +0200, Erik van der Werf wrote:
> On 4/6/07, Don Dailey <[EMAIL PROTECTED]> wrote:
> > However, there is nothing wrong with using alpha beta
> > search with an evauation function that is not deterministic.
> 
> I agree that some limited amount of non-determinism isn't necessarily
> a bad thing, and in some cases it actually helps (e.g., when mobility
> is important, or to avoid the exploitation of repeatable blunders).
> However, do you really believe that this still holds if the variance
> causes a spread over the maximum range of possible values of the
> underlying ground-truths?

I don't understand your question.   I don't claim non-determinism
helps with alpha beta and I'm not recommending a fuzzy evaluation
function, I'm just saying it still works.  A deeper search will
produce better moves in general.

If you build a big tree and attach a score to all end nodes, 
the alpha beta mini-max procedure does not care how those
nodes got their score.If the scores bear some resemblance
to reality, the search will probably return a relatively good
move.   Even if the scores are random, it could help if the
game is of the nature that maximizing your options is a good
thing - which is probably most games.  

Some randomness may have other advantages.  My theory is that 
in UCT, if your playouts have no randomness,  the search could
be locked into a deep conceptual misunderstanding that cannot
be recovered from.   This would be true of UCT constructed
with a deterministic evaluation function.   But it's only a
theory of mine.   

With alpha beta it's tricker, randomness introduces some 
difficulties that reduce the efficiency of alpha beta pruning
and make good move ordering more difficult.

- Don
 

> Erik

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chrilly]

I have this idea that perhaps a good evaluation function could
replace the play-out portion of the UCT programs.  The evaluation
function would return a value between 0 and 1 and would be an
estimate of the odds of winning.

I have tried this with an older and much weaker version of Suzie. It played 
positionally better than the Alpha-Beta version, but the rate of very 
strange moves also increased. UCT greates a more unbalanced tree than 
Alpha-Beta and the programm has therefore even more chances to "cheat". For 
the same reason extensions do not work so far in Suzie.


But I tried not with 0-1 but used the full eval. Maybe I should give it a 
second try. But as I work now 45 hours/week on Computer-Tomography (which is 
also quite interesting) and comute each weekend between Germany and Austria 
its difficult to do.


Chrilly

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

To take a normal evaluation function and convert it to a 
"probability of winning" function is probably difficult to 
do well.   You might have to map some sort of curve where
a few stones ahead represent a near win.

A simple approximation: - call the evaluation function - if
it is less than zero, consider it one monte carlo run where
white wins.If it's greater than zero, consider it a 
monte carlo run where black wins.   

It's probably better to use the curve - but my sense of it
is that you need to map scores fairly accurately to odds
of winning - to truly simulate a monte carlo run.

How did you do this before?  I think almost any reasonable
idea is worth 2 or 3 tries - the devil is in the details.

- Don


 

On Sat, 2007-04-07 at 19:52 +0200, Chrilly wrote:
> >
> > I have this idea that perhaps a good evaluation function could
> > replace the play-out portion of the UCT programs.  The evaluation
> > function would return a value between 0 and 1 and would be an
> > estimate of the odds of winning.
> >
> I have tried this with an older and much weaker version of Suzie. It
> played 
> positionally better than the Alpha-Beta version, but the rate of very 
> strange moves also increased. UCT greates a more unbalanced tree than 
> Alpha-Beta and the programm has therefore even more chances to
> "cheat". For 
> the same reason extensions do not work so far in Suzie.
> 
> But I tried not with 0-1 but used the full eval. Maybe I should give
> it a 
> second try. But as I work now 45 hours/week on Computer-Tomography
> (which is 
> also quite interesting) and comute each weekend between Germany and
> Austria 
> its difficult to do.
> 
> Chrilly
> 

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chrilly]

I don't understand your question.   I don't claim non-determinism
helps with alpha beta and I'm not recommending a fuzzy evaluation
function, I'm just saying it still works.  A deeper search will
produce better moves in general.

One has the randomness anyway. A heuristic evalution can be considered as 
the sum of a systematic term which is an estimator of the "true" evaluation 
and an error term (and a bias).
One consequence of this model is, that the shape of the search tree has a 
significant influence on the evaluation. The programm will favour variations 
where it has a lot of good moves and the opponent has only a few. Because 
the more (good) moves the program has, the higher is the expected value of 
the error terms. The programm has more tickets in the error-term lottery.


I have noticed this effect constantly.  E.g. if one extends captures, the 
programm tends to favour lines with captures, if one extends checks 
stronger, the program likes to check...


Chrilly

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chrilly]

There is a chapter in Ulf Lorenz Dissertation about this topic. Ulf mentions 
this aspect also in  the Hydra papers. E.g. the one for the XCell Journal. 
Search on the net for "Lorenz, Donninger, Hydra" and format "pdf". But in 
this papers the concept is only mentioned without a detailed 
proof/explanation. This is only done in the Diss.
The title of the Diss. is: Ulf Lorenz: Controlled Conspiracy Number Search, 
Paderborn 2000. But the work is in German.
After the match Adams-Hydra Ulf wrote a longer article about his 
error-filter theory for the ICGA-journal. But the article was rejected.


Ulf has used this model for a project to improve the robustness of 
airplane-schedules. The current algorithms just optimize the scheduling of 
airplanes (and the crew), but they have usually no notation of robustness. 
If there is a delay in London, then the flight Frankfurt Paris might be 
delayed too, because according the schedule the airplane is used after the 
return from London in Frankfurt for the Paris fligth. And this can in turn 
delay the flight from Paris to Madrid, because the crew has now - according 
the law - to take a rest in Paris, but the scheduling programm calculated 
that its optimal that they are also on board for Paris-Madrid and take the 
rest in Madrid
One can consider the time according schedule as a noisy evaluation function 
and can try to find more robust solutions which is not much worse than the 
best solution. Its a conspiracy approach for scheduling problems.


Chrilly

- Original Message - 
From: "Darren Cook" <[EMAIL PROTECTED]>

To: "computer-go" 
Sent: Saturday, April 07, 2007 2:18 AM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)



(R==1). An incorrect pruning decission is not taken "forever".  The
general idea is to use information from the search tree to shape the
search tree. Ulf Lorenz from the Univ. Paderborn considers the search
tree as an adaptable error filter.
...

UCT and Monte Carlo.   It's not as much Monte Carlo any longer.

Yes, ecaxtly. I also think that the difference is fuzzy. Both methods
fit into the adaptable error filter model of Ulf.


Hi Chrilly,
Do you have a recommendation for a good paper to read on this? Ideally
one that doesn't need specialized chess knowledge to appreciate, but I
may not have a choice: google is giving me 0 hits on "adaptable error
filter".

Darren


--
Darren Cook
http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
http://dcook.org/work/ (About me and my work)
http://dcook.org/work/charts/  (My flash charting demos)
___
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] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

On Sat, 2007-04-07 at 20:43 +0200, Chrilly wrote:
> I have noticed this effect constantly.  E.g. if one extends captures,
> the 
> programm tends to favour lines with captures, if one extends checks 
> stronger, the program likes to check... 

To bad you cannot extend checkmates. I want my
program to like to give checkmate!

- Don


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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Jacques Basaldúa]

Don Dailey wrote:


I have this idea that perhaps a good evaluation function could
replace the play-out portion of the UCT programs.


I thought about something similar but only for initializing the 
counters: introduce 10 fake playouts and estimate the number of
wins by a function returning something in [0, 10]. After that, 
use UCT with real playouts.


If your guess was right, that should improve performance, but if
it was wrong you are doing nothing irreversible except loosing 
time.



Jacques.


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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chris Fant]

> I have this idea that perhaps a good evaluation function could
> replace the play-out portion of the UCT programs.

I thought about something similar but only for initializing the
counters: introduce 10 fake playouts and estimate the number of
wins by a function returning something in [0, 10]. After that,
use UCT with real playouts.

If your guess was right, that should improve performance, but if
it was wrong you are doing nothing irreversible except loosing
time.


Another option is to replace the playout by a partial playout followed
by a static evaluation, which would probably be deterministic (that's
acceptable since the partial playout introduced plenty of
non-determinism).
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Darren Cook]

> ...XCell Journal. Search on the net for "Lorenz, Donninger, Hydra" and
> format "pdf". But in this papers the concept is only mentioned ...

Thanks Chrilly. For anyone else interested, it is here:
http://www.xilinx.com/publications/xcellonline/xcell_53/xc_pdf/xc_hydra53.pdf

But, as you say, the "the search tree as an adaptable error filter"idea
is only mentioned in passing. I guess I'll just have to wait for Ulf
Lorenz to translate his Dissertation into English :-).

> Ulf has used this model for a project to improve the robustness of
> airplane-schedules. ...

Interesting. It is always motivating to hear about game theory getting
applied to the real world. (And having been stuck in Amsterdam airport
for 5 hours because KLM "forgot to schedule a pilot" for my flight, I
think the airline industry needs all the help it can get!)

Darren

-- 
Darren Cook
http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
http://dcook.org/work/ (About me and my work)
http://dcook.org/work/charts/  (My flash charting demos)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Matt Gokey]

Don Dailey wrote:

(snip)
In my opinion, the insight that Chrilly articulated was that all of
sudden we are now all using some type of global search - the very
idea was considered blasphemy just 2 or 3 years ago.  

That may be too strong a statement.  It may have not been popular but
many people consistently believed global search must be a big part of
any strong playing program, myself included.  Not searching using the
same techniques as used for chess, but IMO certainly searching has not
ever been altogether dismissed nor considered blasphemy.  Look back at
posts around 10 years ago (when I first joined the list) and probably
since its inception and you'll find this to be true.  I personally wrote
about it on several occasions suggesting that to counter the evaluation
problem the search needed to go very deep and even talked about
"sampling" the tree.  Other probability based searches have been studied
and written about in academic papers and on this list as well.  The
crucial combination of techniques didn't bubble up, but not for lack
of trying.

But I have to admit that personally, I have many more ideas than time
with a full time job. Over the last 10 years all I've really done is
play around with various algorithms and ideas, study the game of go,
collect and read a lot of published papers, and keep up on this list -
occasionally posting.  My wife still doesn't understand my putting this
much time into it! ;-)  This is the kind of thing that could consume a
person.  I don't know if particular ideas would pay off or not because I
haven't been able to put in the proper time to focus.  In spare time, on
and off over the years I've only done a few experiments and algorithms
mostly focused on partitioning, goal directed and hierarchical searching
methods. This negligible computer-go work, some plans and a few ideas is
the extent of my would-be program "KatanaGo".

Regardless, it has been great fun watching the progress of computer-go
over the years and the current flurry of activity with MC/UCT is quite
exciting!

As I wrote in a post in early Feb of this year (paraphrasing from
memory), I think the main reason MC/UCT works is because it goes deep
(nearly always to the end) and tends to find paths with more favorable
possibilities and more importantly avoid paths littered with problems.
Though I'm still pretty amazed by how well it plays, but that's the
power of the law of large numbers at work. Correct?

As for the point that different paths may converge on similar methods, I
agree that could be very plausible scenario, but there is a very long
way to go yet...






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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chrilly]

Thanks Chrilly. For anyone else interested, it is here:
http://www.xilinx.com/publications/xcellonline/xcell_53/xc_pdf/xc_hydra53.pdf

But, as you say, the "the search tree as an adaptable error filter"idea
is only mentioned in passing. I guess I'll just have to wait for Ulf
Lorenz to translate his Dissertation into English :-).

Or you learn German. As I side effect you can than also read Goethe and my 
chess columns. The chess columns are interesting, but then you have to learn 
also the Austrian version of German).



Ulf has used this model for a project to improve the robustness of
airplane-schedules. ...


Interesting. It is always motivating to hear about game theory getting
applied to the real world. (And having been stuck in Amsterdam airport
for 5 hours because KLM "forgot to schedule a pilot" for my flight, I
think the airline industry needs all the help it can get!)

The problem is, that there is no economic incentive. A robust solution is 
usually somewhat worse than the non-robust one. I assume that you did not 
get any compensation for the 5 hours in Schiphol. Such methods will only 
become important, if KLM has to pay you. 50 Euro/h. The scheduling was done 
before by humans. These schedules have been robust. Simply for the fact that 
it is too complicated for a human to make an optimal schedule. But also 
because humans have some feeling what can go wrong and they anticipate the 
most likely delays. To a certain degree computer-optimization was introduced 
to make the schedules less robust.


But you have also choosen a very poor airline. KLM was fine a few years 
agos, but then they started to "save money" and now its notorious for being 
late, loosing baggage. But as the other lines have gone the same way, it 
makes no big difference. There a few good lines left. I my experience the 
best one is Emirates from Dubai. You should give it a try the next time.


Chrilly

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Don Dailey]

Yes, I'm exaggerating - but I do remember that when the idea
came up, quite a bit of emotional reaction against it.   Of 
course I realize that there have always been a few who 
believed some type of global search would be needed. 

- Don

 
On Mon, 2007-04-09 at 23:53 -0500, Matt Gokey wrote:
> > In my opinion, the insight that Chrilly articulated was that all of
> > sudden we are now all using some type of global search - the very
> > idea was considered blasphemy just 2 or 3 years ago.  
> That may be too strong a statement.  It may have not been popular but
> many people consistently believed global search must be a big part of
> any strong playing program, myself included.  Not searching using the
> same techniques as used for chess, but IMO certainly searching has not
> ever been altogether dismissed nor considered blasphemy.  Look back at
> posts around 10 years ago (when I first joined the list) and probably
> since its inception and you'll find this to be true.  I personally
> wrote
> about it on several occasions suggesting that to counter the
> evaluation
> problem the search needed to go very deep and even talked about
> "sampling" the tree.  Other probability based searches have been
> studied
> and written about in academic papers and on this list as well.  The
> crucial combination of techniques didn't bubble up, but not for lack
> of trying.
> 

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Sylvain Gelly]

Hello,

2007/4/6, Tom Cooper <[EMAIL PROTECTED]>:


My guess is that the complexity of achieving a fixed standard of play
(eg 1 dan) using a global alpha-beta or MC search is an exponential
function of the board size.



(...)

To some extent, this is testable today by finding how a global search
program's strength scales with board size and with thinking
time



I have experiments of MoGo's playing strength against a fixed player (Gnugo
3.7.10 level 8) on different board sizes and different thinking times.
Of course, to meet your statement we have here to assume that the level of
gnugo level 8 is a constant with the board size.

The results are that in order to keep the same winning rate, you have to
increase the number of simulations by something a little larger than linear
in the board area. From 9x9 to 13x13, you need something like 3 times more
simulations for the same winning rate. Same thing from 13x13 to 19x19. As
the time of one simulation is linear in the board area, to keep the same
level you have to give a time which increases as power ~2.5 of the board
area. So between 9x9 and 19x19, you have to give 32x more time per move for
the "same play level" (always defined as winning rate against gnugo).
This is far from being exponential. (maybe if it was exponential, there
would be little interest to work on 9x9 go).

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chris Fant]

The results are that in order to keep the same winning rate, you have to
increase the number of simulations by something a little larger than linear
in the board area. From 9x9 to 13x13, you need something like 3 times more
simulations for the same winning rate. Same thing from 13x13 to 19x19. As
the time of one simulation is linear in the board area, to keep the same
level you have to give a time which increases as power ~2.5 of the board
area. So between 9x9 and 19x19, you have to give 32x more time per move for
the "same play level" (always defined as winning rate against gnugo).
This is far from being exponential. (maybe if it was exponential, there
would be little interest to work on 9x9 go).


Here's another way to test this sort of thing that is completely
intrinsic to the engine (doesn't require gnugo):

Start with and empty board and zero komi.  Analyze using UCT until the
winning percentage at the root reaches X.  Note the number of
simulations required (or the amount of time).  Repeat for a larger
board size.  One should probably average N trials at each board size
for more reliable numbers.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Sylvain Gelly]

Here's another way to test this sort of thing that is completely
intrinsic to the engine (doesn't require gnugo):

Start with and empty board and zero komi.  Analyze using UCT until the
winning percentage at the root reaches X.  Note the number of
simulations required (or the amount of time).  Repeat for a larger
board size.  One should probably average N trials at each board size
for more reliable numbers.


Is that a better measure of playing strength? I don't think so.
And if the only advantage is that it does not require gnugo, I don't see the
point as gnugo is a marvellous tool, why avoid it?

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Chris Fant]

Is that a better measure of playing strength? I don't think so.
And if the only advantage is that it does not require gnugo, I don't see the
point as gnugo is a marvellous tool, why avoid it?


It's just another way to estimate the scope of the problem (Go) as the
board size increases.  And you don't need to "assume that the level of
gnugo level 8 is a constant with the board size."
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[compgo123]

I watched MoGo playing with different rank of players. Usually 5d players has 
no problem winning. Starting from 4d begin to lose games. However, part of it 
is due to most players are not familar with 9x9 Go. Taking this into 
consideration I place MoGo at about amateur 2d. For professional players 
consider 9x9 is solved. This is all my opinion.
 
Gnu plays at about 5k on 19x19. Let's place MoGo at 4k on 19x19. Besides the 32 
times, it also need to make up the difference between 4k and 2d.
 
Exponential may not be the case. Just consider this that it could be factorial 
which is worse than expernential.
 
 
Daniel Liu
 
-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Tue, 10 Apr 2007 3:12 PM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)


Hello,


2007/4/6, Tom Cooper <[EMAIL PROTECTED]>: 
My guess is that the complexity of achieving a fixed standard of play
(eg 1 dan) using a global alpha-beta or MC search is an exponential
function of the board size. 


(...)
To some extent, this is testable today by finding how a global search
program's strength scales with board size and with thinking
time

I have experiments of MoGo's playing strength against a fixed player (Gnugo 
3.7.10 level 8) on different board sizes and different thinking times.
Of course, to meet your statement we have here to assume that the level of 
gnugo level 8 is a constant with the board size.

The results are that in order to keep the same winning rate, you have to 
increase the number of simulations by something a little larger than linear in 
the board area. From 9x9 to 13x13, you need something like 3 times more 
simulations for the same winning rate. Same thing from 13x13 to 19x19. As the 
time of one simulation is linear in the board area, to keep the same level you 
have to give a time which increases as power ~2.5 of the board area. So between 
9x9 and 19x19, you have to give 32x more time per move for the "same play 
level" (always defined as winning rate against gnugo). 
This is far from being exponential. (maybe if it was exponential, there would 
be little interest to work on 9x9 go).

Sylvain

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

AOL now offers free email to everyone.  Find out more about what's free from 
AOL at AOL.com.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Sylvain Gelly]

2007/4/11, [EMAIL PROTECTED] <[EMAIL PROTECTED]>:


I watched MoGo playing with different rank of players. Usually 5d players
has no problem winning. Starting from 4d begin to lose games. However, part
of it is due to most players are not familar with 9x9 Go. Taking this into
consideration I place MoGo at about amateur 2d. For professional players
consider 9x9 is solved. This is all my opinion.

Gnu plays at about 5k on 19x19. Let's place MoGo at 4k on 19x19. Besides
the 32 times, it also need to make up the difference between 4k and 2d.



I just reported precise and objective experiments which may be interesting
results for some. I have no opinion watching the program play, and no way to
measure it precisely by subjective opinions.

However, maybe it lacks some numbers in my report. On KGS, 9x9, MoGo uses
about 40s per move, and on 19x19 (when rated 4kyu) used 15s per move. So it
almost 3 times less and I reported that it should be 32 times more (so
around 21 minutes per move). In the other way, these 15s per move would be
0.5s per move on 9x9.  Maybe it does not continue to scale so well with
time, I don't know. However with the times I tested, the scale with the
board size is what I reported, and at least the number are precise (many
dozen thousands of games).

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Álvaro Begué]

On 4/11/07, Sylvain Gelly <[EMAIL PROTECTED]> wrote:

2007/4/11, [EMAIL PROTECTED] <[EMAIL PROTECTED]>:
>
>
> I watched MoGo playing with different rank of players. Usually 5d players
has no problem winning. Starting from 4d begin to lose games. However, part
of it is due to most players are not familar with 9x9 Go. Taking this into
consideration I place MoGo at about amateur 2d. For professional players
consider 9x9 is solved. This is all my opinion.
>
> Gnu plays at about 5k on 19x19. Let's place MoGo at 4k on 19x19. Besides
the 32 times, it also need to make up the difference between 4k and 2d.

I just reported precise and objective experiments which may be interesting
results for some. I have no opinion watching the program play, and no way to
measure it precisely by subjective opinions.


In case it matters, I think your experiment was interesting, relevant
and well designed. Once we get dimwit to a decent level of play I'll
probably try to produce similar data.

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[dhillismail]

I also find this kind of information very interesting and useful. Now I have a 
better feel for what kind of scaling is realistic to try for and how to measure 
it.
 
Putting some recent data points together, it look like giving Mogo 2 orders of 
magnitude more computer power would result in low dan level 19x19 play? Not the 
sort of thing one can pull out of a back pocket, but tantalizing.
 
I would be very interested to see equivalent scaling numbers from CrazyStone, 
if Remi would be so kind.
 
- Dave Hillis
 
  -Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Tue, 10 Apr 2007 4:12 PM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)


Hello,


2007/4/6, Tom Cooper <[EMAIL PROTECTED]>: 
My guess is that the complexity of achieving a fixed standard of play
(eg 1 dan) using a global alpha-beta or MC search is an exponential
function of the board size. 


(...)
To some extent, this is testable today by finding how a global search
program's strength scales with board size and with thinking
time

I have experiments of MoGo's playing strength against a fixed player (Gnugo 
3.7.10 level 8) on different board sizes and different thinking times.
Of course, to meet your statement we have here to assume that the level of 
gnugo level 8 is a constant with the board size.

The results are that in order to keep the same winning rate, you have to 
increase the number of simulations by something a little larger than linear in 
the board area. From 9x9 to 13x13, you need something like 3 times more 
simulations for the same winning rate. Same thing from 13x13 to 19x19. As the 
time of one simulation is linear in the board area, to keep the same level you 
have to give a time which increases as power ~2.5 of the board area. So between 
9x9 and 19x19, you have to give 32x more time per move for the "same play 
level" (always defined as winning rate against gnugo). 
This is far from being exponential. (maybe if it was exponential, there would 
be little interest to work on 9x9 go).

Sylvain


-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Wed, 11 Apr 2007 7:43 AM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)

... 
In case it matters, I think your experiment was interesting, relevant 
and well designed. Once we get dimwit to a decent level of play I'll 
probably try to produce similar data. 
 
Álvaro. 

Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam 
and email virus protection.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Sylvain Gelly]

I also find this kind of information very interesting and useful. Now I have
a better feel for what kind of scaling is realistic to try for and how to
measure it.

Putting some recent data points together, it look like giving Mogo 2 orders
of magnitude more computer power would result in low dan level 19x19 play?
Not the sort of thing one can pull out of a back pocket, but tantalizing.


That is quite an large extrapolation.
I would rather conclude that we have to find new improvements in the
algorithms. But keeping in mind that the scalability with the board
size is not impossible.

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Tom Cooper]

Thank you Sylvain for conducting these experiments.  We have had some very
enlightening results posted here recently in my opinion.  I have to admit,
I'm surprised at how well the program seems to scale.  Fortunately, I didn't
make a bet. :)

Taking for granted that these results indeed show what they seem to, and
combining them with the success of Monte-Carlo methods on 7x7 and 9x9 boards,
I'll have to change my opinion about the future of computer go quite radically.

It now seems believable to me that computer go will go the way of 
computer chess,

and within the next decade or so as well.  Or maybe Chrilly will make a monster
go machine even before that.

Could somebody comment please on the likely usefulness of massively parallel
machines to UCT-like algorithms.

Thanks again.
Tom.

At 21:12 10/04/2007, you wrote:


Hello,

2007/4/6, Tom Cooper 
<[EMAIL PROTECTED]>:

My guess is that the complexity of achieving a fixed standard of play
(eg 1 dan) using a global alpha-beta or MC search is an exponential
function of the board size.


(...)
To some extent, this is testable today by finding how a global search
program's strength scales with board size and with thinking
time


I have experiments of MoGo's playing strength against a fixed player 
(Gnugo 3.7.10 level 8) on different board sizes and different thinking times.
Of course, to meet your statement we have here to assume that the 
level of gnugo level 8 is a constant with the board size.


The results are that in order to keep the same winning rate, you 
have to increase the number of simulations by something a little 
larger than linear in the board area. From 9x9 to 13x13, you need 
something like 3 times more simulations for the same winning rate. 
Same thing from 13x13 to 19x19. As the time of one simulation is 
linear in the board area, to keep the same level you have to give a 
time which increases as power ~2.5 of the board area. So between 9x9 
and 19x19, you have to give 32x more time per move for the "same 
play level" (always defined as winning rate against gnugo).
This is far from being exponential. (maybe if it was exponential, 
there would be little interest to work on 9x9 go).


Sylvain
___
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] The dominance of search (Suzie v. GnuGo)

[Jason House]

As with anything, an efficient serial algorithm (alpha-beta, UCT, etc...)
becomes less efficient when made parallel.  I think you can see some
significant improvement with parallel machines, but it may be that you'll
get diminishing returns.

I can think of two parallel approaches:
1. Instruct multiple instances to simulate from the same starting point
(getting higher confidence estimates more quickly)
2. Instruct different instances to examine different subtrees.

Option #1 has the downfall that it may sample a subtree more than necessary
before rejecting it.  It may also lose some subtree information between
processes

Option #2 has the downfall that different instances may dwell on a
particular subtree for too long before getting instructed to simulate
something else.



On 4/11/07, Tom Cooper <[EMAIL PROTECTED]> wrote:


Thank you Sylvain for conducting these experiments.  We have had some very
enlightening results posted here recently in my opinion.  I have to admit,
I'm surprised at how well the program seems to scale.  Fortunately, I
didn't
make a bet. :)

Taking for granted that these results indeed show what they seem to, and
combining them with the success of Monte-Carlo methods on 7x7 and 9x9
boards,
I'll have to change my opinion about the future of computer go quite
radically.

It now seems believable to me that computer go will go the way of
computer chess,
and within the next decade or so as well.  Or maybe Chrilly will make a
monster
go machine even before that.

Could somebody comment please on the likely usefulness of massively
parallel
machines to UCT-like algorithms.

Thanks again.
Tom.

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Rémi Coulom]

[EMAIL PROTECTED] wrote:
I also find this kind of information very interesting and useful. Now 
I have a better feel for what kind of scaling is realistic to try for 
and how to measure it.
 
Putting some recent data points together, it look like giving Mogo 2 
orders of magnitude more computer power would result in low dan level 
19x19 play? Not the sort of thing one can pull out of a back pocket, 
but tantalizing.
 
I would be very interested to see equivalent scaling numbers from 
CrazyStone, if Remi would be so kind.
 
- Dave Hillis
I don't have time to do this right now. I have connected Crazy Stone to 
play 10 minute blitz on KGS, and will leave it all night long. It 
reached [1d] for a while, and is currently [1k]. There is a big surprise 
effect when humans play Crazy Stone. The first moves look so stupid. 
Usually, a human player will lose the first game, then it will win the 
next ones.


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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[dhillismail]

>-Original Message-
>From: [EMAIL PROTECTED]
>To: computer-go@computer-go.org
>Sent: Wed, 11 Apr 2007 4:33 PM
>Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)
>

>[EMAIL PROTECTED] wrote: 
>> I also find this kind of information very interesting and useful. Now > I 
>> have a better feel for what kind of scaling is realistic to try >for > and 
>> how to measure it. 
>> > Putting some recent data points together, it look like giving Mogo 2 > 
>> > orders of magnitude more computer power would result >in low dan level > 
>> > 19x19 play? Not the sort of thing one can pull out of a back pocket, > but 
>> > tantalizing. 
>> > I would be very interested to see equivalent scaling numbers from > 
>> > CrazyStone, if Remi would be so kind. 
>> > - Dave Hillis 
>I don't have time to do this right now. I have connected Crazy Stone to play 
>10 minute blitz on KGS, and will leave it all night long. >It reached [1d] for 
>a while, and is currently [1k]. There is a big surprise effect when humans 
>play Crazy Stone. The first moves look >so stupid. Usually, a human player 
>will lose the first game, then it will win the next ones. 
> 
>Rémi 
___ 
 
Thanks, Remi. I was thinking that you might already have collected this 
information since testing against gnugo is so common. (My own program sucks at 
larger board sizes.) The blitz games sound interesting too. I'm sure I speak 
for all of us when I say that I'm looking forward to seeing your paper after 
the conference and I'd be interested in any hints you might have in the 
meantime. I promise to exploit any indiscretion to the best of my abilities. :)
 
- Dave Hillis
 

Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam 
and email virus protection.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[compgo123]

Remi,
 
Could you change your time as 10 min. plus 8 min. byo yomi? Otherwise it's too 
short for human. It's difficult to get a real results.
 
Daniel Liu
 
 
-Original Message-
From: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Wed, 11 Apr 2007 3:33 PM
Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)


[EMAIL PROTECTED] wrote: 
> I also find this kind of information very interesting and useful. Now > I 
> have a better feel for what kind of scaling is realistic to try for > and how 
> to measure it. 
> > Putting some recent data points together, it look like giving Mogo 2 > 
> > orders of magnitude more computer power would result in low dan level > 
> > 19x19 play? Not the sort of thing one can pull out of a back pocket, > but 
> > tantalizing. 
> > I would be very interested to see equivalent scaling numbers from > 
> > CrazyStone, if Remi would be so kind. 
> > - Dave Hillis 
I don't have time to do this right now. I have connected Crazy Stone to play 10 
minute blitz on KGS, and will leave it all night long. It reached [1d] for a 
while, and is currently [1k]. There is a big surprise effect when humans play 
Crazy Stone. The first moves look so stupid. Usually, a human player will lose 
the first game, then it will win the next ones. 
 
Rémi 
___ 
computer-go mailing list 
[EMAIL PROTECTED] 
http://www.computer-go.org/mailman/listinfo/computer-go/ 

AOL now offers free email to everyone.  Find out more about what's free from 
AOL at AOL.com.
___
computer-go mailing list
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Hideki Kato]

[EMAIL PROTECTED]: <[EMAIL PROTECTED]>:
>Remi,
> 
>Could you change your time as 10 min. plus 8 min. byo yomi? Otherwise it's too 
>short for
>human. It's difficult to get a real results.

Strogly agree! It's too short for me, 4 kyu, to have a meaningful
game with Crazy Stone. I beg you too, Remi.
#GNU bots are 10 min + 20 sec x 5.

- gg

>Daniel Liu
> 
> 
>-Original Message-
>From: [EMAIL PROTECTED]
>To: [EMAIL PROTECTED]
>Sent: Wed, 11 Apr 2007 3:33 PM
>Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)
>
>
>[EMAIL PROTECTED] wrote: 
>> I also find this kind of information very interesting and useful. Now > I 
>> have a better
>feel for what kind of scaling is realistic to try for > and how to measure it. 
>> > Putting some recent data points together, it look like giving Mogo 2 > 
>> > orders of
>magnitude more computer power would result in low dan level > 19x19 play? Not 
>the sort of
>thing one can pull out of a back pocket, > but tantalizing. 
>> > I would be very interested to see equivalent scaling numbers from > 
>> > CrazyStone, if Remi
>would be so kind. 
>> > - Dave Hillis 
>I don't have time to do this right now. I have connected Crazy Stone to play 
>10 minute blitz
>on KGS, and will leave it all night long. It reached [1d] for a while, and is 
>currently [1k].
>There is a big surprise effect when humans play Crazy Stone. The first moves 
>look so stupid.
>Usually, a human player will lose the first game, then it will win the next 
>ones. 
> 
>Rémi 
>___ 
>computer-go mailing list 
>[EMAIL PROTECTED] 
>http://www.computer-go.org/mailman/listinfo/computer-go/ 
>
>AOL now offers free email to everyone.  Find out more about what's free from 
>AOL at AOL.com.
> inline file
>___
>computer-go mailing list
>[EMAIL PROTECTED]
>http://www.computer-go.org/mailman/listinfo/computer-go/
--
[EMAIL PROTECTED] (Kato)
___
computer-go mailing list
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Rémi Coulom]

[EMAIL PROTECTED] wrote:
I also find this kind of information very interesting and useful. Now 
I have a better feel for what kind of scaling is realistic to try for 
and how to measure it.
 
Putting some recent data points together, it look like giving Mogo 2 
orders of magnitude more computer power would result in low dan level 
19x19 play? Not the sort of thing one can pull out of a back pocket, 
but tantalizing.
 
I would be very interested to see equivalent scaling numbers from 
CrazyStone, if Remi would be so kind.
 
- Dave Hillis

Hi,

Here is some data, each result measured over about 200 games, on a 
single CPU (AMD Opteron 2.2 GHz):

9x9, 2 minutes per game, GNU Go level 10: 87.0%
13x13, 16 minutes per game, GNU Go level 10: 72.4%
19x19, 32 minutes per game, GNU Go level 0: 53.6%
19x19, 32 minutes per game, GNU Go level 8: 28.1%
19x19, 64 minutes per game, GNU Go level 8: 35.4%

(GNU Go version 3.6)

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

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[dhillismail]

 
>-Original Message-
>From: [EMAIL PROTECTED]
>To: computer-go@computer-go.org
>Sent: Mon, 16 Apr 2007 5:26 AM
>Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)


>[EMAIL PROTECTED] wrote: 
>> I also find this kind of information very interesting and useful. Now > I 
>> have a better feel for what kind of scaling is realistic to try >for > and 
>> how to measure it. 
>> > Putting some recent data points together, it look like giving Mogo 2 > 
>> > orders of magnitude more computer power would result >in low dan level > 
>> > 19x19 play? Not the sort of thing one can pull out of a back pocket, > but 
>> > tantalizing. 
>> > I would be very interested to see equivalent scaling numbers from > 
>> > CrazyStone, if Remi would be so kind. 
>> > - Dave Hillis 
>Hi, 
> 
>Here is some data, each result measured over about 200 games, on a single CPU 
>(AMD Opteron 2.2 GHz): 
>9x9, 2 minutes per game, GNU Go level 10: 87.0% 
>13x13, 16 minutes per game, GNU Go level 10: 72.4% 
>19x19, 32 minutes per game, GNU Go level 0: 53.6% 
>19x19, 32 minutes per game, GNU Go level 8: 28.1% 
>19x19, 64 minutes per game, GNU Go level 8: 35.4% 
> 
>(GNU Go version 3.6) 
> 
>Rémi 

 
 
Thanks! These are interesting. I assume that the number of playouts per move 
was variable. If it was a fixed number, or easily characterized, it would be a 
helpful statistic too.
 
- Dave Hillis
 

Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam 
and email virus protection.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] The dominance of search (Suzie v. GnuGo)

[Rémi Coulom]

[EMAIL PROTECTED] wrote:
 
>-Original Message-

>From: [EMAIL PROTECTED]
>To: computer-go@computer-go.org
>Sent: Mon, 16 Apr 2007 5:26 AM
>Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo)

>[EMAIL PROTECTED] 
 wrote: 
>> I also find this kind of information very interesting and useful. 
Now > I have a better feel for what kind of scaling is realistic to 
try >for > and how to measure it. 
>> > Putting some recent data points together, it look like giving 
Mogo 2 > orders of magnitude more computer power would result >in low 
dan level > 19x19 play? Not the sort of thing one can pull out of a 
back pocket, > but tantalizing. 
>> > I would be very interested to see equivalent scaling numbers from 
> CrazyStone, if Remi would be so kind. 
>> > - Dave Hillis 
>Hi, 
> 
>Here is some data, each result measured over about 200 games, on a 
single CPU (AMD Opteron 2.2 GHz): 
>9x9, 2 minutes per game, GNU Go level 10: 87.0% 
>13x13, 16 minutes per game, GNU Go level 10: 72.4% 
>19x19, 32 minutes per game, GNU Go level 0: 53.6% 
>19x19, 32 minutes per game, GNU Go level 8: 28.1% 
>19x19, 64 minutes per game, GNU Go level 8: 35.4% 
> 
>(GNU Go version 3.6) 
> 
>Rémi 
 
 
Thanks! These are interesting. I assume that the number of playouts 
per move was variable. If it was a fixed number, or easily 
characterized, it would be a helpful statistic too.
 
- Dave Hillis
Yes, it was variable. On that machine, Crazy Stone does about 15,000 
playouts/second on 9x9 with UCT. BTW, CrazyStone-Fast on CGOS is 5k 
simulations, and CrazyStone-Slower is 20k.


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