[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
-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
[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]
javascript:parent.ComposeTo(dhillismail%40netscape.net, ); wrote
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
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
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
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
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
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
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 filteridea
is only mentioned in passing. I guess I'll just have to wait for Ulf
Lorenz to translate
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
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
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).
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
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
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
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].
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
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,
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
problems.
Chrilly
- Original Message -
From: Darren Cook [EMAIL PROTECTED]
To: computer-go computer-go@computer-go.org
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
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
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
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
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
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
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
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
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
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
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
(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
32 matches
Mail list logo
