RE: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[David Fotland]

Many Faces caches both local tactical results (ladders etc), and life and death 
reading results.  For tactics it records a "shadow".  For life and death it 
saves the whole tree.

The tactical caches are still active in the UCT-MC code since reading tactics 
is part of move generation.  The Life and Death search was a separate pass in 
the traditional program so it is not used by UCT-MC (yet).

David

> 
> This sounds a lot like a description of GNU Go's persistent reading
> cache,
> which calculates "reading shadow" for all its readings. Has something
> similar tried for other programs?
> 
> --
> Seo Sanghyeon
> ___
> 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: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Seo Sanghyeon]

2009/10/30 terry mcintyre :
> This may be useful in computer Go. One of the reasons human pros do well is
> that they compute certain sub-problems once, and don't repeat the effort
> until something important changes. They know in an instant that certain
> positions are live or dead or seki; they know when a move ( reducing a
> liberty, for example ) disturbs that result. This could probably be emulated
> with theorem-proving ability. Presently, search algorithms have to
> rediscover these results many times over; this is (in my opinion) why
> computer programs get significantly weaker when starved for time; they
> cannot think deeply enough to solve problems which may be solved in an
> eyeblink by a pro.

This sounds a lot like a description of GNU Go's persistent reading cache,
which calculates "reading shadow" for all its readings. Has something
similar tried for other programs?

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

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Don Dailey]

What is interesting is not the fact that intrasitivity exists, that is not
in doubt.  But it quite interesting that this much intransitivity can be
created with non-trivial and strong programs.

I would like to see the data though, specifically the number of games
between each player at each level and of course the scores that go with
this.

Such a differece indicates to me that the program (or MC programs in
general)  may be too brittle and needs some knowledge that gnuo has.

- Don



2009/10/29 Olivier Teytaud 

>
>
>> BTW, recently I've measured the strength (win rate) vs time for a move
>> curves with Zen vs GNU Go and Zen vs Zen (self-play) on 19 x 19 board.
>> Without opening book, it saturates between +400 and +500 Elo against
>> GNU but doesn't upto +800 Elo in self-play.  That's somewhat
>> interesting (detail will be open soon at GPW-2009).
>>
>>
> Just a post to say that I find this remark extremely interesting :-)
> Thanks a lot Hideki.
> Olivier
>
>
> ___
> 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: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Olivier Teytaud]

>
> BTW, recently I've measured the strength (win rate) vs time for a move
> curves with Zen vs GNU Go and Zen vs Zen (self-play) on 19 x 19 board.
> Without opening book, it saturates between +400 and +500 Elo against
> GNU but doesn't upto +800 Elo in self-play.  That's somewhat
> interesting (detail will be open soon at GPW-2009).
>
>
Just a post to say that I find this remark extremely interesting :-)
Thanks a lot Hideki.
Olivier
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Mark Boon]

2009/10/29 terry mcintyre :
> That sounds to me like "a dumb human with a smart algorithm can beat a fast
> computer with a dumb algorithm" -- which speaks more to Penrose's reluctance
> to improve algorithms in his dumbed-down computer models than it does to any
> quantum-physical effects.
>
> Stir in some theorem-proving ability - where a great deal of research was
> accomplished decades ago - and a computer chess program can prove theorems
> about chess positions, including "these bishops can never get past these
> pawns."

It's still rather germane to the discussion though. With MC the
algorithms have become dumber rather than smarter, so that influences
the question whether the brute-force method will hit a wall or not.

Take eyes, for example. MC programs have a very poor understanding of
which groups are alive and which are dead. And this leads to problems
which clearly cannot be solved by more computer-power.

If I had time to work on MC programs I'd look for improvements in the
status of groups during the playouts, trying to improve its notion of
eyes.

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

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Don Dailey]

Yes, I agree with you on most of this.  However, I believe that Go is a
very simple domain in some sense and that we romanticize it too much.   I am
not saying there is not amazing depth to it,   but it's represented very
compactly and it's a game of perfect information with very limited choices.


Having said that, I do fully appreciate that even if Moores law could hold
indefinitely,  there are still problems that will take decades to overcome
if there are no software advances.

- Don



On Thu, Oct 29, 2009 at 1:14 PM, Mark Boon  wrote:

> Roger Penrose thinks the human brain can do things a Turing machine cannot.
> (Note: I don't say 'computer'.) He claims it's due to some quantum-physical
> effects used by the brain. I doubt his ideas are correct, but he did have a
> few interesting chess-positions to support his theory. Typically, they would
> contain a completely locked position, say a V-shaped pawn position and
> bishops on the wrong color to pass the pawn-ranks. These types of positions
> are very easily analyzed by even mediocre players, yet a computer never gets
> the right answer.
>
> Basically what it shows is that the human brain is able to conceptualize
> certain things that enable it to reason about situations that cannot be
> calculated by brute force. I don't claim that a Turing machine cannot do
> such things as well if programmed well, but it's very easy to see that there
> could be barriers to computers, no matter how much computing power you give
> them, if they solely rely on a simple method with brute force.
>
> Mark
>
> ___
> 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: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[terry mcintyre]

That sounds to me like "a dumb human with a smart algorithm can beat a fast 
computer with a dumb algorithm" -- which speaks more to Penrose's reluctance to 
improve algorithms in his dumbed-down computer models than it does to any 
quantum-physical effects. 

 
Stir in some theorem-proving ability - where a great deal of research was 
accomplished decades ago - and a computer chess program can prove theorems 
about chess positions, including "these bishops can never get past these pawns."

This may be useful in computer Go. One of the reasons human pros do well is 
that they compute certain sub-problems once, and don't repeat the effort until 
something important changes. They know in an instant that certain positions are 
live or dead or seki; they know when a move ( reducing a liberty, for example ) 
disturbs that result. This could probably be emulated with theorem-proving 
ability. Presently, search algorithms have to rediscover these results many 
times over; this is (in my opinion) why computer programs get significantly 
weaker when starved for time; they cannot think deeply enough to solve problems 
which may be solved in an eyeblink by a pro.

I've observed some high-dan-level amateurs playing complex semeai on 19x19 
games. They might not actually know the result of a semeai, but they  respond 
quickly to moves which would alter the status - if one of my liberties is 
taken, I take one of his - until such point as the player takes a noticeably 
long time to re-analyse the semeai and think "I need not respond to that move" 
and takes sente. The stronger the player, the more accurate these assessments 
are. 

Terry McIntyre 


"And one sad servitude alike denotes
The slave that labours and the slave that votes" -- Peter Pindar




From: Mark Boon 
To: computer-go 
Sent: Thu, October 29, 2009 10:14:18 AM
Subject: Re: [SPAM] Re: [computer-go] First ever win of a computer against a 
pro 9P as black (game of Go, 9x9).

Roger Penrose thinks the human brain can do things a Turing machine cannot. 
(Note: I don't say 'computer'.) He claims it's due to some quantum-physical 
effects used by the brain. I doubt his ideas are correct, but he did have a few 
interesting chess-positions to support his theory. Typically, they would 
contain a completely locked position, say a V-shaped pawn position and bishops 
on the wrong color to pass the pawn-ranks. These types of positions are very 
easily analyzed by even mediocre players, yet a computer never gets the right 
answer.

Basically what it shows is that the human brain is able to conceptualize 
certain things that enable it to reason about situations that cannot be 
calculated by brute force. I don't claim that a Turing machine cannot do such 
things as well if programmed well, but it's very easy to see that there could 
be barriers to computers, no matter how much computing power you give them, if 
they solely rely on a simple method with brute force.

Mark
___
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: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Mark Boon]

Roger Penrose thinks the human brain can do things a Turing machine  
cannot. (Note: I don't say 'computer'.) He claims it's due to some  
quantum-physical effects used by the brain. I doubt his ideas are  
correct, but he did have a few interesting chess-positions to support  
his theory. Typically, they would contain a completely locked  
position, say a V-shaped pawn position and bishops on the wrong color  
to pass the pawn-ranks. These types of positions are very easily  
analyzed by even mediocre players, yet a computer never gets the right  
answer.


Basically what it shows is that the human brain is able to  
conceptualize certain things that enable it to reason about situations  
that cannot be calculated by brute force. I don't claim that a Turing  
machine cannot do such things as well if programmed well, but it's  
very easy to see that there could be barriers to computers, no matter  
how much computing power you give them, if they solely rely on a  
simple method with brute force.


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

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Don Dailey]

On Thu, Oct 29, 2009 at 12:40 PM, Petr Baudis  wrote:

> On Thu, Oct 29, 2009 at 12:00:32PM -0400, Don Dailey wrote:
> > That is exactly as it should be and is not a barrier.   I don't think you
> > know the difference between a wall and a point that is just far away.
>
> I'd phrase this positively - the point is extremely far away with the
> current way MCTS will succumb to blunders because of the way it is
> completely unable to compensate for systematic bias (the amount of
> computation required to overcome the bias is extreme), but some
> clever algorithmic improvement could put the point much closer.
>
> This is just a discussion how steep a slope we will already call a wall,
> I think it's more productive to talk about how to make the slope less
> steep. :)
>

I don't see it as a slope at all,  just a matter of distance.   So to me
it's just a matter of continuing to put one foot in front of the other.
But using different terminology than you,  we should talk about how to get
closer faster.

As software people we have to attack it from the software end and not worry
about the hardware end so much because that is out of our hands anyway
(unless of course we are in hardware.)

- Don




>
> --
>Petr "Pasky" Baudis
> A lot of people have my books on their bookshelves.
> That's the problem, they need to read them. -- Don Knuth
> ___
> 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: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Petr Baudis]

On Thu, Oct 29, 2009 at 12:00:32PM -0400, Don Dailey wrote:
> That is exactly as it should be and is not a barrier.   I don't think you
> know the difference between a wall and a point that is just far away.

I'd phrase this positively - the point is extremely far away with the
current way MCTS will succumb to blunders because of the way it is
completely unable to compensate for systematic bias (the amount of
computation required to overcome the bias is extreme), but some
clever algorithmic improvement could put the point much closer.

This is just a discussion how steep a slope we will already call a wall,
I think it's more productive to talk about how to make the slope less
steep. :)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Don Dailey]

2009/10/29 Olivier Teytaud 

>
>
>>
>> Just curious, who actually claimed that and what was it based on?
>>
>>
> I don't know who claimed it first, and who agreed for it,
> but I agree with it :-)
>

But you always seek the most hardware when you play against a human it
seems.

I think you realize it does help a lot to do this,  otherwise your team
would not be so foolish as to procure the big iron when it comes time to
compete.

You also are painfully aware that there are problems to be solved that will
not easily succumb to just a few more doublings in power.

That is exactly as it should be and is not a barrier.   I don't think you
know the difference between a wall and a point that is just far away.


>
> More precisely, I think that increasing time and computational power
> makes computers stronger, but not for some particular things like
> long-term life-and-death in corners, or semeai situations. This makes a
> big limitation on what is possible with MCTS algorithms, in particular
> against humans. We made a lot
> of efforts for online learning of Monte-Carlo simulations, in order to
> improve
> this, but there's no significant improvement around that.
>

You are thinking with a very limited perspective here.   Think in terms of 2
or 3 decades of Moores Law.We had those same "barriers" in chess that
people said were impossible because we usually don't think in terms of
getting  10,000 X more computing power,  we are stuck in the present and
just realize that getting 10X more is not nearly enough to solve some
problem as you are observing here.And if 2 decades are not enough wait 2
more.

I hope no one responds about Moores Law not holding any longer.   That has
nothing to do with my argument.My argument is that it takes a huge
amount of extra CPU power to make a dent in big problems,  just like it was
in chess.   No big surprise here.If Moores law doesn't hold then we are
in trouble and it will take about twice as long.

Why twice?   I don't really know but by analogy the progress in chess
software has been on par or slightly greater than the advances in
hardware.   (Most people don't realize this and think chess is 95%  about
hardware, but that is a complete misconception.   In very rough terms there
has been about the same increase in ELO due to software as to hardware over
the last several years.)

The combination of software and hardware is the potent combination if
Moore's law will hold out for us.Just because it may not happen within
the next 2 or 3 years doesn't mean it's a wall or that anything odd is going
on here.


- Don










>
> Best regards,
> Olivier
>
>
> ___
> 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: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Don Dailey]

2009/10/29 Olivier Teytaud 

>
>
>> Yes,  this group does not have a consensus at all on this.   On the one
>> hand we hear that MCTS has reached a dead end and there is no benefit from
>> extra CPU power, and on the other hand we have these developers hustling
>> around for the biggest machines they can muster in order to play matches
>> with humans!  And Olivier claims that computers benefit more from
>> additional thinking time than humans!
>>
>>
>>
> Thanks for this comment. I agree that something is strange here :-)
> Olivier
>


I'm being a bit sarcastic - I recognize that most of the statements made
about this general issue are not based as much on logic as they are on
emotional feelings or just making rash interpretations of tiny data
samples.   Almost always with us humans (myself included) when we try to
interpret data we lean way in the direction of our own subjective biases.

Even our own interpretations are in conflict sometimes.I myself have
said things that upon close examination prove to be in conflict with
something else I "believed",  they both could not be true!   And then to add
insult to injury we  try to explain the conflict away with amazingly
creative skill instead of just admitting that we might need to adjust our
belief system.

As far as this subject is concerned,   I honestly don't think we fully
understand it,  myself included. We have a lot of conflicting evidence
and I'm going to take a step backwards until we know more.

With go it is extremely frustrating.   The evaluation (rating/ranking)
system is non-standard and rather kludgey and we would need thousands of
games to settle this under controlled conditions unless the man/machine
difference was enormous.



- 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: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Olivier Teytaud]

>
>
> Just curious, who actually claimed that and what was it based on?
>
>
I don't know who claimed it first, and who agreed for it,
but I agree with it :-)

More precisely, I think that increasing time and computational power
makes computers stronger, but not for some particular things like
long-term life-and-death in corners, or semeai situations. This makes a
big limitation on what is possible with MCTS algorithms, in particular
against humans. We made a lot
of efforts for online learning of Monte-Carlo simulations, in order to
improve
this, but there's no significant improvement around that.

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

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Olivier Teytaud]

>
> Yes,  this group does not have a consensus at all on this.   On the one
> hand we hear that MCTS has reached a dead end and there is no benefit from
> extra CPU power, and on the other hand we have these developers hustling
> around for the biggest machines they can muster in order to play matches
> with humans!  And Olivier claims that computers benefit more from
> additional thinking time than humans!
>
>
>
Thanks for this comment. I agree that something is strange here :-)
Olivier
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Olivier Teytaud]

>
>
> >If there are people interested in a ph.D. or a post-doc around Monte-Carlo
> >Tree Search, candidates are welcome (Monte-Carlo Tree Search, and not
> >necessarily / not only computer-go).
>
> Excuse me, but what press conference and where to ask?
>

People interested in a ph.D. or a post doc can contact me.

>This was during a press conference at Taipei around a French-Taiwanese
> grant
> >for joint research.
> but I can find no links even with Google.
>

I'll ask to the taiwanese people if there is something on the web about the
press conference. I was only there through
a video. I don't know if there is something on the web. This is
essentially for the launching of a France/Taiwan collaboration around
Monte-Carlo Tree Search, I guess there are not thousards of journalists from
tenths of countries interested in it :-)

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

Re: [SPAM] Re: [SPAM] Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Olivier Teytaud]

>
>
> But is it shown that "the score is well done" for these properties to
> hold in case of RAVE-guided exploration? Since it massively perpetuates
> any kind of MC bias...
>

This only matters for the fact that we don't visit all the tree. For the
consistency (the fact that
asymptotically we will find the best possible decision), there's no problem.
If "score ~ success rate" for n--> infinity (which holds for most usual
rules, including rave rules) we also
have that, for binary games, we have some good properties on the part of the
tree which is visited.

Please not that I do not claim that major improvements are possible in
computer-go thanks to this.
We only observed a very small improvement on success rates, and a good
behavior on the situation
which appeared during the game against Fan Hui. It might be interesting to
know, for people who have
similar problems in their bot (a situation in which, even with huge
computation time, the good estimate is
not found), they solve it with this.

>
> > We use a stupid method, i.e. the success rate. The pattenrs are bigger
> than
> > 3x3, with jokers in them. Bandits (Bernstein races, slightly modified)
> are
> > used
> > for distributing the computational effort among the tested patterns.
>
> Thank you for pointing me to more study material. :-)
>
>
The following paper is great for Bernstein races:

http://icml2008.cs.helsinki.fi/papers/523.pdf

Please note, however, that we had only very small improvements with races.
Maybe our code has had too many tuning steps in the past for being strongly
improved
by random generation of patterns and bernstein races for validating them.

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

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Hideki Kato]

Olivier Teytaud: :
>I forgot the most important thing around this win against a pro:
>this press conference was for the starting of a project, and in this project
>we have funding for ph.D. or postdocs.
>If there are people interested in a ph.D. or a post-doc around Monte-Carlo
>Tree Search, candidates are welcome (Monte-Carlo Tree Search, and not
>necessarily / not only computer-go).

Excuse me, but what press conference and where to ask?

You wrote in your first post of this thread,
>This was during a press conference at Taipei around a French-Taiwanese grant
>for joint research.
but I can find no links even with Google.

Hideki
--
g...@nue.ci.i.u-tokyo.ac.jp (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Petr Baudis]

On Tue, Oct 27, 2009 at 06:32:44PM +0200, Olivier Teytaud wrote:
> >
> >
> > AIUI, once upon N simulations in a node you take let's say the node with
> > the lowest value, pick one son of it at random within the tree and start
> > a simulation?
> >
> 
> I'll try to write it clearly (for binary deterministic games, extensions can
> be shown but they are too long and out of topic in this mailing list I guess
> :-) ):
> 
> If (average value of father < threshold )
> then
> randomly pick up one son
>else
>pick up the son with maximum score
> end
> 

Aha, thanks for clearing that up.

> If the score is asymptotically equivalent to the success rate, and if the
> threshold is >0 and < 1, then this ensures
> consistency (convergence to optimal move). If the score is well done, then
> this is consistent without visiting all the tree.

But is it shown that "the score is well done" for these properties to
hold in case of RAVE-guided exploration? Since it massively perpetuates
any kind of MC bias...

> > Wow - one of my planned little projects was genetic development of the
> > 3x3 patterns... To evaluate patterns, do you use tournaments or some
> > smarter method? I feared one generation would take awfully long...
> >
> 
> We use a stupid method, i.e. the success rate. The pattenrs are bigger than
> 3x3, with jokers in them. Bandits (Bernstein races, slightly modified) are
> used
> for distributing the computational effort among the tested patterns.

Thank you for pointing me to more study material. :-)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Olivier Teytaud]

I forgot the most important thing around this win against a pro:
this press conference was for the starting of a project, and in this project
we have funding for ph.D. or postdocs.
If there are people interested in a ph.D. or a post-doc around Monte-Carlo
Tree Search, candidates are welcome (Monte-Carlo Tree Search, and not
necessarily / not only computer-go).

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

Re: [SPAM] Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Olivier Teytaud]

>
>
> AIUI, once upon N simulations in a node you take let's say the node with
> the lowest value, pick one son of it at random within the tree and start
> a simulation?
>

I'll try to write it clearly (for binary deterministic games, extensions can
be shown but they are too long and out of topic in this mailing list I guess
:-) ):

If (average value of father < threshold )
then
randomly pick up one son
   else
   pick up the son with maximum score
end

If the score is asymptotically equivalent to the success rate, and if the
threshold is >0 and < 1, then this ensures
consistency (convergence to optimal move). If the score is well done, then
this is consistent without visiting all the tree.

UCT (with non-zero constant) visits all the tree, and does so infinitely
often.
UCT (with zero constant) does not visit all the tree, but it is not
necessarily consistent.

Wow - one of my planned little projects was genetic development of the
> 3x3 patterns... To evaluate patterns, do you use tournaments or some
> smarter method? I feared one generation would take awfully long...
>

We use a stupid method, i.e. the success rate. The pattenrs are bigger than
3x3, with jokers in them. Bandits (Bernstein races, slightly modified) are
used
for distributing the computational effort among the tested patterns.

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

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Petr Baudis]

On Tue, Oct 27, 2009 at 08:47:41AM +0100, Olivier Teytaud wrote:
> > Could you give us at least a general picture of improvements compared to
> > what was last published as 
> > www.lri.fr/~teytaud/eg.pdf? Is it 
> > "just"
> > further tuning and small tweaks or are you trying out some exciting new
> > things? ;-)
> >
> 
> There is one important improvement, for which I must check with coauthors if
> they agree for me to explain it. Below the other recent improvements in 9x9.
> 
> We have also recently encoded some (very simple) tricks against bad cases as
> we had
> against Fan Hui (i.e. cases in which the only good move is not simulated).
> Roughly,
> is the value of the node is very bad, then simulate randomly among the sons.
> We can
> show (mathematically) that with such tricks, we have the consistency (as
> UCT),
> plus some frugality (i.e. we do not simulate all the tree, even with
> infinite computation time whereas UCT simulates all the tree AND simulates
> all the tree infinitely often).
> It gives very little improvement in self-play, but it understands better at
> least the situation seen in the game with Fan Hui. What I like in this
> improvement is that it's
> the first time there is something which was mathematically developped for
> mogo and
> which leads to a positive result. Well, maybe this changes only 1% of games,
> but maybe it makes mogo more robust for complicated ko fights which do not
> occur in self-play.

Interesting! Conceptually, I don't like this that much since it just
work-arounds RAVE bias instead of solving it in more general way, but I
can see its technical value.

AIUI, once upon N simulations in a node you take let's say the node with
the lowest value, pick one son of it at random within the tree and start
a simulation?

> Finally, there was a GP-based development of new patterns. However, this is
> quite minor I guess - I like the fact that this GP-based module works in a
> somehow stable manner, but maybe it would only be worth using it on an
> implementation which is not
> yet optimized.

Wow - one of my planned little projects was genetic development of the
3x3 patterns... To evaluate patterns, do you use tournaments or some
smarter method? I feared one generation would take awfully long...

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Olivier Teytaud]

> Could you give us at least a general picture of improvements compared to
> what was last published as 
> www.lri.fr/~teytaud/eg.pdf? Is it "just"
> further tuning and small tweaks or are you trying out some exciting new
> things? ;-)
>

There is one important improvement, for which I must check with coauthors if
they agree for me to explain it. Below the other recent improvements in 9x9.

We have also recently encoded some (very simple) tricks against bad cases as
we had
against Fan Hui (i.e. cases in which the only good move is not simulated).
Roughly,
is the value of the node is very bad, then simulate randomly among the sons.
We can
show (mathematically) that with such tricks, we have the consistency (as
UCT),
plus some frugality (i.e. we do not simulate all the tree, even with
infinite computation time whereas UCT simulates all the tree AND simulates
all the tree infinitely often).
It gives very little improvement in self-play, but it understands better at
least the situation seen in the game with Fan Hui. What I like in this
improvement is that it's
the first time there is something which was mathematically developped for
mogo and
which leads to a positive result. Well, maybe this changes only 1% of games,
but maybe it makes mogo more robust for complicated ko fights which do not
occur in self-play.

Finally, there was a GP-based development of new patterns. However, this is
quite minor I guess - I like the fact that this GP-based module works in a
somehow stable manner, but maybe it would only be worth using it on an
implementation which is not
yet optimized.

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