Re: [computer-go] How does MC do with ladders?

[Chris Fant]

On Dec 19, 2007 9:40 AM, Heikki Levanto <[EMAIL PROTECTED]> wrote:
> On Wed, Dec 19, 2007 at 12:21:18AM -0500, Chris Fant wrote:
> > I just witnessed CrazyStone defend a fairly long ladder, resulting in
> > a dead 17-stone block.  Why not use a ladder reader at the root of the
> > UCT tree to prevent provably bad ladder moves from being considered?
>
> I don't know for sure, but I suspect that even if it means that it would not
> play out a bad ladder, the UCT would still see it as a desirable thing, and
> direct the game towards one - and then not play it.

Still better than actually playing it out.  Another idea I had was to
do a tactical analysis of a block whenever the UCT node has been hit X
number of times.  When the move is provably pointless (e.g. adding to
a dead block), prevent that line from continuing to be explored.  If X
is large enough and the tactical analysis is restricted enough,
hopefully it won't significantly affect the overall speed.  And it has
the nice trait that it can be used not only at the root but at any
level in the tree.

> Plus, it is not quite trivial to recognize a bad ladder - some times it pays
> off to extend a stone that is in atari, and then sacrifice two stones. Some
> nakade shapes also require sacrificing more than one stone...

But this was the trivial kind and it cost the game.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Heikki Levanto]

On Wed, Dec 19, 2007 at 12:21:18AM -0500, Chris Fant wrote:
> I just witnessed CrazyStone defend a fairly long ladder, resulting in
> a dead 17-stone block.  Why not use a ladder reader at the root of the
> UCT tree to prevent provably bad ladder moves from being considered?

I don't know for sure, but I suspect that even if it means that it would not
play out a bad ladder, the UCT would still see it as a desirable thing, and
direct the game towards one - and then not play it. 

Plus, it is not quite trivial to recognize a bad ladder - some times it pays
off to extend a stone that is in atari, and then sacrifice two stones. Some
nakade shapes also require sacrificing more than one stone...

- Heikki

-- 
Heikki Levanto   "In Murphy We Turst" heikki (at) lsd (dot) dk

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

Re: [computer-go] How does MC do with ladders?

[Chris Fant]

> I just witnessed CrazyStone defend a fairly long ladder, resulting in
> a dead 17-stone block.  Why not use a ladder reader at the root of the
> UCT tree to prevent provably bad ladder moves from being considered?

I meant to include the CGOS-19 game number:  7613

The game is still in progress as of this writing, but once it's
finished, it should be at
http://www.lri.fr/~teytaud/SGF/2007/12/19/7613.sgf
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Chris Fant]

On Dec 11, 2007 11:36 AM, Rémi Coulom <[EMAIL PROTECTED]> wrote:
> >> Question: how do MC programs perform with a long ladder on the board?
> >
> Crazy Stone handles ladder with progressive widening. Ladder atari is
> usually ranked first or very high in the move list, and ladder extension
> lower. So, the tree-search part usually does not read out the ladder
> completely, but prunes the extension. It seems to work well in practice.
> Because progressive widening will include the ladder extension at some
> point, Crazy Stone may still play ladder extensions if it finds reasons
> to do so.

I just witnessed CrazyStone defend a fairly long ladder, resulting in
a dead 17-stone block.  Why not use a ladder reader at the root of the
UCT tree to prevent provably bad ladder moves from being considered?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Forrest Curo]

Quoting Matt Gokey <[EMAIL PROTECTED]>:


similar multi-level or hierarchical/partitioned search
concepts have been suggested by several people here over the years,
myself included many times.


Certainly it's the obvious approach to try. And then, as you say,  
"how" becomes the difficutly!



... but haven't yet figured out how to make it work in practice.  I
tried some things years before MC/UCT popped up without any real
success.



I don't understand the follow-up to your post claiming that you can't
do this for these kinds of games because they are not forcing move
sequences.  We're talking about the play-out part of the search used to
sample the game tree.  Anything goes, right?  Of course, whether any
particular play-out method helps or not is another question.


That was a response to someone else's response, if I understand you.

I'm thinking along the lines of weighted search. Move order matters in  
a game, but not always, and with the first random playouts it's very  
likely that whatever order we've tried was either unimportant or less  
than optimal.


So we'd keep track of which stones, of which color, were on the board  
each time we'd tried a particular move, and whether this had been for  
White or for Black, and whether the outcome was favorable or  
otherwise. As we went along we'd develop a set of features associated  
with successful outcomes plus a different set of features (probably  
overlapping!) associated with unsuccessful outcomes, and it seems  
potentially useful to weight the likelihood of trying a move with the  
square of the number of positive features, minus the square of the  
negative features. I'd expect this to lead to a tendency to both use  
moves from successful local sequences and play them in order, without  
explicitly calling for that.


Mainly I'm thinking of ways a program could generalize from this kind  
of information. The value of one specific point in relation to the  
stones that had been in place in a different game would almost  
certainly change, but perhaps a different point would have a similar  
relationship to stones in the new position.


Every time I actually start coding, some new idea or some new  
objection comes along...


Forrest Curo


This message was sent using IMP, the Internet Messaging Program.

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

Re: [computer-go] How does MC do with ladders?

[Matt Gokey]

Forrest, similar multi-level or hierarchical/partitioned search concepts 
have been suggested by several people here over the years, myself 
included many times.  I first suggested a chunking probability based 
search concept back in 1998.


I have long been an advocate of goal-directed hierarchical search for 
Go, but haven't yet figured out how to make it work in practice.  I 
tried some things years before MC/UCT popped up without any real success.


There could perhaps be some promise in finding ways to combine some of 
these multi-level ideas with MC/UCT search techniques.


I don't understand the follow-up to your post claiming that you can't do 
this for these kinds of games because they are not forcing move 
sequences.  We're talking about the play-out part of the search used to 
sample the game tree.  Anything goes, right?  Of course, whether any 
particular play-out method helps or not is another question.


-Matt

Forrest Curo wrote:

It's the approach I believe to be more human-like.   Not necessarily the
playing style.


Human beings "chunk".

What all this fuss suggests to me is a "meta-mc" program... You include 
routines that work out good sequences, as a human would--and then you 
have the random part of the program include the more promising 
sequences, where applicable, as if they were individual moves.


Forrest Curo


This message was sent using IMP, the Internet Messaging Program.

___
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] How does MC do with ladders?

[Forrest Curo]

Quoting Álvaro Begué <[EMAIL PROTECTED]>:


On Dec 13, 2007 2:28 PM, Forrest Curo <[EMAIL PROTECTED]> wrote:


> It's the approach I believe to be more human-like.   Not necessarily the
> playing style.

Human beings "chunk".

What all this fuss suggests to me is a "meta-mc" program... You
include routines that work out good sequences, as a human would--and
then you have the random part of the program include the more
promising sequences, where applicable, as if they were individual moves.



You can't do that in two-player games, unless you are convinced that the
opponent is forced throughout the entire sequence.


Humans do a sort of skinny alpha-beta, automatically narrowing the  
search by applying constraints based on what they see as possible  
outcomes. (In the case of a ladder, most of this is searching a long  
branch one-move wide!) So if an opponent fails to follow the sequence  
you've expected, he might be on to something you missed, or he may  
have missed the point of the sequence. An unexpected move thus  
suggests a pair of local searches, concentrating both on the vicinity  
of that move and on the vicinity of the expected move.


But for a program to do something similar, it does need some way of  
arriving at an "idea" of what moves in a certain area could reasonably  
be expected to accomplish. Seeing where the groups end up  in a large  
number of playoffs might give a hint...(?)


Forrest Curo


This message was sent using IMP, the Internet Messaging Program.

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

Re: [computer-go] How does MC do with ladders?

[Jason House]

On Dec 13, 2007 3:52 PM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> wrote:

> Jason House wrote:
>
> > The paper introduces RAVE and
> > near the end talks about using heuristics for initial parameter
> > estimation.  The heuristic they used was based TD.
>
> Ah, you're talking about RLGO. RLGO was trained with TD, but MoGo itself
> doesn't use TD (directly).
>
> There are posts from Sylvain and David here that the latest MoGo's use a
> simpler and faster heuristic which works just as well.



Is it possible for you to provide a link to those posts?  I've missed them
but would be highly interested in them.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Gian-Carlo Pascutto]

Jason House wrote:

> The paper introduces RAVE and
> near the end talks about using heuristics for initial parameter
> estimation.  The heuristic they used was based TD.

Ah, you're talking about RLGO. RLGO was trained with TD, but MoGo itself
doesn't use TD (directly).

There are posts from Sylvain and David here that the latest MoGo's use a
simpler and faster heuristic which works just as well.

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

Re: [computer-go] How does MC do with ladders?

[Álvaro Begué]

On Dec 13, 2007 2:28 PM, Forrest Curo <[EMAIL PROTECTED]> wrote:

> > It's the approach I believe to be more human-like.   Not necessarily the
> > playing style.
>
> Human beings "chunk".
>
> What all this fuss suggests to me is a "meta-mc" program... You
> include routines that work out good sequences, as a human would--and
> then you have the random part of the program include the more
> promising sequences, where applicable, as if they were individual moves.


You can't do that in two-player games, unless you are convinced that the
opponent is forced throughout the entire sequence.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Forrest Curo]

It's the approach I believe to be more human-like.   Not necessarily the
playing style.


Human beings "chunk".

What all this fuss suggests to me is a "meta-mc" program... You  
include routines that work out good sequences, as a human would--and  
then you have the random part of the program include the more  
promising sequences, where applicable, as if they were individual moves.


Forrest Curo


This message was sent using IMP, the Internet Messaging Program.

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

Re: [computer-go] How does MC do with ladders?

[Jason House]

On Dec 13, 2007 11:39 AM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> wrote:

> Jason House wrote:
>
> > MoGo uses TD to predict win rates.
>
> Really? Where did you get that information?


I can't seem to load http://www.lri.fr/~gelly/MoGo.htm at the moment, but I
found it there.  One of the papers you can find from there is very heavy in
ML terminology.  It took me a very long time to work my way through it since
I knew nothing about ML.  The paper introduces RAVE and near the end talks
about using heuristics for initial parameter estimation.  The heuristic they
used was based TD.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Gian-Carlo Pascutto]

Jason House wrote:

> MoGo uses TD to predict win rates.  

Really? Where did you get that information?

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

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

Eric,

Yes,  as Magnus also stated MC play-out doesn't really accurately
estimate the "real" winning probability but it still get the move order
right most of the time.  

The situation is that if the position is really a win,  it doesn't mean
that a MC is able to find the proof tree.   But it means that it's
easier to find wins than losses as so the score as expressed by a
winning percentage goes up - but not to 1.0

I have also found that if Lazarus says 60%,   it is going to win much
more than 60% against equal opposition.   Of course it's not surprise if
it beats weaker opposition from this point.   

I thought of mapping these percentages to actual percentages by playing
a few thousand self play games, but this is pretty much futile. If
the score is, for instance 65% it will tend to grow higher and higher
depending on how long I let it think.Unless it discovers a clever
defense that is - so it's possible that it will start declining at a
deep level.

So these numbers are really meaningless as absolute figures and have
everything to do with the current context of the search.

- Don




Eric Boesch wrote:
> On 12/11/07, Mark Boon <[EMAIL PROTECTED]> wrote:
>   
>> Question: how do MC programs perform with a long ladder on the board?
>>
>> My understandig of MC is limited but thinking about it, a crucial
>> long ladder would automatically make the chances of any playout
>> winning 50-50, regardless of the actual outcome of the ladder.
>> 
>
> No, 50/50 would make too much sense. It might be higher or it might be
> lower, depending on whose move it is in the ladder and what style of
> playouts you use, but exactly 50/50 would be like flipping a coin and
> having it land on its edge. In test cases, MC-UCT evaluations tend to
> cluster near 50/50 in any case, because MC-UCT, especially dumb
> uniform MC-UCT, tends to be conservative about predicting the winner,
> especially in 19x19 where the opportunities for luck to overwhelm the
> actual advantage on the board are greater. But if you accept this as
> just a moot scaling issue -- that a clearly lopsided exchange can mean
> just a 2% increment in winning percentage even if read more or less
> correctly -- then the numbers may not look so even after all. I's
> certainly possible for MC-UCT to climb a broken ladder in a winning
> position (and climbing a broken ladder in an even position is at least
> half as bad as that anyhow).
>
> I tried testing this on 19x19 using libego at 1 million playouts per
> move. The behavior was not consistent, but the numbers trended in the
> defender's favor as the sides played out the ladder. In one bizarre
> case, the attacker played out the ladder until there were just 17
> plies left, and then backed off.
>
> Why would the attacker give up a winning ladder? It appears the MC-UCT
> was never actually reading the ladder to begin with; just four or five
> plies in, sometimes just a few thousand simulations were still
> following the key line. 1 million playouts were not nearly enough for
> that in this case; maybe 100 million would be enough, but I couldn't
> test that. Also, after enough simulations, decisively inferior moves
> lead to fewer losses than slightly inferior ones. Suppose you have
> three moves available: one wins 75% of the time, one 50%, and one 25%.
> In the long run, the 75% move will be simulated almost all the time,
> but the middle move will be simulated roughly four times as often as
> the 25% one that, compared to the best move available, is twice as
> bad, and four times the simulations with half the loss per simulation
> adds up to twice the excess losses compared to the 25% move. That is
> apropos here, because giving up on an open-field ladder once it has
> been played out for a dozen moves is much more painful for the
> defender than for the attacker. The longer the ladder got, the more
> the evaluations trended in the defender's favor, and my best
> explanation would be the fact that -- until you actually read the
> ladder all the way out and find that the defender is dead -- every
> move except pulling out of atari is so obviously bad that even uniform
> MC-UCT did a better job of focusing on that one good move.
>
> (Incidentally, the conservative nature of MC-UCT ratings largely
> explains why maximizing winning probabilities alone is not a bad
> strategy, at least in even games. The classic beginner mistake, when
> you already have a clear lead in theory, is to fail to fight hard to
> grab still more points as blunder insurance. But an MC-UCT evaluation
> of 90% typically means a >90% probability of actually winning against
> even opposition, not just a 90% likelihood of a theoretical win.
> Assigning a 65% evaluation to an obvious THEORETICAL win allows plenty
> of room to assign higher evaluations to even more lopsided advantages.
> As Don said, when MC-UCT starts blatantly throwing away points for no
> obvious reason, it's almost certainly because the game is REALLY over,
> bec

Re: [computer-go] How does MC do with ladders?

[Eric Boesch]

On 12/11/07, Mark Boon <[EMAIL PROTECTED]> wrote:
> Question: how do MC programs perform with a long ladder on the board?
>
> My understandig of MC is limited but thinking about it, a crucial
> long ladder would automatically make the chances of any playout
> winning 50-50, regardless of the actual outcome of the ladder.

No, 50/50 would make too much sense. It might be higher or it might be
lower, depending on whose move it is in the ladder and what style of
playouts you use, but exactly 50/50 would be like flipping a coin and
having it land on its edge. In test cases, MC-UCT evaluations tend to
cluster near 50/50 in any case, because MC-UCT, especially dumb
uniform MC-UCT, tends to be conservative about predicting the winner,
especially in 19x19 where the opportunities for luck to overwhelm the
actual advantage on the board are greater. But if you accept this as
just a moot scaling issue -- that a clearly lopsided exchange can mean
just a 2% increment in winning percentage even if read more or less
correctly -- then the numbers may not look so even after all. I's
certainly possible for MC-UCT to climb a broken ladder in a winning
position (and climbing a broken ladder in an even position is at least
half as bad as that anyhow).

I tried testing this on 19x19 using libego at 1 million playouts per
move. The behavior was not consistent, but the numbers trended in the
defender's favor as the sides played out the ladder. In one bizarre
case, the attacker played out the ladder until there were just 17
plies left, and then backed off.

Why would the attacker give up a winning ladder? It appears the MC-UCT
was never actually reading the ladder to begin with; just four or five
plies in, sometimes just a few thousand simulations were still
following the key line. 1 million playouts were not nearly enough for
that in this case; maybe 100 million would be enough, but I couldn't
test that. Also, after enough simulations, decisively inferior moves
lead to fewer losses than slightly inferior ones. Suppose you have
three moves available: one wins 75% of the time, one 50%, and one 25%.
In the long run, the 75% move will be simulated almost all the time,
but the middle move will be simulated roughly four times as often as
the 25% one that, compared to the best move available, is twice as
bad, and four times the simulations with half the loss per simulation
adds up to twice the excess losses compared to the 25% move. That is
apropos here, because giving up on an open-field ladder once it has
been played out for a dozen moves is much more painful for the
defender than for the attacker. The longer the ladder got, the more
the evaluations trended in the defender's favor, and my best
explanation would be the fact that -- until you actually read the
ladder all the way out and find that the defender is dead -- every
move except pulling out of atari is so obviously bad that even uniform
MC-UCT did a better job of focusing on that one good move.

(Incidentally, the conservative nature of MC-UCT ratings largely
explains why maximizing winning probabilities alone is not a bad
strategy, at least in even games. The classic beginner mistake, when
you already have a clear lead in theory, is to fail to fight hard to
grab still more points as blunder insurance. But an MC-UCT evaluation
of 90% typically means a >90% probability of actually winning against
even opposition, not just a 90% likelihood of a theoretical win.
Assigning a 65% evaluation to an obvious THEORETICAL win allows plenty
of room to assign higher evaluations to even more lopsided advantages.
As Don said, when MC-UCT starts blatantly throwing away points for no
obvious reason, it's almost certainly because the game is REALLY over,
because MC-UCT's errors tend to be probabilistic instead of absolute
-- it may in effect evaluate a dead group as 75% alive, but it won't
call it 100% alive except in the rare cases when the underlying random
playout rules forbid the correct line of play.)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

steve uurtamo wrote:
>> Currently there is no evidence whatsoever that probability estimates
>> 
>  are
>   
>> inferior and they are the ones playing the best GO right now
>> 
>
> are they?
>   
Yes - in both 9x9 and 19x19 go.

- Don


> s.
>
>
>
>   
> 
> Looking for last minute shopping deals?  
> Find them fast with Yahoo! Search.  
> http://tools.search.yahoo.com/newsearch/category.php?category=shopping
> ___
> 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] How does MC do with ladders?

[steve uurtamo]

> Currently there is no evidence whatsoever that probability estimates
 are
> inferior and they are the ones playing the best GO right now

are they?

s.



  

Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  
http://tools.search.yahoo.com/newsearch/category.php?category=shopping
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Jason House]

On Dec 13, 2007 2:03 AM, Harald Korneliussen <[EMAIL PROTECTED]> wrote:

> Wed, 12 Dec 2007 07:14:48 -0800 (PST) terry mcintyre wrote:
>
> >Heading back to the central idea, of tuning the predicted winning
> rates and evaluations: it might be useful to examine lost games, look
> for divergence between expectations and reality, repair the predictor,
> and test the new predictor against a large database of such blunders.
>
> Sounds a little like Temporal Difference Learning to me. I understand
> both MoGo and Crazystone use patterns, do anyone know whether they use
> such machine learning techniques to assign weights to them?


MoGo uses TD to predict win rates.  I haven't heard of any other methods to
predict winning rates.  I have seen some successful stuff with predicting
the next move.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Harald Korneliussen]

Wed, 12 Dec 2007 07:14:48 -0800 (PST) terry mcintyre wrote:

>Heading back to the central idea, of tuning the predicted winning
rates and evaluations: it might be useful to examine lost games, look
for divergence between expectations and reality, repair the predictor,
and test the new predictor against a large database of such blunders.

Sounds a little like Temporal Difference Learning to me. I understand
both MoGo and Crazystone use patterns, do anyone know whether they use
such machine learning techniques to assign weights to them?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

Terry,

Yes, I agree with everything here I think.Nobody ever suggested that
we should not improve the accuracy of the probability estimator.

In fact almost all the progress so far has been based on doing exactly
that.   The programs are getting slower but smarter.   

- Don


terry mcintyre wrote:
> Hear, hear! The question is not one of abandonment of the recognition
> of uncertainty. Like Don Dailey, I think it's brilliant that UCT
> programs explicitly manage uncertainty and winning probabilities. My
> concern is that existing implementations have some serious but
> possibly fixable flaws in those estimates; there are numerous
> situations where the game can actually be analytically proven to be
> won by a large margin, but the UCT/MC algorithms are mis-evaluating
> the situation considerably.
>
> I'd be careful about looking merely at winning rates against mediocre
> programs ( and even the best Go programs of today are not that great
> at 19x19 go ). Whenever a human thinks beating lots of mid-kyu players
> makes him Meijin, a few games with a high-dan player or a pro would
> dispel such notions. I'm just asking "what are the next steps?"
>
> It's great that cpu power is getting dramatically cheaper, and great
> that UCT algorithms do improve with more cpus and more playouts, but
> there's a lot of room for improvement. Here's hope that we find lots
> of interesting avenues for such improvements!
>  
> Heading back to the central idea, of tuning the predicted winning
> rates and evaluations: it might be useful to examine lost games, look
> for divergence between expectations and reality, repair the predictor,
> and test the new predictor against a large database of such blunders.
>
> When I was learning to shoot, we were taught to focus first on
> accuracy, second on speed. Under tournament conditions, speed is very
> crucial, but tuning the accuracy of the evaluations is likely to
> reduce the noise rate, and winnow out a fair number of losing plays.
>
> Terry McIntyre <[EMAIL PROTECTED]>
> They mean to govern well; but they mean to govern. They promise to be
> kind masters; but they mean to be masters. -- Daniel Webster
>
>
> - Original Message ----
> From: Raymond Wold <[EMAIL PROTECTED]>
> To: computer-go 
> Sent: Wednesday, December 12, 2007 12:23:15 AM
> Subject: Re: [computer-go] How does MC do with ladders?
>
> On Tue, 2007-12-11 at 21:17 -0500, Don Dailey wrote:
> > But what does this have to do with anything?  What we are "arguing"
> > about is whether it's good to try to estimate probabilities.  That's
> > what you have been critical of.  Adding ladder code will improve any
> > evaluation function if done correctly but that's not relevant if you
> > believe estimating probability is foolish.
> >
> > To the contrary, I believe it is brilliant - in my opinion it is a key
> > factor in the success of these programs and I would call it a key
> > breakthrough.   
>
> Sorry, it just sounded like you lauded the failures of MC as virtues.
> I'm not opposed to random playouts as an evaluator. Just undue hope and
> reliance on it. I think that to make a breakthrough in go AI, we need
> diversity. Both within a program (use what works when it works,
> including dropping any randomness at all when pure knowledge or full
> search would yield results), and between bots. What we *don't* need is
> people giving up on an approach without even trying it, because others
> have failed at something similar before.
>
> ___
> computer-go mailing list
> computer-go@computer-go.org <mailto:computer-go@computer-go.org>
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>
> 
> Looking for last minute shopping deals? Find them fast with Yahoo!
> Search.
> <http://us.rd.yahoo.com/evt=51734/*http://tools.search.yahoo.com/newsearch/category.php?category=shopping>
>
> 
>
> ___
> 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] How does MC do with ladders?

[Nick Wedd]

In message 
<[EMAIL PROTECTED]>, Álvaro 
Begué <[EMAIL PROTECTED]> writes

Why does anybody care about how human-like our go programs' playing
style is? When we design airplanes we don't care about how bird-like
their flying style is; we care about objective measures like speed,
acceleration, energy efficiency... The merits of go programs should be
based basically on their ability to win games, although other measures
might be useful (ability to solve life-and-death problems, or to
estimate the final result of an incomplete game).


You might care if you intend to sell your program.  Customers are 
unhappy when a program they have paid for makes a move that a human 
15-kyu knows is stupid.


But in general, I agree with your point.

Nick


Not being able to read ladders is definitely a weakness of most current
MC programs, and discussing ways of incorporating that knowledge into
them is interesting, but whether they have human styles or not is
completely irrelevant in my opinion.

Álvaro.


On Dec 12, 2007 8:18 AM, Don Dailey <[EMAIL PROTECTED]> wrote:


 Russ Williams wrote:
 > On Dec 11, 2007 8:53 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
 >
 >> The play-out portion is a crude approximation for imagination.  
 We
 >> basically look at a board and imagine the final position.    The
 MC
 >> play-outs kill the dead groups in a reasonably accurate (but
 fuzzy) way
 >> and put the flesh on the skeleton.      Near the end of the game,  
 the
 >> play-outs end mostly the same the way the game itself would end -
 and
 >> the same way a human would expect it to look like.
 >>
 >
 > This seems pretty fishy to me, given that MC can't read ladders
 > accurately, for instance, but any competent human can, and that MC
 > plays so bizarrely differently from humans in many positions,
 > especially endgames.
 >
 > There may be strong theoretical arguments why MC is STRONG, and
 there
 > are clearly empirical demonstrations that MC IS strong, but it is
 not
 > at all clear that MC is somehow simulating/approximating the
 mental
 > process of a human player playing the game.  If it were, I would
 > expect an MC player to make moves that look a lot more human.
 >
 >
 It's not surpising that other methods make it look more like a human
 playing because they are based more on mimicking the moves of a
 human.      Usually a human expert watches the games, see's an error
 and
 then makes a pattern.    The pattern basically says,  "play this move
 because a human would."      That's not the human approach, even
 though
 it will look human.

 It's like the chat bot competitions which are turing tests.   Try to
 fool people into believing they are talking to a human - but really
 it's
 a random phrase generator with some rules and patterns to mimic a
 person.

 - Don


 >> I attribute the success of MC to the fact that it's the best
 simulation
 >> of how WE do it.    The other approaches are clearly more
 synthetic,
 >> including raw MC without a proper tree.
 >>
 >
 > But those synthetic approaches seem MORE like what many human
 players
 > do (at least humans I've talked to), thinking discretely about
 > different domain-specific concrete things like "are there any
 > appropriate josekis for this situation?", "can I kill that group?
 > what is its final internal eye shape going to look like?", "are
 any of
 > my groups endangered?", "is my opponent's moyo invadable? or
 > reducible?", "does this ladder work?", "can these 2 groups be
 > separated?", "can I make these stones live?  can I do it in
 sente?",
 > "who has more ko threats now?", "how big is that ko threat
 compared to
 > the value of this ko?", "where is the biggest endgame move right
 > now?", "where is the biggest sente endgame move right now?",
 "which of
 > these monkey jumps is bigger?", etc.
 >
 > At a literal detailed analysis level, MC is totally different from
 how
 > we do it.  I know of no human player who imagines the 2 players
 > randomly dropping stones over and over to see what proportion of
 > wins/losses results. The basic "philosophy" of MC is radically
 > different from how humans think about the game.  (Which is not to
 say
 > that MC is a bad approach of course.)
 >
 > And at a higher level (in terms of the actual moves that actually
 get
 > chosen by MC), they also look very bizarre compared to a human
 player,
 > particularly in the end game where (as has been discussed a lot
 > recently) a winning MC often fills its own territory or plays
 neutral
 > points when real points still exist, something a
 better-than-beginner
 > (to say nothing of strong) human player would never do.
 >
 > In the opening, strong humans typically are familiar with many
 joseki,
 > which MC is much less likely to randomly follow.
 >
 > And (to mention the actual subject of this thread...) a competent
 > human player can read out most ladders correctly with certainty,
 > unlike MC.
 >
 > and so on...
 >
 > cheers,
 > russ
 > _

Re: [computer-go] How does MC do with ladders?

[terry mcintyre]

Hear, hear! The question is not one of abandonment of the recognition of 
uncertainty. Like Don Dailey, I think it's brilliant that UCT programs 
explicitly manage uncertainty and winning probabilities. My concern is that 
existing implementations have some serious but possibly fixable flaws in those 
estimates; there are numerous situations where the game can actually be 
analytically proven to be won by a large margin, but the UCT/MC algorithms are 
mis-evaluating the situation considerably. 

I'd be careful about looking merely at winning rates against mediocre programs 
( and even the best Go programs of today are not that great at 19x19 go ). 
Whenever a human thinks beating lots of mid-kyu players makes him Meijin, a few 
games with a high-dan player or a pro would dispel such notions. I'm just 
asking "what are the next steps?"

It's great that cpu power is getting dramatically cheaper, and great that UCT 
algorithms do improve with more cpus and more playouts, but there's a lot of 
room for improvement. Here's hope that we find lots of interesting avenues for 
such improvements!
 
Heading back to the central idea, of tuning the predicted winning rates and 
evaluations: it might be useful to examine lost games, look for divergence 
between expectations and reality, repair the predictor, and test the new 
predictor against a large database of such blunders.

When I was learning to shoot, we were taught to focus first on accuracy, second 
on speed. Under tournament conditions, speed is very crucial, but tuning the 
accuracy of the evaluations is likely to reduce the noise rate, and winnow out 
a fair number of losing plays. 


Terry McIntyre <[EMAIL PROTECTED]>
They mean to govern well; but they mean to govern. They promise to be kind 
masters; but they mean to be masters. -- Daniel Webster

- Original Message 
From: Raymond Wold <[EMAIL PROTECTED]>
To: computer-go 
Sent: Wednesday, December 12, 2007 12:23:15 AM
Subject: Re: [computer-go] How does MC do with ladders?


On Tue, 2007-12-11 at 21:17 -0500, Don Dailey wrote:
> But what does this have to do with anything?   What we are "arguing"
> about is whether it's good to try to estimate probabilities.   That's
> what you have been critical of.   Adding ladder code will improve any
> evaluation function if done correctly but that's not relevant if you
> believe estimating probability is foolish.
> 
> To the contrary, I believe it is brilliant - in my opinion it is a
 key
> factor in the success of these programs and I would call it a key
> breakthrough. 

Sorry, it just sounded like you lauded the failures of MC as virtues.
I'm not opposed to random playouts as an evaluator. Just undue hope and
reliance on it. I think that to make a breakthrough in go AI, we need
diversity. Both within a program (use what works when it works,
including dropping any randomness at all when pure knowledge or full
search would yield results), and between bots. What we *don't* need is
people giving up on an approach without even trying it, because others
have failed at something similar before.

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






  

Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  
http://tools.search.yahoo.com/newsearch/category.php?category=shopping___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

Álvaro Begué wrote:
> Why does anybody care about how human-like our go programs' playing
> style is? When we design airplanes we don't care about how bird-like
> their flying style is; we care about objective measures like speed,
> acceleration, energy efficiency... The merits of go programs should be
> based basically on their ability to win games, although other measures
> might be useful (ability to solve life-and-death problems, or to
> estimate the final result of an incomplete game).
>
> Not being able to read ladders is definitely a weakness of most
> current MC programs, and discussing ways of incorporating that
> knowledge into them is interesting, but whether they have human styles
> or not is completely irrelevant in my opinion.
>
I'm with you on this.   I don't care if they "look like" human
players.I care about how strong they play.   However I do believe
you can make an argument that internally they "think" more like a
human.Nevertheless,  no matter how you slice it all program are
synthetic.  

For some reason,  and I don't know if it applies as much in GO,   humans
seem to value a program that plays more "human-like."  Perhaps it
makes them feel that there is more intelligence behind it.

Here is an odd experience from computer chess.Many years ago I had
some experts over to my house and we played games all night long of
speed chess against 2 well known stand-alone programs.   One of them was
well known for it's "human-like" playing style and interesting play.   
The other was well known for it's very solid style and playing strength.   

They very much enjoyed playing the "human-like" program but played many
games against each.   I asked them which was stronger and there was no
question in their mind - it was the one that played human-like.

When I told them that it was the other machine that was stronger (by
quite a large margin) they did not believe me.  So we played several
games between the two and the human-like program lost every game.   The
continued to believe it was some kind of fluke and thus we ended up
playing about 10 games, where every game was a loss for the machine the
believed must be stronger.

This was a bit of an experiment in human psychology I think.I also
believe we are unduly influenced by our eyes.   The weaker machine was
enclosed inside a beautiful sensory board, was physically much larger
and had nice wood pieces.The stronger machine was a couple of years
more up to date but was enclosed in a cheap plastic housing, had a
cheesy pressure sensitive board (you had to press on the squares)  and
had cheap looking plastic pieces - it was a budget computer but it was
clearly stronger. Although I think the playing style was more of an
influence I'm sure the outward appearance of the device played a role.

This is something all retailers know - it's all about the packaging,
advertising, presentation.   Packaging over real substance.

I think us humans are a bit ego-centric.   If something plays like us, 
we probably equate this with actual intelligence.It's like the
warthogs in the far-side comic where the female warthog is saying to the
other female warthog (in a bar) that "he thinks he is god's gift to
warthogs." Warthogs probably think they are beautiful just as we
think we are.

- Don





> Álvaro.
>
>
> On Dec 12, 2007 8:18 AM, Don Dailey <[EMAIL PROTECTED]
> > wrote:
>
>
>
> Russ Williams wrote:
> > On Dec 11, 2007 8:53 PM, Don Dailey <[EMAIL PROTECTED]
> > wrote:
> >
> >> The play-out portion is a crude approximation for imagination.
>   We
> >> basically look at a board and imagine the final position.The MC
> >> play-outs kill the dead groups in a reasonably accurate (but
> fuzzy) way
> >> and put the flesh on the skeleton.  Near the end of the
> game,  the
> >> play-outs end mostly the same the way the game itself would end
> - and
> >> the same way a human would expect it to look like.
> >>
> >
> > This seems pretty fishy to me, given that MC can't read ladders
> > accurately, for instance, but any competent human can, and that MC
> > plays so bizarrely differently from humans in many positions,
> > especially endgames.
> >
> > There may be strong theoretical arguments why MC is STRONG, and
> there
> > are clearly empirical demonstrations that MC IS strong, but it
> is not
> > at all clear that MC is somehow simulating/approximating the mental
> > process of a human player playing the game.  If it were, I would
> > expect an MC player to make moves that look a lot more human.
> >
> >
> It's not surpising that other methods make it look more like a human
> playing because they are based more on mimicking the moves of a
> human.  Usually a human expert watches the games, see's an
> error and
> then makes a pattern.T

Re: [computer-go] How does MC do with ladders?

[Álvaro Begué]

Why does anybody care about how human-like our go programs' playing style
is? When we design airplanes we don't care about how bird-like their flying
style is; we care about objective measures like speed, acceleration, energy
efficiency... The merits of go programs should be based basically on their
ability to win games, although other measures might be useful (ability to
solve life-and-death problems, or to estimate the final result of an
incomplete game).

Not being able to read ladders is definitely a weakness of most current MC
programs, and discussing ways of incorporating that knowledge into them is
interesting, but whether they have human styles or not is completely
irrelevant in my opinion.

Álvaro.


On Dec 12, 2007 8:18 AM, Don Dailey <[EMAIL PROTECTED]> wrote:

>
>
> Russ Williams wrote:
> > On Dec 11, 2007 8:53 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
> >
> >> The play-out portion is a crude approximation for imagination.   We
> >> basically look at a board and imagine the final position.The MC
> >> play-outs kill the dead groups in a reasonably accurate (but fuzzy) way
> >> and put the flesh on the skeleton.  Near the end of the game,  the
> >> play-outs end mostly the same the way the game itself would end - and
> >> the same way a human would expect it to look like.
> >>
> >
> > This seems pretty fishy to me, given that MC can't read ladders
> > accurately, for instance, but any competent human can, and that MC
> > plays so bizarrely differently from humans in many positions,
> > especially endgames.
> >
> > There may be strong theoretical arguments why MC is STRONG, and there
> > are clearly empirical demonstrations that MC IS strong, but it is not
> > at all clear that MC is somehow simulating/approximating the mental
> > process of a human player playing the game.  If it were, I would
> > expect an MC player to make moves that look a lot more human.
> >
> >
> It's not surpising that other methods make it look more like a human
> playing because they are based more on mimicking the moves of a
> human.  Usually a human expert watches the games, see's an error and
> then makes a pattern.The pattern basically says,  "play this move
> because a human would."  That's not the human approach, even though
> it will look human.
>
> It's like the chat bot competitions which are turing tests.   Try to
> fool people into believing they are talking to a human - but really it's
> a random phrase generator with some rules and patterns to mimic a person.
>
> - Don
>
>
> >> I attribute the success of MC to the fact that it's the best simulation
> >> of how WE do it.The other approaches are clearly more synthetic,
> >> including raw MC without a proper tree.
> >>
> >
> > But those synthetic approaches seem MORE like what many human players
> > do (at least humans I've talked to), thinking discretely about
> > different domain-specific concrete things like "are there any
> > appropriate josekis for this situation?", "can I kill that group?
> > what is its final internal eye shape going to look like?", "are any of
> > my groups endangered?", "is my opponent's moyo invadable? or
> > reducible?", "does this ladder work?", "can these 2 groups be
> > separated?", "can I make these stones live?  can I do it in sente?",
> > "who has more ko threats now?", "how big is that ko threat compared to
> > the value of this ko?", "where is the biggest endgame move right
> > now?", "where is the biggest sente endgame move right now?", "which of
> > these monkey jumps is bigger?", etc.
> >
> > At a literal detailed analysis level, MC is totally different from how
> > we do it.  I know of no human player who imagines the 2 players
> > randomly dropping stones over and over to see what proportion of
> > wins/losses results. The basic "philosophy" of MC is radically
> > different from how humans think about the game.  (Which is not to say
> > that MC is a bad approach of course.)
> >
> > And at a higher level (in terms of the actual moves that actually get
> > chosen by MC), they also look very bizarre compared to a human player,
> > particularly in the end game where (as has been discussed a lot
> > recently) a winning MC often fills its own territory or plays neutral
> > points when real points still exist, something a better-than-beginner
> > (to say nothing of strong) human player would never do.
> >
> > In the opening, strong humans typically are familiar with many joseki,
> > which MC is much less likely to randomly follow.
> >
> > And (to mention the actual subject of this thread...) a competent
> > human player can read out most ladders correctly with certainty,
> > unlike MC.
> >
> > and so on...
> >
> > cheers,
> > russ
> > ___
> > computer-go mailing list
> > computer-go@computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> >
> ___
> computer-go mailing list
> computer-go@comput

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

Russ Williams wrote:
> On Dec 11, 2007 8:53 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
>   
>> The play-out portion is a crude approximation for imagination.   We
>> basically look at a board and imagine the final position.The MC
>> play-outs kill the dead groups in a reasonably accurate (but fuzzy) way
>> and put the flesh on the skeleton.  Near the end of the game,  the
>> play-outs end mostly the same the way the game itself would end - and
>> the same way a human would expect it to look like.
>> 
>
> This seems pretty fishy to me, given that MC can't read ladders
> accurately, for instance, but any competent human can, and that MC
> plays so bizarrely differently from humans in many positions,
> especially endgames.
>
> There may be strong theoretical arguments why MC is STRONG, and there
> are clearly empirical demonstrations that MC IS strong, but it is not
> at all clear that MC is somehow simulating/approximating the mental
> process of a human player playing the game.  If it were, I would
> expect an MC player to make moves that look a lot more human.
>
>   
It's not surpising that other methods make it look more like a human
playing because they are based more on mimicking the moves of a
human.  Usually a human expert watches the games, see's an error and
then makes a pattern.The pattern basically says,  "play this move
because a human would."  That's not the human approach, even though
it will look human.  

It's like the chat bot competitions which are turing tests.   Try to
fool people into believing they are talking to a human - but really it's
a random phrase generator with some rules and patterns to mimic a person.

- Don
 

>> I attribute the success of MC to the fact that it's the best simulation
>> of how WE do it.The other approaches are clearly more synthetic,
>> including raw MC without a proper tree.
>> 
>
> But those synthetic approaches seem MORE like what many human players
> do (at least humans I've talked to), thinking discretely about
> different domain-specific concrete things like "are there any
> appropriate josekis for this situation?", "can I kill that group?
> what is its final internal eye shape going to look like?", "are any of
> my groups endangered?", "is my opponent's moyo invadable? or
> reducible?", "does this ladder work?", "can these 2 groups be
> separated?", "can I make these stones live?  can I do it in sente?",
> "who has more ko threats now?", "how big is that ko threat compared to
> the value of this ko?", "where is the biggest endgame move right
> now?", "where is the biggest sente endgame move right now?", "which of
> these monkey jumps is bigger?", etc.
>
> At a literal detailed analysis level, MC is totally different from how
> we do it.  I know of no human player who imagines the 2 players
> randomly dropping stones over and over to see what proportion of
> wins/losses results. The basic "philosophy" of MC is radically
> different from how humans think about the game.  (Which is not to say
> that MC is a bad approach of course.)
>
> And at a higher level (in terms of the actual moves that actually get
> chosen by MC), they also look very bizarre compared to a human player,
> particularly in the end game where (as has been discussed a lot
> recently) a winning MC often fills its own territory or plays neutral
> points when real points still exist, something a better-than-beginner
> (to say nothing of strong) human player would never do.
>
> In the opening, strong humans typically are familiar with many joseki,
> which MC is much less likely to randomly follow.
>
> And (to mention the actual subject of this thread...) a competent
> human player can read out most ladders correctly with certainty,
> unlike MC.
>
> and so on...
>
> cheers,
> russ
> ___
> 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] How does MC do with ladders?

[Don Dailey]

David Fotland wrote:
> I don't think traditional go programs "tally features and weights".  They
> estimate the final score.
>   
When I say "tally features and weights" I really mean that they estimate
the final score.   They basically tally the number of intersections
expected to be won, although I'm sure there is a great deal of
sophistication in this. I have seen descriptions where they estimate
a groups survival likelihood, and if it's say 50% they give it 50% of
the area encompassed.


> There have been prior global game tree approaches.  Handtalk and GO
> Intellect and SmartGo did global searches a decade ago.
>
> This is not to detract from UCT, which works very well.  UCT/MC programs
> make moves that look very unnatural, so in that sense they don't play at all
> like humans play go.
>   
It's the approach I believe to be more human-like.   Not necessarily the
playing style.

- Don

> David
>
>   
>> -Original Message-
>> From: [EMAIL PROTECTED] [mailto:computer-go-
>> [EMAIL PROTECTED] On Behalf Of Don Dailey
>> Sent: Tuesday, December 11, 2007 11:53 AM
>> To: computer-go
>> Subject: Re: [computer-go] How does MC do with ladders?
>>
>> Hi Petri,
>>
>> I happen to think that MC is the most human like approach currently
>> being tried.
>>
>> The reason I say that is that humans DO estimate their winning chances
>> and "tally" methods, where you simply tally up features/weights
>> (regardless of how sophisticated)  is not how strong humans think about
>> the game.
>>
>> Also, the best first global game tree approach, whatever you call it
>> such as UCT and others,  is a very close model of how humans play the
>> game too.We may notice 3 moves that look playable, but gradually
>> come to focus on just 2 of those.   Essentially monte carlo does this
>> too.Very narrow focused trees.
>>
>> The play-out portion is a crude approximation for imagination.   We
>> basically look at a board and imagine the final position.The MC
>> play-outs kill the dead groups in a reasonably accurate (but fuzzy) way
>> and put the flesh on the skeleton.  Near the end of the game,  the
>> play-outs end mostly the same the way the game itself would end - and
>> the same way a human would expect it to look like.
>>
>> I attribute the success of MC to the fact that it's the best simulation
>> of how WE do it.The other approaches are clearly more synthetic,
>> including raw MC without a proper tree.
>>
>> - Don
>>
>>
>> Petri Pitkanen wrote:
>> 
>>> 2007/12/11, terry mcintyre <[EMAIL PROTECTED]>:
>>>
>>>   
>>>> With Go, there are many situations which can be read out precisely,
>>>> 
>> provided
>> 
>>>> that one has the proper tools - ladders, the ability to distinguish
>>>> 
>> between
>> 
>>>> one and two eyes; the ability to reduce eyespaces to a single eye
>>>> 
>> with an
>> 
>>>> appropriate placement; and so forth. Failure to recognize such
>>>> 
>> situations is
>> 
>>>> like failing to spot a pinned piece or a passed pawn.
>>>>
>>>>
>>>> 
>>> I am no fan on MC approach but basically MC can read L&D given enough
>>> of simulations. It will read them without knowing that they need to
>>>   
>> be
>> 
>>> analysed. Point in MC being that once you get more power you get
>>> better L&D as well, but without extra coding.
>>>
>>> This approach will result in non-human like game BUT likewise chess
>>> programs did not get strong by emulating humans. They just took one
>>> simple thing humans do and took it to extreme. Whatever approach will
>>> do the trick in go it will be similar in this sense.
>>>
>>>
>>>   
>> ___
>> computer-go mailing list
>> computer-go@computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>> 
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>   
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Harald Korneliussen]

Raymond Wold wrote:

>I can code an algorithm that evaluates simple ladders correctly.

>I'll repeat that. I can code a program that reads ladders better than a
>pure MC program without knowledge of ladders. I can beat it. Human
>knowledge programmed into a computer that does that one thing, that
>basic go skill, better than the MC program.

>Are you saying that there is absolutely no way to combine such with an
>MC program to make it better? Not just that no one has done it (I don't
>know if anyone has) but that it is impossible? Are you saying that
>attempts to do so are wasted? If you are, I'd appreciate it if you did
>so clearly.

Complaining that MC programs don't read ladders well is a bit like
complaining that Forrest Gump can't tie his shoelaces, it seems to me.
There will be many things an MC program will be good at that we won't
be, and vice versa. It's not unreasonable to believe that progress
with MC/UCT programs will be through making most of its strengths,
rather than try to patch its weaknesses in a way not compatible with
"how their brains work".
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Raymond Wold]

On Tue, 2007-12-11 at 21:17 -0500, Don Dailey wrote:
> But what does this have to do with anything?   What we are "arguing"
> about is whether it's good to try to estimate probabilities.   That's
> what you have been critical of.   Adding ladder code will improve any
> evaluation function if done correctly but that's not relevant if you
> believe estimating probability is foolish.
> 
> To the contrary, I believe it is brilliant - in my opinion it is a key
> factor in the success of these programs and I would call it a key
> breakthrough. 

Sorry, it just sounded like you lauded the failures of MC as virtues.
I'm not opposed to random playouts as an evaluator. Just undue hope and
reliance on it. I think that to make a breakthrough in go AI, we need
diversity. Both within a program (use what works when it works,
including dropping any randomness at all when pure knowledge or full
search would yield results), and between bots. What we *don't* need is
people giving up on an approach without even trying it, because others
have failed at something similar before.

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

Re: [computer-go] How does MC do with ladders?

[Russ Williams]

On Dec 11, 2007 8:53 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
> The play-out portion is a crude approximation for imagination.   We
> basically look at a board and imagine the final position.The MC
> play-outs kill the dead groups in a reasonably accurate (but fuzzy) way
> and put the flesh on the skeleton.  Near the end of the game,  the
> play-outs end mostly the same the way the game itself would end - and
> the same way a human would expect it to look like.

This seems pretty fishy to me, given that MC can't read ladders
accurately, for instance, but any competent human can, and that MC
plays so bizarrely differently from humans in many positions,
especially endgames.

There may be strong theoretical arguments why MC is STRONG, and there
are clearly empirical demonstrations that MC IS strong, but it is not
at all clear that MC is somehow simulating/approximating the mental
process of a human player playing the game.  If it were, I would
expect an MC player to make moves that look a lot more human.

> I attribute the success of MC to the fact that it's the best simulation
> of how WE do it.The other approaches are clearly more synthetic,
> including raw MC without a proper tree.

But those synthetic approaches seem MORE like what many human players
do (at least humans I've talked to), thinking discretely about
different domain-specific concrete things like "are there any
appropriate josekis for this situation?", "can I kill that group?
what is its final internal eye shape going to look like?", "are any of
my groups endangered?", "is my opponent's moyo invadable? or
reducible?", "does this ladder work?", "can these 2 groups be
separated?", "can I make these stones live?  can I do it in sente?",
"who has more ko threats now?", "how big is that ko threat compared to
the value of this ko?", "where is the biggest endgame move right
now?", "where is the biggest sente endgame move right now?", "which of
these monkey jumps is bigger?", etc.

At a literal detailed analysis level, MC is totally different from how
we do it.  I know of no human player who imagines the 2 players
randomly dropping stones over and over to see what proportion of
wins/losses results. The basic "philosophy" of MC is radically
different from how humans think about the game.  (Which is not to say
that MC is a bad approach of course.)

And at a higher level (in terms of the actual moves that actually get
chosen by MC), they also look very bizarre compared to a human player,
particularly in the end game where (as has been discussed a lot
recently) a winning MC often fills its own territory or plays neutral
points when real points still exist, something a better-than-beginner
(to say nothing of strong) human player would never do.

In the opening, strong humans typically are familiar with many joseki,
which MC is much less likely to randomly follow.

And (to mention the actual subject of this thread...) a competent
human player can read out most ladders correctly with certainty,
unlike MC.

and so on...

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

Re: [computer-go] How does MC do with ladders?

[Petri Pitkanen]

2007/12/11, Don Dailey <[EMAIL PROTECTED]>:
> Hi Petri,
>
> I happen to think that MC is the most human like approach currently
> being tried

Ye in sense Alpha-Beta is human like. It one feature we do and takes
it to extreme. And using different method of evaluation.
.
>
> The reason I say that is that humans DO estimate their winning chances
> and "tally" methods, where you simply tally up features/weights
> (regardless of how sophisticated)  is not how strong humans think about
> the game.
>
Tallying up ius the non-human part. Extracting features and assigning
meaning to them is very human. Good go player describe moves they make
with terms like thicknes, wall, spere of influence,invasion.
Obviously these are not needed if one searches deep enough but how
deep that would be?

> game too.We may notice 3 moves that look playable, but gradually
> come to focus on just 2 of those.   Essentially monte carlo does this
> too.Very narrow focused trees.
Here we completely agree. It just picks the moves with different
emphasis. And we do tactical analysis all the time. Something MC
program is pretty weak at. I for instance played MOGO and it refused
to resign until I places a dead group in atari. Any 20 would have seen
that specific situation. Still that same 20 would have lost the game
easily. So this is very unlike humans
>
> I attribute the success of MC to the fact that it's the best simulation
> of how WE do it.The other approaches are clearly more synthetic,
> including raw MC without a proper tree.
>
It could be the best but it is not very close. And adding more go
knowledge to it may make it weaker by consuming CPU. There must be a
third way. But this is the best idea that has posppoed up in years -
or more like a decade

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

RE: [computer-go] How does MC do with ladders?

[David Fotland]

I don't think traditional go programs "tally features and weights".  They
estimate the final score.

There have been prior global game tree approaches.  Handtalk and GO
Intellect and SmartGo did global searches a decade ago.

This is not to detract from UCT, which works very well.  UCT/MC programs
make moves that look very unnatural, so in that sense they don't play at all
like humans play go.

David

> -Original Message-
> From: [EMAIL PROTECTED] [mailto:computer-go-
> [EMAIL PROTECTED] On Behalf Of Don Dailey
> Sent: Tuesday, December 11, 2007 11:53 AM
> To: computer-go
> Subject: Re: [computer-go] How does MC do with ladders?
> 
> Hi Petri,
> 
> I happen to think that MC is the most human like approach currently
> being tried.
> 
> The reason I say that is that humans DO estimate their winning chances
> and "tally" methods, where you simply tally up features/weights
> (regardless of how sophisticated)  is not how strong humans think about
> the game.
> 
> Also, the best first global game tree approach, whatever you call it
> such as UCT and others,  is a very close model of how humans play the
> game too.We may notice 3 moves that look playable, but gradually
> come to focus on just 2 of those.   Essentially monte carlo does this
> too.Very narrow focused trees.
> 
> The play-out portion is a crude approximation for imagination.   We
> basically look at a board and imagine the final position.The MC
> play-outs kill the dead groups in a reasonably accurate (but fuzzy) way
> and put the flesh on the skeleton.  Near the end of the game,  the
> play-outs end mostly the same the way the game itself would end - and
> the same way a human would expect it to look like.
> 
> I attribute the success of MC to the fact that it's the best simulation
> of how WE do it.The other approaches are clearly more synthetic,
> including raw MC without a proper tree.
> 
> - Don
> 
> 
> Petri Pitkanen wrote:
> > 2007/12/11, terry mcintyre <[EMAIL PROTECTED]>:
> >
> >> With Go, there are many situations which can be read out precisely,
> provided
> >> that one has the proper tools - ladders, the ability to distinguish
> between
> >> one and two eyes; the ability to reduce eyespaces to a single eye
> with an
> >> appropriate placement; and so forth. Failure to recognize such
> situations is
> >> like failing to spot a pinned piece or a passed pawn.
> >>
> >>
> >
> > I am no fan on MC approach but basically MC can read L&D given enough
> > of simulations. It will read them without knowing that they need to
> be
> > analysed. Point in MC being that once you get more power you get
> > better L&D as well, but without extra coding.
> >
> > This approach will result in non-human like game BUT likewise chess
> > programs did not get strong by emulating humans. They just took one
> > simple thing humans do and took it to extreme. Whatever approach will
> > do the trick in go it will be similar in this sense.
> >
> >
> ___
> 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] How does MC do with ladders?

[Don Dailey]

I have had this experience many times:

   1. You see a move that sucks.
   2.  You identify the problem and engineer a solution.
   3.  The solution indeed works - it cures the problem.
   4.  The program plays worse than it did before.

By the way,  you are being modest,  Antigo is not bad on 9x9.It's
true there is a pack of programs that are way out front, but they are
mostly different version of just 3 or 4 programs.   Your program would
be the top program if it was on the server 2 years ago.   Do you
remember when CGOS started?It was an impressive feat to break 1800
back then.

- Don




[EMAIL PROTECTED] wrote:
> My engine, Antigo, is not one of the strongest and only plays 9x9
> games. It does not read ladders correctly unless they are short enough
> for the tree to handle it. But I could uncomment a few lines of code
> and then the playouts would know how to handle simple ladders for
> external nodes. The rules in the heavy playouts can be tuned so that
> both colors will play out any ladder. Or each color can read ahead,
> during the playout, to decide whether or not to continue a ladder-like
> Valkyria does. In my experience, both ways produce a net decrease in
> playing strength for my particular bot.
>
> Adjusting the heavy playout rules to deal with particular tactical
> issues leads to a lot of unintended consequences.
>
> I've also tried doing a tactical analysis for each string
> (coincidentally also using MC/UCT) as a first pass at the root node
> and using information from that to inform the playouts. It almost
> helps... it ought to help... if I tried one more thing...
>
> I'd be happy to accept that any sort of traditional go information
> *might* improve MC/UCT. But until it gets down to specifics, there's
> not much to argue about.
>
> - Dave Hillis
> 
> More new features than ever. Check out the new AIM(R) Mail
> !
> 
>
> ___
> 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] How does MC do with ladders?

[Don Dailey]

Raymond,

Playing a strong game of go is a combination of many factors, not just
reading ladders.You could probably isolate out any particular skill
and write some code that does it pretty well.   But the question will
always be:  "How well does it actually play the game?"

As has been stated here many times,  improving some specific skill could
actually hurt the overall strength.What you want is the best program
overall - one that knows how to win games.   I don't care if you can
make a great ladder reader if the program sucks.


Raymond Wold wrote:
> On Tue, 2007-12-11 at 13:45 -0500, Don Dailey wrote:
>   
>> Do you know of an approach that evaluates go positions perfectly?You
>> are attacking the fact that MC programs have errors in their probability
>> estimates but completely ignoring the fact that SO DOES EVERY OTHER
>> EVALUATION FUNCTION.  
>> 
>
> I can code an algorithm that evaluates simple ladders correctly.
>
> I'll repeat that. I can code a program that reads ladders better than a
> pure MC program without knowledge of ladders. I can beat it. Human
> knowledge programmed into a computer that does that one thing, that
> basic go skill, better than the MC program.
>
> Are you saying that there is absolutely no way to combine such with an
> MC program to make it better? Not just that no one has done it (I don't
> know if anyone has) but that it is impossible? Are you saying that
> attempts to do so are wasted? If you are, I'd appreciate it if you did
> so clearly.
>   
This is the course MC programs have been taking all along,  adding
domain specific (and otherwise) knowledge to the play-outs.Of course
you can add ladder code.

But what does this have to do with anything?   What we are "arguing"
about is whether it's good to try to estimate probabilities.   That's
what you have been critical of.   Adding ladder code will improve any
evaluation function if done correctly but that's not relevant if you
believe estimating probability is foolish.

To the contrary, I believe it is brilliant - in my opinion it is a key
factor in the success of these programs and I would call it a key
breakthrough. 

- Don


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

Re: [computer-go] How does MC do with ladders?

[dhillismail]

My engine, Antigo, is not one of the strongest and only plays 9x9 games. It 
does not read ladders correctly unless they are short enough for the tree to 
handle it. But I could uncomment a few lines of code and then the playouts 
would know how to handle simple ladders for external nodes. The rules in the 
heavy playouts can be tuned so that both colors will play out any ladder. 
Or?each color?can read ahead, during the playout,?to decide whether or not to 
continue a ladder-like Valkyria does. In my experience, both ways produce a net 
decrease in playing strength for my particular bot.

Adjusting the heavy playout rules to deal with particular tactical issues leads 
to a lot of unintended consequences.

I've also tried doing a tactical analysis for each string (coincidentally also 
using MC/UCT) as a first pass at the root node and using information from that 
to inform the playouts. It almost helps... it ought to help... if I tried one 
more thing...

I'd be happy to accept that any sort of traditional go information *might* 
improve MC/UCT. But until it gets down to specifics, there's not much to argue 
about.

- Dave Hillis



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Chris Fant]

> Since Valkyria is slow anyway, I can have it read ladders in the
> simulations. The ladder code is really fast and a little buggy, but
> works often enough to not cause major problems. I never tested the
> benefits of the ladder code it just appeared to be much stronger.
>
> -Magnus

What do you do with the knowledge learned by reading out the ladder in
a simulation?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Sanghyeon Seo]

2007/12/12, Raymond Wold <[EMAIL PROTECTED]>:
> Are you saying that there is absolutely no way to combine such with an
> MC program to make it better? Not just that no one has done it (I don't
> know if anyone has) but that it is impossible? Are you saying that
> attempts to do so are wasted? If you are, I'd appreciate it if you did
> so clearly.

As already stated, Valkyria, a strong MC/UCT program, is known to read
ladders in simulation.

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

Re: [computer-go] How does MC do with ladders?

[Raymond Wold]

On Tue, 2007-12-11 at 13:45 -0500, Don Dailey wrote:
> Do you know of an approach that evaluates go positions perfectly?You
> are attacking the fact that MC programs have errors in their probability
> estimates but completely ignoring the fact that SO DOES EVERY OTHER
> EVALUATION FUNCTION.  

I can code an algorithm that evaluates simple ladders correctly.

I'll repeat that. I can code a program that reads ladders better than a
pure MC program without knowledge of ladders. I can beat it. Human
knowledge programmed into a computer that does that one thing, that
basic go skill, better than the MC program.

Are you saying that there is absolutely no way to combine such with an
MC program to make it better? Not just that no one has done it (I don't
know if anyone has) but that it is impossible? Are you saying that
attempts to do so are wasted? If you are, I'd appreciate it if you did
so clearly.

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

Re: [computer-go] How does MC do with ladders?

[Eric Boesch]

Make sure that you use the -19 argument when starting 19x19 Mogo, and
restart GoGui (in order to restart Mogo indirectly) after you change
the settings. Somewhat confusingly, Mogo does not automatically play
19x19 style just because it receives a request for 19x19 board. Poor
ladder handling and "squeezing the toothpaste" are both behaviors that
Mogo can exhibit when playing 9x9-style on the 19x19 board. If,
assuming you're in GoGui, the GTP shell window shows "shishoCheck is
called" comments, then you're really playing 19x19 style.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

Hi Petri,

I happen to think that MC is the most human like approach currently
being tried.  

The reason I say that is that humans DO estimate their winning chances
and "tally" methods, where you simply tally up features/weights
(regardless of how sophisticated)  is not how strong humans think about
the game. 

Also, the best first global game tree approach, whatever you call it
such as UCT and others,  is a very close model of how humans play the
game too.We may notice 3 moves that look playable, but gradually
come to focus on just 2 of those.   Essentially monte carlo does this
too.Very narrow focused trees.

The play-out portion is a crude approximation for imagination.   We
basically look at a board and imagine the final position.The MC
play-outs kill the dead groups in a reasonably accurate (but fuzzy) way
and put the flesh on the skeleton.  Near the end of the game,  the
play-outs end mostly the same the way the game itself would end - and
the same way a human would expect it to look like.

I attribute the success of MC to the fact that it's the best simulation
of how WE do it.The other approaches are clearly more synthetic,
including raw MC without a proper tree.

- Don


Petri Pitkanen wrote:
> 2007/12/11, terry mcintyre <[EMAIL PROTECTED]>:
>   
>> With Go, there are many situations which can be read out precisely, provided
>> that one has the proper tools - ladders, the ability to distinguish between
>> one and two eyes; the ability to reduce eyespaces to a single eye with an
>> appropriate placement; and so forth. Failure to recognize such situations is
>> like failing to spot a pinned piece or a passed pawn.
>>
>> 
>
> I am no fan on MC approach but basically MC can read L&D given enough
> of simulations. It will read them without knowing that they need to be
> analysed. Point in MC being that once you get more power you get
> better L&D as well, but without extra coding.
>
> This approach will result in non-human like game BUT likewise chess
> programs did not get strong by emulating humans. They just took one
> simple thing humans do and took it to extreme. Whatever approach will
> do the trick in go it will be similar in this sense.
>
>   
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Petri Pitkanen]

2007/12/11, terry mcintyre <[EMAIL PROTECTED]>:
> With Go, there are many situations which can be read out precisely, provided
> that one has the proper tools - ladders, the ability to distinguish between
> one and two eyes; the ability to reduce eyespaces to a single eye with an
> appropriate placement; and so forth. Failure to recognize such situations is
> like failing to spot a pinned piece or a passed pawn.
>

I am no fan on MC approach but basically MC can read L&D given enough
of simulations. It will read them without knowing that they need to be
analysed. Point in MC being that once you get more power you get
better L&D as well, but without extra coding.

This approach will result in non-human like game BUT likewise chess
programs did not get strong by emulating humans. They just took one
simple thing humans do and took it to extreme. Whatever approach will
do the trick in go it will be similar in this sense.

-- 
Petri Pitkänen
e-mail: [EMAIL PROTECTED]
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[terry mcintyre]

At this point, it has to be said that _all_ computer go programs suck at 19xc19 
go. MC programs happen to suck less, especially on small boards.

On the other hand, we do have some very strong special-purpose go programs. 
There are several very strong tsumego/life-and-death programs and at least one 
endgame program. There are some fairly strong fuseki predictors. 

I'm hoping the goal is to develop programs strong enough to play a credible 
game against dan-level humans on a 19x19 board. If we ever figure out how to 
merge the great strengths of UCT/MC with these other strengths, we'd be a good 
bit closer.

If a program is able able to learn from examples and experience. I'd feed it a 
library of go problems, and keep training until the right line of play, and the 
refutations of bad play, are quickly and reliably found for hundreds or 
thousands of games. Often, there is one right line of play, and very many bad 
lines. Important to know the difference. 



  

Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  
http://tools.search.yahoo.com/newsearch/category.php?category=shopping___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

terry mcintyre wrote:
> Ladders are not hard, especially if one is permitted to place stones
> on the (virtual) board to trace the flow. A 20 kyu human can follow
> the logic.
>
> Don, you describe some subtle choices of playing one's opponent, and
> compare them to MC programs, but you are a fairly strong chess player.
> If you were counseling a beginner, you'd surely urge him/her to focus
> on getting the basics right before getting fancy with estimations of
> winning probability vis a vis particular opponents.
For beginners I would strongly council to play the board, not the opponent.

At the top level it's not really like this.You must play soundly but
there is a huge element of playing the opponent. The most basic
winning technique is to constantly present problems to your opponent -
even though this may have little to do with the game theoretic score.  
Part of the reason for this is that if you do it to him,  he is too busy
to hurt you.But the real point is that you want to provoke an
error.   If you don't play this way at the higher level most games would
end in a draw.2700 players do not want to draw 2500 players too much
so must play provocatively. Top level players tend to draw each
other a lot unless the results are very important - and even then it's
difficult to get out of a draw.

Here is some advice for playing against stronger players:   Don't change
your game.  Play the same way you normally would.If you like
tactics, don't be afraid to mix it up. It's not that this is likely
to give you a win, but it's certainly not going the help you to change
your style. 

When your opponent is in time pressure,  naive players start playing
really fast in order to add to their opponents time pressure.This is
a really stupid mistake.   You are giving away your only advantage, the
fact that you have more time than your opponent.  Duhhh!   

In fact, there might even be some benefit to playing a little slower
than usual.   In time pressure your opponent has the advantage of the
adrenalin in his system and it actually helps him.But you cannot
maintain an adrenalin rush for too long without it washing you out.
So if he has 1 minute on his clock, you can keep his adrenalin going for
20 minutes he will be exhausted before long.   Many mistakes are made
immediately after time-control has been reach and the player thinks he
is safe.  

All of these things are attempts to play the opponent and it usually
turns out that this is foolish.   You are upsetting and distracting
yourself from the game when you do this and only if you really know what
you are doing should playing the opponent be attempted. 
 

>
> Go and chess differ in a fundamental way. With chess, many positions
> may be genuinely unknowable, beyond human/machine ability to measure
> the exact outcome; a probabilistic approach may be well suited to such
> situations. With Go, there are many situations which can be read out
> precisely, provided that one has the proper tools - ladders, the
> ability to distinguish between one and two eyes; the ability to reduce
> eyespaces to a single eye with an appropriate placement; and so forth.
> Failure to recognize such situations is like failing to spot a pinned
> piece or a passed pawn.
But so far, the evidence says the probabilistic approach works in GO and
so far nobody has demonstrated a strong chess program that uses this
approach. However I don't know if anyone has seriously tried in chess.
>
> Every now and then, I have the opportunity to play a pro, or watch a
> pro against other amateur players. Even 4 and 5 dan amateurs find
> their groups crumbling against pro players. But in many cases, the pro
> simply exploits weak shape - reducing groups to the "one eyed state."
>
> Evaluating winning odds depends upon evaluating the final score at the
> leaf nodes, which depends on being able to distinguish between one and
> two eyes, to count liberties in capturing races, to recognize seki, to
> read ladders, and other basic skills.  At some point in the game, an
> evaluation function should be able to quickly and accurately report
> "oops, just lost ten or twenty points, with no compensating gain,
> therefore the score is -15; this node should be reported as a lost
> game, back up and try something different." The earlier one can make
> such accurate assessments, the better one's game.
>
I am a lousy go player,  but I started out counting stones,  trying to
win everything.   I think I definitely made a step forward when I
started mentally mapping out the board.   I actually learned this from
my own monte carlo program.   I try to figure out exactly what I need to
win and then  I focus on that.That doesn't mean you are not flexible
and opportunistic - if I have a chance to grab a piece I didn't expect, 
it's that much less I have to worry about elsewhere.Then at some
point I consolidate, making sure if I'm winning I don't attempt any
foolish excursions. 

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

Raymond Wold wrote:
> On Tue, 2007-12-11 at 11:42 -0500, Don Dailey wrote:
>   
>> In fact, this illustrates a wonderful strength of these programs.
>> 
>
> Only it's not strength to ignore a move to your benefit, 

Who suggested that it was? The strength of MC programs is how they
deal with uncertainty,  not the fact that there is uncertainty.  So
what method do you propose that is immune to uncertainty?   


> when it's
> something a 20 kyu human can read out. Nor is it strength when you play
> out a dead ladder, no matter if you're behind.   
>   
Do you know of an approach that evaluates go positions perfectly?You
are attacking the fact that MC programs have errors in their probability
estimates but completely ignoring the fact that SO DOES EVERY OTHER
EVALUATION FUNCTION.  

Currently there is no evidence whatsoever that probability estimates are
inferior and they are the ones playing the best GO right now,  so the
burden of proof is on you.   It's not enough to simply find games where
they played a bad move,  unless you can show that other approaches are
not as subject to bad moves.

- Don


> Pure MC will /not/ cure cancer.
>
> ___
> 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] How does MC do with ladders?

[terry mcintyre]

Ladders are not hard, especially if one is permitted to place stones on the 
(virtual) board to trace the flow. A 20 kyu human can follow the logic. 

Don, you describe some subtle choices of playing one's opponent, and compare 
them to MC programs, but you are a fairly strong chess player. If you were 
counseling a beginner, you'd surely urge him/her to focus on getting the basics 
right before getting fancy with estimations of winning probability vis a vis 
particular opponents.

Go and chess differ in a fundamental way. With chess, many positions may be 
genuinely unknowable, beyond human/machine ability to measure the exact 
outcome; a probabilistic approach may be well suited to such situations. With 
Go, there are many situations which can be read out precisely, provided that 
one has the proper tools - ladders, the ability to distinguish between one and 
two eyes; the ability to reduce eyespaces to a single eye with an appropriate 
placement; and so forth. Failure to recognize such situations is like failing 
to spot a pinned piece or a passed pawn.

Every now and then, I have the opportunity to play a pro, or watch a pro 
against other amateur players. Even 4 and 5 dan amateurs find their groups 
crumbling against pro players. But in many cases, the pro simply exploits weak 
shape - reducing groups to the "one eyed state."

Evaluating winning odds depends upon evaluating the final score at the leaf 
nodes, which depends on being able to distinguish between one and two eyes, to 
count liberties in capturing races, to recognize seki, to read ladders, and 
other basic skills.  At some point in the game, an evaluation function should 
be able to quickly and accurately report "oops, just lost ten or twenty points, 
with no compensating gain, therefore the score is -15; this node should be 
reported as a lost game, back up and try something different." The earlier one 
can make such accurate assessments, the better one's game.





  

Never miss a thing.  Make Yahoo your home page. 
http://www.yahoo.com/r/hs___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Robert Jasiek]

Rémi Coulom wrote:
I don't understand what you mean by "push an intrusion of ladder shape 
into the own territory like tooth paste".


The game below is a 9 stone handicap game between me and Mogo. It is my 
second game against Mogo, after a 7x7 test to understand the GUI and a 
first even game (further below). I do not know how to set up free 
handicap placement yet, so the first few moves are a sort of emulation 
to encourage Mogo to accept a free handicap. Its handicap placement 
style is very similar to mine. (In fact, Mogo plays pretty similar to my 
style in the fuseki.) Mogo shows good attacking and some moves are high 
dan level (while others are double digit kyu level; these occur only as 
systematic exceptions as with tooth paste or, as others have pointed 
out, local deep tactical reading; obviously these are the places to 
embed UCT into a context of go knowledge). The UCT program fuseki is 
about 3 dan level. (You know, I am in a position to judge about the 
seemingly "random" style.)


Bad tooth paste ladder pushing moves were:

99, 101, 103, 105, 107, 109, 131

Impressive moves:

73, 139, 159, 161

***

9 stone game

***


(;SZ[19]FF[4]AP[GOWrite:2.1.24]CA[UTF-8]GM[1]PW[ ]PB[MoGo]OT[10 moves / 
2 min]KM[7.5]GN[ ]DT[2007-12-08]TM[1200.0]RE[B+3.5]

;BL[119.0]B[dd]
;W[tt]WL[118.0]
;BL[119.0]B[tt]
;W[jj]WL[94.0]
;BL[91.0]B[pp]
;W[od]WL[92.0]
;BL[91.0]B[dp]
;W[pi]WL[87.0]
;BL[73.0]B[nm]
;W[tt]WL[83.0]
;BL[57.0]B[fn]
;W[tt]WL[81.0]
;BL[39.0]B[hd]
;W[tt]WL[79.0]
;BL[24.0]B[jn]
;W[tt]WL[77.0]
;BL[8.0]B[fi]
;W[tt]WL[74.0]
;BL[-8.0]B[hk]
;W[tt]WL[63.0]
;BL[-18.0]B[mj]
;W[tt]WL[59.0]
;BL[-29.0]B[hh]
;W[tt]WL[56.0]
;BL[-40.0]B[jh]
;W[ci]WL[45.0]
;BL[-50.0]B[cn]
;W[jq]WL[43.0]
;BL[-57.0]B[iq]
;W[ir]WL[41.0]
;BL[-73.0]B[jr]
;W[kr]WL[36.0]
;BL[-83.0]B[jp]
;W[js]WL[24.0]
;BL[-101.0]B[lq]
;W[hq]WL[22.0]
;BL[-106.0]B[ip]
;W[kq]WL[20.0]
;BL[-116.0]B[lp]
;W[pm]WL[16.0]
;BL[-129.0]B[mf]
;W[lc]WL[4.0]
;BL[-138.0]B[mb]
;W[nc]WL[0.0]
;BL[-150.0]B[jd]
;W[bf]WL[-40.0]
;BL[-167.0]B[df]
;W[dc]WL[-47.0]
;BL[-172.0]B[ec]
;W[cc]WL[-50.0]
;BL[-184.0]B[cd]
;W[bd]WL[-51.0]
;BL[-197.0]B[be]
;W[bc]WL[-59.0]
;BL[-215.0]B[bl]
;W[cf]WL[-79.0]
;BL[-225.0]B[dg]
;W[ed]WL[-85.0]
;BL[-239.0]B[ee]
;W[eb]WL[-93.0]
;BL[-249.0]B[fc]
;W[ce]WL[-96.0]
;BL[-266.0]B[mc]
;W[md]WL[-99.0]
;BL[-278.0]B[ld]
;W[kd]WL[-112.0]
;BL[-283.0]B[le]
;W[lb]WL[-128.0]
;BL[-301.0]B[kc]
;W[kb]WL[-130.0]
;BL[-315.0]B[pn]
;W[qn]WL[-134.0]
;BL[-325.0]B[qm]
;W[ro]WL[-142.0]
;BL[-338.0]B[pl]
;W[rm]WL[-152.0]
;BL[-351.0]B[om]
;W[qk]WL[-155.0]
;BL[-366.0]B[ke]
;W[of]WL[-176.0]
;BL[-376.0]B[me]
;W[nd]WL[-179.0]
;BL[-386.0]B[jb]
;W[fd]WL[-192.0]
;BL[-400.0]B[nb]
;W[ob]WL[-194.0]
;BL[-418.0]B[fq]
;W[gr]WL[-208.0]
;BL[-435.0]B[la]
;W[na]WL[-214.0]
;BL[-445.0]B[ka]
;W[pf]WL[-241.0]
;BL[-455.0]B[fe]
;W[de]WL[-244.0]
;BL[-472.0]B[ch]
;W[bh]WL[-252.0]
;BL[-482.0]B[di]
;W[cj]WL[-254.0]
;BL[-499.0]B[ck]
;W[dj]WL[-257.0]
;BL[-511.0]B[ej]
;W[dk]WL[-258.0]
;BL[-523.0]B[dl]
;W[ek]WL[-260.0]
;BL[-542.0]B[fk]
;W[el]WL[-263.0]
;BL[-558.0]B[em]
;W[fl]WL[-269.0]
;BL[-570.0]B[gl]
;W[mh]WL[-284.0]
;BL[-584.0]B[nh]
;W[ng]WL[-288.0]
;BL[-603.0]B[bj]
;W[bi]WL[-318.0]
;BL[-619.0]B[mi]
;W[mg]WL[-348.0]
;BL[-637.0]B[ki]
;W[gj]WL[-378.0]
;BL[-650.0]B[gk]
;W[eh]WL[-391.0]
;BL[-665.0]B[ei]
;W[dh]WL[-403.0]
;BL[-677.0]B[cg]
;W[ef]WL[-437.0]
;BL[-683.0]B[eg]
;W[ge]WL[-441.0]
;BL[-694.0]B[ff]
;W[gd]WL[-442.0]
;BL[-711.0]B[bg]
;W[ag]WL[-444.0]
;BL[-730.0]B[gf]
;W[he]WL[-449.0]
;BL[-750.0]B[rp]
;W[qq]WL[-465.0]
;BL[-762.0]B[qo]
;W[rn]WL[-467.0]
;BL[-775.0]B[qp]
;W[rq]WL[-473.0]
;BL[-794.0]B[er]
;W[pq]WL[-497.0]
;BL[-805.0]B[oq]
;W[sp]WL[-501.0]
;BL[-822.0]B[hb]
;W[op]WL[-519.0]
;BL[-830.0]B[po]
;W[nq]WL[-523.0]
;BL[-848.0]B[np]
;W[or]WL[-525.0]
;BL[-867.0]B[no]
;W[dm]WL[-530.0]
;BL[-872.0]B[cl]
;W[fm]WL[-531.0]
;BL[-882.0]B[en]
;W[gm]WL[-533.0]
;BL[-892.0]B[hm]
;W[gn]WL[-537.0]
;BL[-910.0]B[gc]
;W[fo]WL[-550.0]
;BL[-920.0]B[go]
;W[hn]WL[-555.0]
;BL[-935.0]B[in]
;W[eo]WL[-566.0]
;BL[-940.0]B[dn]
;W[aj]WL[-580.0]
;BL[-959.0]B[pc]
;W[oc]WL[-592.0]
;BL[-976.0]B[hp]
;W[gq]WL[-604.0]
;BL[-991.0]B[fp]
;W[al]WL[-607.0]
;BL[-1006.0]B[bk]
;W[fh]WL[-636.0]
;BL[-1021.0]B[fj]
;W[fg]WL[-647.0]
;BL[-1026.0]B[ef]
;W[hf]WL[-651.0]
;BL[-1031.0]B[gg]
;W[hg]WL[-652.0]
;BL[-1036.0]B[gh]
;W[bm]WL[-654.0]
;BL[-1041.0]B[cm]
;W[ak]WL[-661.0]
;BL[-1057.0]B[bn]
;W[fb]WL[-721.0]
;BL[-1070.0]B[pk]
;W[pj]WL[-723.0]
;BL[116.0]OB[9]B[ni]
;W[oh]WL[-737.0]
;BL[97.0]OB[8]B[lr]
;W[fs]WL[-750.0]
;BL[80.0]OB[7]B[cr]
;W[es]WL[-757.0]
;BL[62.0]OB[6]B[am]
;W[ah]WL[-775.0]
;BL[44.0]OB[5]B[ds]
;W[fr]WL[-788.0]
;BL[24.0]OB[4]B[ql]
;W[rl]WL[-791.0]
;BL[11.0]OB[3]B[rk]
;W[qj]WL[-793.0]
;BL[-2.0]OB[2]B[lh]
;W[gb]WL[-806.0]
;BL[-26.0]OB[1]B[hc]
;W[eq]WL[-814.0]
;BL[120.0]OB[10]B[dr]
;W[gp]WL[-818.0]
;BL[114.0]OB[9]B[ep]
;W[ho]WL[-820.0]
;BL[100.0]OB[8]B[oj]
;W[kp]WL[-836.0]
;BL[90.0]OB[7]B[ko]
;W[io]WL[-843

Re: [computer-go] How does MC do with ladders?

[Raymond Wold]

On Tue, 2007-12-11 at 11:42 -0500, Don Dailey wrote:
> In fact, this illustrates a wonderful strength of these programs.

Only it's not strength to ignore a move to your benefit, when it's
something a 20 kyu human can read out. Nor is it strength when you play
out a dead ladder, no matter if you're behind.

Pure MC will /not/ cure cancer.

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

Re: [computer-go] How does MC do with ladders?

[Magnus Persson]

Since Valkyria is slow anyway, I can have it read ladders in the  
simulations. The ladder code is really fast and a little buggy, but  
works often enough to not cause major problems. I never tested the  
benefits of the ladder code it just appeared to be much stronger.


-Magnus


Quoting Rémi Coulom <[EMAIL PROTECTED]>:


Robert Jasiek wrote:

Mark Boon wrote:

Question: how do MC programs perform with a long ladder on the board?



Crazy Stone handles ladder with progressive widening. Ladder atari is
usually ranked first or very high in the move list, and ladder
extension lower. So, the tree-search part usually does not read out the
ladder completely, but prunes the extension. It seems to work well in
practice. Because progressive widening will include the ladder
extension at some point, Crazy Stone may still play ladder extensions
if it finds reasons to do so.

According to some discussions I had with Sylvain in Amsterdam, MoGo's
approach is a little more primitive. If I remember correctly, it
completely prunes ladder extensions. I am not sure if it is done only
at the root, or inside the tree search too.

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




--
Magnus Persson
Berlin, Germany
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How does MC do with ladders?

[Don Dailey]

Mark Boon wrote:
> Question: how do MC programs perform with a long ladder on the board?
>
> My understandig of MC is limited but thinking about it, a crucial long
> ladder would automatically make the chances of any playout winning
> 50-50, regardless of the actual outcome of the ladder. If this is the
> case then:
>
> a) when winning it will avoid all ladders, even the ones working for it.
> b) when losing it will look for situations involving ladders, even
> when they're not working.
>
> Is this correct? Probably on 9x9 this is not a problem because all
> ladders will be relatively short.
>
> Mark
The best first search is pretty focused with good heavy play-outs but
the strength of MC programs is definitely not tactics and I think long
ladders are a problem - though not as much as one might think.   

I think your analysis is more or less correct - if it can't read a
ladder it is likely to see it as rather ambiguous which pushes the
winning probability towards even.  If it's happy with it's position
otherwise, it would probably gravitate away from them and otherwise
gravitate towards them just as you say.

In fact, this illustrates a wonderful strength of these programs.   They
are very pragmatic even about what they don't do well.Any good human
player has the sense to avoid tricky situations he doesn't understand if
he is winning anyway. And a good human in a game losing situation
knows that it's time to introduce some risk if the straightforward
conservative play is leading down a dead end.In other words, the MC
programs do not always calculate risk correctly (otherwise the score
would always be 1 or 0)  but they deal gracefully with it and they are
"true to themselves",  a characteristic we humans lack.We prefer to
struggle with self-doubt many times which often clouds our judgment.   
Naturally,  if we can improve our judgment it's a win and this applies
equally to MC programs.

I myself have used this same principle in a chess tournament.   I was
playing a much weaker player and ended up with a losing position due to
bad play on my part and good play on my opponents part.   However, at
one point it became clear that I was going to lose if I continued with
standard play,  I was not making it difficult for my opponent. I
discovered an interesting (but unsound) king side attack but it was
profound enough that it took some work for me to see that it was
unsound.   It turned out that there was a clever defense that would
have given the opponent the win and the game would be over quickly if he
could find this move.   Fortunately,   it also turned out that the
"clearly obvious" defense was losing - but it was not easy to see this.  

I think at this point I played like a monte carlo player.   I estimated
my odds of winning  with the swindle to be much greater than the odds of
winning with correct play (correct in the sense that it delayed the loss
as much as possible.)

So I did exactly what MC programs do,  in a losing position I chose the
murky waters.   In this case I won the game by playing the opponent
instead of the board.  In that same tournament a friend of mine also
made a calculated choice to avoid a line of play against a weaker
opponent that was very likely to end in a draw, even though the move he
chose instead was inferior. He wanted to win,  not draw and he chose
the move that he calculated would give him the best chances of "not
drawing." In other words, as he admitted later, the move he chose
gave him a greater chance of losing or winning  instead of drawing.
His gamble also payed off in this case.

It's usually non-productive to play the odds in this way because we are
actually playing the opponent, not the board and it's more important to
play the board, not to mention the fact that playing the opponent
usually means purposely changing your own style - usually weakening you
game a bit. Still,  in some situations the choice is not so
difficult and you can get away with playing the opponent by applying the
MC principle of estimated your winning chances.

Of course MC programs don't consider the opponent when the make these
estimates,  just the position.

- Don




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

Re: [computer-go] How does MC do with ladders?

[Rémi Coulom]

Robert Jasiek wrote:

Mark Boon wrote:

Question: how do MC programs perform with a long ladder on the board?


Mogo makes the 20k mistake to push an intrusion of ladder shape into 
the own territory like tooth paste. I do not know if this is caused by 
reading ladder-like, by juding the adjacent life wrongly (in a nakade 
there are often more death than life sequences even if a simple vital 
point makes life), or by the short but wrong pattern database. The UCT 
programmers should tell us.



Hi,

I don't understand what you mean by "push an intrusion of ladder shape 
into the own territory like tooth paste".


Crazy Stone handles ladder with progressive widening. Ladder atari is 
usually ranked first or very high in the move list, and ladder extension 
lower. So, the tree-search part usually does not read out the ladder 
completely, but prunes the extension. It seems to work well in practice. 
Because progressive widening will include the ladder extension at some 
point, Crazy Stone may still play ladder extensions if it finds reasons 
to do so.


According to some discussions I had with Sylvain in Amsterdam, MoGo's 
approach is a little more primitive. If I remember correctly, it 
completely prunes ladder extensions. I am not sure if it is done only at 
the root, or inside the tree search too.


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

Re: [computer-go] How does MC do with ladders?

[Robert Jasiek]

Mark Boon wrote:

Question: how do MC programs perform with a long ladder on the board?


Mogo makes the 20k mistake to push an intrusion of ladder shape into the 
own territory like tooth paste. I do not know if this is caused by 
reading ladder-like, by juding the adjacent life wrongly (in a nakade 
there are often more death than life sequences even if a simple vital 
point makes life), or by the short but wrong pattern database. The UCT 
programmers should tell us.


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