[Computer-go] Semeais

[Don Dailey]

On Fri, Jan 14, 2011 at 4:59 PM, Brian Sheppard <sheppardco at aol.com> wrote:

> >Many Faces does something like this, and it does not work well.
>
> Well, you don't have a complete solution. But I guarantee that it works
> better than what Pebbles does.
>
> Here's the thing: search engines will push every heuristic until something
> breaks down.


It is not clear to me that this is true.  What do you mean by "breaks down?"

In general, if you can do something to help,  even if it's not really enough
or ideal,   a search engine will respond in a positive way.   That is the
beauty of search.

It's true that if you try to solve a problem incorrectly,  the program will
often find the holes, but that is not the same as "breaking down."
Breaking down to me is that your change makes it play worse.



> Your solution breaks down when it faces two large semeais.
> Pebbles solution breaks down when it faces *one* *small* semeai.
>
> Pebbles uses only the base RAVE/UCT framework. It has playout heuristics
> for
> one/two liberty situations, and those help a lot. But Pebbles cannot even
> reliably identify a semeai.
>
> Your heuristics are much better than that.
>
> Brian
>
> -----Original Message-----
> From: computer-go-bounces at dvandva.org
> [mailto:computer-go-bounces at dvandva.org] On Behalf Of David Fotland
> Sent: Friday, January 14, 2011 12:59 PM
> To: computer-go at dvandva.org
> Subject: Re: [Computer-go] Semeais
>
> Many Faces does something like this, and it does not work well.  Many Faces
> includes a static semeai solver with local search, and this is applied in
> the tree.  If anyone has many faces you can set up a semeai and ask for
> group status.  This shows you the result of the static life/death/strength
> analysis, and you can see the kind of semeai it will leave for the
> playouts.
>
> The problem comes when the tree finds the semeai, and the correct move is
> made in the tree to resolve the semeai.  At the exit from the tree, any
> semeai on the board has been resolved (in that one side will win by
> typically one move).  The tree won't waste extra moves in the semeai, so at
> tree exit, the winning side is one move ahead.
>
> Then the playout has no clue about the semeai, and lets the losing side win
> perhaps 40% of the time.
>
> Semeai knowledge is required in the playout.  The tree must leave resolved
> semeai positions on the board which the playouts can't understand,
> introducing a large bias.
>
> David
>
> > -----Original Message-----
> > From: computer-go-bounces at dvandva.org [mailto:computer-go-
> > bounces at dvandva.org] On Behalf Of Kahn Jonas
> > Sent: Friday, January 14, 2011 9:35 AM
> > To: computer-go at dvandva.org
> > Subject: Re: [Computer-go] Semeais
> >
> > On Fri, 14 Jan 2011, terry mcintyre wrote:
> >
> > > It is expensive to solve semeai during every playout, but what if
> semeai
> > > solutions were done once per game move (or even less frequently), and
> > the
> > > information obtained were then amortized over many playouts?
> > >
> > > The top-level analysis would solve the semeai, and create a self-
> > updating
> > > set of move-response triggers. The tricky bit is that the indicated
> > > behavior must correctly adapt to all possible moves during a complete
> > > playout, in a manner which does not interfere with other simultaneous
> > > playouts.
> >
> > I think that was the most common idea. At least that's how I understand
> > Olivier's ideas, and my vague suggestion also fits that description.
> >
> > I am copying the suggestion back here to add a remark.
> > >> We may make a local tree (moves only in the zone or that take away a
> > >> liberty of one of the groups), first without tenukis, and see who
> wins.
> > >> We may then add tenukis for the winning side.
> >
> > (Tenukis mean pass move since it's a local tree.)
> >
> > >> During playouts, (we may use that during playouts rather than at the
> > >> beginning), when a move is played in the area, the winning side has to
> > >> follow the tree along a winning line.
> >
> > In fact, we also need to make the tree for when the other side is
> > winning: taking ko into account during playouts is out-of-reach today,
> > but by the time we leave the MCTS tree to enter the playout, there may
> > have been a move added for free in the local area (ko in the tree). And
> > then the other side is the winner for this playout.
> >
> > Jonas
> > _______________________________________________
> > Computer-go mailing list
> > Computer-go at dvandva.org
> > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20110114/8f96feef/attachment.html>