[Computer-go] Semeais

[Kahn Jonas]

On Thu, 13 Jan 2011, Petr Baudis wrote:

>  Hi!
>
> On Thu, Jan 13, 2011 at 12:52:58PM +0100, Kahn Jonas wrote:
>> By the way, has anybody tried the most basic way to settle semeais in
>> playouts? I mean:
>> * Spot semeais (not basic at all, but probably necessary for almost all
>> approaches).
>
>  I think one problem is, most programs use only chain information, not
> group information (well, "group" is chain in Pachi lingo, but that is
> rather unfortunate historical remnant) - then, in many cases part of an
> eye will be considered a different group, etc. Another problem is that
> during simulation, most programs do not judge chain _safety_ at all;
> they do not check if it can live independently, is seki, is making
> nakade within larger group (Pachi checks this newly now), or is in
> semeai. The problem is, this kind of analysis is very expensive. It is
> difficult to code it without many bugs in the first place, it will bias
> the simulations even worse than now if inaccurate, and it is very slow
> so it must work well even with small number of playouts.
>
>  (Maybe Zen and Valkyria are doing high-level analysis like above,
> though...)
>
>  There is plenty of places where to put high level analysis. But it
> takes a lot of time and the progress is slow. I'm myself rather trying
> for more domain-independent techniques to address semeai - though I also
> sense that likely, adding some stone safety analysis will be inevitable
> for pro-level 19x19 performance in the end.

The MC way to treat groups might be something along those lines:
* a group is a set of stones that die or live all together in playouts.
That is if P(stone A lives and stone B lives) is almost equal to P(A
lives or B lives), they are in the same group.
* a semeai is then two groups of stones with anticorrelation
P((white stones live and black stones live) OR (white stones die and
black stones die)) almost 0, whereas P(B lives) and P(W lives) both
nonzero and non-one.


>  (Yes, I guess I'm optimistic in the last few days ;-), but now I'm
> rather convinced that MCTS can reach pro-level performance in a few
> years; it scales well with hardware, and there is still huge amount
> of research going on. The problem for most people I think is certainly
> not a shortage of very promising ideas to try, but time to code them
> and most importantly debug them - in my experience, that can easily take
> 10x the programming time, not just checking that the code finally does
> what you want in the situation you want, but also all the crazy things
> it does in variety of other situations.)
>
>> * Play all the moves in the semeai before going to usual playouts.
>
>  You forgot "in correct order". This can be also very complex
> decision-making process.

Well, I thought, after having solved the semeai in one way or another.

If we reuse the definition of semeai above:

We now have an area that is semeai (all the intersections strongly
correlated to the stones above).
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.

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.


Of course I'm sure many people have tried and try ideas like that, and
that it does not work because of the 10x debugging time you mention with
all corner cases...

Jonas